计算机软件技术基础-课件 第2章 线性结构

第2章线性结构2.1线性表2.2栈和队列2.3串2.4数组、特殊矩阵和广义表线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构

若结构是非空有限集，则有且仅有一个起始元素和一个终点元素，并且所有的数据元素最多只有一个直接前驱和一个直接后继。→可表示为：（a1,a2,……,an）

线性数据结构有且仅有一个起始元素，无直接前驱仅有一个直接后继；有且仅有一个终点元素，无直接后继仅有一个直接前驱；除起始元素和终点元素外，其它元素只有一个直接前趋和一个直接后继。线性结构的逻辑特征：

简言之，线性结构反映元素间的逻辑关系是

的。一对一(1:1)线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表用线性序列来表示线性结构

（a1,a2,…,ai

,…,an）

a1

为起始元素，an

为终点元素，

ai

为索引号为i

的内部元素线性数据结构II2.1线性表2.1.1线性表的逻辑结构2.1.2线性表的顺序存储及运算2.1.3线性表的链式存储及运算2.1.4顺序表和链表的比较2.1.1线性表的逻辑结构1.线性表的定义2.线性表的基本操作（a1,a2,…ai-1，ai,ai＋1

，…,an）1.线性表的定义

定义：线性表是n（n≥0）个相同类型的数据元素a1,a2,…,an所构成的有限线性序列。n=0时称为空表n>0时称为非空表数据元素线性起点ai的直接前驱ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长线性终点

其中数据元素ai（1≤i≤n）只是一个抽象的符号，其具体含义在不同的情况下可以不同。例126个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级2008011810205于春梅女182008级电信016班2008011810260何仕鹏男182008级电信017班2008011810284王爽女182008级通信011班2008011810360王亚武男182008级通信012班：：：

：：例2

学生情况登记表分析：数据元素都是记录；元素间关系是线性的。分析：数据元素都是字母；元素间关系是线性的。注意：同一线性表中的元素必定具有相同数据类型！2.线性表的基本操作1.置空表：Init_List（L）将线性表L置成空表2.求长度：Length_List（L）求给定线性表L的长度3.取元素：Get_List（L，i)若1≤i≤length(L)，则取第i个位置上的元素，否则取得的元素为NULL（空元素）。4.定位函数：Locate_List（L，X）在线性表L中查找值为X的元素的位置。5.插入：Insert_List（L，i，X）在线性表L中第i个位置上插入值为X的元素。6.删除：Delete_List（L，i）删除线性表L中第i个位置上的元素。

例：假设线性表L=(23,56,89,76,18)，i=3，x=56，y=88，则对L的一组操作及结果如下：

所得结果//5//89//2//(23,56,88,89,76,18)//(23,56,88,76,18)(1)Length(L)(2)Get(L,i)(3)Locate(L,x)(4)Insert(L,i,y)(5)Delete(L,i+1)

线性表的分类根据数据元素在计算机内的存储结构，可分成两类：顺序存储结构——顺序表（向量表）链式存储结构——链表2.1.2线性表的顺序存储及运算1.顺序表的定义及C语言描述2.顺序表基本操作的实现3.顺序表应用举例顺序表线性表的顺序表示又称为顺序存储结构或顺序映像。

顺序表的定义：用一组物理地址连续的存储单元顺序存储在逻辑上相邻的线性表数据元素。

顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素。1.顺序表的定义及C语言描述可以用

类型来实现数组线性表顺序存储特点：逻辑上相邻的数据元素，其物理上也相邻；若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。注意：C语言中的数组的下标从0开始，即：data[n]的有效范围是V[0]～V[n-1]

设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为D字节，则表中任一数据元素ai的存放地址为：LOC(ai)=LOC(

a1

)+D*（i-1）上述公式的解释如图所示a1a2……aiai+1……an

地址内容元素在表中的位序1i2n空闲区i+1Db=LOC(a1)b+Db+(i-1)Db+(n-1)Db+(max-1)DLOC(ai)=LOC(a1)+D*（i-1）线性表的顺序存储结构示意图注：顺序表中任意一个元素的存取时间都相等，它是一个随机存取结构。因此：LOC(M[3])=98+5×(3-0)=113此题要注意下标起点的不同解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例：设有一维数组Ｍ，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素Ｍ[0]的第一个字节的地址是98，则Ｍ[3]的第一个字节的地址是多少？113元素a1元素a2……..元素ai+1……..01i

