线性表（福建教师招考信息技术算法和程序部分）课件

第二章线形表第二章线形表11、线性表(LinearList)：定义：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。记作：L=(a1，a2，…ai-1，ai，ai+1，…an)其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）1、线性表(LinearList)：定义：2例3、学生健康情况登记表如下：例4、一副扑克的点数（2，3，4，…，J，Q，K，A）姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例3、学生健康情况登记表如下：姓名学号性3线性表——元素及元素之间的关系为线性线性：（1）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节点）（2）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）（3）除首节点，其余节点有且仅有一个前趋k1k2k3k4k1k2k3（4）除尾节点，其余节点有且仅有一个后继数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。线性表——元素及元素之间的关系为线性（1）有且仅有一个开始4线性表的类型定义抽象数据类型线性表的定义

ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

{初始化} InitList(&L) 操作结果：构造一个空的线性表L。

{结构销毁} DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。

{引用型操作} ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则FALSE。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中元素个数。线性表的类型定义抽象数据类型线性表的定义ADTList5ADTList

GetElem(L,i,&e) 初始条件：线性表L已存在，1≤i≤LengthList(L) 操作结果：用e返回L中第i个元素的值。 LocateElem(L,e,compare()) 初始条件：线性表L已存在，compare()是元素判定函数。 操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。 PriorElem(L,cur_e,&pre_e) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。 NextElem(L,cur_e,&next_e) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继， 否则操作失败，next_e无定义。 ListTraverse(L,visit()) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ADTList GetElem(L,i,&e)6ADTList {加工型操作} ClearList(&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 PutElem(L,i,&e) 初始条件：线性表L已存在，1≤i≤LengthList(L) 操作结果：L中第i个元素赋值同e的值。 ListInsert(&L,i,e) 初始条件：线性表L已存在，1≤i≤LengthList(L)+1 操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。 ListDelete(&L,i,&e) 初始条件：线性表L已存在且非空，1≤i≤LengthList(L) 操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTListADTList {加工型操作}7举例假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下：ListLength(L)//所得结果为5GetElem(L,i,&e)//所得结果为89PriorElem(L,x,&pre_e)//所得结果为23NextElem(L,x,&next_e) //所得结果为89LocateElem(L,x,equal) //所得结果为2ListInsert(&L,i,y)//所得结果为(23,56,88,89,76,18)ListDelete(&L,i+1,&e) /所得结果为(23,56,88,76,18)89举例假设线性表L=(23,56,89,76,18),8如何实现线性表的其它操作例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。设计思想： 扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。分下列三步进行：1．从线性表LB中依次取得每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。如何实现线性表的其它操作例2-1利用两个线性表LA9A=A∪B算法描述：//将所有在线性表Lb中但不在La中的数据元素插入到La中voidUnion(List&La，ListLb){ //求线性表的长度La-len=ListLength(La);Lb-len=ListLength(Lb);for(i=1;i<=Lb-len;i++){

//取Lb中第i个数据元素赋给e GetElem(Lb，i，e);

//La中不存在和e相同的数据元素，则插入之 if(!LocateElem(La，e，equal)) ListInsert(La，++La-en，e); }}//UnionA=A∪B算法描述：10A=A∪B时间复杂度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；循环体内的Locate操作平均需ListLength(La)次 最坏情况为：ListLength(La)总的时间复杂度： O[ListLength(Lb)*ListLength(La)]A=A∪B时间复杂度分析：11例2-1-2已知一个非纯集合B，试构造集合A，要求集合A中只包含集合B中所有值不相同的数据元素。设计思想：解法一： 同上例，分别以线性表LA和LB表示集合A和B，则首先初 始化线性表LA为空表，之后的操作和例2-1完全相同。解法二： 仍以线性表表示集合。只是求解之前先对线性表LB中的 数据元素进行排序，即线性表LB中的数据元素依其值从 小到大有序排列，则值相同的数据元素必相邻。则上述 操作中的第二步就不需要进行从头至尾的查询。

例2-1-2已知一个非纯集合B，试构造集合A，要求集合A12A=Bvoidpurge(List&La,ListLb){//已知线性表Lb中的数据元素依值非递减有序排列，现构造线性表La，//使La中只包含Lb中所有值不相同的数据元素 InitList（La）；//初始化La为空表 La_len=ListLength(La); Lb_len=ListLength(Lb);//求线性表的长度 for(i=1;i<=Lb_len;i++) { GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e if(ListEmpty(La)||!equal(en，e)) ListInsert(La,++La_len,e); //La中不存在和e相同的数据元素，则插入之 en=e;//en，La中的已插入元素 }//for}//purgeA=Bvoidpurge(List&La,List13A=B时间复杂度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；解法一: 循环体内的Locate操作平均需ListLength(Lb)次 故时间复杂度为：O(ListLength2(LB))；

解法二的时间复杂度： 循环体内的基本操作与表长无关 故时间复杂度为： O(ListLength(Lb))A=B时间复杂度分析：14C=A∪B例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。设计思想：1、LC为空表，用来存放LA和LB的元素2、表LA和LB的元素逐一进行比较取小者放入表LC中3、插入表LA或表LB中剩余的元素C=A∪B例2-2巳知线性表LA和线性表LB中的15算法描述：//已知线性表La和Lb中的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。

voidMergeList(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)) { //La和Lb均非空 GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<=bj) { ListInsert(Lc,++k,ai); ++i; } else { ListInsert(Lc,++k,bj); ++j; } }算法描述：//已知线性表La和Lb中的元素按值非递减排列16C=A∪B

while

(i<=La_len) { GetElem(La,i++,ai); ListInsert(Lc,++k,ai); }

while(j<=Lb_len) { GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj); }}//MergeListC=A∪B while(i<=La_len17C=A∪B时间复杂度分析：该算法中包含了三个WHILE语句，其中，第一个处理了某一张表的全部元素和另一张表的部分元素；后两个WHILE循环只可能有一个执行，用来完成将未归并到LC中的余下部分元素插入到LC中。“插入”是估量归并算法时间复杂度的基本操作，其语句频度为：

