一起学数据结构（3）——万字解析：链表的概念及单链表的实现

上篇文章介绍了数据结构的一些基本概念，以及顺序表的概念和实现，本文来介绍链表的概念和单链表的实现，在此之前，首先来回顾以下顺序表的特点：

1.顺序表特点回顾：

1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构，逻辑上：顺序表中相邻的数据元素，其物理次序也是相邻的。

2. 顺序表的优点： 任一元素均可以随机存取

3.顺序表的缺点：进行插入和删除操作时，需要移动大量的元素，存储空间不灵活。

2. 链表的分类及概念：

2.1 链表的分类：

1.单链表：结点只有一个指针域的链表，称之为链式线性表或者单链表:

   

2.双链表：结点由两个指针域的链表：

3.循环链表：首尾相连的链表：

 本文将着重介绍单链表，下面给出单链表的概念及相关特点：

2.2 单链表的概念即特点：

单链表指的是链表的每个结点中只包含一个指针域，对于链表，下面给出定义：

线性表链式存储的结构是：用一组任意的存储单元 存储线性表的数据元素（这组存储单元可以连续，也可以不连续）。为了表示每个数据元素a_i与其后记数据元素^{a_{i+1}}之间的逻辑关系，所以，对于存储数据元素a_i的存储单元，还需要存储一个指示后记数据元素^{a_{i+1}}的相关信息，（即存储^{a_{i+1}}所在的地址）。这两部分信息构成了数据元素a_i的存储映像，称为结点。

对于结点，包括了两个域：存储数据元素信息的域称之为数据域，存储后记元素存储位置的域称之为指针域。指针域中存储的信息称作指针或者链。n个结点链成一个链表，即为线性表的链式存储结构

（注：对于链表更详细的定义可以参考人民邮电出版社出版的《数据结构》，本文不再过多说明）

3.单链表的代码实现：

3.1 链表的存储结构及结点的创建：

单链表的定义中提到了，链表是由n个结点构成的，每个结点中包含了两个与，一个是用于存储数据元素信息的数据域，另一个是用于存储下一个数据元素信息地址的指针域。不同类型的信息的保存，可以由结构体进行实现，所以，下面用图给出单个结点的结构：

其中，data表示存储的数据元素信息，next表示下一个数据元素信息的地址。并且，将每一个这种结点命名为newnode，对上述结点用代码表示：

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;// 对应了存储的元素信息struct SListNode* next; // 对应了下一个数据元素信息的地址
}SLTNode;

对于链表，也和顺序表一样，可以实现增删查改各种功能，而实现这些功能的基础，就是如何创造新的结点，为了解决这个问题，可以专门定义一个函数BySListNode来实现。前面说到，链表各个结点之间的链接是通过某个结点存储下一个结点的地址来实现的。所以，对于函数BySListNode的返回类型，应该定义为SLTNode*型，即返回结构体的地址。

对于一个结点的创建，同样可以采用在顺序表中用动态内存函数malloc动态开辟内存的方式进行实现。具体代码如下:

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

 下面给出代码来测试函数BySListNode的功能:

为了测试函数的功能，首先需要针对链表来封装一个打印函数，将打印函数命名为SLTPrint，代码如下：

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}

在链表的定义中说过，链表取任意元素必须从头节点开始向后依次寻找。所以，为了防止头指针的值被更改，后续无法找到第一个结点，所以，在上述代码中，创建了一个新的变量cur用来存放头指针phead中的地址。

对于cur = cur->next;这一行代码，是用于让cur保存下一个结点的地址，例如下图中cur的变化所示：

 下面，封装一个函数Testlist1来测试插入结点的功能，代码初步表示如下：

void Testlist()
{printf("请输入想要插入的元素的个数：");int n = 0;scanf("%d", &n);printf("请输入插入的元素：");for (size_t i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);}
}
int main()
{Testlist1();return 0;
}

