C语言单链表

你的名字 2022-07-15 03:23 216阅读 0赞

学过线性表中的顺序表的都知道，顺序表里的数据在物理内存上是相邻的，所以当我们在顺序表中想要访问下一个元素时可以直接去访问，就像数组一样。但是单链表却不同，单链表的数据存储的位置是动态分配的，也就是说单链表的存储在物理内存上不是相邻的，所以我们就只能通过指针这种方式来把单链表串起来，通过指针来访问下一个结点。

## 单链表结点 ##

单链表的结点里有数据域和指针域，数据域是用来储存数据的，指针域是用来储存直接后继结点的域。

![Center][]

typedef struct Node{
    	int data;//数据域
    	struct Node *next;//指针域
    }LinkList,*Link;

## 创建单链表 ##

这里我创建的是带头头结点的单链表，头结点里并不储存你输入的数据，但可以储存一些例如表长的数据，同时头结点的next指针指向下一个首元结点也就是第一个开始储存数据的结点，单链表结构如下图：

![Center 1][]

在我们创建头结点的同时会用一个指针来指向头结点也就是头指针，这个头指针对于整个链表来说是非常重要的，因为我们每次想要来遍历链表中的数据时必须要先找到头指针然后才能一个一个往下找到所有的数据，所以我们不能把单链表的头指针丢了。还有链表的最后一个结点的指针要指向空，也可以指向头结点，指向头结点之后链表也就成了循环链表，当我们把最后一个结点的指针指向空时，我们就可以判空值来判断是不是最后一个结点。

创建链表的代码：

//创建链表 
    void CreasteList(Link H){//这里H是一个结构体指针，我在声明结构体时Link是带*号的所以这里Link就是Link*
    	Link P,newNode;//P是用来指向头结点的指针，因为我上面也说过了头指针不能动，所以我们就创建一个头指针的副本P，通过P来遍历所有结点
    	int i = 1,s;//s是我们输入的数据，i是此时链表的长度
    	P = H;//将P指向了头结点，也就是创建了一个头指针的副本
    	printf("请输入第%d个元素(-1结束)：",i);
    	scanf("%d",&s);
    	while(s!=-1){//输入-1时结束输入
    		newNode = (Link)malloc(sizeof(LinkList));//为新的结点分配空间
    		newNode->data = s;//将输入的s存入新结点newNode中
    		P->next = newNode;//将此时的P的指针指向新创建的结点
    		P = newNode;//这一点是将P从上一个结点指向新创建的结点，也就是指向此时链表的最后一个结点
    		i++;//链表的长度增加1
    		printf("请输入第%d个元素(-1结束)：",i);
    		scanf("%d",&s);
    	}
    	ListLength = i;//链表的长度
    	P->next = NULL; //最后结束输入后P指向的是最后一个结点，将最后一个结点的next指向空
    }

## 打印单链表 ##

打印单链表我们只需要让头指针的副本P不断的指向下一个结点，遍历了整个链表，结束条件就是尾结点的next为NULL。

![Center 2][]

//打印链表
    void PrintList(Link H){
    	Link P=H;//P指向头结点
    	while(P->next){//判断最后一个结点后继为NULL时结束
    		P = P->next;//不断的指向单链表下一个结点
    		printf("%d ",P->data);	
    	}
    	printf("\n");
    }

## 单链表的删除操作 ##

要删除一个单链表中的一个元素不需要像顺序表那样把删除位置的后面的数据都前移一个位置，只需要改变一下指针的指向就可以了。

![Center 3][]

所以相比顺序表，单链表的删除操作的时间复杂度要低很多。

代码如下：

//删除链表
    void DeleteList(Link H,int i){//H为链表的头指针，i为你要删除的位置
    	Link P = H;
    	Link deleP;//要删除的指针
    	int j = 0;//j是一个标记变量，表示此时是第几个结点
    	if(i<=0||i>ListLength) printf("你要删除的位置不存在！\n");//当i的值小于0或者大于链表长度时，删除的结点不存在
    	else{
    		while(P->next&&j<i-1){//j<i-1时，即当P指向需要删除的第i个结点的前一个结点时结束循环
    			P = P->next;//不断的指向下一个结点
    			j++;
    		}
    		deleP = P->next;//此时的P指向需要删除的结点的前一个结点，deleP指向需要删除的结点
    		P->next = deleP->next;//将P的next指向deleP的next指向的结点，例如上图将2的next指针指向4
    		free(deleP);
    		printf("删除成功！\n");
    		ListLength--;//删除成功后链表长度减1
    	}
    }

## 单链表的插入操作 ##

同样的单链表的插入操作要比顺序表的时间复杂度低很多，单链表插入时不需要把所有元素后移，只需要改变指针的指向。

![Center 4][]

代码如下：

//插入链表 
    void InsertList(Link H,int i){//i为插入的位置
    	Link P = H;//P指向头结点
    	int j=0;
    	if(i<=0||i>ListLength+1) printf("你插入的位置有错误！");//当插入位置小于=0和大于链表长度加1时，插入有误，链表长度加1是因为可以在链表的尾部加结点
    	else{
    		Link cnew = (Link)malloc(sizeof(LinkList));//为需要插入的结点分配空间
    		printf("请输入你要插入的数据:\n");
    		scanf("%d",&(cnew->data)); 
    		while(P->next&&j<i-1){//同样的j<i-1执行结束时P指向了需要插入的位置的前一个结点
    			P = P->next;
    			j++;
    		}
    		cnew->next = P->next;//将新结点的next指向P->next，即如上图将P的next指向4
    		P->next = cnew;//然后将P的next指向新结点
    		printf("插入成功！");
    		ListLength++;//插入成功后链表长度加1
    	}
    }

