数据结构第二章线性表

第二章线性表

第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录数据结构课程的起点什么是线性结构？线性结构的定义若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。一对一(1:1)线性结构的逻辑类型线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现（重点）2.3线性表的链式表示和实现（重点）2.4应用举例（a1,a2,…ai-1，ai,ai＋1

，…,an）线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点2.1线性表的逻辑结构

（A,B,C,D,……,Z）分析：数据元素都是同类型（字母），元素间关系是线性的。例1分析26个英文字母组成的英文表是什么结构。例2分析学生情况登记表是什么结构。学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班：：：

：：分析：数据元素都是同类型（记录），元素之间关系是线性的。注意：同一线性表中的元素必定具有相同特性（数据类型）！1、“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列叙述的正误2、线性结构就是线性表×线性表的物理结构类型

线性表的物理结构类型

顺序存储结构与链式存储结构在确定线性表物理结构的基础上，可以进行相关的操作和编程，用函数实现。物理结构与逻辑结构区别逻辑结构是抽象的，独立于计算机的，无法进行具体的计算；物理结构是具体的，包括顺序结构与链式结构，决定了数据对象如何实现具体的运算。

例如数组与单链表就是两种不同的物理结构，在插入与删除操作时具体实现不一样2.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析2.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现注意：在C语言中数组的下标是从0开始，即：

V[n]的有效范围是从V[0]～V[n-1]顺序存储定义：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组a[n]的下标）。线性表顺序存储特点设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：

LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）对上述公式的解释如图所示线性表顺序存储特点a1a2……aiai+1……an

地址内容元素在表中的位序1i2n空闲区i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)LLOC(ai)=LOC(a1)+L*（i-1）线性表的顺序存储结构示意图设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的4个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是多少？110但此题要注意下标起点略有不同：LOC(M[3])=98+4×(4-1)=110解：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例1

charV[30];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;例2顺序表的操作用数组V来存放26个英文字母组成的线性表（a，b，c，…，z），写出在顺序结构上生成和显示该表的C语言程序。voidmain(void)

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

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

