單向鏈表的總結-有解無憂

創建一個結構體（存一個數字和一個結構體指標）

typedef struct _list{
	int date;
	struct _list *next;
}List;

創建鏈表

尾插法：

List* link_list_tail()//尾插法 
{
	int number;
	printf("輸入多個數字添加到鏈表中，輸入q結束\n");
	List *head=(List*)malloc(sizeof(List));
	head->next=NULL;
	List *tail=head;
	while(scanf("%d",&number)==1)
	{
		List *p=(List*)malloc(sizeof(List));
		p->date=number;
		p->next=NULL;
		tail->next=p;
		tail=p;
	}
	getchar();
	return head;
}

頭插法：

List* link_list_head()//頭插法反著的 
{
	int number;
	printf("輸入多個數字添加到鏈表中，輸入q結束\n");
	List *head=(List*)malloc(sizeof(List));
	head->next=NULL;
	while(scanf("%d",&number)==1)
	{
		List *p=(List*)malloc(sizeof(List));
		p->date=number;
		p->next=head->next;
		head->next=p;
	}
	getchar();
	return head;
}

不過頭插法輸入的資料最后讀的時候是反著的

查找某一個值k

List* find(int k,List*head)//查找某值 
{
	List *p=head->next;
	List *q=head;
	while(p)
	{
		if(p->date==k)
		{
			printf("Find\n");
			break;
		}
		q=p;
		p=p->next;
	}
	if(!p)
	{
		printf("No\n");
	}
	return q;//回傳前一個的指標 
}

增加某個數number到第targer個節點

List* add(int targer,int number,List*head)//增加某個數到某個節點 
{
	int i;
	List *p=head;
	for(i=0;i<targer-1&&p;i++)
	{
		p=p->next;//找到它的前一個指標 
	}
	if(p)
	{
		List *tar=(List*)malloc(sizeof(List));
		tar->date=number;
		tar->next=p->next;
		p->next=tar;
		printf("OK\n"); 
	}else
	{
		printf("No\n");
	}
	return p;
}

洗掉某個值k

List* del(List *head,int k)//洗掉某個值 
{
	List*p=head->next;
	List*q=head;
	while(p)
	{
		if(p->date==k){
			printf("Find\n");
			break;
		}
		q=p;
		p=p->next;
	}
	if(!p){
		printf("No\n");
	}else{
		p=p->next;
		free(q->next);
		q->next=p;
		printf("OK\n");
	}
}

鏈表逆置：

原地逆置：

List* ReverseLink(List *head)//原地逆置 
{
	List* p=head->next;
	List* q=p;
	head->next=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		q->next=head->next;
		head->next=q;
	}
}

遞回逆置：

List* ReverseLink_D(List *head)//遞回逆置 
{
	if(head->next==NULL||head==NULL){
		return head;
	}//遞回結束條件
	List *p=ReverseLink_D(head->next);
	List *t=head->next;
	t->next=head;
	head->next==NULL;
	return p;
}

顯示鏈表：

List* print(List*head)//顯示鏈表 
{
	List*p=NULL;
	if(head->next){
		p=head->next;
	}else{
		printf("NO\n");
		return NULL;
	}
	while(p)
	{
		printf("%d ",p->date);
		p=p->next;
	}
	putchar('\n'); 
	return head;
}

洗掉所有鏈表：

List* del_all(List*head)//洗掉所有鏈表 
{
	List*p=head->next->next;
	List*q=head->next;
	head->next=NULL;
	for(;p;q=p,p=p->next)
	{
		free(q);
		
	}
	printf("OK\n");
}

最后綜合一下（可以把上述內容放到一個檔案里面呼叫更方便）

#include<stdio.h>
#include<stdlib.h>
typedef struct _list{
	int date;
	struct _list *next;
}List;
List* link_list_tail()//尾插法 
{
	int number;
	printf("輸入多個數字添加到鏈表中，輸入q結束\n");
	List *head=(List*)malloc(sizeof(List));
	head->next=NULL;
	List *tail=head;
	while(scanf("%d",&number)==1)
	{
		List *p=(List*)malloc(sizeof(List));
		p->date=number;
		p->next=NULL;
		tail->next=p;
		tail=p;
	}
	getchar();
	return head;
}
List* link_list_head()//頭插法反著的 
{
	int number;
	printf("輸入多個數字添加到鏈表中，輸入q結束\n");
	List *head=(List*)malloc(sizeof(List));
	head->next=NULL;
	while(scanf("%d",&number)==1)
	{
		List *p=(List*)malloc(sizeof(List));
		p->date=number;
		p->next=head->next;
		head->next=p;
	}
	getchar();
	return head;
}

