http://www.carrefourstation.com

数据结构 第4讲 单链表

2019-11-14 分类：概况

 

  1. 安插三个递归算法，删除不带头结点的单链表L中的全部值为x的结点。

链表是线性表的链式存款和储蓄方式，逻辑上周边的数额在微型机内的仓库储存位置不鲜明相邻，那么怎么表示逻辑上的邻座关系啊？能够给每种成分附加一个指针域，指向下四个要素的囤积地点。如图所示：

宣称：数据结构与算法类别博文参照他事他说加以考查了《天勤高分笔记》、《王道复习辅导》、C语言汉语网。非商业用场，仅为上学笔记总括！

/* 单链表整表创建算法思路 1.声明一结点p和计数器变量i 2.初始化一空链表L 3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表 4.循环：     生成一新结点赋值给p     随机生成一数字赋值给p的数据域p->data     将p插入到头结点与前一新结点之间 */     #include <stdio.h> #include <stdlib.h> #define DATATYPE char typedef struct Node {     DATATYPE  data;     struct Node *next; }LINKLIST;   //尾插法创建循环单链表，执行输入：abcd1234回车，就创建8个数据节点 LINKLIST *RearCreateLinkList() {     LINKLIST *LinkList_Head,*LinkList_Point,*LinkList_Rear;     char InputChar;       LinkList_Head = (LINKLIST *)malloc(sizeof(LINKLIST));     LinkList_Rear = LinkList_Head;          puts("Please input the linklist' data: ");     InputChar = getchar();     while(InputChar != 'n')     {         LinkList_Point = (LINKLIST *)malloc(sizeof(LINKLIST));         LinkList_Point->data = InputChar;         LinkList_Rear->next = LinkList_Point;         LinkList_Rear = LinkList_Point;         InputChar = getchar();     }     LinkList_Rear->next = LinkList_Head;     return(LinkList_Rear); }   /*遍历循环链表，显示出每个节点data域*/  void LinkListPrint(LINKLIST *LinkList_Rear) {     LINKLIST *List_Point,*LinkList_Head;     LinkList_Head = LinkList_Rear->next;       if(LinkList_Head == LinkList_Rear)     {         printf("n链表为空！n");         return;     }       List_Point = LinkList_Head->next;     puts("遍历节点:");     while(List_Point != LinkList_Head)     {         printf("%c  ",List_Point->data);         List_Point=List_Point->next;     }     puts("");     /* 暂停，也可以使用system("pause"); */      getchar();  }     int main() {     LINKLIST *LinkList_Rear_1;      /*尾插法创建循环单链表*/      LinkList_Rear_1=RearCreateLinkList();     /*打印循环单链表*/      LinkListPrint(LinkList_Rear_1);          return 0;  } 

图片 1

第一章《绪论》

 Microsoft Visual C++ 6.0 下运转成功。

void delX(linkList &L, int x) { Node *p; if (L == NULL) return; if (L->data == x) { p = L; L = L->pNext; free; delX; } else delX(L->pNext, x);}

从图中能够见见，每一种结点蕴含四个域：数据域和指针域，指针域存储下三个结点的地点，由此指针指向的种类也是结点类型。

生机勃勃、基本概念及入门常识 

图片 2

  1. 在起头结点的单链表L中，删除全数值为x的结点，并释放其空间，假若值为x的结点不唯大器晚成。

结点结构体的定义：

图片 3图片 4

 

图片 5

////（一）数据结构的基本概念和术语////
1. 数据
数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
2. 数据元素
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
注意：不要混淆数据、数据元素、数据项之间的概念，也要注意和数据库中的相关术语进行区别：如数据记录、数据字段等概念。
3. 数据对象
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合 N= {0,±1, 士2, ...}。
4. 数据类型
数据类型是一个值的集合和定义在此集合上一组操作的总称。
1) 原子类型：其值不可再分的数据类型。
2) 结构类型：其值可以再分解为若千成分（分量）的数据类型。
3) 抽象数据类型：抽象数据组织和与之相关的操作。
5. 抽象数据类型

抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。通常用（数据对象、 数据关系、基本操作集）这样的三元组来表示抽象数据类型。
6. 数据结构
在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（structure)。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所釆用的存储结构。

