第十一讲 链表

(完整版)《链表》知识点总结
链表是计算机科学中常用的数据结构之一，用于存储和操作数据序列。

它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

下面是链表的一些重要知识点总结。

1. 链表的基本概念
- 链表是一种动态数据结构，与数组不同，链表的元素不必在内存中连续存储。

- 链表由节点组成，每个节点包含数据和指向下一个节点的指针。

2. 链表的分类
- 单向链表：每个节点只包含指向下一个节点的指针。

- 双向链表：每个节点既包含指向下一个节点的指针，也包含指向前一个节点的指针。

- 循环链表：最后一个节点指向第一个节点，形成一个循环。

3. 链表的操作
- 插入操作：在链表中插入一个新的节点，可以在链表的开头、中间或末尾插入。

- 删除操作：从链表中删除一个节点，可以删除链表的第一个
节点、最后一个节点或指定位置的节点。

- 查找操作：在链表中查找指定的数据，可以顺序遍历整个链
表进行查找。

4. 链表的优势和劣势
- 优势：链表的插入和删除操作比较高效，不需要像数组一样
重复移动元素。

- 劣势：链表的随机访问效率较低，需要从头开始遍历链表才
能找到指定位置的节点。

5. 链表的应用场景
- 链表常被用于实现其他数据结构，如栈、队列和哈希表。

- 链表还可以用于解决一些特定的问题，如链表反转、链表中
环的检测等。

以上是关于链表的一些重要知识点总结。

通过对链表的了解，
我们可以更好地理解和应用这一常用的数据结构。

(完整版)《链表》知识点总结链表的定义链表是一种常见的线性数据结构，由一系列节点组成。

每个节点包含一个数据元素和一个指向下一个节点的指针。

链表的头节点指向第一个节点，尾节点指向最后一个节点，且最后一个节点的指针为空。

链表的分类单向链表单向链表是最简单的链表形式。

每个节点只有一个指针，指向下一个节点。

双向链表双向链表在单向链表的基础上，每个节点新增一个指针，指向前一个节点。

循环链表循环链表是一种特殊的链表，其尾节点的指针指向头节点，形成一个循环。

链表的操作链表的创建class Node:def __init__(self, data=None):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None链表的插入- 在链表头部插入节点：def insert_head(self, data):new_node = Node(data)new_node.next = self.head self.head = new_node- 在链表尾部插入节点：def insert_tail(self, data):new_node = Node(data)if self.head is None:self.head = new_nodeelse:current_node = self.headwhile current_node.next: current_node = current_node.next current_node.next = new_node链表的删除- 删除链表头部节点：def delete_head(self):if self.head:temp = self.headself.head = temp.nexttemp.next = None- 删除链表尾部节点：def delete_tail(self):if self.head:if self.head.next is None:self.head = Noneelse:current_node = self.headwhile current_node.next.next: current_node = current_node.next current_node.next = None链表的查找- 根据值查找节点：def find_node(self, data):current_node = self.headwhile current_node:if current_node.data == data:return current_nodecurrent_node = current_node.next return None- 根据索引查找节点：def find_node_by_index(self, index): current_node = self.headcount = 0while current_node:if count == index:return current_nodecount += 1current_node = current_node.next return None链表的优缺点优点- 动态性：链表可以根据需求动态增加或删除节点。

第十一讲 动态存储一、静态存储与动态存储数据的存储方式分为两类：静态存储(Static storage)和动态存储(Dynamic storage)。

静态存储方式是指在程序运行期间分配固定的存储空间的方式。

简单点说，就是在程序开始的时候存储空间就已经分配，在程序的执行过程中，该存储地址不会改变。

前面我们介绍了很多的数据类型，例如整型、实型、布尔型等标准类型，以及数组、记录、集合等等，都是属于静态储存的。

然而，静态存储是有一定局限性的，下面我们从一个例子来了解一下。

例1.6.1.1.1:读入n个整数，倒序输出。

