当前位置：文档之家 › 第3章线性表的链式存储

第3章线性表的链式存储

  • 格式：ppt
  • 大小：573.50 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

第三章 线性表习题

第三章 线性表习题

第三章 线性表填空题1.线性表的顺序存储结构通过 来直接反映数据元素之间的逻辑关系，而链式存储结构通过 间接反映数据元素之间的逻辑关系。

2.在线性表的顺序存储结构中，逻辑位置相邻的数据元素在 上也相邻，而链式存储结构中，逻辑位置相邻的数据元素在物理位置上 相邻。

3.线性表的链式存储结构主要包括 、 和 三种形式，其中最基本的形式是 。

4.从结构上来看，循环单链表与非循环单链表的不同在于 。

5.一元多项式f(x)=9x13-4x8+3x-5的线性链表表示是 。

6.栈和队列的逻辑结构都是 结构。

7.栈是一种特殊的线性表，其特殊性是 。

8.队列是一种特殊的线性表，其特殊性是 。

9.栈的插入与删除操作都是在 位置进行的；而队列的插入在 进行，删除操作在 进行。

选择题10.中缀形式的算术表达式A+(B-C/D)*E的后缀形式是 。

11.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是 。

A.112B.144C.148D.41212.若频繁地对线性表进行插入和删除操作，该线性表应该采用 存储结构。

A.散列B.顺序C.链式D.索引13.若长度为n的非空线性表采用顺序储存结构，删除表中第i个数据元素是，需要移动表中 个数据元素。

A.n+iB.n-iC.n-i+1D.n-i-114.若长度为n的线性表采用顺序储存结构，在表的第i个位置插入一个数据元素，需要移动表中 个数据元素。

A.n+iB.n-iC.n-i+1D.n-i-115.若长度为n的线性表采用顺序储存结构，在表的第i个位置插入一个数据元素的算法的使劲复杂性是 。

A.O(n)B. O(n2)C. O(nlog2n)D. O(log2n)16.线性链表中各结点的地址 。

A.必须连续B.一定不连续C.部分地址必须连续D.可能连续也可能不连续17.在一个具有n个结点的线性链表中查找一个结点，若查找成功，需要平均比较（ ）个结点。

《数据结构及其应用》笔记含答案 第三章_栈和队列

《数据结构及其应用》笔记含答案 第三章_栈和队列

第3章栈和队列一、填空题1、栈是限定仅在表尾进行插入或删除操作的线性表。

2、栈的修改是按照后进先出的原则进行的。

3、队是一种先进先出的线性表。

4、把队列头尾相接的顺序存储结构称为循环队列。

5、队列也是一种操作受限的线性表，允许插入的一端叫做__队尾___，允许删除的一端叫做__队头__。

二、判断题1、栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。

（√）2、任何一个递归过程都可以转换成非递归过程。

（√）3、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。

（√）4、通常使用队列来处理函数的调用。

（╳）5、循环队列通常用指针来实现队列的头尾相接。

（╳）三、单项选择题1、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C）。

A．i B．n-i C．n-i+1 D．不确定解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

3、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（D）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

数据结构c 版第二版课后习题答案

数据结构c 版第二版课后习题答案

数据结构c 版第二版课后习题答案数据结构是计算机科学中的重要概念，它研究如何组织和存储数据，以便能够高效地进行操作和检索。

C语言是一种广泛应用于软件开发的编程语言，而数据结构C版第二版是一本经典的教材，它介绍了C语言中常用的数据结构和算法。

在学习这本教材时，课后习题是检验自己理解和掌握程度的重要方式。

下面我将为大家提供一些课后习题的答案，希望对大家的学习有所帮助。

1. 第一章：引论习题1：数据结构是什么？它的作用是什么？答案：数据结构是一种组织和存储数据的方式，它可以帮助我们更高效地进行数据操作和检索。

它的作用是提供一种合理的数据组织方式，使得我们可以快速地找到和处理需要的数据。

