线性表-链式存储结构

妖狐艹你老母 2022-09-28 13:27 168阅读 0赞

# 3.6 线性表的链式存储结构 #

## 3.6.1 顺序存储结构不足的解决办法 ##

前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

要解决这个问题，我们就得考虑一下导致这个问题的原因。

为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2, 3,…,n。它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后， 当中就会留出空隙，自然需要弥补。问题就出在这里。

A同学思路:让当中每个元素之间都留有一个空位置，这样要插入时，就不至于移动。可一个空位置如何解决多个相同位置插入数据的问题呢?所以这个想法显然不行。

B 同学思路 : 那就让当中每个元素之间都留足够多的位置，根据实际情况制定空隙大小，比如10个，这样插入时，就不需要移动了。万一10个空位用完了，再考虑移动使得每个位置之间都有 10 个空位置。如果删除，就直接删掉，把位置留空即可。这样似乎暂时解决了插入和删除的移动数据问题。可这对于超过10个同位置数据的插入，效率上还是存在问题.对于数据的遍历，也会因为空位置大多而造成判断时间上的浪费。而且显然这里空间复杂度还增加了，因为每个元素之间都有若干个空位置。

C同学思路 : 我们反正也是要让相邻元素间留有足够余地，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道包下一个元素的位置在哪里，这样，我们可以在第一个元素时，就知道第二个元素的位置(内存地址) ,而找到它; 在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。

好!太棒了，这个想法非常好 ! C 同学，你可惜生晚了几十年，不然，你的想法对于数据结构来讲就是划时代的意义。我们要的就是这个思路。

## 3.6.2 线性表链式存储结构定义 ##

在解释这个思路之前，我们先来谈另一个话题。前几年，有一本书风靡了全世界，它叫《达·芬奇密码》，成为世界上最畅销的小说之一，书的内容集合了侦探、惊悚和阴谋论等多种风格，很好看。

我由于看的时间太过于久远，情节都忘记得差不多了，不过这本书和绝大部分侦探小说一样，都是同一种处理办法。那就是，作者不会让你事先知道整个过程的全部，而是在一步一步地到这某个环节， 才根据现场的信息，获得或推断出下一步是什么，也就是说，每一步除了对侦破的信息进一步确认外(之前信息也不一定都是对的，有时就是证明某个信息不正确) ，还有就是对下一步如何操作或行动的指引。

不过，这个例子也不完全与线性表相符合。因为案件侦破的线索可能是错综复杂的，有点像我们之后要讲到的树和图的数据结构。今天我们要谈的是单线索，无分支的情况。即线性表的链式存储结构。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置(如图 3-6-1所示)。

![Center][]

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外 ，还要存储它的后继元素的存储地址。

因此，为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。 **我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。**