program p1_6_1_1_1(input,output);type arr=array [1..100000] of longint;var n,i:longint;a:arr;begini:=0;while not(eoln()) dobegininc(i);read(a[i]);end;readln();n:=i;for i:=n downto 1 dowrite(a[i],' ');writeln();readln();end.运用数组，这个程序很容易实现。

不过当我们看一下这一个简单的程序，我们可以发现一个小问题：n的不确定性会导致这个程序或是浪费了部分存储空间或是存储空间不足导致下标溢出。

这就是静态存储的缺陷。

要解决这个问题，我们必须暂时抛弃固有的静态存储的思想，引入动态存储的思想。

动态存储方式就是指在程序运行期间根据需要进行动态的分配存储空间的方式。

简单点说，现在我需要一个存储空间，我就申请它，当我不需要了，我就释放它，这样就能做到要多少就正好多少，既不多，也不少。

这就是动态存储方式。

二、指针1）简介类似于每一户人家都有一个门牌号码，计算机内存中的存储单元也都有一个整数编号，称为该存储单元的地址。

存储单元里存放的数据（类似于每一户人家住的人）可以根据该存储单元的地址读入或读出。

数据结构之线性表（链表）链表1.链表的定义：线性表的链式存储结构的特点是⽤⼀组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

因此，为了表⽰每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本⾝的信息之外，还需存储⼀个指⽰其直接后继的信息（即直接后继的存储位置）。

这两部分信息组成数据元素ai的存储映像，称为结点。

它包括两个域，其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。

指针域中存储的信息称做指针或链。

