单链表的 (增删查改) 的实现
作者：lovevivi
- 2022-10-22 吉林
本文字数：2143 字
阅读完需：约 7 分钟
@TOC
一、链表
1.链表的概念
一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
2.链表优点
1.空间上按需所给空间 2.在头部和中间插入时，不需要挪动数据
二、单链表的实现
1.函数的定义和结构体的创建——list.h
#include<stdio.h>#include<stdlib.h>#include<assert.h>typedef int slistdatatype;typedef struct slistnode{ slistdatatype data; struct s* next;}slistnode;
void stackpushback(slistnode**pphead, slistdatatype x);void slistprint(slistnode* phead);void stackpopback(slistnode**phead);void stackpushfront(slistnode** phead, slistdatatype x);void stackpopfront(slistnode** phead);slistnode* slistfind(slistnode* phead, slistdatatype x);void slistinsertafter(slistnode**pphead, slistnode* pos, slistdatatype x);void slisteraseafter(slistnode**pphead,slistnode*pos);
复制代码
2.函数的调用——test.c
#include"list.h"int main(){ slistnode* phead = NULL; stackpushback(&phead, 1);//尾插 stackpushback(&phead, 2); stackpushback(&phead, 3); stackpushback(&phead, 4); slistprint(phead);//打印 stackpopback(&phead);//尾删 slistprint(phead); stackpushfront(&phead,5);//头插 slistprint(phead); stackpopfront(&phead);//头删 slistprint(phead); slistnode* pos1 = slistfind(phead, 2);//查找位置 slistinsertafter(&phead, pos1, 6);//指定插 slistprint(phead); slistnode*pos2=slistfind(phead,2); slisteraseafter(&phead,pos2);//指定删 slistprint(phead); return 0;}
复制代码
3.二级指针问题
此时发现传过去的 &pehad，接收是二级指针,传址调用才能真正改变主函数中 phead 指针但比如 打印或者查找位置并没有改变 phead 指针，所以也就不用传地址了
4.单链表的接口实现
1.尾插
void stackpushback(slistnode** pphead, slistdatatype x)//尾插{ slistnode* newnode = (slistnode*)malloc(sizeof(slistnode)); if (newnode != NULL) { newnode->data = x; newnode->next = NULL; } if (*pphead == NULL)//为空时 { *pphead = newnode; } else//不为空时 { slistnode* tail = *pphead; while (tail->next != NULL)//遍历到最后一个节点 { tail = tail->next; } tail->next = newnode; }}
复制代码
2.尾删
void stackpopback(slistnode** pphead)//尾删{ if (*pphead == NULL)//为空 { return; } else if ((*pphead)->next == NULL)//只有一个节点时 { free(*pphead); *pphead = NULL; } else//正常情况下 要把尾节点free 尾节点的前一个节点的指针置为NULL { slistnode* prev = NULL;//prev指向前一个节点 slistnode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; }}
复制代码
3.头插
void stackpushfront(slistnode** pphead, slistdatatype x)//头插{ slistnode* newnode = (slistnode*)malloc(sizeof(slistnode)); newnode->data = x; newnode->next = NULL; newnode->next = *pphead; *pphead = newnode;}
复制代码
4.头删
void stackpopfront(slistnode** pphead)//头删{ if (*pphead == NULL)//若为空 { return; } else { slistnode* newnode = (slistnode*)malloc(sizeof(slistnode)); newnode = (*pphead)->next;//*pphead的后一个节点作为*pphead free(*pphead); *pphead = NULL; *pphead = newnode; }}
复制代码
5.查找位置
slistnode* slistfind(slistnode* phead, slistdatatype x)//查找位置(返回该位置，不是下标）{ slistnode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur;//如果找到了则返回该位置 } cur = cur->next; } return NULL;//没找到直接返回NULL}
复制代码
6.指定插
void slistinsertafter(slistnode** pphead, slistnode* pos, slistdatatype x)//指定插{ assert(pos);//pos为找到的位置， x是要插入的值 slistnode* newnode = (slistnode*)malloc(sizeof(slistnode)); newnode->data = x; newnode->next = NULL; newnode->next = pos->next;//先将新节点与pos后面的节点连接 pos->next = newnode;//再将pos与新节点连接}
复制代码
这里一定不要先将 pos 与 x 先连接，否则会使 pos->next 找不到 2
7.指定删
void slisteraseafter(slistnode** pphead, slistnode* pos)//指定删{ assert(pos);//pos有可能传过来NULL slistnode* prev = *pphead; while (prev->next != pos)//prev为pos的前一个节点 { prev = prev->next; } prev->next = pos->next;//将pos的前一个节点与pos的后一个节点连接 free(pos); pos = NULL;}
复制代码
8.打印
void slistprint(slistnode* phead)//打印{ slistnode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n");}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【lovevivi】的原创文章。
原文链接:【http://xie.infoq.cn/article/2a6f3b9966c7195a6bbb37d60】。文章转载请联系作者。
lovevivi
关注
还未添加个人签名 2022-10-12 加入
还未添加个人简介
评论