數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第2章 線性表

第2章線性表2024/9/262導(dǎo)學(xué)問題1：簡易的學(xué)生信息管理系統(tǒng)實(shí)現(xiàn)一個(gè)簡易的學(xué)生信息管理系統(tǒng)，其中學(xué)生信息包括：學(xué)號(hào)、姓名、性別、年齡、專業(yè)等。要求系統(tǒng)能提供建立、查詢、刪除和增加學(xué)生信息等功能。2024/9/263導(dǎo)學(xué)問題2：簡易的商品信息管理系統(tǒng)實(shí)現(xiàn)一個(gè)簡易的商品信息管理系統(tǒng)，其中商品信息包括：商品代碼、品名、單價(jià)、庫存量等。要求系統(tǒng)能提供建立、查詢、刪除和增加商品信息等功能。2024/9/264程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一種合適的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，并設(shè)計(jì)基于此結(jié)構(gòu)上的一批高效的處理算法。因此，首先需要分析實(shí)際問題中需要處理的數(shù)據(jù)對(duì)象的特點(diǎn)。問題分析2024/9/265學(xué)生信息表問題分析2024/9/266商品信息表問題分析2024/9/267考慮：數(shù)據(jù)元素之間的關(guān)系是什么？——數(shù)據(jù)如何表示？數(shù)據(jù)元素如何存儲(chǔ)？數(shù)據(jù)元素如何處理？2024/9/2682.1知識(shí)學(xué)習(xí)2.1.1線性表的概念線性表是具有相同數(shù)據(jù)類型的n（n≥0）個(gè)數(shù)據(jù)元素組成的有限序列，通常記為L=(a1，a2，…，ai

1，ai，ai+1，…，an)a1a3a4ana22024/9/2692.1知識(shí)學(xué)習(xí)非空線性表的特性有且僅有一個(gè)表頭結(jié)點(diǎn)a1，它沒有前驅(qū)，而僅有一個(gè)后繼a2；（2）有且僅有一個(gè)表尾結(jié)點(diǎn)an，它沒有后繼，而僅有一個(gè)前驅(qū)an－1；（3）其余的結(jié)點(diǎn)ai（2≤i≤n

1）都有且僅有一個(gè)前驅(qū)a

i－1和一個(gè)后繼a

i+1。2.1.1線性表的概念2024/9/26102.1知識(shí)學(xué)習(xí)2.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)及基本操作2.1.2.1順序結(jié)構(gòu)342367434存儲(chǔ)要點(diǎn)用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素例：（34,23,67,43）2024/9/2611例：（34,23,67,43）34236743存儲(chǔ)空間的起始位置4用什么屬性來描述順序表？順序表的容量（最大長度）順序表的當(dāng)前長度2024/9/26122.1知識(shí)學(xué)習(xí)2.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)及基本操作2.1.2.1順序結(jié)構(gòu)數(shù)據(jù)元素為整型數(shù)的順序表類型描述。constintMAXSIZE=100;//順序表最大長度typedefstruct{ intdata[MAXSIZE];//存放數(shù)據(jù)元素的數(shù)組 intlength;//順序表的長度}SeqList;2024/9/2613算法描述：voidInitList_Seq(SeqList&L){L.length=0;}初始化操作——?jiǎng)?chuàng)建空表

datalength02.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2614初始化操作——?jiǎng)?chuàng)建長度為n的順序表2.1.2.2順序表基本操作的實(shí)現(xiàn)順序表

數(shù)組a351224334253512243342算法描述：voidCreatList_Seq(SeqList&L,inta[],intn){if(n>L.MAXSIZE){cout<<"參數(shù)超出順序表容量"<<endl;exit(1);}

L.length=0;

for(inti=0;i<n;i++)

L.data[L.length++]=a[i];}2024/9/2615遍歷順序表2.1.2.2順序表基本操作的實(shí)現(xiàn)voidShow_Seq(SeqList&L){ for(inti=0;i<L.length;i++) cout<<L.data[i]<<""; cout<<endl;}

算法描述：2024/9/2616求順序表長度2.1.2.2順序表基本操作的實(shí)現(xiàn)intListLength_Seq(SeqList&L){ returnL.length;}算法描述：2024/9/2617按值查找元素：535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號(hào)。iii注意序號(hào)和下標(biāo)之間的關(guān)系2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2618intLocateElem_Seq(SeqListL,inte){for(inti=0;i<L.length;i++) if(L.data[i]==e) returni+1;

return0;}按值查找算法描述：時(shí)間復(fù)雜度？2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2619插入操作2.1.2.2順序表基本操作的實(shí)現(xiàn)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,e

,ai,…,an)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系2024/9/262033例：（35，12，24，42），在i=2的位置上插入33。表滿：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號(hào)）435122442a1a2a3a401234422412335什么時(shí)候不能插入？注意邊界條件2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/26212.1.2.2順序表基本操作的實(shí)現(xiàn)插入操作算法描述①檢查順序表的存儲(chǔ)空間是否已到最大值（被占滿），若是，則停止插入，并給出“上溢”出錯(cuò)提示；否則，執(zhí)行第②步。②檢查插入位置i是否合法，若不合法，則停止插入，并給出“插入位置非法”出錯(cuò)提示；否則，執(zhí)行第③步。③從最后一個(gè)元素向前直至第i個(gè)元素（下標(biāo)為i

