大學(xué)數(shù)據(jù)結(jié)構(gòu)課件線性表

第2章線性表主要知識點線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)鏈表與雙向鏈表第2章線性表主要知識點線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)鏈12.1線性表抽象數(shù)據(jù)類型1.線性表的定義線性表是n(n≥0)個數(shù)據(jù)元素的有限序列。由相同類型數(shù)據(jù)元素（a1,a2,…,an）組成的線性結(jié)構(gòu)。數(shù)據(jù)元素之間存在著線性的邏輯關(guān)系：（1）表中有且僅有一個開始結(jié)點；（2）表中有且僅有一個終端結(jié)點；（3）除開始結(jié)點外，表中每個結(jié)點均只有一個前趨結(jié)點（Predecessor）;（4）除終端結(jié)點外，表中每個結(jié)點只均只有一個后繼結(jié)點（Successor）2.1線性表抽象數(shù)據(jù)類型1.線性表的定義線性22.線性表抽象數(shù)據(jù)類型數(shù)據(jù)對象:｛a1,a2,…,an｝,ai的數(shù)據(jù)類型為ElemType操作集合:(1)Initiate(L)初始化線性表(2)Length(L)求當(dāng)前數(shù)據(jù)元素個數(shù)(3)Insert(L,i,x)插入數(shù)據(jù)元素*(4)Delete(L,i)刪除數(shù)據(jù)元素*(5)Get(L,i)取數(shù)據(jù)元素邏輯關(guān)系:<ai

,ai+1>,對ai，當(dāng)1＜i≤n時，它有一個直接前趨ai-1；當(dāng)1≤i＜n時，它有一個直接后繼ai+1。(6)Locate(L,x)確定x在表中的位置2.線性表抽象數(shù)據(jù)類型數(shù)據(jù)對象:｛a1,a2,…,32.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)1.順序表的存儲結(jié)構(gòu)

實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲單元的物理前后位置上。

向量是內(nèi)存中一批地址連續(xù)的存儲單元。所以，線性表的順序存儲也稱為向量存儲。順序表的存儲結(jié)構(gòu)如圖所示順序存儲結(jié)構(gòu)的線性表稱作順序表2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)1.順序表的存儲結(jié)構(gòu)4a0a1a2a3a4a5…elemlength=6MaxSize-1123456第i個元素的地址：LOC(ai)=LOC(a1)+L*(i-1)typedefstruct{ ElemTypeelem[MAXSIZE]; intlength;}Sqlist;靜態(tài)一維數(shù)組事先定義的常量結(jié)構(gòu)體類型名，之后可用于說明結(jié)構(gòu)體變量a0a1a2a3a4a5…elemlength=6MaxSi5在結(jié)構(gòu)體中還可以使用動態(tài)一維數(shù)組。如下定義：typedefstruct{ ElemType*elem; intlength;}Sqlist1;使用指針表示數(shù)組域表長域Sqlista;

…

a.Elem=(Sqlist1*)malloc(MAXSIZE*sizeof(ElemType));

…

free(a.elem)#defineMAXSIZE100在結(jié)構(gòu)體中還可以使用動態(tài)一維數(shù)組。如下定義：typedef62.順序表操作的實現(xiàn)（線性表在向量中基本運算的實現(xiàn)）#defineMAXSIZE100TypedefintElemType;typedefstruct{ ElemTypeelem[MAXSIZE];/*數(shù)組域*/ intlength;

/*表長域*/}Sqlist;/*結(jié)構(gòu)體類型名*/2.順序表操作的實現(xiàn)（線性表在向量中基本運算的實現(xiàn)）#def7（1）插入數(shù)據(jù)元素Insert(L,i,x)（1）插入數(shù)據(jù)元素Insert(L,i,x)8（1）插入數(shù)據(jù)元素Insert(L,i,x)（1）插入數(shù)據(jù)元素Insert(L,i,x)9（1）插入數(shù)據(jù)元素Insert(L,i,x)（1）插入數(shù)據(jù)元素Insert(L,i,x)10（1）插入數(shù)據(jù)元素Insert(L,i,x)（1）插入數(shù)據(jù)元素Insert(L,i,x)11intInsert(Sqlist*L,inti,ElemTypex){ intj; for(j=L->length;j>i;j--) L->elem[j]=L->elem[j-1];/*依次后移*/

L->elem[i]=x; /*插入x*/ L->length++; /*元素個數(shù)加1*/