n个结点(ai的存储映像)链结成一个链表，即为线性表 (ai，a2,… , an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起，如图3-6-2所示。

![Center 1][]

对于线性表来说，总得有个头有个尾，链表也不例外。 **我们把链表中第一个结点的存储位置叫做头指针** ，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为"空"(通常用NULL或“^”符号表示，如图 3-6-3 所示)。

![Center 2][]

有时，我们为了更加方便地对链表进行操作， **会在单链表的第一个结点前附设一个结点，称为头结点。** 头结点的数据域可以不存储任何信息，谁叫它是第-个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如图 3-6-4所示。

![Center 3][]

## 3.6.3 头指针与头结点的异同 ##

头指针与头结点的异同点，如图 3-6-5 所示。

![Center 4][]

## 3.6.4线性表链式存储结构代码描述 ##

若线性表为空表，则头结点的指针域为"空"，如图 3-6-6 所示。

![Center 5][]

这里我们大概地用图示表达了内存中单链表的存储状态。看着满图的省略号"……" ，你就知道是多么不方便。而我们真正关心的:它是在内存中的实际位置吗?不是的，这只是它所表示的线性表中的数据元素及数据元素之间的逻辑关系。所以我们改用更方便的存储示意图来表示单链表，如图3-6-7 所示。

![Center 6][]

若带有头结点的单链表，则如图 3-6-8 所示。

![Center 7][]

空链表如图 3-6-9 所示。

![Center 8][]

单链表中，我们在 C 语言中可用结构指针来描述。

![Center 9][]

从这个结构定义中，我们也就知道， **结点由存放数据元素的数据域和存放后继结点地址的指针域组成** 。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点 ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next 指向谁呢? 当然是指向第i+l个元素，即指向a(i+1)的指针。也就是说，如果p->data=ai，那么p->next>data=ai+l (如图3-6-10 所示)。

![Center 10][]

# 3.7 单链表的读取 #

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪?没办法一开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作 GetElem ，在算法上，相对要麻烦一些。

获得链表第i个数据的算法思路:

1.声明一个结点 p 指向链表第一个结点，初始化j从 1 开始;

2.当j<i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加 1;

3.若到链表末尾p为空，则说明第i个元素不存在;

4.否则查找成功，返回结点p的数据 。

实现代码算法如下 :

/*初始条件:顺序线性表L已存在，1<=i<=ListLength(L)*/
    /*操作结果:用e返回L中第i个数据元素的值*/
    Status getElem(LinkList L, int i, ElemType *e)
    {
    	int j;
    	LinkList p;				/*声明结点p*/
    	p = L->next;				/*让P指向链表L的第一个结点*/
    	j = 1;					/*j为计数器*/
    	while(p && j < i)			/*p不为空或者计数器j还没有等于i时，循环继续*/
    	{
    		p = p -> next;			/*让p指向下一个节点*/
    		++j;
    	}
    	if( !p || j > i)
    		return ERROR;			/*第i个元素不存在*/
    	*e = p -> data;			/*取第i个元素的数据*/
    	return OK;
    }

说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，当i=l 时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是 O(n)。

由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是" **工作指针后移** "，这其实也是很多算法的常用技术。

此时就有人说，这么麻烦，这数据结构有什么意思!还不如顺序存储结构呢。

哈，世间万物总是两面的，有好自然有不足，有差自然就有优势。下面我们来看一下在单链表中的如何实现"插入"和"删除。

# 3.8 单链表的插入与删除 #

## 3.8.1 单链表的插入 ##

先来看单链表的插入。假设存储元素e的结点为S，要实现结点 p、p->next和s之间逻辑关系的变化，将结点s插入到结点p和p->next 之间即可。可如何插入呢(如图3-8-1所示)?

![Center 11][]

根本用不着惊动其他结点，只需要让 s->next 和 p->next 的指针做一点改变即可。

s->next=p->next; p->next=s;

解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点(如图 3- 8-2 所示)。

![Center 12][]

考虑一下，这两句的顺序可不可以交换?

如果先p->next=s;再s->next=p->next;会怎么样?哈哈，因为此时第一句会使得将p->next给覆盖成s 的地址了。那么s->next=p->next，其实就等于s->next=s ，这样真正的拥有ai+l数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的，这点初学者一定要注意。

插入结点s后，链表如图3-8-3 所示。

![Center 13][]

对于单链表的表头和表尾的特殊情况，操作是相同的，如图 3-8-4 所示。

![Center 14][]

单链表第i个数据插入结点的算法思路:

1. 声明一结点p指向链表第一个结点，初始化j从1开始;

2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点， j累加1;

3. 若到链表末尾p为空，则说明第i个元素不存在;

4. 否则查找成功，在系统中生成一个空结点s;

5. 将数据元素e赋值给 s->data ;

6. 单链表的插入标准语句 s->next=p->next; p->next=s;

7. 返回成功 。

实现代码算法如下:

![Center 15][]

在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与 Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放e数据s结点。

## 3.8.2单链表的删除 ##

现在我们再来看单链表的删除。设存储元素ai的结点为 q，要实现将结点q删除单链表的操作,其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图3-8-5所示。

![Center 16][]

我们所要做的，实际上就是一步，p->next=p->next->next，用q来取代 p->next，即是

q=p->next; p - >next=q- >next ;

解读这两句代码，也就是说让p的后继的后继结点改成p的后继结点。有点拗口呀，那我再打个形象的比方。本来是爸爸左手牵着妈妈的手，右手牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸一下子看呆了，此情景被妈妈逮个正着，于是她生气地甩开牵着的爸爸的手，绕过他，扯开父子俩，拉起宝宝的左手就快步朝前走去。此时妈妈是p结点，妈妈的后继是爸爸p->next，也可以叫q结点，妈妈的后继 的后继是儿子p->nex->next，即q->next。当妈妈去牵儿子的手时，这个爸爸就已经与母子俩没有牵手联系了，如图 3-8-6 所示。

![Center 17][]

单链表第i个数据删除结点的算法思路 :

1. 声明一结点 p 指向链表第一个结点，初始化j从1开始;

2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

3. 若到链表末尾p为空，则说明第i个元素不存在;

4. 否则查找成功，将欲删除的结点p-> next赋值给q;

5. 单链表的删除标准语句 p->next=q->next;

6. 将q结点中的数据赋值给e，作为返回;

7. 释放q结点;

8. 返回成功。

实现代码算法如下 ;

![Center 18][]

这段算法代码里 ，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成;第一部分就是遍历查找第i个元素；第二部分就是插入和删除元素。

从整个算法来说，我们很容易推导出:它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为 O(n) ，接下来只是简单地通过赋值移动指针而已，时间复杂度都是 0(1)。显然 ，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

# 3.9 单链表的整表创建 #

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态、生成链表的过程。即从"空表"的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路 :

1.声明一结点p和计数器变量i;

2.初始化一空链表 L;

3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表;

4.循环 :

• 生成一新结点赋值给 p;

• 随机生成一数字赋值给p的数据域 p->data;

• 将p插入到头结点与前一新结点之间。

实现代码算法如下:

/*随时产生n个元素的值，建立带表头结点的单链线性表L(头插法)*/
    void CreateListHead(LiolcList *L, int n)
    {	
    	LinkList p;
    	int i;
    	srand(time(0));/*初始化随机数种子*/ 
    	*L = (LinkList)malloc(sizeof(Node));
    	(*L) -> next = NULL;/*先建立一个带头结点的单链表*/
    	for(i = 0; i < n; i++)
    	{
    		p = (LinkList)malloc(sizeof(Node));/*生成新结点*/
    		p->data = rand()%100+1;/*随机生成100以内的数字*/
    		p->next = (*L) ->next;
    		(*L) ->next = p;/*插入到表头*/
    	}
    }

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法，如图 3-9-1 所示。

![Center 19][]

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

实现代码算法如下:

/*随时产生n个元素的值，建立带表头结点的单链线性表L(尾插法)*/
    void CreateListTail(LiolcList *L, int n)
    {	
    	LinkList p,r;
    	int i;
    	srand(time(0));/*初始化随机数种子*/ 
    	*L = (LinkList)malloc(sizeof(Node));/*为整个线性表*/
    	r = *L;/*r为指向表尾的结点*/
    	for(i = 0; i < n; i++)
    	{
    		p = (Node *)malloc(sizeof(Node));/*生成新结点*/
    		p->data = rand()%100+1;/*随机生成100以内的数字*/
    		r ->next = p;/*将表尾终端结点的指针指向新结点*/
    		r = p;/*将当前新结点定义为表尾终端结点*/
    	}
    	r ->next = NULL;
    }

注意L和r的关系，L是指整个单链表，而r是指向尾结点的变量。r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

这里需要解释一下，r->next = p;的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如图3-9-2 所示，当中①位置的连线就是表示这个意思。

![Center 20][]

r->next=p;这一句应该还好理解，我以前很多学生不理解的就是后面这一句 r=p;是什么意思?请看图 3-9-3 。

![Center 21][]

它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai ，所以应该将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。

循环结束后，那么应该让这个链表的指针域置空，因此有了"r->next=NULL",以便以后遍历时可以确认其是尾部。

# 3.10 单链表的整表删除 #

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下:

1. 声明一结点p和q;

2. 将第一个结点赋值给p;

3. 循环:

• 将下一结点赋值给q;

• 释放p;

• 将q赋值给p。

实现代码算法如下:

![Center 22][]

这段算法代码里，常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(p) ;p=p->next; 即可。可这样会带来什么问题?

要知道p是一个结点，它除了有数据域，还有指针域。你在做free(p);时，其实是在对它整个结点进行删除和内存释放的工作。这就好比皇帝快要病死了，却还没有册封大子，他儿子五六个，你说要是你脚一蹬倒是解脱了，这国家咋办，你那几个儿子咋办?这要是为了皇位，什么亲兄弟血肉情都成了浮云，一定会打起来。所以不行，皇帝不能马上死，得先把遗嘱写好，说清楚，哪个儿子做太子才行。而这个遗嘱

就是变量q的作用，它使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。明白了吗?

好了，说了这么多，我们可以来简单总结一下。

# 3.11 单链表结构与顺序存储结构优缺点 #

简单地对单链表结构和顺序存储结构做对比:

![Center 23][]

通过上面的对比，我们可以得出一些经验性的结论:

· 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构 。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不大合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。

· 当线性表中的元素个数变化较大或者根本不知道有多大肘，最好用单链表结构 ， 这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年 12 个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。总之，线性衰的顺序存储结构和单链表结构各有其优缺点 ， 不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。

# 3.12 静态链表 #

其实C语言真是好东西，它具有的指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其它高级语言更加灵活方便。后来的面向对象语言，如 Java、 C\#等，虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。但对于一些语言，如 Basic、 Fortran 等早期的编程高级语言，由于没有指针，链表结构按照前面我们的讲法，它就没法实现了。怎么办呢?

有人就想出来用数组来代替指针，来描述单链表。真是不得不佩服他们的智慧，我们来看着他是怎么做到的。

首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个 data和一个 cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据;而游标cur相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。

**我们把这种用数组描述的链表叫做静态链表** ，这种描述方法还有别名叫做 **游标实现法** 。

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

/*线性表的静态链表存储结构*/
    #define MAXSIEZE 1000 /*假设链表的最大长度是 1000*/
    typedef struct
    {
    	ElemType data;
    	int cur; /*游标(Cursor),为0时表示无指向*/
    }Component,StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为 0 的元素的cur就存放备用链表的第一个结点的下标;而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0。如图3-12-1 所示 。

![Center 24][]

此时的图示相当于初始化的数组状态，见下面代码 :

![Center 25][]

Java实现：

/*将一维数组space中各分量链成一个备用链表*/
    	/*space[0].cur为头指针，"0"表示空指针*/
    	static StaticLinkList[] initList(StaticLinkList[] space){
    		
    		for(int i = 0; i < MAXSIZE; i++){
    			space[i] = new StaticLinkList();
    			space[i].cur = i+1;
    		}
    		space[MAXSIZE-1].cur = 0;//目前静态链表为空.最后一个元素的cur为0
    		return space;
    	}
    /*静态链表*/
    static class StaticLinkList{
    	int cur;//游标
    	String data;//数据 
    	@Override
    	public String toString() {
    		return "StaticLinkList [cur=" + cur + ", data=" + data + "]";
    	}
    }

假设我们已经将数据存入静态链表，比如分别存放着"甲" 、 "乙"、 "丁"、"戊'、"己"、"庚"等数据，则它将处于如图 3-12-2 所示这种状态。

![Center 26][]

此时"甲"这里就存有下一元素"乙"的游标2，"乙"则存有下一元素"丁'的游标3。而"庚"是最后一个有值元素，所以它的cur设置为0。而最后一个元素(下标999)的cur则因"甲'是第一有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7 。

## 3.12.1 静态链表的插入操作 ##

现在我们来看看如何实现元素的插入。

静态链表中要解决的是:如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

我们前面说过，在动态链表中，结点的申请和释放分别借用 malloc()和 free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

![Center 27][]

Java实现：

/*若备用链表非空，则返回分配的结点下标，否则返回0*/
    	static int Malloc_SLL(StaticLinkList[] space){
    		int i = space[0].cur;/*当前数组第一个元素的cur存的值，就是要返回的第一个备用空闲的下标*/
    		if(space[0].cur != 0){
    			space[0].cur = space[i].cur;/*由于要拿出来一个分量使用，所以我们就得把它的下一个分量用来备用*/
    		}
    		return i;
    	}

这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。从上面的图示例子来看，其实就是返回7 。

那么既然下标为7的分量准备要使用了，就得有接替者，所以就把分量7的cur值赋值给头元素，也就是把8给space\[O\].cur，之后就可以继续分配新的空闲分量，实现类似malloc()函数的作用。

现在我们如果需要在"乙"和"丁"之间，插入一个值为"丙"的元素，按照以前顺序存储结构的做法，应该要把"丁"、"戊"、"己"、"庚"这些元素都往后移一位。但目前不需要，因为我们有了新的手段。

新元素"丙"，想插队是吧?可以，你先悄悄地在队伍最后一排第7个游标位置待着，我一会就能帮你搞定。我接着找到了"乙"，告诉他，你的 cur 不是游标为3的"丁"了，这点小钱，意思意思，你把你的下一位的游标改为7就可以了。"乙"叹了口气，收了钱把cur值改了 。此时再回到"丙"那里，说你把你的 cur 改为3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变(如图3-12-3所示)。

C实现代码如下，代码左侧数字为行号。

![Center 28][]

•当我们执行插入语句时，我们的目的是要在"乙"和"丁"之间插入"丙"。调用代码时，输入i值为3 。

• 第 4 行让 k=MAX\_SIZE - 1=999。

• 第 7 行，j=Malloc\_SSL(L)=7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。

• 第 ll -12行，for循环l由1到2，执行两次。代码k=L\[k\].cur;使得k=999，得到k=L\[999\].cur=1，再

得到 k=L\[1\].cur=2。

• 第 13 行， L\[j\].cur = L(k).cur;因j=7，而k=2得到L\[7\].cur=L\[2\].cur=3。这就是刚才我说的让

"丙"把它的cur改为3的意思。

• 第 14 行. L\[k\].cur = j;意思就是 L\[2\].cur=7。也就是让"乙"得点好处，把它的cur改为指向

"丙'的下标 7。

Java实现代码如下。

/*在L中第i个元素之前插入新的数据元素e*/
    	static int ListInsert(StaticLinkList[] L,int i, String e){
    		int j,k;
    		k = MAXSIZE-1;//注意k首先是最后一个元素的下标
    		if(i < 1 || i > L.length + 1)
    			return ERROR;
    		j = Malloc_SLL(L);/*获取空闲分量的下标*/
    		if(j!=0){
    			L[j].data = e;
    			for(int l = 1; l <= i - 1; l++)/*找到第i个元素之前的位置*/
    				k = L[k].cur;
    			L[j].cur = L[k].cur;/*把第i个元素之前的cur赋值给新元素的cur*/
    			L[k].cur = j;/*把新元素的下标赋值给第i个元素之前的cur*/
    			return OK;
    		}
    		return ERROR;
    	}

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作(如图3-12-3所示)。没理解可能觉得有些复杂，理解了，也就那么回事。

![Center 29][]

## 3.12.2 静态链表的删除操作 ##

故事没完，接着，排在第一个的甲突然接到一电话，看着很急，多半不是家里有紧急情况，就是单位有突发状况，反正稍有犹豫之后就急匆匆离开。这意味着第一位空出来了，那么自然刚才那个收了好处的乙就成了第一位--有人走运起来，喝水都长肉。

和前面一样，删除元素时，原来是需要释放结点的函数free()。现在我们也得自己实现它:

C代码：

/**删除在L中第i个元素e*/
    Status ListDelete(StaticLinkList L,int i){
    	int j,k;
    	if(i < 1 || i > ListLength(L))
    		return ERROR;
    	k = MAX_SIZE - 1;
    	for(j = 1; j <= i - 1; j++){
    		k = L[k].cur;
    	}
    	j = L[k].cur;
    	L[k].cur = L[j].cur;
    	Free_SSL(L,j);
    	return OK;
    }

Java代码：

/**删除在L中的第i个元素e*/
    static int ListDelete(StaticLinkList[] L,int i){
    	int j,k;
    	if(i < 1 || i > L.length)
    		return ERROR;
    	k = MAXSIZE-1;//注意k首先是最后一个元素的下标
    	for(j = 1; j <= i -1; j++)
    		k = L[k].cur;
    	j = L[k].cur;
    	L[k].cur = L[j].cur;
    	Free_SLL(L, j);
    	return OK;
    }

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for循环因为i=l而不操作j=k\[999\].cur=1 , L\[k\].cur=L\[j\].cur 也就是L\[999\].cur=L\[l\]=2 。这其实就是告诉计算机现在"甲"已经离开了，"乙"才是第一个元素。Free\_SSL(L,j);是什么意思呢?来看C代码;

![Center 30][]

Java代码:

/**将下标为k的空闲结点回收到备用链表*/
    static void Free_SLL(StaticLinkList[] space,int k){
    	space[k].cur = space[0].cur;//把第一个元素的cur值赋值给要删除的分量cur
    	space[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
    }

意思就是"甲 "现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是8的分量，它降级了，把8给"甲"所在下标为1的分量的 cur ，也就是 space\[l\].cur=space\[O\].cur=8，而space\[O\] .cur=k=l其实就是让这个删除的位置成为第一个优先空位，把它存入第一个元素的cur中，如图3-12-4所示。

![Center 31][]

当然，静态链表也有相应的其他操作的相关实现。比如我们代码中的ListLength

就是一个，来看C代码。

![Center 32][]

Java代码：

/**初始条件：静态链表L已存在。操作结果：返回L中的数据元素的个数*/
    static int ListLength(StaticLinkList[] L){
    	int j = 0;
    	int i = L[MAXSIZE].cur;
    	while(i!=0){
    		i = L[i].cur;
    		j++;
    	}
    	return j;
    }

另外一些操作和线性表的基本操作相同，实现上也不复杂，我们在课堂上就不讲解了。

## 3.12.3 静态链表优缺点 ##

总结一下静态链表的优缺点(见图3-12-5 ) :

![Center 33][]

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

# 3.13 循环链表 #

在座的各位都很年轻，不会觉得日月如梭。可上了点年纪的人，比如我--的父辈们，就常常感慨，要是可以回到从前该多好。网上也盛传，所谓的成功男人就是3岁时不尿裤子，5岁能自己吃饭……80岁能自己吃饭，90岁能不尿裤子。

![Center 34][]

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们刚才说的，不能回到从前。

比如，你是一业务员，家在上海。你要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务，如图3-13-2所示。

![Center 35][]

有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海是第一站。你会对这人说什么?神经病。哪有这么傻的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链表 ，这都是原来的单链表结构解决不了的问题。

事实上，把北京和上海之间连起来，形成一个环就解决了前面所面临的困难。这就是我们现在要讲的循环链表。

**将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linkedlist)** 。

从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。 循环链表带有头结点的空链表如图 3-13-3所示 :

![Center 36][]

对于非空的循环链表就如图3-13-4所示。

![Center 37][]

其实循环链表和单链表的主要差异就在于循环的判断条件土，原来是判断p->next是否为空，现在则是 p-> next 不等于头结点，则循环未结束。

在单链表中，我们有了头结点时，我们可以用0(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要 O(n)时间，因为我们需要将单链表全部扫描一遍 。

有没有可能用 0(1)的时间由链表指针访问到最后一个结点呢?当然可以。

不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表(如图3.13.5所示)，此时查找开始结点和终端结点都很方便了。

![Center 38][]

从上图中可以看到，终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是 rear->next->next，其时间复杂也为O(1)。

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB，如图3-13-6所示。

![Center 39][]

要想把它们合并，只需要如下的操作即可，如图3-13-7所示。

![Center 40][]

p = rearA -> next; /*保存A表的头结点，即1*/
    rearA -> next = rearB->next->next;/*将本是指向B表的第一个结点(不是头结点)，赋值给rearA->next,即2*/
    rearB->next=p;/*将原A表的头结点赋值给rearB->next,即3*/
    free(p);/*释放p*/

# 3.14 双向链表 #

继续我们刚才的例子，你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时你怎么办?

![Center 41][]

有人又出主意了，你可以先飞回上海，一路再乘火车走遍这儿个城市，到了北京后，你再飞回上海。

你会感慨，人生中为什么总会有这样出馊主意的人存在呢?真要气死人才行。哪来这么麻烦，我一路从北京坐火车或汽车回去不就完了吗。

![Center 42][]

对呀，其实生活中类似的小智慧比比皆是，并不会那么的死板教条。我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗?当然可以，只不过需要加点东西而已。

我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。 **双向链表(double linked List) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。** 所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

/*线性表的双向链表存储结构*/
    typedef struct DulNode
    {
    	ElemType data;
    	struct DulNode *prior;/*直接前驱指针*/
    	struct DulNode *next;/*直接后继指针*/
    }DulNode, *DuLinkList;

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表 。

双向链表的循环带头结点的空链表如图3-14-3 所示。

![Center 43][]

非空的循环的带头结点的双向链表如图3-14-4 所示。

![Center 44][]

由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己，即:

p->next->prior = p = p- >prior ->next

这就如同上海的下一站是苏州，那么上海的下一站的前一站是哪里?哈哈，有点废话的感觉。

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的 ListLength ，查找元素的 GetElem ，获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

就像人生一样，想享乐就得先努力，欲收获就得付代价。双向链表既然是比单链表多了可以反向遍历查找等数据结构，那么也就需要付出一些小的代价:在插入和删除时，需要更改两个指针变量。

插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。

我们现在假设存储元素 e 的结点为s，要实现将结点s插入到结点p和p -> next之间需要下面几步，如图3-14-5所示 。

![Center 45][]

s -> prior = p;/*把p赋值给s的前驱，如图1*/
    s -> next = p -> next;/*把p -> next 赋值给s的后继，如图2*/
    p -> next -> prior = s;/*把s赋值给p->next的前驱，如图3*/
    p -> next = s;/*把s赋值给p的后继，如图4*/

关键在于它们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。 所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定 s 的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

如果插入操作理解了，那么删除操作，就比较简单了 。

若要删除结点p，只需要下面两步骤，如图3-14-6所示。

![Center 46][]

p->prior->next=p->next;/*把p->next赋值给p->prior的后继，如图1*/
    p->next->prior=p->prior;/*把p->prior赋值给p->next的前驱，如图2*/
    free(p);/*释放结点*/

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior 指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

# 3.15 总结回顾 #

这一章，我们主要讲的是线性表。

先谈了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。

之后我们就线性表的两大结构做了讲述，先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。

后来是我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，如单链表、循环链表和双向链表做了讲解，另外我们还讲了若不使用指针如何处理链表结构的静态链表方法。

总的来说，线性表的这两种结构(如图 3-15-1 所示)其实是后面其他数据结构的基础，把它们学明白了，对后面的学习有着至关重要的作用 。

![Center 47][]

# 3.16 结尾语 #

知道为什么河里钓起来的鱼要比鱼塘里养的鱼好吃吗?因为鱼塘里的鱼，天天有人喂，没有天敌追，就等着养肥给人吃，一天到晚游快游慢都一样，身上鱼肉不多，鱼油不少。而河里的鱼，为了吃饱，为了避免被更大的鱼吃掉，它必须要不断地游。这样生存下来的鱼，那鱼肉吃起来自然有营养、爽口 。

五六十年代出生的人，应该也就是我们父母那一辈， 当年计划经济制度下，他们的生活被社会安排好了，先科员再科长、后处长再局长，混到哪算哪;学徒、技工、高级技工;教师、中级教师、高级教师，总之无论哪个行业都论资排辈。这样的生活如何让人奋发努力，所以经济发展缓慢。就像我们的线性表的顺序存储结构一样，位置是排好的，一切都得慢慢来。

可见，舒适环境是很难培养出坚强品格，被安排好的人生，也很难做出伟大事业。

市场经济社会下，机会就大多了，你可以从社会的任何一个位置开始起步，只要你真有决心，没有人可以拦着你。事实也证明，无论出身是什么，之前是凄苦还是富足，都有出人头地的一天。当然，这也就意味着，面临的竞争也是空前激烈的，一不小心，你的位置就可能被人插足，甚至你就得out出局。这也很像我们线性表的链式存储结构，任何位置都可以插入和删除.

不怕苦，吃苦半辈子，怕吃苦，吃苦一辈子。 如果你觉得上学读书是受罪，假设你可以活到80岁，其实你最多也就吃了 20 年苦。用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥。再说了，跟着我学习，这也能算是吃苦?

好了，今天课就到这， 下课。

**引用《大话数据结构》作者：程杰**

[Center]: /images/20220708/5f4fc790204a4bea811fe4113682434c.png
[Center 1]: /images/20220708/826f37edeed64a749a0083becfa6c0fb.png
[Center 2]: /images/20220708/e5779beb2f9948ec84cde4e3f2cd5da5.png
[Center 3]: /images/20220708/6f9010594536465b88fc8ebd81a16802.png
[Center 4]: /images/20220708/136f45013ff04e32b6608d4c275c68f3.png
[Center 5]: /images/20220708/3afd4fff195949b7b7dacd85c0cc9b9b.png
[Center 6]: /images/20220708/90304d080f1d4ac5ab28d63fd9293924.png
[Center 7]: /images/20220708/38f43ac237d9465d9cc4ddf096417870.png
[Center 8]: /images/20220708/05cd164ff7c14951bb6cae68df6610ad.png
[Center 9]: /images/20220708/e1daa895ff1443b09d3d48547eed7037.png
[Center 10]: /images/20220708/dfd25cfe5b6940499b562a556397ed56.png
[Center 11]: /images/20220708/2449e162fe2d4c7f95e20b06f99c75fe.png
[Center 12]: /images/20220708/234beb29d12843a7bee23dbf7420c8a4.png
[Center 13]: /images/20220708/43558a26be254539895cd0ea8e4c1185.png
[Center 14]: /images/20220708/41b525ae91eb47ff8f30dd6cb4386733.png
[Center 15]: /images/20220708/beba4f343e5a4767a7152ead8b27a237.png
[Center 16]: /images/20220708/f6445c940a164423b6fa8bb5a9073090.png
[Center 17]: /images/20220708/0f5ecf11b51840d0808b26b1838d6173.png
[Center 18]: /images/20220708/ecca669d11c9445fb3cdb4b62a966513.png
[Center 19]: /images/20220708/aa8ba6d8ca7e4381a3c24e910c489042.png
[Center 20]: /images/20220708/aa8d28cd89a14c5e81204e913c89b999.png
[Center 21]: /images/20220708/db7aacc28a44448189253fdc810137d1.png
[Center 22]: /images/20220708/038a11dbbb71408da0a513e1f8046b1f.png
[Center 23]: /images/20220708/33f92bc66de84a33af7d60f00c181cd6.png
[Center 24]: /images/20220708/938dcbbb01a340b890b517bffa151d96.png
[Center 25]: /images/20220708/233afd5964964f9595fffb9cf9e69244.png
[Center 26]: /images/20220708/cb711fad2216446f93a25590b19e09f8.png
[Center 27]: /images/20220708/95edf550a7a34ea1a62f070cba1020f2.png
[Center 28]: /images/20220708/5d1d6feb0ca444ab97ff3532d0c7b03a.png
[Center 29]: /images/20220708/dcda9dd7bffd4c11947c82f1029a59cc.png
[Center 30]: /images/20220708/34cc0953dca64db190f06bb8807675e9.png
[Center 31]: /images/20220708/1a7069c20f6f4ad8a59d5d34eb07d450.png
[Center 32]: /images/20220708/2308538c92cb4d539ba2201b1ea3df92.png
[Center 33]: /images/20220708/e408195f198143088504618c7aebb026.png
[Center 34]: /images/20220708/5bd5e6304bde498db61a914bc0cae928.png
[Center 35]: /images/20220708/145fa731923a4c428944eb25a484be59.png
[Center 36]: /images/20220708/b02eaa998dcc4506bf6f463bcd7971ef.png
[Center 37]: /images/20220708/67f775b0cb694ce7ab2ac5edb44ec312.png
[Center 38]: /images/20220708/ebaa3eade76f4d708621638390338ab7.png
[Center 39]: /images/20220708/8d58e096d33d4522b4d2d49e3cf2b922.png
[Center 40]: /images/20220708/94d8caea6a0f4051b4ec7979ed9516df.png
[Center 41]: /images/20220708/87c2c6404fc54db0bd460c89bc4282ad.png
[Center 42]: /images/20220708/ed108789c8ef4e02854709eb61af88e4.png
[Center 43]: /images/20220708/96559f9a69b5476e9f7e07fff47fc3a9.png
[Center 44]: /images/20220708/04f05020e30f46468c1116e525353d11.png
[Center 45]: /images/20220708/570d0b5a54a549cfa5577d3d8d190b6b.png
[Center 46]: /images/20220708/d00557a1ed9c4a91b1b3d734f66dd836.png
[Center 47]: /images/20220708/a9f50c59cd374e70896d0465e138f5d5.png