C语言单链表实现方法详解
本文实例讲述了C语言单链表实现方法。分享给大家供大家参考，具体如下：
slist.h
#ifndef__SLIST_H__ #define__SLIST_H__ #include#include #include typedefintElemType; typedefstructNode{//定义单链表中的结点信息 ElemTypedata;//结点的数据域 structNode*next;//结点的指针域 }Node,*PNode; typedefstructList{//定义单链表的链表信息 PNodefirst;//first指向单链表中的第一个结点 PNodelast;//last指向单链表中的最后一个结点 size_tsize;//记录单链表中的结点个数 }List; voidInitList(List*list);//初始化单链表 voidpush_back(List*list,ElemTypex);//在单链表的末尾插入元素 voidpush_front(List*list,ElemTypex);//在单链表的头部插入元素 voidshow_list(List*list);//打印单链表 voidpop_back(List*list);//删除单链表的最后一个元素 voidpop_front(List*list);//删除单链表的第一个元素 voidinsert_val(List*list,ElemTypeval);//将数据元素插入到单链表中（要求此时单链表中的数据元素顺序排列） Node*find(List*list,ElemTypex);//查找单链表中数据值为x的结点 intlength(List*list);//求单链表的长度 voiddelete_val(List*list,ElemTypex);//按值删除单链表中的某个数据元素 voidsort(List*list);//对单链表进行排序 voidreverse(List*list);//逆置单链表 voidclear(List*list);//清除单链表 voiddestroy(List*list);//摧毁单链表 #endif//__SLIST_H__
slist.cpp
#include"slist.h"
voidInitList(List*list){
list->first=list->last=(Node*)malloc(sizeof(Node));//头结点
assert(list->first!=NULL);
list->first->next=NULL;
list->size=0;
}
voidpush_back(List*list,ElemTypex){
//step1：创建一个新的结点
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->next=NULL;
//step2：将新结点插入单链表的表尾
list->last->next=s;
list->last=s;
//step3：更新单链表的长度
list->size++;
}
voidpush_front(List*list,ElemTypex){
//step1：创建一个新的结点
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->next=NULL;
//step2：将新结点插入单链表的表头
s->next=list->first->next;
list->first->next=s;
//step3：判断插入的结点是否是单链表的第一个结点，若是更新链表的尾指针
if(list->size==0)
list->last=s;
//step4：更新单链表的长度
list->size++;
}
voidshow_list(List*list){
//step1：指针p指向单链表的第一个结点
Node*p=list->first->next;
//step2：循环打印结点的信息
while(p!=NULL){
printf("%d->",p->data);
p=p->next;
}
printf("Nul.\n");
}
voidpop_back(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：定义指针p使其指向目标结点的前一个结点
Node*p=list->first;//从头结点开始
while(p->next!=list->last)
p=p->next;
//step3：删除目标结点
free(list->last);
list->last=p;
list->last->next=NULL;
//step4：更新单链表的长度
list->size--;
}
voidpop_front(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：定义指针p使其指向目标结点的前一个结点
Node*p=list->first->next;
//step3：删除目标结点
list->first->next=p->next;
free(p);
//step4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针
if(list->size==1)
list->last=list->first;
//step4：更新单链表的长度
list->size--;
}
voidinsert_val(List*list,ElemTypex){
//step1：创建一个新的结点
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->next=NULL;
//step2：定义指针p使其指向待插入位置的前一个结点
Node*p=list->first;//从头结点开始
while(p->next!=NULL&&p->next->datadata)
p=p->next;
//step3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针
if(p->next==NULL)
list->last=s;
//step4：插入结点
s->next=p->next;
p->next=s;
//step5：更新单链表长度
list->size++;
}
Node*find(List*list,ElemTypex){
//step1：指针p指向单链表的第一个结点
Node*p=list->first->next;
//step2：按照循环顺序查找链表结点
while(p!=NULL&&p->data!=x)
p=p->next;
returnp;
}
intlength(List*list){
returnlist->size;
}
voiddelete_val(List*list,ElemTypex){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：确定结点在单链表中的位置，并判断其是否存在于单链表中
Node*p=find(list,x);
if(p==NULL){
printf("要删除的数据不存在！\n");
return;
}
//step3：判断结点位置是否是表尾
if(p==list->last)//是表尾
pop_back(list);
else{//不是表尾
Node*q=p->next;
p->data=q->data;
p->next=q->next;
free(q);
list->size--;
}
}
voidsort(List*list){
//step1：判断单链表中的结点数是否为0或1
if(list->size==0||list->size==1)return;
//step2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中
Node*s=list->first->next;//指针s指向单链表的第一个节点
Node*p=s->next;//q指向s后面的结点
list->last=s;//单链表的尾指针指向单链表的第一个结点
list->last->next=NULL;//截断链表
//step3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中
while(p!=NULL){
s=p;
p=p->next;
Node*q=list->first;
while(q->next!=NULL&&q->next->datadata)
q=q->next;
if(q->next==NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针
list->last=s;
//将结点重新插入链表
s->next=q->next;
q->next=s;
}
}
voidreverse(List*list){
//step1：判断单链表中的结点数是否为0或1
if(list->size==0||list->size==1)return;
//step2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中
Node*p=list->first->next;
Node*q=p->next;
list->last=p;
list->last->next=NULL;
while(q!=NULL){
p=q;
q=q->next;
p->next=list->first->next;
list->first->next=p;
}
}
voidclear(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：释放单链表中的每一个结点
Node*p=list->first->next;
while(p!=NULL){
list->first->next=p->next;
free(p);
p=list->first->next;
}
//step3：头指针和尾指针重新都指向头结点
list->last=list->first;
//step4：更新链表长度
list->size=0;
}
voiddestroy(List*list){
//step1：清空单链表
clear(list);
//step2：释放头结点
free(list->first);
//step3：头指针和尾指针都赋值为空
list->first=list->last=NULL;
}
main.cpp
#include"slist.h"
voidmain(){
Listmylist;
InitList(&mylist);
ElemTypeitem;
Node*p=NULL;
intselect=1;
while(select){
printf("*******************************************\n");
printf("*[1]push_back[2]push_front*\n");
printf("*[3]show_list[4]pop_back*\n");
printf("*[5]pop_front[6]insert_val*\n");
printf("*[7]find[8]length*\n");
printf("*[9]delete_val[10]sort*\n");
printf("*[11]reverse[12]clear*\n");
printf("*[13*]destroy[0]quit_system*\n");
printf("*******************************************\n");
printf("请选择：>>");
scanf("%d",&select);
if(select==0)break;
switch(select){
case1:
printf("请输入要插入的数据（-1结束）:>");
while(scanf("%d",&item),item!=-1){
push_back(&mylist,item);
}
break;
case2:
printf("请输入要插入的数据（-1结束）:>");
while(scanf("%d",&item),item!=-1){
push_front(&mylist,item);
}
break;
case3:
show_list(&mylist);
break;
case4:
pop_back(&mylist);
break;
case5:
pop_front(&mylist);
break;
case6:
printf("请输入要插入的数据:>");
scanf("%d",&item);
insert_val(&mylist,item);
break;
case7:
printf("请输入要查找的数据:>");
scanf("%d",&item);
p=find(&mylist,item);
if(p==NULL)
printf("要查找的数据在单链表中不存在！\n");
break;
case8:
printf("单链表的长度为%d\n",length(&mylist));
break;
case9:
printf("请输入要删除的值:>");
scanf("%d",&item);
delete_val(&mylist,item);
break;
case10:
sort(&mylist);
break;
case11:
reverse(&mylist);
break;
case12:
clear(&mylist);
break;
//case13:
//destroy(&mylist);
//break;
default:
printf("选择错误,请重新选择！\n");
break;
}
}
destroy(&mylist);//程序结束，摧毁链表
}
附：单链表优化版本
slist.h
#ifndef__SLIST_H__ #define__SLIST_H__ #include#include #include typedefintElemType; typedefstructNode{//定义单链表中的结点信息 ElemTypedata;//结点的数据域 structNode*next;//结点的指针域 }Node,*PNode; typedefstructList{//定义单链表的链表信息 PNodefirst;//first指向单链表中的第一个结点 PNodelast;//last指向单链表中的最后一个结点 size_tsize;//记录单链表中的结点个数 }List; voidInitList(List*list);//初始化单链表 voidpush_back(List*list,ElemTypex);//在单链表的末尾插入元素 voidpush_front(List*list,ElemTypex);//在单链表的头部插入元素 voidshow_list(List*list);//打印单链表 voidpop_back(List*list);//删除单链表的最后一个元素 voidpop_front(List*list);//删除单链表的第一个元素 voidinsert_val(List*list,ElemTypeval);//将数据元素插入到单链表中（要求此时单链表中的数据元素顺序排列） Node*find(List*list,ElemTypex);//查找单链表中数据值为x的结点 intlength(List*list);//求单链表的长度 voiddelete_val(List*list,ElemTypex);//按值删除单链表中的某个数据元素 voidsort(List*list);//对单链表进行排序 voidreverse(List*list);//逆置单链表 voidclear(List*list);//清除单链表 voiddestroy(List*list);//摧毁单链表 //代码优化 Node*CreateNode(ElemTypex);//创建一个单链表结点 Node*begin(List*list);//返回单链表的第一个结点 Node*end(List*list);//返回单链表中最后一个结点的下一个结点 voidinsert(List*list,Node*pos,ElemTypex);//在单链表的特定位置（pos）插入新的结点 #endif//__SLIST_H__
slist.cpp
#include"slist.h"
voidInitList(List*list){
list->first=list->last=(Node*)malloc(sizeof(Node));//头结点
assert(list->first!=NULL);
list->first->next=NULL;
list->size=0;
}
//push_back的优化
voidpush_back(List*list,ElemTypex){
insert(list,end(list),x);
}
//push_front的优化
voidpush_front(List*list,ElemTypex){
insert(list,begin(list),x);
}
voidshow_list(List*list){
//step1：指针p指向单链表的第一个结点
Node*p=list->first->next;
//step2：循环打印结点的信息
while(p!=NULL){
printf("%d->",p->data);
p=p->next;
}
printf("Nul.\n");
}
voidpop_back(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：定义指针p使其指向目标结点的前一个结点
Node*p=list->first;//从头结点开始
while(p->next!=list->last)
p=p->next;
//step3：删除目标结点
free(list->last);
list->last=p;
list->last->next=NULL;
//step4：更新单链表的长度
list->size--;
}
voidpop_front(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：定义指针p使其指向目标结点的前一个结点
Node*p=list->first->next;
//step3：删除目标结点
list->first->next=p->next;
free(p);
//step4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针
if(list->size==1)
list->last=list->first;
//step4：更新单链表的长度
list->size--;
}
//insert_val的优化
voidinsert_val(List*list,ElemTypex){
//step1：创建一个新的结点
Node*s=CreateNode(x);
//step2：定义指针p使其指向待插入位置的前一个结点
Node*p=list->first;//从头结点开始
while(p->next!=NULL&&p->next->datadata)
p=p->next;
//step3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针
if(p->next==NULL)
list->last=s;
//step4：插入结点
s->next=p->next;
p->next=s;
//step5：更新单链表长度
list->size++;
}
Node*find(List*list,ElemTypex){
//step1：指针p指向单链表的第一个结点
Node*p=list->first->next;
//step2：按照循环顺序查找链表结点
while(p!=NULL&&p->data!=x)
p=p->next;
returnp;
}
intlength(List*list){
returnlist->size;
}
voiddelete_val(List*list,ElemTypex){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：确定结点在单链表中的位置，并判断其是否存在于单链表中
Node*p=find(list,x);
if(p==NULL){
printf("要删除的数据不存在！\n");
return;
}
//step3：判断结点位置是否是表尾
if(p==list->last)//是表尾
pop_back(list);
else{//不是表尾
Node*q=p->next;
p->data=q->data;
p->next=q->next;
free(q);
list->size--;
}
}
voidsort(List*list){
//step1：判断单链表中的结点数是否为0或1
if(list->size==0||list->size==1)return;
//step2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中
Node*s=list->first->next;//指针s指向单链表的第一个节点
Node*p=s->next;//q指向s后面的结点
list->last=s;//单链表的尾指针指向单链表的第一个结点
list->last->next=NULL;//截断链表
//step3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中
while(p!=NULL){
s=p;
p=p->next;
Node*q=list->first;
while(q->next!=NULL&&q->next->datadata)
q=q->next;
if(q->next==NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针
list->last=s;
//将结点重新插入链表
s->next=q->next;
q->next=s;
}
}
voidreverse(List*list){
//step1：判断单链表中的结点数是否为0或1
if(list->size==0||list->size==1)return;
//step2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中
Node*p=list->first->next;
Node*q=p->next;
list->last=p;
list->last->next=NULL;
while(q!=NULL){
p=q;
q=q->next;
p->next=list->first->next;
list->first->next=p;
}
}
voidclear(List*list){
//step1：判断单链表是否为空
if(list->size==0)return;
//step2：释放单链表中的每一个结点
Node*p=list->first->next;
while(p!=NULL){
list->first->next=p->next;
free(p);
p=list->first->next;
}
//step3：头指针和尾指针重新都指向头结点
list->last=list->first;
//step4：更新链表长度
list->size=0;
}
voiddestroy(List*list){
//step1：清空单链表
clear(list);
//step2：释放头结点
free(list->first);
//step3：头指针和尾指针都赋值为空
list->first=list->last=NULL;
}
//优化
Node*CreateNode(ElemTypex){
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->next=NULL;
returns;
}
Node*begin(List*list){
returnlist->first->next;
}
Node*end(List*list){
returnlist->last->next;
}
voidinsert(List*list,Node*pos,ElemTypex){
//step1：创建一个新的结点
Node*s=CreateNode(x);
//step2：确定带插入位置
Node*p=list->first;
while(p->next!=pos)
p=p->next;
//step3：插入结点
s->next=p->next;
p->next=s;
//step4：判断结点是否插入到链表的表尾，若是则更新单链表的表尾指针
if(pos==NULL)
list->last=s;
//step5：更新单链表长度
list->size++;
}
main.cpp
#include"slist.h"
voidmain(){
Listmylist;
InitList(&mylist);
ElemTypeitem;
Node*p=NULL;
intselect=1;
while(select){
printf("*******************************************\n");
printf("*[1]push_back[2]push_front*\n");
printf("*[3]show_list[4]pop_back*\n");
printf("*[5]pop_front[6]insert_val*\n");
printf("*[7]find[8]length*\n");
printf("*[9]delete_val[10]sort*\n");
printf("*[11]reverse[12]clear*\n");
printf("*[13*]destroy[0]quit_system*\n");
printf("*******************************************\n");
printf("请选择：>>");
scanf("%d",&select);
if(select==0)break;
switch(select){
case1:
printf("请输入要插入的数据（-1结束）:>");
while(scanf("%d",&item),item!=-1){
push_back(&mylist,item);
}
break;
case2:
printf("请输入要插入的数据（-1结束）:>");
while(scanf("%d",&item),item!=-1){
push_front(&mylist,item);
}
break;
case3:
show_list(&mylist);
break;
case4:
pop_back(&mylist);
break;
case5:
pop_front(&mylist);
break;
case6:
printf("请输入要插入的数据:>");
scanf("%d",&item);
insert_val(&mylist,item);
break;
case7:
printf("请输入要查找的数据:>");
scanf("%d",&item);
p=find(&mylist,item);
if(p==NULL)
printf("要查找的数据在单链表中不存在！\n");
break;
case8:
printf("单链表的长度为%d\n",length(&mylist));
break;
case9:
printf("请输入要删除的值:>");
scanf("%d",&item);
delete_val(&mylist,item);
break;
case10:
sort(&mylist);
break;
case11:
reverse(&mylist);
break;
case12:
clear(&mylist);
break;
//case13:
//destroy(&mylist);
//break;
default:
printf("选择错误,请重新选择！\n");
break;
}
}
destroy(&mylist);//程序结束，摧毁链表
}
希望本文所述对大家C语言程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。