可用C语言中的一维数组来描述:#defineM100

/*定义M为常数100，M的值作为数组的最大容量*/

intV[M];

/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*DV[０]V[１]V[i]V[M-1]顺序表的存储结构由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。【？缺少什么信息？】又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。

顺序表的存储结构#defineMAXSIZE100

/*线性表可能达到的最大长度为100*/typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];

/*线性表占用的数组空间*/intcnt;/*线性表实际长度，空表置0。线性表中最后一个元素在数组data[]中的下标为cnt-1*/}SeqList;

顺序表的存储结构

顺序表的存储结构 #defineMAXSIZE100 typedefintElemType;typedefstruct { ElemTypedata[MAXSIZE]; intcnt; }SeqList;2.顺序表基本操作的实现在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是SeqList类型的顺序表，则表中第i

个元素是L.data[i-1]。顺序表的表长cnt，最后一个元素为L.data[cnt-1]。

2.顺序表基本操作的实现顺序表的运算：主要有存取、插入、删除、合并、分解、复制、检索（查找）、排序（分类）、求长度等常用的指针基本操作（设指针变量p、q的定义为SeqList*p,*q）q=(SeqList*)malloc(sizeof(SeqList));//stdlib.hp=q;free(p);2.顺序表基本操作的实现顺序表的初始化：(指针形式)顺序表的初始化即构造一个空表。将L设为指针参数，首先动态分配存储空间，然后，将表中cnt置为0，表示表中没有数据元素。算法如下：

SeqList*Init_SeqList(){ SeqList*L; L=(SeqList*)malloc(sizeof(SeqList)); L->cnt=0;returnL;}设调用函数为主函数，主函数对初始化函数的调用如下：

main(){ SeqList*L; L=Init_SeqList(); …

}顺序表的初始化2.顺序表基本操作的实现按序号查找：注意：元素标号与数组的下标之间的关系时间复杂度为?