1）為止，將每一個(gè)元素均后移一個(gè)存儲(chǔ)單元，將第i個(gè)元素的存儲(chǔ)位置空出。④將新元素e寫入到第i個(gè)元素處，即下標(biāo)為i

1的位置。⑤將順序表長度加1。2024/9/2622插入操作算法描述：2.1.2.2順序表基本操作的實(shí)現(xiàn)voidListInsert_Seq(SeqList&L,inti,inte){ if(L.length>=MAXSIZE)

{cout<<"線性表已滿"<<endl;exit(1);} if(i<1||i>L.length+1)

{cout<<"i值不合法"<<endl;exit(1);}

for(intj=L.length-1;j>=i-1;j--)

L.data[j+1]=L.data[j];

L.data[i-1]=e;

L.length++;}

2024/9/2623最好情況（i=n+1）：基本語句執(zhí)行0次，時(shí)間復(fù)雜度為O(1)。最壞情況（i=1）：基本語句執(zhí)行n+1次，時(shí)間復(fù)雜度為O(n)。平均情況（1≤i≤n+1）：時(shí)間復(fù)雜度為O(n)。插入算法時(shí)間性能分析：?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)2.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2624刪除操作：刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化2.1.2.2

順序表基本操作的實(shí)現(xiàn)2024/9/2625例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出算法的描述；3.分析時(shí)間復(fù)雜度。535a1a2a3a401234422412334a51224422.1.2.2順序表基本操作的實(shí)現(xiàn)2024/9/2626刪除操作算法描述：2.1.2.2順序表基本操作的實(shí)現(xiàn)voidListDelete_Seq(SeqList&L,inti,int&e){ if((i<1)||(i>L.length))

{cout<<"i值不合法"<<endl;exit(1);} e=L.data[i-1]; for(intj=i;j<L.length;j++)

L.data[j-1]=L.data[j];

L.length--;}2024/9/26272.1.2.3順序表基本操作的優(yōu)化（1）增強(qiáng)通用性（2）增強(qiáng)靈活性（3）增強(qiáng)適應(yīng)性2024/9/26282.1.3線性表的鏈接存儲(chǔ)及基本操作鏈表：線性表的鏈接存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)思想：用一組任意的存儲(chǔ)單元存放線性表的元素。靜態(tài)存儲(chǔ)分配順序表事先確定容量鏈表動(dòng)態(tài)存儲(chǔ)分配運(yùn)行時(shí)分配空間連續(xù)不連續(xù)零散分布2024/9/26292.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例：(a1,a2

,a3,a4)的存儲(chǔ)示意圖存儲(chǔ)特點(diǎn)：邏輯次序和物理次序不一定相同。元素之間的邏輯關(guān)系用指針表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26300200020803000325…………a10200a20325a30300a4∧結(jié)點(diǎn)數(shù)據(jù)域指針域單鏈表是由若干結(jié)點(diǎn)構(gòu)成的；單鏈表的結(jié)點(diǎn)只有一個(gè)指針域。data：存儲(chǔ)數(shù)據(jù)元素next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域指針域2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2631typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：如何申請(qǐng)一個(gè)結(jié)點(diǎn)？2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2632s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：……sNode2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2633s=newNode;datanext……sNode如何引用數(shù)據(jù)元素？s->data;(*s).data;data如何引用指針域？nexts->next;2.1.3.1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/26340200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表頭指針：指向第一個(gè)結(jié)點(diǎn)的地址。尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭铡?.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26350200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不統(tǒng)一，缺點(diǎn)？如何將空表與非空表統(tǒng)一？2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2636頭結(jié)點(diǎn)：在單鏈表的第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)，以便空表和非空表處理統(tǒng)一。非空表heada1a2an∧空表head∧2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26372.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——?jiǎng)?chuàng)建空的單鏈表2024/9/26382.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidCreateList_L(LinkList&L,ElemTypea[],intn){

LinkLists;

L=newNode;L->next=NULL;for(inti=n-1;i>=0;i--)

{s=newNode;s->data=a[i];

s->next=L->next;L->next=s;}}初始化——用數(shù)組a中的n個(gè)元素創(chuàng)建單鏈表2024/9/26392.1.3.2單鏈表基本操作的實(shí)現(xiàn)voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//輸出結(jié)點(diǎn)數(shù)據(jù)域 p=p->next; } cout<<endl;}遍歷單鏈表2024/9/26402.1.3.2單鏈表基本操作的實(shí)現(xiàn)intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//計(jì)數(shù)p=p->next;}returnk;}求單鏈表長度。2024/9/26412.1.3.2單鏈表基本操作的實(shí)現(xiàn)intLocateElem_L(LinkListL,ElemTypee){LinkListp=L->next;

