数据结构————单链表

大家好，欢迎来到IT知识分享网。

目录

一、单链表的定义及其特点

定义

特点

二、单链表的实现

  准备工作：

1.单链表的创建

1.1头插法介绍

1.2尾插法介绍

总结：

2.单链表的初始化

3.单链表的求表长

4.单链表的销毁

5.单链表的插入

6.单链表的查找

 6.1按序查找

6.2按值查找

7.单链表的删除元素

全部代码：

结语： 

一、单链表的定义及其特点

定义

  单链表（Singly Linked List）是一种基本的数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，而指针域则存储指向链表中下一个节点的地址。在单链表中，除了最后一个节点外，每个节点的指针域都指向下一个节点，最后一个节点的指针域通常设置为NULL，以标识链表的结束。单链表的特点是其存储不需要连续的内存空间，节点可以分散在内存中的任意位置，通过指针连接形成线性结构。 

特点

1. 动态存储：单链表的长度可以动态变化，可以根据需要动态地添加或删除节点。
2. 非连续存储：节点在内存中的位置不需要连续，只需通过指针连接即可。
3. 易于插入和删除：在单链表中插入或删除节点只需修改相应节点的指针，时间复杂度为O(1)，但前提是能够快速访问到要操作的节点或其前驱节点。
4. 不支持随机访问：访问单链表中的特定节点需要从头节点开始逐个遍历，时间复杂度为O(n)。
5. 额外空间存储指针：每个节点除了存储数据外，还需要额外的空间来存储指向下一个节点的指针。
6. 头指针：单链表通常有一个头指针，用于访问链表的第一个节点。头指针可能指向头节点（头节点包含数据）或直接指向第一个实际数据节点（头节点不存储数据）。 

二、单链表的实现

  准备工作：

自定义数据元素类型：

typedef int ElemType; 

结构体：