O(1)元素an……..元素ai……..元素a2元素a1data[0]data[1]data[i-1]data[n-1]2.顺序表基本操作的实现按内容查找：Locate（L，x）：查找顺序表中是否含有与x值相同的元素。ai-1…..a2a1an…ai+1aix2.顺序表基本操作的实现按内容查找：Locate（L，x）：查找顺序表中是否含有与x值相同的元素。ai-1…..a2a1an…ai+1aix2.顺序表基本操作的实现按内容查找：ai-1…..a2a1an…ai+1aix如果x和ai-1相同，则找到并停止查找；否则按照前面的步骤继续下去2.顺序表基本操作的实现按内容查找：ai-1…..a2a1an…ai+1aix如果此时仍然没有找到，返回错误并停止有关算法及程序在“查找与排序”一章中介绍2.顺序表基本操作的实现按内容查找Locate（L，x）：intLocate_SeqList(SeqList*L,ElemTypex){ inti=1;//i为逻辑序号 while(i<=L->cnt&&L->data[i-1]!=x) i++; if(i>L->cnt)return-1; elsereturni;/*返回数据元素逻辑序号*/}2.顺序表基本操作的实现以下主要讨论线性表的插入和删除两种运算。1)顺序表的插入：顺序表的插入是指在长度为n的线性表（a1，a2，…，ai，…，an）的第i－1个元素ai－1之后和第i个元素ai之前插入一个新元素ax。设插入后的线性表中的数据元素为，则插入操作示意图…..a2a1an…..ai+1ai01i-1iai-1…..a2a1an…ai+1ai

axai-1…..a2a1

aiai+1…an

an……ai+1ai

axn-1插入操作示意图动画顺序表上完成这一运算通过以下步骤进行：

(1)将ai～an顺序向后移动，为新元素让出位置,向后移动的结点个数为（n－i＋1）

(2)将x置入空出的第i个位置；

(3)修改表长。在第i个结点之前插入数据元素时，移动元素次数的平均值为：2.顺序表基本操作的实现其中，注：时间复杂度为O(n)插入运算intInsert_SeqList(SeqList*L,inti,ElemTypex){/*在线性表L中第i个元素之前插入x，

i的合法值为1

i(L->cnt+1)*/intj;if((i<1)||(i>L->cnt+1)){ printf(“位置错LocateError!”); return0;} /*位置i值不合法*/if(L->cnt==MAXSIZE){printf(“表满Filled!");return(ERROR);}for(j=(L->cnt-1);j>=(i-1);j--) L->data[j+1]=L->data[j];/*插入位置后的元素依次右移*/L->data[i-1]=x;/*插入x*/L->cnt++;/*表长加1*/return1;}示例：2.顺序表基本操作的实现2)顺序表的删除：顺序表的删除是指在长度为n的线性表（a1，a2，…，ai，…，an）中删除第i个元素ai，则其长度变为n-1。设删除后的线性表中的数据元素为，则删除操作示意图ai-1…..a2a1alen

…ai+1aiai-1…..a2a1aiai+1…alen

ai+1alenai+1…ai+1

…alen

…..a2a1an…..ai+1ai01i-1in-12.顺序表基本操作的实现2)顺序表的删除：删除第i个元素，移动结点的个数为（n-i），则移动次数的平均值为其中，注：时间复杂度为O(n)例：下图(a)是一个长度为7的有序线性表，若要删除表中值为24的元素，则必须把值为28到77的所有元素依次向前移动一个位置。算法流程图→(,a1,a2,…,ai-1,ai+1,...,an)3.顺序表应用举例例

将顺序表(a1,a2,…,ai-1,ai,ai+1,...,an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大(这里假设数据元素的类型具有可比性,不妨设为整数型)，操作过程如图2.5所示。这一操作称为划分。a1也称为基准。基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：(a)当前数据元素ai比a1大(>=)时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。(b)若比a1小，说明它应该在a1的前面，此时将它前面的元素都依次向后移动一个位置，然后将它置入最前面。

(a1,a2,…,ai-1,ai,ai+1,...,an)ai

↑

2515301020206025103035601535……

(a)划分前

(b)划分后图2.5顺序表的划分算法描述如下：

voidpart(SeqList*L){ inti,j;//i是逻辑序号，j是循环变量 ElemTypex,y; x=L->data[0];//将基准置入x中 for(i=2;i<=L->cnt;i++) { if(L->data[i-1]<x)//当前元素小于基准

{ y=L->data[i-1];//保存当前元素

for(j=i-1;j>=1;j--)//移动

L->data[j]=L->data[j-1]; L->data[0]=y;//当前元素置入最前面

} }}说明：

本算法中，有两重循环，外循环执行n-1次，内循环中移动元素的次数与当前数据的大小有关。当第i个元素小于a1时，要移动它上面的i-1个元素，再加上当前结点的保存及置入，所以移动i-1+2次，在最坏情况下，a1后面的结点都小于a1，总的移动次数为：即最坏情况下移动数据时间性能为O(n2)。这个算法简单但效率低，在快速排序中的另一种划分算法，它的性能为O(n)。nn(n-1)*(n+4)∑(i-1+2)=∑(i+1)=i=2i=22→(,a1,a2,…,ai-1,ai+1,...,an)(a1,a2,…,ai-1,ai,ai+1,...,an)ai

↑顺序表小结顺序表的优点：逻辑关系体现在存储结构的相邻关系中，无需增加额外的存储空间；可以随机存取表中任一元素(时间复杂度为O(1))。缺点：插入和删除运算都不太方便(时间复杂度为O(n))

；采用静态存储分配，可能会浪费空间；容量不容易扩充。解决方法?：引入另一种存储形式：链式存储结构顺序表作业：习题2:2.5(1)2.1.3线性表的链式存储及运算1.

单链表2.

双向链表线性表要点回顾线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或1:1存储结构：顺序、链式运算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找快O(1)缺点：插入、删除慢O(n)1.单链表(1)链式存储结构的特点链表(LinkedList)是指用一组任意的存储单元来存储线性表中的数据元素。这组存储单元即可以是连续的，也可以是不连续的。逻辑上相邻的数据元素在物理上不一定相邻，只能顺序(依次)访问。如何实现？ 在存储每个结点值的同时，还必须存储指示其后继或前驱结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。(1)链式存储结构的特点链表中的结点结构：数据域+指针域。链表的样式：指针数据指针数据指针或样式：数据域：存储数据元素信息指针域：存储直接后继或者直接前驱的存储位置链表存放示意图如下：a1heada2/\an……说明：链表中的每一个结点只有一个指向后继的指针，这种链表称为单链表（SingleLinkedList)。单链表中每个结点的存储地址是存放在其前驱结点的指针域中。起始结点（表头结点）无前驱，故应设表头指针（头指针）HEAD指向起始结点。终点元素无后继，它的指针域为空，即NULL（图示中也可用^表示)。链表存放示意图datanext结点示意图例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）讨论1：每个存储结点包含两部分：数据域和

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

指示。其前驱结点的指针域的值指针域(2)与链式存储有关的术语：1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

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

示意图如下：头指针头结点首结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点或为首结点）（即线性表的第一个元素）的特殊指针；首结点是指链表中存储线性表第一个数据元素a1的结点；头结点是在链表的首结点之前附设的一个结点，其数据域内可以不存储任何信息（也可存放线性表的长度等附加信息）。（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：一个线性表的逻辑结构为：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①

无头结点②

有头结点上例链表的逻辑结构示意图有以下两种形式：答：讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点讨论1.在链表中设置头结点有什么好处？讨论3.头结点的数据域内装的是什么？头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。答：什么是结构类型？如何书写表达？——补充C语言内容

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

node

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

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

node

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

//SLNODE等价于structnodeSLNODE

test，*head;//test变量是structnode结构类型,*head是node结构类型的头指针//以26个字母的链表为例，每个结点都有两个分量：字符型指针型假设某个结点用变量test表示，其中两个分量分别用data和*next表示，则：*nextdatatest补充：结构类型的C语言表示法②对于指向结构变量test首地址的指针，还可说明为：

SLNODE

test

,*p,*q;

③每个结点的分量如何表示？*nextdatatestp方式1：直接用

test.data＝'a'；

test.next=q方式2：先让指针变量p指向该结点的首地址，然后用：

p->data='a';p->next=q;方式3：先让指针变量p指向该结点的首地址，然后用：

(*p).data='a'；(*p).next＝q‘a’‘b’qp设p为指向链表的第i个元素的指针,则第i个元素的数据域写为

，指针域写为

。p->dataai的值p->nextai+1的地址练习：对于单链表结点结构的抽象描述:typedefstructnode{ElemTypedata;//数据域

structnode*next;//指针域}SLNODE;数据元素之间的相对关系是由指针域所指示的，由链建立的顺序必须与数据元素的逻辑次序一致，而结点在存储器中的物理位置可以是任意的。对比：关于顺序表的抽象定义：typedefstructSqnode{ElemTypedata[MAXNUM];//表长（特指元素个数）intLast;//表当前存储容量（字节数）}SqList;补充：结构类型的C语言表示法④三个有用的库函数（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度；malloc(m)

—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)

——释放指针p所指变量的存储空间，即彻底删除一个变量。问1：自定义结构类型结点的长度m是多少？问2：结构变量的首地址(指针p）是多少？问3：怎样删除结构结点？*nextdata长度为m字节pm＝sizeof(SLNODE)p＝(SLNODE*)malloc(m)free(p)只能借助其指针删除！

单链表的实现(1)单链表的定义及其初始化

(2)单链表的建立和输出(3)单链表的访问(4)单链表的插入(5)单链表的删除(1)单链表的定义及其初始化单链表的定义：n个结点由指针链组成一个链表。其结点只有一个指针域的链表，称为单链表或线性链表；链表是由一个个结点构成的，结点定义如下：typedefstructnode{

ElemTypedata;//数据域

structnode*next;//指针域

}SLNODE;单链表的初始化定义头指针变量：

structnode*h;或者SLNODE*h这样定义一个structnode类型的指针变量之后，系统并没有为它分配内存单元。这需要通过动态申请内存单元来存放结点。C语言中提供的malloc(n)可以完成此功能。由于一个空的单链表没有一个结点，故头结点(或头指针)指向为空NULL。具体操作如下：h=(SLNODE*)malloc(sizeof(SLNODE));h->next=NULL;执行后的逻辑示意图如上图所示。

^空表h(2)单链表的建立实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将其地址存放在相应结点的指针域中。假设线性表中结点的数据类型是字符型，我们逐个输入这些字符型的结点，并以特殊字符(例如“\n”)为输入结束标记。动态地建立单链表的常用方法有如下两种：头插法建表尾插法建表babaxPPs在P所指向的结点之后插入新的结点xs单链表的插入关键语句：s->next=P->next;P->next=s;∧HH∧a1Hsa2该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。关键语句：

s->next=H->next;H->next=s;头插法建表s∧a1SLNODE*createfromHead(){ SLNODE*head;SLNODE*s; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE));x=get_data();while(x!=-1）{s=(SLNODE*)malloc(sizeof(SLNODE));s–>data=x;s–>next=head->next;

head->next=s;x=get_data();} returnhead}头插法建表head->next=NULL;头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。如何实现？该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。尾插法建表关键是要保存尾结点（最后一个结点）的位置。尾插法建表∧HrHq新结点头指针头结点a1∧增加一个结点Ha1b2∧q新结点rr（始终指向尾结点）关键语句：r->next=q;r=q;SLNODE*createfromRear(){SLNODE*head;SLNODE*r,*q; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE)); r=head;

