專業(yè)課-數(shù)據(jù)結(jié)構(gòu)線性表

第2章線性表

2.1線性表的類型定義

2.2線性表的順序表示和實現(xiàn)

2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

2.4一元多項式的表示及相加2.1線性表的類型定義線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中，1）有且僅有一個開始結(jié)點；2）有且僅有一個終端結(jié)點；3）除第一個結(jié)點外，集合中的每個數(shù)據(jù)元素均有且只有一個前驅(qū)；4）除最后一個結(jié)點外，集合中的每個數(shù)據(jù)元素均有且只有一個后繼。線性序列：線性結(jié)構(gòu)中的所有結(jié)點按其關(guān)系可以排成一個序列，記為(a1,…,ai,ai+1,…an)2.1線性表的類型定義1.線性表

1）線性表是n(n≥0)個數(shù)據(jù)元素的有限序列。

2）線性表是一種最常用且最簡單的數(shù)據(jù)結(jié)構(gòu)。含有n個數(shù)據(jù)元素的線性表是一個數(shù)據(jù)結(jié)構(gòu)：

List=(D,R)

其中：D={ai|ai∈D0,i=1,2,…n,n≥0}R={N},N={<ai-1,ai>|ai-1,ai∈D0,i=2,3,…n}D0

為某個數(shù)據(jù)對象——數(shù)據(jù)的子集特性：均勻性，有序性（線性序列關(guān)系）2.1線性表的類型定義1.線性表

3）線性表的長度及空表線性表中數(shù)據(jù)元素的個數(shù)n（n≥0）定義為線性表的長度當(dāng)線性表的長度為0時，稱為空表。

ai是第i個數(shù)據(jù)元素，稱i為ai在線性表中的位序。2.線性表的基本操作p19～p201）InitList(&L)初始化，構(gòu)造一個空的線性表2）ListLength(L)求長度,返回線性表中數(shù)據(jù)元素個數(shù)3）GetElem(L,i,&e)取表L中第i個數(shù)據(jù)元素賦值給e4）LocateElem(L,e)按值查找，若表中存在一個或多個值為e的結(jié)點，返回第一個找到的數(shù)據(jù)元素的位序，否則返回一個特殊值。5）ListInsert(&L,i,e)在L中第i個位置前插入新的數(shù)據(jù)元素e，表長加1。6）ListDelete(&L,i,e)刪除表中第i個數(shù)據(jù)元素，e返回其值，表長減1。線性表的基本操作舉例例2-1求A=A∪BP20算法2.1時間復(fù)雜度：LocateElem()執(zhí)行次數(shù)O(ListLength(A)*ListLength(B))例2-2合并LA和LB到LC中

P20-21算法2.2時間復(fù)雜度：ListInsert()執(zhí)行次數(shù)O(ListLength(LA)+ListLength(LB))2.2線性表的順序表示和實現(xiàn)

1.順序表——線性表的順序存儲結(jié)構(gòu)1）在計算機(jī)內(nèi)存中用一組地址連續(xù)的存儲單元依次存儲線性表中的各個數(shù)據(jù)元素。2）假設(shè)線性表的每個元素需占用L個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的起始存儲位置，則線性表中第i+1個數(shù)據(jù)元素的存儲位置

Loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置Loc(ai)之間滿足下列關(guān)系：

Loc(ai+1)=Loc(ai)+L

一般來說，線性表的第i個元素ai的存儲位置為：

Loc(ai)=Loc(a1)+(i-1)*L

其中Loc(a1)是線性表的第一個數(shù)據(jù)元素a1的存儲位置，通常稱作線性表的起始位置或基地址。1.順序表—線性表的順序存儲結(jié)構(gòu)3）線性表的順序存儲結(jié)構(gòu)示意圖——p22圖2.2用“物理位置”相鄰來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。根據(jù)線性表的順序存儲結(jié)構(gòu)的特點，只要確定了存儲線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。#defineLIST_MAX_LENTH100/或者N/或者是一個常數(shù)typedefstructElemType{int*elem;intlength;}SqList;SqListL;2.順序存儲線性表的描述C語言中靜態(tài)分配描述p22求置空表StatusClearList(&L){L.length=0;returnOK;}2.順序存儲線性表的描述C語言中靜態(tài)分配描述p22求長度SatusListlength(SqListL){length=L.length;returnOK;}2.順序存儲線性表的描述C語言中靜態(tài)分配描述p22初始化StatusInitList_SqList(SqListL){L.elem=(*int)malloc(LIST_MAX_LENGTH*sizeof(int));if(!L.elem)exit(Overflow);L.length=0;returnOK;}2.順序存儲線性表的描述C語言中靜態(tài)分配描述p222.順序表的描述

