Microsoft PowerPoint - 2线性表.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 2线性表.ppt [兼容模式]"

幼圳艾
5 years ago
Views:

1 2 线性表董洪伟 1

2 主要内容线性表的类型定义即抽象数据类型顺序实现即用一连续的存储空间来表示链式实现即用链表实现一元稀疏多项式链表实现 2

3 线性表的类型定义线性表 n 个元素的有限序列数据项元素 ( 记录 ) 姓名学号性别年龄班级健康状况王小林男 18 计 91 健康陈红女 20 计 91 一般刘建平男 21 计 91 健康

4 线性表的类型定义线性表的长度元素的个数 n 如果 n = 0, 则为空表位序非空线性表中的每个元素都有一个确定的位置,a i 是第 i 个元素,i 称为数据元素 a i 在线性表中的位序 4

5 线性表的抽象数据类型 ADT List{ 数据关系 : 数据元素具有线性关系 (a1,a2,,an) 基本操作 : // 构造一个空的线性表 L InitList(List &L ) // 销毁线性表 L DestroyList(List &L ) // 将 L 重置为空表 ClearList(List &L ) 5

6 线性表的抽象数据类型 //L 是空表吗? IsEmpty(List L ) // 返回 L 中数据元素的个数 ListLength(List L ) // 把 L 中第 i 个元素的值赋给 e GetElem(List L,int i, ElemType &e ) // 把 e 值赋给 L 中第 i 个元素 SetElem(List L,int i, ElemType e ) 6

7 线性表的抽象数据类型 // 查询 L 中第 1 个与 e 满足关系 compare() // 的数据元素的位序 FindElem(List L, ElemType e, compare() ) // 在 L 中第 i 个位置之前插入新的数据元素 e,l 的长度加 1 ListInsert(List &L,int i, ElemType e ) // 删除 L 的第 i 个数据元素, 并把其值赋给 e,l 的长度减 1 ListDelete(List &L,int i, ElemType &e ) } // 依次对 L 的每个数据元素调用函数 visit() ListTraverse(List L, visit() ) 7

8 线性表的顺序表示和实现即用一连续的存储空间来表示比如数组 :ElemType array[n]; 或动态分配的一块空间 : ElemType *array= (ElemType*) malloc(n*sizeof(elemtype)); ElemType *array= (ElemType*) realloc (p,n*sizeof(elemtype)); 8

9 动态分配顺序存储结构 #define LIST_INIT_CAPACITY 100 #define LISTINCREMENT 10 typedef struct{ ElemType *elem; int capacity; int n; }SqList; elem capacity n a1 a2 a3... 可以把 ElemType 定义为任何类型 : typedef int ElemType; 9

10 初始化 bool InitList_Sq(SqList &L){ } L.elem = (ElemType*)malloc (LIST_INIT_CAPACITY * if(!l.elem) sizeof(elemtype)); return false; L.capacity = LIST_INIT_CAPACITY; L.n = 0; return true; elem capacity n L 100 0

11 插入 ListInsert(SqList& L, int i, ElemType e) 在线性表 L 的第 i 个元素前面, 插入元素 e i = 3 25 L 必须向下移动 n-i+1 个元素 11

12 插入 ListInsert(SqList& L, int i, ElemType e) 在线性表 L 的第 i 个元素前面, 插入元素 e i = 3 25 L

13 插入 ListInsert(SqList& L, int i, ElemType e) 在线性表 L 的第 i 个元素前面, 插入元素 e i = 3 25 L

14 插入 ListInsert(SqList& L, int i, ElemType e) 在线性表 L 的第 i 个元素前面, 插入元素 e i = 3 25 L

15 插入 ListInsert(SqList& L, int i, ElemType e) 在线性表 L 的第 i 个元素前面, 插入元素 e i = 3 25 L

16 bool ListInsert_Sq(SqList &L,int i,elemtype e){ // 判断 i 是否合法 if(i < 1 i > L.n + 1) return false; // 若线性表空间不足, 再分配一些空间 if(l.n >= L.capacity) { ElemType *temp = (ElemType *) realloc(l.elem, (L.capacity+LISTINCREMENT)* sizeof(elemtype) ); if(temp==0) return false; free(l.elem); L.elem = temp; L.capacity += LISTINCREMENT; }

17 } // q 指向插入的位置 ElemType * q = &(L.elem[i-1]); // p 指向最后一个元素, // 从 p 到 q 的所有元素后移一个单元 ElemType *p; for(p = &(L.elem[L.n - 1]); p >= q; --p) *(p+1) = *p; *q = e; // 写进待插入的元素 e ++ L.n; // 表长加 1 return true; 17

18 q = &(L.elem[i-1]); // q 指向插入的位置 // p 指向最后一个元素, // 从 p 到 q 的所有元素后移一个单元 for(p=&(l.elem[l.n-1]); p>=q; --p) *(p+1) = *p; } *q = e; // 写进待插入的元素 e ++ L.n; // 表长加 1 return true; i=3, 即插入在第三个元素之前 q p a b ce d f g

19 插入操作的时间复杂度很显然, 插入操作的复杂度由需要移动的元素的个数决定而需要移动元素的个数由插入位置决定 i = n+1 时, 需要移动 0 个 i = n 时 :1 个... i = 1 时 :n 个即 : 需要移动的元素个数 = n+1-i 19

20 插入操作的时间复杂度最差情况 T(n) = O(n) 平均情况呢? 一共有 1,2,...,n+1,n+1 个可能的插入位置, 在第 i 个位置上插入的概率是 1/(n+1) 所以平均需要移动元素的个数 n = + = = n n n( n+ 1) ( n 1 i) + i= 1 n+ 所以平均复杂度 = O(n) 20

21 删除 ListDelete( &L, i, &e ) 删除第 i 个元素, 其值赋给 e i = 3 L 必须向上移动 n-i+1 个元素 21

22 bool ListDelete_Sq(SqList &L, int i, ElemType &e) { if((i < 1) (i > L.length)) return false; ElemType *p,*q; p = &(L.elem[i-1]); //p 指向被删除的节点 e = *p; //e 得到被删除的节点的值 // q 指向最后一个节点 q = L.elem + L.n - 1; // 从 p+1 到 q 的所有节点前移一个单元 for(++ P; p <= q; ++ p) *(p-1) = *p; } -- L.n; // 表长减 1 return true; 22

23 删除操作的时间复杂度是多少? 23

24 特点及优缺点特点各单元的内存地址连续优点可随机访问任一元素即访问任何一个元素所用时间都相同缺点插入删除操作需移动大量元素算法复杂度 = O(n) 24

25 线性表的链式表示和实现特点每个元素的存储地址任意使用指针相链接节点数据域指针域

26 存储结构 typedef struct node{ ElemType data; struct node *next; }LNode; 头节点数据域为空 a1 a2 a3 a4

27 为什么要有一个头结点? 因为原来的第一个结点有点儿特殊 : 第一个节点的前面没有结点 ( 前驱结点 ) 而其它节点的前面都有前驱结点这个特殊性导致了链表操作的很多算法都必须分第一个结点和非第一个结点两种情况来讨论所以增加一个无用的空结点, 这样消除了这种不一致, 从而简化了算法

28 初始化 typedef LNode* LkList; bool InitLkList(LkList &L); bool InitLkList(LNode* &L); bool InitLkList(LNode* &L){ L = (LNode *) malloc (sizeof(lnode)); if(!l) return false; L->next = 0; return true; } L 0

29 存取操作要访问线性表的第 i 个元素, 要从表头起沿着指针一个一个元素的查找显然, 访问第 i 个节点所需时间由 i 决定所以存取操作复杂度 = O(n) L a1 a2 i a3 a4

30 bool GetElem_L (LNode* L, int i, ElemType &e) { LNode* p = L->next; int j = 1; } // 循环直到 p 为空或到了第 i 个节点 while(p && j < i) { p = p->next; ++ j; } if(!p j > i) // 第 i 个节点不存在 return false; e = p->data; // copy 数据到 e 中 return true; 2 线性表 30

31 p = L->next; j = 1; // 循环直到 p 为空或到了第 i 个节点 while(p && j < i) { p = p->next; ++ j; } if(!p j > i) // 第 i 个节点不存在 return false; i=3 p L a1 a2 a3 a4 j=123 31

32 p = L->next; j = 1; // 循环直到 p 为空或到了第 i 个节点 while(p && j < i) { p = p->next; ++ j; } if(!p j > i) // 第 i 个节点不存在 return false; p 已经走到了尽头, 却还没找到第 i 个节点, 说明第 i 个节点不存在 i=3 p L a1 a2 j=123 32

33 插入操作因为各个元素的存储地址任意, 所以不需要移动节点, 只需修改 next 指针 p a b s x 33

34 bool ListInsert_Lk (LNode* &L, int i, ElemType e) { LNode* p = L; j = 0; // 寻找第 i-1 个节点 while(p && j < i-1){ p = p->next; ++ j; } 不就是前面的 GetElem_L 算法么? // 若第 i-1 个节点不存在 if(!p j > i-1) return false; 34

35 // 生成一个新节点, 并链接到 L 中 s = (LNode *) malloc (sizeof(lnode)); s->data = e; s->next = p->next; p->next = s; return true; } i=3, 即在第 3 个节点前面插入一个新的节点 p 注意 : 这两条语句的顺序不能颠倒 a1 a2 a3 a4 j=012 s e 35

36 插入操作的时间复杂度插入这个过程所需时间为常数但是找到插入位置的复杂度 = O(n) 所以插入操作的复杂度 = O(n) 36

37 删除和插入类似, 只需移动几个指针但是也必须先找到待删除的节点 p a b c 37

38 bool ListDelete_Lk (LNode* &L, int i, ElemType& e) { LNode* p = L; j = 0; // 让 p 指向第 i-1 个节点 while(p && j < i-1){ p = p->next; ++ j; } // 若第 i 个节点不存在 if(!(p->next) j > i-1) return false; 38

39 } LNode* q = p->next; // q 指向待删除节点 p->next = q->next; // 使 q 脱离链表 e = q->data; // e 得到 q 的数据 free(q); // 释放 q 的空间 return true; i=3, 即删除第 3 个节点 p q a1 a2 a3 a4 j=012 39

40 删除操作的时间复杂度是多少? 40

41 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L 41

42 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 42

43 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 43

44 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 44

45 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 a4 45

46 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 a4 L 46

47 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 a4 L a4 47

48 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 a4 L a3 a4 48

49 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 L a1 a2 a3 a4 L a2 a3 a4 49

50 创建即从空表开始不停的插入节点不过如果每次都是从表尾插入的话, 需要先搜索到表尾的位置所以从表头插入更快 bool push_back(lnode *L,elemType e); bool insert_front(lnode *L,elemType e); L a1 a2 a3 a4 L a1 a2 a3 a4 50

51 静态链表动态链表链表中的每个节点都是动态分配使用 malloc 函数节点之间使用指针链接静态链表静态分配空间使用数组来存储但是像动态链表一样, 节点地址不一定连续使用下标作为指针 51

52 存储结构数据 L 指针 #define SIZE 500 typedef struct{ ElemType data; int next; }snode; typedef snode slklist[size]; slklist L; Zhao 4 2 Wu 0 3 Sun 6 4 Qian 3 5 Zhou 2 6 Li 5 7

53 优缺点优点 : 可以应用于没有指针的语言 ( 比如 Matlab) 缺点 : 空间是静态分配的, 缺乏灵活性因此引入备用链表模拟动态分配当需要一个节点的空间时, 从备用链表中分配当删除一个节点时, 把该节点链入备用链表 53

54 从备用链表中分配一个节点返回该节点的下标 54

55 释放一个节点到备用链表

56 循环链表非循环链表尾指针为空, 浪费循环链表尾指针指向表头 a1 a2 a3 a4 a1 a2 a3 a4 56

57 循环链表循环链表通常设尾指针要找头指针? 尾指针指向的就是便于链表合并 a1 a2 A b1 b2 B A 57

58 双向链表单向链表只知道后继节点, 不知前趋节点 NextElem 操作复杂度为 O(1) PriorElem 操作复杂度为 O(n) 必须从头开始查找双向链表增加一个前趋指针 58

59 存储结构 typedef struct DulNode{ ElemType data; struct DulNode *prior; struct DulNode *next; }DulNode; L A B 59

60 循环双向链表 L A B 60

61 双向链表 : 插入操作在第 i 个节点 p 之前, 插入节点 s p a b s x 61

62 双向链表 : 插入操作 s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; p a b s x 62

63 双向链表 : 删除操作 p->prior->next = p->next; p->next->prior = p->prior; free(p); 绕过 p P a b c 63

64 一元稀疏多项式一元多项式的表示 : P n (x) = p 0 +p 1 x+p 2 x 2 + +p n x n 可表示为系数的线形表 :P = (p 0, p 1,,p n ) 一元稀疏多项式如 1 + 3x x 可表示为 ( 系数项, 指数项 ) 的线性表 : ( (1,0), (3,10000), (-2,20000) ) ((p1, e1), (p2, e2),, (pm, em) ) 64

65 一元稀疏多项式 : 类型定义 ADT Polynomial{ 数据元素是 ( 系数指数 ) 的线性表基本操作 : InitPolyn (&P); // 初始化一个空的一元多项式 P DestroyPolyn (&P); // 销毁一元多项式 P PolynLength(P); // 多项式项数 Value (P, x);// 变量为 x 时多项式的值 Ceof(P, int k); // 指数为 k 的项系数 65

66 int MaxExp(P); // 最大指数 InsertTerm( coef, expn);// 插入一项 DeleteItem(&P,int k); AddPolyn (&Pa,&Pb);// 多项式加法 SubtractPolyn (&Pa,&Pb);// 多项式减法 MultiplyPolyn(&Pa, &Pb);// 多项式乘法 ScalPolyn (&P, coef, expn);// 数乘一项 CopyPolyn(&Pa,Pb);// 复制多项式 }// ADT Polynomial 66

67 一元稀疏多项式 : 链式实现用带头结点的链式表表示多项式, 每个结点对应多项式的一项. ha

68 一元稀疏多项式 : 链式实现 typedef struct { float coef; int expn; } ElemType; // 数据元素类型 typedef struct polynode{ ElemType data; struct polynode* next; }PolyNode, *Poly; P

69 初始化 bool InitPoly(Poly &P){ P = new PolyNode(); if(!p) return false; P->next = 0; return true; } P 0 69

70 插入一项 bool InsertPoly(Poly &P,float c,int k){ PolyNode *q = new PolyNode(); q->data.coef = c; q->data.expn = k; } PolyNode *s = P; while(s->next && s->next->data.expn<k) s = s->next; q->next = s->next; s->next = q; P s q

71 加法 pa qa pb qb pcqc

72 加法 : Pc = Pa + Pb void AddPolyn (Poly Pa, Poly Pb, Poly &Pc ){ PolyNode *qa,*qb,*qc; InitPolyn(Pc); qa = Pa->next;qb = Pb->next;qc = Pc; while( qa && qb){// 都不空时 } while( qa){ //Pa 还有剩余 } while( qb){//pb 还有剩余 } } 72

73 加法? Pa += Pb void AddPolyn (Poly &Pa, Poly Pb){ } 73

74 乘法 void MultiplyPolyn(Poly Pa, Poly Pb, Poly &Pc ){ Poly TP; PolyNode *qb; InitPolyn (Pc); if(! Pa->next!Pb->next) return ; CopyPolyn(Pc,Pa); 74

75 qb = qb->next; while (qb){ CopyPolyn(TP,Pa); ScalPolyn (TP,qb->coef,qb->expn); AddPolyn (Pc,TP); qb = qb->next; } } 75

76 本章小结线性表的类型定义理解线性表的概念顺序实现用静态连续的空间来存储数据存取操作方便但是插入删除操作需要大量移动数据 76

77 本章小结链式实现即用链表实现动态分配空间结点的地址之间不一定连续存取操作需要从头结点开始一个一个的搜索, 复杂度为 O(n) 插入删除操作因为先要找到待处理的节点, 所以复杂度仍然是 O(n) 77

78 本章小结静态链表静态存储, 动态使用循环链表尾指针指向指向头节点, 便于合并操作双向链表增加前驱指针算法重点插入删除操作, 注意语句的顺序 78

79 本章小结一元稀疏多项式的表示与实现一种特殊的线形表 79

80 作业 1. 双向链表中有两个指针域,llink 和 rlink, 分别指回前驱及后继, 设 p 指向链表中的一个结点,q 指向一待插入结点, 现要求在 p 前插入 q, 则正确的插入为 ( ) A.p->llink=q; q->rlink=p; p->llink->rlink=q; q->llink=p->llink; B.q->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink=q->rlink; C.q->rlink=p; p->rlink=q; p->llink->rlink=q; q->rlink=p; D.p->llink->rlink=q; q->rlink=p; q->llink=p->llink; p->llink=q; 80

81 2. 设有循环链表如下, 设计算法将链表中指针方向取反 3. 对 2 个有序的线性表进行合并 1) 编写对 2 个有序的顺序表进行合并的程序并测试 2) 编写对 2 个有序的链式表进行合并的程序并测试 4. 编写程序判断 : 用单链表存储的一个整数序列是否是等差数列 81

Microsoft Word - 专升本练习2：线性表.doc

Microsoft Word - 专升本练习2：线性表.doc 第二章线性表一选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率插入一个元素时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.