C语言实现的双链表功能完整示例
本文实例讲述了C语言实现的双链表功能。分享给大家供大家参考，具体如下：
Dlist.h
#ifndef__DLIST_H__ #define__DLIST_H__ #include#include #include typedefintElemType; typedefstructNode{ ElemTypedata; structNode*prio; structNode*next; }Node,*PNode; typedefstructList{ PNodefirst; PNodelast; size_tsize; }List; voidInitDlist(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*_buynode(ElemTypex);//创建结点 #endif
Dlist.cpp
#include"Dlist.h"
Node*_buynode(ElemTypex){
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
s->data=x;
s->prio=s->next=NULL;
returns;
}
voidInitDlist(List*list){
Node*s=(Node*)malloc(sizeof(Node));
assert(s!=NULL);
list->first=list->last=s;
list->first->prio=NULL;
list->last->next=NULL;
list->size=0;
}
voidpush_back(List*list,ElemTypex){
Node*s=_buynode(x);
s->prio=list->last;
list->last->next=s;
list->last=s;
list->size++;
}
voidpush_front(List*list,ElemTypex){
Node*s=_buynode(x);
if(list->first==list->last){
s->prio=list->first;
list->first->next=s;
list->last=s;
}
else{
s->next=list->first->next;
s->next->prio=s;
s->prio=list->first;
list->first->next=s;
}
list->size++;
}
voidshow_list(List*list){
Node*p=list->first->next;
while(p!=NULL){
printf("%d->",p->data);
p=p->next;
}
printf("Nul.\n");
}
voidpop_back(List*list){
if(list->size==0)return;
Node*p=list->first;
while(p->next!=list->last)
p=p->next;
free(list->last);
list->last=p;
list->last->next=NULL;
list->size--;
}
voidpop_front(List*list){
if(list->size==0)return;
Node*p=list->first->next;
if(list->first->next==list->last){
list->last=list->first;
list->last->next=NULL;
}
else{
list->first->next=p->next;
p->next->prio=list->first;
}
free(p);
list->size--;
}
voidinsert_val(List*list,ElemTypex){
Node*p=list->first;
while(p->next!=NULL&&p->next->datanext;
if(p->next==NULL)
push_back(list,x);
else{
Node*s=_buynode(x);
s->next=p->next;
s->next->prio=s;
s->prio=p;
p->next=s;
list->size++;
}
}
Node*find(List*list,ElemTypex){
Node*p=list->first->next;
while(p!=NULL&&p->data!=x)
p=p->next;
returnp;
}
intlength(List*list){
returnlist->size;
}
voiddelete_val(List*list,ElemTypex){
if(list->size==0)return;
Node*p=find(list,x);
if(p==NULL){
printf("要删除的数据不存在！\n");
return;
}
if(p==list->last){
list->last=p->prio;
list->last->next=NULL;
}
else{
p->next->prio=p->prio;
p->prio->next=p->next;
}
free(p);
list->size--;
}
voidsort(List*list){
if(list->size==0||list->size==1)return;
Node*s=list->first->next;
Node*q=s->next;
list->last=s;
list->last->next=NULL;
while(q!=NULL){
s=q;
q=q->next;
Node*p=list->first;
while(p->next!=NULL&&p->next->datadata)
p=p->next;
if(p->next==NULL){
s->next=NULL;
s->prio=list->last;
list->last->next=s;
list->last=s;
}
else{
s->next=p->next;
s->next->prio=s;
s->prio=p;
p->next=s;
}
}
}
voidreverse(List*list){
if(list->size==0||list->size==1)return;
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;
p->next->prio=p;
p->prio=list->first;
list->first->next=p;
}
}
voidclear(List*list){
if(list->size==0)return;
Node*p=list->first->next;
while(p!=NULL){
if(p==list->last){
list->last=list->first;
list->last->next=NULL;
}
else{
p->next->prio=p->prio;
p->prio->next=p->next;
}
free(p);
p=list->first->next;
}
list->size=0;
}
voiddestroy(List*list){
clear(list);
free(list->first);
list->first=list->last=NULL;
}
main.cpp
#include"Dlist.h"
voidmain(){
Listmylist;
InitDlist(&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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。