习题2：请举例说明数据结构的应用场景。

答案：数据结构可以应用于各个领域，比如在图像处理中，我们可以使用二维数组来表示图像的像素点；在网络通信中，我们可以使用链表来存储和管理网络节点之间的连接关系；在数据库中，我们可以使用树结构来组织数据的层次关系等等。

2. 第二章：算法分析习题1：什么是时间复杂度和空间复杂度？它们分别表示什么？答案：时间复杂度是衡量算法执行时间的度量，它表示随着输入规模的增加，算法执行时间的增长趋势。

空间复杂度是衡量算法所需内存空间的度量，它表示随着输入规模的增加，算法所需内存空间的增长趋势。

习题2：请解释最坏情况时间复杂度和平均情况时间复杂度的区别。

答案：最坏情况时间复杂度是指在最不利的情况下，算法执行的时间复杂度。

平均情况时间复杂度是指在所有可能输入情况下，算法执行的平均时间复杂度。

最坏情况时间复杂度是对算法性能的保证，而平均情况时间复杂度更能反映算法的平均性能。

3. 第三章：线性表习题1：请实现一个线性表的顺序存储结构。

答案：可以使用数组来实现线性表的顺序存储结构。

定义一个固定大小的数组，然后使用一个变量来记录线性表中元素的个数，通过数组下标来访问和操作元素。

习题2：请实现一个线性表的链式存储结构。

线性表的链式存储结构实验报告

线性表的链式存储结构实验报告

实验一：线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。

（3）显示要求的结果。

【实验步骤;】（1）运行PC中的Microsoft Visual C++ 6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:head=create(PWRS);printf("所有评委打分信息如下:\n");print(head);//显示当前评委打分calc(head);//计算成绩printf("该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n");print(head);//显示去掉极限分后的评委打分}void input(NODE *s) #include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <iostream.h>#include <conio.h>#define NULL 0#define PWRS 5 //定义评委人数struct pw //定义评委信息{ char name[6];float score;int age;};typedef struct pw PW;struct node //定义链表结点{struct pw data;struct node * next;};typedef struct node NODE;//自定义函数的声明NODE *create(int m); //创建单链表int calc(NODE *h); //计算、数据处理void print(NODE *h); //输出所有评委打分数据void input(NODE *s);//输入评委打分数据void output(NODE *s);//输出评委打分数据void main(){NODE *head;float ave=0;float sum=0;{printf("请输入评委的姓名: ");scanf("%S",&s->);printf("年龄: ");scanf("%d",&s->data.age);printf("打分: ");scanf("%f",&s->data.score);printf("\n");}void output(NODE *s){printf("评委姓名: %8s ,年龄: %d,打分: %2.2f\n",s->,s->data.age,s->data.score);}NODE *create(int m){NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p->next=NULL;q->next=p;q=p;}return (head);}void print(NODE *h){ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h); }printf("\n");}int calc(NODE *h){NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h->next; //指向首元结点pmin=pmax=p; //设置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){if(p->data.score>pmax->data.score) pmax=p;if(p->data.score<pmin->data.score) pmin=p;sum+=p->data.score;}cout<<"给出最高分的评委姓名："<<pmax-><<"年龄： "<<pmax->data.age<<"分值："<<pmax->data.score<<endl;cout<<"给出最低分的评委姓名："<<pmin-><<"年龄： "<<pmin->data.age<<"分值："<<pmin->data.score<<endl;printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for (q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next; p=q;}//删除最低分结点if(p==pmax) {q->next=p->next; p=q;}//删除最高分结点}ave=sum/(PWRS-2);cout<<"该选手的最后得分是："<<ave<<endl;return 1;}实验结束。

第3章 线性表及其存储结构

第3章 线性表及其存储结构