intindex=1;while(p&&p->data!=e)

{p=p->next;

index++;}

if(p)returnindex;

elsereturn0;}按值查找。2024/9/2642插入操作：

voidListInsert_L(LinkListL,inti,ElemTypee)如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、e和ai之間邏輯關(guān)系的變化？pesheada1ai-1an∧ai算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2643注意分析邊界情況——表頭、表尾。

heada1an∧aipes算法描述：s=newNode;s->data=e;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結(jié)點(diǎn)，表頭、表中、表尾三種情況的操作語句一致。

2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2644算法描述——偽代碼1.工作指針p初始化；累加器j清零；

2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；3.若查找不成功，說明插入位置不合理，拋出插入位置異常；否則，

3.1生成一個(gè)元素值為e的新結(jié)點(diǎn)s；

3.2將新結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后；2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2645

voidListInsert_L(LinkListL,inti,ElemTypee){ LinkListp=L,s; intj=0; while(p&&j<i-1){ p=p->next; j++; }

算法描述

if(!p){cout<<"插入位置非法";exit(1);}else{

s=newNode; s->data=e;

s->next=p->next;

p->next=s; }}，基本語句？時(shí)間復(fù)雜度？2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2646刪除操作接口：voidListDelete_L(LinkListL,inti);p如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1和ai之間邏輯關(guān)系的變化？heada1ai-1ai+1ai算法描述：q=p->next;p->next=q->next;deleteq;q2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2647算法描述：q=p->next;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。

pqpq表尾的特殊情況：雖然被刪結(jié)點(diǎn)不存在，但其前驅(qū)結(jié)點(diǎn)卻存在。p->next=NULLheada1ana2∧2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2648算法描述——偽代碼1.工作指針p初始化；累加器j清零；2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；3.若p不存在或p不存在后繼結(jié)點(diǎn)，則拋出位置異常；否則，否則刪除結(jié)點(diǎn)p的后一個(gè)結(jié)點(diǎn)。2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2649voidListDelete_L(LinkListL,inti){ LinkListp=L,q; intj=0; while(p&&j<i-1){ p=p->next; j++;}算法描述

if(!p||!p->next){cout<<"刪除位置非法";exit(1);}

else

{

q=p->next;

p->next=q->next;

deleteq;

}}2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2650將單鏈表中所有結(jié)點(diǎn)的存儲(chǔ)空間釋放。

單鏈表的銷毀操作：heada1a2an∧aipq算法描述：q=p;p=p->next;deleteq;p注意：保證鏈表未處理的部分不斷開

2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/2651voidDestroyList_L(LinkList&L){

LinkListp=L,q; while(p) { q=p; p=p->next; deleteq; } L=NULL;}2.1.3.2單鏈表基本操作的實(shí)現(xiàn)2024/9/26522.2知識(shí)應(yīng)用2024/9/26532.2知識(shí)應(yīng)用2024/9/2654voidUnion(SeqList&La,SeqList&Lb){intLa_len=ListLength_Seq(La);//求線性表La的長度ElemTypee;

while(Lb.length!=0)//Lb表的元素尚未處理完

{

ListDelete_Seq(Lb,1,e);//從Lb中刪除第一個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem_Seq(La,e))//若La中不存在值和e相等的元素，ListInsert_Seq(La,++La_len,e);//則將它插入到La的最后

}}2.3知識(shí)拓展——順序表的其他操作求集合的并集：2024/9/2655voidOrdInsert_Seq(SeqList&L,ElemTypex){

if(L.length>=MAXSIZE){cout<<"線性表已滿"<<endl;exit(1);}

inti=0;while(L.data[i]<=x&&i<L.length)//查找插入位置i

i++;

for(intj=L.length-1;j>=i;j--)//元素后移

L.data[j+1]=L.data[j];

L.data[i]=x;//插入元素x

L.length++;//表長增1}2.3知識(shí)拓展——順序表的其他操作有序表的插入：2024/9/2656voidInvertLinkedList(LinkList&L)//逆置頭指針L所指鏈表{LinkLists,p=L->next;

L->next=NULL;//設(shè)逆置后的鏈表的初態(tài)為空表while(p){//p為待逆置鏈表的頭指針s=p;p=p->next;//從p所指鏈表中刪除第一個(gè)結(jié)點(diǎn)(s結(jié)點(diǎn))s->next=L->next;L->next=s;//將s結(jié)點(diǎn)插入到逆置表的表頭}}2.3

知識(shí)拓展——單鏈表的其他操作單鏈表的逆置：2024/9/2657voidMergeLinkList(LinkList&La,LinkList&Lb){LinkListpa=La->next;//pa指向La中當(dāng)前考察的結(jié)點(diǎn)LinkListpb=Lb->next;//pb指向Lb中當(dāng)前考察的結(jié)點(diǎn)LinkListpc=La;//pc指向Lc中當(dāng)前的表尾結(jié)點(diǎn)while(pa!=NULL&&pb!=NULL)

{if