但是对于上面给出的代码，并不能完成对多个结点的数据元素的打印，因为在创建结点后，并没有将前后的结点进行链接。同时，也并没有出现上面图中所说的头指针。

为了建立前后结点的链接。所以，在上面Testlist1函数中的代码的基础上，人为建立一个头指针，定义为plist,赋值为NULL。

（注：下面为了方便进行演示，对于结点之间建立的过程采用头插的思想，但是并不等价于后面的头插）

对于链接各个结点，需要分以下两种情况：

1.头指针为NULL，即还未链接任何结点，但是已经创建了一个结点：

为了达到链接的效果，只需要将plist中存储的地址改为新结点newnode的地址即可。 

2.头指针不为空：

 此时，plist中已经通过存储第一结点的地址达到链接第一结点的目的，为了链接第二结点，需要将plist中存储的地址改为第二结点的地址。

注释中提到，为了方便演示采用头插的思想，对于头插，可以用下图进行表示：

例如，将地址为 0x0012ffa0的结点进行头插。为了完成头插，需要进行两步操作：

1.将地址为0x0012ffa0的结点（即新结点）中存储的地址改为0x0012ffb0（插入前的第一个结点）

2.将头指针中存储的地址改为0x0012ffa0（即新结点的地址）

对上述分析进行归纳，代码如下：

void Testlist()
{printf("请输入想要插入的元素的个数：");int n = 0;scanf("%d", &n);SLTNode* plist = NULL;printf("请输入插入的元素：");for (size_t i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);if (plist == NULL){plist = newnode;}else{newnode->next = plist;plist = newnode;}}SLTPrint(plist);
}

其中，newnode是一个结构体指针，所以需要用到->进行解引用。来改变新结点newnode中存储的下一个数据元素信息的地址。

测试效果如下：

3.2 链表功能实现——尾插： 

定义尾插函数SLTPushBack其内部参数如下面代码所示：

void SLTPushBack(SLTNode* phead, SLTDataType x);

对于尾插这一功能，首先需要找到链表的尾端。前面说到，头指针对于链表的各种功能来说都非常重要，所以，为了保证头指针不被更改，这里定义一个新的结构体指针tail来存储头指针中存储的地址。

对于如何找到尾端，下面给出一段示例的代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);SLTNode* tail = phead;while (tail != NULL){tail = tail->next;}tail = newnode;
}

上述代码给出的思路很明确。利用while循环不断检查指针tail是否为NULL,不为空，则tail存储下一个结点的指针。看似没有错误。但是如果将上述过程用图形表示，则上述代码会引起内存泄漏这一错误，具体如下：

一开始，指针tail存储了头指针phead中的地址，此时tail\neq NULL,于是执行循环内部的代码，此时，tail中存储的地址为0x0012ffb0，效果如下图所示：

依次循环上述步骤：

 再次循环上述步骤：

 到最后一步时，指针tail中存储的地址为NULL。到这里，while循环终止。已经寻找到尾端地址。假设，在循环之前新建立的结点如下图所示：

如果按照上面给出的代码来执行，即：tail = newnode;，则，执行结束后，最后一个结点和指针tail中存储的地址如下：

此时，便会出现一个问题，即，指针tail是只存在与函数内部的一个临时变量，出函数便会销毁。但是，最后一个结点中存储的地址仍然为NULL。最后一个结点和新的结点并未建立联系。造成了内存泄露的问题。 

因为，完成尾插的标志，便是最后一个结点存储的地址被更改为新结点的地址。通过上面的错误例子。可以得出一个结论。如果想要将最后一个结点存储的地址改为新结点的地址，则，不可以让临时指针tail赋值最后一个结点中存储的地址。应该赋值最后一个结点的前一个结点的存储的地址。

再通过这个结点存储的地址，来对最后一个结点存储的地址进行修改。所以，代码可以更改为：
 

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);SLTNode* tail = phead;while (tail ->next != NULL){tail = tail->next;}tail -> next = newnode;
}

通过下面的测试来测试尾插的功能：

