链表的代码实现

2025-01-22 技术教程

linklist.h

#ifndef__LINKLIST_H__#define__LINKLIST_H__#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintDataType;typedefstructLinkNode{DataTypedata;structLinkNode*next;}LinkNode,*pLinkNode;typedefstructLinkList{LinkNode*pHead;}LinkList,*pLinkList;voidInitLinkList(pLinkListlist);voidDestoryList(pLinkListlist);voidPushBack(pLinkListlist,DataTypex);voidPopBack(pLinkListlist);voidPushFront(pLinkListlist,DataTypex);voidPopFront(pLinkListlist);voidPrintList(pLinkListlist);pLinkNodeFind(pLinkListlist,DataTypex);voidInsert(pLinkListlist,pLinkNodepos,DataTypex);voidRemove(pLinkListlist,DataTypex);voidRemoveAll(pLinkListlist,DataTypex);voidErase(pLinkListlist,pLinkNodepos);voidBubbleSort(pLinkListlist);voidSelectSort(pLinkListlist);voidInsertSort(pLinkListlist);#endif//__LINKLIST_H__

linkllist.c

#include"linklist.h"voidCreateNode(pLinkNode*newNode,DataTypex)//创建节点{*newNode=(pLinkNode)malloc(sizeof(LinkNode));if(NULL==*newNode){printf("outofmemory\n");exit(EXIT_FAILURE);}(*newNode)->data=x;(*newNode)->next=NULL;}voidInitLinkList(pLinkListlist)//初始化{list->pHead=NULL;assert(list);}voidDestoryList(pLinkListlist){assert(list);if(NULL==list->pHead)//链表为空直接返回{return;}else{pLinkNodecur=list->pHead;//cur指向第一个结点while(cur!=NULL){list->pHead=cur->next;//pHead指向cur的下一个结点，当cur是最后一个结点时，pHead指向空free(cur);cur=list->pHead;//cur指向当前第一个结点,当链表为空时，cur指向空}}}voidPushBack(pLinkListlist,DataTypex){pLinkNodenewNode=NULL;assert(list);CreateNode(&newNode,x);if(NULL==(list->pHead))//如果是空链表，直接插入头指针之后{list->pHead=newNode;}else{pLinkNodecur=list->pHead;while(NULL!=(cur->next))//找到最后一个结点cur{cur=cur->next;}cur->next=newNode;}}voidPopBack(pLinkListlist){assert(list);if(NULL==list->pHead){return;}else{pLinkNodecur=list->pHead;if(NULL==cur->next)//如果只有一个结点{free(cur);list->pHead=NULL;}else{while(NULL!=cur->next->next)//大于一个结点，先找到倒数第二个结点{cur=cur->next;}free(cur->next);cur->next=NULL;}}}voidPushFront(pLinkListlist,DataTypex){pLinkNodenewNode=NULL;assert(list);CreateNode(&newNode,x);newNode->next=list->pHead;//newNode的指针域先指向第一个结点list->pHead=newNode;//头指针指向newNode}voidPopFront(pLinkListlist){pLinkNodecur=list->pHead;//cur指向第一个结点assert(list);if(NULL==list->pHead)//空链表{return;}list->pHead=cur->next;//指向第一个结点的指针域free(cur);cur=NULL;}voidPrintList(pLinkListlist){pLinkNodecur=list->pHead;assert(list);while(NULL!=cur){printf("%d->",cur->data);cur=cur->next;}printf("over\n");}pLinkNodeFind(pLinkListlist,DataTypex){pLinkNodecur=list->pHead;assert(list);while(NULL!=cur){if(cur->data==x){break;}cur=cur->next;}returncur;}voidInsert(pLinkListlist,pLinkNodepos,DataTypex)//在pos后面插入元素{pLinkNodecur=list->pHead;pLinkNodenewNode=NULL;assert(list);CreateNode(&newNode,x);while(NULL!=cur)//先找到这个位置{if(cur==pos){break;}cur=cur->next;}if(NULL!=cur){newNode->next=cur->next;cur->next=newNode;}else{printf("没有这个结点\n");}}voidRemove(pLinkListlist,DataTypex){pLinkNodecur=list->pHead;pLinkNodep=list->pHead;assert(list);if(NULL==list->pHead)//空链表直接返回{return;}if(NULL==cur->next)//如果只有一个结点{if(cur->data==x){list->pHead=cur->next;free(cur);return;}}else{if(cur->data==x)//先判断第一个结点是不是要删除的结点{list->pHead=cur->next;free(cur);return;}cur=cur->next;while(NULL!=cur){if(cur->data==x){p->next=cur->next;//p结点的指针域指向要删除结点的指针域free(cur);return;}p=cur;cur=cur->next;}}}voidRemoveAll(pLinkListlist,DataTypex){pLinkNodecur=list->pHead;pLinkNodep=NULL;assert(list);if(NULL==list->pHead){return;}while(NULL!=cur){if(NULL==list->pHead->next)//如果要只有一个结点{if(cur->data==x)//如果是则删除{list->pHead=cur->next;free(cur);return;}}elseif(list->pHead->data==x)//判断是不是第一个结点，是则删除，继续判断{list->pHead=cur->next;free(cur);cur=list->pHead;}else{break;}}//要删除的结点在第一个结点之后cur=cur->next;p=list->pHead;while(NULL!=cur){if(cur->data==x){p->next=cur->next;//p结点的指针域指向要删除结点的指针域free(cur);cur=p;}p=cur;cur=cur->next;}}voidErase(pLinkListlist,pLinkNodepos)//删除pos后面的结点{pLinkNodecur=list->pHead;pLinkNodep=list->pHead;assert(list);if(NULL==cur){return;}if(NULL==cur->next)//如果只有一个结点{if(cur==pos){free(cur);list->pHead=NULL;}}else{if(cur==pos)//如果是第一个结点{list->pHead=cur->next;free(cur);return;}cur=cur->next;while(NULL!=cur){if(cur==pos){p->next=cur->next;free(cur);return;}p=cur;cur=cur->next;}}}voidBubbleSort(pLinkListlist){pLinkNodecur=list->pHead;pLinkNodep1=list->pHead;intflag=0;DataTypetmp=0;pLinkNodep2=list->pHead->next;assert(list);if(NULL==list->pHead){return;}if(NULL==cur->next){return;}cur=cur->next;while(NULL!=cur){flag=1;while(NULL!=p2){if(p1->data>p2->data){tmp=p1->data;p1->data=p2->data;p2->data=tmp;flag=0;}p2=p2->next;p1=p1->next;}if(flag){break;}p1=list->pHead;p2=list->pHead->next;cur=cur->next;}}