////（二）数据结构三要素：数据逻辑结构、数据存储结构和数据的运算////
1. 数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。数据的逻辑结构分类
    集合结构中的数据元素之间除了 “同属于一个集合”的关系外，别无其他关系。
    线性结构结构中的数据元素之间只存在一对一的关系。
    树形结构结构中的数据元素之间存在一对多的关系。
    图状结构或网状结构结构中的数据元素之间存在多对多的关系。

2. 数据的存储结构
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
1) 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2) 链接存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象，充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。
3) 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其优点是检索速度快；缺点是增加了附加的索引表，会占用较多的存储空间。另外，在增加和删除数据时要修改索引表，因而会花费较多的时间。
4) 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。其优点是检索、增加和删除结点的操作都很快；缺点是如果散列函数不好可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
3. 数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。    

////（三）算法的基本概念及特性(有穷性、确定性、可行性、输入和输出)////    
算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性：
1) 有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2) 确定性
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出。
3) 可行性
一个算法是可行的，即算法中描述的操作都是吋以逋过已经实现的基本运算执行有限次来实现的。
4) 输入
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
5) 输出
一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

通常设计一个“好”的算法应考虑达到以下目标：
正确性：算法应当能够正确地解决求解问题。
可读性：算法应当具有良好的可读性，以助于人们理解。
健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。    
////算法效率度量：时间复杂度和空间复杂度////    
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记作T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中的基本运算（最深层循环内的语句）的频度与T(n)同数量级，所以通常釆用算法中基本运算的频度 f(n)来分析算法的时间复杂度。因此，算法的时间复杂度也记为：
T(n)=O(f(n))
上式中“O”的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n>=n0时，都满足0 <= T(n) <= C * f(n)。
注意：取f(n)中随n增长最快的项将其系数置为1作为时间复杂度的度量。例如，fi(n) = a * n3 + b * n2 + c * n，则其时间复杂度为O(n3)。
算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）。

例如：在数组A[0...n-1]中，查找给定值K的算法大致如下：
i=n-1;
while( i>=0 && (A[i]!=k) )
    i--;  // 语句(3)
return i;

此算法中的语句(3)（基本运算）的频度不仅与问题规模n有关，还与输入实例中A 的各元素取值及K的取值有关：
若A中没有与K相等的元素，则语句(3)的频度 f(n)=n。
若A的最后一个元素等于K，则语句(3)的频度f(n)是常数0。
最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好情况下，算法的时间复杂度。
一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
在分析一个程序的时间复杂性时，有以下两条规则：
a) 加法规则
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
b) 乘法规则
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n) )
常见的渐近时间复杂度有：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
空间复杂度
算法的空间复杂度S(n)，定义为该算法所耗费的存储空间，它是问题规模n的函数。渐近空间复杂度也常简称为空间复杂度，记作S(n)=O(g(n))。
一个上机程序除了需要存储空间来存放本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间，若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需辅助空间是常量，即O(1)。

 

void delX_1(linkList &L, int x) { Node *p = L->pNext, *pre = L, * q; while (p!=nullptr){ if (p->data == x) { q = p; p = p->pNext; pre->pNext = p; free; } else { pre = p; p = p->pNext; } }}void delX_2(linkList &L, int x) { Node *p = L->pNext, *r = L, *q; while (p != nullptr) { if (p->data != x) { r->pNext = p; r = p; p = p->pNext; } else { q = p; p = p->pNext; free; } } r->pNext = nullptr;}

概念了结点之后，大家就足以把多少个结点连接在联合具名，产生二个链表：

#侃大山（密集恐惧症者慎入卡塔尔0.0

正文出自 “_Liang_Happy_Life__Dream” 博客，转发请与小编联系！

  1. 设L为带头结点的单链表，编写算法完结从尾到头反向输出各个结点的值。

图片 6

 第二章《线性表》

单链表整表创造算法思路 1.声称后生可畏结点p和计数器变量i 2.开始化生机勃勃空链表L 3.让L的头结点的指针指向NULL，即成立三个为首结点的单链表...

是还是不是像四个铁链子，风姿罗曼蒂克环扣风流罗曼蒂克环的连在一起？

一、概述 
线性表：具备相像本性数据元素的有数系列
　　---相同特性：把同风度翩翩类东西归类，方便批量拍卖
　　---有限：表中元素个数为n，n有限大，n可认为0
　　---种类：表夷则素排成一列，展现了一定的逻辑天性（各种成分有且唯有叁个先行者和叁个后继卡塔尔国

