搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 安卓情报局 > VIP课程预告2-数据结构与算法

VIP课程预告2-数据结构与算法

安卓情报局 2017-11-02

1.5
栈的递归和实现

汉诺塔的问题:

解决:

1)如果有一个盘子,直接从X移到Z即可。
2)如果有n个盘子要从X移到Z,Y作为辅助。问题可以转化为,先将上面n-1个从X移动到Y,Z作为辅助,然后将第n个从X移动到Z,最后将剩余的n-1个从Y移动到Z,X作为辅助。


完整实现代码,包括栈的实现:


1. // Test.cpp : Defines the entry point for the console application.    

2. //    

3. #include "stdafx.h"    

4. #include <stdio.h>    

5. #include "stdlib.h"  

6. #include <iostream>  

7. using namespace std;  

8. //宏定义    

9. #define TRUE   1    

10. #define FALSE   0    

11. #define OK    1    

12. #define ERROR   0    

13. #define INFEASIBLE -1    

14. #define OVERFLOW -2   

15. #define STACKEMPTY -3    

16.   

17. #define LT(a,b)   ((a)<(b))    

18. #define N = 100           

19.   

20. typedef int Status;    

21. typedef int ElemType;    

22.   

23. typedef struct LNode{    

24.     ElemType        data;                 

25.     struct LNode   *next;       

26. }LNode, *LinkList;   

27.   

28. typedef struct stack{  

29.     LinkList top;  

30. } STACK;  

31.   

32.   

33. /************************************************************************/  

34. /*     接口: 

35. */  

36. /************************************************************************/  

37. void InitStack(STACK &S);  

38. void Push(STACK &S,ElemType e);  

39. void Pop(STACK &S, ElemType *e);  

40. ElemType GetTop(STACK S,ElemType *e);  

41. int StackEmpty(STACK S);  

42.   

43. /************************************************************************/  

44. /*  

45. */  

46. /************************************************************************/  

47. void InitStack(STACK &S)  

48. {  

49.     S.top=NULL;  

50. }  

51.   

52. /************************************************************************/  

53. /* 入栈  

54. */  

55. /************************************************************************/  

56. void Push(STACK &S,ElemType e)  

57. {  

58.     LinkList p;  

59.     p = (LinkList )malloc(sizeof(LNode));  

60.     if (!p) exit(OVERFLOW);  

61.     p->data = e;  

62.     p->next = S.top;  

63.     S.top = p;  

64. }  

65. /************************************************************************/  

66. /* 出栈 

67. */  

68. /************************************************************************/  

69. void Pop(STACK &S, ElemType *e)  

70. {  

71.     LinkList p;  

72.     if(StackEmpty(S)) exit(STACKEMPTY);  

73.     *e = S.top->data;  

74.     p = S.top;  

75.     S.top = p->next;   

76.     free(p);  

77. }  

78. /************************************************************************/  

79. /* 获取栈顶元素内容  

80.  

81. */  

82. /************************************************************************/  

83. ElemType GetTop(STACK S, ElemType *e)  

84. {  

85.     if(StackEmpty(S)) exit(STACKEMPTY);  

86.     *e = S.top->data;  

87. }  

88. void printStack(STACK S){  

89.     LinkList p;  

90.     p = S.top;  

91.     printf("栈: ");  

92.     while (p) {  

93.         printf("%d ", p->data);  

94.         p = p->next;  

95.     }  

96. }  

97. /************************************************************************/  

98. /* 如果有一个盘子,直接从X移到Z即可。 

99. 如果有n个盘子要从X移到Z,Y作为辅助。问题可以转化为,先将上面n-1个从X移动到Y,Z作为辅助,然后将第n个从X移动到Z,最后将剩余的n-1个从Y移动到Z,X作为辅助。 

100. */  

101. /************************************************************************/  

102.   

103. void move(STACK &Sa,STACK &Sb)  

104. {     

105.     ElemType e;  

106.     Pop(Sa,&e);  

107.     Push(Sb, e);  

108. }  

109. void hanoi(int n,STACK  &X,STACK &Y,STACK &Z)  