void Testlist1()
{printf("请输入想要插入的元素的个数：");int n = 0;scanf("%d", &n);SLTNode* plist = NULL;printf("\n请输入插入的元素：");for (size_t i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);if (plist == NULL){plist = newnode;}else{newnode->next = plist;plist = newnode;}}SLTPrint(plist);printf("\n");SLTPushBack(plist, 10000);SLTPrint(plist);
}

结果如下：

上面关于尾插的代码，只能是在有结点的情况下运行。对于头指针为空的情况下并不适用，下面将对上面的尾插代码进行完善：

给出下列代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (phead == NULL){phead = newnode;}SLTNode* tail = phead;while (tail ->next != NULL){tail = tail->next;}tail -> next = newnode;
}

这里给出的代码对比尾插，仅仅是多了一个对于头指针phead = NULL的情况的判定。中心思想就是在头指针phead = NULL时，将头指针保存的地址改为第一个结点的地址。但是这种做法并不正确。因为这里所说的头指针phead只是函数内部的一个形式参数。真正的头指针时上面定义的plist。此时，函数形式参数传递的时形参phead中保存的值，在前面关于C语言函数的文章中曾提到函数的两个传递参数的方式：传值和传址。对于传值调用，并不能改变外部变量的值。所以，这里虽然对头指针phead存储的地址进行改变。但是却没有真正的改变函数外部实际参数plist中保存的地址。

对于上面的错误，可以通过传址调用来改变头指针plist中保存的地址。在前面对于C语言函数的文章的介绍中曾写过一个用传址调用来实现交换函数。所以，通过函数来交换两个变量中的值，需要用到一级指针。相对于，对于头指针plist，想要通过函数来改变他的值，需采用二级指针。

所以，正确的尾插代码应为：

void SLTPushBack(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (*phead == NULL){*phead = newnode;}else{SLTNode* tail = *phead;while (tail ->next != NULL){tail = tail->next;}tail -> next = newnode;} 
}

运用下面的测试，来测试尾插的功能：

void Testlist2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);
}

结果如下：

3.3 链表功能实现——头插：

对于头插功能的实现，上面已经给出来了大体思路。但是上面的头插并不是通过函数实现的。根据刚才尾插的实现可以发现。每进行一次头插，都需要对头指针plist中存储的地址进行更改。所以。在函数传递参数时，也需要传递二级指针。

代码如下：

void SLTPushFront(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *phead;*phead = newnode;
}

用下列代码对头插功能进行测试：

void Testlist3()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPrint(plist);
}

结果如下：

3.4 链表功能实现——尾删：

对于尾删功能的实现，需要考虑下面的三种情况：

1. 链表整体为空：

2.链表内只有一个结点

3.链表有多个结点

对第一种情况，只需要在进行尾删功能前，检查一下地址是否合法即可。

对于第三种情况，需要两步。第一步是删除处于尾部的结点。第二种情况是将前一个结点中保存的地址改为NULL即：

 第二种情况也需要分为两步，首先删除尾部结点。再把头指针中存储的地址改为NULL。与第三步不同的时，第三步更改地址的对象是结构体中的一个成员。第二步中更改的对象时头指针。所以，在进行对于第二种情况的地址改动时，需要传递二级指针。

下面先给出针对第一、第二种情况下的代码：