void reverse_traverse(linkList L,int cnt) { Node *p = L->pNext; if  { reverse_traverse(p, cnt + 1); if  cout << p->data << " "; else cout << p->data << endl; }}//我带了格式化输出

图片 7

逻辑结构：唯有二个表头成分，独有一个表尾成分，表头元素未有前人，表尾成分未有后继，除表头表尾之后的别的因素独有一个先行者，也只有三个后继。
积存结构：①顺序存款和储蓄结构（顺序表卡塔尔国；②链式存款和储蓄结构（单链表、双链表、单循环链表、双循环链表卡塔尔

  1. 试编写在领头结点的单链表L中删去一个微细值结点的高效算法（如若最小值结点是唯意气风发的卡塔 尔（英语：State of Qatar）

不管这么些铁链子有多少长度，只要我们找到它的头，就足以拉起整个铁链子，因而我们给那么些链表设置三个头指针，那些链表中的各样结点都足以找到了。

①顺序存储结构：利用数组的三番五次存款和储蓄空间顺序寄存线性表的各因素，每一个结点富含所积累成分的音信。
②链式存储结构：不必要逻辑上相邻的八个成分物理上也紧邻；通过“链”创设起数据成分之间的逻辑关系。每一种结点不仅仅富含所积累成分的新闻，还包蕴成分之间的逻辑关系消息；比如能够通过后驱结点中的地址音讯找到后继结点的岗位。

图片 8

特征相比较：

void deleteMin(linkList &L) { Node *p = L->pNext, *pre = L,*minNode = p , *minNodePre = L; while (p != nullptr) { if ( p->data < minNode->data ) { minNode = p; minNodePre = pre; } pre = p; p = p->pNext; } minNodePre->pNext = minNode->pNext; free;}

有的时候为了操作方便，大家还有或许会给链表扩大三个不贮存数据的头结点：

　　1.在相继表中插入和删除成分恐怕会促成移动大批量成分的连锁操作（表尾地点除此而外卡塔 尔（阿拉伯语：قطر‎，而链表不会；
　　2.在单链表中找到任意三个结点的职位不想顺序表那么粗略，因为顺序表帮助随机存取（存取卡塔尔，而单链表不援助；
　　3.为了弥补上一天单链表的欠缺，开荒了双链表、循环单链表和巡回双链表等积累结构，那一个囤积结构得以在仅知道链表中自由多个结点地址的气象下的推测其余            全部结点的地点，但照样不支持随机存取。
　　4.不经常候还有也许会给链表定义二个外加的指针，最分布的表尾指针，它指向链表中最终二个结点。能够依赖它来拉长某个习感觉常操作的进行功能
　　5.线性表选取顺序存款和储蓄结构，必得占用一片接二连三的存款和储蓄单元，而利用链式存款和储蓄结构则无需这么。
　　6.从全部来看，日常顺序表存款和储蓄空间利用率低于链表；而从单个存款和储蓄单元来看，顺序表存款和储蓄空间利用率要高于链表。

  1. 试编写算法将领衔指针的单链表就地逆置，协理空间复杂度为O

图片 9

线性表的基本操作
三个数据结构的基本操作是指其最焦点、最核心的操作。别的较复杂的操作能够通过调用其基本操作来完毕。线性表的要紧操作如下：
　　①InitList(&L)：发轫化表。构造叁个空的线性表。
　　②Length(L)：求表长度。再次来到线性表L的长短，即L中数量成分的个数。
　　③LocateElem(L, e)：按值查找操作。在表L中追寻具备给定关键字值的因素。
　　④GetElem(L, i)：按位查找操作。获取表L中第i个任务的要素的值。
　　⑤ListInsert(&L, i, e)：插入操作。在表L中第i个岗位上插入钦定成分。
　　⑥ListDelete(&L, i, &e)：删除操作。删除表L中第i个岗位的要素。
　　⑦PrintList(L)：输出操作。按前后相继输出线性表L的富有成分值。
　　⑧Empty(L)：判空操作。若L为空表，则赶回true,不然再次来到false。
　　⑨DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占领的内部存款和储蓄器空间。

