Microsoft PowerPoint - Slides03_第二章 线性表.ppt [兼容模式]

Transcription

1 第二章线性表 定义 基本操作 实现 顺序存储 链式存储 应用 多项式

2 线性表 (Linear List) 定义 线性表是 n ( 0) 个数据元素的有限序列, 记作 (a 1, a 2,, a n ) a i 是表中数据元素,n 是表长度 假定 : 各元素的数据类型相同 原则上 : 线性表中, 表元素的数据类型可以不相同 采用的存储表示可能会对元素的数据类型有限制

3 特点 除第一个元素外, 其他每一个元素有一个且仅有一个直接前驱 (predecessor) 除最后一个元素外, 其他每一个元素有一个且仅有一个直接后继 (successor) a 1 a 2 a 3 a 4 a 5 a 6 直接前驱和直接后继 描述了结点之间的逻辑关系 ( 即邻接关系 )

4 第二章线性表 定义 类定义和基本操作 实现 顺序存储 链式存储 应用 多项式

5 线性表的抽象基类 (Abstract Base Class)

6 线性表的抽象数据类型 ADT LinearList is Object:n(>=0) 个原子表项的一个有限序列 每个表项的数据类型为 T Function: create() // 创建一个空线性表 bool getdata(int i, T& x) // 取值 void setdata(int i, T& x) // 赋值 void CopyList(List<T>& L)// 将表 L 复制到当前表中 int Length() // 计算表长度 int Search(T& x) // 搜索 : 寻找并返回 x 在表中的位置 int Locate(int i) // 定位 : 返回第 i 个表项在表中的位置 bool Insert(int i, Ex) // 插入 : 在第 i 个表项后插入 x, 返回成功标志 bool Remove(int i, E& x) // 删除第 i 个表项, 通过 x 返回该表项的的值 bool IsEmpty() // 判表空 : 满返回 true, 否则返回 false bool IsFull() // 判表满 : 满返回 true,, 否则返回 false void Sort() // 排序 End LinearList