110. {  

111.     if(n==1) return move(X, Z);     //将圆盘1号直接移到z  

112.     hanoi(n-1,X,Z,Y);               //将x上的1大n-1圆盘移到y,z做辅助塔  

113.     move(X, Z);                     //将编号为n的圆盘移z  

114.     hanoi(n-1,Y,X,Z);               //将y上的1大n-1圆盘移到z,x做辅助塔  

115. }  

116.   

117. /************************************************************************/  

118. /* 判断栈S是否空  

119. */  

120. /************************************************************************/  

121. int StackEmpty(STACK S)   

122. {  

123.     if(S.top==NULL) return TRUE;  

124.     return   FALSE;  

125. }  

126.   

127. void main()    

128. {    

129.   

130.     STACK Sx, Sy,Sz;  

131.     InitStack( Sx);  

132.     InitStack( Sy);  

133.     InitStack( Sz);  

134.     int i, n = 10;  

135.     for (i = 10 ; i>=1 ;i--) {  

136.         Push(Sx, i);  

137.     }  

138.     printStack(Sx);  

139.     hanoi(n,  Sx,Sy,Sz);  

140.     printStack(Sz);  

141. }    


VIP课程预告2-数据结构与算法


队列

队列定义

队列(Queue)也是一种运算受限的线性表它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进)允许删除的一端称为队尾(rear),允许插入的一端称为队头 (Front)

,队列的操作原则是先进先出的,所以队列又称作FIFO表(First In First Out)

队列的基本运算也有六种:

置空队 :InitQueue(Q)

判队空: QueueEmpty(Q)

判队满: QueueFull(Q)

入队 : EnQueue(Q,x)

出队 : DeQueue(Q)

取队头元素: QueueFront(Q),不同与出队,队头元素仍然保留。


队列也有顺序存储和链式存储两种存储结构,前者称顺序队列,后者为链队


对于顺序队列,我们要理解"假上溢"的现象。


我们现实中的队列比如人群排队买票,队伍中的人是可以一边进去从另一头出来的,除非地方不够,总不会有"溢出"的现象,相似地,当队列中元素完全充满这个向量空间时,再入队自然就会上溢,如果队列中已没有元素,那么再要出队也会下溢。

那么"假上溢"就是怎么回事呢?


因为在这里,我们的队列是存储在一个向量空间里,在这一段连续的存储空间中,由一个队列头指针和一个尾指针表示这个队列,当头指针和尾指针指向同一个位置时,队列为空,也就是说,队列是由两个指针中间的元素构成的。在队列中,入队和出队并不是象现实中,元素一个个地向前移动,走完了就没有了,而是指针在移动,当出队操作时,头指针向前(即向量空间的尾部)增加一个位置,入队时,尾指针向前增加一个位置,在某种情况下,比如说进一个出一个,两个指针就不停地向前移动,直到队列所在向量空间的尾部,这时再入队的话,尾指针就要跑到向量空间外面去了,仅管这时整个向量空间是空的,队列也是空的,却产生了"上溢"现象,这就是假上溢。


为了克服这种现象造成的空间浪费,我们引入循环向量的概念,就好比是把向量空间弯起来,形成一个头尾相接的环形,这样,当存于其中的队列头尾指针移到向量空间的上界(尾部)时,再加1的操作(入队或出队)就使指针指向向量的下界,也就是从头开始。这时的队列就称循环队列


通常我们应用的大都是循环队列。由于循环的原因,光看头尾指针重叠在一起我们并不能判断队列是空的还是满的,这时就需要处理一些边界条件,以区别队列是空还是满。方法至少有三种,一种是另设一个布尔变量来判断(就是请别人看着,是空还是满由他说了算),第二种是少用一个元素空间,当入队时,先测试入队后尾指针是不是会等于头指针,如果相等就算队已满,不许入队。第三种就是用一个计数器记录队列中的元素的总数,这样就可以随时知道队列的长度了,只要队列中的元素个数等于向量空间的长度,就是队满。


VIP课程预告2-数据结构与算法


2.2
队列的顺序储存

顺序存储如图:

VIP课程预告2-数据结构与算法

由于是顺序存储结构的存储空间是静态分配的,所以在添加数据的时,有可能没有剩余空间的情况。