就像给铁链子加个钥匙扣：

 

void reverse_1(linkList &L) { Node *p = L->pNext, *next; L->pNext = nullptr; while  { next = p->pNext; p->pNext = L->pNext; L->pNext = p; p = next; }}void reverse_2(linkList &L) { Node *p = L->pNext, *next = p->pNext; Node *pre; p->pNext = nullptr; while  { pre = p; p = next; next = next->pNext; p->pNext = pre; } L->pNext = p;}

图片 10

二、线性表的操作 
（1）顺序表 

  1. 有三个起头结点的单链表L，设计四个算法使其成分依次增加有序。

咱俩能够看见刚才的链表每一个指针都是指向下叁个结点，都以朝向一个主旋律的，那样的链表称为单向链表，或单链表。

图片 11

在种种表中，想找第i个要素，就能够及时通过L.elem[i-1]找到，称为随机存取主意，而在单链表中，想找第i个成分？没那么轻松，必得从头开头，按顺序一个多少个来，向来数到第i个元素，称为种种存取方式。

1、顺序表的构造体定义

void sort_increase(linkList &L) { Node *p = L->pNext, *pre; Node *r = p->pNext; p->pNext = nullptr; p = r; while  { r = p->pNext; pre = L; while (pre->pNext != nullptr && pre->pNext->data < p->data) pre = pre->pNext; p->pNext = pre->pNext; pre->pNext = p; p = r; }}

上边以领头结点的单链表为例，讲授单链表的起头化、创立、取值、查找、插入、删除操作。

#define maxSize 50 //定义线性表的最大长度
typedef struct
{
int data[maxSize]; //顺序表的元素（这里我们假设是int类型，也可能为其他类型）
int length;        //顺序表的当前长度
}Sqlist;           //顺序表的类型定义
  1. 设在三个带表头结点的单链表中负有因素结点的数据值冬日，编写风流洒脱函数，删除表中全部介于给定的三个值时期的要素。
  1. 单链表开端化

2、顺序表的操作

单链表开头化是指塑造五个空表：

①初始化
viod InitList(Sqlist &L)
{
    L.length=0;
}
②按值查找元素
//要求：用e获取P位置上的元素
int GetElem(Sqlist L,int p,int &e)         //e本身要发生变化，所以用引用型&e（从没有元素到有元素）
{
    if(p<0||p>L.length-1)
        return 0;
    e=L.data[p];
    return 1;
}
③按序号位置查找元素
//要求：查找元素e的序号
int LocateElem(Sqlist L,int e) 
{
    int i;
    for(i=0;i<L.length;i++)
        if(e==L.data[i])
            return i;
    return -1;
}
④插入元素
//要求：插入元素e
int ListInsert(Sqlist &L,int p,int e)        //L本身要发生变化，所以用引用型&L
{
    int i;
    if(p<0||p>L.length||L.length==max.Size)  //位置错误或者已经达到最大允许值，插入失败
        return 0;
    for(i=L.length-1;i>=p;--i)
        L.data[i+1]==L.data[i];              //采用先移动最右边的元素；若先移动最左边，右边的元素会被覆盖
    L.data[p]=e;                             //将e赋值给p位置（成为p位置上的新元素）
    ++(L.length);                            //表内多了一个元素e，表长自增1
    return -1;
}
⑤删除元素
//要求：删除元素p，并把删除的元素赋值给e
int ListDelete(Sqlist &L,int p,int &e)        //L、e本身要发生变化，所以用引用型&L，&e
{
    int i;
    if(p<0||p>L.length-1)
        return 0;                             //将p位置上的元素赋值给e
    e=L.data[p];
    for(i=p;i<L.length-1;++i)
        L.data[i]==L.data[i+1];               //被删除元素右边的所有元素都往左边移动一个位置
    --(L.length);
    return 1;                                 //表内多了一个元素e，表长自减1
}

void del_between_AandB(linkList &L, int a, int b) { Node *p = L->pNext, *pre = L; while  { if (p->data >= a && p->data <= b) { Node *temp = p; p = p->pNext; pre->pNext = p; free; } else { pre = p; p = p->pNext; } }}

图片 12

（2）单链表 

  1. 给定三个单链表，搜索多少个链表的集体结点。

bool InitList_L(LinkList &L)//构造叁个空的单链表L