/*字母线性表的显示，即读表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",v[i]);printf("\n");}执行结果：abcdefghijklmnopqrstuvwxyz例2顺序表的操作2.2.2顺序表的实现（或操作）数据结构的基本运算：修改、插入、删除、查找、排序1)修改

通过数组的下标便可访问某个特定元素并修改之。核心语句:V[i]=x;显然，顺序表修改操作的时间效率是O(1)2)插入在线性表的第i个位置前插入一个元素实现步骤：将第n至第i

位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?

应当有1≤i≤n+1或i=[1,n+1]在线性表的第i个位置前插入一个元素for(j=n;j>=i;j--)a[j+1]=a[j];

a[i]=x;n++;//元素后移一个位置//插入x//表长加1核心语句2)插入在线性表的第i个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入25实现步骤：将第i+1

至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当有1≤i≤n或i=[1,n]删除线性表的第i个位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一个位置//表长减1核心语句：3)删除123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：2.2.3顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）

T(n)=O

(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.时间效率分析:2.2.3顺序表的运算效率分析思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。讨论1插入元素：若在长度为n的线性表的第i(i>=1)位前插入一个元素，则向后移动元素的次数f(n)为: f(n)=n–i+1推导：假定在每个元素位置上插入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种!2.2.3顺序表的运算效率分析讨论2删除元素同理可证：顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)

2.2.3顺序表的运算效率分析想一想：顺序表插入、删除算法的平均空间复杂度为多少？插入效率：删除效率：教材P25算法2.5也是对执行效率的推导：因为没有占用辅助空间！含义：对于顺序表，插入、删除操作平均需要移动一半元素(n/2)O(1)即插入、删除算法的平均时间复杂度为O(n)2.2.3顺序表的运算效率分析课堂讨论：1、顺序表的“宏观”算法该如何书写？———采用抽象数据类型来表示2、顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？———采用动态分配的一维数组1、抽象数据类型定义初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除线性表的定义（见教材P19）ADTList

{数据对象：D={ai

|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<ai–1,ai>|ai–1,ai∈D,i=2,…,n}基本操作：}

ADTList线性表的基本操作如何表示？（见教材P19）InitList(&L);//建空表，初始化DestoryList(&L);//撤销表，释放内存intLengthList(L);//求表中元素个数，即表长POSITIONLocateElem(L,ElemTypee，compare());PriorElem(L,cur_e,&pre_e);//求当前元素e的前驱NextElem(L,cur_e,&next_e);//求当前元素e的后继ListInsertBefore(&L,i,e);//把e插入到第i个元素之前ListDelete(&L,i,&e);//删除第i个元素并“看”此元素ListTraverse(L,Visit());//“看”表中全部元素（遍历）初始化、撤销、清空、判空；求表长、表头、表尾、前趋、后继；读元素、查找（含定位）、遍历；插入、删除顺序表操作的典型例子教材例2-1：求两个线性表的“并”，即：LAULB=?算法至少有两种：①LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA；②若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。2、动态数组先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量typedefstruct{ElemType*elem;//表基址(用指针*elem表示）

intlength;//表长度（表中有多少个元素）

intlistsize;//当前分配的表尺寸（字节单位）}SqList;注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（见教材P22）：为什么不用数组sizeof(x)算符的意思是：计算变量x的长度(字节数)malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。StatusInitList_Sq(SqList&L)

//创建一个空线性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem)exit(OVERFLOW);

//分配失败，结束程序

L.length=0;

//暂无元素放入，空表

L.listsize=LIST_INIT_SIZE;

//表尺寸=初始分配量

ReturnOK;}//InitList_Sq动态创建一个空顺序表的算法realloc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表中第i个位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//检验i值的合法性if(L.length≥L.listsize)//若表长超过表尺寸则要增加尺寸

{newbase=(ElemType*)realloc(L.elem,(L.listsize+

LISTINCREMENT)*sizeof(ElemType));if(newbase=NULL)exit(OVERFLOW);//分配失败则退出并报错

L.elem=newbase;//重置新基址

L.listsize=L.listsize+LISTINCREMENT;}//增加表尺寸q=&L.elem[i-1];//q为插入位置指针

for(p=&L.elem[L.length-1];p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素统统后移,p为元素位置*q=e;//插入e++L.length;//增加1个数据元素，则表长+1returnOK;}//ListInsert_Sq动态数组的核心是realloc(void*ptr,newsize)函数！for(intk=L.length-1;k>=i-1;k--)L.elem[k+1]=L.elem[k];动态顺序表的插入算法(续）StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序表L中删除第i个元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被删除元素的位置

e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//q是表尾的位置

for(++p;p<=q;p++)*(p-1)=*p;//待删元素后面的统统前移--L.length;//表长-1returnOK;}//ListDelete_Sq动态顺序表的删除算法链式存储结构2.2本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例2.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！2.3.1链表的表示让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率2.3.1链表的表示例：请画出26个英文字母表的链式存储结构。解：该字母表的逻辑结构为：（a,b,…,y,z）该字母表在内存中链式存放的样式举例如下：链表存放示意图如下：a1heada2/\an……指针域(链域)链表存放示意图如下：讨论1

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

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

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

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。(2)与链式存储有关的术语3）单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语4）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；通常头指针也是一个类似于结点的结构体头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。示意图如下：讨论1.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，编程更方便。答：答：讨论2.如何表示空表？无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！

一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31（3）举例例1：上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点头结点不计入链表长度！

线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例2：讨论:

链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？p*nextdatanode方式1：直接表示为

node.data＝'a'；node.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的地址附1：介绍C的三个有用的库函数/算符（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度（字节数）；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。sizeof(x)——计算x的长度malloc(m)—开m字节空间free(p)——删除一个变量问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pm＝sizeof(node)

//单位是字节p＝(node*)malloc(m)free(p)//只能借助node的指针删除！P->data=‘a’;p->next=q练习：①类型定义和变量说明可以合写为：typedefstruct

LinkList

//LinkList是自定义结构类型名称{chardata;//定义数据域的变量名及其类型

struct

LinkList*next;//定义指针域的变量名及其类型}node，*pointer;//node是LinkList结构类型的类型替代,*pointer是指针型的LinkList结构类型的替代，也是数据类型*/附2：补充结构数据类型的C表示法②对于指向结构类型的指针变量，可说明为：

node

*p,*q;

//或用

struct

LinkList

*p,*q;pointerp,q;//注：上面已经定义了node为用户自定义的LinkList类型。附2：补充结构数据类型的C表示法单链表的抽象数据类型描述如下（参见教材P28）：typedefstructLnode