head->next=NULL;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;r–>next=q; r=q;/*r永远指向链表的最后一个结点*/x=get_data();}

r->next=NULL;

//将最后一个结点的next链域置为空returnhead;}尾插法建表特别容易忘记！！//带头结点SLNODE*createfromRear2(){SLNODE*head; SLNODE*r,*q; ElemTypex;

head=NULL; r=head;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;

if(head==NULL){head=q;r=head;}//新结点插入空表

else

r–>next=q; r=q;/*r永远指向链表的最后一个结点*/x=get_data();}

if(r!=NULL) r->next=NULL;

//将最后一个结点的next链域置为空returnhead;}尾插法建表不带头结点头结点的用途：对首结点进行统一的处理；对空表、非空表进行统一的处理。voiddisplay(SLNODE*head)/*字母链表的输出*/{SLNODE*p;p=head;/*只要没到最后一个元素，就不停地“顺藤摸瓜”输出*/while(p->next!=NULL)/*存在头结点*/{p=p->next;printf("%c",p->data);}

}讨论：要统计链表中数据元素的个数，该如何改写？

sum++;单链表的输出(3)单链表的访问思路：要找到第i个数据元素，关键是要先找到指向该结点的指针p即可。难点：单链表中想访问第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取。核心语句：j=0;p=head;WHILE(p->next!=NULL&&j<i){p=p->next;j++;}if(p!=NULL&&j==i)

