單循環連結清單的相關操作

單循環連結清單的相關操作

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct LinkListNode
{
	int data;
	struct LinkListNode* next;
}node,*LinkList;  //結構體變量類型

void  GreatLinklistTail(LinkList* head); // 建立連結清單
void LinkListInsert(LinkList* head); //插入節點
void LinkListFind(LinkList* head); //查找資料 
void LinkListnode_Delete(LinkList* head); //删除節點
void LinkListDatePrint(LinkList* head);  //連結清單的輸出
void LinkListClean(LinkList* head);   //連結清單的整表删除 
/**
*為了建立、使用、維護連結清單，對連結清單的操作如下：
*建立連結清單
*周遊連結清單
*尾部追加
*删除結點
*查找結點
*/
/******************************************************************************/
int main(void)
{
	LinkList head;
	int i;
	printf("*************************單循環連結清單操作***************************\n\n");
	printf("1.初始化循環連結清單\n\n2.插入節點 \n\n3.删除節點 \n\n4,查找節點\n\n0.釋放記憶體操作完成\n\n"); 
	while(1)
	{
		scanf("%d", &i);
		switch(i)
		{
		
			case 1:
				{
					printf("下面進行建立連結清單操作！\n"); 
					GreatLinklistTail(&head);
					LinkListDatePrint(&head);
				}
				break;
			case 2:
				{
					printf("下面進行插入節點操作！\n"); 
					LinkListInsert(&head);
					LinkListDatePrint(&head);
				}
				break;
			case 3:
				{ 
				printf("下面進行删除節點操作！\n"); 
				LinkListnode_Delete(&head);
				LinkListDatePrint(&head);
				} 
				break;
			case 4:
				{
					printf("下面進行查找資料操作！\n"); 
					LinkListFind(&head);
				} 
				break;
			
		}
		if(i == 0)
		{
			break;
		}
	}
	printf("連結清單操作結束！\n"); 
	LinkListClean(&head);
	system("pause"); 
	return 0;
}
/**********************************************************************************/

//單循環連結清單初始化操作 
void GreatLinklistTail(LinkList* head)
{
	node *p, *target = NULL;   //聲明節點p 和周遊結構體指針變量 target 
	int i, j;
 
	*head = (LinkList)malloc(sizeof(LinkList)); //為第一個節點開辟記憶體 
	(*head)->next = *head;  //将第一個指針的next 指向第一個節點 
	target = *head;    //令周遊指針 指向第一個節點 
	printf("請輸入所要開辟節點的個數,輸入0退出: \n");
	scanf_s("%d", &i);
	fflush(stdin);

	if(i == 0)
	{
		return ;  //如果輸入 0直接退出程式 
	}
	
	 
	if (i == 1)//當隻要開辟一個節點的時候  令第一個節點的next指向自身形成循環連結清單 
	{
		printf("請輸入要存儲的值：");
		scanf_s("%d", &(*head)->data);
		fflush(stdin);
		
		(*head)->next = *head; //令第一個節點的next指向自身形成循環連結清單 
		printf("單循環連結清單建立完畢！！！\n\n");
	}
	
	else
	{	
		for (j = 1; j <= i; j++)
		{
			
			if(j == 1)  //開辟第一個節點時 
			{	
				printf("請輸入第%d個節點所要存儲的資料：", j);
				p = *head;  //令p指向第一個節點 便于操作 
				scanf_s("%d", &p->data); 
				p->next = p;  //令第一個節點的next指向 自身 
			}
			else  //第一個節點建立結束後 
			{
				p = (node*)malloc(sizeof(node));  //為新節點開辟節點 
				if (!p)
				{
					exit(0);  //配置設定記憶體失敗退出  
				}
				
				printf("請輸入第%d個節點所要存儲的資料：", j);
				scanf_s("%d", &p->data);
	
				p->next = target->next; //先後繼再前驅原則，令p的next指向第一結點 
				target->next = p; //将上一個節點的next 指向p 
				target = p; //周遊節點向後移位 
			}
		}
	}
	printf("單連結清單建立完畢！！！\n\n");
} 