return1;}typedefstruct{ ElemTypeelem[MAXSIZE]; intlength;

}Sqlist;插入算法的實現(xiàn)intInsert(Sqlist*L,inti,12（2）刪除數(shù)據(jù)元素ListDelete(L,i,x)（2）刪除數(shù)據(jù)元素ListDelete(L,i,x)13（2）刪除數(shù)據(jù)元素操作的算法實現(xiàn)intDelete(Sqlist*L,inti) {intj;for(j=i+1;j<=L->lengh-1;j++)L->elem[j-1]=L->elem[j];/*依次前移*/L->lengh--; /*數(shù)據(jù)元素個數(shù)減1*/return1;}（2）刪除數(shù)據(jù)元素操作的算法實現(xiàn)intDelete(143.順序表操作的效率分析時間效率分析:算法時間主要耗費在移動元素的操作上，因此計算時間復(fù)雜度的基本操作(最深層語句頻度)

T(n)=O(移動元素次數(shù))

而移動元素的個數(shù)取決于插入或刪除元素的位置i若i=lengh，則根本無需移動（特別快）；若i=0，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)才合理。3.順序表操作的效率分析時間效率分析:算法時間主要耗費在移動15設(shè)Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，順序表中的數(shù)據(jù)元素個數(shù)為n,當(dāng)在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Pi=1/(n+1),則

插入時的平均移動次數(shù)為:n(n+1)/2÷(n+1)＝n/2≈O(n)同理可證:順序表刪除一元素的時間效率為:T（n)=(n-1)/2≈O(n)

設(shè)Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，順序16順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在順序表中插入和刪除一個數(shù)據(jù)元素的時間復(fù)雜度為O(n),其余操作的時間復(fù)雜度都為O(1)插入效率：刪除效率：順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在順序表中插174.順序表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。實現(xiàn)方法：

1、采用直接編寫一個主函數(shù)實現(xiàn)。

2、利用已設(shè)計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SqList.h中，通過#include“SqList.h”）

4.順序表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線18程序設(shè)計如下：

voidmain(void){SqlistmyList;inti,x;Initiate(&myList);for(i=0;i<10;i++)

Insert(&myList,i,i+1);Delete(&myList,4);for(i=0;i<Length(myList);i++)Get(myList,i,&x);}程序運行結(jié)果：1234678910

elem[100]length=0#include<stdio.h> #include"Sqlist.h"#defineMAXSIZE100typedefintElemType;elem[0]=1Elem[1]=2…Elem[4]=5…Elem[9]=10length=10typedefstruct{ElemTypeelem[MAXSIZE];

intlength;}Sqlist;elem[0]=1Elem[1]=2…Elem[4]=6…Elem[8]=10length=9程序設(shè)計如下：voidmain(void)程序運行結(jié)果：119主要優(yōu)點:算法簡單，空間單元利用率高；主要缺點:1.插入和刪除時需要移動較多的數(shù)據(jù)元素，所以在頻繁時行插入、刪除操作時效率較低。

2.需要預(yù)先確定數(shù)據(jù)元素的最大個數(shù)。并預(yù)先占用一片地址連續(xù)的存儲空間。

