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->data data) 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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。