数据结构课件第2章线性表A

上堂课要点回顾数据结构课程——涉及数学、计算机硬件和计算机软件数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,S)表示。数据结构内容——数据的逻辑结构、存储结构和运算

算法效率指标——时间效率和空间效率1数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构2近3周

上课

内容第2章线性表第3章栈和队列第4章串第5章数组和广义表

线性结构

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：（逻辑、存储和运算）3第二章线性表

学习指南【学习目标】

1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。

3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

4.结合线性表类型的定义增强对抽象数据类型的理解。4【重点和难点】

链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点】

线性表、顺序表、链表【学习指南】

本章建议完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38第二章线性表

学习指南(续)5线性结构的特点：①只有一个首结点和尾结点；

②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表简言之，线性结构反映结点间的逻辑关系是一对一的见第2章6第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表

2.4一元多项式的表示及相加7线性表：由一组数据组成，线性表或者是一个空表，或者可以写成（a1,a2,…ai,…an）,其中ai是取自某个集合S的元素。当1<i<n时，数据元素ai-1称为数据元素ai的直接前驱，而称ai+1为ai的直接后继。线性表中数据元素的个数称为该线性表的长度。2.1

线性表的类型定义8（a1,a2,…ai-1，ai,ai＋1

，…,an）1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点9形式化定义：Linearlist=(D,R)其中：D0为某个数据对象的集合N为线性表长度10线性表的主要操作初始化求长度取元素定位插入删除11对线性表可进行如下基本运算：

InitList(&L)：构造一个空的线性表L。ListLength(&L)：返回L数据元素的个数。GetElem(L,i,&e)：用e返回L中第i个数据元素的值。ListInsert(&L,i,e)：在L中第i个位置前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)：删去L中第i个元素，用e返回其值，L的长度减1。

PriorElem(L,cur_e,&pre_e)：用pre_e返回数据元素cur_e的前驱，如果存在的话。

NextElem(L,cur_e,&next_e)：用next_e返回数据元素cur_e的后继，如果存在的话。

LocateElem(L,e,compare())：返回L中第一个与e满足关系compare()的数据元素的位序。0表示这种元素不存在。12例1分析26个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女182001级电信016班2001011810260何仕鹏男182001级电信017班2001011810284王爽女182001级通信011班2001011810360王亚武男182001级通信012班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性13例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18

健康陈红790632女20

一般刘建平790633男21

健康张立立790634男17

神经衰弱……..……..…….…….…….14例4、一副扑克的点数（2，3，4，…，J，Q，K，A）

15从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

16

线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P1917

算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。

voidunion(List&La，ListLb){La-len=ListLength(La);Lb-len=ListLength(Lb);for(I=1;I<=Lb-len;I++){

GetElem(Lb，I，e);

if(!LocateElem(La，e，equal))

ListInsert(La，++La-len，e)}//for}18算法2.2p21例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：

19voidMergeList(listla，listlb，list&lc)

InitList(lc);I=j=1;k=0;La-len=ListLength(la);Lb-len=ListLength(lb);while((I<=la-len)&&(j<=lb-len)){

GetElem(la，I，ai);getelem(lb，j，bj);

if(ai<=bj){listinsert(lc，++k，ai);++I;}

else{listinsert(lc，++k，bj);++j;}}//while20

while(I<=la-len){

getelem((la，I++，ai);listinsert(lc，++k，ai);}//while处理la表

while(j<=lb-len){

getelem((lb，j++，bj);listinsert(lc，++k，bi);}//while处理lb表

}//MergeList21练：判断下列叙述的正误：1.数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.数据结构是指相互之间存在一种或多种关系的数据元素的全体。4.线性结构反映结点间的逻辑关系是一对一的。一维向量是线性表，但二维或N维数组不是。“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。√×√√××222.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析本节小结作业232.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻24线性表顺序存储特点：1.

逻辑上相邻的数据元素，其物理上也相邻；2.

若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC(ai)=LOC(a1)+L*（i-1）

LOC(ai+1)=LOC(ai)+L

注意：C语言中的数组的下标从0开始，即：V[n]的有效范围是V[0]～V[n-1]25线性表的顺序存储结构示意图a1a2……aiai+1……an

地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L26一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是

113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）27用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。

voidbuild()/*字母线性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

V[i]=V[i-1]+1;

}核心语句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例228voidmain(void)

/*主函数，字母线性表的生成和输出*/{n=26;

/*n是表长，是数据元素的个数，而不是V的实际下标*/build();display();}voiddisplay()

/*字母线性表的显示，即读表操作*/{

inti;for(i=0;i<=n-1;i++)printf("%c",V[i]);printf("\n");}执行结果：abcdefghijklmnopqrstuvwxyz292.2.2顺序表的实现（或操作）回忆：数据结构基本运算操作有：修改、插入、删除、查找、排序1)修改通过数组的下标便可访问某个特定元素并修改之。核心语句:

V[i]=x;显然，顺序表修改操作的时间效率是T(n)=O(1)302)插入在线性表的第i个位置前插入一个元素实现步骤：将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?应当有1≤i≤n+1或i=[1,n+1]for(j=n;j>=i;j--)a[j+1]=a[j];

