第二章線性表

1、第二章 線性表 線性結構：在數(shù)據元素的非空集中，存在唯一的一個首元素，存在唯一的一個末元素，除首元素外每個元素均只有一個直接前驅，除末元素外每個元素均只有一個直接后繼。第一節(jié) 邏輯結構 形式定義： Linear_list=(D，S，P) D = ai| aiElemSet, i=0,1,2,n-1 S = | ai-1,aiD, i=1,2,n-1為序偶，表示前后關系 基本操作P：插入、刪除、修改，存取、遍歷、查找。 void ListAppend(List L, Elem e) ; void ListDelete(List L, int i) ; int SetElem(List L, in

2、t i, Elem e); int GetElem(List L, int i, Elem &e); int ListLength(List L); void ListPrint(List L); int LocateElem(List L, Elem e);合并、分解、排序 基本操作的用途：集合的并、交、差運算 有序線性表的合并、多項式的運算 例：利用線性表LA和LB分別表示集合A和B，求A=AB。void union(List &La，List Lb) int La_len, Lb_len; La_len=ListLength(La); / 計算表長 Lb_len=ListLength(L

3、b); for(i=1; i=i; j-) A.elemj+1 = A.elemj; A.elemi=e; A.length+; 2、刪除ai：a0a1ai-1aiai+1an-1 如何移動元素？a0a1ai-1ai+1an-1void SqList_Delete(SqList A, int i) for(j=i+1; jA.length; j+) A.elemj-1 = A.elemj; A.length-;三、效率分析 插入、刪除時，大量時間用在移動元素上。 設插入位置為等概率事件，時間復雜度？例1：增序順序表的合并，設其中無相同元素Status SqList_Merge(SqList L

4、a,SqList Lb,SqList &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; Lc.listsize=Lc.length=La.length+Lb.length; Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) return ERROR; pa=La.elem; pb=Lb.elem; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last

