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

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

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

i－1和一個后繼a

i+1。2.1.1線性表的概念2024/9/26102.1知識學(xué)習(xí)2.1.2線性表的順序存儲結(jié)構(gòu)及基本操作2.1.2.1順序結(jié)構(gòu)342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素例：（34,23,67,43）2024/9/2611例：（34,23,67,43）34236743存儲空間的起始位置4用什么屬性來描述順序表？順序表的容量（最大長度）順序表的當前長度2024/9/26122.1知識學(xué)習(xí)2.1.2線性表的順序存儲結(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;}初始化操作——創(chuàng)建空表

datalength02.1.2.2順序表基本操作的實現(xiàn)2024/9/2614初始化操作——創(chuàng)建長度為n的順序表2.1.2.2順序表基本操作的實現(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順序表基本操作的實現(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順序表基本操作的實現(xiàn)intListLength_Seq(SeqList&L){ returnL.length;}算法描述：2024/9/2617按值查找元素：535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

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

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

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

1）為止，將每一個元素均后移一個存儲單元，將第i個元素的存儲位置空出。④將新元素e寫入到第i個元素處，即下標為i

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

順序表基本操作的實現(xiàn)2024/9/2625例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出算法的描述；3.分析時間復(fù)雜度。535a1a2a3a401234422412334a51224422.1.2.2順序表基本操作的實現(xiàn)2024/9/2626刪除操作算法描述：2.1.2.2順序表基本操作的實現(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）增強通用性（2）增強靈活性（3）增強適應(yīng)性2024/9/26282.1.3線性表的鏈接存儲及基本操作鏈表：線性表的鏈接存儲結(jié)構(gòu)。存儲思想：用一組任意的存儲單元存放線性表的元素。靜態(tài)存儲分配順序表事先確定容量鏈表動態(tài)存儲分配運行時分配空間連續(xù)不連續(xù)零散分布2024/9/26292.1.3.1鏈式存儲結(jié)構(gòu)例：(a1,a2

,a3,a4)的存儲示意圖存儲特點：邏輯次序和物理次序不一定相同。元素之間的邏輯關(guān)系用指針表示。0200020803000325…………a10200a20325a30300a4∧2024/9/26300200020803000325…………a10200a20325a30300a4∧結(jié)點數(shù)據(jù)域指針域單鏈表是由若干結(jié)點構(gòu)成的；單鏈表的結(jié)點只有一個指針域。data：存儲數(shù)據(jù)元素next：存儲指向后繼結(jié)點的地址datanext單鏈表的結(jié)點結(jié)構(gòu)：數(shù)據(jù)域指針域2.1.3.1鏈式存儲結(jié)構(gòu)2024/9/2631typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點結(jié)構(gòu)：如何申請一個結(jié)點？2.1.3.1鏈式存儲結(jié)構(gòu)2024/9/2632s=newNode;typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node,*LinkList;datanext單鏈表的結(jié)點結(jié)構(gòu)：……sNode2.1.3.1鏈式存儲結(jié)構(gòu)2024/9/2633s=newNode;datanext……sNode如何引用數(shù)據(jù)元素？s->data;(*s).data;data如何引用指針域？nexts->next;2.1.3.1鏈式存儲結(jié)構(gòu)2024/9/26340200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表頭指針：指向第一個結(jié)點的地址。尾標志：終端結(jié)點的指針域為空。2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/26350200020803000325…………a10200a20325a30300a4∧heada1a2an∧非空表head=NULL空表空表和非空表不統(tǒng)一，缺點？如何將空表與非空表統(tǒng)一？2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2636頭結(jié)點：在單鏈表的第一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一。非空表heada1a2an∧空表head∧2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/26372.1.3.2單鏈表基本操作的實現(xiàn)voidInitList_L(LinkList&L){ L=newNode; L->next=NULL;}初始化——創(chuàng)建空的單鏈表2024/9/26382.1.3.2單鏈表基本操作的實現(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個元素創(chuàng)建單鏈表2024/9/26392.1.3.2單鏈表基本操作的實現(xiàn)voidShow_L(LinkListL){ LinkListp=L->next; while(p) { cout<<p->data<<"";//輸出結(jié)點數(shù)據(jù)域 p=p->next; } cout<<endl;}遍歷單鏈表2024/9/26402.1.3.2單鏈表基本操作的實現(xiàn)intListLength_L(LinkListL){LinkListp=L->next;intk=0;while(p)

{k++;//計數(shù)p=p->next;}returnk;}求單鏈表長度。2024/9/26412.1.3.2單鏈表基本操作的實現(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)如何實現(xiàn)結(jié)點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單鏈表基本操作的實現(xiàn)2024/9/2643注意分析邊界情況——表頭、表尾。

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

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

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

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

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

pqpq表尾的特殊情況：雖然被刪結(jié)點不存在，但其前驅(qū)結(jié)點卻存在。p->next=NULLheada1ana2∧2.1.3.2單鏈表基本操作的實現(xiàn)2024/9/2648算法描述——偽代碼1.工作指針p初始化；累加器j清零；2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點；3.若p不存在或p不存在后繼結(jié)點，則拋出位置異常；否則，否則刪除結(jié)點p的后一個結(jié)點。2.1.3.2單鏈表基本操作的實現(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單鏈表基本操作的實現(xiàn)2024/9/2650將單鏈表中所有結(jié)點的存儲空間釋放。

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

2.1.3.2單鏈表基本操作的實現(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單鏈表基本操作的實現(xiàn)2024/9/26522.2知識應(yīng)用2024/9/26532.2知識應(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中刪除第一個數(shù)據(jù)元素賦給e

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

}}2.3知識拓展——順序表的其他操作求集合的并集：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知識拓展——順序表的其他操作有序表的插入：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所指鏈表中刪除第一個結(jié)點(s結(jié)點)s->next=L->next;L->next=s;//將s結(jié)點插入到逆置表的表頭}}2.3

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

{if