7 线性表的抽象基类 template <class T,classE> class LinearList { public: LinearList(); ~LinearList(); // 构造函数 // 析构函数 virtual E* getdata(int i) const = 0; virtual void setdata(int i, Ex)=0; virtual void input() = 0; virtual void output() = 0; // 取值 // 赋值 // 输入 // 输出 virtual LinearList<T, E>operator= (LinearList<T, E>& L) =0; // 复制 -- 赋值运算符重载

8 virtual int Size() const = 0; virtual int Length() const = 0; // 求表最大体积 // 求表长度 }; virtual int Search(Tx) const = 0; virtual int Locate(int i) const = 0; virtual bool Insert(int i, Ex)=0; virtual bool Remove(int i, E& x) =0; virtual bool IsEmpty() const = 0; virtual bool IsFull() const = 0; virtual void Sort() = 0; // 搜索 // 定位 // 插入 // 删除 // 判表空 // 判表满 // 排序

9 第二章线性表 定义 基本操作 实现 顺序存储 链式存储 应用 多项式

10 线性表的存储表示方式 1 顺序表 (Sequential List) 存储 2 链表 (Linked List) 存储

11 顺序表 (Sequential List)

12 顺序表 (Sequential List) data 定义 将线性表中的元素相继存放在一个连续的存储空间中 存储结构的具体实现 : 利用一维数组 (Array) 描述存储结构 特点 所有元素的逻辑先后顺序与其物理存放顺序一致

13 作为顺序表存储结构的数组有 2 种分配形式 : 静态和动态 #define maxsize 100 typedef int T; typedef struct { T data[maxsize]; int n; } SeqList; typedef int T; typedef struct { T*data; int maxsize, n; } SeqList; // 顺序表的静态存储表示 // 顺序表的动态存储表示

14 结点的变体 ( 异质数据 ) 25 s t 若想在线性表中存放不同类型的数据, 可采用等价定义 union: typedef union { int val; // 按 data.val 引用 char ch; // 按 data.ch 引用 float dir; // 按 data.dir 引用 union data *link; // 按 data.link 引用 } data; // 整体上是同一类型 data

15 顺序表的类定义 (Sequential List class)

16 顺序表 SeqList 类的定义 #include <iostream.h> #include <stdlib.h> #include "LinearList.h" const int defaultsize = 100; // 定义在 seqlist.h 中 template <class T, class E> class SeqList: public LinearList<T, E> { protected: E *data; // 存放数组 int maxsize; // 最大可容纳表项的项数 int n; // 当前已存表项数 void resize(int newsize); // 改变数组空间大小

17 public: SeqList(int sz = defaultsize); // 构造函数 SeqList(SeqList<T,E>& L); // 复制构造函数 ~SeqList() {delete[ ] data;} // 析构函数 int Size() const {return maxsize;} // 求表最大容量 int Length() const {return n;} // 计算表长度 int Search(Tx) const; // 搜索 x 在表中位置, 函数返回表项序号 int Locate(int i) const; // 定位第 i 个表项, 函数返回表项序号 bool Insert(int i, E x); // 插入 bool Remove(int i, E& x); // 删除 };

18 顺序表的构造函数 #include <stdlib.h> // 操作 exit 存放在此 #include seqlist.h // 操作实现放在 seqlist.cpp template <class T, class E> SeqList<T, E>::SeqList(int sz) { if (sz > 0) { maxsize = sz; n = 0; data = new E[maxSize]; // 创建表存储数组 if (data == NULL) // 动态分配失败 { cerr << " 存储分配错误!" << endl; exit(1); } } };

19 复制构造函数 / 拷贝构造函数 template <class T, class E> SeqList<T, E>::SeqList ( SeqList<T, E>& L ) { maxsize = L.Size(); n = L.Length(); data = new E[maxSize]; // 创建存储数组 if (data == NULL) // 动态分配失败 {cerr << " 存储分配错误!" << endl; exit(1);} for (int i = 1; i <= n; i++) // 传送各个表项 data[i-1] = L.getData(i); };

20 搜索 / 查找 (Search)

21 顺序搜索图示 data 搜索 i i i i 搜索成功

22 data 搜索 50 i i i i i 搜索失败

23 顺序表的搜索算法 template <class T, class E> int SeqList<T, E>::search(T& x) const { // 在表中顺序搜索与给定值 x 匹配的表项, 找到则 // 函数返回该表项是第几个元素, 否则函数返回 0 for (int i = 1; i <= n; i++) // 顺序搜索 if ( data[i-1] == x ) return i; // 表项序号和表项位置差 1 return 0; // 搜索失败 };

24 搜索算法的性能分析 搜索成功, 平均比较次数 ACN (Average Comparing Number) ACN= n pi i 1 c i pi : 搜索第 i 项的概率 ci : 找到时的比较次数 若搜索概率相等, 则 ACN ACN = 1 n 1 n n i 1 i (1 1 (1 n n) n n 2 n) 搜索不成功数据比较 n 次

25 插入 (Insert)

26 表项的插入 data i 插入 x data

27 表项的插入算法 template <class T, class E> bool SeqList<T, E>::Insert (int i, Ex) { // 将新元素 x 插入到表中第 i (1 i n+1) 个表项位 // 置 函数返回插入成功的信息 if (n == maxsize) return false; // 表满 }; if (i < 1 i > n+1) return false; // 参数 i 不合理 for (int j = n; j >= i; j--) // 依次后移 data[j] = data[j-1]; data[i-1] = x; // 插入 ( 第 i 表项在 data[i-1] 处 ) n++; return true; // 插入成功

28 在表中第 i 个位置插入 插入算法的性能分析 从 data[i-1] 到 data [n-1] 成块后移 移动 n-1-(i-1)+1 = n-i+1 项 考虑所有插入位置, 相等插入概率时, 从 1 到 n+1 平均移动次数 AMN (Average Moving Number) AMN = 1 n 1 n 1 i 1 ( n 1 n( n ( n 1) 2 i 1) 1) n 2 n 1 ( n 1 1 0)

29 删除 (Remove)

30 表项的删除 data 删除 x data

31 表项的删除算法 template <class T, class E> bool SeqList<T, E>::Remove (int i, E& x) { // 从表中删除第 i(1 i n) 个表项 // 通过引用型参 // 数 x 返回被删元素 // 函数返回删除成功信息 if (n == 0) return false; // 表空 if (i < 1 i > n) return false; // 参数 i 不合理 }; x = data[i-1]; for (int j = i; j <= n-1; j++) // 依次前移, 填补 data[j-1] = data[j]; n--; return true;

32 删除算法的性能分析 删除第 i 个表项, 需将第 i+1 项到第 n 项全部前移, 需前移的项数为 : n-(i+1)+1 = n-i 考虑表中所有可能删除位置 (1 i n-1), 相等删除概率时, 平均移动次数 AMN: AMN = n 1 1 ( n 1) n n ( n i ) n 1 n 2 2 i 1

33 应用 集合运算

34 集合的 并 运算 void Union ( SeqList<int, int>& LA, SeqList<int, int>& LB ) { int n1 = LA.Length ( ); int n2 = LB.Length ( ); int i, k, x; for ( i = 0; i < n2; i++ ) } { } x = LB.getData(i); // 在 LB 中取一元素 k = LA.Search(x); // 在 LA 中搜索它 if (k == 0) // 若在 LA 中未找到插入它 { LA.Insert(n1, x); n1++; }// 插入到第 n1 个表项位置

35 集合的 交 运算 void Intersection (SeqList<int, int> & LA, SeqList<int, int> & LB) { int n1 = LA.Length ( ); int x, k, i = 0; while ( i < n1 ) { x = LA.getData(i); // 在 LA 中取一元素 k = LB.Search(x); // 在 LB 中搜索它 if (k == 0) // 若在 LB 中未找到 { LA.Remove(i, x); n1--; } // 在 LA 中删除它 else i++; // 找到, 继续处理 LA 中的下一个元素 } }

36 单链表 (Singly Linked List)

37 特点 每个元素 ( 表项 ) 由结点 (Node) 构成 data link 线性结构 单链表 (Singly Linked List) first a 1 a 2 a 3 a 4 a 5 Λ 结点之间 : 可以连续 / 可以不连续存储 结点的逻辑顺序与物理顺序可以不一致 表可扩充

38 单链表的存储映像 free (a) 可利用存储空间 a 0 a 2 a 1 a 3 first free (b) 经过一段运行后的单链表结构

39 单链表的类定义 使用面向对象方法, 要把数据与操作一起定义和封装, 用多个类表达一个单链表 链表结点 (ListNode) 类 链表 (List) 类 4 种定义的方式 结构 (Sturct) 复合 (composition) 继承 (Inheritance) 嵌套

40 单链表的结构 (struct) 定义 在 C 语言中, 定义单链表的结构十分简单 : typedef int T; // 结点数据的类型 // 结点结构定义 typedef struct node { T data; // 结点数据域 node *link; // 结点链接指针域 }; 是一个递归 (Recursion) 的定义 结构定义时, 不考虑操作, 链表定义与实现时, 其操作直接访问结构变量的结构分量

41 结构方式 struct ListNode { int data; ListNode * link; }; // 链表结点 // 链表类, 直接使用链表结点类的数据和操作 class List { private: ListNode *first; // 表头指针 }; // 链表中的结点属于链表私有, 别人无法访问

42 复合类方式 class List; // 类的声明 class ListNode { // 链表结点类定义 friend class List; // 链表类为友元类的声明 private: int data; // 结点数据, 整型 ListNode * link; // 结点指针 }; class List { // 链表类定义 private: ListNode *first ; // 表头指针 };

43 复合方式 链表结点类中声明链表类是它的友元类 即 : 它的私有成员与链表类所共享 特点 : 灵活

44 继承方式 // 链表结点类定义 class ListNode { protected: int data; ListNode * link; }; // 链表类定义, 继承链表结点类的数据和操作 class List : public class ListNode { private: ListNode *first; // 表头指针 };

45 继承方式 链表类声明为链表结点类的派生类 在实现上是可行的, 在逻辑上是有问题的 如 三角形 is 多边形 ( 继承关系 ) 链表 is 链表结点 ( 显然概念不准确 )

46 嵌套方式 class List { private: class ListNode { public: int data; ListNode *link; }; ListNode *first; public: // 链表操作 }; // 链表类定义 // 嵌套链表结点类定义 // 表头指针

47 嵌套方式 链表结点类是链表类的私有成员 限制了链表结点类的应用范围

48 插入 (Insert )

49 单链表中的插入操作 插入 第一种情况 : 在链表最前端插入 newnode->link = first ; first = newnode; newnode first newnode first ( 插入前 ) ( 插入后 )

50 第二种情况 : 在链表中间插入 newnode->link = current->link; current->link = newnode; newnode current newnode current ( 插入前 ) ( 插入后 )

51 第三种情况 : 在链表末尾插入 newnode->link = current->link; current->link = newnode; current newnode newnode current ( 插入前 ) ( 插入后 )

52 单链表的插入算法描述及实现 bool List::Insert(int i, int x) { // 将新元素 x 插入到第 i 个结点之后 i 从 1 开始, //i = 0 表示插入到首元结点之前 if (first == NULL i == 0) { // 空表或首元结点前 LinkNode *newnode = new LinkNode(x); // 建立一个新结点 newnode->link = first; first = newnode; // 新结点成为首元结点 } else { // 否则, 寻找插入位置 LinkNode *current = first; int k = 1;

53 }; while (k < i && current!= NULL) // 找第 i 结点 { current = current->link; k++; } if (current == NULL && first!= NULL) // 链短 {cerr << 无效的插入位置!\n ; return false;} else { // 插入在链表的中间 LinkNode *newnode = new LinkNode(x); newnode->link = current->link; current->link = newnode; } } return true;

54 删除 (Remove)

55 删除 第一种情况 : 删除表中第一个元素 第二种情况 : 删除表中或表尾元素 a i-1 a i a i+1 删除前 a i-1 a i a i+1 p q 删除后 在单链表中删除含 a i 的结点

56 单链表的删除算法 bool List::Remove (int i, int& x) { // 将链表中的第 i 个元素删去, i 从 1 开始 LinkNode *del; // 暂存删除结点指针 if (i <= 1) { del = first; first = first->link; } else { LinkNode *current = first; k = 1; // 找 i-1 号结点 while (k < i-1 && current!= NULL) { current = current->link; k++; } if (current == NULL current->link == NULL) { cout << 无效的删除位置!\n ; return false; }

57 }; del = current->link; // 删中间 / 尾结点 current->link = del->link; } x = del->data; delete del; // 取出被删结点数据 return true;

58 实现单链表的插入和删除算法 不需要移动元素, 只需修改结点指针, 比顺序表方便 情况复杂 专门讨论空表和在表头插入的特殊情形 寻找插入或删除位置 只能沿着链顺序检测

59 带表头结点的单链表 (Single Linked List with first pointer)

60 表头结点 带表头结点的单链表 位于表的最前端, 仅标志表头 本身不带数据, 设置表头结点的目的 统一空表与非空表的操作, 简化链表操作的实现 a 1 a n-1 first 0 first 0 非空表 空表

61 在带表头结点的单链表最前端插入新结点 first p newnode 插入 first p newnode first p newnode 0 first 插入 p newnode 0 newnode->link = p->link; p->link = newnode;

62 从带表头结点的单链表中删除最前端的结点 first ( 非空表 ) first first first p p 0 q q 0 ( 空表 ) q = p->link; p->link = q->link; delete q;

63 单链表的模板类 类模板 使得类的数据成员和成员函数的设计更完整 更灵活 更易于重用 / 复用 在单链表的类模板定义中, 增加了表头结点

64 用模板定义的单链表类 template <class T, class E> // 定义在 LinkedList.h struct LinkNode { // 链表结点类的定义 E data; // 数据域 LinkNode<T, E> *link; // 链指针域 LinkNode() { link = NULL; } // 构造函数 LinkNode(E item, LinkNode<T, E> *ptr = NULL) { data = item; link = ptr; } // 构造函数 bool operator== (T x) { return data == x; } // 重载函数, 判相等 bool operator!= (T x) { return data!= x; } };

65 template <class T, class E> class List : public LinearList<T, E> { // 单链表类定义, 不用继承也可实现 protected: LinkNode<T, E> *first; // 表头指针 public: List() { first = new LinkNode<T, E>; } // 构造函数 List(E x) { first = new LinkNode<T, E>; first->link = new LinkNode<T, E>(x);} List( List<T, E>& L); // 复制构造函数 ~List(){ } // 析构函数 void makeempty(); // 将链表置为空表 int Length() const; // 计算链表的长度

66 LinkNode<T, E> *Search(T x); // 搜索含 x 元素 LinkNode<T, E> *Locate(int i); // 定位第 i 个元素 E *getdata(int i); // 取出第 i 个元素值 void setdata(int i, E x); // 更新第 i 个元素值 bool Insert (int i, E x); // 在第 i 个元素后插入 bool Remove(int i, E& x); // 删除第 i 个元素 bool IsEmpty() const // 判表空否 { return first->link == NULL? true : false; } LinkNode<T, E> *getfirst() const { return first; } void setfirst(linknode<t, E> *f ) { first = f; } void Sort(); // 排序 };

67 前插创建 (inputfront)

68 前插法建立单链表 从一个空表开始, 重复读入数据 : 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端 直到读入结束符为止 first 0 first newnode 0 newnode

69 template <class T, class E> void inputfront (T endtag, List<T, E>& L) { LinkNode<T, E> *newnode, *newf; E val; newf = new LinkNode<T, E>; L.setFirst (newf); //first->link 默认值为 NULL cin >> val; while (val!= endtag) { newnode = new LinkNode<T, E>(val); newnode->link = newf->link; // 插在表前端 newf->link = newnode; cin >> val; } };

70 后插创建 (inputrear)

71 后插法建立单链表 每次将新结点加在链表的表尾 ; 设置一个尾指针 last, 总是指向表中最后一个结点, 新结点插在它的后面 ; 尾指针 last 初始时置为指向表头结点地址 first last 0 newnode last 0 last newnode last 0 0

72 template <class T, class E> void inputrear ( T endtag, List<T, E>& L ) { LinkNode<T, E> *newnode, *last; E val; last = new LinkNode<T, E>; // 建立链表的头结点 L.setFirst(last); // 为链表 L 的 first 赋值 cin >> val; while ( val!= endtag ) { //last 指向当前的表尾 }; newnode = new LinkNode<T, E>(val); last->link = newnode; last = newnode; cin >> val; // 插入到表末端 } last->link = NULL; // 表收尾

73 链表的长度 (Length)

74 first first first first c = 0 a 0 a 1 a 2 p a 0 a 1 a 2 c = 1 p a 0 a 1 a 2 c = 2 p a 0 a 1 a 2 c = 3 p

75 求单链表的长度的算法 template <class T, class E> int List<T, E> :: Length ( ) const { ListNode<T, E> *p = first->link; // 检测指针 p 指示第一号结点 int count = 0; while ( p!= NULL ) { // 逐个结点检测 p = p->link; count++; } return count; }

76 置空 (makeempty) ( 保留表头结点 )

77 first first first first a 0 a 1 q a 1 q current a 2 a 2 a 2 q

78 template <class T, class E> void List<T, E>::makeEmpty() { LinkNode<T, E> *q; while (first->link!= NULL) { q = first->link; // 保存被删结点 } }; 链表置空算法 ( 保留表头结点 ) first->link = q->link; // 从链上摘下该结点 delete q; // 删除

79 单链表的搜索算法 template <class T, class E> LinkNode<T, E> *List<T, E>::Search(T x) { // 在表中搜索含数据 x 的结点, 搜索成功时函数返 // 该结点地址 ; 否则返回 NULL LinkNode<T, E> *current = first->link; while ( current!= NULL && current->data!= x ) current = current->link; // 沿着链找含 x 结点 return current; };

80 单链表的定位算法 template <class T, class E> LinkNode<T, E> *List<T, E>::Locate ( int i ) { // 函数返回表中第 i 个元素的地址 若 i < 0 或 i 超 // 出表中结点个数, 则返回 NULL }; if (i < 0) return NULL; //i 不合理 LinkNode<T, E> *current = first; int k = 0; while ( current!= NULL && k < i ) { current = current->link; k++; } return current; // 返回第 i 号结点地址或 NULL

81 单链表的插入算法 template <class T, class E> bool List<T, E>::Insert (int i, E x) { // 将新元素 x 插入在链表中第 i 个结点之后 LinkNode<T, E> *current = Locate(i); if (current == NULL) return false; // 无插入位置 LinkNode<T, E> *newnode = new LinkNode<T, E>(x); // 创建新结点 newnode->link = current->link; // 链入 current->link = newnode; return true; // 插入成功 };

82 单链表的删除算法 template <class T, class E> bool List<T, E>::Remove (int i, E& x ) { // 删除链表第 i 个元素, 通过引用参数 x 返回元素值 LinkNode<T, E> *current = Locate(i-1); if ( current == NULL current->link == NULL) return false; // 删除不成功 LinkNode<T, E> *del = current->link; current->link = del->link; x = del->data; delete del; return true; };

83 第二章线性表 定义 基本操作 实现 顺序存储 链式存储 应用 多项式

84 i n i i n n n x a x a x a x a a x P ) ( 多项式 (Polynomial) n 阶多项式 P n (x) 有 n+1 项 系数 a 0, a 1, a 2,, a n 指数 0, 1, 2,, n, 按升幂排列

85 多项式 (polynomial) 顺序存储

86 第一种 : private: ( 静态数 int degree; 组表示 ) float coef [maxdegree+1]; P n (x) 可以表示为 : pl.degree = n pl.coef[i] = a i, 0 i n coef degree maxdegree a 0 a 1 a 2 a n n

87 第二种 :private: ( 动态数 int degree; 组表示 ) float * coef; Polynomial :: Polynomial (int sz) { degree = sz; coef = new float [degree + 1]; }

88 以上两种存储表示 适用于指数连续排列的多项式 但对于绝大多数项的系数为零的多项式 不经济 如 P 101 (x) = 3+5x 50-4x 101

89 第三种 : i m coef a 0 a 1 a 2 a i a m exp e 0 e 1 e 2 e i e m struct term { // 多项式的项定义 float coef; // 系数 int exp; // 指数 }; static term termarray[maxterms]; // 项数组 static int free, maxterms; // 当前空闲位置

90 初始化 : // term Polynomial::termArray[MaxTerms]; // int Polynomial::free = 0; class Polynomial { public: private: int start, finish; } // 多项式定义 // 多项式始末位置

91 两个多项式存储的例子 A(x) = 2.0x B(x) = x x 101 A.start A.finish B.start B.finish free maxterms coef exp 两个多项式存放在 termarray 中

92 多项式 (polynomial) 链式存储

93 多项式的链表存储 多项式顺序存储表示的缺点 : 插入和删除时项数可能有较大变化, 因此要移动大量数据 不利于多个多项式的同时处理 多项式的链表表示 : 多项式的项数可以动态地增长, 不存在存储溢出问题 插入 删除方便, 不移动元素

94 多项式的链表结构 结点三个数据成员 : Data Term coef exp link Link: 将多项式各项按指数递增的顺序链接成一个单链表 新项的加入 : 执行简单的链表插入操作 废项的删除 : 执行简单的链表删除操作

95 多项式 (polynomial) 类定义

96 多项式 (polynomial) 类的链表定义 struct Term { // 多项式结点定义 float coef; // 系数 int exp; // 指数 Term *link; // 链接指针 Term (float c, int e, Term *next = NULL) { coef = c; exp = e; link = next;} Term *InsertAfter ( float c, int e); friend ostream& operator << (ostream&, const Term& ); };

97 class Polynomial {// 多项式类的定义 public: Polynomal() { first = new Term(0, -1);} // 构造函数 Polynomal ( Polynomal& R); // 复制构造函数 int maxorder(); // 计算最大阶数 private: Term *first; friend ostream& operator << (ostream&, const Polynomal& ); friend istream& operator >> ( istream&, Polynomal& );

98 }; friend void Add ( Polynomial& A, Polynomial& B, Polynomial& C ); friend void Mul ( Polynomial& A, Polynomial& B, Polynomial& C ); Term *Term::InsertAfter ( float c, int e ) { // 在调用此函数的对象后插入一个新项 link = new Term (c, e, link); // 创建一个新结点, 自动链接 return link; // 插入到 this 结点后面 };

99 ostream& operator << (ostream& out, const Term& x) { //Term 的友元函数 : 输出一个项 x 的内容到输出流对 // 象 out 中去 if (x.coef == 0.0) return out; // 零系数项不输出 out << x.coef; // 输出系数 switch (x.exp) { // 输出指数 }; case 0: break; // 指数为 0, 不出现 X case 1: out << X ; break; // 在系数后输出 X default: out << X^ << x.exp; break; // 否则 } return out;

100 istream& operator >> (istream& in, Polynomal& x) { //Polynomal 类的友元函数 : 从输入流 in 输入各项, // 用尾插法建立一个多项式 Term *rear = x.first; intc, e; //rear 是尾指针 while (1) { cout << Input a term(coef, exp): << endl; in >> c >> e; // 输入项的系数 c 和指数 e if ( e < 0 ) break; // 用 e < 0 控制输入结束 }; rear = rear->insertafter(c, e);// 链接到 rear 后 } return in;

101 ostream& operator << (ostream& out, Polynomal& x) {//Polynomal 类的友元函数 : 输出带头结点的多项式 // 链表 x Term *current = x.first->link; out << The polynomal is: << endl; out << *current; // 调用 Term 的重载操作 << }; while (current!= NULL) { out << + << *current; current = current->link; } out << endl; return out; // 逐项输出

102 多项式相加 (Add)

103 两个多项式的相加算法 设两个多项式都带表头结点, 检测指针 pa 和 pb 分别指示两个链表当前检测结点, 设结果多项式的表头指针为 C, 存放指针为 pc, 初始位置在 C 的表头结点

104 当 pa 和 pb 没有检测完各自的链表时, 比较当前检测结点的指数域 : 指数不等 : 小者加入 C 链, 相应检测指针 pa 或者 pb 进 1; 指数相等 : 对应项系数相加 若相加结果不为零, 则结果加入 C 链,pa 与 pb 进 1 当 pa 或 pb 指针中有一个为 NULL, 则把另一个链表的剩余部分加入到 C 链

105 多项式链表的相加 AH = 1-3x 6 + 7x 12 BH = - x 4 + 3x 6-9x x 14 CH = 1 - x 4-9x x x 14 AH.first BH.first CH.first

106 pa AH.first BH.first CH.first pc pb

107 pa AH.first BH.first pb pc CH.first 1 0

108 pa AH.first BH.first pb pc CH.first

109 pa AH.first BH.first tmp = -3+3 = 0 pc pb CH.first

110 pa AH.first BH.first pb CH.first pc -9 10

111 pa AH.first BH.first pb CH.first pc 7 12

112 pa AH.first BH.first pb p CH.first pc

113 friend void Add(Polynomal& A, Polynomal& B, Polynomal& C) { // 友元函数 : 两个带表头结点的按升幂排列的 // 多项式链表的头指针分别是 A.first 和 //B.first, 结果为多项式链表 C. Term *pa, *pb, *pc, *p; floattemp; pc = C.first; // 结果链尾指针 pa = A.first->link; //A 链检测指针 pb = B.first->link; //B 链检测指针 while (pa!= NULL && pb!= NULL) {

114 if (pa->exp == pb->exp) { // 对应项指数相等 temp = pa->coef + pb->coef; if ( fabs(temp) > 0.001) pc = pc->insertafter(temp, pa->exp); pa = pa->link; pb = pb->link; } else if (pa->exp < pb->exp) { //pa 指数小 pc = pc->insertafter(pa->coef, pa->exp); pa = pa->link; } else { } //pb 指数小 pc = pc->insertafter(pb->coef, pb->exp); pb = pb->link;

115 }; p = (pa!= NULL)? pa : pb; //p 指示剩余链 while (p!= NULL) { pc = pc->insertafter(p->coef, p->exp); p = p->link; }

116 第二章线性表 扩展 循环链表 双向链表

117 循环链表 (Circular List) 循环链表是单链表的变形 循环链表的最后一个结点的 link 指针不为 NULL, 而是指向了表的前端 为简化操作, 在循环链表中往往加入表头结点 循环链表的特点是 : 只要知道表中某一结点的地址, 就可搜寻到所有其他结点的地址

118 循环链表的示例 first a 0 a 1 a 2 a n-1 带表头结点的循环链表 first a 0 a 1 a n-1 first ( 空表 ) ( 非空表 )

119 循环链表类定义

120 循环链表类定义 template <class T, class E> struct CircLinkNode { // 链表结点类定义 E data; CircLinkNode<T, E> *link; CircLinkNode ( CircLinkNode<T, E> *next = NULL ) { link = next; } CircLinkNode ( E d, CircLinkNode<T, E> *next = NULL ) { data = d; link = next; } bool Operator==(E x) { return data == x; } bool Operator!=(E x) { return data!= x; } };

121 template <class T, class E> // 链表类定义 class CircList : public LinearList<T, E> { private: CircLinkNode<T, E> *first, *last; // 头指针, 尾指针 public: CircList(const E x); // 构造函数 CircList(CircList<T, E>& L); // 复制构造函数 ~CircList(); // 析构函数 int Length() const; // 计算链表长度 bool IsEmpty() { return first->link == first; } // 判表空否 CircLinkNode<T, E> *gethead() const; // 返回表头结点地址

122 }; void sethead ( CircLinkNode<T, E> *p ); // 设置表头结点地址 CircLinkNode<T, E> *Search ( T x ); // 搜索 CircLinkNode<T, E> *Locate ( int i ); // 定位 E *getdata ( int i ); // 提取 void setdata ( int i, E x ); // 修改 bool Insert ( int i, E x ); // 插入 bool Remove ( int i, E& x); // 删除 循环链表与单链表的操作实现, 最主要的不同就是扫描到链尾, 遇到的不是 NULL, 而是表头

123 搜索 (Search)

124 循环链表的搜索算法 first 搜索 15 current current current 搜索成功 first current 搜索 25 current current current current 搜索不成功

125 循环链表的搜索算法 template <class T, class E> CircListNode<T, E> * CircList<T, E>::Search( T x ) { // 在链表中从头搜索其数据值为 x 的结点 current = first->link; while ( current!= first && current->data!= x ) current = current->link; return current; }

126 带尾指针的循环链表 rear 如果插入与删除仅在链表的两端发生, 可采用带表尾指针的循环链表结构 在表尾插入, 时间复杂性 O(1) 在表尾删除, 时间复杂性 O(n) 在表头插入, 相当于在表尾插入 在表头删除, 时间复杂性 O(1)

127 应用 -- 约瑟夫问题

128 用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈, 首先第 1 个人从 1 开始, 一个人一个人顺时针报数, 报到第 m 个人, 令其出列 然后再从下一个人开始, 从 1 顺时针报数, 报到第 m 个人, 再令其出列,, 如此下去, 直到圆圈中只剩一个人为止 此人即为优胜者 用不带表头结点的循环链表来组织

129 例如 n = 8 m =

130 n = 8 m =

131 void main() { CircList<int, int> clist; int i, n m; cout << 输入游戏者人数和报数间隔 : ; cin >> n >> m; for (i = 1; i <= n; i++ ) clist.insert(i, i); // 约瑟夫环 Josephus(clist, n, m); // 解决约瑟夫问题 }

132 求解 Josephus 问题的算法 #include <iostream.h> #include CircList.h template <class T, class E> void Josephus(CircList<T, E>& Js, int n, int m) { CircLinkNode<T, E> *p = Js.getHead(); CircLinkNode<T, E> *pre = NULL; } int i, j; for ( i = 0; i < n-1; i++ ) { // 执行 n-1 次 for ( j = 1; j < m; j++) // 数 m-1 个人 { pre = p; p = p->link; } cout << 出列的人是 << p->data << endl; pre->link = p->link; delete p; // 删去 p = pre->link; }

133 第二章线性表 扩展 循环链表 双向链表

134 双向链表 (Doubly Linked List) 双向链表是指在前驱和后继方向都能游历 ( 遍历 ) 的线性链表 双向链表每个结点结构 : llink data rlink 前驱方向 后继方向 双向链表通常采用带表头结点的循环链表形式

135 first first 非空表 空表 结点指向 p == p->llink->rlink == p->rlink->llink rlink llink p->llink p p->rlink

136 双向循环链表类定义

137 双向循环链表类定义 template <class T, class E> struct DblNode { // 链表结点类定义 E data; // 链表结点数据 DblNode<T,E> *llink, *rlink; // 前驱 后继指针 DblNode ( DblNode<T,E> *l = NULL, DblNode<T,E> *r = NULL ) { llink = l; rlink = r; } // 构造函数 DblNode ( E value, DblNode<T, E> *l = NULL, DblNode<T,E> *r = NULL) { data = value; llink = l; rlink = r; } // 构造函数 };

138 template <class T, class E> class DblList { // 链表类定义 public: DblList ( E uniqueval ) { // 构造函数 first = new DblNode<T, E> (uniqueval); first->rlink = first->llink = first; }; DblNode<T, E> *getfirst () const { return first; } void setfirst ( DblNode<T, E> *ptr ) { first = ptr; } DblNode<T, E> *Search ( T x, int d); // 在链表中按 d 指示方向寻找等于给定值 x 的结点, //d=0 按前驱方向,d 0 按后继方向

139 DblNode<T, E> *Locate ( int i, int d ); // 在链表中定位序号为 i( 0) 的结点, d=0 按前驱方 // 向,d 0 按后继方向 bool Insert ( int i, E x, int d ); // 在第 i 个结点后插入一个包含有值 x 的新结点,d=0 // 按前驱方向,d 0 按后继方向 bool Remove ( int i, E& x, int d ); // 删除第 i 个结点 bool IsEmpty() { return first->rlink == first; } // 判双链表空否 private: DblNode<T, E> *first; // 表头指针 };

140 搜索 (Search)

141 双向循环链表的搜索算法 first 搜索 15 搜索成功 first 搜索 25 搜索不成功

142 双向循环链表的搜索算法 template <class T, class E> DblNode<T, E> *DblList<T, E>::Search (T x, int d) { // 在双向循环链表中寻找其值等于 x 的结点 DblNode<T,E> *current = (d == 0)? first->llink : first->rlink; // 按 d 确定搜索方向 while ( current!= first && current->data!= x ) current = (d == 0)? current->llink : current->rlink; if ( current!= first ) return current; // 搜索成功 else return NULL; // 搜索失败 };

143 插入 (Insert)

144 双向循环链表的插入算法 ( 非空表 ) first 后插入 25 first current current newnode newnode->rlink = current->rlink; current->rlink = newnode; newnode->rlink->llink = newnode; newnode->llink = current;

145 双向循环链表的插入算法 ( 空表 ) first first 25 后插入 25 current current newnode newnode->rlink = current->rlink (newnode->rlink = first); current->rlink = newnode; newnode->rlink ->llink = newnode; ( first->llink = newnode ) newnode->llink = current;

146 双向循环链表的插入算法 template <class T, class E> bool DblList<T, E>::Insert ( int i, E x, int d ) { // 建立一个包含有值 x 的新结点, 并将其按 d 指定的 // 方向插入到第 i 个结点之后 DblNode<T, E> *current = Locate(i, d); // 按 d 指示方向查找第 i 个结点 if ( current == NULL ) return false; // 插入失败 DblNode<T,E> *newnd = new DblNode<T,E>(x); if (d == 0) { // 前驱方向 : 插在第 i 个结点左侧 newnd->llink = current->llink; // 链入 llink 链 current->llink = newnd;

147 newnd->llink->rlink = newnd; // 链入 rlink 链 newnd->rlink = current; } else { // 后继方向 : 插在第 i 个结点后面 newnd->rlink = current->rlink; // 链入 rlink 链 current->rlink = newnd; newnd->rlink->llink = newnd; // 链入 llink 链 newnd->llink = current; } return true; // 插入成功 };

148 删除 (Remove)

149 双向循环链表的删除算法 first 非空表 删除 48 first current current current->rlink->llink = current->llink; current->llink->rlink = current->rlink;

150 双向循环链表的删除算法 template <class T, class E> bool DblList<T, E>::Remove( int i, E& x, int d ) { // 在双向循环链表中按 d 所指方向删除第 i 个结点 DblNode<T, E> *current = Locate (i, d); }; if (current == NULL) return false; current->rlink->llink = current->llink; current->llink->rlink = current->rlink; // 从 llink 链和 rlink 链中摘下 // 删除失败 x = current->data; delete current; // 删除 return true; // 删除成功

151 静态链表

152 静态链表 为数组中每一个元素附加一个链接指针, 就形成静态链表结构 处理时中可以不改变各元素的物理位置, 只要重新链接就能改变这些元素的逻辑顺序 它是利用数组定义的, 在整个运算过程中存储空间的大小不会变化 静态链表每个结点由两个数据成员构成 : data 域存储数据,link 域存放链接指针 所有结点形成一个结点数组,

153 静态链表的结构 first a 1 a 2 a 3 a 4 a 5 Λ data a 3 a 4 a 1 a 5 a 2 link (0) 1 0 号是表头结点,link 给出首元结点地址 循环链表收尾时 link = 0, 回到表头结点 如果不是循环链表, 收尾结点指针 link = -1 link 指针是数组下标, 因此是整数

154 The END