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

第2章線性表主要知識(shí)點(diǎn)線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)鏈表與雙向鏈表第2章線性表主要知識(shí)點(diǎn)線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)鏈12.1線性表抽象數(shù)據(jù)類型1.線性表的定義線性表是n(n≥0)個(gè)數(shù)據(jù)元素的有限序列。由相同類型數(shù)據(jù)元素（a1,a2,…,an）組成的線性結(jié)構(gòu)。數(shù)據(jù)元素之間存在著線性的邏輯關(guān)系：（1）表中有且僅有一個(gè)開始結(jié)點(diǎn)；（2）表中有且僅有一個(gè)終端結(jié)點(diǎn)；（3）除開始結(jié)點(diǎn)外，表中每個(gè)結(jié)點(diǎn)均只有一個(gè)前趨結(jié)點(diǎn)（Predecessor）;（4）除終端結(jié)點(diǎn)外，表中每個(gè)結(jié)點(diǎn)只均只有一個(gè)后繼結(jié)點(diǎn)（Successor）2.1線性表抽象數(shù)據(jù)類型1.線性表的定義線性22.線性表抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:｛a1,a2,…,an｝,ai的數(shù)據(jù)類型為ElemType操作集合:(1)Initiate(L)初始化線性表(2)Length(L)求當(dāng)前數(shù)據(jù)元素個(gè)數(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>,對(duì)ai，當(dāng)1＜i≤n時(shí)，它有一個(gè)直接前趨ai-1；當(dāng)1≤i＜n時(shí)，它有一個(gè)直接后繼ai+1。(6)Locate(L,x)確定x在表中的位置2.線性表抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:｛a1,a2,…,32.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)1.順序表的存儲(chǔ)結(jié)構(gòu)

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

向量是內(nèi)存中一批地址連續(xù)的存儲(chǔ)單元。所以，線性表的順序存儲(chǔ)也稱為向量存儲(chǔ)。順序表的存儲(chǔ)結(jié)構(gòu)如圖所示順序存儲(chǔ)結(jié)構(gòu)的線性表稱作順序表2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)1.順序表的存儲(chǔ)結(jié)構(gòu)4a0a1a2a3a4a5…elemlength=6MaxSize-1123456第i個(gè)元素的地址：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)體中還可以使用動(dòng)態(tài)一維數(shù)組。如下定義：typedefstruct{ ElemType*elem; intlength;}Sqlist1;使用指針表示數(shù)組域表長(zhǎng)域Sqlista;

…

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

…

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

/*表長(zhǎng)域*/}Sqlist;/*結(jié)構(gòu)體類型名*/2.順序表操作的實(shí)現(xiàn)（線性表在向量中基本運(yùn)算的實(shí)現(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++; /*元素個(gè)數(shù)加1*/

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

}Sqlist;插入算法的實(shí)現(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ù)元素操作的算法實(shí)現(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ù)元素個(gè)數(shù)減1*/return1;}（2）刪除數(shù)據(jù)元素操作的算法實(shí)現(xiàn)intDelete(143.順序表操作的效率分析時(shí)間效率分析:算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作(最深層語句頻度)

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

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

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

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

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

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

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

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);}程序運(yùn)行結(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è)計(jì)如下：voidmain(void)程序運(yùn)行結(jié)果：119主要優(yōu)點(diǎn):算法簡(jiǎn)單，空間單元利用率高；主要缺點(diǎn):1.插入和刪除時(shí)需要移動(dòng)較多的數(shù)據(jù)元素，所以在頻繁時(shí)行插入、刪除操作時(shí)效率較低。

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

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

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

在帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)pa1a2an∧…h(huán)datanextxs(b)插入后第一步:s->next=p->next第二步:p->next=s2.3.3線性鏈表基本運(yùn)算的實(shí)現(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é)點(diǎn)單鏈表的首元結(jié)點(diǎn)和其它結(jié)點(diǎn)前插入結(jié)點(diǎn)的操作比較pa1a2an∧…h(huán)datanextxs第一步:第二步:p272)刪除帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)pa1a2an∧…h(huán)datanext刪除前pa1a2an∧…h(huán)datanext刪除后p->next=p->next->next(a1.next)2)刪除帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)pa1a2an∧…28*刪除帶頭結(jié)點(diǎn)單鏈表首元結(jié)點(diǎn)和其它結(jié)點(diǎn)操作的比較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é)點(diǎn)單鏈表首元結(jié)點(diǎn)和其它結(jié)點(diǎn)操作的比較pa1a2293)在不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)a1a2an∧…h(huán)x∧s(a)插入前a1a2an∧…h(huán)xs(b)插入后第一步:s->next=h第二步:h=s3)在不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素前插入結(jié)點(diǎn)a1a2an304).在不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素前插入結(jié)點(diǎn)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é)點(diǎn)單鏈表其他數(shù)據(jù)元素前插入結(jié)點(diǎn)pai-1a131*在不帶頭結(jié)點(diǎn)單鏈表首元結(jié)點(diǎn)和其他結(jié)點(diǎn)前插入結(jié)點(diǎn)之比較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é)點(diǎn)單鏈表首元結(jié)點(diǎn)和其他結(jié)點(diǎn)前插入結(jié)點(diǎn)之比較pa325)刪除不帶頭結(jié)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)6)刪除不帶頭結(jié)點(diǎn)單鏈表其他數(shù)據(jù)元素結(jié)點(diǎn)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é)點(diǎn)單鏈表第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)6)刪除不帶頭33結(jié)論（1）帶頭結(jié)點(diǎn)單鏈表無論在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入，還是在其他結(jié)點(diǎn)前插入，操作方法一樣；而不帶頭結(jié)點(diǎn)單鏈表在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入，和在其他結(jié)點(diǎn)前插入，操作方法不一樣（2）刪除操作和插入操作類似（3）設(shè)計(jì)帶頭結(jié)點(diǎn)單鏈表的算法時(shí)，頭指針參數(shù)可設(shè)計(jì)成輸入型參數(shù)；設(shè)計(jì)不帶頭結(jié)點(diǎn)單鏈表的算法時(shí)，頭指針參數(shù)必須設(shè)計(jì)成輸出型參數(shù)（4）因此，帶頭結(jié)點(diǎn)單鏈表的算法設(shè)計(jì)簡(jiǎn)單結(jié)論342.3.4單鏈表的操作實(shí)現(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é)點(diǎn)前插入數(shù)據(jù)元素x2.3.4單鏈表的操作實(shí)現(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é)點(diǎn)b…qpca{q=h;while(q->next!=p)q=q->next;q->next=p->next;free(p);}3、刪除p所指向的結(jié)點(diǎn)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個(gè)元素結(jié)點(diǎn)，并返回該數(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個(gè)元素結(jié)點(diǎn)存在*/{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個(gè)元素結(jié)點(diǎn)，并返回該數(shù)據(jù)元素的值。El392.3.5單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動(dòng)數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí)，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為：所以，單鏈表進(jìn)行數(shù)據(jù)元素插入刪除操作的時(shí)間復(fù)雜度為O(n)。2.3.5單鏈表操作的效率分析單鏈表的插入和刪除操作不需402.4循環(huán)鏈表與雙向鏈表循環(huán)單鏈表是單鏈表的另一種形式的存儲(chǔ)結(jié)構(gòu)，其結(jié)構(gòu)特點(diǎn)是鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。它的優(yōu)點(diǎn)是從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。程序設(shè)計(jì)：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)鏈表與雙向鏈表