第二章 线性表 1 线性表的逻辑定义、基本运算 线性表：由n个数据元素a1, a2, , an组成的有限序列，长度为n。 例：成绩单，英文字母，多边形，实数的计算机表示，多项式的计算机表示等。 基本运算： 置空表： InitList(&L); 求表长： ListLength(L)； /返回一个整数 取表中第 i 个结点：GetElem(L, i, &e)；/用 e 返回 查找： Locate(L, x)；/x 是否位于 L 中， /是返回 true 否则返回 false 插入： ListInsert(&L, i, e)； /第 i 位置插入 e，长度加 1 删除：ListDelete(&L, i, &e)； /删除第 i 个元素，放入 e 中 其它运算：线性表的拆分，合并，求差，求交，复制， 例：La = La U Lb / 将 La 与 Lb 元素合并，得到新的线性表 La void ListUnion (List &La, List Lb) n = ListLength(La); for (i=0; i=ListLength(Lb); i+) GetElem(Lb, i, &x); If (LocateNode(La, x)=0) ListInsert(La, +n, x); 例：求两单调增加序列的并集(仍单调增加) La=1, 4, 5, 8, 10 Lb=2, 5, 7, 8, 12, 15 Lc=La U Lb =1, 2, 4, 5, 7, 8, 10, 12, 15 void SetMerge(List La, List Lb, List &Lc) La.len = ListLength(La); Lb.len = ListLength(Lb); / InitList(Lc); if (La.len =0) for (i=0; iLb.len; i+) GetElem (Lb, i, &bi); ListInsert(Lc, i, bi); if (Lb.len =0) for (i=0; iLa.len; i+) GetElem (La, i, &ai); ListInsert(Lc, i, ai); if (La.len=0)|(Lb.len=0) return; / La, Lb 均非空 i=j=0; k=0; GetElem(La, i, &ai); GetElem(Lb, j, &bj); While (iLa.len)|(jLb.len) If (ai=bj) ListInsert(Lc, k, ai); i+; k+; if (iLa.len) GetElem(La, i, &ai); else ai = +; else ListInsert(Lc, k, bj); j+; k+; if (jelem=(Elemtype*)malloc(ListSize* sizeof(Elemtype); If (!L-elem) exit(OVERFLOW); L-length = 0; Return true; main() SqList *L; L = (SqList *)malloc(sizeof(SqList ); InitList(L); /删除第 i 个结点 void ListDelete(SqList *L, int i, Elemtype *e) if (i=L-length) printf(“position errorn”); return error; *e = L-elemi; /保存被删除结点值 for (j=i; jlength; j+) L-elemj=L-elemj+1; /结点前移 L-length-; /表长减一 return; 3 线性表的链式表示和实现 链表特点：用指针指明逻辑上相邻元素之间的关系。 线性链表(单链表) 结点：数据域+指针域 typedef struct node Lnode; struct node ElemType data; Lnode *next; 100wang220 105zhao 185 150zhang180 155Wu 105 180Li 100 185sun head 建立单链表 Lnode *LinkList; LinkList CreateList(int n, ElemType *elem) Lnode *head, *p, *r; head =(Lnode *)malloc(sizeof(Lnode); r = head; For (int i=0; idata=elemi; r-next=p; r=p; r-next=NULL; return head; head E0 E1 En-1 null 单链表的检索 int GetListElem(Linklist L, int i, ElemType *e) Lnode *p; p=L-next; j=1; while (p&(jnext; j+; if (!p|(ji) return FAIL; *e =p-data; /取第 i 个元素 return true; 插入运算 s head p s-next = p-next; p-next = s; int InsertList(Linklist L, int i, ElemType b) Lnode *p, *s; p=L-next; j=1; while (p&jnext; j+; Ei Ei+1En-1 b null if (!p|ji) return FAIL; s=(Lnode *)malloc(sizeof(Lnode); s-data = b; s-next=p-next; p-next=s; return true; 删除运算 head p q p-next=q-next; free (q); 例： La, Lb 为两个带头结点的单链表， 均按结点数值递增，将这两个单链表合并为一个有序的单链表。 /Lc = La ? La U Lb void MergList(Linklist La, Linklist Lb, Linklist Lc) Lnode *pa, *pb, *pc; pa =La-next; pb=Lb-next; Lc=pc=La; Ei Ei+1En-1 null While (pa&pb) If (pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc = pb; pb = pb-next; pc-next=pa?pa:pb; /插入剩余部分 free (Lb); /释放 Lb 头结点 0 8 13.5 6 22.2 1 36.0 5 45.5 3 57.8 9 64.3 4 79.5 0 81.5 2 98.5 7 4 静态链表 ? 用一维数组来描述线性链表 ? 下一元素编号代替指针 #define MAXSIZE 100 typedef struct ElemType memb; Int cur; SlinkListMAXSIZE; 思考题：设计算法将静态链表从小到大排序。 5 双向链表 typedef struct dLnode ElemType data; Struct dLnone *prior, *next; DLNode; e A B C s p ? 在结点 p 前插入新结点 s s-next = p; s-prior=p-prior; s-prior-next=s; p-prior=s; ? 删除结点 p： p-prior-next=p-next; p-next-prior=p-prior; free(p); 例：设有一个带头结点的循环双链表，但每一结点 prior指针为空，试写一算法将此表改为真正的双链表。 void LinklistRedirection(Dlinklist head) DLNode *p, *q; p=head-next; q=head; while (p!=head) p-prior=q; q=p; /p,q 后移 p=p-next; head-prior=q; 练习： p head e A B C (1) 已知两个单链表 A 和 B 分别表示两个集合，其元素值递增有序，试写一算法求 A 和 B 的交集 C，要求C 同样以元素值递增单链表形式存储。 (2) 设有一个带头结点的双向循环链表，head 为链表的头指针，试写一算法，实现在值为 x 的结点之前插入一个值为 y 的结点。 6 错误分析与复杂性分析 错误删除算法 void DeleteList(List L) Lnode *p; p=L-next; / L 头 L-next=null; while (p!=null) Free (p); p=p-next; 正确删除算法 void DeleteList(List L) Lnode *p， *tmp; p=L-next; / L 头 L-next=null; while (p!=null) tmp=p-next; free (p); p=tmp; 复杂性分析 ? 顺序线性表 取值复杂度 O(1) 插入、删除复杂度 O(n) ? 单向链表 取值复杂度 O(n) 插入、删除复杂度 O(1) project 2. 以多边形表示为例实现单向链表的创建、结点插入、结点删除以及单向链表向顺序线性表的转换操作。