解决这种“假溢出”情况,使用循环队列在c语言中,不能用动态分配的一维数组来实现循环队列。若使用循环队列,必须设置最大队列长度,若无法估计最大长度,就使用链式队列。

c实现:


1. // Test.cpp : Defines the entry point for the console application.    

2. //    

3. #include "stdafx.h"    

4. #include <stdio.h>    

5. #include "stdlib.h"  

6. #include <iostream>  

7. using namespace std;  

8. //宏定义    

9. #define TRUE   1    

10. #define FALSE   0    

11. #define OK    1    

12. #define ERROR   0    

13. #define INFEASIBLE -1    

14. #define OVERFLOW -2   

15. #define QUEUEEMPTY  -3    

16.         

17. #define MAX_QUEUE 10 //队列的最大数据元素数目  

18.   

19. typedef int Status;    

20. typedef int ElemType;    

21.   

22. typedef struct queue{    

23.     ElemType        elem[MAX_QUEUE] ;     ///假设当数组只剩下一个单元时认为队满            

24.     int front;      //队头指针  

25.     int rear;       //队尾指针     

26. }QUEUE;   

27.   

28.   

29. /************************************************************************/  

30. /*     各项基本操作算法。 

31. */  

32. /************************************************************************/  

33. void InitQueue(QUEUE *&Q);  

34. void EnQueue(QUEUE *Q,ElemType elem);  

35. void DeQueue(QUEUE *Q,ElemType *elem);  

36. int QueueEmpty(QUEUE Q);  

37.   

38. /************************************************************************/  

39. /*  

40.   初始化 

42. */  

43. /************************************************************************/  

44. void InitQueue(QUEUE *&Q)   

45. {  

46.   

47.     Q = (QUEUE *) malloc (sizeof(QUEUE));  

48.     Q->front = Q->rear = -1;  

49.   

50. }  

51. /************************************************************************/  

52. /*     入队                                                               

53. */  

54. /************************************************************************/  

55.    

56. void EnQueue(QUEUE *Q, ElemType elem)  

57. {  

58.     if((Q->rear+1)% MAX_QUEUE == Q->front) exit(OVERFLOW);  

59.     Q->rear = (Q->rear + 1)%MAX_QUEUE;  

60.     Q->elem[Q->rear] = elem;   

61. }  

62. /************************************************************************/  

63. /*     出队                                                                

64. */  

65. /************************************************************************/  

66. void DeQueue(QUEUE *Q,ElemType *elem)  

67. {  

68.     if (QueueEmpty(*Q))  exit(QUEUEEMPTY);  

69.     Q->front =  (Q->front+1) % MAX_QUEUE;  

70.     *elem=Q->elem[Q->front];  

71. }  

72. /************************************************************************/  

73. /*    获取队头元素内容                                                             

74. */  

75. /************************************************************************/  

76.   

77. void GetFront(QUEUE Q,ElemType *elem)   

78. {  

79.     if ( QueueEmpty(Q) )  exit(QUEUEEMPTY);  

80.     *elem = Q.elem[ (Q.front+1) % MAX_QUEUE ];  

81. }  

82. /************************************************************************/  

83. /*    判断队列Q是否为空                                                              

84. */  

85. /************************************************************************/  

86. int QueueEmpty(QUEUE Q)  

87. {  

88.     if(Q.front==Q.rear) return TRUE;  

89.     else return FALSE;  

90. }  

91.   

92. void main()    

93. {    

94.   

95.     QUEUE *Q;  

96.     InitQueue( Q);  

97.     EnQueue( Q, 1);  

98.     EnQueue( Q, 2);  

99.     ElemType e;  

100.     DeQueue( Q,&e);  

101.     cout<<"De queue:"<<e;  

102. }    


VIP课程预告2-数据结构与算法


2.3
链式队列

1. // Test.cpp : Defines the entry point for the console application.    

2. //    

3. #include "stdafx.h"    

4. #include <stdio.h>    

5. #include "stdlib.h"  

6. #include <iostream>  

7. using namespace std;  

8. //宏定义    

9. #define TRUE   1    

10. #define FALSE   0    

11. #define OK    1    

12. #define ERROR   0    

13. #define INFEASIBLE -1    

14. #define OVERFLOW -2   

