2 线性表 Linear List 姜玻 2 线性表 Linear List 2.1 线性表的定义和 基本操作 2.2 线性表的实现 线性表的顺序存储 姜玻 教育科学与技术学院 数字媒体技术系 单链表 带表头结点的单链表 单循环链表 双向链

Transcription

1 2.1 线性表的定义和 基本操作 2.的实现 教育科学与技术学院 数字媒体技术系

2 前情提要 程序 = 数据结构 + 算法何为数据结构, 相关的术语逻辑结构存储结构运算抽象数据类型 (Abstract Data Type,ADT) C++ 定义和实现何为算法, 其特点和设计要求算法的时间复杂度 ( 大 O 表示 ) 算法的空间复杂度 2.的实现

3 前情提要 ADT Stack{ 数据 : 0 个或多个元素的序列 a 0, a 1,..., a n 1 最大允许长度为 MaxStackSize 运算 : Create(): 建立一个空栈 Destroy(): 撤销一个栈 Push(x): 值为 x 的新元素进栈, 成为栈顶元素 Pop(): 从栈中删除栈顶元素 Top(x): 在 x 中返回栈顶元素 2.的实现

4 本章主要内容 线性表的定义和基本操作线性表的实现顺序存储链式存储线性表的应用 2.的实现

5 本章主要内容 线性表的定义和基本操作线性表的实现顺序存储链式存储线性表的应用 2.的实现

6 线性表是 n( 0) 个元素 a 0, a 1,..., a n 1 的线性序列, 记为 (a 0, a 1,..., a n 1 ) 其中 n 是线性表中元素的个数, 称为线性表的长度 (n = 0 时称为空表 ) a i 是表中下标为 i 的元素称 a i 是 a i+1 的直接前驱元素称 a i+1 是 a i 的直接后继元素 2.的实现

7 线性表的定义和基本操作 通常, 线性表中的元素具有相同类型简单类型 : 整数结构类型 : 记录动态数据结构, 表长可变化可执行检索 修改操作, 也可在表中任意位置执行插入和删除元素的操作 2.的实现

8 线性表的定义和基本操作 2.1 线性表的定义和 基本操作 2.的实现

9 线性表 ADT ADT LinearList{ 数据 : 0 个或多个元素的线性序列 (a 0, a 1,..., a n 1 ) 最大允许长度 MaxListSize 运算 : Create(): 创建一个空线性表 Destroy(): 撤销一个线性表 IsEmpty(): 若线性表为空, 则返回 true, 否则返回 false Length(): 返回表中元素个数 2.的实现

10 线性表 ADT Find(i, x): 在 x 中返回表中下标为 i 的元素 a i 若不存在, 返回 false, 否则返回 true Search(x): 若 x 不在表中, 则返回 -1, 否则返回 x 在表中的下标 Insert(i, x): 在元素 a i 之后插入 x 若 i = 1, 则 x 插在第一个元素 a 0 前 若插入成功, 则返回 true, 否则返回 false 2.的实现

11 线性表 ADT Delete(i): 删除元素 a i 若删除成功, 则返回 true, 否则返回 false Update(i, x): 将元素 a i 的值修改为 x 若修改成功, 则返回 true, 否则返回 false Output(out): 把表送至输出流 2.的实现

12 线性表的 C++ 模板抽象类 #include <iostream.h> template<class T> class LinearList { public: virtual bool IsEmpty() const = 0; virtual int Length() const = 0; virtual bool Find(int i, T& x) const = 0; virtual int Search(T x) const = 0; virtual bool Insert(int i, T x) = 0; 2.的实现

13 线性表的 C++ 模板抽象类 virtual bool Delete(int i) = 0; virtual bool Update(int i, T x) = 0; virtual void Output(ostream& out) const = 0; protected: int n;// 线性表的长度 ; 2.的实现

14 本章主要内容 线性表的定义和基本操作线性表的实现顺序存储链式存储线性表的应用 2.的实现

15 2.的实现 线性表有两种典型的存储方式 顺序存储链式存储 单链表 带表头结点的单链表 单循环链表 双向链表 2.的实现

16 本章主要内容 线性表的定义和基本操作线性表的实现顺序存储链式存储线性表的应用 2.的实现

17 用一组地址连续的存储单元依次存储线性表 (a 0, a 1,..., a n 1 ) 中的元素 逻辑上相邻的元素在物理上 ( 存储空间上 ) 也相邻 顺序表示的线性表称为顺序表 2.的实现

18 线性表的顺序存储 若顺序表中每个元素占 k 个存储单元, 第一个元 素 a 0 在计算机内存中的首地址为 loc(a 0 ), 则表中任意 一个元素 a i 在内存中的存储地址 loc(a i ) 为 2.的实现?

19 线性表的顺序存储 若顺序表中每个元素占 k 个存储单元, 第一个元 素 a 0 在计算机内存中的首地址为 loc(a 0 ), 则表中任意 一个元素 a i 在内存中的存储地址 loc(a i ) 为 2.的实现 loc(a i ) = loc(a 0 ) + i k 随机存取给定 loc(a 0 ) 和 k, 可确定线性表中任一元素的存储地址

20 线性表顺序存储的 C++ 实现 C++ 中的一维数组占用一组地址连续的存储单元用 C++ 的一维数组来描述顺序表的存储结构, 并实现顺序表类动态分配一维数组 2.的实现

21 顺序表的 C++ 实现 #include linearlist.h template<class T> class SeqList:public LinearList<T> { public: SeqList(int msize); SeqList() { delete [] elements; bool IsEmpty() const; int Length() const; bool Find(int i, T& x) const; 2.的实现

22 顺序表的 C++ 实现 int Search(T x) const; bool Insert(int i, T x); bool Delete(int i); bool Update(int i, T x); void Output(ostream& out) const; private: int maxlength;// 顺序表的最大长度 T *elements// 动态一维数组指针 ; ; 2.的实现

23 顺序表的 C++ 实现 template<class T> SeqList<T>::SeqList(int msize) { maxlength=msize; elements=new T[maxLength];// 动态分配存储空间 n=0; 2.的实现

24 顺序表的 C++ 实现 template<class T> bool SeqList<T>::IsEmpty() const { return n==0; template<class T> int SeqList<T>::Length() const { return n; 2.的实现

25 顺序表的 C++ 实现 template<class T> bool SeqList<T>::Find(int i, T& x) const { if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; x=elements[i];// 通过引用参数 x 返回 return true; 2.的实现

26 顺序表的 C++ 实现 template<class T> bool SeqList<T>::Search(T x) const { for(int j=0; j<n; j++) if(elements[j] == x) return j;// 从头开始 return -1; 2.的实现

27 顺序表的 C++ 实现 template<class T> bool SeqList<T>::Insert(int i, T x) { if(i<-1 i>n-1){ cout<< Out of Bounds <<endl; return false; if(n == maxlength){// 上溢 cout<< OverFlow <<endl; return false; for(int j=n-1; j>i; j- -) elements[j+1] = elements[j]; elements[i+1]=x; n++; return true; 2.的实现

28 顺序表的 C++ 实现 2.1 线性表的定义和 基本操作 2.的实现

29 顺序表的 C++ 实现 template<class T> bool SeqList<T>::Delete(int i) { if(!n){// 下溢 cout<< UnderFlow <<endl; return false; if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; for(int j=i+1; j<n; j++) elements[j-1] = elements[j]; n- -; return true; 2.的实现

30 顺序表的 C++ 实现 2.1 线性表的定义和 基本操作 2.的实现

31 顺序表的 C++ 实现 template<class T> bool SeqList<T>::Update(int i, T x) { if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; elements[i] = x; return true; 2.的实现

32 顺序表的 C++ 实现 template<class T> void SeqList<T>::Output(ostream& out) const { for(int i=0; i<n; i++) out<<elements[i]<< ; out<<endl; 2.的实现

33 顺序表的 C++ 实现 SeqList 中的 n 哪里来的? 顺序表可随机存取表中元素 插入和删除时效率较低 2.的实现

34 插入操作的时间复杂度 设顺序表长度为 n, 在位置 i( 1 i n 1) 后插入一 个元素要移动 n i 1 个元素 有 n + 1 个可插入元素的位置, 概率相等 为 P i = 1/(n + 1) 平均情况 E i = n 1 i= 1 1 n + 1 (n i 1) = n 2 2.的实现 平均移动多少元素,O(?)

35 插入操作的时间复杂度 设顺序表长度为 n, 在位置 i( 1 i n 1) 后插入一 个元素要移动 n i 1 个元素 有 n + 1 个可插入元素的位置, 概率相等 为 P i = 1/(n + 1) 平均情况 E i = n 1 i= 1 1 n + 1 (n i 1) = n 2 2.的实现 平均移动一半元素,O(n)

36 删除操作的时间复杂度 在位置 i(0 i n 1) 删除一个元素同样要移 动 n i 1 个元素 有 n 个可删除元素的位置, 概率相等为 Q i = 1/n 平均情况 E d = n 1 i=0 平均移动一半元素,O(n) 1 n 1 (n i 1) = n 2 2.的实现

37 顺序表应用实例 : 求集合的并 求集合 A 和 B 的并 A = A B 用顺序表 LA 和 LB 分别表示集合 A 和 B, 并 的结果放在 LA 中, 算法 :? 2.的实现

38 顺序表应用实例 : 求集合的并 求集合 A 和 B 的并 A = A B 用顺序表 LA 和 LB 分别表示集合 A 和 B, 并 的结果放在 LA 中, 算法 : (1) 置 i = 0 (2) 若 i 小于集合 LB 的元素个数, 则做 (3), 否则转 (7) (3) 取出集合 LB 中 i 位置的元素 x (4) 若 x 不在集合 LA 中, 则将其插入 LA 最后 (5)i + + (6) 转 (2) 继续 (7) 结束 2.的实现

39 顺序表应用实例 : 求集合的并 #include seqlist.h template<class T> void Union(SeqList<T> &LA, SeqList<T> LB) { T x; for(int i=0; i<lb.length(); i++){ LB.Find(i, x); if(la.search(x)==-1) LA.Insert(LA.Length()-1, x); 2.的实现

40 顺序表应用实例 : 求集合的并 #include seqlistu.h const int SIZE = 20; void main() { SeqList<int> LA(SIZE); SeqList<int> LB(SIZE); for(int i=0; i<5; i++) LA.Insert(i-1, i); for(i=5; i<10; i++) LB.Insert(i-6, i); 2.的实现

41 顺序表应用实例 : 求集合的并 LB.Insert(-1, 0); LB.Insert(3, 2); LB.Insert(LB.Length()-1, 4); Union(LA, LB); LA.Output(cout); 最终的输出是什么? 2.的实现

42 前情提要 线性表的定义和基本操作线性表的实现顺序存储 顺序表链式存储 链表线性表的应用 2.的实现

43 前情提要 : 线性表 ADT ADT LinearList{ 数据 : 0 个或多个元素的线性序列 (a 0, a 1,..., a n 1 ) 最大允许长度 MaxListSize 运算 : Create(): 创建一个空线性表 Destroy(): 撤销一个线性表 IsEmpty(): 若线性表为空, 则返回 true, 否则返回 false Length(): 返回表中元素个数 2.的实现

44 前情提要 : 线性表 ADT Find(i, x): 在 x 中返回表中下标为 i 的元素 a i 若不存在, 返回 false, 否则返回 true Search(x): 若 x 不在表中, 则返回 -1, 否则返回 x 在表中的下标 Insert(i, x): 在元素 a i 之后插入 x 若 i = 1, 则 x 插在第一个元素 a 0 前 若插入成功, 则返回 true, 否则返回 false 2.的实现

45 前情提要 : 线性表 ADT Delete(i): 删除元素 a i 若删除成功, 则返回 true, 否则返回 false Update(i, x): 将元素 a i 的值修改为 x 若修改成功, 则返回 true, 否则返回 false Output(out): 把表送至输出流 2.的实现

46 前情提要 : 顺序表 顺序表的优点?? 顺序表的劣势?? 2.的实现

47 前情提要 : 顺序表 顺序表的优点存储空间利用率高可以随机存取元素顺序表的劣势插入 删除操作效率低须事先估计元素个数, 估计大了浪费空间, 估计小了容易产生溢出克服劣势, 怎么办? 2.的实现

48 前情提要 : 顺序表 顺序表的优点存储空间利用率高可以随机存取元素顺序表的劣势插入 删除操作效率低须事先估计元素个数, 估计大了浪费空间, 估计小了容易产生溢出克服劣势, 怎么办? 链接表示的线性表 链表举例 : 上课回答问题 2.的实现

49 线性表的链接表示 链表 用一组任意的存储单元存储线性表的数据元素 这组存储单元可以是连续的, 也可以是不连续的动态链表 静态链表 单向链表 ( 循环链表 / 非循环链表 ) 双向链表 ( 循环链表 / 非循环链表 ) 2.的实现

50 单链表 结点 (Node) 每个元素占用一个结点每个结点由两个域组成 数据域 element 指针域 link( 后继结点的地址 ) 2.的实现

51 结点类的 C++ 实现 #include linearlist.h template<class T> class SingleList; template<class T> class Node { private: T element; Node<T> *link; friend class SingleList<T>; ; 2.的实现

52 单链表 线性表 (a 0, a 1,..., a n 1 ) 的单链表结构如图所示第一个元素 a 0 所在的结点称为头结点指向头结点的指针称为头指针 (first 指针 ) 元素 a n 1 所在结点称为尾结点 ( 无后继 ) 空单链表其头指针为 NULL 2.的实现

53 单链表 结点与结点不要求存放在相邻的存储空间里, 相邻关系通过指针表现插入和删除操作比顺序表简单高效失去了顺序表随机存取元素的特性 2.的实现

54 单链表的 C++ 实现 2.1 线性表的定义和 基本操作 2.的实现

55 单链表的 C++ 实现 template<class T> class SingleList:public LinearList<T> { public: SingleList(){first=NULL;n=0; SingleList(); bool IsEmpty() const; int Length() const; bool Find (int i, T& x) const; int Search(T x) const; 2.的实现

56 单链表的 C++ 实现 bool Insert(int i, T x); bool Delete(int i); bool Update(int i, T x); void Clear(); void Output(ostream& out) const; private: Node<T>* first; ; 2.的实现

57 单链表的 C++ 实现 template<class T> SingleList<T>:: SingleList() { Node<T> *p; while(first){ p=first->link; delete first; first=p; 2.的实现

58 单链表的 C++ 实现 template<class T> int SingleList<T>::Length() const { return n; template<class T> bool SingleList<T>::IsEmpty() const { return n==0; 2.的实现

59 单链表的 C++ 实现 template<class T> bool SingleList<T>::Find(int i, T& x) const { if(i<0 i>n-1){ cout<< Out of Bounds ; return false; Node<T> *p=first; for(int j=0; j<i; j++) p=p->link; x=p->element; return true; 2.的实现

60 单链表的 C++ 实现 template<class T> int SingleList<T>::Search(T x) const { Node<T> *p=first; for(int j=0; p&&p->element!=x; j++) p=p->link; if(p) return j; return -1; 2.的实现

61 单链表的插入操作 2.1 线性表的定义和 基本操作 q->link=p->link; p->link=q; 2.的实现

62 单链表的 C++ 实现 template<class T> bool SingleList<T>::Insert(int i, T x) { if(i<-1 i>n-1){ cout<< Out of Bounds ; return false; Node<T> *q=new Node<T>; q->element=x; Node<T> *p=first; for(int j=0; j<i; j++) p=p->link; 2.的实现

63 单链表的 C++ 实现 if(i>-1){ q->link=p->link; p->link=q; else{ q->link=first; first=q; n++; return true; 2.的实现

64 单链表的删除操作 2.1 线性表的定义和 基本操作 q->link=p->link; delete p; 2.的实现

65 单链表的 C++ 实现 template<class T> bool SingleList<T>::Delete(int i) { if(!n){ cout<< UnderFlow <<endl; return false; if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; 2.的实现

66 单链表的 C++ 实现 Node<T> *p=first, *q=first;// 删除 p,q 是 p 的前驱 for(int j=0; j<i-1; j++) q=q->link; if(i==0) first=first->link; b else{ p=q->link; q->link=p->link; delete p; n- -; return true; 2.的实现

67 单链表的 C++ 实现 template<class T> bool SingleList<T>::Update(int i, T x) { if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; Node<T> *p=first; for(int j=0; j<i; j++) p=p->link; p->element=x; return true; 2.的实现

68 单链表的 C++ 实现 template<class T> void SingleList<T>::Output(ostream& out) const { Node<T> *p=first; while(p){ out<<p->element<< ; p=p->link; out<<endl; 2.的实现

69 单链表运算的优缺点 优点插入和删除只需修改一两个指针, 无需移动元素 如已知前驱结点, 插入 删除运算的复杂度为 O(1) 可以动态分配结点空间, 线性表的长度只受内存大小限制缺点查找运算费时, 只能顺序查找, 不能随机查找, 复杂度为 O(n) 2.的实现

70 单链表应用实例 : 求集合的交 求集合 A 和 B 的交 A = A B 用单链表 LA 和 LB 分别表示集合 A 和 B, 交 的结果放在 LA 中, 算法 :? 2.的实现

71 单链表应用实例 : 求集合的交 求集合 A 和 B 的交 A = A B 用单链表 LA 和 LB 分别表示集合 A 和 B, 交 的结果放在 LA 中, 算法 : (1) 置 i = 0 (2) 若 i 小于当前集合 LA 中的元素个数, 则做 (3), 否则转 (6) (3) 取出集合 LA 中 i 位置的元素 x (4) 若 x 不在集合 LB 中, 则将其从 LA 中删除, 否 则 i++ (5) 转 (2) 继续 (6) 结束 2.的实现

72 单链表应用实例 : 求集合的交 #include singlelist.h template<class T> void Intersection(SingleList<T> &LA, SingleList<T> &LB){ T x; int i=0; while(i<la.length()){ LA.Find(i, x); if(lb.search(x)==-1) LA.Delete(i); else i++; 2.的实现

73 前情提要 线性表 顺序表链表 单链表 重点关注插入 删除操作及其运行效率 2.的实现

74 前情提要 : 单链表的插入操作 2.1 线性表的定义和 基本操作 q->link=p->link; p->link=q; 2.的实现

75 前情提要 : 单链表插入操作的 C++ 实现 template<class T> bool SingleList<T>::Insert(int i, T x) { if(i<-1 i>n-1){ cout<< Out of Bounds ; return false; Node<T> *q=new Node<T>; q->element=x; Node<T> *p=first; for(int j=0; j<i; j++) p=p->link; 2.的实现

76 前情提要 : 单链表插入操作的 C++ 实现 if(i>-1){ q->link=p->link; p->link=q; else{ q->link=first; first=q; n++; return true; 2.的实现

77 前情提要 : 单链表的删除操作 2.1 线性表的定义和 基本操作 q->link=p->link; delete p; 2.的实现

78 前情提要 : 单链表删除操作的 C++ 实现 template<class T> bool SingleList<T>::Delete(int i) { if(!n){ cout<< UnderFlow <<endl; return false; if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; 2.的实现

79 前情提要 : 单链表删除操作的 C++ 实现 Node<T> *p=first, *q=first;// 删除 p,q 是 p 的前驱 for(int j=0; j<i-1; j++) q=q->link; if(i==0) first=first->link; else{ p=q->link; q->link=p->link; delete p; n- -; return true; 2.的实现

80 带表头结点的单链表 上述单链表在插入和删除操作时 : 一般情况特殊情况 : 表的最前面进行插入和删除特殊 一般在单链表前增加一个结点 : 表头结点表头结点的数据域 element 为空 / 存放辅助数据, 不存放线性表中的元素 2.的实现

81 带表头结点的单链表 2.1 线性表的定义和 基本操作 每个结点都有一个前驱结点 简化了插入和删除算法的描述 2.的实现

82 带表头结点的单链表 2.1 线性表的定义和 基本操作 每个结点都有一个前驱结点 简化了插入和删除算法的描述 2.的实现

83 带表头结点单链表的 C++ 实现 template<class T> HeaderList<T>::HeaderList() { Node<T> *first = new Node<T>; first->link = NULL; n = 0; 2.的实现

84 带表头结点单链表的 C++ 实现 template<class T> bool HeaderList<T>::Insert(int i, T x) { if(i<-1 i>n-1){ cout<< Out of Bounds <<endl; return false; Node<T> *p=first; for(int j=0; j<=i; j++) p=p->link; 2.的实现

85 带表头结点单链表的 C++ 实现 Node<T> *q=new Node<T>; q->element=x; q->link=p->link; p->link=q; n++; return true; 2.的实现

86 带表头结点单链表的 C++ 实现 template<class T> bool HeaderList<T>::Delete(int i) { if(!n){ cout<< UnderFlow <<endl; return false; if(i<0 i>n-1){ cout<< Out of Bounds <<endl; return false; 2.的实现

87 带表头结点单链表的 C++ 实现 Node<T> *q=first, *p; for(int j=0; j<i; j++) q=q->link; p=q->link; q->link=p->link; delete p; n- -; return true; 2.的实现

88 单循环链表 单链表尾结点的指针域置为第一个结点的地址 (a 0 所 在结点的地址 ) 从表中任一结点出发, 可访问表中所有结点 2.的实现

89 单循环链表 单链表尾结点的指针域置为第一个结点的地址 (a 0 所 在结点的地址 ) 从表中任一结点出发, 可访问表中所有结点 2.的实现

90 课堂练习 1 已知一个带头结点的单链表, 假如该链表只给出了头指针 L, 在不改变链表的前提下设计一个算法 : 查找链表中 倒数 第 k(k 为正整数 ) 个结点, 若查找成功, 输出该结点的 data 值, 并返回 1; 否则, 返回 0 要求 : (1) 描述算法的基本设计思想 (2) 描述算法的详细实现步骤 (3) 根据设计思想和实现步骤, 用程序设计语言描述算法 ( 使用 C 或 C++ 或 Java 语言实现 ), 关键之处请给出简要注释 2.的实现 全国统考 2009

91 课堂练习 1 解析 : (1) 基本思想 : 从头至尾遍历单链表, 用指针 P 指向当前结点的前 k 个结点 当遍历到链表最后一个结点时, P 指向的结点恰为所查找结点 (2) 实现步骤 : 两个指针变量 P 和 P1, 一个整型变量 i 链表从头开始遍历 P1 指向当前遍历的结点,P 指向 P1 所指向的结点的前 k 个结点 若 P1 前没有 k 个结点, 则 P 指向表头结点 i 表示当前遍历的结点个数, 当 i>k 时, P 随着 P1 的前进而前进 当遍历完成时,P 或者指向表头, 或者指向倒数第 k 个结点 2.的实现

92 课堂练习 1 (3) 算法描述 : int LocateElement(linklist list, int k){ P1=list->next; P=list; i=1; while(p1){ P1=P1->next; i++; if(i>k) p=p->next; 2.的实现

93 课堂练习 1 if(p==list) return 0; else{ printf( %d\n, p->data); return 1; 2.的实现

94 课堂练习 2 假定采用带头结点的单链表保存单词, 当两个单词有 相同的后缀时, 则可以共享相同的后缀存储空间 例 如, loading 和 being 的存储映像如图所示 : 2.的实现

95 课堂练习 2 设 str1 和 str2 分别指向两个单词所在单链表的头结点, 请设计一个时间上尽可能高效的算法, 找出由 str1 和 str2 所指的两个链表共同后缀的起始位置 ( 图中字符 i 所在的结点 p) 要求: (1) 给出算法的基本设计思想 (2) 根据设计思想, 用 C 或 C++ 或 Java 语言描述算法, 关键之处给出注释 (3) 说明所设计算法的时间复杂度 全国统考 的实现

96 课堂练习 2 解析 : (1) 算法的基本设计思想 : 第一步 : 分别求出 str1 和 str2 所指的两个链表的长度 m 和 n 第二步 : 将两个表以表尾对齐 : 令指针 p q 分别指向 str1 和 str2 的头结点, 若 m n, 则使 p 指向链表中 m-n+1 个结点 ; 若 m < n, 则 q 指向链表中 n-m+1 个结点, 即使指针 p 和 q 所指的结点到表尾长度相等 ( 其中之一指向开始位置 ) 第三步 : 反复将指针 p 和 q 同步向后移动, 并判断它们是否指向同一结点 2.的实现

97 课堂练习 2 (2) 算法实现 : typedef struct Node{ char data; struct Node *next; SNODE; 2.的实现

98 课堂练习 2 (2) 算法实现 : int listlen(snode* head){ int len=0; while(head->next!= NULL){ len++; head=head->next; return len; 2.的实现

99 课堂练习 2 (2) 算法实现 : SNODE *findlist(snode *str1, SNODE *str2){ int m, n; SNODE *p, *q; m=listlen(str1);//o(m) n=listlen(str2);//o(n) 2.的实现

100 课堂练习 2 // 下面三个循环 O(max(m, n)) for(p=str1;m>n;m- -) p=p->next; for(q=str2;m<n;n- -) q=q->next; while(p->next!= NULL && p->next!= q->next){ p = p->next; q = q->next; return p->next; (3) 算法的时间复杂度为 :O(m+n) 2.的实现

101 前情提要 线性表 顺序表链表 单链表 带表头结点的单链表 单循环链表 重点关注插入 删除操作及其运行效率 2.的实现

102 双向链表 各种单链表上的插入和删除操作 必须从头结点开始沿链查找 时间复杂度? 2.的实现

103 双向链表 各种单链表上的插入和删除操作必须从头结点开始沿链查找时间复杂度 O(n) 有时需要逆向访问继续进化 : 单链表 双向链表添加了 llink 指针 2.的实现

104 双向链表的结点类 template<class T> class DoubleList; template<class T> class DNode { private: T element; DNode<T> *llink, *rlink; friend DoubleList<T>; ; 2.的实现

105 双向链表 2.1 线性表的定义和 基本操作 如图所示为带表头结点的双向循环链表 : 2.的实现

106 双向链表的插入操作 核心步骤 : DNode<T> *q=new DNode<T>; q->element=x; q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q; 2.的实现

107 双向链表的删除操作 核心步骤 : p->llink->rlink=p->rlink; p->rlink->llink=p->llink; delete p; 2.的实现

108 静态链表 链表的数组描述 ( 如果高级程序设计语言没有 指针 类型 ) 数组的每个元素对应于链表中的一个结点 struct SNode{ ELEMTYPE element; int next; 2.的实现

109 静态链表 数组的第 0 个元素看成是表头结点, 其 next 指向链表的第 1 个结点最后一个结点的 next 为 0 线性表 (20, 25, 12, 15) 的表示如下 : 2.的实现

110 静态链表 类似顺序表, 需要预先分配较大的存储空间插入 删除操作时, 不需要移动元素, 只需要修改 指针 ( 下标 ) 例如, 在元素 25 之后插入新元素 9 2.的实现

111 静态链表 new 和 delete 需要自己实现 将未被使用的以及被删除的单元用下标链成 空闲链 表 2.的实现

112 线性表的应用 多项式的算术运算 围绕一元整系数多项式展开讨论 ( 降幂排列 ) 表示类定义算术运算的实现 p(x) = 3x 14 8x 8 + 6x 的实现 每一项均可表示为 coef x exp

113 多项式的算术运算 一个多项式可以看成是由 n 个元素组成的线性表表中元素为多项式中的各项 (coef,exp) 采用何种存储方式的线性表? p(x) = 3x 14 8x 8 + 6x 2 + 2, q(x) = 2x x 8 6x 2 2.的实现 q(x) q(x) + p(x) 链接存储! 频繁插入 删除操作这里采用带表头结点的单循环链表

114 多项式的算术运算 2.1 线性表的定义和 基本操作 2.的实现

115 前情提要 线性表 顺序表链表 单链表 带表头结点的单链表 单循环链表 双向链表 静态链表 重点关注插入 删除操作及其运行效率 2.的实现

116 多项式的算术运算 2.1 线性表的定义和 基本操作 2.的实现

117 项结点的 C++ 类 class Term { public: Term(int c, int e); Term(int c, int e, Term* nxt); Term* InsertAfter(int c, int e); 2.的实现

118 项结点的 C++ 类 private: int coef; int exp; Term *link; friend std::ostream & operator<<(std::ostream &, const Term &); friend class Polynominal; ; 2.的实现

119 项结点 C++ 类的实现 Term::Term(int c, int e) : coef(c), exp(e) { link = 0; Term::Term(int c, int e, Term* nxt) : coef(c), exp(e) { link = nxt; 2.的实现

120 项结点 C++ 类的实现 构造一个新的项结点, 系数为 c, 指数为 e, 并将新节点插入调用该函数的项结点及其后继结点之间 Term* Term::InsertAfter(int c, int e) { link = new Term(c, e, link); return link; 2.的实现

121 q1->insertafter(3, 14); 2.1 线性表的定义和 基本操作 2.的实现

122 项结点 C++ 类的实现 std::ostream &operator<<(std::ostream & out, const Term& val) { if (val.coef == 0) return out; if (!((val.coef == 1 val.coef == -1) && val.exp!= 0)){// Caution: for 1Xˆe and -1Xˆe, this is different from the textbook! out << val.coef; else if (val.coef == -1) out << - ; 2.的实现

123 项结点 C++ 类的实现 switch (val.exp) { case 0:break; case 1:out << X ; break; default: out << Xˆ << val.exp; break; break; return out; 2.的实现

124 多项式的 C++ 类 class Polynominal { public: Polynominal(); Polynominal(); void AddTerms(std::istream& in); void Output(std::ostream& out) const; void PolyAdd(Polynominal& r); 2.的实现

125 多项式的 C++ 类 private: Term* thelist; friend std::ostream & operator << (std::ostream &, const Polynominal &); friend std::istream& operator >> (std::istream&, Polynominal &); friend Polynominal& operator + (Polynominal &, Polynominal &); ; 2.的实现

126 多项式类的实现 : 构造和析构函数 Polynominal::Polynominal() { thelist = new Term(0, -1); thelist->link = thelist; 2.的实现

127 多项式类的实现 : 构造和析构函数 Polynominal:: Polynominal() { Term* p = thelist->link; while (p!= thelist) { thelist->link = p->link; delete p; p = thelist->link; delete thelist; 2.的实现

128 多项式类的实现 : 输入和输出 教材第 31 页第 2 行印刷错误,(0, 1) (0, -1) void Polynominal::AddTerms(std::istream& in) { Term* q = thelist; int c, e; 2.的实现

129 多项式类的实现 : 输入和输出 for (;;) { //std::cout << Input a term (coef, exp):\n << std::endl; std::cin >> c >> e; if (e < 0) break; q = q->insertafter(c, e); 2.的实现

130 多项式类的实现 : 输入和输出 void Polynominal::Output(std::ostream& out) const { int first = 1; Term *p = thelist->link; //std::cout << The polynominal is:\n << std::endl; if (p == thelist){// Caution: for empty polynomial, you should output a 0, and this is different from the textbook! out << 0 ; return; 2.的实现

131 多项式类的实现 : 输入和输出 for (; p!= thelist; p = p->link) { if (!first && (p->coef > 0)) out << + ; first = 0; out << *p; std::cout << std::endl; 2.的实现

132 多项式类的实现 : 多项式相加 q(x) q(x) + p(x) p 和 q 初始分别指向两多项式的最高次结点,q1 指向 q 的前驱结点 对 p(x) 进行遍历 : 若 p->exp < q->exp,q 指示的项为最终相加结果中的一项,p 不动,q 和 q1 右移若 p->exp == q->exp, 系数相加 结果不为零, 则 q 和 q1 右移, 否则从 q(x) 中删除 q 指示的结点,p 右移若 p->exp > q->exp, 则复制 p 所指示的结点, 并将其插入 q1 之后,p 右移 2.的实现

133 多项式类的实现 : 多项式相加 void Polynominal::PolyAdd(Polynominal& r) { Term* q, *q1 = thelist, *p; p = r.thelist->link; q = q1->link; while (p->exp >= 0) { while (p->exp < q->exp) { q1 = q; q = q->link; 2.的实现

134 多项式类的实现 : 多项式相加 if (p->exp == q->exp){ q->coef = q->coef + p->coef; if (q->coef == 0){ q1->link = q->link; delete(q); q = q1->link; else{ q1 = q; q = q->link; 2.的实现

135 多项式类的实现 : 多项式相加 else q1 = q1->insertafter(p->coef, p->exp); p = p->link; 2.的实现

136 多项式类的实现 : 友元函数 std::ostream& operator <<(std::ostream &out, const Polynominal &x){ x.output(out); return out; std::istream& operator >>(std::istream& in, Polynominal &x){ x.addterms(in); return in; 2.的实现

137 多项式类的实现 : 友元函数 Polynominal& operator +(Polynominal &a, Polynominal &b){ a.polyadd(b); return a; 2.的实现

138 主函数 int main() { Polynominal p, q; std::cin >> p; std::cout << p; std::cin >> q; std::cout << q; q = q + p; std::cout << q; return 0; 2.的实现

139 2.1 线性表的定义和 基本操作 2.的实现