test.c

#include"linklist.h"voidMenu(){printf("**********************************\n");printf("*0.Quit1.InitLinkList*\n");printf("*2.PushBack3.PopBack*\n");printf("*4.PushFront5.PopFront*\n");printf("*6.PrintList7.Find*\n");printf("*8.Insert9.Remove*\n");printf("*10.RemoveAll11.Erase*\n");printf("*12.BubbleSort\n");printf("**********************************\n\n");printf("请选择:");}voidtest(){LinkListlist;DataTypex=0;pLinkNodepos=NULL;intn=-1;while(1){Menu();scanf("%d",&n);switch(n){case0:DestoryList(&list);exit(1);break;case1:InitLinkList(&list);break;case2:printf("请输入：");scanf("%d",&x);PushBack(&list,x);break;case3:PopBack(&list);break;case4:printf("请输入：");scanf("%d",&x);PushFront(&list,x);break;case5:PopFront(&list);break;case6:PrintList(&list);break;case7:printf("请输入：");scanf("%d",&x);pos=Find(&list,x);printf("查找成功\n");break;case8:printf("请输入元素：");scanf("%d",&x);Insert(&list,pos,x);break;case9:printf("请输入：");scanf("%d",&x);Remove(&list,x);break;case10:printf("请输入：");scanf("%d",&x);RemoveAll(&list,x);break;case11:Erase(&list,pos);break;case12:BubbleSort(&list);break;default:printf("选择无效,请重新选择\n");break;}}}intmain(){test();system("pause");return0;}