第2章線性表(2)數據結構

第二章線性表(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不空，Ａ＜Ｂ；如果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){//輸入各項的系數和指數，建