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

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

安卓情报局 2017-11-02

数据结构与算法

第一节:数据结构-线性表


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

告示:因为我们VIP课程在本周就要开始讲数据结构与算法了,所以,提前两天给大家发一点资料。好啦,安静,安静。都坐下。我又不是第一次泄漏学院的机密了。再泄漏一次咯。

      你们难道不打算感谢本仙女吗?


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


1
线性表:N个数据元素的有序集合

线性表是一种常用的数据结构在实际应用中,线性表都是以、队列、字符串数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。  线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。


特征:

1.集合中必存在唯一的一个“第一元素”;
2.集合中必存在唯一的一个 “最后元素” ;
3.除最后一个元素之外,均有 唯一的后继(后件);
4.除第一个元素之外,均有 唯一的前驱(前件)。

java中的List接口,就是线性表。ArrayList就是顺序线性表,LinkedList就是链表线性表。



VIP课程预告1-数据结构与算法
2
线性表的顺序表示:ArrayList

优点:在于随机访问元素,

缺点:插入和和删除的时候,需要移动大量的元素。

c语言实现代码:

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

2. //  

3.   

4. #include "stdafx.h"  

5. #include <stdio.h>  

6. #include "stdlib.h"  

7. //宏定义  

8. #define TRUE   1  

9. #define FALSE   0  

10. #define OK    1  

11. #define ERROR   0  

12. #define INFEASIBLE -1  

13. #define OVERFLOW -2  

14.   

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

16. #define N = 100         

17.   

18. #define LIST_INIT_SIZE 100 //线性表初始空间分配量  

19. #define LISTINCREMENT   10 //线性表空间分配的增量  

20.   

21. typedef int Status;  

22. typedef int ElemType;  

23.   

24. typedef struct LNode{  

26.     int      lenght;        //当前的长度  

27.     int      listsize;      //当前分配的存储容量  

28. }SqList;  

29.   

30. /** 

31.  *构造空的线性表 

32.  */  

33.   

34. Status initList(SqList &L, int lenght){  

35.     if (lenght == 0) lenght = LIST_INIT_SIZE;  

36.     L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));  

37.     if(!L.elem) exit(OVERFLOW);  //分配存储空间失败  

38.     L.lenght = 0;                //初始空表长度为0  

39.     L.listsize = lenght ;//初始存储容量为100  

40.     return OK;  

41. }  

42. /************************************************************************/  

43. /* 在第i位置插入e 

44. */  

45. /************************************************************************/  

46. Status insertList(SqList &L, ElemType e, int i){  

47.     ElemType *p,  *q;  

48.     if(i<0 ||i > L.lenght) return ERROR;  //i值不合法  

49.     if (L.lenght >= L.listsize) {  

50.         ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));  

51.         if(!newbase) return OVERFLOW;   //存储分配失败    

52.         L.elem = newbase;               //新基值  

53.         L.listsize += LISTINCREMENT;    //增加存储容量  

54.     }  

55.     q = &L.elem[i];                     //q为插入的位置  

56.     for (p = &L.elem[L.lenght]; p>=q; --p) {  

57.         *p = *(p-1);                    //i元素之后的元素往后移动  

58.     }  

59.     *q = e;                             //插入e  

60.     L.lenght +=1;  

61.     return OK;  

62.   

63. }  

64. /************************************************************************/  

65. /* 快速排序  

66. */  

67. /************************************************************************/  

68. void sortList(SqList &L){  

69.       

70.   

71. }  

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

73. /* 删除第i位置元素,并用e返回其值                                                                     */  

74. /************************************************************************/  

75. Status deleteListElem(SqList &L, int i, ElemType &e){  

76.     int *p,  *q;  

77.     if(i<0 ||i > L.lenght) return ERROR;  //i值不合法  

78.     q = &L.elem[i];                       //被删除元素的位置为i,L.elem就是数组名,  

79.     e = *q;                               //被删除元素的值赋值给e  

80.     for (p = q; p< (L.elem + L.lenght); p++){ //元素左移  

81.         *p = *(p+1);  

82.     }  

83.     --L.lenght;  

84.     return OK;  

85. }  

86.   

87. /************************************************************************/  

88. /*  快速排序 

89. */  

90. /************************************************************************/  

91.   