链式存储结构，既可用来表示线性结构， 也可用来表示非线性结构。线性表的链式存 储结构，称为线性链表。 对线性链表而言，它不要求逻辑上相邻的 元素在物理位置上也相邻。其存储单元既可 以是连续的，也可以是不连续的，甚至可以 零散分布在内存中的任何位置上。 通常，为了适应线性链表的存储，计算机 的存储空间被划分成一个一个的小块，每一 小块占若干字节，这些小块就是存储结点。 存储结点的结构，如图 3-2 所示。
在稍微复杂的线性表中，一个数据元素还 可以由若干个数据项组成。例如，某班的学 生情况登记表是一个复杂的线性表，表中每 一个学生的情况就组成了线性表中的每一个 元素，每一个数据元素包括学号、姓名、性 别、入学成绩4个数据项。
3.2线性表的顺序存储及其运算
3.2.1 线性表的顺序存储 线性表的顺序存储结构称为顺序表。
第3章 线性表及其存储结构
3.1线性表的基本 概念 3.2线性表的顺序 存储及运算 3.3线性表的链式 存储及运算
3.1 线性表的基本概念
线性表是由 n (n≥0)个数据元素 a1 ,a2 ,…,an 组成的一个有限序列。表中的每一个数据元 素，除了第一个外，有且只有一个前件；除 了最后一个外，有且只有一个后件。即线性 表或是一个空表或可以表示为：
（a1 ,a2 ,…,ai ,…,an）其中 ai（i=1,2,…,n) 是属于数据对象的元素，通常也称其为线性 表中的一个结点。
数据元素在线性表中的位置，只取决于它们 自己的序号 。 非空线性表的结构特征为： ① 有且只有一个根结点a1 ,它无前件；
② 有且只有一个终端结点an ,它无后件；
③ 除根结点与终端结点外，其他所有结点 有且只有一个前件，也有且只有一个后件。线 性表中结点的个数n称为线性表的长度。当 n=0时，称为空表。

数据结构（二）：线性表的链式存储结构

数据结构（二）：线性表的链式存储结构

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

指针域：存储直接后继位置的域。

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

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。

线性表的链式存储结构