//列印資料函數 
//連結清單資料的輸出 
/*思路：
	1，開辟一個節點p
	2，令節點p指向第一個節點
	3，通過循環列印出每個節點的值
*/
void LinkListDatePrint(LinkList *head)    //輸出循環連結清單的所有元素 
{
	node *p;  
	int j = 1;
	p = *head;
	printf("********************連結清單中的資料********************\n"); 
	do   // 不可用 當型循環 
	{
		printf("第%d個節點存儲的數為：%4d;\n", j , p->data);
		p = p->next;  //循環周遊連結清單算法 
		j++;
	}while(p != *head);  //周遊到最後一個節點為止 
	
	printf("連結清單資料列印完畢！！！\n\n");
}

//連結清單的整表删除
/*思路：
	1,聲明節點p,q
	2,将第一個節點賦給p,下一個賦給 q
	3，循環執行釋放p和将q賦給p操作
*/
void LinkListClean(LinkList* head)
{
	node* p, * q;

	p = *head;
	while (p->next != (*head))  //循環釋放法則 
	{
		q = p->next;
		free(p);
		p = q;
	}  
	printf("單連結清單記憶體釋放成功！！！\n");
}

//連結清單的資料插入操作

void LinkListInsert(LinkList* head) //插入節點
{
	node *p, *s;  //聲明循環周遊結構體指針p 和 插入節點 s 
	int i, j = 1;

	s = (node*)malloc(sizeof(node));  //為要插入的節點開辟記憶體  
	
	s->next = NULL;  //防止成為野指針
	p = *head;  //令循環節點指向頭結點 
	
	printf("請輸入要插入的節點的位置：");
	scanf_s("%d", &i);
	fflush(stdin);

	if (i == 1)
	{
		printf("請輸入第%d個節點要插入的值：\n", i);
		scanf_s("%d", &s->data);  //指派操作  
		fflush(stdin);
		
	for(p = *head; p->next != *head; p= p->next)
		;  //尋找最後一個節點 
	
		s->next = *head;  //先後繼 
		p->next = s;  //尾節點指向s  後前驅  算法 
		*head = s;   //把head 再次換成第一個節點 
	}
	else
	{	
		for (j = 1; j < i-1; j++)
		{
			p = p->next; 将循環指針指向 要插入的前一個節點 
		}

		printf("請輸入第%d個節點要插入的值：\n", i);
		scanf_s("%d", &s->data);
		fflush(stdin);

		s->next = p->next;//令插入的節點的next指向原本的第 i個節點 //先後繼 
		p->next = s;  //後前驅 
		printf("\n");
	}
	printf("節點插入成功！！！\n\n"); 
}
//節點的查找并傳回節點的位置 
/*
思路：
	1，聲明節點 p,開辟節點，指向頭結點
	2， 聲明計數器j 和存儲資料的 容器
	3， 循環查找
*/
void LinkListFind(LinkList* head)  //查找第i個元素
{
	node *target;
	int  i, j = 1;

	printf("請輸入查找的資料：");
	scanf_s("%d", &i);
	fflush(stdin);

	for (target = *head; target->data != i && target->next != *head; target = target->next)
		j++;  //循環周遊尋找最後一個節點 
	printf("該節點的位置是: %d\n\n", j);
}

//單連結清單節點删除操作
void LinkListnode_Delete(LinkList* head)
{
	node *p, *target = NULL;  //聲明節點p指向連結清單的第一個節點
	int i;   //要删除的節點 
	int j = 1; //聲明一個計數器  
	p = *head;  //p節點指向第一個節點 

	printf("請輸入要删除的節點标号：");
	scanf_s("%d", &i);
	fflush(stdin);

	if (i == 1)
	{
		for (target = *head; target->next != (*head); target = target->next)
			;  //循環周遊尋找最後一個節點  
			
		p = *head;
		*head = (*head)->next;
		target->next = *head;
		 
		free(p);
	}
	else
	{
		target = *head;
		for (; j < i - 1; j++)  //尋找要删除節點的前一位 
		{
			target = target->next;
		}
		
		p = target->next;  //将p 指向要删除的節點，  
		target->next = p->next;  //使前一個節點指向後一個節點 
		free(p);
		printf("節點删除成功！！！！\n\n"); 
	}

}