概念：在各类结点中除去满含数据域外，还隐含一个指针域，用以指向其后继结点；这两局地音讯整合数据成分的储存结构，称之为“结点”。n个结点通过指针域互相链接，组成二个链表。

{

图片 13

linkList search_first_common(linkList L1, linkList L2) { int len1 = length, len2 = length; int sub = abs(len1 - len2); linkList long_list, short_list; if (len1 > len2) long_list = L1->pNext, short_list = L2->pNext; else long_list = L2->pNext, short_list = L1->pNext; while  long_list = long_list->pNext; while (long_list) { if (long_list == short_list) return long_list; else long_list = long_list->pNext, short_list = short_list->pNext; } if (long_list == nullptr) return nullptr;}

L=new LNode; //生成新结点作为头结点，用头指针L指向头结点

图片 14
①起头结点：头指针head指向头结点，头结点的值域不含任何新闻，从头结点的后继结点开端积攒数据消息；头指针始终不对等NULL，当head->next等于NULL的时候，链表为空。
②不带头结点：头指针head直接针对开首结点；当head等于NULL的时候，链表为空
区分别指针和头结点：不论链表是不是起头结点，头指针都指向链表中第3个结点；而领衔结点的链表中头结点是率先个结点，只充当链表存在的注脚，通常不积攒新闻。

  1. 给定叁个带表头结点的单链表，按依次增加次序输出单链表中相继结点的多少成分，并释放结点所占的蕴藏空间。（不容许选取数组作为扶助空间卡塔 尔（阿拉伯语：قطر‎

if(!L)

图片 15
注：一时半刻暗中同意操作的链表都起头结点，现在有的时候间再回头计算不领头结点的有关操作。。。

return false; //生成结点退步

<1>单链表结点定义

void print_increase(linkList &L) { linkList pre, p; while (L->pNext) { pre = L; p = pre->pNext; while (p->pNext) { if (p->pNext->data < pre->pNext->data) pre = p; p = p->pNext; } cout << pre->pNext->data; linkList temp = pre->pNext; pre->pNext = temp->pNext; free; } free;}

L->next=NULL; //头结点的指针域置空

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
  1. 将叁个起头结点的单链表A分解为四个领头结点的单链表A和B，使得A中隐含原表中序号为奇数的因素，B中包涵原表中序号为偶数的元素，保持相对顺序不变。

return true;

<2>查找结点
①按序号查找结点
在单链表中从第三个结点出发，顺指针next域每个往下搜寻，直到找到第i个结点截至，不然再次回到最终三个结点指针域NULL。
LNode GetElem(LNode *C,int i)

}

LNode GetElem(LNode *C,int i)
{
    //本算法取出单链表C（带头结点,L为头结点）中第i个位置的结点指针
    int j=1;             //计数，初始为1
    LNode *p;            //定义指针p（指向结点）
    p= C;                //指针P指向头结点C（因为此时头结点也是终端结点）
    if(i==0)
        return L;        //若i等于0，则返回头结点
    if(i<1)
        return NULL;     //若 i 无效，则返回 NULL
    while( p && j<i )    //从第1个结点开始找，查找第i个结点
    {  
        p=p->next;
        j++;
    }
    return p;            //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
}

时间复杂度：按序号查找操作的时间复杂度为O(n)

void split_list_to_a_b(linkList L, linkList a, linkList b) { Node *p = L; int i = 0; Node *pa = a; Node *pb = b; while (p->pNext) { if (i % 2 == 1) { pa->pNext = p->pNext; pa = pa->pNext; p = p->pNext; print_node; } else { pb->pNext = p->pNext; pb = pb->pNext; p = p->pNext; print_node; } i++; } pa->pNext = nullptr; pb->pNext = nullptr;}
  1. 单链表的制造

②按值查找表结点
从单链表第叁个结点初叶，由前将来种种相比表中各结点数据域的值，若某结点数据域的值等于给定值e，则赶回该结点的指针。若一切单链表中绝非如此的结点，则赶回NULL。

  1. 在多个线性递增的静止单链表中，有数值相符的因素存在，设统计法去除数值相近的要素，使表中不再有双重的因素。

创设单链表分为前插法和尾插法三种，前插法成立的单链表和输入顺序适逢其时相反，由此称为逆序建表，尾插法成立的单链表和输入顺序生龙活虎致，由此称为正序建表。

