




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第二章線性表(2)本講重點:順序表的應用線性鏈表的表示、實現、操作循環(huán)鏈表的定義雙向循環(huán)鏈表的定義、操作線性表的典型應用回顧線性表的定義,ADT線性表的順序存儲
constLIST_INIT_SIZE=100;//表初始分配空間constLISTINCREMENT=10;//空間分配增量
typedef
struct{ElemType*elem;//存儲空間
intlength;//當前長度
int
listsize;//當前存儲容量
intLISTINCREMENT;//可增加存儲空間
}SqList;StatusInitList_Sq(SqList&L){//構造空表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*
sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE; returnOK;}//InitList_Sq線性表的初始化(創(chuàng)建一個空的線性表)刪除線性表中的第i個元素StatusListDelete_Sq(SqList&L,intI,ElemType&e){//刪除L中第i個元素,后面的元素前移
if((i<1)||i>L.length))returnERROR;P=&L.Elem[i-1];e=*p;q=L.Elem+L.length-1;for(++p;p<=q;++P)*(p-1)=*p;--L.length;returnOK;}//ListDelete_Sq
順序表的應用
例1設A=(a1,a2,a3,…,am),
B=(b1,b2,b3,…,bn)為兩個線性表,試寫出比較A,B大小的算法。比較原則:首先去掉A,B兩個集合的最大前綴子集之后如果A,B為空,則A=B;如果A空B不空,A<B;如果B空A不空,則A>B;如果A和B均不空,則首元素大者為大。分析:268915Bi26811AiA[i]>B[i]A[i]<B[i]A[i]=B[i]A.len>B.lenA.len<B.lenA.len=B.len依次比較線性表A和B的相同下標上的元素:IntCompare(SqListA,SqListB)
{//若A<B返回–1,A=B返回0,A>B返回1j=0;while(j<A.length&&j<B.length){if(A.elem[j]<B.elem[j])return–1;elseif(A.elem[j]>B.elem[j])return1;elsej++;}if(A.length==B.length)return0;elseif(A.length<B.length)return–1;elsereturn1;}//compare
例:設計一個算法,用盡可能少的輔助空間將順序表中前m個元素和后n個元素進行整體互換。即將線性表(a1,a2,…,am,b1,b2,…,bn)(b1,b2,…,bn,a1,a2,…,am)
a1a2amb1b2bn參考算法:取一臨時空間,將b1放入臨時空間,a1-am全部后移一個位置,如此b2,b3,直到bn.分析下面的過程voidexchange1(SqList&L,intm,intn){//線性表分成兩個部分后,兩部分倒置
for(i=0;i<n;i++){w=L.Elem[i+m];for(j=m;j>=1;j--)L.Elem[i+j]=L.Elem[i+j-1];
L.Elem[i]=w;}}//exchange1
算法特點:犧牲時間節(jié)省空間分析:如果另外申請空間m+n個存儲單元,將b,a分別寫入.時間復雜度將為n+m,即:犧牲空間節(jié)省時間。2.3線性表的鏈式表示和實現順序表的局限:插入、刪除時要移動大量的元素,耗費大量時間。鏈式表示:用一組任意的存儲單元存儲線性表存儲單元不要求連續(xù):物理結構不反應邏輯結構不可以隨機存取,但插入和刪除方便需要兩個域:一個表示數據本身;一個表示數據元素間的先后關聯?!粋€結點。結點中表示關聯的部分為指針域,內部存放指針或鏈。n個結點鏈接成一個鏈表。2.3.1線性鏈表線性鏈表的物理存儲結構(Zhao,Qian,Sun,Li,Zhou,Wu,Zheng,Wang)ZhaoQianSunLiWangZhengWuZhou數據域指針域存儲地址171319253137434931頭指針LZhaoQianSunWang^線性鏈表(單鏈表)的定義:
typedefstruct
LNode{
ElemTypedata;
struct
Lnode*next;}Lnode,*LinkListLa1aiai-1an^La1aiai-1an^帶頭結點的鏈表 StatusInitList_L(LinkList&L){ //建立頭結點,其next為空 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK; }^L空表線性鏈表的基本操作:初始化線性鏈表
GetElem在單鏈表中的實現GetElem_L(L,i,&e)StatusGetElem_L(LinkListL,inti,ElemType&e){ //L為帶頭結點的單鏈表的頭指針 //當第i個元素存在時,將值返回給e,OK,否則ERROR P=L->next,j=1; While(p&&j<i){ P=p->mext;++j; } if(!p||j>i)returnERROR; e=p->data; returnOK;}//GetElem_L提問:順序表與單鏈表在取第i個元素的操作上有什么不同?插入操作:在第i個結點之前插入一個元素e分析:1.插入的過程:La1aiai-1an^eP122.尋找插入的位置:3.考慮空間問題qStatusListInsert_L(LinkList&L,intI,ElemTypee){//在線性鏈表的第i個元素之前插入一個元素e
p=(LinkList)malloc(sizeof(LNode));if(!p)exit(OVERFLOW);p->data=e;q=L;j=0;while(q&&j<i-1){q=q->next;++j;}if(!q||j>i-1)returnERROR;p->next=q->next;q->next=p;
returnOK;}//ListInsert_L時間復雜度分析:O(n)課堂練習:寫出單鏈表刪除結點的算法,并分析算法時間復雜度。
寫出單鏈表的定位算法,并分析算法的時間復雜度。
LNode*LocateElem_L(LinkListL,ElemTypee){//在L中找到第一個值和e相同的結點,返回其//地址,若不存在,返回空值。
if(!L)returnNULL;p=L;while(P&&P->data!=e)p=p->next;returnp;}
時間復雜度:O(n)線性鏈表的復雜操作例:將兩個有序鏈表歸并為一個新的有序鏈表。
分析:將Lb中的元素插入到La,使其有序。La412620^Lb59731^papbpa->data
pb->data
>將pb插入到pa的前面插入過程中,注意臨時指針的使用。
VoidMergeList(LinkList&La,LinkList&Lb){//歸并兩個非遞減單鏈表La,Lb,形成新的La pa=La->next;pb=Lb->next;q=La;while(pa&&pb){if(pa->data<=pb->data){q=pa;pa=pa->next;}else{t=pb;pb=pb->next;t->next=pa;q->next=t;q=t;}if(pb)q->next=pb;}
時間復雜度分析:O(n)
2.3.2循環(huán)鏈表循環(huán)鏈表:線性表的另一種鏈式存儲結構。Ha1anH特點:從表的任何位置出發(fā),都可以找到其他結點;操作與單鏈表的差別:判斷表尾的條件:P->next=H空表循環(huán)鏈表2.3.2雙向鏈表每一個結點有兩個指針域:一個指向直接后繼;另一個指向直接前驅。Ha1a2
^^H^^雙向鏈表存儲結構:
typedef
struct
DuLNode{
ElemTypedata;
struct
DuLNode*prior;
struct
DuLNode*next;}DuLNode,*DuLinkList;雙向循環(huán)鏈表Ha1
a2
H雙向循環(huán)鏈表的基本操作在第i個結點的前面插入一個新元素ecfeSPS->next=P;S->prior=P->prior;P->prior->next=s;P->prior=S;插入算法:
statusListInsert_Dul(DuLinkList&L,intI,ElemTypee){//在帶頭結點的雙向循環(huán)鏈表中的第i個位置插入元素ej=0;p=L;while(j<i-1&&P){p=p->next;j++;}if(!P)returnERROR;//表的長度小于is=(DuLinkList)malloc(sizeof(ElemType));if(!s)exit(OVERFLOW)//空間不夠,溢出s->data=e;s->next=p->next;s->prior=p;p->next->prior=s;p->next=s; returnOK;}課堂練習1、在線性表的下列存儲結構中,讀取元素花費的時間最少的是()A)單鏈表
B)雙向鏈表
C)循環(huán)鏈表
D)順序表2、線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址
A) 必須是連續(xù)的
B) 部分地址必須是連續(xù)的C)一定是不連續(xù)的
D) 連續(xù)或不連續(xù)都可以3、在()鏈表中,不能從任一結點出發(fā)訪問到表中的所有結點的是:A)單鏈表
B)單向循環(huán)鏈表
C)雙向循環(huán)鏈表
D)循環(huán)鏈表請當場回答問題,將答案通過手機短信發(fā)送過來,課后點播的同學不能發(fā)短信編輯短信:“C509+短信內容”移動用戶發(fā)送至6255211528聯通用戶:7255211528如:如果上述3題的答案是BCC,“C504BCC”課程結束前公布答案2.4線性表的應用——多項式運算一元多項式的形式:
Pn(x)=p0+p1x+p2x2+…+pnxn線性表的表示方法:P=(p0,p1,p2,···,pn)一元多項式的運算設m<n,則Rn(x)=Pn(x)+Qm(x)R=(p0+q0,p1+q1,···,pm+qm,pm+1,···,pn)如何存儲?——順序/鏈式抽象數據類型一元多項式的定義:ADT=(D,R,P)鏈表表示的一元多項式定義Typedef
struct
PNode{floatcoef;//浮點數
intexpn;//整數指數
struct
Pnode*next;}ElemType,term;Typedef
LinkListpolynomial;
例:多項式的鏈表建立VoidCreatePolyn(polynomail&p,intm){//輸入各項的系數和指數,建
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權】 ISO/TR 41019:2024 EN Facility managements role in sustainability,resilience and adaptability
- 2025年度校園基礎設施裝修改造工程合同
- 2025年度房產居間合同:旅游地產項目開發(fā)合作協(xié)議
- 2025年度標前協(xié)議模板:XX基礎設施建設合作前期協(xié)議
- 2025年度酒店客房預訂客戶投訴處理合同
- 2025年度博物館安防監(jiān)控設備采購與安裝合同
- 學期班級教學活動工作任務計劃
- 學期閱讀推廣活動計劃
- 社區(qū)文藝活動計劃
- 生物教育在新時代的挑戰(zhàn)與機遇計劃
- EN50317-2002-鐵路應用集電系統(tǒng)受電弓和接觸網的動力交互
- 人教版美術八下課程綱要
- 項目部組織機構框圖(共2頁)
- 機動車登記證書
- ASTM-D471橡膠性能的標準試驗方法-液體影響(中文版)(共24頁)
- 鉭鈮礦開采項目可行性研究報告寫作范文
- 小升初數學銜接班優(yōu)秀課件
- 中國十大名茶(課堂PPT)
- 出口食品生產企業(yè)備案自我評估表
- 鋼結構廠房招標文件
- 肥城市死因漏報調查方案PPT課件
評論
0/150
提交評論