a[i]=x;n++;//元素后移一个位置//插入x//表长加1核心语句：31由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。用结构类型来定义顺序表类型。

#defineListSize100

typedef

int

DataType;

typedef

struc{

DataType

data[ListSize];

intlength;}Sqlist;32线性表的插入运算是指在表的第I(1≦i≦n+1)个位置上，插入一个新结点x，使长度为n的线性表

(a1，…ai-1，ai，…，an)

变成长度为n+1的线性表

(a1，…ai-1，x，ai，…，an)33算法2.3P23VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1){printf(“Positionerror”);returnERROR};34

if(L.length>=ListSize){

printf(“overflow”);

exit(overflow);}

for(j=L.length-1;j>=I-1;j--)L.data[j+1]=L.data[j];L.data[I-1]=x;

L.length++;}35在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入2536实现步骤：将第i至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当有1≤i≤n或i=[1,n]3)删除删除线性表的第i个位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：37123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：38顺序表插入和删除的完整程序可自行用C语言编制。自行上机练习题：设有线性表LA＝（3,5,8,11）和

LB=（2,6,8,9,11,15,20）；①若LA和LB分别表示两个集合A和B，求新集合

A＝AUB（‘并’操作，相同元素不保留）；注：此题来源于教材的例2.1和例2.2，见P20按规律插入插入到尾部预测输出：LA=（3,5,8,11,2,6,9,15,20）②将LA与LB表归并，要求仍有序（相同元素要保留）预测输出：LC=（2,3,5,6,8,8,9,11,11,15,20）392.2.3顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？讨论1：若在长度为n的线性表的第i位前插入一元素，则向后移动元素的次数f(n)为: f(n)=n–i+1时间效率分析:40讨论2：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为：

f(n)=思考：若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中元素全部要前移（特别慢）；若要考虑在各种位置删除（共n+1种可能）的平均移动次数，该如何计算？n–i可以证明：插入、删除操作平均需要移动一半元素(n/2)插入、删除算法的平均时间复杂度为：O(n)显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）41证明：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n-1;……若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+…+n=n(n+1)/2

所以平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少种插入形式?——连头带尾有n+1种同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)

42教材P25算法2.5也是对执行效率的推导：假定在表中任意位置插入、删除元素都是等概率的，插入概率p(i)=1/(n+1)，删除概率q(i)=1/n，则：插入操作时间效率（平均移动次数）

删除操作时间效率（平均移动次数）

43本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素；缺点：在插入，删除某一元素时，需要移动大量元素。为克服这一缺点，我们引入另一种存储形式：链式存储结构见2.3节442.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析本节小结作业452.3.1链表的表示链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现注意：每个存储结点都包含两部分：

数据域和指针域46例1画出26个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下：

解：该字母表的逻辑结构为：（a,b,…,y,z）aheadb/\z……各结点由两个域组成：数据域：存储元素数值数据；指针域：存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或样式：47与链式存储有关的术语：1、结点：数据元素的存储映像。由数据域和指针域两部分组成；2、链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……head循环链表示意图：484、头指针、头结点和首元结点

示意图如下：头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。492.3.1线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：50

其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（SingleLinked)。

显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink51单链表示意图如下：

……110……130135……160头指针head165170……200205…………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………16552headbatcateatmat^…单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。用C语言描述的单链表如下：Typedefchardatatype;

Typedef

structnode{

datatypedata;

structnode*next;}listnode;53

typedef

listnode*linklist;

listnode*p;

linklisthead;注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即

p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数

free(p)释放所指的结点变量空间。54指针变量P和（其值为结点地址）和结点变量*P之间的关系。551.链式存储特点：逻辑上相邻，物理上不一定相邻链表存放示意图如下：a1heada2/\an……讨论1

：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)562.与链式存储有关的术语1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。4）头指针、头结点和首元结点以教材P27图2.5和图2.6内容为例说明。57何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。

头指针头结点首元结点a158一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是3159上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点60答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点61讨论3.头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。答：什么是结构类型？如何书写表达？

——补充C语言内容

头结点的数据域H623.补充结构数据类型及其C语言表示法①类型定义和变量说明可以合写为：struct

mytest

{

//mytest是自定义结构类型名称char

data;//定义数据域的变量名及其类型struct

mytest

*next;//定义指针域的变量名及其类型}test，*head