单链表的基本操作代码实现(C语言版)

阅读本书更多章节>>>>

目录

前言：

单链表的基本操作

准备工作（头文件、各种宏定义以及结构体定义）

一.较简单操作

1.单链表的初始化

2.判断单链表是否为空表

3.单链表的销毁

4.单链表的清空

5.求单链表的表长

二.较重要操作

1.单链表的取值

2.单链表元素的查找

3.单链表的结点插入

4.单链表的结点删除

5.单链表的创建

以下是主函数以及函数声明

补充

---

前言：

        在实现顺序表的基本操作后，觉得自己对单链表基本操作的思路无大问题，因此当时没有对链表基本操作进行实现，在后来的稀疏多项式的运算中需要运用到单链表(顺序表实现会造成大量空间的浪费)，而自己并没有实现过这些基本操作，为防止在做稀疏多项式的运算时出现难以解决的问题，打算再把单链表的基本操作实现一遍。并写一篇博客，耗时：70分钟。

        希望能够对您有一定帮助和参考价值。新csdner，有所不足尽管提出。

单链表的基本操作

        单链表的基本操作包括单链表的初始化、判断空链表、销毁、清空以及求表长这些较为简单的操作，还有更为重要的单链表的取值、按值查找返回元素所在地址、按值查找返回元素所对应序号、结点插入和删除以及头插法和尾插法建立单链表。目前只实现了这些操作，并进行的测试。

准备工作（头文件、各种宏定义以及结构体定义）

#include <stdio.h>#include <stdlib.h>#include<stdbool.h>#define OK 1#define ERROR 0        /*用于返回函数执行的状态值*/typedef int Status;typedef int ElemType;typedef struct Node {ElemType data; //存储数据struct Node *next;//存储下一个元素的地址} Node;typedef struct Node *LinkList; /* 定义LinkList */

一.较简单操作

1.单链表的初始化

        单链表的初始化指生成一个只有头指针的单链表，并将其指向的头结点的指针域置空。需要注意的是，传入的参数为LinkList *L；为什么L本来就是指针类型了还要加   " * "呢，因为你要知道你是要对链表的本质(内存，指针指向等)进行更改而不是使用链表进行元素的查找取值等，如果只是这些操作，只要告诉计算机你要查找的对象是哪个表，即把链表的头指针传过去就行（这样就不需要添加 " * " ）。以下是代码实现：

/* 初始化链式线性表 */Status IniList(LinkList *L) {*L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */(*L)->next=NULL; /* 指针域为空 */return OK;}

2.判断单链表是否为空表

        只需要判断对应单链表头结点的指针域是否为空即可。该实现我使用的是bool类型返回值，实际上c语言中逻辑值就是0，1，因此多此一举了属于是；如果要用bool类型需要添加头文件#include<stdbool.h>。以下是代码实现：