List* find(int k,List*head)//查找某值 
{
	List *p=head->next;
	List *q=head;
	while(p)
	{
		if(p->date==k)
		{
			printf("Find\n");
			break;
		}
		q=p;
		p=p->next;
	}
	if(!p)
	{
		printf("No\n");
	}
	return q;//回傳前一個的指標 
}

List* add(int targer,int number,List*head)//增加某個數到某個節點 
{
	int i;
	List *p=head;
	for(i=0;i<targer-1&&p;i++)
	{
		p=p->next;//找到它的前一個指標 
	}
	if(p)
	{
		List *tar=(List*)malloc(sizeof(List));
		tar->date=number;
		tar->next=p->next;
		p->next=tar;
		printf("OK\n"); 
	}else
	{
		printf("No\n");
	}
	return p;
}
List* del(List *head,int k)//洗掉某個值 
{
	List*p=head->next;
	List*q=head;
	while(p)
	{
		if(p->date==k){
			printf("Find\n");
			break;
		}
		q=p;
		p=p->next;
	}
	if(!p){
		printf("No\n");
	}else{
		p=p->next;
		free(q->next);
		q->next=p;
		printf("OK\n");
	}
}
List* del_all(List*head)//洗掉所有鏈表 
{
	List*p=head->next->next;
	List*q=head->next;
	head->next=NULL;
	for(;p;q=p,p=p->next)
	{
		free(q);
		
	}
	printf("OK\n");
}
List* ReverseLink(List *head)//原地逆置 
{
	List* p=head->next;
	List* q=p;
	head->next=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		q->next=head->next;
		head->next=q;
	}
}
List* ReverseLink_D(List *head)//遞回逆置 
{
	if(head->next==NULL||head==NULL){
		return head;
	}//遞回結束條件
	List *p=ReverseLink_D(head->next);
	List *t=head->next;
	t->next=head;
	head->next==NULL;
	return p;
}
List* print(List*head)//顯示鏈表 
{
	List*p=NULL;
	if(head->next){
		p=head->next;
	}else{
		printf("NO\n");
		return NULL;
	}
	while(p)
	{
		printf("%d ",p->date);
		p=p->next;
	}
	putchar('\n'); 
	return head;
}
int main()
{
	List*head=NULL;
	while(1){
		printf("輸入1創建鏈表\n");
		printf("輸入2查找某值\n");
		printf("輸入3插入某數到某個節點\n");
		printf("輸入4洗掉某值\n");
		printf("輸入5逆置鏈表\n");
		printf("輸入6顯示鏈表\n");
		printf("輸入7洗掉整個鏈表\n");
		printf("輸入0結束程式\n");
		int n;
		scanf("%d",&n);
		if(n==0)
		{
			break;
		}
		switch (n){
			case 1:
				head=link_list_tail();
				break;
			case 2:
				printf("輸入需要查找的值\n");
				int k;
				scanf("%d",&k);
				List*p=find(k,head);
				break;
			case 3:
				printf("輸入要插入的節點序號和要插入的值\n");
				int targer,number;
				scanf("%d%d",&targer,&number);
				add(targer,number,head);
				break;
			case 4:
				printf("輸入一個數來洗掉它\n");
				int key;
				scanf("%d",&key);
				del(head,key);
				break;
			case 5:
				printf("逆置鏈表\n");
				ReverseLink(head);
				break;
			case 6:
				printf("顯示鏈表\n");
				print(head);
				break;
			case 7:
				printf("洗掉整個鏈表\n");
				del_all(head);
				break;
			defult:
				break;
		} 
	} 
	return 0;
}

運行結果：

創建一個鏈表：
在這里插入圖片描述
查找鏈表中是否存在某個值：

插入某數到某個節點：

洗掉鏈表中的一個值：

逆置鏈表：

洗掉整個鏈表：

結束程式：

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/238104.html

標籤：其他

上一篇：理想的開放自動化

下一篇：Codeforces Round #691 (Div. 2)