1
线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单 元（可以连续，也可以不连续）存储线性表中的数据 元素。为了反映数据元素之间的逻辑关系，对于每个 数据元素不仅要表示它的具体内容，还要附加一个表 示它的直接后继元素存储位置的信息。假设有一个线 性表（a,b,c,d），可用下图2所示的形式存储：
27
p
s
图 2-9
28
完整的算法：
int DuListInsert(DuLinkList *L,int i,EntryType e)
if (L.head->next==NULL) return TRUE; else return FALSE; }
12
6. 通过e返回链表L中第i个数据元素的内容 void GetElem(LinkList L,int i,EntryType *e) {
LNode *p; int j; //j为计数器，记载所经过的结点数目 if (i<1||i>ListLength(L)) exit ERROR; //检测i值的合理性 for (p=L.head,j=0; j!=i;p=p->next,j++); //找到第i个结点 *e=p->data; //将第i个结点的内容赋给e指针所指向的存储单元中 }
10
4. 求链表L的长度
int ListLength(LinkList L)
{
LNode *p;
int len;
for(p=L.head, len=0;p->next==NULL; p=p->next,len++);
return(len);
循环条件表达式 重复执行的语句

第3周线性表(下)第2讲-循环链表

循环链表是另一种形式的链式存储结构形式。

循环单链表：将表中尾节点的指针域改为指向表头节点，整个链表形成一个环。

由此从表中任一节点出发均可找到链表中其他节点。

循环双链表：形成两个环。

节点类型与非循环单链表的相同节点类型与非循环双链表的相同线性表(a 1, a 2, …, a i , … a n )映射逻辑结构存储结构a 1a 2a n…L带头节点循环单链表示意图1、循环单链表与非循环单链表相比，循环单链表：链表中没有空指针域p所指节点为尾节点的条件：p->next==LL pa1a2a n…【例2-8】某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素，故采用存储方式最节省运算时间。

A.单链表B.仅有头结点指针的循环单链表C.双链表D.仅有尾结点指针的循环单链表D.仅有尾结点指针的循环单链表a 1a2a n…L在尾元素之后插入一个元素删除第一个元素时间复杂度均为O(1)选择D线性表(a 1, a 2, … , a i , … a n )映射逻辑结构存储结构a 1a 2a n…L带头节点循环双链表示意图2、循环双链表与非循环双链表相比，循环双链表：链表中没有空指针域p所指节点为尾节点的条件：p->next==L一步操作即L->prior可以找到尾节点p La1a2a n…【例2-9】如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用。

A.只有尾结点指针没有头结点的循环单链表B.只有尾结点指针没有头结点的非循环双链表C.只有首结点指针没有尾结点指针的循环双链表D.既有头指针也有尾指针的循环单链表a 1a 2a n…LC.只有首结点指针没有尾结点指针的循环双链表删除第一个元素删除尾元素在第一个元素前面插入新元素在尾元素的后面插入新元素时间复杂度均为O(1)选择C【例2-10】设计判断带头节点的循环双链表L（含两个以上的节点）是否对称相等的算法。

《软件技术基础》课件第3章


else if(i<1||i>L->last+1){ print (“非法插入位置”); return 0;}
else{
for(j=L->last;j>=i;j--) L->data[j+1]=L->data[j]; //结点后移
L->data[i]=x;
//插入到L->data[i]中
L->last++;
//表长度加1
return 1;
}
}
现在分析顺序表插入算法的时间复杂度。显然，算法3.3 的时间主要花费在结点的移动上，移动结点的个数不仅依赖于 表的长度n，而且与插入的位置i有关。for语句的循环体执行了 n-i+1次。当i=n+1时，由于循环变量的终值大于初值，因而结 点后移语句不执行；当i=1时，结点后移语句执行n次，移动表 中所有结点。也就是说，该算法在最好情况下的时间复杂度是 O(1)，在最坏情况下的时间复杂度是O(n)。由于插入可能在表 中任意位置上进行，因此需分析算法的平均性能。
其删除过程见图3.3。
图3.3 顺序表删除结点的过程
具体算法如下：
算法3.4 删除顺序表的第i个结点。
int Delete(sequenlist*L,int i) //删除顺序表的第i个结点。删除成功，返回1；不成功，返回0
{ int j; if ((i<1)||(i>L->last)){ print(“非法删除位置”); return 0;}
(6) Insert(L,x,i)——插入，在L中第i个位置前插入值为x的 元素，表长加1。
(7) Delete(L,i)——删除，删除表L中第i个数据元素，表长 减1。

第3章数据结构基本类型3.3操作受限的线性表——队列-高中教学同步《信息技术-数据与数据结构》(教案

作业布置
编程实践：请实现一个循环队列，包含入队（enqueue）、出队（dequeue）、判断队列是否为空（is_empty）等基本操作。你可以使用Python语言进行编程，并编写相应的测试用例来验证你的实现。
理论思考：
思考并解释为什么队列的“先进先出”特性在现实生活中有广泛的应用。
假设你是一家大型超市的经理，你需要设计一个顾客结账排队系统。请说明你会如何利用队列的原理来设计一个既高效又公平的排队系统。
队列的应用：
结合日常生活中的排队场景，解释队列原理的实际应用，如银行取号系统、医院挂号系统等。
强调队列在处理具有“先来先服务”特性问题时的有效性，以及如何通过队列来优化服务流程。
教学难点
循环队列的实现与理解：
理解循环队列如何通过循环使用数组空间来避免“假溢出”现象。
掌握如何根据队列的头部和尾部指针判断队列的空和满状态。
完成后与同学交流并分享自己的解题思路和经验。
通过编程练习巩固所学知识，提高学生的编程能力和解决实际问题的能力。
鼓励学生互相交流和讨论，培养学生的团队协作能力和沟通能力。
课堂小结
作业布置
课堂小结
本节课我们深入学习了数据结构中的队列（Queue）这一重要概念。首先，通过日常生活中排队的例子，我们直观地理解了队列的基本特点——先进先出（FIFO），即新加入的元素总是排在队尾，而需要处理的元素总是从队头开始。
准备课后作业：设计一些与队列相关的课后作业，如编写顺序队列和链式队列的实现代码、分析队列在实际问题中的应用等，以巩固学生的学习效果。
教学媒体
教材或讲义：
提供了队列的基本概念、特征、实现方式以及应用实例的文字描述。
包含了队列的抽象数据类型定义、队列的存储结构（顺序队列、循环队列、链队列）等核心知识点的详细解释。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
L
(a) 空循环链表
L
a1
a2
...
an
(b) 非空循环链表
3.1.3 双向链表
在单链表结点中只有一个指向其后继结点的next 指针域，而找其前驱则只能从该链表的头指针开始，顺 着各结点的next指针域进行查找，也就是说找后继的时 间复杂度是O(1)，找前驱的时间复杂度是O(n)。如果也 希望找前驱像后继那样快，则只能付出空间的代价：每 个结点再加一个指向前驱的指针域prior，结点的结构修 改为下图，这样链表中有两个方向不同的链，用这种结 点组成的链表称为双向链表。
1．带头结点的单链表 2．不带头结点的单链表
3.3.3 单链表插入操作的实现
单链表的插入操作是指在表的第i个位置结点处插入 一个值为data的新结点。插入操作需要从单链表的第一个结 点开始遍历，直到找到第i个位置的结点。插入操作分为在 结点之前插入的前插操作和在结点之后插入的后插操作。
1．前插操作 2．后插操作
2．整数型单链表算法
3．不带头结点的单链表算法
3.2.2 尾插法单链表的创建实现
用头插法实现单链表的创建，比较简单，但读入的 数据元素的顺序与生成的链表中元素的顺序是相反的。若希 望两者次序一致，则用尾插法创建单链表。为了快速找到新 结点插入到链表的尾部位置，所以需加入一个尾指针r用来 始终指向链表中的尾结点。初始状态：头指针L和尾指针r均 为空，把各数据元素按顺序依次读入，申请结点，将新结点 插入到r所指结点的后面，然后r指向新结点，直到读入结束 标志为止。
3.2.2 尾插法单链表的创建实现
L
插入P前的尾指针 插入P后的尾指针
r
3
4
P1
x^
2
3.3 单链表运算的实现
单链表建立之后，如果要进行一些如查找、插入、删除 等操作该如何实现？所以还须掌握一些单链表的各种算法，来 实现这些操作。单链表的运算和顺序表类似，比较多。它的运 算包括链表初始化、判表空、清空辅助运算和求表长、查找、 插入和删除基本运算。下面分别介绍各运算的算法的实现过程 。
第3章 线性表的链式存储
本章介绍线性表的另一种存储方式：链式存储。链 式存储结构通过“链”建立起数据元素之间的逻辑关系。它 不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要 用地址连续的存储单元来实现，因此在操作上使得插入和删 除操作不需要移动大量的结点。本章主要讲解线性表的链式 存储结构、链表的创建及它的基本运算和实现算法。
存Hale Waihona Puke 地址 数据域108C
指针域
136
首元素位置
100
A
110
……… ……… ………
136
D NULL
110
B
108
3.1.2 循环链表
循环链表就是将单链表中的最后一个结点的next指 针指向链表中第一个结点。链的表头和表尾相接，使整个链 表构成一个环形。这样做的好处是对表的链接方式改变后， 无须增加存储量，即可使得表处理更加方便灵活。
3.2.1 头插法单链表的创建实现
用头插法实现单链表的创建是从一个空表开始重复 读入数据，每读入一个数据元素则申请一个结点，将读入 数据存放到新结点的数据域中，然后将新结点插入到当前 链表的表头上，直到读入结束标志为止。因为是在链表的 头部插入，读入数据的顺序和链表中的逻辑顺序是相反的 。
1．字符型单链表算法
3.3.1 单链表辅助运算的实现
单链表辅助运算主要是指在对单链表进行插入、删 除和查找等操作时的执行条件或准备工作的检查和判断。具 体分为链表初始化、判表空、清空三个操作。
1．初始化链表L 2．清空链表L 3．判链表L是否为空
3.3.2 单链表求表长的实现
求单链表的长度与顺序表不同，顺序表可以通过保 存表的实际长度length的值直接求得；而单链表需要从第一 个结点开始，一个一个结点进行遍历，直到表的末尾。下面 对单链表是否带头结点分别介绍实现算法。
3.1.1 单链表
在链式存储中，逻辑上相邻的数据元素在物理存储 位置不一定也相邻。那么，怎么表示两个数据元素逻辑上的 相邻关系呢？可以这样解决，把原来的数据元素结点存储信 息进行扩展，每个存储结点不仅存储数据元素本身的信息， 而且需要存储数据元素之间逻辑关系的信息。
3.1.1 单链表
0123
ABCD
3.1 线性表的链式存储结构
线性表的顺序表示的特点是用物理位置上的邻接关系 来表示结点间的逻辑关系，这使得可以随机存取表中的任一 结点，但也使得插入和删除操作会移动大量的数据元素，而 且线性表的容量难以扩充。下面介绍的链式存储结构具有很 多优点，它可以避免插入和删除操作带来的大量结点的移动 ，能给结点动态分配存储空间等优点。下面介绍几种常用的 链表。
指针域 数据域 指针域
prior data next
3.1.3 双向链表
L L
prior data next
^
^
(a) 空双向循环链表
a1
... ...
an
(b) 非空双向循环链表
3.1.4 静态链表
静态链表就是用一维数组来描述线性链表，结点中 使用游标（即数组下标）指示直接后继结点在数组中的相对 位置。这种描述方法便于在没有指针类型的高级程序设计语 言（如FORTRAN）中使用链表结构。这种存储结构，虽然 仍需要预先分配一个较大的空间，但在做线性表的插入和删 除操作时不需移动元素，仅需修改指针，故仍具有链式存储 结构的主要优点。
3.3.3 单链表插入操作的实现
q
p
ai-2
ai-1
ai
s
x
(a) 插入前
q
p
ai-2
ai-1
ai
s
x
(b) 插入后
p
ai-1
ai
ai+1
s
x
(a) 插入前
p
ai-1
ai
ai+1
s
x
(b) 插入后
3.3.4 单链表删除操作的实现
单链表的删除操作是指删除第i个结点。通过改变待 删除结点的前驱结点指针，让它直接指向待删除结点的后继 就可以实现删除操作。删除操作和插入操作相同的是需要从 开始结点进行遍历，直到找到第i个位置的结点。如果删除 的是第一个结点，情况有所不同，需要把该结点的直接后继 结点的地址赋给头指针。对于其它结点，需要保存被遍历到 的结点的直接前驱，找到第i个结点后，把该结点的直接后 继作为它的直接前驱的直接后继。
3.1.4 静态链表
头结点位置
SL=0
AV=6
data next
0
4
1
a4
5
2
a2
3
3
a3
1
4
a1
2
5
a5
-1
6
7
7
8
8
9
9
10
10
11
11
-1
3.2 单链表创建算法的实现
单链表的建立与顺序表的建立不同，它是一种动态 管理的存储结构，链表中的每个结点占用的存储空间不是预 先分配，而是运行时系统根据需求而动态生成的。单链表的 建立分为在头部插入结点建立单链表和在尾部插入结点建立 单链表（分别简称为头插法和尾插法）。下面分别介绍两种 创建算法的实现过程。