//尾删
void SLTPopBack(SLTNode** phead)
{assert(*phead);if ((*phead)->next == NULL)//只有一个结点的情况{free(*phead);*phead = NULL;}}

对于第三种情况，假设此时有三个结点：

对于尾删功能，与尾插功能相同，第一步都是需要找到尾结点：

寻找尾结点时，采用与尾插寻找尾结点相同的方式，创建一个函数内部的指针变量SLTNode*tail来保存头指针保存的地址。当tail找到尾结点时：

如果此时就删除尾结点，还是会造成在讲解尾插原理中的错误。即，没能更改尾部结点前一个结点中存储的地址。如下图所示：

此时最后一个由malloc函数开辟的结点已经被free 。

为了解决上面的问题，可以在创建一个临时变量也用于保存phead中存储的地址。不过，这个变量的作用是用于更改尾结点前一个结点中存储的地址。这里将这个指针命名为tailprev,再有了这个指针后，当找到尾结点时，这两个指针的关系如下图所示：

先用代码表示指针tail：

SLTNode* tail = *phead;SLTNode* tailprev = *phead;while (tail->next != NULL){tail = tail->next;}

 为了达到图中两个指针一前一后的关系，可以让循环中在执行tail = tail -> next之前，让tailprev存储一次tail中的地址。代码如下：

//尾删
void SLTPopBack(SLTNode** phead)
{assert(*phead);if ((*phead)->next == NULL)//只有一个结点的情况{free(*phead);*phead = NULL;}else{SLTNode* tail = *phead;SLTNode* tailprev = NULL;while (tail->next != NULL){tailprev = tail;tail = tail->next;}free(tail);tailprev->next = NULL;}
}

测试功能的代码如下：
 

void Testlist3()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPrint(plist);printf("\n尾删");SLTPopBack(&plist);SLTPopBack(&plist);SLTPopBack(&plist);printf("\n");SLTPrint(plist);
}

结果如下：

3.5 链表功能实现——头删：

对于头删功能，依旧分为以下三种情况：

1. 链表整体为空：

2.链表内只有一个结点

3.链表有多个结点

对于第一种情况，直接检查头指针合法性即可。对于第三种情况，即多个结点，需要分为两步来完成头删：首先将头指针存储的地址改为第二个结点的地址。再把第一个结点free。对于第二种情况，和第三种情况相同，虽然只有一个结点。但是可以将NULL看作第二个结点的地址。代码如下：

//头删
void SLTPopFront(SLTNode** phead)
{assert(*phead);SLTNode* newhead = (*phead)->next;free(*phead);*phead = newhead;
}

测试函数如下：

void Testlist4()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);printf("\n");printf("头删");printf("\n");SLTPrint(plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);printf("\n");SLTPrint(plist);}

 结果如下：

 4. 单链表的代码实现——针对某一元素对应的位置进行操作：

4.1 通过某一具体元素来找到特定位置：

例如给出下面所示的一个单链表：

如果需要找到元素2所对应的位置，只需要将整体单链表进行一次遍历，若某个结点中的元素= 想要寻找的元素。则返回这个元素对应的结点的坐标，具体代码如下：

//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (phead != NULL){if (tail->data == x){return tail;}else{tail = tail->next;}}return NULL;
}

4.2 在某一特定数据对应的结点前插入新结点：

前面知道了如何找到一个特定数据对应的结点的位置后，如果需要在这个结点之前插入一个新的结点。

对于这种形式的插入，需要分为两种情况：

1. 头指针为空，此时无法插入，检查指针合法性即可

2. 链表中只有一个结点，此时的插入就等于头插

3. 链表中有多个结点

对于前两种情况，具体的代码如下：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(*phead);if (*phead == NULL){SLTPushFront(phead, x);}
}

对于第三种情况，需要考虑到，上面给出的查找函数返回的地址并不是插入新结点的地址，而是在这个地址对应的结点的前面进行插入。所以，此时的插入可以分为两步：

1.将新结点存储查找函数找到的结点的地址，这里将用查找函数找到的地址用指针pos存储。即：

2. 将原来pos对应的结点的前一个结点中存储的地址，改为存储新结点的地址，即：

 用代码表示上述过程，即：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(*phead);if (*phead == NULL){SLTPushFront(phead, x);}else{SLTNode* prev = *phead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

用下面的函数测试前插的功能：

void Testlist5()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");int x = 0;printf("请输入想要查找的值");scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);printf("插入后：");SLTInsert(&plist, pos, x*10);SLTPrint(plist);
}

结果如下：

4.3 在某一特定数据对应的结点后插入新结点：

原理与前插相似，这里不再叙述，只给出图形表示：

对应代码如下：