LENGTH（LA）+LENGTH（LB）该算法的时间复杂度为：

O（LENGTH（LA）+LENGTH（LB））若LA和LB的元素个数为同数量级n，则该算法的时间复杂度为: O(n)C=A∪B时间复杂度分析：18线性表的顺序表示和实现一、线性表的顺序存储结构顺序表：——线性表的顺序存储结构把线性表的结点按逻辑顺序（顺序）依次存放在一组地址连续的存储单元里。1、线性表的地址计算： 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置（首地址）。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：

LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i-1)*l线性表的顺序表示和实现一、线性表的顺序存储结构19存储示意：存储示意：20线性表的顺序存储用数组实现线性表（顺序存储、顺序表）线性表元素：a1、a2、a3、a4....数组元素：a[0]、a[1]、a[2]、a[3]线性关系：a1a2a3a4数组下标大小注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[i-1]。线性表的顺序存储用数组实现线性表（顺序存储、顺序表）线性关系21ElemType*getElem(intpos);//若1<=pos<=cursize,则返回指示第pos个元素//的位置;否则返回NULL

intLocation(ElemType&e);//返回其值和e所指元素值相同的数据元素在线性//表中的序号，若不存在这样的数据元素，则返回0

//modification

voidclearList(void);StatusputElem(intpos,constElemType&e);//若1<=pos<=cursize,则修改线性表中第pos个数//据元素的值，并且返回OK;否则不进行修改并返//回ERRORStatusInsert(intpos,constElemType&e);//若1<=pos<=cursize+1,则插入元素e在线性表//中第pos个数据元素之前，并且返回OK;否则不//进行插入并返回ERRORStatus*Delete(intpos,ElemType&e);//若1<=pos<=cursize,则删除并返回指示第pos//个数据元素的位置，否则返回NULL}