return

(p->data);eslereturn(-1);}在链表中插入一个元素的示意图如下：(4)单链表的插入babax∧anaia1a2ppai-1xLs∧anaia1a2pai-1LInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/

s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)单链表的插入∧anaia1a2ai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的结点之后插入新的结点*/SLNODE*s;/*定义指向结点类型的指针*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新结点*/s->data=x;s->next=p->next;

p->next=s;returnOK;}(4)单链表的插入ps思考：如何在p所指向的结点之前插入新的结点？(5)单链表的删除思想方法

删除运算是将表的第i个结点（ai）删去。

具体步骤：（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前驱结点ai-1的指针域中）（2）令ai-1的指针域(p-＞next)指向ai的直接后继结点（即把ai从链上摘下）（3）释放结点ai的空间。单链表的删除删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；//删除b结点，彻底释放在链表中删除某元素的示意图如下：cabpp->next(p->next)->next××DelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;

if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}q(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}(5)单链表的删除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/

p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}

(5)单链表的删除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/

free(q);}/*删除并释放结点*/}(5)单链表的删除intDelete_LinkList(SLNODE*HEAD,inti){SLNODE*q,*p;int j=0;q=HEAD;while(q->next!=NULL&&j<i-1){q=q->next;j++;} //使p指向第i-1个结点if((j!=i-1)||(q->next==NULL))return0; //第i个结点不存在，不能删除else{ p=q->next; q->next=p->next; //修改指向关系free(p); //释放被删除结点空间return1;}}ai-1a1aiai+1Lq(5)单链表的删除:删除第i个结点p背景：对于单链表而言，若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，即找后继的时间性能是O(1)，找前驱的时间性能是O(n)。问题：如何使得找前驱的时间性能达到O(1)？付出空间的代价：每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。双向链表:

在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双链表一般也是由头指针唯一确定的，增加头结点也能使双链表上的某些运算变得方便。

2.双向链表双向链表在非线性结构（如树结构）中将大量使用。2.

双向链表这种指针域包括指向该结点的直接前驱和直接后继的两个指针的存储结构－双向链表此结点结构的C语言描述为：typedefstructnode{elemtypedata;structnode*prior,*next;}DLNODEpriordatanext指向前驱结点的指针域数据域指向后继结点的指针域双向链表的逻辑示意图：ˆ

双向链表结构的对称性若P是指向表中某一结点的指针则有：(P->next)->prior=p(P->prior)->next=p即结点*p的存储位置既存放在其前驱结点*(p->prior)的直接后继指针域中，也存放在它的后继结点*(p->next)的直接前驱指针域中。ana1a2ˆhintDlinkIns(DLNODE*L,DLNODE*P,ElemTypex)如何在P指向结点之前插入新的结点SL123PSx

S->prior=P->prior;

P->prior->next=S;

S->next=P;

P->prior=S;双向链表的前插运算关键步骤∧∧注意：步骤

必须在步骤

和

后面，即确保指针域P->prior使用完之后，再赋新的值。L123intDlinkDel(DLNODE*L,DLNODE*P)//删除指定结点PPP->next->prior=P->prior;P->prior->next=P->next；Free(P)注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。双向链表的删除操作讨论：链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结点即可(P->next=head;)。这种形成环路的链表称为循环链表。特别：带头结点的空循环链表样式H

特点：

1、从任一结点出发均可找到表中其他结点。

2、操作仅有一点与单链表不同：循环条件单链表-----p=NULL或p->next=NULL

循环链表-----p=head或p->next=head3.循环链表单向循环链表双向循环链表hha1a2an……hhana1a2单向循环链表最后一个结点的指针指向第一个结点；用尾指针命名，则

a1:r->next->nextan:r常作为队列的存储结构a1a2an……hr2.1.4顺序表与链表的比较（讨论题形式小结）线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。问1：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？答：

顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。问2：顺序存储和链式存储各有哪些优缺点？顺序存储的三个优点：

(1)方法简单，容易实现，没有使用指针。

(2)不用为表示结点间的逻辑关系而增加额外的存储开销。

(3)顺序表具有按元素序号随机访问的特点（时间复杂度O(1)）。顺序存储的两个缺点：

(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低（时间复杂度O(n)）。

(2)需要预先分配足够大的存储空间（估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出）。链表的优缺点恰好与顺序表相反。

答：问2：顺序存储和链式存储各有哪些优缺点？链表优点：

(1)无需事先了解线性表的长度，允许线性表的长度动态变化(2)能够适应经常插入删除内部元素的情况（时间复杂度O(1)）。链表的缺点：

(1)需要使用指针。

(2)每个元素都有结构性存储开销

(3)按元素序号访问不方便（时间复杂度O(n)）。问3：在什么情况下用顺序表比链表好？顺序表适宜于存储静态数据，如进行查找(按序号访问)这样的操作；链表宜于存储动态数据，进行插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。答：作业：链表作业：习题22.1,2.2,2.5(2)Ch2线性结构

2.2栈和队列

2.2.1栈

1栈的定义及基本运算

2栈的存储结构和运算实现

3栈的应用

2.2.2队列

1队列的定义及基本运算

2队列的存储结构和运算实现

3队列应用举例

操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行

2.2.1栈（stack）

1栈的定义及基本运算定义：栈是限定在表的一端进行插入和删除运算的线性表。允许插入和删除的一端称为栈顶(top），另一端称为栈底（bottom）。如给定栈s＝（a1，a2，…，an），栈中元素按a1，a2，…，an的顺序进栈，则称a1是栈底元素，an是栈顶元素。后进先出（LIFO）表

栈的基本运算(1)栈初始化：Init_Stack()初始条件：栈不存在。操作结果：构造一个空栈(不含任何元素）。(2)判栈空：IsEmpty_Stack(s)/EMPTY(S)初始条件：栈s已存在。操作结果：若s为空栈返回为1(T)，否则返回为0(F)。(3)入栈：Push_Stack(s，x)初始条件：栈s已存在。操作结果：在栈s顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。

栈的基本运算(4)出栈：Pop_Stack(s)初始条件：栈s存在且非空。操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。(5)读栈顶元素：GetTop_Stack(s)初始条件：栈s存在且非空。操作结果：栈顶元素作为结果返回，栈不变化。

仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶;表头(即a1端)称为栈底。例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！栈：2栈的存储结构和运算实现存储结构： 用顺序栈或链栈存储均可，但以顺序栈更常见。逻辑结构： 与线性表相同，仍为一对一关系。运算规则： 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。实现方式：关键是编写入栈和出栈函数，具体实现因顺序栈或链栈的不同而不同。Q1：堆栈是什么？它与一般线性表有什么不同？

堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取/删减运算规则：后进先出“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)1）顺序栈栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。栈底位置是固定不变的，可以将栈底位置设置在数组的两端的任何一个端点。栈顶位置是随着进栈和退栈操作而变化。需用一个整型变量top来指示当前栈顶的位置(通常称top为栈顶指针)。顺序栈的类型定义只需将顺序表的类型定义中的长度cnt改为top即可。1）顺序栈利用一组地址连续的存储单元依次存放从栈底到栈顶的若干数据元素。(1)定义：

#defineMaxSize1024typedefstructstack{ElemTypedata[MaxSize];

/*用一维数组存放自栈底到栈顶的数据元素*/inttop;

/*附设一个位置变量top*/}SeqStack;

设S是SeqStack类型的指针变量。若栈底位置在数组低端，即s–>data[0]是栈底元素.那么：进栈：出栈：空栈：栈满：上溢：下溢：1）顺序栈s–>top加1；s–>top减1；s–>top=-1；s–>top=MaxSize-1。当栈满时再做进栈运算必定产生的空间溢出;当栈空时再做出栈运算产生的溢出。设数组S是一个顺序栈栈S的最大容量MaxSize=4，初始状态top=－1

10S[4]2310basetop=top+1S[top]=xtop

10

25

30S[4]2310topbase*x=S[top]top=top-1栈空10进栈30出栈S[4]2310top=-1top栈满top=MaxSize-1

10

25

30

40S[4]2310top=3basetop1）顺序栈(2)初始化SeqStack*Init_SeqStack(){ SeqStack*s; s=(SeqStack*)malloc(sizeof(SeqStack));

s->top=-1; returns;};#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return0;S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入栈操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);

S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入栈操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);S->top++;

S->data[S->top]=x;return(1);}a2a3a4987654321a10topx（3）入栈操作

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{*x=S->data[S->top];/*返回出栈元素*/S->top--;return(1);}

}通过指针变量x，带回出栈元素a2a3a4987654321a10top（4）出栈操作a2a3a4987654321a10top*x

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{

*x=S->data[S->top];/*返回出栈元素*/

S->top--;return(1);}

}（4）出栈操作（5）取栈顶元素elemtypeGetTop(SeqStack*s){ if(s->top<0) return0；//栈空

elsereturn(s->data[s->top]);}顺序栈的共享为两个栈申请一个共享的一维数组空间S[M]将两个栈的栈底分别放在一维数组的两端，分别是0，M－1a1a2a3b5b4b3b2b10M－1top1top2a1a2a3

0M－1top共享栈的结构定义a1a2a3b5b4b3b2b10M－1top1top2#defineM100typedefstructstack{ElemTypedata[M];inttop1,top2;}SharedStack;共享栈的操作a1a2a3b5b4b3b2b10M－1top1top2判空：判满：

top1==-1&&top2==M;top1+1==top2;共享栈的初始化SharedStack*InitSharedStack(){ SharedStack*s; s=(SharedStack*)malloc(sizeof(SharedStack)); s->top1=-1; s->top2=M; returns;}共享栈的进栈操作intPush(SharedStack*S,ElemTypex,inti){ if(S->top[0]+1==S->top[1])return(0); switch(i)//i=1或2，表示堆栈号

{ case1:

S->top1++; S->data[S->top1]=x;break;

case2: S->top2--; S->data[S->top2]=x;break; default: return(0);} return(1);}共享栈的出栈操作intPop(SharedStack*S,ElemType*x,inti){switch(i){ case1: if(S->top1==-1)return(0); *x=S->data[S->top1]; S->top1--;break;

case2: if(S->top