目录
1、单链表
1.1 概念
1.2 链表结构分析
1.3 单链表的基本操作
1.4 单链表的基本操作源码
1、单链表
1.1 概念
单链表是一种简单的链表表示，也叫做线性链表。用它来表示线性表时，用指针表示结点间的逻辑关系。因此单链表的一个存储结点包含两部分内容：
data 部分称为数据域，用于存储线性表的一个数据元素；next 部分称为指针域，用于存放一个指针，该指针是该链表下一个结点的开始存储地址。下面对单链表的逻辑结构和物理逻辑进行分析。
1.2 链表结构分析
单链表逻辑结构：
逻辑结构： 想象出来的，形象，方便理解。结构图如下：
单链表物理结构：
物理结构：在内存中实实在在如何存储的。物理结构图如下：
上面对逻辑结构和物理结构进行了分析需要注意如下几点：
（1）从上图看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
（2）现实中的结点一般都是从堆上申请出来的。
（3）从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
单链表的第 1个结点，也称为首节点，它的地址可以通过链表的头指针 head 找到，其他节点的地址通过前结点的 next 域找到，链表的最后一个结点没有后继，则在 next 域放一个空指针NULL。
线性表中的数据元素的顺序与其链表表示中的物理顺序可能不一致，一般是通过单链表的指针将各个数据元素按照线性表的逻辑顺序链接起来。当 head 为空时，则单链表为空表，否则为非空表。
1.3 单链表的基本操作
链表是一种动态的数据结构，在程序中需要使用 malloc() 或者使用动态内存开辟的其他函数创建链表。为了有效地存储结点数据，并且实现链表的链式功能，可建立 SListNode 结构体。代码如下：
typedef int SLTDataType;//使用 STDataType 代替 int
typedef struct SListNode
{
SLTDataType data;//数据域
struct ListNode* pnext;//指针域
}SListNode;
1.链表结点的创建
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//定义一个结构体指针变量，该指针变量在使用前必须分配存储空间。
newnode->data = x;//然后输入值初始化结点数据
newnode->pnext = NULL;//同时初始化该结点指向的下一个结点为空。
return newnode;
}
分析：运行上面的结构的声明后，SListNode 就成为一个动态指针结构。建立了结点的结构后，接下来定义一个结构体指针变量，该指针变量在使用前必须分配存储空间，然后输入值初始化结点数据，同时初始化该结点指向的下一个结点为空。
2.链表尾插
分析：尾插是什么意思呢？尾插的意思就是把新创建好的链表插放到该链表的尾部。如下图：
那我们该怎么做呢？其实很简单，就是让 结点 4 指针域的指针存储着新结点的地址就可以了。如下图：
// 链表尾插
void SListPushBack(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*head == NULL)//判断链表是不是为空
{
*head = newnode;
}
else
{
SListNode* tail = *head;
while (tail->pnext != NULL)//如果head不为空，那么我们就要找到尾结点，找到尾结点才能尾插。
{
tail = tail->pnext;
}
tail->pnext = newnode;
}
}
看了代码之后有的人就觉得和上面说的不一样了。其实不然，我们在尾插的时候需要考虑链表 head 是不是空的链表，如果是空的，那么新结点 newnode 就作为头结点。如下图：
head 为什么是二级指针呢？我们都知道通过指针去改变指向空间的内容，传一级指针；改变指针的指向，传二级指针，因为 head 指向的是一个空，我们要改变指针的指向就要传指针 head 的地址，用二级指针存储一级指针的地址，只有拿到地址后，我们才能通过地址去改变 head 指针的指向。
如果 head 不为空，那么我们就要找到尾结点，通过遍历，找到尾结点后进行尾插。
3.链表头插
头插是什么意思？头插就是在原链表的头结点前面插入一个 newnode，如下图：
把 newnode 指针域的指针指向 结点1 的存储地址，然后更新一下头指针，这个时候 newnode 就成为新的头指针。如下图：
即使 head 为空亦如此，如下图：
// 链表的头插
void SListPushFront(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->pnext = *head;
*head = newnode;
}
4.链表尾删
//链表尾删
void SListPopBack(SListNode** head)
{
assert(*head);//判断是不是空链表，是空的链表就删不了。
if ((*head)->pnext==NULL)//判断是不是只有一个结点
{
free(*head);//释放内存空间
*head = NULL;//将头结点置空
}
else
{
SListNode* tail = *head;
SListNode* previous = NULL;
while (tail->pnext!= NULL)//找尾结点
{
previous = tail;//记录上一个结点
tail = tail->pnext;
}
free(tail);//释放该内存空间-->也就是删除
tail = NULL;
previous->pnext = NULL;//将新的尾结点置ko
}
}
链表尾删就是把链表的最后一个结点删除掉，就达到尾删的效果了。首先判断链表是不是空链表，空链表就删不了。随后判断是不是只有一个结点，如果链表只有一个结点（头结点），那就对头结点进行释放，然后对指向头结点的头指针置空。如下图：
第三种情况就是对非空，非一个结点的链表进行操作。尾删之前，得先找到尾结点才能对该结点进行删除。找到尾结点了，删除之前我们还要找到尾结点的上一个结点的地址。因为尾删之后，尾结点的上一个结点就成为尾结点了，尾结点指针域的指针要置空，否则会造成非法访问。操作如下图：
5.链表头删
头删就是把头结点删除，然后指针 head 指向第二个结点，此时，也就是成为头结点。
// 链表头删
void SListPopFront(SListNode** head)
{
assert(*head);
SListNode* temp = *head;
*head = (*head)->pnext;
free(temp);
temp = NULL;
}
头删之前先检查链表是不是为空链表，如果为空链表，就会报错，终止程序。这里我是用断言对链表是否为空进行检查，对头结点删除的操作如下图：
6.链表查找
链表查找意思是对链表中的数据进行查找，若找到了返回该数据的地址（也就是该数据结点的地址），若找不到则返回空指针；查找之前先用断言判断该链表是否为空链表，查找的方式是对该链表进行遍历。
// 链表查找
SListNode* SListFind(SListNode* head, SLTDataType x)
{
assert(head);
SListNode* current = head;
while (current != NULL)
{
if (current->data == x)
{
return current;
}
current = current->pnext;
}
return NULL;
}
7.在 pos 位置之前插入一个数据
//在pos位置之前插入x
void SListInsertBefore(SListNode** head,SListNode* pos, SLTDataType x)
{
assert(*head);//如果是空链表，则不进行操作。
SListNode* newnode = BuySListNode(x);
if (*head == pos)
{
newnode->pnext = *head;
*head = newnode;
}
else
{
SListNode* previous = *head;
while (previous->pnext != pos)
{
previous = previous->pnext;
}
previous->pnext = newnode;
newnode->pnext = pos;
}
}
第一种情况：判断 pos 是不是头结点，如果是头结点，那么就进行头插。第二种情况：如果 pos 不是头结点，那么就要先找到 pos 的前一个结点的位置。找到 pos 的前一个结点的位置，使 pos 前一个结点指针域的指针储存插入的结点 newnode，然后再将 newnode 指针域的指针储存 pos。如下图：
7.在 pos 位置之后插入一个数据
// 在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* temp = pos->pnext;
pos->pnext = newnode;
newnode->pnext = temp;
}
相对于在 pos 位置之前插入一个数据，在 pos 位置之后插入一个数据更加简单。 使用一个指针变量 temp 储存 pos 下一个位置的地址，然后将 pos 指针域的指针储存 newnode，newnode 指针域的指针储存 temp 的地址，就达到 pos 之后插入一个数据了。如下图：
8.删除 pos 位置之前的值
// 链表删除pos位置之前的值
void SListEraseBefore(SListNode** head, SListNode* pos)
{
assert(*head&&pos);//判断链表和pos是否为空
if (*head ==pos)
{
return;
}
else
{
SListNode* previous = NULL;
SListNode* current = *head;
if (current->pnext == pos)
{
free(*head);
*head = pos;
}
else
{
while (current->pnext != pos)
{
previous = current;
current = current->pnext;
}
free(current);
current = NULL;
previous->pnext = pos;
}
}
}
第一种情况：如果pos为头结点，直接return；第二种情况：pos不为头结点，先判断pos是不是第二个结点，如果是第二个结点，那就属于头删。如果pos不是第二节点，要对pos的前一个结点进行删除，那就要找到 pos 的前一个结点，和 pos 前前一个结点。再将 pos 的前一个结点删除，再把 pos 的前前一个结点的指针域的指针指向 pos。如下图：
9.删除pos位置之后的值
// 删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
//if (pos->pnext == NULL)
//{
// return;
//}
assert(pos);//判断pos是否为空
SListNode* posafter = pos->pnext;//pos的下一个结点
SListNode* posafterafter = posafter->pnext;//pos的下下一个结点
pos->pnext = posafterafter;
free(posafter);
posafter = NULL;
//②
//SListNode* next = pos->pnext;
//pos->pnext = next->pnext;
//free(next);
//next = NULL;
}
删除pos之后的值，需要找到 pos 的下一个结点和 pos 的下下一个结点。然后再将 pos 的下一个删除，最后再将 pos 指针域的指针指向 pos 的下下一个结点的地址。如下图：
10.删除 pos 的位置的值
//删除 pos 位置的结点
void SListErase(SListNode** head, SListNode* pos)
{
assert(*head&&pos);//判断head和pos是否为空
if (pos == *head)
{
/*SListNode* temp = *pplist;
*pplist = (*pplist)->pnext;
free(temp);
temp = NULL;*/
*head = pos->pnext;
free(pos);
}
else
{
SListNode* current = *head;
SListNode* posafter = pos->pnext;
while (current->pnext != pos)
{
current = current->pnext;
}
free(pos);
pos = NULL;
current->pnext = posafter;
}
}
第一种情况：如果 pos 等于 head ，那就相当于头删；第二种情况：pos 不等于 head ，想要删除 pos 位置的结点，那么就要先找出 pos 前一个结点和 pos 后一个结点。后一个容易找，就是 pos 指针域的指针存储的地址。那么 pos 的前一个结点就需要靠遍历链表找到的，当找到 pos 前一个结点时，就把 pos 前一个结点指针域的指针指向 pos 的下一个结点的地址。如下图：
11.释放链表的所有结点
//释放链表的所有结点
void SListDestroy(SListNode** head)
{
SListNode* current = *head;
while (current)
{
SListNode* next = current->pnext;
free(current);
current = next;
}
*head = NULL;
}
释放链表，就是将链表中的所有结点进行释放，释放的方法是：遍历链表，记住当前结点的下一个结点的地址，然后释放当前的结点，再把 当前结点的下一个结点的地址 赋值给当前结点，直到释放完全部链表的结点。最后，将 head 指针置空。
12.链表打印
// 打印链表中的数据
void SListPrint(SListNode* head)
{
SListNode* current = head;
while (current!= NULL)
{
printf("%d->", current->data);
current = current->pnext;
}
printf("NULL");
printf("\n");
}
从头结点到尾结点开始遍历，将一个一个结点的数据打印出来。
1.4 单链表的基本操作源码
SList.h
#pragma
#include
#include
#include
typedef int SLTDataType;//使用 STDataType 代替 int
typedef struct SListNode
{
SLTDataType data;//数据域
struct ListNode* pnext;//指针域
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* head);
// 单链表尾插
void SListPushBack(SListNode** head, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** head, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** head);
// 单链表头删
void SListPopFront(SListNode** head);
// 单链表查找
SListNode* SListFind(SListNode* head, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
//在pos位置之前插入x
void SListInsertBefore(SListNode** head, SListNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseBefore(SListNode** head, SListNode* pos);
// 单链表删除pos位置之前的值
void SListEraseAfter(SListNode* pos);
//删除掉当前的位置
void SListErase(SListNode** head, SListNode* pos);
//释放链表
void SListDestroy(SListNode** head);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
newnode->data = x;
newnode->pnext = NULL;
return newnode;
}
// 打印链表中的数据
void SListPrint(SListNode* head)
{
SListNode* current = head;
while (current!= NULL)
{
printf("%d->", current->data);
current = current->pnext;
}
printf("NULL");
printf("\n");
}
// 单链表尾插
void SListPushBack(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*head == NULL)
{
*head = newnode;
}
else
{
SListNode* tail = *head;
while (tail->pnext != NULL)
{
tail = tail->pnext;
}
tail->pnext = newnode;
}
}
// 单链表的头插
void SListPushFront(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->pnext = *head;
*head = newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** head)
{
assert(*head);
if ((*head)->pnext==NULL)
{
free(*head);
*head = NULL;
}
else
{
SListNode* tail = *head;
SListNode* previous = NULL;
while (tail->pnext!= NULL)
{
previous = tail;
tail = tail->pnext;
}
free(tail);
tail = NULL;
previous->pnext = NULL;
}
}
// 单链表头删
void SListPopFront(SListNode** head)
{
assert(*head);
SListNode* temp = *head;
*head = (*head)->pnext;
free(temp);
temp = NULL;
}
// 单链表查找
SListNode* SListFind(SListNode* head, SLTDataType x)
{
assert(head);
SListNode* current = head;
while (current != NULL)
{
if (current->data == x)
{
return current;
}
current = current->pnext;
}
return NULL;
}
//在pos位置之前插入x
void SListInsertBefore(SListNode** head,SListNode* pos, SLTDataType x)
{
assert(*head);
SListNode* newnode = BuySListNode(x);
if (*head == pos)
{
newnode->pnext = *head;
*head = newnode;
}
else
{
SListNode* previous = *head;
while (previous->pnext != pos)
{
previous = previous->pnext;
}
previous->pnext = newnode;
newnode->pnext = pos;
}
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* temp = pos->pnext;
pos->pnext = newnode;
newnode->pnext = temp;
}
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** head, SListNode* pos)
{
assert(*head&&pos);
if (*head ==pos)
{
return;
}
else
{
SListNode* previous = NULL;
SListNode* current = *head;
if (current->pnext == pos)
{
free(*head);
*head = pos;
}
else
{
while (current->pnext != pos)
{
previous = current;
current = current->pnext;
}
free(current);
current = NULL;
previous->pnext = pos;
}
}
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
//if (pos->pnext == NULL)
//{
// return;
//}
assert(pos);
SListNode* posafter = pos->pnext;
SListNode* posafterafter = posafter->pnext;
pos->pnext = posafterafter;
free(posafter);
posafter = NULL;
//②
//SListNode* next = pos->pnext;
//pos->pnext = next->pnext;
//free(next);
//next = NULL;
}
//删除 pos 位置的结点
void SListErase(SListNode** head, SListNode* pos)
{
assert(*head &&pos);
if (pos == *head)
{
/*SListNode* temp = *pplist;
*pplist = (*pplist)->pnext;
free(temp);
temp = NULL;*/
*head = pos->pnext;
free(pos);
}
else
{
SListNode* current = *head;
SListNode* posafter = pos->pnext;
while (current->pnext != pos)
{
current = current->pnext;
}
free(pos);
pos = NULL;
current->pnext = posafter;
}
}
//释放链表的所有结点
void SListDestroy(SListNode** head)
{
SListNode* current = *head;
while (current)
{
SListNode* next = current->pnext;
free(current);
current = next;
}
*head = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test()
{
SListNode* head = NULL;
printf("尾插:> ");
SListPushBack(&head, 1);//尾插
SListPushBack(&head, 2);
SListPushBack(&head, 3);
SListPushBack(&head, 4);
SListPrint(head);//链表打印
printf("头插:> ");
SListPushFront(&head, 4); //头插
SListPushFront(&head, 3);
SListPushFront(&head, 2);
SListPushFront(&head, 1);
SListPrint(head);
printf("尾删:> ");
SListPopBack(&head);//尾删
SListPopBack(&head);
SListPrint(head);
printf("头删:> ");
SListPopFront(&head);//头删
SListPopFront(&head);
SListPrint(head);
printf("在 pos 位置之前插入一个数据 10 :> ");
SListNode* pos = SListFind(head, 1);//查找
SListInsertBefore(&head,pos, 10);//在 pos 位置之前插入一个数据
SListPrint(head);
printf("在 pos 位置之后插入一个数据 40 :> ");
pos = SListFind(head, 4);//查找
SListInsertAfter(pos, 40);//在 pos 位置之后插入一个数据
SListPrint(head);
printf("删除 pos 位置之前的值:> ");
pos = SListFind(head, 1);//查找
SListEraseBefore (&head,pos);//删除 pos 位置之前的值
SListPrint(head);
printf("删除 pos 位置之后的值:> ");
pos = SListFind(head, 4);//查找
SListEraseAfter(pos);//删除 pos 位置之后的值
SListPrint(head);
printf("删除 pos 位置的值:> ");
pos = SListFind(head, 4);//查找
SListErase(&head,pos);//删除 pos 位置的值
SListPrint(head);
SListDestroy(&head);//释放链表
}
int main()
{
test();
return 0;
}
好文推荐
发表评论