n个结点（ai(1<=i<=n）的存储映像）链结成⼀个链表，即为线性表的链式存储结构。

⼜由于此链表的每个结点中只包含⼀个指针域，故⼜称线性链表或单链表。

2.链表的数据结构#define ElemType inttypedef struct ListNode{ElemType data;ListNode *next;}ListNode;typedef struct List{ListNode *first;ListNode *last;size_t size;}List;3.在链表中有以下操作：void InitList(List *list);bool push_back(List *list, ElemType x);bool push_front(List *list, ElemType x);void show(List *list);void pop_back(List *list);bool insert_val(List *list, ElemType x);bool delete_val(List *list, ElemType key);ListNode *find_key(List *list, ElemType key);void clear_list(List *list);void reverse_list(List *list);void sort_list(List *list);void destroy_list(List *list);以上声明的⽅法有：（1）初始化⼀个链表.（2）尾插法向链表中添加元素.（3）头插法向链表中添加元素.（4）展⽰链表内容.（5）尾部删除链表中的数据元素.（6）按值向链表中插⼊数据元素.（7）按值删除链表中的数据元素.（8）按值查找链表中的数据数据元素.（9）清空链表操作.（10）逆序排列链表中的数据元素.（11）对链表中的数据元素进⾏排序.（12）销毁链表.4.将上⾯所声明的⽅法在LinkList.h的头⽂件中进⾏实现：#ifndef _LINKLIST_H#define _LINKLIST_H#include <iostream>#include <assert.h>using namespace std;#define ElemType inttypedef struct ListNode{ElemType data;ListNode *next;}ListNode;typedef struct List{ListNode *first;ListNode *last;size_t size;}List;bool push_back(List *list, ElemType x);bool push_front(List *list, ElemType x);void show(List *list);void pop_back(List *list);bool insert_val(List *list, ElemType x);bool delete_val(List *list, ElemType key);ListNode *find_key(List *list, ElemType key);void clear_list(List *list);void reverse_list(List *list);void sort_list(List *list);void destroy_list(List *list);void InitList(List *list){list->first = list->last = (ListNode*)malloc(sizeof(ListNode)); list->last->next = NULL;assert(list->first != NULL);list->size = 0;}bool push_back(List *list, ElemType x){ListNode *s = (ListNode*)malloc(sizeof(ListNode));if (s == NULL)return false;s->data = x;s->next = NULL;list->last->next = s;list->last = s;list->size++;return true;}bool push_front(List *list, ElemType x){ListNode *s = (ListNode*)malloc(sizeof(ListNode));if (s == NULL)return false;s->data = x;s->next = list->first->next;list->first->next = s;if (list->size == 0)list->last = s;list->size++;return true;}void show(List *list){ListNode *p = list->first->next;while (p != NULL){cout << p->data << "->";p = p->next;}cout << "Over." << endl;}void pop_back(List *list){if (list->size == 0)return;ListNode *p = list->first;while (p->next != list->last)p = p->next;p->next = NULL;free(list->last);list->last = p;list->size--;}bool insert_val(List *list, ElemType x){ListNode *p = list->first;while (p->next != NULL && p->next->data < x)p = p->next;ListNode *s = (ListNode*)malloc(sizeof(ListNode));if (s == NULL)return false;s->data = x;s->next = NULL;s->next = p->next;p->next = s;list->size++;return true;}bool delete_val(List *list, ElemType key){if (list->size == 0)return false;ListNode *p = list->first;while (p->next != NULL && p->next->data != key)p = p->next;if (p->next == NULL)return false;ListNode *q = p->next;p->next = q->next;if (q == list->last)list->last = p;free(q);list->size--;return true;}ListNode *find_key(List *list, ElemType key){if (list->size == 0)return false;ListNode *p = list->first->next;while (p != NULL &&p->data != key)p = p->next;return p;}void clear_list(List *list){if (list->size == 0)return;ListNode *p = list->first->next;while (p != NULL){list->first->next = p->next;free(p);p = list->first->next;}list->last = list->first;list->size = 0;}void reverse_list(List *list){if (list->size <= 1)return;ListNode *p = list->first->next;ListNode *q = p->next;list->last = p;list->last->next = NULL;while (q != NULL){p = q;q = p->next;p->next = list->first->next;list->first->next = p;}}void sort_list(List *list){if (list->size <= 1)return;ListNode *p = list->first->next;ListNode *q = p->next;list->last = p;list->last->next = NULL;ListNode *t;while (q != NULL){p = q;q = q->next;t = list->first;while (t->next != NULL && p->data > t->next->data) t = t->next;if (t->next = NULL)list->last = p;}}void destroy_list(List *list){clear_list(list);free(list->first);list->first = list->last = NULL;}#endif5.将上⾯所实现的⽅法在主函数中调⽤实现：#include <iostream>#include "LinkList.h"using namespace std;int main(){List mylist;InitList(&mylist);ListNode *p = NULL;ElemType item;int pos;int select = 1;while (select){cout << "******************************************" << endl; cout << "*[1] push_back [2] push_front *" << endl; cout << "*[3] Show [4] pop_back *" << endl; cout << "*[5] insert_val [6] delete_val *" << endl; cout << "*[7] find_key [8] reverse_list *" << endl; cout << "*[9] sort_list [10] clear_list *" << endl;cout << "*[0] quit_system *" << endl;cout << "******************************************" << endl; cout << "请选择:>";cin >> select;switch (select){case1:cout << "请输⼊要插⼊的数据(-1结束):>";while (cin >> item, item != -1) //逗号表达式{push_back(&mylist, item);}break;case2:cout << "请输⼊要插⼊的数据(-1结束):>";while (cin >> item, item != -1){push_front(&mylist, item);}break;case3:show(&mylist);break;case4:pop_back(&mylist);break;case5:cout << "请输⼊要插⼊的值:>";cin >> item;insert_val(&mylist, item);break;case6:cout << "请输⼊要删除的值:>";cin >> item;delete_val(&mylist, item);break;case7:cout << "请输⼊要查找的值:>";cin >> item;p = find_key(&mylist, item);if (p == NULL){cout << "要查找的值:" << item << "不存在!" << endl; }break;case8:case9:sort_list(&mylist);break;case10:clear_list(&mylist);break;}system("pause");system("cls");}destroy_list(&mylist); return0;}。

链表一种数据结构的链接实现是指按链式存储方式构建其存储结构，并在此链式存储结构上实现其基本运算。

线性表的常见链式存储结构有单链表、循环链表和双链表，其中最简单的单链表。

本节讨论单链表的组织方法以及线性表的基本运算在单链表上的实现。

单链表示法的基本思想是用指针表示结点间的逻辑关系。

因此单链表的一个存储结点包含两个部分，结点形式如下：其中，data部分称为数据域，用于存储线性表的一个数据元素。

next部分称为指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继所在的结点。

从上述单链表中可以联想到我们生活中的火车，还有一种火车只有火车头。

假设数据元素的类型为Datatype。

单链表的类型定义如下：typedef struct node{Datatype data;struct node * next;} node，* LinkList;struct node表示链表的结点，一个结点是由两个域数据域data和指针域next组成的记录（每个域实际上相当于一个变量），而next本身又是一个pointer类型的指针型变量。

这个定义与上面给出的单链表的结点形式一致。

单链表的简单操作：1、初始化建立一个空表。

空表由一个头指针和一个头结点（该结点同时也是尾结点）组成。

LinkList Initiate_LinkList()/* 建立一空表 */{ LinkLis head;head= malloc(sizeof(node));head -> next = NULL;return head;}2、定位：按值查找。

按从前往后的顺序，依次比较单链表中各表结点数据域的值与给定值X，第一个值与X相等的表结点的序号就是结果。

若没有这样的结点，运算结果为0。

int Locate_LinkList(LinkList head,Datatype x){ Node *p;p = head; /* 置初值 */p=p->next;j = 0; /* 置初值 */while((p!= NULL)&&(p -> data != x)){ p = p -> next;j ++;} /* 未达尾结点又未找到等于x的结点时继续扫描 */if (p -> data == x)return(j+1);elsereturn(0);}3、插入:把新的结点x插入到i结点之前。

链表的概念什么是链表链表（Linked List）是一种常用的数据结构，用于存储一系列具有顺序关系的元素。

与数组相比，链表具有动态性和灵活性。

链表通过节点（Node）将元素连接在一起，每个节点包含了数据和指向下一个节点的指针。

单向链表单向链表（Singly Linked List）是最简单的链表结构。

每个节点包含数据和指向下一个节点的指针。

链表的第一个节点被称为头节点，最后一个节点被称为尾节点，尾节点的指针指向空值。

单向链表的基本操作1.创建链表：初始化头节点，并将其指针指向空值。

2.插入节点：在链表的任意位置插入新的节点，需要修改前一个节点的指针，使其指向新的节点，新节点的指针指向原来的后一个节点。

3.删除节点：将前一个节点的指针指向要删除节点的后一个节点，释放待删除节点的内存空间。

4.遍历链表：从头节点开始，依次访问每个节点的数据。

单向链表的优缺点优点：•动态性：链表可以根据需要动态分配内存空间，而数组的大小是固定的。

•灵活性：链表允许在运行时插入和删除节点，而数组需要移动其他元素。

缺点：•非随机访问：链表中的元素无法直接访问，需要从头节点开始按顺序遍历。

•消耗额外空间：链表每个节点需要额外的指针来指向下一个节点。

双向链表双向链表（Doubly Linked List）在单向链表的基础上增加了一个指向前一个节点的指针。

双向链表可以从前向后或从后向前遍历。

双向链表的基本操作1.创建链表：初始化头节点和尾节点，并将其指针指向空值。

2.插入节点：在链表的任意位置插入新的节点，需要修改前一个节点的指针，使其指向新的节点，新节点的指针指向原来的后一个节点，同时修改后一个节点的前向指针。

3.删除节点：将前一个节点的指针指向要删除节点的后一个节点，修改后一个节点的前向指针，释放待删除节点的内存空间。

4.遍历链表：可以从头节点开始正向遍历，也可以从尾节点开始逆向遍历。

双向链表的优缺点优点：•双向遍历：双向链表可以从前向后或从后向前遍历，避免了单向链表非随机访问的缺点。

数据结构—链表链表⽬录⼀、概述1.链表是什么链表数⼀种线性数据结构。

它是动态地进⾏储存分配的⼀种结构。

什么是线性结构，什么是⾮线性结构？线性结构是⼀个有序数据元素的集合。

常⽤的线性结构有：线性表，栈，队列，双队列，数组，串。

⾮线性结构，是⼀个结点元素可能有多个直接前趋和多个直接后继。

常见的⾮线性结构有：⼆维数组，多维数组，⼴义表，树(⼆叉树等)。

2.链表的基本结构链表由⼀系列节点组成的集合，节点（Node）由数据域（date）和指针域（next）组成。

date负责储存数据，next储存其直接后续的地址3.链表的分类单链表（特点：连接⽅向都是单向的，对链表的访问要通过顺序读取从头部开始）双链表循环链表单向循环链表双向循环链表4.链表和数组的⽐较数组：优点：查询快（地址是连续的）缺点：1.增删慢，消耗CPU内存链表就是⼀种可以⽤多少空间就申请多少空间，并且提⾼增删速度的线性数据结构，但是它地址不是连续的查询慢。

⼆、单链表[1. 认识单链表](#1. 认识单链表)1. 认识单链表（1）头结点：第0 个节点（虚拟出来的）称为头结点（head），它没有数据，存放着第⼀个节点的⾸地址（2）⾸节点：第⼀个节点称为⾸节点，它存放着第⼀个有效的数据（3）中间节点：⾸节点和接下来的每⼀个节点都是同⼀种结构类型：由数据域（date）和指针域（next）组成数据域（date）存放着实际的数据，如学号（id）、姓名（name）、性别（sex）、年龄（age）、成绩（score）等指针域（next）存放着下⼀个节点的⾸地址（4）尾节点：最后⼀个节点称为尾节点，它存放着最后⼀个有效的数据（5）头指针：指向头结点的指针（6）尾指针：指向尾节点的指针（7）单链表节点的定义public static class Node {//Object类对象可以接收⼀切数据类型解决了数据统⼀问题public Object date; //每个节点的数据Node next; //每个节点指向下⼀结点的连接public Node(Object date) {this.date = date;}}2.引⼈头结点的作⽤1. 概念头结点：虚拟出来的⼀个节点，不保存数据。

链表建立的原理
链表是一种常见的数据结构，它是由一系列通过指针链接起来的节点
组成的，这些节点可以分布在内存中的任意位置。

链表建立的原理很
简单，它通过指针将节点链接起来，按照顺序形成一个链表。

链表的
建立经历了以下几个步骤。

（一）定义链表节点结构体
链表的节点是一个结构体，它包含两个部分：数据域和指针域。

数据
域用来存储节点的数据，指针域用来指向下一个节点。

（二）创建头节点
头节点是链表中的第一个节点，它主要用于管理链表。

创建头节点时，需要将它的指针域指向链表的第一个节点。

（三）创建新节点
创建新节点时，先定义一个指向节点的指针，然后通过动态内存分配
函数申请一块内存，将指针指向该内存地址。

（四）连接新节点
将新节点的指针域指向下一个节点，这样就将新节点添加到链表中。

此时需要注意的是，如果链表为空，新节点将成为链表的第一个节点。

（五）删除节点
删除节点时，只需要将要删除节点的前一个节点的指针指向要删除节
点的下一个节点即可，被删除的节点将被释放。

链表建立的原理就是通过指针将节点链接起来，形成一个链表。

链表
的优点是可以动态地添加或删除节点，同时占用的内存空间也比较灵活。

但链表的缺点也很明显，由于需要遍历整个链表，访问节点的时
间复杂度为O(n)，因此在数据访问频繁的情况下，链表的效率不如数组。