LNode *LocateElem (LinkList L, ElemType e) {
    //本算法查找单链表 C（带头结点）中数据域值等于e的结点指针，否则返回NULL
    LNode *p;
    p=C;
    while( p!=NULL && p->data!=e)  //从第1个结点开始查找data域为e的结点
        p=p->next;
    return p;                      //找到后返回该结点指针，否则返回NULL
}

时间复杂度：按值查找操作的时间复杂度为O(n)。

前插法建表如图：

<3>插入结点
①后插操作（利用四驱结点卡塔尔：插入操作是将值为x的新结点插入到单链表的第i个地方上。先检查插入地方的合法性，然后找到待插入地方的前任结点，即第i-1个结点，再在其后插入新结点。

void uniquify_sortedList(linkList L) { linkList p = L->pNext, temp = p; while (p->pNext) { temp = p->pNext; if (temp->data == p->data) { p->pNext = temp->pNext; free; }else p = p->pNext; }}

之前状态

图片 16

哇标题大多，写到晕厥！！加上链表达成快400行代码了。。后一次再补！！

图片 17

p=GetElem(L, i-1) ;  //①查找插入位置的前驱结点
s->next=p->next;     //②令新结点*s的指针域指向*p的后继结点
p->next=s;           //③令结点*p的指针域指向新插入的结点*s

注意：语句②③的顺序不能颠倒，否则，当先执行p->next=s后，指向其原后继的指针就不存在了，再执行s->next = p->next时，相当于执行了 s->next=s,显然是错误的。
时间复杂度：本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。

输入数据元素1，创造新结点，把成分1归入新结点数据域：

②前插操作（利用后继结点卡塔尔国：设待插入结点为*s，将插入到*p的先头。大家依旧将*s插入到*p的后面，然后将p->data与s->data交换

图片 18

图片 19

s=new LNode; //生成新结点s

s->next = p->next;   //①令新结点*s的指针域指向*p的后继结点
p->next = s;         //②令结点*p的指针域指向新插入的结点*s
temp = p->data;      //③把*p的指针域赋值给temp                  
p->data=s->data;     //④把*s的指针域赋值给*p      （③④⑤为交换数据域部分）
s->data=temp;        //⑤把temp的指针域赋值给*s

时间复杂度：O(1)

cin>>s->data; //输入成分值赋给新结点的数据域

<4>删除结点
①删减结点（利用四驱结点卡塔 尔（英语：State of Qatar）：先从链表的头结点先河挨门挨户找到其前任结点，然后再实施删除操作。

前插操作，插入到头结点的背后：

图片 20

图片 21

p=GetElem(L,i-1);  //①查找删除位置的前驱结点
q=p->next;         //②令q指向被删除结点
p->next=q->next    //③将*q结点从链中“断开”
free (q) ;         //④释放结点的存储空间

时间复杂度：该算法的主要时间也是耗费在查找操作上，时间复杂度为O(n)

输入数据成分2，成立新结点，把成分2放入新结点数据域：

②删减结点（利用后继结点卡塔尔：用删除*p的后继结点操作来促成，实质便是将其后继结点的值给与其自个儿，然后删除后继结点，也能使得时间复杂度为O(1)

图片 22

图片 23

前插操作，插入到头结点的末尾：

q=p->next;              //①令q指向*p的后继结点
p->data=p->next->data;  //②和后继结点交换数据域（删除操作只考虑被留下来的数据即可）
p->next=q->next;        //③将*q结点从链中“断开”
free (q) ;              //④释放后继结点的存储空间

时间复杂度：O(1)

图片 24

<5>创立链表

解释：

需求：n个成分已经累积在数组a中，营造链表C

图片 25

①尾插法

缘何要先修改前边那叁个指针呢？