1)C語言中動態(tài)分配描述p22#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;SqListL;說明：elem數(shù)組指針指向線性表的基地址；length指示線性表的當(dāng)前長度；listsize指示順序表當(dāng)前分配的存儲空間大小。當(dāng)空間不足時，再分配的存儲空間增量為LISTINCREMENT*sizeof(ElemType)2)幾個基本操作

①初始化p23算法2.3StatusInitList_SqList(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;}②插入p24算法2.4StatusListInsert_sq(SqList&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;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;}需將第n(即L.length)至第i個元素向后移動一個位置。注意：C語言中數(shù)組下標(biāo)從0開始，則表中第i個數(shù)據(jù)元素是L.elem[i-1]。②插入p24算法2.4函數(shù)realloc的格式及功能格式：void*realloc(void*p,unsignedsize)功能：將p所指向的已分配內(nèi)存區(qū)域的大小改為size。size可以比原來分配的空間大或小。②插入（續(xù)）q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}③刪除p24～p25算法2.5StatusListDelete_sq(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+length-1;//表尾

for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK}需將第i+1至第L.length個元素向前移動一個位置插入和刪除算法時間分析用“移動結(jié)點的次數(shù)”來衡量時間復(fù)雜度。與表長及插入位置有關(guān)。插入：最壞：i=1，移動次數(shù)為n最好:i=表長+1，移動次數(shù)為0平均：等概率情況下，平均移動次數(shù)n/2刪除：最壞：i=1，移動次數(shù)為n-1最好:i=表長，移動次數(shù)為0平均：等概率情況下，平均移動次數(shù)(n-1)/2查找p25～p26算法2.6intLocateElem_Sq(SqListL,ElemTypee){i=1;while(i<=L.length&&e!=L.elem[i-1])++i;if(i<=L.length)returni;elsereturn0;}查找的另一種描述i=1;p=L.elem;while(i<=L.length&&e!=*p++)++i;if(i<=L.length)returni;elsereturn0;合并P26算法2.7的另外一種描述

voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){inti=0,j=0,k=0;InitList_SqList(Lc);while(i<=La.length-1&&j<=Lb.length-1){if(La.elem[i]<=Lb.elem[j])Lc.elem[k++]=La.elem[i++]; elseLc.elem[k++]=Lb.elem[j++];}while(i<=La.length-1)Lc.elem[k++]=La.elem[i++];while(j<=Lb.length-1)Lc.elem[k++]=Lb.elem[j++];Lc.length=k;}合并P26算法2.7voidMergeList_Sq(SqListLa,SqListLb,SqList&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++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}建立#defineLIST_INIT_SIZE100StatusCreateList_Sq(SqList&L,intn){inti;

L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)exit(OVERFLOW);L.length=n;L.Listsize=LIST_INIT_SIZE;for(i=0;i<n;i++)scanf("%d“,&L.elem[i]);for(i=0;i<n;i++)printf(“%d,",L.elem[i]);printf("\n");}遞增插入StatusOrderInsert_Sq(SqList&La,ElemTypex){ inti=0;

if(La.length>=La.listsize)returnOVERFLOW; while(i<La.length&&La.elem[i]<x)i++; for(intj=La.length-1;j>=i;j--) La.elem[j+1]=La.elem[j]; La.elem[i]=x; La.length++; returnOK;}遞減插入StatusDeOrderInsert_Sq(SqList&La,ElemTypex){inti,j; if(La.length>=La.listsize)returnOVERFLOW; i=La.length-1; while(i>=0&&La.elem[i]<x)i--; for(j=La.length-1;j>i;j--) La.elem[j+1]=La.elem[j]; La.elem[i+1]=x; La.length++; returnOK;}4.順序表的分析1）優(yōu)點順序表的結(jié)構(gòu)簡單順序表的存儲效率高，是緊湊結(jié)構(gòu)順序表是一個隨機(jī)存儲結(jié)構(gòu)（直接存取結(jié)構(gòu)）2）缺點在順序表中進(jìn)行插入和刪除操作時，需要移動數(shù)據(jù)元素，算法效率較低。對長度變化較大的線性表，或者要預(yù)先分配較大空間或者要經(jīng)常擴(kuò)充線性表，給操作帶來不方便。原因：數(shù)組的靜態(tài)特性造成作業(yè)2.1編寫程序，建立并顯示一個有10個數(shù)據(jù)元素的順序線性表。2.2實現(xiàn)順序線性表的插入、查找、刪除等算法。順序表之整體概念：

