数据结构与算法-第2章线性表

数据结构与算法

《数据结构（C语言版）》第2章线性表

安财.管理科学与工程学.计算机.王准生邮箱：bbwhs@163.com2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示的实现第2章线性表线性结构的特点：在数据元素的非空有限集中，存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个之外，集合中的每个数据元素均只有一个前驱除最后一个之外，集合中的每个数据元素均只有一个后继2.1线性表的类型定义什么是线性表一个线性表是n个数据元素的有限序列。在稍复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下常把数据元素称为记录（Record）,含有大量记录的线性表又称文件（File）。若将线性表记为

（a1，．．．，ai-1，ai，ai+1，．．．，an）,则表中ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素

。n是线性表的长度，n≥0，n=0时称为空表。a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i是数据元素ai在线性表中的位序。抽象数据类型线性表的定义应用举例例2－1假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A＝A∪B。（集合中的成员即线性表中的元素）voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//分别求两个线性表的长度for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);//假如La中不存在和e相同的数据元素，则将e插入到La中}}//union例2－2已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，LC中的数据元素仍按值非递减有序排列。voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的数据元素按值非递减有序排列//归并La和Lb得到新的线性表LC，LC中的数据元素仍按值非递减排列。InitList(Lc);//初始化一个线性表Lci=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;}}while(i<=La_len){//当La仍为非空时GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){//当Lb仍为非空时GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList2.2线性表的顺序表示和实现线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构／顺序映象假设线性表的每个元素需占用l个存储单元，则线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l,式中LOC(a1)是线性表中的第一个数据元素a1的在存储位置，通常称做线性表的起始位置，或基地址。线性表的这种机内表示称作线性表的顺序存储结构或顺序映象，反之，称这种存储结构的线性表为顺序表。特点以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。只要确定了存储线性表的起始位置，线性表中任一个数据元素都可随机存取，所以，线性表的顺序存储结构是一种随机存取的存储结构。线性表的顺序存储结构的实现C语言的描述由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组描述。//――――线性表的动态顺序存储结构――――#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{Elemtype*elem;//存储空间基址，即线性表的基址intlength;//线性表的当前长度intlistsize;//顺序表当前分配的存储容量（以sizeof(ElemType)为单位）//插入空间不足时可再分配能存储LISTINCREMENT个数据元素的空间}SqList;初始化顺序表L的算法2.3StatusInitList_Sq(SqList&L){//构造一个空的线性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)

exit(OVERFLOW);//存储分配失败L.length=0;//空表长度应为0L.listsize=LIST_INIT_SIZE://初始的存储容量returnOK;}//InitList_Sq

注意：C语言中数组的下标从0开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。算法2.4：在第i个元素之前插入一个数据元素e。

