第二章线性表

1、第二章 线性表 线性结构：在数据元素的非空集中，存在唯一的一个首元素，存在唯一的一个末元素，除首元素外每个元素均只有一个直接前驱，除末元素外每个元素均只有一个直接后继。第一节 逻辑结构 形式定义： 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元素的个数 for(k=0,i=0; inext=p-next; p-next=q; 在*p之前插入？ 时间复杂度？ 各种插入方法：首插：插入在首结点前；尾插：入在尾结点后。有序插：保持结点的顺序，插在表中间； 编程细节：首插：修改头指针尾插：链表为空时，修改头

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); 简化程序细节的方法：特殊头结点/ 首插（有特殊头结点）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个结点的数据元素。i1,n/ 注意计数次数的边界条件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、利用线性表的基本运算，实现清除L中多余的重复节点。 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);作业与上机：(选一)1、A-B2、AB3、AB4、(A-B)(B-A)第五节 循环链表 尾结点的指针域指向首结点。 实际应用：手机菜单 遍历的终止条件？例：La、Lb链表的合并 / 将Lb链表中的数据结点接在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);第六节 双向链表 非空表 空表 t