elem01length-1listsizelength數(shù)組下標(biāo)

內(nèi)存狀態(tài)變量操作算法listsize-1初始化操作插入操作刪除操作查找操作排序操作......

.........空閑表區(qū)elem順序表之整體概念：順序表有下列缺點： （1）插入、刪除操作時需要移動大量元素， 效率較低； （2）最大表長難以估計，太大了浪費空間， 太小了容易溢出。因此，在插入和刪除操作是經(jīng)常性操作的應(yīng)用場合選用順序存儲結(jié)構(gòu)不太合適，此時可以選用鏈?zhǔn)酱鎯Y(jié)構(gòu)，數(shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點中的指針來指示。2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

1.線性鏈表特點：在內(nèi)存中用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素，用每個數(shù)據(jù)元素所帶的指針來確定其后繼元素的存儲位置。這兩部分信息組成數(shù)據(jù)元素的存儲映像，稱作結(jié)點。結(jié)點：數(shù)據(jù)域+指針域（鏈域）鏈?zhǔn)酱鎯Y(jié)構(gòu)：n個結(jié)點鏈接成一個鏈表線性鏈表（單鏈表）：鏈表的每個結(jié)點只包含一個指針域。datanext單鏈表(SinglyLinkedList)first頭指針last尾指針^指針為空單鏈表由頭指針唯一確定，因此常用頭指針的名字來命名。如表first.單鏈表的存儲映像1）線性鏈表的描述p28typedefstructLNode{ElemTypedata;StructLNode*next;}LNode,*LinkList;LinkListL;//L是LinkList類型的變量，表示單鏈表的頭指針2）術(shù)語頭指針：指向鏈表中第一個結(jié)點第一個數(shù)據(jù)元素結(jié)點（開始結(jié)點）頭結(jié)點：有時在單鏈表的第一個數(shù)據(jù)元素結(jié)點之前附設(shè)一個結(jié)點，稱之頭結(jié)點。說明：頭結(jié)點的next域指向鏈表中的第一個數(shù)據(jù)元素結(jié)點。對于頭結(jié)點數(shù)據(jù)域的處理：

a.加特殊信息

b.置空

c.如數(shù)據(jù)域為整型，則在該處存放鏈表長度信息。3）帶頭結(jié)點的單鏈表示意圖p28圖2.7由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以對鏈表第一個位置的操作同其他位置一樣，無須特殊處理。無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針，因此對空表與非空表的處理也就統(tǒng)一了，簡化了鏈表操作的實現(xiàn)。非空表 空表2.基本操作1）取元素p29算法2.82）插入元素p30算法2.93）刪除元素p30算法2.104）建立鏈表p30～p31算法2.115）有序鏈表的合并p31算法2.126）查找（按值查找）7）求長度8）集合的并運算取元素（按序號查找）p29算法2.8

從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直至找到第i個結(jié)點為止（j=i)StatusGetElem_L(LinkListL,inti,ElemType&e){LinkListp; p=L->next;intj=1; while(p&&j<i){p=p->next;++j;} if(!p||j>i)returnERROR; e=p->data; returnOK;}插入元素p30算法2.9

在第i個元素之前插入，先找到第i-1個結(jié)點StatusListInsert_L(LinkList&L,inti,ElemTypee){LinkListp,s; p=L;intj=0; while(p&&j<i-1){p=p->next;++j;} if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e;s->next=p->next; p->next=s; returnOK;}…esP->next=s…(2)(3)ps->next=p->nexta(1)b在帶表頭結(jié)點的單鏈表第一個結(jié)點前插入新結(jié)點

newnode→next=p→next; if(p→next==NULL)last=newnode;p→next=newnode;刪除元素p30算法2.10StatusListDelete_L(LinkList&L,inti,ElemType&e){LinkListp,q; p=L;intj=0; while(p->next&&j<i-1){p=p->next;++j;} if(!(p->next)||j>i-1)returnERROR; q=p->next; p->next=q->next; e=q->data; free(q); returnOK;}

q=p→next;p→next=q→next;deleteq;if(p→next==NULL)last=p;從帶表頭結(jié)點的單鏈表中刪除第一個結(jié)點建立鏈表（頭插法建表）p31算法2.11