StatusListInsert_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){//当前存储空间已满，应增加分配newbase＝（ElemType*）realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加了存储容量}q=&(L.elem[i–1]);//q为插入位置，C语言数组从0开始下标for(p=&(L.elem[L.length–1];p>=q;--p)*(p+1)=*p;//从最后一个元素开始直到第i个元素为止，所有元素依次后移*q=e;//插入元素e到第个i位置++L.length;//表长增1returnOK;}//ListInsert_sq算法2.5删除第i个元素StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序线性表L中删除第

i个元素,并用e返回其值//i的合法值为1≤i≤ListLength_Sq(L)if((i<1)||(i>L.length))returnERROR;//i值不合法p=&(L.elem[i–1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给

eq=L.elem+L.length–1;//表尾元素的位置for(++p;p<=q;++p)*(p–1)=*P;//从被删元素之后的下一个位置，元素依次左移，覆盖前一个――L.length;//表长减一returnOK;}//ListDelete_Sq对以上两个算法的时间复杂度的分析以上两个算法的时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。算法2.4假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为

假定概率相等，即pi=1/(n+1)，则上式可简化为若表长为n,则时间复杂度为O（n）

算法2.5分析假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为假定概率相等，即qi=1/n，则上式可简化为若表长为n,则时间复杂度为O（n）定位算法，即求线性表中元素e的位置2.6intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()(即相等)的元素的位序//若找到,则返回其在L中的位序,否则返回0i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while(i<=L.length&& !(*compare)(*P++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq两个非递减有序的线性表的合并算法2.7voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//已知顺序表La和Lb的元素按值非递减排列//归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列Pa=La.elem;Pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败pa_last=La..elem+La.length–1;pb_last=Lb..elem+Lb.length–1;while(pa<=pa_last&&pb<=pb_last){//归并if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}

//插入La的剩余元素while(pa<=pa_last)*pc++=*pa++;

//插入Lb的剩余元素while(pb<=pb_last)*pc++=*pb++;}//MergeList_Sq2.3线性表的链式表示的实现线性链表①链式存储结构的特点是用任意的一组存储单元（不连续）存储线性表的数据元素。②对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映象，称为结点。即结点包括两个域：数据域和指针域。

指针域中存储的信息称作指针或链。③N个结点的结成一个链表。即为线性表（a1,a2,．．．,an）的链式存储结构。逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，因此，这种存储结构为非顺序映象或链式映象。由于每个结点只包含一个指针域，故又称线性链表或单链表。④头指针指示链表中的第一个结点的存储位置。⑤头结点：在单链表的第一个结点之前附设的一个结点，其数据域可以不存储任何信息，也可以存储诸如线性表的长度等之类的附加信息，其指针域存储指向第一个结点的指针。定义描述//单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述//线性表的单链表存储结构typedefstructLnode{ElemTypedata;StructLnode*next;}LNode,*LinkList;函数GetElem在单链表中的实现，算法2.8StatusGetElem­_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针,当第i个元素存在//时，

其值赋给e并返回OK，否则返回ERRORp=L－＞next;j=1;

//初始化，p指向第一个结点，j为计数器while(p&&j<i){p=p－＞next;++j;}//顺着指针向后查找，直到p指向第

i个元素或p为空if(!p||j>i)returnERROR;e=p－＞data;returnOK;}//GetElem­_L单链表的插入StatusListInsert_L(LinkList&L,inti,ElemTypee){

//在带头结点的单链表L中第i个位置之前插入元素ep=L;j=0;while(p&&j<i－1){p=p－＞next;++j;}//寻找第i－1个结点if(!P||j>i－1)returnERROR;//插入位置i小于1或大于表长s=(LinkList)malloc(sizeof(Lnode));s－＞data=e;//生成新结点s－＞next=p－＞next;p－＞next=s;//插入到链表中P结点之后returnOK;}//ListInsert_Laiai+1ai-1eS②p－＞next=S

①S－＞next=p－＞nextPai+1^…a1…L插入位置StatusListDelete_L(LinkList&L,inti,ElemType&e){

//在带头结点的单链表L中删除第i个元素，并由e返回其值p=L;j=0;while(p－＞next&&j<i－1){p=p－＞next;++j;}//寻找第i个结点，并令p指向其前驱结点(第i-1个结点)if(!(p－＞next)||j>i－1)returnERROR;

//找不到欲删除的结点q=p－＞next;p－＞next=q－＞next;

//删除指针q所指向的第i个结点e=q－＞data;free(q);//用参数e保留q结点的值，并释放结点所占的空间returnOK;}//ListDelete_L单链表的删除②p－＞next=q－＞nextaiai+1ai-1P①q=p－＞nextqai+1^…a1…L欲删结点voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带头结点的单链线性表LL=(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;//插入到表头}}//CreateList_La2a1a3eP②

L－＞next=p;①p－＞next=L－＞next;头结点L单链表的创建头结点

^L初始情况(习题集17页2.19)已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。(习题集18页2.22)试以单链表为存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。(习题集19页2.31)假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。(习题集19页2.33)已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。。单链表习题归并两个非递减有序的单链表的算法2.12voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知单链表La和Lb的元素按值非递减有序排列//归并La和Lb得到新的单链表Lc，Lc的元素也按值非递减有序排列pa=La－＞next；

pb=Lb－＞next;Lc=pc=la;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa－＞data<=pb－＞data){pc－＞next=pa;pc=pa;pa=pa－＞next;}else{pc－＞next=pb;pc=pb;pb=pb－＞next;}}pc－＞next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}//MergeList_L静态链表―――借助一维数组来描述的线性链表简介其它类型的链表单向循环链表双向链表双向循环链表a1a2a3

^头结点首元结点第二个最后一个单向循环链表

双向链表/双向循环链表表中的结点有两个指针，其一指向直接前趋，另一指向其直接后继//线性表的双向循环链表存储结构typedefstructDuLNode{