void SLTInsertafter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

测试函数如下：

void Testlist5()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");int x = 0;int y = 0;printf("请输入想要查找的值");scanf("%d %d", &x,&y);SLTNode* pos = SLTFind(plist, x);printf("插入后：");SLTInsert(&plist, pos, x*10);SLTPrint(plist);printf("\n");printf("前插\n");SLTInsertafter(pos, y * 10);SLTPrint(plist);
}

结果如下：

4.4 删除某一特定元素对应位置的结点：

对于删除结点，也要分三种情况：

1. 链表整体为空，检查指针合法性即可

2.链表内只有一个结点，相当于头删 

3.链表有多个结点。

对于第三种情况。与前插相同，也需要创建一个指针来改变pos前面的结点中存储的地址，具体对应的代码如下：

void SLTErase(SLTNode** phead, SLTNode* pos)
{assert(pos);if (pos == *phead){SLTPopFront(phead);}else{SLTNode* prev = *phead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

测试函数如下：

void Testlist6()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");printf("请输入想要查找的值");int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);SLTErase(&plist,pos);printf("\n");SLTPrint(plist);
}

结果如下：

 4.5删除某一特定元素对应位置后一个结点：

随机给出一个链表：

通过观察不难发现： 对于删除某一特定元素对应结点的后一个结点这个功能，对于两种情况是没有意义的：

1. 链表中没有结点。

2. 对应元素的结点恰好是最后一个结点。

所以，在进行删除之前，应该针对这两种情况进行地址的检查。

而对于删除，也需要创建一个新的指针，用来保存pos->nxet这个地址。如果不保存，则删除结点和链接结点之间会出现矛盾，例如：

如果不保存pos->nxet，若选择直接链接数据元素为3的结点，此时没有指针保存数据为2的结点的地址。如果先删除pos->nxet，也无法得到数据元素为3的结点的地址。所以应该创建一个新的指针，pos->nxet，用指针变量posNext保存这个地址。在进行链接数据元素为1,3这两个结点时，可以pos->next = posNext -> next来实现。删除数据元素为2的结点时，直接free(posNext)，代码如下：

//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//检查是否是最后一个结点SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);
}

测试函数如下：

void Testlist6()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");printf("请输入想要查找的值");int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);/*SLTErase(&plist,pos);printf("\n");SLTPrint(plist);*/SLTEraseAfter(pos);printf("\n");SLTPrint(plist);}

结果如下：

 5.总体代码：

5.1 头文件 SList.h:

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//创建结点
SLTNode* BuySListNode(SLTDataType x);//打印各节点的信息
void SLTPprint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);//头插
void SLTPushFront(SLTNode** phead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** phead);//头删
void SLTPopFront(SLTNode** phead);//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);//对应位置前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);//对应位置后插入：
void SLTInsertafter(SLTNode* pos, SLTDataType x);//对应位置前删除
void SLTErase(SLTNode** phead, SLTNode* pos);//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos);

5.1 函数功能实现——SLIst.c:

#include"SList.h"//创建结点
SLTNode* BuySListNode(SLTDataType  x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//打印结点信息
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (*phead == NULL){*phead = newnode;}else{SLTNode* tail = *phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}//头插：
void SLTPushFront(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *phead;*phead = newnode;
}//尾删
void SLTPopBack(SLTNode** phead)
{assert(*phead);if ((*phead)->next == NULL)//只有一个结点的情况{free(*phead);*phead = NULL;}else{SLTNode* tail = *phead;SLTNode* tailprev = NULL;while (tail->next != NULL){tailprev = tail;tail = tail->next;}free(tail);tailprev->next = NULL;}
}//头删
void SLTPopFront(SLTNode** phead)
{assert(*phead);SLTNode* newhead = (*phead)->next;free(*phead);*phead = newhead;
}//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (phead != NULL){if (tail->data == x){return tail;}else{tail = tail->next;}}return NULL;
}//特定位置前插入：
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(*phead);if (*phead == NULL){SLTPushFront(phead, x);}else{SLTNode* prev = *phead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}//特定位置后插入新结点
void SLTInsertafter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTErase(SLTNode** phead, SLTNode* pos)
{assert(pos);if (pos == *phead){SLTPopFront(phead);}else{SLTNode* prev = *phead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//检查是否是最后一个结点SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);
}

5.3 函数测试文件Test.c:

#include"SList.h"void Testlist1()
{printf("请输入想要插入的元素的个数：");int n = 0;scanf("%d", &n);SLTNode* plist = NULL;printf("\n请输入插入的元素：");for (size_t i = 0; i < n; i++){int val = 0;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);if (plist == NULL){plist = newnode;}else{newnode->next = plist;plist = newnode;}}SLTPrint(plist);printf("\n");SLTPushBack(&plist, 10000);SLTPrint(plist);printf("\n");
}void Testlist2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);printf("尾插");printf("\n");SLTPrint(plist);printf("\n");
}void Testlist3()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTPrint(plist);printf("\n尾删");SLTPopBack(&plist);SLTPopBack(&plist);SLTPopBack(&plist);printf("\n");SLTPrint(plist);}
void Testlist4()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);printf("\n");printf("头删");printf("\n");SLTPrint(plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);printf("\n");SLTPrint(plist);}void Testlist5()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");int x = 0;int y = 0;printf("请输入想要查找的值");scanf("%d %d", &x,&y);SLTNode* pos = SLTFind(plist, x);printf("插入后：");SLTInsert(&plist, pos, x*10);SLTPrint(plist);printf("\n");printf("前插\n");SLTInsertafter(pos, y * 10);SLTPrint(plist);printf("\n");
}void Testlist6()
{SLTNode* plist = NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);printf("\n");printf("请输入想要查找的值");int x = 0;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);/*SLTErase(&plist,pos);printf("\n");SLTPrint(plist);*/SLTEraseAfter(pos);printf("\n");SLTPrint(plist);}
int main()
{/*Testlist1();*//*Testlist2();*//*Testlist3();Testlist4();*//*Testlist5();*/Testlist6();return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/80711.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

FL Studio21高级中文版本下载及切换中文语言教程

FL Studio21高级中文版本下载及切换中文语言教程

FL Studio对新人有极高的友好度&#xff0c;成为编曲软件的入门首选&#xff01;FL Studio官方提供多达31款各类插件&#xff0c;令你编曲功力大涨&#xff01;FL Studio是超多顶级音乐人的启蒙首选&#xff01;包括百大DJ冠军Martin Garrix&#xff0c;六获格莱美提名的Deadma…
阅读更多...
Java入门2022黑马-200-1

Java入门2022黑马-200-1

1-5 常用cmd命令 dir可以查看隐藏的文件&#xff0c; exit 退出 6-20 20-30 30-40 37 三元表达式 switch新特性 统计 while continue break 50
阅读更多...
ELK企业级日志分析系统

ELK企业级日志分析系统

目录 一、ELK 概述 1.ElasticSearch 2.Kiabana 3.Logstash 可以添加的其它组件 1.Filebeat 2.Fluentd 三、为什么要使用 ELK 四、ELK 的工作原理 五、 ELK Elasticsearch 集群部署 更改主机名、配置域名解析、查看Java环境 部署 Elasticsearch 软件 修改elasticsearc…
阅读更多...
怎么合并多个视频？简单视频合并方法分享

怎么合并多个视频？简单视频合并方法分享

合并多个视频可以将它们组合成一个更长的视频&#xff0c;这对于需要播放多个短视频的情况非常有用。此外&#xff0c;合并视频还可以使视频编辑过程更加高效&#xff0c;因为不必将多个独立的视频文件分别处理。最后&#xff0c;合并视频可以减少文件数量&#xff0c;从而使整…
阅读更多...
K8S系列文章之 Kind 部署K8S的 服务发布

K8S系列文章之 Kind 部署K8S的 服务发布

安装kind 下载 https://github.com/kubernetes-sigs/kind/releases/download/0.17.0/kind-linux-amd64 执行以下命令&#xff1a; mv kind-linux-amd64 /usr/local/bin/kind chmod 777 /usr/local/bin/kind 之前需要先在本地主机安装好docker yum -y install yum-utils d…
阅读更多...
vscode Google代码风格设置无效解决

vscode Google代码风格设置无效解决

1. 采用第一个方法设置google代码设置风格 2. 安装了clangd后需要在格式化风格做选择 vscode 安装 clang-format插件 $ code /home/tony/.config/Code/User/settings.json 这就能解决google风格设置无效的问题了&#xff0c;原来根因在于使用的格式化插件没有生效导致&#xf…
阅读更多...
MemFire教程｜FastAPI+MemFire Cloud+LangChain开发ChatGPT应用-Part2

MemFire教程｜FastAPI+MemFire Cloud+LangChain开发ChatGPT应用-Part2

基本介绍 上篇文章我们讲解了使用FastAPIMemFire CloudLangChain进行GPT知识库开发的基本原理和关键路径的代码实现。目前完整的实现代码已经上传到了github&#xff0c;感兴趣的可以自己玩一下&#xff1a; https://github.com/MemFire-Cloud/memfirecloud-qa 目前代码主要…
阅读更多...
VIM 编辑器： Bram Moolenaar

VIM 编辑器： Bram Moolenaar

VIM 用了很长时间&#xff0c; 个人的 VIM 配置文件差不多10年没有更新了。以前写程序的时候&#xff0c; 编辑都用这个。 linux kernel&#xff0c; boost规模的代码都不在话下。现在虽然代码写的少了&#xff0c;依然是我打开文件的首选。 现在用手机了&#xff0c;配个蓝牙键…
阅读更多...
UE中低延时播放RTSP监控视频解决方案

UE中低延时播放RTSP监控视频解决方案

第1章 方案简介 1.1 行业痛点 在各种智慧城市、智慧社区、智慧水利、智慧矿山等数字孪生项目中&#xff0c;经常使用通UE来开发三维可视化场景。在这些场景中通常都需要把现场的各种监控视频在UE的可视化场景中接入&#xff0c;主要包含海康威视、大华、宇视、华为等众多监控…
阅读更多...
腾讯云-宝塔添加MySQL数据库

腾讯云-宝塔添加MySQL数据库

1. 数据库菜单 2. 添加数据库 3. 数据库添加成功 4. 上传数据库文件 5. 导入数据库文件 6. 开启数据库权限 7. 添加安全组 (宝塔/腾讯云) 8. Navicat 连接成功
阅读更多...
小白到运维工程师自学之路 第六十五集 （docker-compose）

小白到运维工程师自学之路 第六十五集 （docker-compose）

一、概述 Docker Compose 的前身是 Fig&#xff0c;它是一个定义及运行多个 Docker 容器的工具。可以使用YAML文件来配置应用程序的服务。然后&#xff0c;使用单个命令&#xff0c;您可以创建并启动配置中的所有服务。Docker Compose 会通过解析容器间的依赖关系&#xff08;…
阅读更多...
网络编程——深入理解TCP/IP协议——OSI模型和TCP/IP模型：构建网络通信的基石

网络编程——深入理解TCP/IP协议——OSI模型和TCP/IP模型：构建网络通信的基石

TCP/IP协议— 一、简介 TCP/IP协议&#xff0c;即传输控制协议/互联网协议&#xff0c;是一组用于在计算机网络中实现通信的协议。它由两个主要的协议组成&#xff1a;TCP&#xff08;传输控制协议&#xff09;和IP&#xff08;互联网协议&#xff09;。TCP负责确保数据的可靠…
阅读更多...
一、安全世界观

一、安全世界观

文章目录 1、 Web安全简史1.1 中国黑客简史1.2 黑客技术的发展历程1.3 web安全的兴起 2、黑帽子、白帽子3、安全的本质4、安全三要素5、如何实施安全评估5.1 资产等级划分5.2 威胁分析5.3 风险分析5.4 设计安全方案 6、白帽子兵法6.1 Secure By Default6.2 纵深防御原则6.3 数据…
阅读更多...
iOS永久签名工具 - 轻松签使用教程

iOS永久签名工具 - 轻松签使用教程

轻松签是一款IOS端免费的IPA签名和安装工具&#xff0c;最新版可以不用依赖证书对ipa永久签名&#xff0c;虽然现在用上了巨魔&#xff08;TrollStore&#xff09;- 是国外iOS开发人员opa334dev发布的一款工具&#xff0c;可以在不越狱的情况下&#xff0c;安装任何一款APP。 …
阅读更多...
科大讯飞分类算法挑战赛2023的一些经验总结

科大讯飞分类算法挑战赛2023的一些经验总结

引言: ResNet是he kaiming大佬的早年神作&#xff0c;当年直接刷榜各大图像分类任务。ResNet是一种残差网络&#xff0c;咱们可以把它理解为一个子网络&#xff0c;这个子网络经过堆叠可以构成一个很深的网络&#xff0c;而ResNext在其基础上&#xff0c;进行了一定修改完善&am…
阅读更多...
【vim 学习系列文章 4 - vim与系统剪切板之间的交互】

【vim 学习系列文章 4 - vim与系统剪切板之间的交互】

文章目录 背景1.1.1 vim支持clipboard 检查1.1.2 vim的寄存器 上篇文章&#xff1a;【vim 学习系列文章 3 - vim 选中、删除、复制、修改引号或括号内的内容】 背景 从vim中拷贝些文字去其它地方粘贴&#xff0c;都需要用鼠标选中vim的文字后&#xff0c;Ctrlc、Ctrlv&#x…
阅读更多...
集成学习：机器学习模型如何“博采众长”

集成学习：机器学习模型如何“博采众长”

前置概念 偏差 指模型的预测值与真实值之间的差异&#xff0c;它反映了模型的拟合能力。 方差 指模型在不同的训练集上产生的预测结果的差异&#xff0c;它反映了模型的稳定性。 方差和偏差对预测结果所造成的影响 在机器学习中&#xff0c;我们通常希望模型的偏差和方差都…
阅读更多...
c++11 标准模板（STL）（std::basic_fstream）（一）

c++11 标准模板（STL）（std::basic_fstream）（一）

定义于头文件 <fstream> template< class CharT, class Traits std::char_traits<CharT> > class basic_fstream : public std::basic_iostream<CharT, Traits> 类模板 basic_fstream 实现基于文件的流上的高层输入/输出。它将 std::basic_i…
阅读更多...
2023牛客暑期多校训练营6 A-Tree (kruskal重构树))

2023牛客暑期多校训练营6 A-Tree (kruskal重构树))

文章目录 题目大意题解参考代码 题目大意 ( 0 ≤ a i ≤ 1 ) , ( 1 ≤ c o s t i ≤ 1 0 9 ) (0\leq a_i\leq 1),(1 \leq cost_i\leq 10^9) (0≤ai​≤1),(1≤costi​≤109) 题解 提供一种新的算法&#xff0c;kruskal重构树。 该算法重新构树&#xff0c;按边权排序每一条边…
阅读更多...
【IMX6ULL驱动开发学习】01.IMX6ULL驱动开发_编写第一个hello驱动（不涉及硬件操作）

【IMX6ULL驱动开发学习】01.IMX6ULL驱动开发_编写第一个hello驱动（不涉及硬件操作）

目录 一、驱动程序编写流程 二、代码编写 2.1 驱动程序hello_drv.c 2.2 测试程序 2.3 编写驱动程序的Makefile 三、上机实验 3.1 NFS 挂载 3.2 测试示例 一、驱动程序编写流程 构造file_operations结构体 在里面填充open/read/write/ioctl成员 注册file_operations结…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023