classSqList{

private

constMAXLISTSIZE=100

protectedElemType*elemPtr;

intcursize;

public//constructorSqList(intsize=MAXLISTSIZE);//destructor~SqList(){delete[]elemPtr;}

//accessmethod

intEmpty(void)const;{return(cursize==0)}

intLength(void)const;{returncursize}使用C++进行定义线性表的顺序存储：ElemType*getElem(intpos);cl22线性表的顺序表示和实现2、动态存储：分配策略：预分配一段空间，固定长度设定增量当线性表空间满，则按增量增加空间，动态调整3、数据类型：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefstruc{ ElemType*elem; intlength; intlistsize;}SqList;使用数组来描述线性表的顺序表示和实现2、动态存储：使用数组来描述23二、基本操作的实现：1、初始化——IniList_Sq(SqList&L见P23算法2.32、插入操作：ListInset(L,i,e)3、删除操作：deleteList(Sqlist*L，inti)二、基本操作的实现：24构造函数（初始化）SqList::SqList(intsize){

//构造一个空的顺序表size=(size>MAXLISTSIZE)?MAXLISTSIZE:size;elemPtr=newElemType[size];cursize=0;}构造函数（初始化）SqList::SqList(int25插入示意：插入示意：26插入运算插入运算问题描述以a1开始的线性表中在第i个元素前插入一个新元素new_node。a1a2ai-1aian……a1a2ai-1newnodeai+1ai……anai+1插入运算插入运算a1a2ai-1aian……a1a2ai-127插入运算从ai开始向后移动从an开始向前每个元素向后移一格a1a2ai-1aiai+1......anaiaiaiaia1a2ai-1aiai+1…anan…ai+1aifor(j=i;j<L.length;j++){L.elem[j+1]=L.elem[j];}for(j=L.length;j>i;j--){L.elem[j+1]=L.elem[j];}newnode插入运算从ai开始向后移动a1a2ai-1aiai+1...28算法思想：①进行合法性检查，1<=i<=n+1；②利用线性表是否已满；③将第n个至第i个元素逐一后移一个单元；④在第i个位置处插入新元素；⑤将表的长度加1。算法思想：29StatusListInsert_Sq(Sqlist&L，inti，ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e//i的合法值为1≤i≤ListLength_Sq(L)+1if(i<1||i>L.length+1) returnERROR;//i值不合法 if(L.length>=L.ListSize) exit(overflow);for(i=L.length-1;i>=I-1;i--)L.elem[i+1]=L.elem[i];L.elem[I-1]=x;l.length++;}StatusListInsert_Sq(Sqlist30删除示意：删除示意：31anai删除运算删除运算问题描述：删除第i个元素算法实现分析a1a2ai…anai－1a1a2ai－1ai+1…ananai+1anai删除运算删除运算a1a2ai…anai－1a1a2a32删除运算算法实现分析从an开始向前逐个元素向前移动从ai＋1开始向后逐个元素向前移动a1a2ai+1ai…anai-1anananfor(i=L.length-1;i>i;i--){L.elem[i-1]=L.elem[i];}a1a2ai-1aiai+1…anfor(i=i;i<L.length-1;i++){L.elem[i]=L.elem[i+1];}删除运算算法实现分析a1a2ai+1ai…anai-1ana33算法思想：①进行合法性检查，i是否满足1<=i<=n；②判线性表是否已空，v.last=0；③将第i+1至第n个元素逐一向前移一个位置；④将表的长度减1。算法思想：34StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//被删除元素之后的元素左移--L.length;//表长减1returnOK;算法时间复杂度为:

O(ListLength(L))p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//删除位置不合法元素左移StatusListDelete_Sqfor(++p;35考虑移动元素的平均情况:假设删除第

i个元素的概率为,

则在长度为n

的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：考虑移动元素的平均情况:假设删除第i个元素的概率36p2118307542568721183075L.length-10ppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)pp211830754256872137

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem_Sq

O(ListLength(L))算法的时间复杂度为：i=1;//i的初值为第1元素的位序p=L.elem;

//p的初值为第1元素的存储位置while

(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;(*compare)(*p++,e)利用顺序表类实现线性表的其它操作intLocateElem_Sq(SqListL,E38例如：顺序表23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可见，基本操作是，将顺序表中的元素逐个和给定值e相比较。例如：顺序表237541385439集合归并：#include<iostream.h>#includeSqList.hSqListmerge(Sqlist&a,SqList&b){ElemType*ai,*bj;

intm=a.Length();

intn=b.Length();SqListc(m+n);

inti=1;

intj=1;

intk=c.Length();

while((i<=m)&&(j<=n)){ai=a.getElem(i);bj=b.getElem(j);

switch(compare(*ai,*bj)){

case–1:

case0:c.Insert(++k,ai);i++;

break;

case1:c.Insert(++k,bj);j++;

break;

default:;}//switch}//while利用顺序表类实现线性表的其它操作集合归并：while((i<=m)&&(j<=n))40while(i<=m){ai=a.getElem(i++);c.Insert(++k,ai);}while(j<=n){bj=b.getElem(j++);c.Insert(++k,bj);}returnc;}//mergewhile(i<=m)41线性表的链式存储链接存储的线性表（链表）的定义1、链表的引入数组结构的缺点:（1）在插入、删除时要移动大量的结点（2）表的大小固定。 预先在申明数组时指定，无法更改原因：存放的连续性突破离散存放用指针来表示元素之间的关系。线性表的链式存储链接存储的线性表（链表）的定义42线性表的链式存储用链表实现线性表（非连续存储）线性表元素：a1、a2、a3、a4....链表链点线性关系：a1a2a3a4指针域，指针关系线性表的链式存储用链表实现线性表（非连续存储）线性表元素：a43链表的定义1链表的定义结点datalink元素域指针域元素域（数据元素域）：存放一个数据元素。指针域（关系域）：存放指向下一个元素的指针 ——元素间的关系。元素域+指针域=结点（链点）链表的定义1链表的定义datalink元素域指针域元素域（44

用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象)

+指针(指示后继元素存储位置)=

结点

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作链表一、单链表用一组地址任意的存储单元存放线性表中的数据元素。以45头指针以线性表中第一个数据元素

的存储地址作为线性表的地址，称作线性表的头指针头结点a1a2…...an^头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针空指针线性表为空表时，头结点的指针域为空头指针以线性表中第一个数据元素的存储地址作为线性46

TypedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域}LNode,*LinkList;

LinkListL；//L为单链表的头指针二、结点和单链表的描述TypedefstructLNode{Lin47classNode{protected:ElemTypedata;//数据域Node*next;//指针域public://constructorNode(constElemTypeitem,Node*ptr=NULL);

//destructor~Node(void){}//accessmethodNode*nextNode(void)const;{returnnext;}//返回结点的后继ElemType*info(void)const;{returndata;}//返回结点数据域的值//modificationmethodvoidinsertAfter(Node*p);//插入后继结点Node*deleteAfter(void);//删除并返回后继结点};

//Node类的实现Node::Node(constElemTypeitem,Node*ptr=NULL){data=item;next=ptr;}voidNode::insertAfter(Node*p){//插入后继结点

p>next=next;next=p;}Node*Node::deleteAfter(void){//删除并返回后继结点

Node*s=next;next=s>next;

returns;}classNode{//Node类的实现48L线性表的操作

GetElem(L,i,&e)在单链表中的实现:211830754256∧pppj123L线性表的操作211830754256∧ppp49

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i

单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。令指针p始终指向线性表中第j个数据元素因此，查找第i个数据元素的基本操作为：移动指针，比较50

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;++j;}//

顺指针向后查找，直到p指向第i个元素

//或p为空if(!p||j>i)

returnERROR;//第i个元素不存在e=p->data;//取得第i个元素returnOK;StatusGetElem_L(LinkListL,51ai-1

线性表的操作

ListInsert(&L,i,e)

在单链表中的实现：

有序对<ai-1,ai>改变为<ai-1,e>和<e,ai>eaiai-1ai-1线性表的操作ListInsert(&L,i,52因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。因此，在单链表中第i个结点之前进行插入的基本操作53StatusListInsert_L(LinkListL,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

returnERROR;//

i大于表长或者小于1StatusListInsert_L(LinkList54s=newLNode;

//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sps=newLNode;eai-1aiai-1sp55线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>ai-1aiai+1ai-1线性表的操作ListDelete(&L,i,&e)在链56

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq在单链表中删除第i个结点的基本操作为:找到线性表中57StatusListDelete_L(LinkListL,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理q=p->next;p->next=q->next;

//删除并释放结点e=q->data;free(q);returnOK;StatusListDelete_L(LinkList58操作ClearList(&L)在链表中的实现:voidClearList(&L){//将单链表重新置为一个空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListfree(p);算法时间复杂度：O(ListLength(L))操作ClearList(&L)在链表中的实现:void59如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配60例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：1、建立一个“空表”；2、输入数据元素an，建立结点并插入；3、输入数据元素an-1，建立结点并插入；ananan-14、依次类推，直至输入a1为止。如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如：操作步骤：1、建立一个“空表”；2、输入数据元素an，61voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入}voidCreateList_L(LinkList&L,62回顾2.1节中三个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？回顾2.1节中三个例子的算法，看一下当线性表分别以顺序存63voidunion(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}//union控制结构：基本操作：for循环GetElem,LocateElem和ListInsert当以顺序映像实现抽象数据类型线性表时为:

O(ListLength(La)×ListLength(Lb))

当以链式映像实现抽象数据类型线性表时为:

O(ListLength(La)×ListLength(Lb))例2-1算法时间复杂度

voidunion(List&La,ListLb)64voidpurge(List&La,ListLb){

InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);

if(ListEmpty(La)||

!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

}//for}//purge控制结构：基本操作：for循环GetElem和ListInsert当以顺序映像实现抽象数据类型线性表时为:

O(ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:

O(ListLength2(Lb))例2-2算法时间复杂度voidpurge(List&La,ListLb)65voidMergeList(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;}

}……控制结构：基本操作：三个并列的while循环GetElem,ListInsert当以顺序映像实现抽象数据类型线性表时为:

O(ListLength(La)+ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:

O(ListLength2(La)+ListLength2(Lb))例2-3算法时间复杂度voidMergeList(ListLa,ListL66用上述定义的单链表实现线性表的操作时，存在的问题：

改进链表的设置：1．单链表的表长是一个隐含的值；

1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．在单链表的最后一个元素之后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2．将基本操作中的“位序i”改变为“指针p”。用上述定义的单链表实现线性表的操作时，改进链表的设置：167四、一个带头结点的线性链表类型typedefstructLNode{//结点类型ElemTypedata;

structLNode*next;}*Link,*Position;StatusMakeNode(Link&p,ElemTypee);

//分配由p指向的值为e的结点，并返回OK；//若分配失败，则返回ERRORvoidFreeNode(Link&p);

//

释放p所指结点四、一个带头结点的线性链表类型typedefstruct68typedefstruct

{//链表类型

Linkhead,tail;

//分别指向头结点和

//最后一个结点的指针

intlen;

//指示链表长度

Linkcurrent;

//指向当前被访问的结点//的指针，初始位置指向头结点}LinkList;typedefstruct{//链表类型69链表的基本操作:{结构初始化和销毁结构}StatusInitList(LinkList&L);

//构造一个空的线性链表L，其头指针、

//

尾指针和当前指针均指向头结点，

//

表长为零。StatusDestroyList(LinkList&L);

//销毁线性链表L，L不再存在。O(1)O(n)链表的基本操作:{结构初始化和销毁结构}StatusIni70{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//

求表长StatusPrior(LinkListL);

//改变当前指针指向其前驱StatusNext(LinkListL);

//改变当前指针指向其后继ElemTypeGetCurElem(LinkListL);

//返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1){引用型操作}StatusListEmpty(Link71

StatusLocatePos(LinkListL,inti);

//改变当前指针指向第i个结点StatusLocateElem(LinkListL,ElemTypee,

Status(*compare)(ElemType,ElemType));

//若存在与e满足函数compare()判定关系的元

//素，则移动当前指针指向第1个满足条件的

//元素的前驱，并返回OK;否则返回ERRORStatusListTraverse(LinkListL,Status(*visit)());

//

依次对L的每个元素调用函数visit()O(n)O(n)O(n)StatusLocatePos(LinkListL72

{加工型操作}StatusClearList(LinkList&L);

//重置L为空表StatusSetCurElem(LinkList&L,ElemTypee);

//更新当前指针所指数据元素StatusAppend(LinkList&L,Links);

//在表尾结点之后链接一串结点StatusInsAfter(LinkList&L,Elemtypee);

//将元素e插入在当前指针之后StatusDelAfter(LinkList&L,ElemType&e);

//删除当前指针之后的结点

O(1)O(n)

O(s)

O(1)

O(1){加工型操作}StatusC73StatusInsAfter(LinkList&L,ElemTypee){

//若当前指针在链表中，则将数据元素e插入在线性链

//表L中当前指针所指结点之后,并返回OK;//否则返回ERROR。}//InsAfterif(!L.current)returnERROR;

if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;

if(L.tail=L.current)L.tail=s;L.current=s;returnOK;StatusInsAfter(LinkList&L,74StatusDelAfter(LinkList&L,ElemType&e){

//若当前指针及其后继在链表中，则删除线性链表L中当前//指针所指结点之后的结点，并返回OK;否则返回ERROR。}//DelAfterif(!(L.current&&L.current->next))

returnERROR;q=L.current->next;L.current->next=q->next;if(L.tail=q)L.tail=L.current;e=q->data;FreeNode(q);returnOK;StatusDelAfter(LinkList&L,75

例一StatusListInsert_L(LinkListL,inti,ElemTypee){

//在带头结点的单链线性表L的第i个元素之前插入元素e}//ListInsert_L

利用上述定义的线性链表如何完成线性表的其它操作？if(!LocatePos(L,i-1))returnERROR;

//i值不合法，第i-1个结点不存在if(InsAfter(L,e))returnOK;//完成插入else

returnERROR;例一利用上述定义的线性链表如何完成76StatusMergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，int(*compare)(ElemType,ElemType))){

//归并有序表La和Lb,生成新的有序表Lc,

//并在归并之后销毁La和Lb,

//compare为指定的元素大小判定函数……}//MergeList_L例二StatusMergeList_L(LinkList&L77if(!InitList(Lc))returnERROR;//存储空间分配失败while(!(a=MAXC&&b=MAXC)){

//La或Lb非空}……LocatePos(La,0);LocatePos(Lb,0);

//

当前指针指向头结点if(DelAfter(La,e))a=e;//取得La表中第一个元素aelsea=MAXC;//MAXC为常量最大值if(DelFirst(Lb,e))b=e;//取得Lb表中第一个元素belseb=MAXC;//a和b为两表中当前比较元素DestroyList(La);DestroyList(Lb);

//销毁链表La和LbreturnOK;if(!InitList(Lc))returnER78

if((*compare)(a,b)<=0){

//a≤bInsAfter(Lc,a);

if(DelAfter(La,e1))a=e1;

elsea=MAXC;}else{

//a＞bInsAfter(Lc,b);

if(DelAfter(Lb,e1))b=e1;

elseb=MAXC;

}if((*compare)(a,b)<=0){79

1.双向链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;五、其它形式的链表1.双向链表typedefstructDuLNod80最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。2.循环链表最后一个结点的指针域的指针又指回第一个结点的链表81双向循环链表空表非空表a1a2…...an双向循环链表空表非空表a1a282双向链表的操作特点：“查询”和单链表相同“插入”和“删除”时需要同时修改两个方向上的指针。双向链表的操作特点：“查询”和单链表相同“插入”和“删除83ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1aies->next=p->next;p84ai-1删除aiai+1p->next=p->next->next;p->next->prior=p;pai-1ai-1删除aiai+1p->next=p->next-85ADT

Ordered_List{

数据对象:

S={xi|xiOrderedSet，i=1,2,…,n,n≥0}集合中任意两个元素之间均可以进行比较数据关系:R={<xi-1,xi>|xi-1,xi

S,

xi-1≤xi,i=2,3,…,n}回顾例2-2的两个算法六、有序表类型ADTOrdered_List{集合中数据关系:R=86

基本操作：…………

LocateElem(L,e,&q,int(*compare)(ElemType,ElemType))初始条件：有序表L已存在。操作结果：若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回函数值FALSE。Compare是一个有序判定函数基本操作：……Locat87(12,23,34,45,56,67,78,89,98,45)例如:若e=45,则q指向

若e=88,则q指向表示值为88的元素应插入在该指针所指结点之后。(12,23,34,45,56,67,78,88voidunion(List&La,ListLb){//Lb为线性表

InitList(La);//构造(空的)线性表LA

La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之}}//union算法时间复杂度：O(n2)voidunion(List&La,ListLb)89voidpurge(List&La,ListLb){//Lb为有序表InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度

for(i=1;i<=Lb_len;i++){

}}//purge

GetElem(Lb,i,e);

//取Lb中第i个数据元素赋给eif

(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);

en=e;}

//La中不存在和e相同的数据元素，则插入之算法时间复杂度：O(n)voidpurge(List&La,ListLb)902.4一元多项式的表示2.4一元多项式的表示91在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)但是对于形如

S(x)=1+3x10000–2x20000的多项式，上述表示方法是否合适？一元多项式在计算机中，可以用一个线性表来表示:但是对于形如一元多项式92

一般情况下的一元稀疏多项式可写成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指数为ei

的项的非零系数，

0≤e1<e2<┄<em=n可以下列线性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）一般情况下的一元稀疏多项式可写成可以下列线性表表示：93

P999(x)=7x3-2x12-8x999例如:可用线性表

((7,3),(-2,12),(-8,999))表示P999(x)=7x3-2x12-8x999例94ADTPolynomial{

数据对象：

数据关系：抽象数据类型一元多项式的定义如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n且ai-1中的指数值＜ai中的指数值

}ADTPolynomial{抽象数据类型一元多项式的定义95

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)基本操作：操作结果：输入m项的系数和指数，建立一元多项式P。初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。