3.如果插入數(shù)據(jù)元素量超過預(yù)先分配的存儲空間時，要臨時擴大有很大困難。線性表順序存儲結(jié)構(gòu)的主要優(yōu)缺點主要優(yōu)點:主要缺點:線性表順序存儲結(jié)構(gòu)的主要優(yōu)缺點202.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈表存儲結(jié)構(gòu)的特點：是構(gòu)成鏈表的結(jié)點（即分配給每一個數(shù)據(jù)元素的存儲單元）可分為兩個域（數(shù)據(jù)域和指針域）。數(shù)據(jù)域保存數(shù)據(jù)元素本身的數(shù)據(jù)信息，指針域保存其直接后繼結(jié)點的地址（稱為指針）。數(shù)據(jù)元素間的邏輯關(guān)系由每個結(jié)點的指針體現(xiàn)。所以，邏輯上相鄰的數(shù)據(jù)元素在物理上不要求相鄰。因此它不需要一片地址連續(xù)的存儲空間，可以避免了順序表所具有的缺點。指針域數(shù)據(jù)域nextdata或2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈表存儲結(jié)構(gòu)的特點：21指針域數(shù)據(jù)域nextdata或存儲數(shù)據(jù)元素信息（簡單類型或結(jié)構(gòu)類型）的子域存儲直接后繼結(jié)點的地址（即存儲位置)的子域（存儲地址的變量稱為指針變量）2.3.1結(jié)點結(jié)構(gòu)與指針變量結(jié)點的存儲結(jié)構(gòu)定義為：typedefintElemType;Typedefstructnode{ElemTypedata;

/*數(shù)據(jù)域*/structnode*next;/*指針域*/}Lnode1.結(jié)點結(jié)構(gòu)指針域數(shù)據(jù)域nextdata或存儲數(shù)據(jù)元素信息（簡單類型或結(jié)22假設(shè)h,p,q為指針變量，可說明如下：Lnode*h,*p,*q;/*4bytes未賦值*/h=NULL;/*setNULLtoh*/h=(Lnode*)malloc(sizeof(Lnode));/*pointtoanewnode*/p=h;/*p和h中存放的是同一結(jié)點的首地址*/p->data=12;p->next=NULL;free(h)/*orfree(p),releasethenode’sspacetothesystem*/h∧p?h?q?12∧h→p→??h→p→??h→Next:4bytesData:Sizeof(ElemType)2.指針變量及其基本操作假設(shè)h,p,q為指針變量，可說明如下：h∧p?h?q?123p=q;qqpp=q->next;qqpp->next=q;pqpqp->next=q->next;ppqq指針變量的主要操作：語句執(zhí)行前執(zhí)行后p=q;qqpp=q->next;qqpp->next=242.3.2單鏈表及其結(jié)構(gòu)

n個結(jié)點鏈接在一起可以構(gòu)成一個鏈表。由于其每個結(jié)點中只包含一個指針域，故稱為單鏈表。非空線性單鏈表,包括一個頭結(jié)點和n個數(shù)據(jù)元素的結(jié)點。頭指針h指向鏈表的頭結(jié)點或首元結(jié)點。頭指針h可以作為鏈表的唯一已知條件。對鏈表的各種操作一般須從頭指針開始?！膆→空鏈表h->next=NULLh…a1a2an∧附加頭結(jié)點，簡稱頭結(jié)點，h結(jié)點，數(shù)據(jù)域可放表長信息，它不計入表長度。頭指針首元結(jié)點存儲線性表第一個數(shù)據(jù)元素2.3.2單鏈表及其結(jié)構(gòu)非空線性單鏈表,包括一個頭結(jié)點和252.3.3線性鏈表基本運算的實現(xiàn)pa1a2an∧…h(huán)datanextx∧s(a)插入前1)

在帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點pa1a2an∧…h(huán)datanextxs(b)插入后第一步:s->next=p->next第二步:p->next=s2.3.3線性鏈表基本運算的實現(xiàn)pa1a2an∧…h(huán)da26pa1a2an∧…h(huán)datanextxs第一步:s->next=p->next第二步:p->next=spai-1a1aian∧…datanextxs…s->next=p->next(x.next=ai-1.next)p->next=s(ai-1.next=s)h*分別在帶頭結(jié)點單鏈表的首元結(jié)點和其它結(jié)點前插入結(jié)點的操作比較pa1a2an∧…h(huán)datanextxs第一步:第二步:p272)刪除帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點pa1a2an∧…h(huán)datanext刪除前pa1a2an∧…h(huán)datanext刪除后p->next=p->next->next(a1.next)2)刪除帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點pa1a2an∧…28*刪除帶頭結(jié)點單鏈表首元結(jié)點和其它結(jié)點操作的比較pa1a2an∧…h(huán)datanext刪除后p->next=p->next->next(a1.next)pai-1a1aian∧…datanext…×ai+1p->next=p->next->next(ai-1.next=ai.next)h*刪除帶頭結(jié)點單鏈表首元結(jié)點和其它結(jié)點操作的比較pa1a2293)在不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點a1a2an∧…h(huán)x∧s(a)插入前a1a2an∧…h(huán)xs(b)插入后第一步:s->next=h第二步:h=s3)在不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點a1a2an304).在不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素前插入結(jié)點pai-1a1aian∧…h(huán)datanextx∧s…插入前pai-1a1aian∧…h(huán)datanextxs…s->next=p->next(x.next=ai-1.next)p->next=s(ai-1.next=s)插入后4).在不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素前插入結(jié)點pai-1a131*在不帶頭結(jié)點單鏈表首元結(jié)點和其他結(jié)點前插入結(jié)點之比較pai-1a1aian∧…h(huán)datanextxs…s->next=p->next(x.next=ai-1.next)p->next=s(ai-1.next=s)a1a2an∧…h(huán)xs第一步:s->next=h第二步:h=s*在不帶頭結(jié)點單鏈表首元結(jié)點和其他結(jié)點前插入結(jié)點之比較pa325)刪除不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點6)刪除不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素結(jié)點a1a2an∧…h(huán)datanext×h=h->nextpai-1a1aian∧…h(huán)datanext…×ai+1p->next=p->next->next(ai-1.next=ai.next)5)刪除不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點6)刪除不帶頭33結(jié)論（1）帶頭結(jié)點單鏈表無論在第一個數(shù)據(jù)元素結(jié)點前插入，還是在其他結(jié)點前插入，操作方法一樣；而不帶頭結(jié)點單鏈表在第一個數(shù)據(jù)元素結(jié)點前插入，和在其他結(jié)點前插入，操作方法不一樣（2）刪除操作和插入操作類似（3）設(shè)計帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)可設(shè)計成輸入型參數(shù)；設(shè)計不帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)必須設(shè)計成輸出型參數(shù)（4）因此，帶頭結(jié)點單鏈表的算法設(shè)計簡單結(jié)論342.3.4單鏈表的操作實現(xiàn)舉例x∧…h(huán)q…sp{q=h;while(q->next!=p)q=q->next;s=(Lnode*)malloc(sizeof(Lnode))s->data=x;s->next=p;q->next=s;}Typedefstructnode{ElemTypedata;

structnode*next;}Lnode1、在p指向的結(jié)點前插入數(shù)據(jù)元素x2.3.4單鏈表的操作實現(xiàn)舉例x∧…h(huán)q…sp{q=h352、在線性表中值為x的元素前插入值為y的數(shù)據(jù)元素aiyan∧…h(huán)q…xa1spvoidInsert(Lnode*h,ElemTypex,ElemTypey){s=(Lnode*)malloc(sizeof(Lnode))s->data=y;q=h;p=q->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}s->next=p;q->next=s;}Typedefstructnode{ElemTypedata;

structnode*next;}Lnode2、在線性表中值為x的元素前插入值為y的數(shù)據(jù)元素aiyan∧363、刪除p所指向的結(jié)點b…qpca{q=h;while(q->next!=p)q=q->next;q->next=p->next;free(p);}3、刪除p所指向的結(jié)點b…qpca{q=h;374、刪除線性表中值為x的數(shù)據(jù)元素voidDelete(Lnode*h,ElemTypex){q=h;p=q->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL)printf(“NO!”);else{q->next=p->next;free(p);printf(“YES!”);}}Typedefstructnode{ElemTypedata;

structnode*next;}Lnodeaixan∧…h(huán)q…ai+1a1p4、刪除線性表中值為x的數(shù)據(jù)元素voidDelete(L385、刪除線性鏈表中第i個元素結(jié)點，并返回該數(shù)據(jù)元素的值。ElemTypeDeletei(Lnode*h,inti){intk=0;p=h;while((p->next!=NULL)&&(k<i-1)){p=p->next;k++;}if((p->next!=NULL)&&k==i-1))/*第i個元素結(jié)點存在*/{q=p->next;y=q->data;p->next=q->next;free(q);}else{printf(“\nierror!”);y=-1;}returny;}ai-1aian∧…h(huán)p…ai+1a1qp5、刪除線性鏈表中第i個元素結(jié)點，并返回該數(shù)據(jù)元素的值。El392.3.5單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：所以，單鏈表進行數(shù)據(jù)元素插入刪除操作的時間復(fù)雜度為O(n)。2.3.5單鏈表操作的效率分析單鏈表的插入和刪除操作不需402.4循環(huán)鏈表與雙向鏈表循環(huán)單鏈表是單鏈表的另一種形式的存儲結(jié)構(gòu)，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針域指向整個鏈表的第一個結(jié)點，從而使鏈表形成一個環(huán)。它的優(yōu)點是從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點。程序設(shè)計：p!=NULL 改為 p!=headP->!=NULL 改為 p->!=headhead(a)空鏈表reara0a1an-1…h(huán)ead(b)非空鏈表r尾指針2.4.1循環(huán)鏈表2.4循環(huán)鏈表與雙向鏈表