15. #define QUEUEEMPTY  -3    

16.         

17.   

18. typedef int Status;    

19. typedef int ElemType;    

20.   

21. typedef struct LNode {          //链式队列的结点结构  

22.     ElemType elem;          //队列的数据元素类型  

23.     struct LNode *next;      //指向后继结点的指针  

24. }LNode, *LinkList;  

25.   

26. typedef struct queue{   //链式队列  

27.     LinkList front;     //队头指针  

28.     LinkList rear;      //队尾指针  

29. }QUEUE;   

30.   

31. /************************************************************************/  

32. /*     各项基本操作算法。 

33. */  

34. /************************************************************************/  

35. void InitQueue(QUEUE *Q);  

36. void EnQueue(QUEUE *Q,ElemType elem);  

37. void DeQueue(QUEUE *Q,ElemType *elem);  

38. void GetFront(QUEUE Q,ElemType *elem) ;  

39. bool QueueEmpty(QUEUE Q);  

40.   

41. /************************************************************************/  

42.   

43.   

44. /*初始化队列Q  */  

45. void InitQueue(QUEUE *Q)  

46. {  

47.     Q->front = (LinkList)malloc(sizeof(LNode));  

48.     if (Q->front==NULL) exit(ERROR);  

49.     Q->rear= Q->front;  

50. }  

51. /*入队 */   

52. void EnQueue(QUEUE *Q,ElemType elem)  

53. {  

54.     LinkList s;  

55.     s = (LinkList)malloc(sizeof(LNode));  

56.     if(!s) exit(ERROR);  

57.     s->elem = elem;  

58.     s->next = NULL;  

59.     Q->rear->next = s;  

60.     Q->rear = s;  

61. }  

62.   

63. /*出队  */   

64. void DeQueue(QUEUE *Q,ElemType *elem)  

65. {  

66.     LinkList s;  

67.     if(QueueEmpty(*Q)) exit(ERROR);  

68.     *elem = Q->front->next->elem;  

69.     s = Q->front->next;  

70.     Q->front->next = s->next;  

71.     free(s);  

72. }  

73. /*获取队头元素内容  */   

74.   

75. void GetFront(QUEUE Q,ElemType *elem)   

76. {  

77.     if(QueueEmpty(Q)) exit(ERROR);  

78.     *elem = Q.front->next->elem;  

79. }  

80. /*判断队列Q是否为空   */   

81. bool QueueEmpty(QUEUE Q)  

82. {  

83.     if(Q.front == Q.rear) return TRUE;  

84.     return FALSE;  

85. }  

86.   

87. void main()    

88. {    

89.   

90.     QUEUE Q;  

91.     InitQueue( &Q);  

92.     EnQueue( &Q, 1);  

93.     EnQueue( &Q, 2);  

94.     ElemType e;  

95.     DeQueue( &Q,&e);  

96.     cout<<"De queue:"<<e;  

97. }    



2.4

队列的应用

【举例1】银行排队


【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时,会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然,这样会降低主机的使用效率。为此人们设想了一种办法:为打印机设置一个打印数据缓冲区,当主机需要打印数据时,先将数据依次写入这个缓冲区,写满后主机转去做其他的事情,而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印,这样做即保证了打印数据的正确性,又提高了主机的使用效率。由此可见,打印机缓冲区实际上就是一个队列结构。


【举例3CPU分时系统
在一个带有多个终端的计算机系统中,同时有多个用户需要使用CPU运行各自的应用程序,它们分别通过各自的终端向操作系统提出使用CPU的请求,操作系统通常按照每个请求在时间上的先后顺序,将它们排成一个队列,每次把CPU分配给当前队首的请求用户,即将该用户的应用程序投入运行,当该程序运行完毕或用完规定的时间片后,操作系统再将CPU分配给新的队首请求用户,这样即可以满足每个用户的请求,又可以使CPU正常工作。



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《VIP课程预告2-数据结构与算法》的版权归原作者「安卓情报局」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注安卓情报局微信公众号

安卓情报局微信公众号:AndroidCIA

安卓情报局

手机扫描上方二维码即可关注安卓情报局微信公众号

安卓情报局最新文章

精品公众号随机推荐