92. int partition(SqList &L, ElemType low, ElemType high){  

93.     ElemType pivotkey = L.elem[low];               //枢轴记录关键字  

94.     while (low < high) {                  //从表的两端向中间扫描  

95.         while (low < high &&  L.elem[high] >= pivotkey ) --high;//高端位置扫描  

96.         L.elem[low] = L.elem[high];     //交换数据,小于pivotkey移到低端  

97.         L.elem[high] = pivotkey;  

98.   

99.         while (low < high && L.elem[low] <= pivotkey ) ++low;     //低端扫描  

100.         L.elem[high] = L.elem[low];               //交换数据 大于pivotkey移到高端  

101.         L.elem[low] = pivotkey;                                   

102.     }  

103.     return low;  

104. }  

105.   

106. void quickSort(SqList &L, ElemType low, ElemType high){  

107.     int pivot;  

108.     if(low < high) {                                          

109.         pivot =  partition(L,  low,  high);       

110.         quickSort(L,  low,  pivot -1);          //低端子表排序  

111.         quickSort(L,  pivot +1, high);          //高端子表排序  

112.     }  

113.       

114. }  

115.   

116.   

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

118. /*  

119. 合并两个线性表 

120. */  

121. /************************************************************************/  

122.   

123. void mergeList(SqList La, SqList Lb,  SqList &Lc){  

124.     ElemType *pa, *pb, *pc;  

125.     Lc.listsize =  La.lenght + Lb.lenght;  

126.     initList(Lc, Lc.listsize);          //初始化LC\pc = Lc.elem;  

127.     Lc.lenght = Lc.listsize;  

128.     pc = Lc.elem;  

129.     pa = La.elem;  

130.     pb = Lb.elem;  

131.     while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){  

132.         if (*pa <= *pb) *pc++ = *pa++;  

133.         else *pc++ = *pb++;  

134.     }  

135.     while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素  

136.     while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素  

137.   

138. }  

139.   

140. /************************************************************************/  

141. /* 打印list 

142. */  

143. /************************************************************************/  

144. void printList(SqList L){  

145.     printf("当前值:");   

146.     for (int i =0; i<L.lenght;i++) {  

148.     }   

149.     printf("\r\n");   

150. }  

151.   

152. void main()  

153. {  

154.     SqList La,Lb,Lc;  

155.     ElemType e;  

156.     int init,i;  

157.     init = initList(La, LIST_INIT_SIZE);  

158.     int data[6] = {5,3,6,2,7,4};  

159.     for (i=0; i<6;i++) {  

160.         insertList(La,  data[i],  i);  

161.     }  

162.     printf("LA:\r\n");   

163.     printList(La);  

164.     deleteListElem(La, 3, e );  

165.     printList(La);  

166.     insertList(La,  e,  3);  

167.     printList(La);  

168.   

169.     //排序  

170.     quickSort(La,0, La.lenght-1);  

171.     printList(La);  

172.   

173.     printf("LB:\r\n");   

174.     initList(Lb, LIST_INIT_SIZE);  

175.     int Bdata[5] = {1,3,2,4,6};  

176.     for (i=0; i<5;i++) {  

177.         insertList(Lb,  Bdata[i],  i);  

178.     }  

179.     //排序  

180.     quickSort(Lb,0, Lb.lenght-1);  

181.     printList(Lb);  

182.   

183.     mergeList(La, Lb,  Lc);  

184.     printList(Lc);  

185.   

186. }  


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


2
线性表的链表表示

一般使用链表来描述。

优点:对于新增和删除操作add和remove和方便。不需要移动元素。

缺点:不方便随机访问元素,LinkedList要移动指针

代码实现:

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. //宏定义  

7. #define TRUE   1  

8. #define FALSE   0  

9. #define OK    1  

10. #define ERROR   0  

11. #define INFEASIBLE -1  

12. #define OVERFLOW -2  

13.   

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

15. #define N = 100         

16.   

17. typedef int Status;  

18. typedef int ElemType;  

19.   

20. typedef struct LNode{  

21.     ElemType  data;               

22.     struct LNode   *next;     

23. }LNode, *LinkList;  

24.   

25. /************************************************************************/  

26. /* 

27. 初始化链表 

28. */  

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

30. Status initList(LinkList &L){  

31.     /*单链表的初始化*/  

32.     L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点  

33.     if(!L) exit(OVERFLOW);          //申请空间失败    

34.     L->next=NULL;                //建立一个带都节点的空链表  

35.     return OK;  

36.   

37.     /*  

38.     需要改变指针的指针,所以参数必须是引用或者是 *L: 

39.     (*L) = (Lnode *)malloc(sizeof(Lnode)); 

40.     (*L)->next=NULL; 

41.     return 1;                                                                      

42.     */  

43.   

44. }  

45.   

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

47. /*      

48. 创建链表 

49. */  

