使用C语言实现单链表的功能（带头节点）

目录

1.单链表定义

2. 单链表特点

3.顺序表和单链表的对比

4.单链表的定义

5.单链表的相关操作

（1）初始化（申请头节点）

（2）销毁单链表

（3）按序查找第i个节点和按值查找节点的存在性

（4）第i位置插入节点

（5）指定节点的后插操作和前插操作

（6）删除指定节点，删除指定值的节点，按序删除第i个节点

（7）求表长和打印

（8）主函数

（9）测试

---

1.单链表定义

每个节点除了存放数据元素外，还要存储指向下一个节点的指针。

2. 单链表特点

（1）链式存储结构：不要求逻辑上相邻的元素在物理位置上也相邻。

（2）包含两个域：数据域和指针域，其中数据域用来存储数据元素信息，指针域用来存储直接后继存储位置。

（3）头指针：整个链表的存取必须从头指针位置开始，头指针指示链表中的第一个节点的存储位置。

（4）尾指针：最后一个数据元素没有直接后继，因此线性链表中最后一个节点的指针为“空”（NULL）。

（5）头节点：头节点的数据域可以不用存储任何信息，也可存储如线性表的长度子类的附加信息，头节点的指针域指向第一个节点的指针。但是有了头节点对于后面的插入，删除等操作非常有帮助。

3.顺序表和单链表的对比

   顺序表：

          优点：可以随机的存取，存储密度高；

          缺点：要求大片连续的存储空间；

   单链表：

           优点：不要去大片连续的空间，改变容量方便；

           缺点：不能进行随机的存取，需要耗费一点时间才能访问到，如果是第一个节点，O（1），如果是最后一个节点O（n）.

使用C语言实现动态顺序表

使用C语言实现静态顺序表

4.单链表的定义

#include
#include
 
typedef int ElemType;
 
typedef struct LNode {
	ElemType data;
	struct LNode*next;
}LNode,*LinkList;
 
//清单列表
void MenuLinkList(){
	printf("-------------1.插入操作-------------\n");
	printf("-------------2.定位插入操作---------\n");
	printf("-------------3.按序查找操作---------\n");
	printf("-------------4.按值查找操作---------\n");
	printf("-------------5.定位删除操作---------\n");
	printf("-------------6.按值删除元素---------\n");
	printf("-------------7.删除整个表-----------\n"); 
	printf("-------------8.表的长度-------------\n");
	printf("-------------9.打印操作-------------\n");
	printf("-------------10.结束操作-------------\n");
} 

5.单链表的相关操作

（1）初始化（申请头节点）

//初始化不带头节点
void InitList(LinkList&L){
	L=(LNode*)malloc(sizeof(LNode));
	if(L==NULL){
		printf("内存分配失败!\n");
		return ;
	}
	L->next=NULL;
	printf("空间申请成功!\n");
} 

（2）销毁单链表

//销毁链表
void DestryLinkList(LinkList&L,int flag=1){
	//这里不删除头节点 
	LNode*p=L;
	while(p->next!=NULL){
		LNode*s=p->next;
		p->next=s->next;
		free(s);
	}
	//当flag==9表示结束操作，则删除整个表 
	if(flag==10){
		free(p);
	}
} 

（3）按序查找第i个节点和按值查找节点的存在性

//获取单链表的第i个节点 
LNode*GetElem(LinkList L,int i){
	int j=1;
	LNode*p=L->next;
	if(i<0)return NULL;
	if(i==0)return L->next;
	while(p!=NULL&&j
		p=p->next;
		j++;
	}
	return p;
}
//按值查找节点是否存在
LNode*FindElem(LinkList L,ElemType e){
	LNode*p=L->next;
	while(p!=NULL&&p->data!=e){
		p=p->next;
	}
	return p;
} 

（4）第i位置插入节点

//按位序查找第i个节点 
LNode*FindLNode(LinkList L,int i){
	if(i<1){
		printf("不符合插入节点位置!\n");
		return NULL;
	}
	LNode*p=L;
	int j=0;
	while(p!=NULL&&j-1){
		p=p->next;
		j++;
	}
	if(p==NULL){
		printf("不符合插入节点位置!\n");
		return NULL;
	}
	return p; 
} 
//按位序插入节点操作
void ListInsert(LinkList L,int i,ElemType e){
	LNode*p=FindLNode(L,i);
	LNode*s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	printf("插入节点成功!\n");
} 

（5）指定节点的后插操作和前插操作

 