在鏈表表頭插入新結(jié)點，結(jié)點次序與輸入次序相反。voidCreateList_L(LinkList&L,intn){LinkListp; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(inti=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next=L->next;L->next=p;}}尾插法建表：將新結(jié)點插到鏈表尾部，須增設(shè)一個尾指針last，使其始終指向當(dāng)前鏈表的尾結(jié)點。合并有序鏈表p31算法2.12voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){LinkListpa,pb,pc; pa=La->next;pb=Lb->next; Lc=pc=La; 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);}查找（按值查找）intLinkLocate_L(LinkListL,intx){inti;LinkListp;p=L->next;i=1;while(p!=NULL&&p->data!=x){p=p->next;i++;}if(!p){printf("Notfound!\n");return(0);}else{printf("i=%d\n",i);return(i);}}求長度intLinkLength_L(LinkListL){intj;LinkListp;p=L->next;j=0;while(p){p=p->next;j++;}return(j);}注意：p=NULL與p->next=NULL是不同的?？偨Y(jié)：帶頭結(jié)點：鏈表置空L-〉next=NULL；判斷是否為空的條件if(L->next=NULL)

不帶頭結(jié)點：則置空L=NULL;

判空條件if(L=NULL)集合并運算5-2A=A∪BvoidUnionList_L(LinkList&La,LinkListLb){LinkListp,q,first;intx;first=La->next;p=Lb->next;while(p){x=p->data;p=p->next;q=first;while(q&&q->data!=x)q=q->next;if(!q){q=(LinkList)malloc(sizeof(LNode));q->data=x;q->next=La->next;La->next=q;}}}說明：first的位置始終不變；插入位置在La表的表頭元素之前；查找不會在剛剛插入的結(jié)點間進(jìn)行，只能從first指向的原始La表中進(jìn)行（因為每次查找時均有q=first）時間復(fù)雜度：O(m*n)；

3.循環(huán)鏈表1）循環(huán)鏈表——是一種首尾相接的鏈表。循環(huán)鏈表最后一個結(jié)點的next指針不為0(NULL)，而是指向了表頭結(jié)點。在循環(huán)鏈表中沒有NULL

為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。

特點：循環(huán)鏈表中，從任一結(jié)點出發(fā)都可訪問到表中所有結(jié)點；而在單鏈表中，必須從頭指針開始，否則無法訪問到該結(jié)點之前的其他結(jié)點。循環(huán)鏈表與單鏈表不同的是鏈表中表尾結(jié)點的指針域不是NULL，而是鏈表頭結(jié)點的指針H（鏈表指針）循環(huán)鏈表的示例帶表頭結(jié)點的循環(huán)鏈表（循環(huán)條件：p->next!=H）

2）循環(huán)鏈表的操作合并兩個單鏈表

p=La;while(p->next)p=p->next;p->next=Lb->next;free(Lb);時間復(fù)雜度O(m)合并兩個循環(huán)鏈表p=La;while(p->next!=La)p=p->next;p->next=Lb->next;p=p->next;while(p->next!=Lb)p=p->next;p->next=La;free(Lb);時間復(fù)雜度O(m+n)循環(huán)鏈表的建立算法voidCreateList_L(LinkList&L){LinkListp;intx; L=(LinkList)malloc(sizeof(LNode));L->next=L; while(scanf("%d,",&x),x!=0){p=(LinkList)malloc(sizeof(LNode)); p->data=x;p->next=L->next;L->next=p;}}顯示輸出算法（帶頭結(jié)點）——循環(huán)鏈表voidPrintList_LC(LinkListL){LinkListp; p=L->next;printf("L->"); while(p!=L){ printf("%d->",p->data); p=p->next;} printf("L\n");}4.雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。1)雙向鏈表的結(jié)點結(jié)構(gòu)：前驅(qū)方向(a)結(jié)點結(jié)構(gòu)后繼方向雙向鏈表通常采用帶表頭結(jié)點的循環(huán)鏈表形式。對雙向循環(huán)鏈表中任一結(jié)點的指針，有：

p==p→prior→next==p→next→prior置空表：

p→prior=p;p→next=p;

(b)非空雙向循環(huán)鏈表(c)空表2）雙向循環(huán)鏈表存儲結(jié)構(gòu)的

描述p35～p36typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;DuLinkListd,p;p→prior=current; (1)p→next=current→next;(2) current→next=p;(3)p→next→prior=p;(4)雙向循環(huán)鏈表的插入算法current→next→prior=current→prior;current→prior→next=current→next;雙向循環(huán)鏈表的刪除算法3）基本操作：

雙向循環(huán)鏈表的建立voidCrtList_DuL(DuLinkList&L){ DuLinkListp;intx; L=p=(DuLinkList)malloc(sizeof(DuLNode));L->next=L;L->prior=L; while(scanf("%d",&x),x!=0){ p->next=(DuLinkList)malloc(sizeof(DuLNode)); p->next->prior