50. /************************************************************************/  

51. void createList(LinkList L, int n){  

52.     /*单链表的初始化*/  

53.     if (!L) {  

54.         initList(L);  

55.     }  

56.     ElemType data;  

57.     LinkList p,q = L;  

58.     printf("输入节点数据的个数%d:\r\n", n);  

59.     for(int i = 0; i<n; i++) {  

60.         p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点  

61.         scanf("%d",&data);  

62.         p->data = data;  

63.         p->next = q->next;  

64.         q->next = p;  

65.         q = p;  

66.     }  

67. }  

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

69. /* 在第i位置插入e 

70. */  

71. /************************************************************************/  

72. Status insertList(LinkList L, ElemType e, int i){  

73.     LinkList s, p = L;  

74.     int j = 0;  

75.     while (p && j<i){                //寻找i节点  

76.         p = p->next;  

77.         j++;  

78.     }  

79.     if (!p ||j >i) return ERROR;  

80.     s = (LinkList) malloc(sizeof(LNode));       //生成新节点  

81.     s->data = e; s->next = p->next;            //插入L中  

82.     p->next = s;  

83.     return OK;  

84.   

85. }  

86.   

87. /************************************************************************/  

88. /* 删除第i位置元素,并用e返回其值                                                                     */  

89. /************************************************************************/  

90. Status deleteListElem(LinkList L, int i, ElemType &e){  

91.     LinkList p, q;  

92.     int j = 0;  

93.     p = L;  

94.     while (p && j<i){  

95.         p = p->next;  

96.         ++j;  

97.     }  

98.     if (!p->next || j>i)  return ERROR;   //删除的位置不对  

99.     q  = p->next; p->next = q->next;  

100.     e = q->data; free(q);            //释放节点  

101.     return OK;  

102. }  

103.   

104.   

105. /************************************************************************/    

106. /*  插入排序  

107. */    

108. /************************************************************************/    

109.   

110. void  InsertSort(LinkList L)  

111. {  

112.     LinkList  list;             /*为原链表剩下用于直接插入排序的节点头指针*/  

113.     LinkList  node;             /*插入节点*/  

114.     LinkList  p;          

115.     LinkList  q;          

116.   

117.     list = L->next;              /*原链表剩下用于直接插入排序的节点链表*/  

118.     L->next = NULL;              /*只含有一个节点的链表的有序链表。*/  

119.     while (list != NULL)   {    /*遍历剩下无序的链表*/  

120.         node = list, q = L;     

121.         while (q && node->data > q->data  ) {  

122.             p = q;  

123.             q = q->next;  

124.         }  

125.           

126.         if (q == L) {  /*插在第一个节点之前*/  

127.             L = node;  

128.         }  else {     /*p是q的前驱*/  

129.             p->next = node;     

130.         }  

131.         list = list->next;  

132.         node->next = q; /*完成插入动作*/  

133.   

134.     }  

135. }  

136.   

137.   

138.   

139. /************************************************************************/  

140. /*  

141. 合并两个线性表 

142. */  

143. /************************************************************************/  

144.   

145. void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){  

146.     LinkList pa, pb, pc;  

147.     pa  = La->next;  

148.     pb  = Lb->next;  

149.     Lc =  pc = La;  

150.     while (pa && pa) {  

151.         if (pa->data > pb->data) {  

152.             pc->next = pb;  

153.             pc = pb;  

154.             pb =pb->next;  

155.         }else{  

156.             pc->next = pa;  

157.             pc = pa;   

158.             pa =pa->next;  

159.         }  

160.     }  

161.     pc->next = pa? pa :pb;  

162.     free(Lb);  

163. }  

164.   

165. /************************************************************************/  

166. /* 打印list 

167. */  

168. /************************************************************************/  

169. void printList(LinkList  L){  

170.     printf("当前值:");  

171.     LinkList p;  

172.     p = L->next;  

173.     while(p){  

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

175.         p = p->next;  

176.     }  

177.     printf("\r\n");   

178. }  

179.   

180. void main()  

181. {  

182.     LinkList  La,Lb,Lc;  

183.     ElemType e;  

184.     int init,i;  

185.     printf("LA:\r\n");    

186.     initList(La);  

187.     createList(La, 5);  

188.     insertList(La, 7,  3);    

189.     printList(La);  

190.     deleteListElem(La, 3,  e);    

191.     printList(La);  

192.     InsertSort(La);  

193.     printList(La);  

194.   

195.     printf("Lb:\r\n");    

196.     initList(Lb);  

197.     createList(Lb, 4);  

198.     InsertSort(Lb);  

199.     printList(Lb);  

200.   

201.     printf("Lc:\r\n");   

202.     initList(Lc);  

203.     mergeList(La,   Lb,   Lc);  

204.     printList(Lc);  

205.   

206. }  



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


