C语言实现链表的基本操作
程序员文章站
2022-03-23 22:01:26
链表在数据结构和算法中的重要性不言而喻。这里我们要用c来实现链表(单链表)中的基本操作。对于链表的基本概念请参考《》这篇博客。
(1)定义单链表的节点类型
typedef int elemtyp...
链表在数据结构和算法中的重要性不言而喻。这里我们要用c来实现链表(单链表)中的基本操作。对于链表的基本概念请参考《》这篇博客。
(1)定义单链表的节点类型
typedef int elemtype ; // 定义单链表结点类型 typedef struct listnode{ elemtype element; //数据域 struct listnode *next; //地址域 }node;(2)初始化线性表
// 1.初始化线性表,即置单链表的表头指针为空 void initlist(node *pnode){ pnode = null; printf("%s函数执行,初始化成功\n",__function__); }当声明一个头结点后,把该头结点设置为空,即把数据域和地址域都设为空,即可完成该链表的初始化。
(3)创建线性表
// 2.创建线性表,此函数输入负数终止读取数据 node *creatlist(node *phead){ node *p1;//表头节点,始终指向头结点 node *p2;//表尾节点,始终指向链表的最后一个元素 p1 = p2 = (node *)malloc(sizeof(node)); //申请新节点,分配空间 if(p1 == null || p2 == null){ printf("内存分配失败\n"); exit(0); } memset(p1,0,sizeof(node)); scanf("%d",&p1->element); //输入新节点的值 p1->next = null; //新节点的指针置为空 while(p1->element > 0){ //输入的值大于0则继续,直到输入的值为负 if(phead == null){ //空表,接入表头 phead = p1; //直接把p1作为头结点,也可以理解为把phead头结点指向p1 }else{ p2->next = p1; //非空表,接入表尾 } p2 = p1; //p1插入后,p1就是尾结点,所以p2要指向尾结点 p1 = (node *)malloc(sizeof(node)); //再重申请一个节点 if(p1 == null || p2 == null){ printf("内存分配失败\n"); exit(0); } memset(p1,0,sizeof(node)); scanf("%d",&p1->element); p1->next = null; } printf("%s函数执行,链表创建成功\n",__function__); return phead; //返回链表的头指针 }我这里使用手动的方式输入元素,直到输入0或者负数停止。
(4)打印链表
// 3.打印链表,链表的遍历 void printlist(node *phead){ if(null == phead){ //链表为空 printf("%s函数执行,链表为空\n",__function__); }else{ while(null != phead){ printf("%d ",phead->element); phead = phead->next; } printf("\n"); } }使用地址域顺序打印即可。
(5)清空链表
// 4.清除线性表l中的所有元素,即释放单链表l中所有的结点,使之成为一个空表 void clearlist(node *phead){ node *pnext; //定义一个与phead相邻节点,理解为当前节点的下一个节点 if(phead == null){ printf("%s函数执行,链表为空\n",__function__); } while(phead->next != null){ pnext = phead->next;//保存下一结点的指针 free(phead); //释放当前节点 phead = pnext; //指向下一个节点 } printf("%s函数执行,链表已经清除\n",__function__); }想要检验是否清空成功,可以使用(4)中的链表打印检验即可。
(6)计算链表长度
// 5.返回单链表的长度 int sizelist(node *phead){ int size = 0; while(phead != null){ size++; phead = phead->next; } printf("%s函数执行,链表长度 %d \n",__function__,size); return size; //链表的实际长度 }也就是计算有多少个节点。
(7)判断链表是否为空
// 6.检查单链表是否为空,若为空则返回1,否则返回0 int isemptylist(node *phead){ if(phead == null){ printf("%s函数执行,链表为空\n",__function__); return 1; } printf("%s函数执行,链表非空\n",__function__); return 0; }
(8)查找链表某个位置元素
// 7.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行 void getelement(node *phead, int pos){ int i = 0; if(pos < 1){ printf("%s函数执行,pos值非法\n",__function__); } if(phead == null){ printf("%s函数执行,链表为空\n",__function__); } while(phead != null){ i++; if(i == pos){ break; } phead = phead->next; //移到下一结点 } if(i < pos){ //pos值超过链表长度 printf("%s函数执行,pos值超出链表长度\n",__function__); } printf("%s函数执行,位置 %d 中的元素为 %d\n",__function__,pos,phead->element); }
(9)返回某元素值在链表中的内存地址
// 8.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回null elemtype* getelemaddr(node *phead, elemtype x){ if(null == phead){ printf("%s函数执行,链表为空\n",__function__); return null; } while((phead->element != x) && (null != phead->next)) {//判断是否到链表末尾,以及是否存在所要找的元素 phead = phead->next; } if((phead->element != x) && (phead != null)){ //当到达最后一个节点 printf("%s函数执行,在链表中未找到x值\n",__function__); return null; } if(phead->element == x){ printf("%s函数执行,元素 %d 的地址为 0x%x\n",__function__,x,&(phead->element)); } return &(phead->element);//返回元素的地址 }
(10)修改某个节点的值
// 9.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0 int modifyelem(node *pnode,int pos,elemtype x){ int i = 0; if(null == pnode){ printf("%s函数执行,链表为空\n",__function__); return 0; } if(pos < 1){ printf("%s函数执行,pos值非法\n",__function__); return 0; } while(pnode != null){ i++; if(i == pos){ break; } pnode = pnode->next; //移到下一结点 } if(i < pos) { //pos值大于链表长度 printf("%s函数执行,pos值超出链表长度\n",__function__); return 0; } pnode->element = x; printf("%s函数执行\n",__function__); return 1; }(11)表头插入一个节点(头节点)
// 10.向单链表的表头插入一个元素 int insertheadlist(node **pnode,elemtype insertelem){ node *pinsert; pinsert = (node *)malloc(sizeof(node)); memset(pinsert,0,sizeof(node)); pinsert->element = insertelem; pinsert->next = *pnode; *pnode = pinsert; //头节点*pnode指向刚插入的节点,注意和上一行代码的前后顺序; printf("%s函数执行,向表头插入元素成功\n",__function__); return 1; }(12)表尾插入一个节点
// 11.向单链表的末尾添加一个元素 int insertlastlist(node **pnode,elemtype insertelem){ node *pinsert; node *phead; phead = *pnode; pinsert = (node *)malloc(sizeof(node)); //申请一个新节点 memset(pinsert,0,sizeof(node)); pinsert->element = insertelem; while(phead->next != null){ phead = phead->next; } phead->next = pinsert; //将链表末尾节点的下一结点指向新添加的节点 printf("%s函数执行,向表尾插入元素成功\n",__function__); return 1; }(13)测试函数
int main(int argc, const char * argv[]) { node *plist; //声明头结点 initlist(plist); //链表初始化 printlist(plist); //遍历链表,打印链表 plist = creatlist(plist); //创建链表 printlist(plist); sizelist(plist); //链表的长度 printlist(plist); isemptylist(plist); //判断链表是否为空链表 getelement(plist,3); //获取第三个元素,如果元素不足3个,则返回0 printlist(plist); getelemaddr(plist,5); //获得元素5的内存地址 modifyelem(plist,4,1); //将链表中位置4上的元素修改为1 printlist(plist); insertheadlist(&plist,5); //表头插入元素5 printlist(plist); insertlastlist(&plist,10); //表尾插入元素10 printlist(plist); clearlist(plist); //清空链表 printlist(plist); return 0; }