bool Empty(LinkList L) {if(L->next==NULL)return true;    return false;//main函数中测试bool c=Empty(L); printf("%d",c);  返回 1}

3.单链表的销毁

        单链表的销毁指将链表中的所有结点包括头结点都释放掉（c语言中使用free（），c++中使用delete（））。由于仍然是对单链表的“本质”进行修改，所以参数需加  " * " ，思路是利用头指针以及新指针p(用于释放其指向的结点)，在释放之前，先将头指针后移，否则找不到下一结点。以下是代码实现：

/* 单链表的销毁*/         Status DestoryList(LinkList *L) {LinkList p=*L;              //p此时指向头结点//注意此时不能直接释放p，因为头结点中还存放着下一结点的地址，释放就找不到下一个结点了while(*L) {*L=(*L)->next;free(p);            p=*L;}return OK;//测试int b=DestoryList(&L);  printf("%d",b);ListTraverse(L); 输出1，且并不打印其他的}

4.单链表的清空

        将除头结点以外的结点释放，并将头结点的指针域置空。与销毁不同，该操作的头指针不能动，所以还需要新定义一个指针对下一结点进行定位。以下是代码实现：

/*清空链表*/Status ClearList(LinkList L) {LinkList p,q;    //p用于指向需要释放的结点，q用于在p释放之前指向下一结点，以使p移动p=L->next;       //p指向首元结点while(p) {q=p->next;   //q指向下一结点free(p);p=q;}//最后不要忘了，结点释放后还需要将头结点的指针域更改为NULL，形成空表L->next=NULL;return OK;/*测试CreateList(&L,n); ClearList(L);ListTraverse(L);//不输出创建时输入的元素*/}

5.求单链表的表长

        以下是代码实现：

/*求链表的表长*/int ListLength(LinkList L) {LinkList p;   //用于指向除头结点以外的结点int count=0;p=L->next;while(p) {count++;p=p->next;}return count; //测试  printf("%d",ListLength(L)); 输出正确}

二.较重要操作

1.单链表的取值

        取出链表中位置 i 对应的元素，i表示的是序号，不按逻辑层面确定。思路：将指针p移动到对应序号逻辑层面存储位置，随后将其指向的元素返回即可。注意循环终止条件，以下是代码实现：

/*获得某一元素*/  //返回链表中第i位置的元素Status GetElem(LinkList L,int i,ElemType *e) {Node *p;p=L->next;int j = 1;for(; p&&j<i ;) {p = p->next; /*p所指元素存在且j<1时循环执行*/++j;}if(!p||j>i) //j大于i的情况：如i传入的为0或负数return ERROR;*e=p->data;return OK; //测试：元素返回正确}

2.单链表元素的查找

        查找分为按值查找返回元素所在地址和返回所在序号，思路：定义一个指针p指向头结点，随后利用循环将指针p进行移动即对链表进行遍历，将每次循环时结点的数据与待查找数据比较，如果找到则返回对应地址(反映为当前指针的指向),以及对应的序号。以下是代码实现：

//查找/*按值查找数据所在地址并返回*/  //参数为所需查询链表，需要查询的数据，返回p的地址LinkList searchAD(LinkList L,ElemType e) {LinkList p;p=L->next;for(int i=0; p&&i<ListLength(L); i++) {if(p->data==e)break;p=p->next;}return p; //测试；printf("%p",searchAD(L,5));  5所在元素次序不同，打印的地址不同}/*按值查找数据所在链表的序号(第几个元素)*/  //参数：所需查询链表，所需查询数据，返回数据所在序号int searchNum(LinkList L,ElemType e) {LinkList p;p=L->next;for(int i=0; p&&i<ListLength(L) ; i++) {if(p->data==e) {    //遍历链表中p所指项结点的数据，与e比较，找到后返回对应序号即可return i+1;}p=p->next; //当前结点的数据不等于e则p指针后移}return 0;  //测试：printf("%d",searchNum(L,5));  返回5所在位置正确,如果不存在所查询数据，返回0}

3.单链表的结点插入

        思路：先将待插入位置找到，利用其前一个位置的指针p对其后继进行保留，随后定义一个新结点并用指向它的指针q，进行前驱后继的链接。以下是代码实现：

//链表元素的插入    //参数:需要插入数据的链表，需要插入元素的位置，需要插入的数据，返回插入结束状态Status ListInsert(LinkList L,int i,ElemType e) {LinkList p,q;p=L;        //指向头结点//先新建并初始化好需要插入的结点，用指针q指向它q=(Node *)malloc(sizeof(Node));q->data=e;q->next=NULL;for(int j=0; p&&j<i-1 ; j++) { if(i>ListLength(L)+1)return ERROR;   //如果插入的位置大于链表的尾结点后面的一个位置,则返回错误p=p->next; }//将待插入结点的前后结点与之形成链式关系q->next=p->next;    //接后继结点p->next=q;        //接前驱结点return OK;/*测试：ListInsert(L,4,99);ListTraverse(L); 在表中元素为5个的情况下插入位置为1--6均可正确插入，如果插入位置大于等于7，则不插入元素              */}

4.单链表的结点删除

        思路：同样是先找到待删除结点，将q指针指向它，并新定义一个指针p对其前驱进行指向，以便后续链接，接好待删除结点的前驱后继后即可释放该结点。以下是实现代码：

//链表元素的删除  //参数需要删除元素的链表，需要删除的结点Status deleElem(LinkList L,int i) {LinkList p,q;   //p指向删除位置的前一结点,q指向需要删除的结点p=L;  //p指向头结点//首先需要将p移动到删除结点的前一结点for(int j=0; p&&j<i-1; j++) {p=p->next;}q=p->next;  //如果所需删除结点存在,则将q指向它，如果不存在返回错误，不执行删除if(!q)return ERROR;  //判断删除的结点是否存在p->next=p->next->next;  //也可以p->next=q->next;但一定要在释放之前将p指向下一结点，否则找不到free(q);return OK;/*测试：deleElem(L,1);ListTraverse(L);假设表中有5个元素，则第1--5个位置的元素正常删除，如果为大于等于6的位置，不删除*/}

5.单链表的创建

        包括尾插法和头插法，进行单链表的内存分配和结点的添加与赋值。以下是代码实现：

/*头插法创建链表*/ //输入n个元素 ，元素从头开始依次插入Status CreateList_H(LinkList *L,int n) {LinkList p,r;  //p用于指向新结点,r指向头结点//建立一个带有头结点的单链表并将指针域置为空*L=(LinkList)malloc(sizeof(Node));r=*L;r->next=NULL;//结点添加与赋值for(int i=n; i>0; i--) {p=(Node *)malloc(sizeof(Node));printf("请输入该链表的第%d个元素：",i);scanf("%d",&p->data);p->next=NULL;p->next=r->next;r->next=p;}return OK;/*测试:printf("请输入头插法创建链表的元素个数：");scanf("%d",&n);CreateList_H(&L_H,n);ListTraverse(L_H);  新建正常*/}

/*尾插法创建链表*/ //输入n个元素， 元素从尾部依次接入Status CreateList(LinkList *L,int n) {LinkList p,r;//p用于指向新结点(待插入结点)，r指向尾部结点*L = (LinkList)malloc(sizeof(Node));r=*L;  //刚开始时r指向头结点r->next=NULL;for(int i=0; i<n; i++) {p=(Node *)malloc(sizeof(Node));   //注意这里不要忘记将这块内存定义为Node的指针类型printf("请输入该链表的第%d个元素：",i+1);scanf("%d",&p->data);p->next=NULL;r->next=p;r=r->next;}r->next=NULL;return OK;}

以下是主函数以及函数声明

对应操作的运行截图就不搞了，主函数也没有对所有函数进行调用，但是各个操作都已进行测试，程序的健壮性还是有的。

Status IniList(LinkList *L);Status GetElem(LinkList L,int i,ElemType *e);Status CreateList(LinkList *L,int n);  //尾插法Status CreateList_H(LinkList *L,int n);//头插法Status visit(ElemType c);Status ListTraverse(LinkList L);bool Empty(LinkList L);Status DestoryList(LinkList *L);Status ClearList(LinkList L);int ListLength(LinkList L);LinkList searchAD(LinkList L,ElemType e);int searchNum(LinkList L,ElemType e);Status ListInsert(LinkList L,int i,ElemType e);Status deleElem(LinkList L,int i);int main() {LinkList L,L_H;int n;int a=IniList(&L);     //a用于判断是否成功初始化printf("请输入尾插法创建链表的元素个数：");scanf("%d",&n);CreateList(&L,n);ListTraverse(L);printf("请输入头插法创建链表的元素个数：");scanf("%d",&n);CreateList_H(&L_H,n);ListTraverse(L_H);return 0;}

补充

        为了更方便的对链表进行输出，新定义了两个子函数实现，代码如下：

//打印元素Status visit(ElemType c) {printf("%d ",c);return OK;}//遍历链表Status ListTraverse(LinkList L) {LinkList p=L->next;printf("链表中所有元素为： ");if(!p)return ERROR;//如果首元结点不存在返回0while(p) {visit(p->data);p=p->next;}printf("\n");return OK;}

我的小站：Kris20030907.gitee.io，有需要的话可以交换友链哦，评论区留言

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-12/157448.html，文章来源：网络cs，作者：往北，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！