数据结构-栈和队列


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


1

1.1 栈的定义

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:

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


结论:后进先出(Last In First Out),简称为LIFO线性表。

栈的基本运算有六种:

构造空栈:InitStack(S)、

判栈空: StackEmpty(S)、

判栈满: StackFull(S)、

进栈: Push(S,x)、可形象地理解为压入,这时栈中会多一个元素

退栈: Pop(S) 、 可形象地理解为弹出,弹出后栈中就无此元素了。

取栈顶元素:StackTop(S),不同与弹出,只是使用栈顶元素的值,该元素仍在栈顶不会改变。


 由于栈也是线性表,因此线性表的存储结构对栈也适用,通常栈有顺序栈链栈两种存储结构,这两种存储结构的不同,则使得实现栈的基本运算的算法也有所不同。

我们要了解的是,在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个盒子,我们在里头放了一叠书,当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^),那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算,哼哼),这时就是"上溢","上溢"也就是栈顶指针指出栈的外面,显然是出错了。反之,当栈中已没有书时,我们再去拿,看看没书,把盒子拎起来看看盒底,还是没有,这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。

链栈则没有上溢的限制,它就象是一条一头固定的链子,可以在活动的一头自由地增加链环(结点)而不会溢出,链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要在头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。



VIP课程预告1-数据结构与算法
1.2
栈的顺序储存

使用c++的面向对象封装:

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

2. //  

3. #include "stdafx.h"    

4. #include <iostream>  

5. using namespace std;  

6. #define MAX 10 // MAXIMUM STACK CONTENT  

7. class stack     

8. {     

9. private:     

10.     int arr[MAX];   

11.     int top;   

12. public:     

13.     stack()   

14.     {     

15.         inItStack();   

16.     }  

17.     /************************************************************************/  

18.     /* 初始化栈                                                                     */  

19.     /************************************************************************/  

20.     void inItStack()   

21.     {   

22.         top=-1;   

23.     }   

24.     /************************************************************************/  

25.     /* 入栈                                                                     */  

26.     /************************************************************************/  

27.     void push(int a)   

28.     {     

29.         top++;  

30.         if(top < MAX)  {     

31.             arr[top]=a;   

32.         }   else   {     

33.             cout<<"STACK FULL!!"<<top;     

34.         }     

35.     }     

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

37.     /* 出栈                                                                     */  

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

39.     int pop()  

40.     {      

41.         if(isEmpty())   {     

42.             cout<<"STACK IS EMPTY ";  

43.             return NULL;     

44.         } else {     

45.             int data=arr[top];   

46.             arr[top]=NULL;   

47.             top--;  

48.             return data;   

49.         }     

50.     }     

51.   

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

53.     /* 是否为空                                                                     */  

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

55.     bool isEmpty()  

56.     {  

57.         if(top == -1) return true;  

58.         else return false;  

59.     }  

60. };     

61. int main()     

62. {     

63.     stack a;     

64.     a.push(3);     

65.     a.push(10);     

66.     a.push(1);     

67.     cout<<"Pop:"<<a.pop();        

68.     return 0;     

69. }  

结论:由于栈的插入和删除操作具有它的特殊性,所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量难以扩充的弱点仍就没有摆脱。


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


1.3
栈的链式储存


若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作"链栈"。链栈通常用一个无头结点的单链表表示。如图所示:

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

栈的操作是线性表操作的特例。


简单用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 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. ElemType GetTop(STACK S, ElemType *e)  

83. {  

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

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

86. }  

87.   

88. /************************************************************************/  

89. /* 判断栈S是否空  

90. */  

91. /************************************************************************/  

92. int StackEmpty(STACK S)   

93. {  

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

95.     return   FALSE;  

96. }  

97.   

98. void main()    

99. {    

100.   

101.     STACK S;  

102.     InitStack( S);  

103.     Push(S, 3);  

104.     Push(S, 4);  

105.     ElemType e;  

106.     Pop(S,&e);  

107.     cout<<"Pop elem:"<<e;  

}   


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


1.4
栈的应用

1)  数制转换

2)语法词法分析

3)表达式求值等





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

文章来源: 阅读原文

相关阅读

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

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

安卓情报局

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

安卓情报局最新文章

精品公众号随机推荐