viod creatlistR(LNode *&C,int a[],int n)  //要改变的变量用引用型//（R代表rear 尾巴）
{
    LNode *s,*r;                          //定义指针s（指向新申请的结点）；r（指向C的终端结点）
    C=(LNode*)malloc(sizeof(LNode));      //创建头结点（申请C的头结点空间）
    C->next=NULL;                         //初始化成空链表（链表取头结点作为新链表的头）
    r=C;                                  //指针r指向头结点C（因为此时头结点也是终端结点）
    int i;                                
    for(i=0;i<n;++i)                      //循环申请n个结点来接收数组a[]中的元素
    {
        s=(LNode*)malloc(sizeof(LNode));  //指针s指向新申请的结点
        s->data=a[i];                     //用新申请的结点来接收a数组中的一个元素
        r->next=s;                        //用r来接纳新结点
        r=r->next;                        //r始终指向终端结点，以便接收下一个新来的结点
    }
    r->next=NULL;                         //（r始终指向终端结点）r下一个设置为NULL，链表C建立完成
}

因为借使校勘了L结点的指针域指向s，那么原本L结点前面的结点就找不到了，

②头插法

在乎：改进指针顺序的规格：先更正未有指针标识的那生龙活虎边。

viod creatlistF(LNode *&C,int a[],int n)  //（F代表first 第一个，开头）
{
    LNode *s;                          
    C=(LNode*)malloc(sizeof(LNode));   
    C->next=NULL;
    int i;
    for(i=0;i<n;++i)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=a[i];
        s->next=C->next;                //s所指新结点的指针域next指向C中的开始结点
        C->next=s;                      //头结点的指针域next指向s结点，使得s成为新的开始结点（插入结点操作）
    } 
}

图片 26

<6>求表长
求表长操作便是计量单链表中数量结点（不含头结点卡塔 尔（英语：State of Qatar）的个数，要求从第多少个结点开头相继依次寻访表中的每多少个结点，为此须要安装一个流速計变量，每访谈一个结点，流速計加1，直到访问到空结点甘休。算法的时刻复杂度为O(n)。
注：因为单链表的长度是不包罗头结点的，因而，不领头结点和起头结点的单链表在求表长操作上会略有不一致。对不起头结点的单链表，当表为空时，要独立管理。

假诺要插入结点的两端都有号子，例如再定义三个指南针q本着第四个结点，那么先改善哪个指针都无所谓了。

（3）双链表 
概念：单链表中独有贰个指南针，指向直接后继，整个链表只好单方向从表头访谈到表尾。尽管算法中需求频繁地找某结点的先驱者结点，单链表的消除方法是遍历整个链表，扩张算法的时日复杂度，影响总体功用。
双链表：在单向链表的根基上，给各种结点额外布置一个指针变量，用于指向各样结点的第一手四驱元素。

拉直链表之后：

优点：双链表可以很有利地找到其前任结点，因而，插入、删除结点算法的时光复杂度仅为O(1)

图片 27

图片 28

持续依次输入数据成分3，4，5，6，7，8，9，10，前插法制造链表的结果：

图片 29

图片 30

<1>双链表结点定义

void CreateList_H(LinkList &L)//前插法创造单链表

typedef struct DLNode      //定义双链表结点类型
{
    int data;              //数据域
    struct DLNode *prior;  //指向直接前驱
    struct DLNode *next;   //指向直接后继
}DLNode;

