数据结构 Data Structure

Transcription

1 第三章 : 线性表

2 线性表 定义 : 线性表 L 是 n 个数据元素 a 0,a, a n- 的有限序列, 记作 L=(a 0,a, a n- ) 其中元素个数 n(n 0) 定义为表 L 的长度 当 n=0 时,L 为空表, 记作 ( ) 特性 : 在表中, 除第一个元素 a 0 外, 其他每一个元素 a i 有一个且仅有 一个直接前驱 a i- 除最后一个元素 a n- 外, 其他每一个元素 a i 有一个且仅有一个直接后继 a i+ a 0 为第一个元素, 又称为表 头元素 ; a n- 为最后一个元素, 又称为表尾元素 2

3 线性表的抽象数据类型 (ADT) template <typename E> class List { public: List() {} virtual ~List() {} virtual void clear()=0; virtual void insert(const E& item)=0; virtual void append(const E& item)=0; virtual E remove()=0; virtual void movetostart()=0; virtual void movetoend()=0; virtual void prev()=0; virtual void next()=0; virtual int length() const=0; virtual int currpos() const=0; virtual void movetopos(int pos)=0; virtual bool getvalue(elem&) const=0; virtual const E& getvalue() const=0;

4 顺序表的实现 采用连续的存储单元依次存储线性表中各元素 我们称这种存储方式为顺序存储方式, 按这种存储方式所得到的线性表叫顺序表 顺序表具有这样的一个特点 : 逻辑上相邻的元素在物理上一定相邻 4

5 顺序表类的定义 template <typename E> class AList :public List<E> { private: int maxsize; int listsize; int curr; E* listarray; public: 5

6 顺序表类成员函数的实现 顺序表结点插入操作 void insert(const E& it) { Assert (listsize<maxsize, List capacity exceeded ) ;// 边界检查 for (int i=listsize;i>curr;i--) // 移位 listarray[i]=listarray[i-]; listarray[curr]=it; listsize++; } 6

7 顺序表的插入图示 k 0 k k 0 k k 0 k position k 2 k k 4 position k 2 k position k 2 x k k 5 k 6 k 4 k 5 k 4 k 5 k 6 k 6 7 7

8 顺序表结点删除操作 E remove() { Assert ((curr>=0) &&(curr<listsize), No element );// 边界检查 E it=listarray[curr]; for (int i=curr;i<listsize-;i++) // 移位 listarray[i]=listarray[i+]; listsize--; return it; } 8

9 顺序表的删除图示 k 0 k 0 k k position k 2 position k 2 k k 4 k 4 k 5 k 5 k 6 k 6 9 9

10 链表 特点 : 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻 的元素 每个数据元素 ai, 除存储本身信息外, 还需存储其直 接后继的信息 结点 数据域 : 元素本身信息 指针域 : 指示直接后继的存储位置 结点数据域指针域 0

11 链表 template <typename E> class Link { public: E element; // value for this node Link *next; // Pointer to next node in list Link(const E& elemval, Link* nextval=null) { element=elemval; next=nextval; } Link(link* nextval=null) { next=nextval; } }

12 单链表类 template <typename E> class LList :public List<E> { private: Link<E>* head; Link<E>* tail; Link<E>* curr; int cnt; void init(){ curr=tail=head=new Link<E>; cnt=0; } void removeall(){ while (head!=null) { curr=head; head=head->next; delete curr; } } 2

13 单链表类 public: LLlist(int size=defaultlistsize){init();} ~LList(){removeall();} void clear(){removeall();init();} bool insert(const E& it); bool append(const E& it); E remove(); void movetostart() {curr=head;} void movetoend() {curr=tail;} void prev(); void next(); int length() const {return cnt;} int currpos() const; void movetopos(int pos); const E& getvalue() const; }

14 单链表的结点插入 void insert(const E& it) { curr->next=new link<e>(it, curr->next); if (tail == curr) tail =curr->next; cnt++; } 创建新的结点并且赋给新值 new link<e>(it, curr->next); 当前结点元素的 next 域要指向新插入的结点 curr->next=new link<e>(it, curr->next); 4

15 单链表的插入 head tail 在 2 和 2 之间插入 0 head tail 创建新结点 2. 新结点指向右边的结点. 左边结点指向新结点 5 5

16 单链表结点的删除 E remove() { Assert(curr->next!=NULL, No element ); E it =curr->next->element; link<e>* ltemp =curr->next; if (tail == ltemp) tail =curr; curr->next =curr->next->next; delete ltemp; cnt--; return it; } 6

17 单链表删除示意 head p. x. 用 p 指向元素 x 的结点, 可以吗? x. p 7 7

18 删除值为 x 的结点 q p p q = p next; p next = q next; free(q); x 8 8

19 循环链表 循环链表是表中最后一个结点的指针指向头结点, 使链表构成环状 特点 : 从表中任一结点出发均可找到表中其他结点, 提高查找效率 操作与单链表基本一致, 循环条件不同 单链表 p:p->link=null 循环链表 p:p->link=h h 空表 h 9

20 双链表 双向链表是指在前驱和后继方向都能遍历的线性链 表 双向链表每个结点结构 : prev ( 左链指针 ) element ( 数据 ) nextt ( 右链指针 ) 前驱方向 后继方向 双向链表通常采用带表头结点的循环链表形式 20

21 双链表 非空表 空表 结点指针的指向 p == p llink rlink == p rlink llink 2

22 双链表结点 template <typename E> class link { private: static Link<E> *freelist; public: E element; Link* next; Link* prev; Link(const E& it, Link* prevp, Link* nextp) { element=it; prev=prevp; next=nextp; } Link(Link* prevp=null,link* nextp=null) { prev=prevp;next=nextp; } void* operator new(size_t); void operator delete(void*); } 22

23 双链表插入示意 p p next k i- k i k i+ q q prev = p; x q next = p next; p next prev = q; p next = q; 2 2

24 双链表的插入 void insert(const E& it) { curr->next=curr->next->prev =new Link<E>(it,curr,curr->next); cnt++; } 24

25 双链表删除示意 p prev p p next k i- k i k i+ prev next p prev next = p next p next prev = p prev 25 25

26 双链表的删除 E remove() { if (curr->next==tail) return NULL; E it =curr->next->element; link<e>* ltemp =curr->next; curr->next->next->prev=curr; curr->next= curr->next->next; delete ltemp; cnt--; return it; } 26

27 约瑟夫问题 : 背景 约瑟夫问题 (JosephusProblem) 据说著名犹太历史学家 Josephus 有过以下的故事 : 在罗马人占领乔塔帕特后,9 个犹太人与 Josephus 及他的朋友躲到一个洞中,9 个犹太个人开始报数, 每报数到第 人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止 然而 Josephus 和他的朋友并不想遵从,Josephus 要他的朋友先假装遵都自杀身亡为止 然而 Josephus 和他的朋友并不想遵从,Josephus 要他的朋友先假装遵从, 他将朋友与自己安排在第 6 个与第 个位置, 于是逃过了这场死亡游戏 205 年 5 月 2 日星期四 27

28 约瑟夫问题 : 描述 问题描述设编号为 -n 的 n(n>0) 个人按顺时针方向围成一圈. 首先第 个人从 开始顺时针报数. 报 m 的人 (m 为正整数 ). 令其出列 然后再从他的下一个人开始, 重新从 顺时针报数, 报 m 的人, 再令其出列 如此下去, 直到圈中所有人出列为止 求出列编号序列 基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用链表来实现线性表 205 年 5 月 2 日星期四 28

29 解法一 :( 使用循环链表模拟整个游戏过程 ) 基本思路 由于约瑟夫环本身具有循环性质, 考虑采用循环链表, 为了统一对表中任意节点的操作, 循环链表不带头结点 每个结点的编号依次为,2,,n 初始当前位置为最后一个结点, 每次从当前位置向前移动 m- 步, 则下一个结点即为要淘汰的结点, 删掉当前要淘汰的节点, 将前一节点和后一节点连接在一起, 重复上述过程, 从而得到出列编号序列 算法的时间复杂度为 O(nm) 205 年 5 月 2 日星期四 29

30 使用循环链表 #include<iostream> using namespace std; class Link { // 建立结点类 public: int element; Link* next; Link(const int elemval,link* nextval=null) { element=elemval; next=nextval; } Link(Link* nextval=null) { next=nextval; } }; 205 年 5 月 2 日星期四 0

31 使用循环链表 class LList { // 建立循环链表类 private: void removeall() { // 删除链表中所有结点 while(cnt>0) { curr=head; head=head->next; tail->next=head; delete curr; cnt--; } } public: int cnt; // 当前链表中的结点数目 Link * curr; // 当前结点的指针 Link * head; // 第一个结点的指针 Link * tail; // 最后一个结点的指针 205 年 5 月 2 日星期四

32 使用循环链表 LList(){ // 构造函数 cnt=0; curr=tail=head=null; } ~LList() {removeall();} // 析构函数 void append(const int it) { // 在循环链表的末尾追加一个结点 if(cnt==0) curr=tail=head=new Link(it); else { tail->next=new Link(it); tail=tail->next; } tail->next=head; cnt++; } 205 年 5 月 2 日星期四 2

33 使用循环链表 bool remove(int &it){ // 删除当前指针的下一个结点 if(cnt==0) return false; it=curr->next->element; Link* Itemp=curr->next; if(tail==curr->next) tail=curr; curr->next=curr->next->next; delete Itemp; cnt--; return true; } }; 205 年 5 月 2 日星期四

34 使用循环链表 void main() { int i, m, n, it; LList L; cout<<" 请输入总共的人数和出列人数的号码 ( 从 开始 )"<<endl; cin>>n>>m; /* 读入数据 */ for(i=;i<n+;i++) L.append(i); L.curr=L.tail; // 初始当前指针指向最后一个结点 while(l.cnt>0) { for(i=;i<=m-;i++) { // 每次从当前位置向前移动 m- 步 L.curr=L.curr->next; } if(l.remove(it)) cout<<it<< ; // 删除下一个结点并返回编号 } cout<<endl; system("pause"); } 205 年 5 月 2 日星期四 4

35 解法二 :( 使用数学公式推导 ) 问题描述 :n 个人 ( 编号 0~(n-)), 从 0 开始报数, 报到 (m-) 的退出, 剩下的人继续从 0 开始报数 求胜利者的编号 第一个被淘汰的编号为 (m-)%n, 剩下的 n- 人组成了一个新的约瑟夫环 ( 以编号为 k=m%n 的人开始 ), 做一个简单的映射 : k -----> 0 k >... k > n-2 假如知道 n - 个人的最后胜利者的编号为 x, 利用映射关系逆推, 就可以得出 n 个人的胜利者的编号为 (x + k) % n 其中 k 等于 m % n 代入 (x + k) % n <=> (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n 205 年 5 月 2 日星期四 5

36 解法二 :( 使用数学公式推导 ) 第二个被淘汰的编号为 (m-)%(n-), 同样剩下的 n-2 人组成了一个新的约瑟夫环 ( 以编号为 k=m%(n-) 的人开始 ) 要得到 n - 个人问题的解, 只需得到 n - 2 个人问题的解, 倒推下去 只有一个人时, 胜利者就是编号 0 下面给出递推式: f [] = 0; f [ i ] = ( f [i -] + m) % i; (i>) 时间复杂度为 O(n) 205 年 5 月 2 日星期四 6

37 数学公式 #include<iostream.h> void main() { int n,m,s = 0; cout<<" 请输入人数 n:"<<endl; cin>>n; cout<<" 请输入数字 m:"<<endl; cin>>m; for(int i = 2; i <= n; i++) { s = (s + m) % i; //cout<<s<<" "; } cout<<" 最后一人是 : "<<s+<<endl; } 205 年 5 月 2 日星期四 7

38 约瑟夫环 (Joseph Circle) 问题描述 : 编号为,2,...,n 的 n 个人按顺时针方向围坐一圈, 每人持有一个密码 ( 正整数 ) 现在给定一个随机数 m>0, 从编号为 的人开始, 按顺时针方向 开始顺序报数, 报到 m 时停止 报 m 的人出圈, 同时留下他的密码作为新的 m 值, 从他在顺时针方向上的下一个人开始, 重新从 开始报数, 如此下去, 直至所有的人全部出列为止 205 年 5 月 2 日星期四 8

39 约瑟夫环 (Joseph Circle) 例 : start 5 k= 2 8 k: 计数 m: 密码 出队序列 : 205 年 5 月 2 日星期四 9

40 例 : start 约瑟夫环 (Joseph Circle) 5 k=2 2 8 k: 计数 m: 密码 出队序列 : 205 年 5 月 2 日星期四 40

41 约瑟夫环 (Joseph Circle) 例 : start 2 8 k: 计数 m: 密码 7 5 k= 出队序列 : 205 年 5 月 2 日星期四 4

42 约瑟夫环 (Joseph Circle) 例 : start 2 8 k: 计数 m: 密码 k=4 5 出队序列 : 205 年 5 月 2 日星期四 42

43 约瑟夫环 (Joseph Circle) 例 : start 2 8 k: 计数 m: 密码 7 5 出队序列 : k= 存入密码 205 年 5 月 2 日星期四 4

44 约瑟夫环 (Joseph Circle) 例 : start 2 8 k: 计数 m: 密码 k= 出队序列 : 年 5 月 2 日星期四 44

45 例 : start 约瑟夫环 (Joseph Circle) 4 k=4 2 8 k: 计数 m: 密码 出队序列 : 年 5 月 2 日星期四 45

46 约瑟夫环 (Joseph Circle) 例 : start k: 计数 m: 密码 7 5 k= 出队序列 : 年 5 月 2 日星期四 46

47 例 : start 约瑟夫环 (Joseph Circle) k: 计数 m: 密码 k= 出队序列 : 年 5 月 2 日星期四 47

48 例 : start 约瑟夫环 (Joseph Circle) k: 计数 m: 密码 9 k= 出队序列 : 年 5 月 2 日星期四 48

49 例 : start 约瑟夫环 (Joseph Circle) k: 计数 m: 密码 9 k= 出队序列 : 年 5 月 2 日星期四 49

50 约瑟夫环 (Joseph Circle) 例 : start 5 k= k: 计数 m: 密码 4 22 出队序列 : 年 5 月 2 日星期四 50

51 例 : start 约瑟夫环 (Joseph Circle) k: 计数 m: 密码 4 22 k=5 5 出队序列 : 年 5 月 2 日星期四 5

52 约瑟夫环 (Joseph Circle) 例 : start 2 2 k= k: 计数 m: 密码 出队序列 : 年 5 月 2 日星期四 52

53 例 : start 约瑟夫环 (Joseph Circle) k: 计数 m: 密码 k= 出队序列 : 年 5 月 2 日星期四 5

54 约瑟夫环 (Joseph Circle) 例 : start k= k: 计数 m: 密码 出队序列 : 年 5 月 2 日星期四 54

55 约瑟夫环 (Joseph Circle) 例 : start k= k: 计数 m: 密码 出队序列 : 年 5 月 2 日星期四 55

56 数据结构 使用数组实现单向循环链表 使用整形数组 que[],que[i] 记录了第 i 个位置上人紧挨着的下一个人的位置 每次找到一个被删除的人, 取出删除位置上的密码, 且将其删除 205 年 5 月 2 日星期四 56

57 Solution #include <stdio.h> void joseph(int m,int n,int a[]) { int i,que[n+],j; for(i=;i<n;++i) que[i]=i+; que[n]=; i=n; while(que[i]!=i) { for(j=;j<m;++j) i=que[i]; printf("%d ",que[i]); m=a[que[i]]; que[i]=que[que[i]]; } printf("%d\n",i); } int main(){ int n,m,a[20],i; while(scanf("%d%d",&n,&m),n m) { for(i=;i<=n;++i) scanf("%d",a+i); joseph(m,n,a); } return 0; } 205 年 5 月 2 日星期四 57

58 线性表实现方法的比较 顺序表 插入 删除运算时间代价 O(n) 预先申请固定长度的数组 如果整个数组元素很满, 则没有结构性存储开销链表 插入 删除运算时间代价 O() 但找第 i 个元素删除运算时间 代价 O(n) 存储利用指针, 动态地按照需要为表中新的元素分配存储 空间 每个元素都有结构性存储开销 58

59 顺序表和链表存储密度的临界值 n 表示线性表中当前元素的数目, P 表示指针的存储单元大小小 ( 通常为 4 个字节 ) E 表示数据元素的存储单元大小 D 表示可以在数组中存储的线性表元素的最大数目 空间需求 顺序表的空间需求为 DE 链表的空间需求为 n(p+e) n 的临界值, 即 n>de/(p+e) n 越大, 顺序表的空间效率就更高 如果 P=E, 则临界值为 n=d/2 59

60 根据应用选择顺序表和链表 顺序表 结点总数目大概可以估计 线性表中结点比较稳定 ( 插入删除操作少 ) n>de/(p+e) 链表 结点数目无法预知 线性表中结点动态变化 ( 插入删除多 ) n<de/(p+e) 60

61 Thank you!!! 6