typedef struct LNode { ElemType data;//数据域 struct LNode* next;//指针域 }LinkNode; 

1.单链表的创建

单链表的创建通常涉及两种主要的插入方法：头插法和尾插法。

1.1头插法介绍

定义

  头插法指的是在单链表的头部插入节点。新节点的指针将指向当前的头节点，然后更新头指针以指向新节点。

特点

• 实现简单，插入操作时间复杂度为O(1)。
• 但链表元素的顺序与插入顺序相反，如果需要保持原有顺序，需要在插入后进行反转

大致实现步骤：

1. 创建新节点。
2. 将新节点的next指针设置为头指针所指向的节点。
3. 更新头指针，使其指向新节点。

代码：整体建立单链表，给定数组

void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode * s; //新节点 L = (LinkNode*)malloc(sizeof(LinkNode));//创建头节点 L->next = NULL;//头节点初始化 for (int i = 0; i < n; i++) { s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建 s->data = a[i];// 初始化 s->next = L->next; L->next = s; } }

1.2尾插法介绍

定义

  尾插法指的是在单链表的尾部插入节点。此方法下，新节点成为链表的最后一个节点。

特点

• 插入操作的时间复杂度为O(n)，因为可能需要遍历整个链表。
• 保持了数据的插入顺序，链表元素的顺序与插入顺序一致。

大致实现步骤：

1. 创建新节点。
2. 如果链表为空，新节点同时作为头节点和尾节点。
3. 如果链表非空，遍历链表找到尾节点，将尾节点的next指针指向新节点。

代码：整体建立单链表，给定数组

//<2>尾插法建立单链表 void CreateListR(LinkNode*& L, ElemType a[], int n) { LinkNode* r, * s;//尾指针和新的节点指针 L = (LinkNode*)malloc(sizeof(LinkNode)); r = L; //r始终指向尾节点，初始指向L for (int i = 0; i < n; i++) { s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建和初始化 s->data = a[i]; r->next = s;//将节点s插入到r后面 r = s; } r->next = NULL; //尾节点的next域置为NULL }

总结：

 头插法和尾插法各有优劣，选择哪种方法取决于具体的应用场景。如果需要快速插入节点且不关心元素的顺序，头插法是更好的选择。反之，如果要保持元素的插入顺序，尾插法则更为合适。在实际应用中，根据需求灵活选择插入方法，可以更高效地创建和管理单链表。

2.单链表的初始化

  创建一个头结点，并将其头结点的next域置空

void InitList(LinkNode*&L) { L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = NULL; }

3.单链表的求表长

 用p指向头结点，用n来累计数据节点的个数，n初始值为0；

int ListLength(LinkNode *L) { int n = 0; LinkNode* p = L; while (p->next != NULL) { n++; p = p->next; } return n; }

4.单链表的销毁

实现步骤：

1.  pre 和 p指向相邻的节点，初始pre 指向头结点，p指向首个数据节点。

2.p不为空时循环，释放pre节点，然后pre 和p 俩个节点后移。

3. 循环结束后pre指向尾节点，将其释放

代码：

/*【3】基本运算 ----销毁*/ void DestoryList(LinkNode*& L) { LinkNode* pre = L; LinkNode* p = L->next;//pre指向p的前驱节点 while (p != NULL) //遍历单链表L { free(pre);//释放前驱节点 pre = p; //移动 p = pre->next; } free(pre); //循环结束，p为NULLL,pre指向尾节点，释放它 }

5.单链表的插入

 给定单链表L ,在第i个位置插入节点s，值为e。

实现步骤：

1.在单链表L中找到第i-1个结点，由p指向他

2.若存在该结点，将值为e的s结点插入p节点的后面。

代码：

/*【7】基本运算 ----插入 在第i个位置前面插入节点， p指向第i-1个节点，将s节点插入p后面 */ bool ListInsert(LinkNode*& L, int i, ElemType e) { int j = 0; if (i <= 0)return false; LinkNode* s, * p=L; while (j < i-1 && p != NULL)//寻找i-1的节点，然后由p指向它 { j++; p = p->next; } if (p == NULL)//未找到·返回false { return false; } else { s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = e; s->next = p->next;//将新节点插入到p之后（i-1的节点） p->next = s; return true; } } 

6.单链表的查找

 6.1按序查找

实现步骤：

1. p指向头结点，用j来累计遍历过的数据结点的个数（初始值为0)，当j<i且不为空时循环：j增1,p指向下一个结点。

2. 循环结束后有两种情况，若为空，表示单链表L中没有第i个数据结点（参数i错误），返回false；否则找到第i个数据结点力，提取它的值并返回true。

代码：

/<2>按序号求线性表中的元素，给定单链表L,查找第i个节点的元素值，提取到e，存在返回true 否则返回false bool GetElem(LinkNode* L, int i, ElemType& e) { LinkNode* p = L;//p指向头结点i，j置为0，即头节点序号为0 int j = 0; if (i < 0)return false; while (j < i && p != NULL) { j++; p = p->next; } if (p == NULL)//不存在第 i 个数据节点，返回false { return false; } else//存在，取值 并返回true { e = p->data; return true; } }

6.2按值查找

 在单链表L中从头开始找到第一个值域为e的结点，找到返回逻辑序号，否则返回0

实现步骤： 

代码：

//<1>按元素查找节点的序号 给定单链表 L 查找值为e的节点的序号i，存在返回该序号，否则返回0 int LocateElem(LinkNode* L, ElemType e) { LinkNode* p = L->next; int n = 1; //逻辑序号，首节点位置为1 while (p->next != NULL && p->data != e)//查找该节点 { n++; p = p->next; } if (p == NULL)//不存在元素为e的节点 { return 0; } else //存在，返回逻辑序号n { return n; } }

7.单链表的删除元素

  给定单链表L，删除第i个节点，并将删除节点的值带回，p指向第i-1个节点,q为第i个节点，*/

实现步骤：

1.在单链表L中找到第i一1个结点，由p指向它。

2.若存在这样结点，且也存在后继结点（由q指向它），则删除通过结点pq所指的结点，返回true；否则回false,表示参数i错误。

代码：

/*【8】基本运算 ---- 删除 ，给定L，删除第i个节点，并将删除节点的值带回p指向第i-1个节点,q为第i个节点，*/ bool ListDelete(LinkNode*& L, int i, ElemType& e) { int j = 0; LinkNode* q, * p = L; if (i <= 0)return false; while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL)//没有找到第i-1个节点 返回false { return false; } else//找到第i-1和节点 ，进行删除操作 { q = p->next;//q指向第i个节点 if (q == NULL)return false; //这个容易忽略，我们也因该判断第i个元素是否为空 e = q->data; p->next = q->next; free(q); return true; } }

全部代码：

#include<stdlib.h> #include<stdio.h> typedef int ElemType; typedef struct LNode { ElemType data;//数据域 struct LNode* next;//指针域 }LinkNode; /*【1】整体建立单链表 给定数组a[n] */ //<1>头插法建立单链表 void CreateListF(LinkNode *&L,ElemType a[],int n) { LinkNode * s; //新节点 L = (LinkNode*)malloc(sizeof(LinkNode));//创建头节点 L->next = NULL;//头节点初始化 for (int i = 0; i < n; i++) { s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建 s->data = a[i];// 初始化 s->next = L->next; L->next = s; } } //<2>尾插法建立单链表 void CreateListR(LinkNode*& L, ElemType a[], int n) { LinkNode* r, * s;//尾指针和新的节点指针 L = (LinkNode*)malloc(sizeof(LinkNode)); r = L; //r始终指向尾节点，初始指向L for (int i = 0; i < n; i++) { s = (LinkNode*)malloc(sizeof(LinkNode));//新节点创建和初始化 s->data = a[i]; r->next = s;//将节点s插入到r后面 r = s; } r->next = NULL; //尾节点的next域置为NULL } /*【2】基本运算 ----初始化*/ void InitList(LinkNode*&L) { L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = NULL; } /*【3】基本运算 ----销毁*/ void DestoryList(LinkNode*& L) { LinkNode* pre = L; LinkNode* p = L->next;//pre指向p的前驱节点 while (p != NULL) //遍历单链表L { free(pre);//释放前驱节点 pre = p; //移动 p = pre->next; } free(pre); //循环结束，p为NULLL,pre指向尾节点，释放它 } /*【4】基本运算 ----求表的长度*/ int ListLength(LinkNode *L) { int n = 0; LinkNode* p = L; while (p->next != NULL) { n++; p = p->next; } return n; } /*【5】基本运算 ----输出线性表*/ void printLinkNode(LinkNode* L) { LinkNode* p = L->next;//指向头节点的下一个节点，头节点不存放数据 while (p!= NULL) { printf("%d->", p->data); p = p->next; } printf("end\n"); } /*【6】基本运算 ----查找 */ //<1>按元素查找节点的序号 给定单链表 L 查找值为e的节点的序号i，存在返回该序号，否则返回0 int LocateElem(LinkNode* L, ElemType e) { LinkNode* p = L->next; int n = 1; //逻辑序号，首节点位置为1 while (p->next != NULL && p->data != e)//查找该节点 { n++; p = p->next; } if (p == NULL)//不存在元素为e的节点 { return 0; } else //存在，返回逻辑序号n { return n; } } //<2>按序号求线性表中的元素，给定单链表L,查找第i个节点的元素值，提取到e，存在返回true 否则返回false bool GetElem(LinkNode* L, int i, ElemType& e) { LinkNode* p = L;//p指向头结点i，j置为0，即头节点序号为0 int j = 0; if (i < 0)return false; while (j < i && p != NULL) { j++; p = p->next; } if (p == NULL)//不存在第 i 个数据节点，返回false { return false; } else//存在，取值 并返回true { e = p->data; return true; } } /*【7】基本运算 ----插入 在第i个位置前面插入节点， p指向第i-1个节点，将s节点插入p后面 */ bool ListInsert(LinkNode*& L, int i, ElemType e) { int j = 0; if (i <= 0)return false; LinkNode* s, * p=L; while (j < i-1 && p != NULL)//寻找i-1的节点，然后由p指向它 { j++; p = p->next; } if (p == NULL)//未找到·返回false { return false; } else { s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = e; s->next = p->next;//将新节点插入到p之后（i-1的节点） p->next = s; return true; } } /*【8】基本运算 ---- 删除 ，给定L，删除第i个节点，并将删除节点的值带回p指向第i-1个节点,q为第i个节点，*/ bool ListDelete(LinkNode*& L, int i, ElemType& e) { int j = 0; LinkNode* q, * p = L; if (i <= 0)return false; while (j < i - 1 && p != NULL) { j++; p = p->next; } if (p == NULL)//没有找到第i-1个节点 返回false { return false; } else//找到第i-1和节点 ，进行删除操作 { q = p->next;//q指向第i个节点 if (q == NULL)return false; //这个容易忽略，我们也因该判断第i个元素是否为空 e = q->data; p->next = q->next; free(q); return true; } } int main() { int a[5]; int b[5] = { 1,2,3,4,5 }; for (int i = 0; i < 5; i++) { scanf_s("%d", &a[i]); } //用数组创建单链表 LinkNode * L1; LinkNode * L2; CreateListF(L1, a,5); //头插法 CreateListR(L2, b,5);//尾插法 printLinkNode(L1);//输出单链表 printLinkNode(L2);//输出单链表 //按值查找，返回序号 printf("L2 's number 5 is in the %d position\n", LocateElem(L2, 5)); printf("L2 's number 3 is in the %d position\n", LocateElem(L2, 3)); //按序号查找元素值 int e1, e2; if(GetElem(L1,5,e1)) { printf("The value at the 5 position of the L1 is %d\n", e1); } if (GetElem(L1, 1, e2)) { printf("The value at the 1 position of the L1 is %d\n", e2); } //插入元素,插入到第i 个位置 ListInsert(L1,5,6); printLinkNode(L1);//输出单链表 ListInsert(L2, 1, 2); printLinkNode(L2);//输出单链表 //删除元素 int e = 0; if (ListDelete(L1,5,e)) { printf("删除成功，删除的值为%d\n",e); } else { printf("删除失败，节点不存在"); } printLinkNode(L1);//输出单链表 DestoryList(L1); DestoryList(L2); return 0; }

结语： 

  单链表的实现，不仅是一次理论与实践的完美结合，更是一个程序员逻辑思维与动手能力的双重考验。通过对单链表的深入理解与实现，我们不仅掌握了数据结构的精髓，更在编程的道路上迈出了坚实的一步。未来，无论是面对复杂的数据处理，还是高效算法的设计，单链表都将成为我们手中得心应手的工具，助力我们在编程的世界里自由翱翔。