{

<2>插入结点
需求：1,2结点之间插入4结点（双链表中p所指的结点之后插入结点*q）

int n; //输入n个成分的值，组建到头结点的单链表L

图片 31

LinkList s; //定义二个指南针变量

p->next->prior=q;   // ①把4变成2的前驱结点（新结点*q的指针域指向*p的后继结点）
q->next=p->next;    // ②把2变成4的后继结点（结点*p的指针域指向新插入的结点*s）
q->prior=p;         // ③把1变成4的前驱结点
p->next=q;          // ④把4变成1的后继结点

注：代码的语句顺序不是唯一的，但也不是任意的，①②两步必须在④步之前，否则*p 的后继结点的指针就丢掉了，导致插入失败。

L=new LNode;

<3>删除结点
双链表删除结点时，直接遍历链表，找到要刨除的结点，然后接受该结点的五个指针域达成删除操作。
需求：删除2结点（删除双链表中结点*p的后继结点*q）

L->next=NULL; //先建构二个起头结点的空链表

图片 32

cout <<"请输入元素个数n：" <

p->next=q->next;   //①把3变成1的后继结点
q->next->prior=p;  //②把1变成3的前驱结点
free (q) ;         //③释放结点空间

cin>>n;

树立双链表的操作中，也得以接收就好像单链表的头插法和尾插法，可是在操作上急需介怀指针的变化和单链表有所分裂。

cout <<"请依次输入n个成分：" <

（4卡塔尔国循环单链表 

cout <<"前插法创立单链表..." <

图片 33
在循环单链表中，表尾结点的next域指向L，故表中未有指针域为NULL的结点，由此，循环单链表的判空条件不是头结点的指针是还是不是为空，而是它是还是不是等于头指针。

while(n--)

循环单链表的插入、删除算法与单链表的大致毫发不爽，所例外的是豆蔻梢头旦操作是在表尾实行，则试行的操作不均等，以让单链表继续维持循环的性质。当然，就是因为循环单链表是贰个“环”，因而，在其他一个地方上的插入和删除操作都以等价的，无须判别是或不是是表尾。

{

在单链表中只可以从表头结点开头现在逐叁遍历整个链表，而循环单链表能够从表中的任风流洒脱结点最早遍历整个链表。有的时候对单链表常做的操作是在表头和表尾举办的，那时可对循环单链表不设头指针而仅设尾指针，进而使得操作效用越来越高。原因：若设置头指针，则对表尾实行操作须要时刻复杂度O(n)；若设置尾指针r，则头指针为r->next，即对表头表尾操作的日子复杂度都为O(1)

s=new LNode; //生成新结点s

（5卡塔 尔（英语：State of Qatar）循环双链表 

cin>>s->data; //输入成分值赋给新结点的数据域

图片 34

s->next=L->next;

 

L->next=s; //将新结点s插入到头结点之后

在循环双链表中，头结点的prior 指针还要针对表尾结点。
在循环双链表L中，某结点*p为尾结点时，p->next=L;当循环双链表为空表时，其头结点的prior域和next域都等于L。

}

（6卡塔尔静态链表 

}

图片 35

尾插法建表如图：

静态链表是信任数组来陈述线性表的链式存款和储蓄结构，结点也许有多少域data和指针域 next，与日前所讲的链表中的指针差异的是，这里的指针是结点的周旋地址（数组下标卡塔 尔（英语：State of Qatar），又叫做游标。和顺序表同样，静态链表也要先行分配一块一而再接二连三的内存空间。
静态链表和动态链表的差别：静态链表约束了数额成分贮存的职责范围；动态链表是成套内部存款和储蓄器空间。数据成分只同意在此块内部存款和储蓄器空间中大肆存放。

发端状态(尾插法供给二个尾指针永久指向链表的尾结点)

 静态链表布局体定义：

图片 36

#define MaxSize 50   //静态链表的最大长度
typedef struct{      //静态链表结构类型的定义
    ElemType data;   //存储数据元素
    int next;        //下一个元素的数组下标
}SLinkList[MaxSize];

输入数据成分1，创造新结点，把成分1归入新结点数据域：

静态链表以next==-1作为其得了的标识。静态链表的插入、删除操作与动态链表肖似，只要求改过指针，而无需活动元素。总体来讲，静态链表未有单链表使用起来方便，可是在部分不支持指针的高级语言（如Basic卡塔 尔（阿拉伯语：قطر‎中，这又是风华正茂种非常神奇的宏图方法。

图片 37

 

s=new LNode; //生成新结点s

 

cin>>s->data; //输入成分值赋给新结点的数据域

 下风度翩翩篇预报：其三章《栈与队列》

尾插操作，插入到尾结点的末端：

图片 38

解释：

图片 39

输入数据成分2，创制新结点，把成分2放入新结点数据域：

图片 40

尾插操作，插入到尾结点的末尾：

图片 41

再三再四依次输入数据成分3，4，5，6，7，8，9，10，前插法成立链表的结果：

图片 42

void CreateList_Enclave(LinkList &L)//尾插法创立单链表

{

//输入n个成分的值，创建带表头结点的单链表L

int n;

LinkList s, r;

L=new LNode;

L->next=NULL; //先创建三个带头结点的空链表

r=L; //尾指针r指向头结点

cout <<"请输入成分个数n：" <

cin>>n;

cout <<"请依次输入n个成分：" <

cout <<"尾插法创制单链表..." <

while(n--)

{

s=new LNode;//生成新结点

cin>>s->data; //输入成分值赋给新结点的数据域

s->next=NULL;

郑重声明：本文版权归澳门新莆京手机网站所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。

标签：