//指定节点的后插操作
LNode* InsertNextNode(LNode*p,ElemType e){
	if(p==NULL){
		printf("插入位置不合法!\n");
		return NULL;
	}
	LNode*s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL){
		printf("内存分配失败!\n");
		return NULL;
	}
	s->data=e;
	s->next=p->next;
	p->next=s;
	printf("插入节点成功!\n");
	return s;
} 
//指定节点前的插入操作
void InsertPriorLNode(LNode*p,ElemType e){
	if(p==NULL){
		printf("插入位置不合法!\n");
		return ;
	}
	LNode*s=(LNode*)malloc(sizeof(LNode));
	ElemType temp=p->data;
	s->data=temp;
	p->data=e;
	s->next=p->next;
	p->next=s;
	printf("插入节点成功!\n");
} 

（6）删除指定节点，删除指定值的节点，按序删除第i个节点

 

//删除指定节点
void DeleteElemLNode(LNode*p){
	if(p==NULL){
		printf("删除不合法!\n");
		return ;
	}
	LNode*q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
} 
//删除指定值节点(删除所有这样的值) 
void DeleteLNode(LinkList&L,ElemType e){
	if(L->next==NULL){
		printf("表为空!\n");
		return ;
	}
	LNode*p=L->next;
	LNode*s,*q;
	while(p!=NULL){
		LNode*temp;
		temp=p; 
		if(p->data==e&&p->next!=NULL){
			DeleteElemLNode(temp);
		}else{
			//针对删除尾节点 
			q=p;
			s->next=p->next;
			free(q);
		}
		//s用来记录p的前一个节点 
		s=p;
		//如果存在连续的几个值和e相等，则不进行p=p->next 
		if(p->data!=e){
			p=p->next;
		}
	}
	printf("删除指定值节点成功!\n");
} 
//按序删除第i个节点
void DeleteOrder(LinkList&L,int i,ElemType&e){
	if(L->next==NULL){
		printf("表为空!\n");
		return ;
	}
	LNode*p=L->next;
	int j=1;
	while(p!=NULL&&j1){
		p=p->next;
		j++;
	}
	if(p==NULL){
		printf("删除位置不合法!\n");
		return ;
	}
	LNode*s=p->next;
	e=s->data;
	p->next=s->next;
	free(s);
	printf("删除节点成功!\n");
} 

（7）求表长和打印

//表的长度
int LinkListLength(LinkList L){
	int len=0;
	LNode*p=L;
	while(p->next!=NULL){
		len++;
		p=p->next;
	}
	return len;
} 
//打印链表的节点
void PrintLinkList(LinkList L){
	LNode*p=L->next;
	while(p!=NULL){
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

（8）主函数

int main(){
	LinkList L;
	InitList(L);
	//对顺序表进行插入操作
	ElemType x;
	int flag=-1;
	LNode*p=L; 
	//各种操作 
	while(1) {
		int i=0;
		ElemType e=0;
		MenuLinkList();
		printf("请输入操作: ");
		scanf("%d",&flag);
		int len=0;
		LNode*s;
		switch(flag){
			case 1:
				printf("请输入元素(-1_end): ");
				scanf("%d",&x);
				while(x!=-1) {
					p=InsertNextNode(p,x);
					printf("请输入元素(-1_end): ");
					scanf("%d",&x);
				} 
				break;
			case 2:
				printf("请输入元素插入位置: \n");
				scanf("%d",&i); 
				printf("请输入元素: ");
				scanf("%d",&x);
				ListInsert(L,i,x);
				break;
			case 3:
				printf("请输入查找元素位置: ");
				scanf("%d",&i);
				s=GetElem(L,i);
				if(s!=NULL){
					printf("查找的元素为 = %d\n",s->data);
				}
				break;
			case 4:
				printf("请输入要查找的值是否存在: ");
				scanf("%d",&x);
				s=FindElem(L,x);
				if(s!=NULL){
					printf("查找的元素存在!\n");
				}else{
					printf("查找的元素不存在!\n");
				}
				break;
			case 5:
				printf("请输入删除的定位位置: ");
				scanf("%d",&i);
				DeleteOrder(L,i,e);
				printf("删除的元素为 = %d\n",e);
				break;
			case 6:
				printf("请输入要删除的元素: ");
				scanf("%d",&e);
				DeleteLNode(L,e);
				break;
			case 7:
				DestryLinkList(L);
				printf("删除成功!\n");
				break;
			case 8:
				len=LinkListLength(L);
				printf("表的长度 = %d\n",len);
				break;
			case 9:
				PrintLinkList(L);
				break;
			default:
				DestryLinkList(L,flag);
				printf("结束操作\n");
		}
		if(flag==10){
			break;
		}
	}
	return 0;
}

（9）测试