{ElemTypedata;//数据域

structLnode*next;//指针域}Lnode,*LinkList;//*LinkList为Lnode类型的指针至此应可看懂教材P22关于顺序表动态分配的存储结构。其特点是：用结构类型和指针来表示顺序结构，更灵活。如何具体编程来建立和访问链表？——链表的实现typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;教材P28对于线性表的单链表存储结构描述:教材问题讨论：Q1：第一行的Lnode与最后一行的Lnode是不是一回事？A1：不是。前者Lnode是结构名，后者Lnode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;Q2：那为何两处要同名(Lnode和Lnode）？太不严谨了吧？A2：同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。Q3：结构体中间的那个struct

Lnode是何意？A3：在“缩写”

Lnode还没出现之前，只能用原始的structLnode来进行变量说明。此处说明了指针分量的数据类型是struct

Lnode。typedefstructstudent

{charname;intage;}student,*pointer;教材问题讨论：2.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析2.3.2链表的实现（1）单链表的建立和输出（2）单链表的修改（3）单链表的插入（4）单链表的删除（1）单链表的建立和输出例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。算法实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。先挖“坑”,后种“萝卜”！#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;node*p,*q,*head;//一般需要3个指针变量intn;//数据元素的个数intm=sizeof(node);/*结构类型定义好之后，每个变量的长度就固定了，m求一次即可*/将全局变量及函数提前说明：新手特别容易忘记！！{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i<26;i++)//因尾结点要特殊处理，故i≠26{p->data=i+‘a’-1;//第一个结点值为字符ap->next=(node*)malloc(m);//为后继结点“挖坑”！p=p->next；}//让指针变量P指向后一个结点p->data=i+‘a’-1;//最后一个元素要单独处理p->next=NULL;}//单链表尾结点的指针域要置空！voidbuild()//字母链表的生成。要一个个慢慢链入如何建立带头结点的单链表（1）创建单链表{p=head;while(p)//当指针不空时循环，仅限于无头结点的情况

{printf("%c",p->data);

p=p->next;

//让指针不断“顺藤摸瓜”

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

sum++;sum=0;voiddisplay()/*字母链表的输出*/（2）单链表元素值显示（2）单链表的修改(或读取）思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p->data=new_value。修改第i个数据元素的操作函数可写为：Status

GetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=1;//带头结点的链表while(p&&j<i){p=p->next;++j;}if(!p

||j>i)returnERROR;p->data=e;//若是读取则为：e=p->data;returnOK;}//

GetElem_L缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取。在链表中插入一个元素X的示意图如下：Xsabp链表插入的核心语句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和Step2能互换么？X结点的生成方式：s=(node*)malloc(m);s->data=X;s->next=?bap插入X（3）单链表的插入（重点）在链表中删除某元素b的示意图如下：cabp删除动作的核心语句（要借助辅助指针变量q）：q=p->next;//首先保存b的指针，靠它才能找到c；p->next=q->next;//将a、c两结点相连，淘汰b结点；free(q)；//彻底释放b结点空间p->next思考：省略free(q)语句行不行？(p->next)->next××q（4）单链表的删除2.3.3链表的运算效率分析（1）查找

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为

O(n)。时间效率分析（2）插入和删除

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为

O(1)。但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是O(n)。空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n个整型变量，空间复杂度为

O(n)。在n个结点的单链表中要删除已知结点*P，需找到它的，其时间复杂度为前驱结点的地址/指针O(n)练习：2.4应用举例算法要求：已知：线性表A和B，分别由单链表La和Lb存储，其中数据元素按值非递减有序排列（即已经有序）；要求：将A和B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表Lc存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后的C=（2,3,5,6,8,8,9,11，11）例1：两个链表的归并（教材P31例）重点是链表链表示意图：3511/\8

La2611/\8

Lb92365

Lc8头结点算法设计算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向La、Lb和Lc链表；比较：比较La和Lb表中结点数据的大小；插入：将La和Lb表中数据较小的结点插入新链表Lc。请注意链表的特点，仅改变指针便可实现数据的移动,即“数据不动，指针动”La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新链表当前结点。归并过程示意如下：Lc=LaPbPaPaPb算法设计typedefstructLnode{//结点类型Elemtype

data;

structLnode

*next;}*linkList;typedefstruct{

//链表类型

linkhead,

tail;//分别指向链表头尾结点

int

len;

//链表中元素个数（长度）}

link;一个带头结点的线性链表类型定义如下：

（用类C语言，见P37）：结点的结构表结构算法实现：

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知单链线性表La和Lb的元素按值非递减排列。归并为Lc后也按值非递减排列。free(Lb);//释放Lb的头结点}//MergeList_Lpc->next=pa?pa:pb;//插入非空表的剩余段while(pa&&pb)//将pa、pb结点按大小依次插入Lc中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next}}pa=La->next;pb=Lb->next;Lc=pc=La；//有头结点见P31算法2.12?是条件运算符（为真则取第1项，见P10条件赋值）注：Lc用的是La的头指针思考（举一反三）编程实践题1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，怎么修改？2、重复的数据元素不需要插入，怎么修改？{elseif(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}例2：一元多项式的计算

(参见教材P39–43)讨论：一元多项式的数学通式？用抽象数据类型如何描述它的定义？用C语言如何描述它的定义？如何编程实现两个一元多项式相加？但当多项式的次数很高且零系数项很多时，更适于用链表存储。1.一元多项式的数学通式？机内存储方式？一般用顺序存储——a0a1a2…am-2am-1链式存储am-1

em-1am-2

em-2…a0e0^或0.0-1…am-1

em-1

^a0e0通常设计两个数据域（系数项和指数项）和一个指针域头结点只存系数项（但零系数项也不能遗漏）coefexponlinkP2000(x)=1+3x1000+5x20002.如何编程实现两个一元多项式相加？3142810a^814－310106b^例：运算规则：两多项式中指数相同的项对应系数相加，若和不为0,则构成多项式c(=a+b)中的一项；a和b中所有指数不相同的项均应拷贝到c中。链表a：链表b：实现思路：依次比较Pa和Pb所指结点中的指数项，依Pa->expon=、<或>Pb->expon等情况，再决定是将两系数域的数值相加（并判其和是否为0），还是将较高指数项的结点插入到新表c中。3142810^aPa814-310106^bPb1114-3102810^cPc106+运算效率分析：(1) 系数相加 0加法次数min(m,n)

其中m和n分别表示表A和表B的结点数。(2) 指数比较

极端情况是表A和表B没有一项指数相同，比

较次数最多为m+n-1(3) 新结点的创建

极端情况是产生m+n

个新结点

合计时间复杂度为

O(m+n)续例2：一元多项式的计算

(参见教材P39–43)

后续内容3.用抽象数据类型如何定义一元多项式？（参见P40）ADTPolynomial{数据对象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,

且ai-1中的指数值<ai中的指数值,i=1,2,…,n}基本操作：线性链表若干公共基本操作的定义见教材P37（此处略）为本例定义的更多基本操作有：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一元多项式P。//建表DestroyPolyn(&P)//销毁也是P的一种变化初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。//释放表PrintPolyn(P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。//输出一元多项式表PolynLength(P)//项数=表长初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。//求表长，用函数值返回为本例定义的更多基本操作有：AddPolyn(&Pa,&Pb)

初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相加运算，即：Pa＝Pa＋Pb，

并销毁一元多项式Pb。//两表相加SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa＝Pa－Pb，并销毁一元多项式Pb。//两表相减}ADTPolynomialMultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa＝Pa×Pb，并销毁一元多项式Pb。//两表相乘为本例定义的更多基本操作有：4.用C语言如何具体描述它的定义？用标准C语言：

typedefstructpoly_node{intcoef;intexpon;poly_pointerlink;};typedefstructpoly_node*poly_pointer;poly_pointera,b,c;coefexponlink5.具体编程（用C语言）利用建表操作CreatPolyn(&P,m)分别建立链表a和链表b；详细内容参见教材P42下部描述。2.利用加操作AddPolyn(&Pa,&Pb)对链表a和链表b进行相加；详细内容参见教材P43描述。编程时请注意，在前面定义中已规定：初始条件：一元多项式Pa和Pb已存在。

操作结果：完成多项式相加运算，即：Pa＝Pa＋Pb，

并销毁一元多项式Pb。从教材程序中可“猜”出，例中的链表是按指数项升序排列的。ha=GetHead(Pa);hb=GetHead(Pb);//取二表头指针(指向头结点）qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);//指向二表首元/下一结点while(qa&&qb){//若二表均未到末尾，

a=GetCurElem(qa);//则比较两结点的数据域（注意a,b含有

b=GetCurElem(qb);//两个数据分量）switch(*cmp(a,b)){//

cmp(a,b)是用户自定义函数，见P42倒9行case-1://依a的指数值>=<b的指数值，分别返回-1,0,+1ha=qa;qa=NextPos(Pa,ha);break;

//a的指数值小则链接，说明是升序case0://若a的指数值等于b，则系数相加，但和为0时不要sum=a.coef+b.coef;If(sum!=0.0){SetCurElem(qa,sum);ha=qa;}教材第43页的算法2.23——多项式加法

else{DelFirst(ha,qa);FreeNode(qa);}//若系数为0，则两结点都删DelFirst(hb,qb);FreeNode(qb);//a<=b时都会删除b结点。qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);break;case1://若a的指数值>b，应先链接（前插）b（保持升序）DelFirst(hb,qb);InsFirst(ha,qb);//此二动作不要调换qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;//a表结点大，后移}//switch}//while//直到查完a表If(!ListEmpty(Pb))Append(Pa,qb);//若b表还不空，则剩表全部//链接到a表中；b表空时无需动作，因为此时a表已求和完毕。FreeNode(hb);//无论什么结局，最终b表都是要废掉的。}}//AddPolyn教材第43页的算法2.23——多项式加法分析：要想让an指向an-1,……a2指向a1，一般有两种算法：①替换法：扫描a1……an,

将每个ai的指针域指向ai-1。实际上是链栈的概念^a1heada2思路：后继变前驱思路：头部变尾部②插入法：扫描a1……an,

将每个ai插入到链表首部即可。例3：试用C或类C语言编写一个高效算法，将一循环单链表就地逆置。

p=head->next;//有头结点if(p!=head){q=p->next;p->next=head;p=q};//处理a1while(p!=head)//循环单链表{q=p->next//保存原后继

p->next=head->next;head->next=p;p=q;}//准备处理下一结点q=head;p=head->next;//有头结点while(p!=head)//循环单链表{r=p->next;p->next=q;//前驱变后继

q=p;p=r;}//准备处理下一结点head->next=q;//以an为首替换法的核心语句：插入法的核心语句：ai-1aiqai+1prheada1heada2pq请上机验证并分析效率！1、试用C或类C语言编写一个高效算法，将一不带头结点单链表就地逆置。

举一反三2、试用C或类C语言编写一个高效算法，将一带头结点单链表就地逆置。

3、试用C或类C语言编写一个高效算法，将一不带头结点循环单链表就地逆置。

2.5几种特殊链表静态链表双向链表循环链表问题：若某种高级语言没有指针类型，能否实现链式存储和运算？如何实现？答：能！虽然链表通常用动态级联方式存储，但也可以用一片连续空间（一维数组）实现链式存储，这种方式称为静态链表。具体实现方法：定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针。指示域也常称为“游标”2.5.1静态链表动态链表样式：静态链表样式：指针数据指针数据指针数据指示数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。2.5.1静态链表

静态单链表的类型定义如下：

#defineMAXSIZE1000//预分配最大的元素个数（连续空间

typedefstruct{ElemTypedata;//数据域

intcur;//指示域

}component,SLinkList[MAXSIZE];//这是一维结构型数组前例1：软考题：L={23，17，47，05，31}若此分量定义为指针型，属于动态链表（题目中是指针）；若此分量定义为整型（通常存放下标），则属于静态链表。Z47Y31V23X17U05100119104108116112前例2：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？——教材P32例题data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]

为一个静态链表；S[0].cur则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].cur

表示第k+1个结点(即k的直接后继)的位置。i头结点说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：S[7].cur=S[3].cur；Step2:将QIAN的游标换为新元素LIU的下标：S[3].cur=7Step1:将QIAN的游标值存入LIU的游标中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi头结点LIU677静态链表各种操作编程静态链表的各种操作建立、查找、插入、删除、修改等操作例6：在双向链表中如何实现插入和删除运算？单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，称为双向链表。其结点的结构为：priordatanexttypedefstructDuLNode{ElemTypedata;//数据域

stru