## 单链表查询的实现 ##

查询时只需将查询的数据和链表的每一个数据进行配对，配对成功时返回此时的数据位置。

// 查询元素
    int FindList(Link H,int s){//s为查询的数据
    	Link P = H;
    	int i=0;
    	while(P->next&&P->data!=s){//结束的判定为P的next为空和数据配对成功时，当配对成功时结束,此时的P的data就是与s配对成功结点
    		i++;
    		P = P->next;
    	}
    	if(i>ListLength||P->data!=s) return 0;//如果i的值大于了链表的长度或者此时的P->data不是s，那么就是链表中没有和s配对成功的结点
    	else return i;//配对成功返回此时的结点的位置
    }

## 所有代码 ##

#include<stdio.h>
    #include<malloc.h>
    int ListLength = 0;//链表长度 
    typedef struct Node{
    	int data;
    	struct Node *next;
    }LinkList,*Link;
    void CreasteList(Link H);//创建链表
    void InsertList(Link H,int i);//插入链表，i为插入位置
    void DeleteList(Link H,int i);//删除，i为删除的位置
    int FindList(Link H,int s);//查询，i为查询的数据，查询链表中是否有这个数据 
    void PrintList(Link H);//打印链表
    int GetListLength(Link H);//获取链表长度 
    void SortInsert(Link H,int s);//有序插入 
    
    
    int main(){
    	Link H;
    	H = (Link)malloc(sizeof(LinkList));//产生头结点
    	CreasteList(H);
    	PrintList(H);
    	SortList(H);
    	PrintList(H);
    	return 0;
    } 
    //创建链表 
    void CreasteList(Link H){
    	Link P,newNode;
    	int i = 1,s;
    	P = H;
    	printf("请输入第%d个元素(-1结束)：",i);
    	scanf("%d",&s);
    	while(s!=-1){
    		newNode = (Link)malloc(sizeof(LinkList));
    		newNode->data = s;
    		P->next = newNode;
    		P = newNode;
    		i++;
    		printf("请输入第%d个元素(-1结束)：",i);
    		scanf("%d",&s);
    	}
    	ListLength = i;
    	P->next = NULL; 
    }
    //打印链表
    void PrintList(Link H){
    	Link P=H;
    	while(P->next){
    		P = P->next;
    		printf("%d ",P->data);	
    	}
    	printf("\n");
    }
    //获取链表长度 
    int GetListLength(Link H){
    	Link P = H;
    	int length = 0;
    	while(P->next){
    		length++;
    		P=P->next;
    	}
    	return length;
    }
    //删除链表
    void DeleteList(Link H,int i){
    	Link P = H;
    	Link deleP;
    	int j = 0;
    	if(i<=0||i>ListLength) printf("你要删除的位置不存在！\n");
    	else{
    		while(P->next&&j<i-1){
    			P = P->next;
    			j++;
    		}
    		deleP = P->next;
    		P->next = deleP->next;
    		free(deleP);
    		printf("删除成功！\n");
    		ListLength--;
    	}
    } 
    //有序插入
    void SortenInsert(Link H,int s){
    	Link P = H;
    	Link newNode = (Link)malloc(sizeof(LinkList));
    	newNode->data = s;
    	while(P->next&&P->next->data<s){
    		P = P->next;
    	}
    	if(P->next==NULL){
    		P->next = newNode;
    		newNode->next = NULL;
    	}else{
    		newNode->next = P->next;
    		P->next = newNode; 
    	}
    	ListLength++;
    } 
    //插入链表 
    void InsertList(Link H,int i){
    	Link P = H;
    	int j=0;
    	if(i<=0||i>ListLength+1) printf("你插入的位置有错误！");
    	else{
    		Link cnew = (Link)malloc(sizeof(LinkList));
    		printf("请输入你要插入的数据:\n");
    		scanf("%d",&(cnew->data)); 
    		while(P->next&&j<i-1){
    			P = P->next;
    			j++;
    		}
    		cnew->next = P->next;
    		P->next = cnew;
    		printf("插入成功！");
    		ListLength++;
    	}
    }
    // 查询元素
    int FindList(Link H,int s){
    	Link P = H;
    	int i=0;
    	while(P->next&&P->data!=s){
    		i++;
    		P = P->next;
    	}
    	if(i>ListLength||P->data!=s) return 0;
    	else return i;
    }

[Center]: /images/20220715/460b829837cb4800816db73a0c145796.png
[Center 1]: /images/20220715/382288c6d7464103b212c5a196a338d6.png
[Center 2]: /images/20220715/c9c9f5a7d7994d95b482785ec9e00da7.png
[Center 3]: /images/20220715/55a7de500c3142f1a9cc74fb4b66b8af.png
[Center 4]: /images/20220715/3d9a3a0a945e4360b6ad5c0a8bec3eae.png