5、 & pb=pb_last) if(*pa=*pb) *pc=*pa; pc+; pa+; else *pc=*pb; pc+; pb+; while(pa=pa_last) *pc=*pa; pc+; pa+; while(pb 1 2 3 4 5 6 7 8 9void del(int A,int n) int i,k; / k是0元素的個數(shù) for(k=0,i=0; inext=p-next; p-next=q; 在*p之前插入？ 時間復雜度？ 各種插入方法：首插：插入在首結點前；尾插：入在尾結點后。有序插：保持結點的順序，插在表中間； 編程細節(jié)：首插：修改頭指針尾插：鏈表為空時，修改頭

6、指針。有序插：鏈表為空時，修改頭指針。鏈表不空時，可能修改頭指針/ 首插LNODE * LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head; return(newp); / 遍歷打印void LinkList_Print(LNODE *head) LNODE *p; for(p=head; p; p=p-next) printf(.,p-data);/ 尾插LNODE * LinkList_InsertAfterTail(LNODE *head, LNODE *newp) LNODE *p; if(head=NU

7、LL) newp-next=NULL; return(newp); for(p=head-next; p-next; p=p-next); newp-next=NULL; p-next=p; return(head); 簡化程序細節(jié)的方法：特殊頭結點/ 首插（有特殊頭結點）void LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head-next; head-next=newp;/ 尾插（有特殊頭結點）void LinkList_InsertAfterTail(LNODE *head, LNODE *newp) LN

8、ODE *p; for(p=head; p-next; p=p-next); newp-next=NULL; p-next=p; 2、刪除結點 刪除*p的后繼結點： q=p-next; p-next=q-next; free(q); 刪除*p？ 時間復雜度？ 各種刪除方法：首刪除： 尾刪除： 思考查找刪除：思考/ 首刪除（有特殊頭結點）void LinkList_DeleteHead(LNODE *head) LNODE *p; if(head-next=NULL) return; p=head-next; head-next=p-next; free(q);三、單個鏈表的例程（設以下鏈表有特

9、殊頭結點）例1、按序號查找：取鏈表第i個結點的數(shù)據元素。i1,n/ 注意計數(shù)次數(shù)的邊界條件Status LinkList_GetElemBySID(LNODE *head,int i,ElemType &e) LNODE *p; int j;for(p=head-next,j=1; p & jnext; if(p=NULL) return ERROR; e=p-data; return OK;例2、按值查找：取鏈表中值為e的結點的地址。LNODE * LinkList_GetElemByValue(LNODE *head, ElemType e) LNODE *p; for(p=head-ne

10、xt; p; p=p-next)if(p-data=e) break; return(p);例3、釋放鏈表中所有結點。void LinkList_DeleteAll(LNODE *head) LNODE *p; while(head) p=head-next; free(head); head=p; 例4、復制線性鏈表的結點/ 適合有/無特殊頭結點的鏈表LNODE * LinkList_Copy(LNODE *L) LNODE *head=NULL,*p,*newp,*tail; if(!L) return(NULL); for(p=L; p; p=p-next) newp=(LNODE *)

11、malloc(sizeof(LNODE); if(head=NULL) head=tail=newp; else tail-next=newp; tail=newp; newp-data=p-data; tail-next=NULL; return(head);例5、線性鏈表的逆序LNODE * LinkList_Reverse(LNODE *head) LNODE *newhead,*p;newhead=(LNODE *)malloc(sizeof(LNODE);newhead-next=NULL; while(head-next!=NULL) p=head-next; head-next=

12、p-next; /卸下 p-next=newhead-next; newhead-next=p; /安裝 free(Head); return(newhead);例6、利用線性表的基本運算，實現(xiàn)清除L中多余的重復節(jié)點。 3 5 2 5 5 5 3 5 6= 3 5 2 6void LinkList_Purge(LNODE *head) LNODE *p, *q, *prev_q; for(p=head-next; p; p=p-next) for(prev_q=p,q=p-next; q; ) if(p-data=q-data) prev_q=q-next; free(q); q=prev_q

13、-next; else prev_q=q; q=q-next; 四、多個鏈表之間的例程（設以下鏈表有特殊頭結點）例1、增序線性鏈表的合并，設其中無相同元素。/破壞La和Lb，用La和Lb的結點組合LcLNODE *LinkList_Merge(LNODE *La,LNODE *Lb) LNode *pa,*pb,*pctail,*Lc;Lc=pctail=La; / Lc的頭結點是原La的頭結點pa=La-next; pb=Lb-next; free(Lb); while(pa!=NULL & pb!=NULL) if(pa-data data) pctail-next=pa; pctail=

14、pa; pa=pa-next; else pctail-next=pb; pctail=pb; pb=pb-next; if(pa!=NULL) pctail-next=pa; else pctail-next=pb; return(Lc);例2、無序線性鏈表的交集AB/不破壞La和Lb，/新鏈表Lc的形成方法：向尾結點后添加結點 LNODE *LinkList_Intersection(LNODE *La,LNODE *Lb) LNode *pa,*pb,*Lc,*newp,*pctail;Lc=pctail=(LNODE *)malloc(sizeof(LNODE); for(pa=La-

15、next; pa; pa=pa-next) for(pb=Lb-next; pb; pb=pb-next)if(pb-data=pa-data) break;if(pb) newp=(LNODE *)malloc(sizeof(LNODE); newp-data=pa-data; pctail-next=newp; pctail=newp;pctail-next=NULL; return(Lc);作業(yè)與上機：(選一)1、A-B2、AB3、AB4、(A-B)(B-A)第五節(jié) 循環(huán)鏈表 尾結點的指針域指向首結點。 實際應用：手機菜單 遍歷的終止條件？例：La、Lb鏈表的合并 / 將Lb鏈表中的數(shù)據結點接在La鏈表末尾void Connect(LNODE * La，LNODE * Lb) LNODE *pa, *pb;for(pa=La-next; pa-next!=La; pa=pa-next);for(pb=Lb-next; pb-next!=Lb; pb=pb-next); pa-next=Lb-next; pb-next=La; free(Lb);第六節(jié) 雙向鏈表 非空表 空表 t