C语言菜鸟入门·数据结构·链表超详细解析

 

目录

1.  单链表

1.1  什么是单链表

1.1.1  不带头节点的单链表

1.1.2  带头结点的单链表

1.2  单链表的插入

1.2.1  按位序插入

（1）带头结点

（2）不带头结点

1.2.2  指定结点的后插操作

1.2.3  指定结点的前插操作

1.3  单链表的删除

1.3.1  按位序删除

1.3.2  指定结点的删除

---

1.  单链表

1.1  什么是单链表

        对比于顺序表的每个节点只存放数据元素，单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。

顺序表：

优点：可随机存储，存储密度较高；

缺点：要求大片连续空间，改变容量不方便。

单链表：

优点：不要求大片连续空间，改变容量方便；

缺点：不可随机存取，要耗费一定空间存放指针。

        对于单链表的每一个结点，都需要有一个数据域用于存放节点的数据元素，需要一个指针域用于指向下一个结点。

struct LNode{ElemType data;struct LNode *next;
};

对于struct关键字的用法可参考：C语言菜鸟入门·结构体·struct用法超详细解析_c语言数据结构菜鸟-CSDN博客

        而若是我们想要增加一个新的结点，我们可以使用malloc关键字，例如：

        首先，我们先声明一个指向struct LNode类型的对象p，通过malloc函数动态分配内存大小为struct LNode类型大小的内存。

struct LNode* p=(struct LNode*)malloc(sizeof(struct LNode));

        对于每次增加一个新的结点，我们每次都需要加上struct LNode这样声明起来有些太麻烦了。那么要怎么简单点呢？我们可以使用typedef进行重命名操作，那么就可以写为：

struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;

其中对于typedef的操作可以参考：C语言菜鸟入门·各种typedef用法超详细解析-CSDN博客中的结构体介绍。

1.1.1  不带头节点的单链表

        我们使用typedef后，可以开始创建一个不带头节点的单链表：

struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//初始化一个空链表
bool InitList(LinkList &L)
{L = NULL;  //空表，按时还没任何结点，防止脏数据return trun;
}void test()
{Linklist L;//声明一个指向单链表的指针，注意此处没有创建一个结点//初始化一个空表InitList(L);//····后续代码····
}

        其作用是判断单链表是否为空，通过头指针L，初始化一个空表，防止脏数据：

        其中初始化一个空链表的代码也可以写为：

bool Empty(LinkList L)
{if(L==NULL)return true;elsereturn true;        
}

        或者：

bool Empty(LinkList L)
{return (L==NULL);      
}

1.1.2  带头结点的单链表

struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//初始化一个空链表
bool InitList(LinkList &L)
{L = (LNode*)malloc(sizeof(LNode));//分配一个头节点if(L == NULL)//内存不足，分配失败return false;L->next = NULL;//头结点之后暂时还没有结点return true;}void test()
{Linklist L;//声明一个指向单链表的指针//初始化一个空表InitList(L);//····后续代码····
}

        不带头结点的头指针指向的下一个结点，这个结点就是实际用于存放数据的结点，

        带头节点的头指针指向的下一个结点，这个结点不用来存放实际的数据元素的，只有这个结点的下一个结点才会用来存放数据。

1.2  单链表的插入

1.2.1  按位序插入

（1）带头结点

        插入操作，例如在表L中的第i个位置上插入指定元素e：

Listlnsrrt(&L,i,e);

        我们要如何来实现插入操作呢？我们要想在i个位置上插入，那么我们就需要找到第i-1个结点，将新的节点插入其后，假设我们的i=2的话（a2），那么我们就需要找到其前一个结点（a1）的结点，然后我们使用malloc函数，申请一个新的结点，往这个结点存入指针e，然后修改指针，就可以得到：

struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;//在第i个位置上插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{if (i<1)return false;LNode* p;//指针p指向当前扫描到的结点int j = 0;//指针p指向第几个结点p = L;//L指向头结点，头结点是第0个结点（不存数据）while (p != NULL && j < i - 1)//循环找到第i-1个结点{p = p->next;j++;}if(p==NULL)//i值不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->date = e;s -> next = p->next;//将结点s连接到p之后p -> next = s;//插入成功return true;}

    s->date = e;s -> next = p->next;//将结点s连接到p之后p -> next = s;//插入成功

（2）不带头结点

        由于不带头结点，所以不存在头结点是0的情况，那么数据处理为：

struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;//在第i个位置上插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, ElemType e)
{if (i<1)return false;if (i == 1)//插入第1个节点的操作与其他结点操作不同{LNode* s = (LNode*)malloc(sizeof(LNode));s->date = e;s - next = L;L = s;return true;}LNode* p;//指针p指向当前扫描到的结点int j = 1;//指针p指向第几个结点p = L;//L指向头结点，头结点是第0个结点（不存数据）while (p != NULL && j < i - 1)//循环找到第i-1个结点{p = p->next;j++;}if(p==NULL)//i值不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->date = e;s -> next = p->next;//将结点s连接到p之后p -> next = s;//插入成功return true;}

1.2.2  指定结点的后插操作

        后插操作比较简单，对比按位序插入，仅仅将其改为指定插入，就明确告诉你我要插哪里：

struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;bool InsertNextNode(LinkList* p, ElemType e)
{if(p==NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if(s==NULL)return false;s->date = e;s -> next = p->next;p -> next = s;return true;
}

1.2.3  指定结点的前插操作

        在链表中，我们并不能通过后一节点的数据data找到，前一个结点的指针域next，那我们要如何实现前插操作呢？

例如：我们想在结点1之前插入一个结点：

        首先，我们先创建一个结点：

         然后，我们既然找不到前驱结点，干脆不找了，直接将结点1的数据data1以及指针域next1复制到新建的结点，这样复制的结点数据就和结点1的数据相同：

        然后我们在将想要插入的结点赋值给结点1：

        然后将插入结点的next指向复制的结点1的data，让复制的结点1的next指向结点2的data，此时的复制结点1和结点1是相同的，结点插在复制的结点1之前，等价于结点插，插入到结点1之前：

struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;bool InsertNextNode(LinkList* p, ElemType e)
{if(p==NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if(s==NULL)return false;s -> next = p->next;p -> next = s;s->date = p->data;p->data = e;return true;
}

1.3  单链表的删除

1.3.1  按位序删除

        删除操作，删除表L中的第i个位置的元素，并用e返回删除元素的值：

ListDelete(&L,i,&e);

        简单来说就是找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。

struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;bool ListDelete(LinkList& L, int i, ElemType &e)
{if (i<1)return false;LNode* p;//指针p指向当前扫描到的结点int j = 0;//指针p指向第几个结点p = L;//L指向头结点，头结点是第0个结点（不存数据）while (p != NULL && j < i - 1)//循环找到第i-1个结点{p = p->next;j++;}if(p==NULL)//i值不合法return false;if (p->next == NULL)//第i-1个结点之后已无其他结点return false;LNode* q = p->next;//令q指向被删除的结点e = q->date;//用e返回元素的值p - next = q->next;//将*q结点从链中“断开”free(q);//释放结点的存储空间return true;}

1.3.2  指定结点的删除

        指定结点的删除，删除结点p，需要修改其前驱节点的next指针。有两种方法：

方法1：传入头指针，循环寻找p的前驱结点；

方法2：类似于结点前插的实现方式。

bool DeleteNode(LNode *p)
{if(p==NULL)//i值不合法return false;LNode* q = p->next;//令q指向*p的后续结点p->date = p -> next->date;//和后续结点交换数据域p -> next = q->next;//将*q结点从链中“断开”free(q);//释放结点的存储空间return true;
}

        但是以上代码，若是p是最后一个节点，那么代码：

    p->date = p -> next->date;//和后续结点交换数据域

        就会发生错误，解决方法：我们就只能从表头开始一次寻找p的前驱。

C语言_时光の尘的博客-CSDN博客