1700415299
1700415300
在牧场中,把干草堆积在地上就会形成一座小山。为了把干草堆成山就要从下往上不断地堆积。在程序中干草就相当于数据。而在给家畜喂食的时候,要从上往下把堆积的干草(数据)取下来,也就是说,数据的使用顺序与堆积顺序是相反的,通常把这种存取方式称为LIFO(Last In First Out,后进先出),即最后被存入 的数据最先被处理的。在那些作为程序处理对象的实际业务中,可以用栈来模拟诸如堆积在桌子上的文件等场景,既然无法马上处理,就暂且先都堆放在栈里吧
1700415301
1700415302
队列(Queue)就是等待做某事而排成的队(如图6.5所示)
1700415303
1700415304
图6.5 队列示意图
1700415305
1700415306
1700415307
1700415308
1700415309
队列与栈正相反,排在队首的乘客最先接受服务,通常把这种形式称为FIFI(First In First Out,先进先出),即最先被存入的数据最先被处理。当无法一下处理完数据的时候,就可以暂且先把这些数据排队。之后会介绍队列的数据结构,其实现方式一般是把数组的首尾相连,形成一个圆环
1700415310
1700415311
“链表”的概念相当于几个人手拉手排成一排(如图6.6所示)
1700415312
1700415313
图6.6 链表示意图
1700415314
1700415315
1700415316
1700415317
1700415318
某个人只要松开拉住的那只手,再去拉住另一只手,这一排人(相当于数据)的排列顺序就改变了。而只要松开拉住的手,再让一个新人加入进来并拉住他的手,就相当于完成了数据的插入操作
1700415319
1700415320
二叉树的概念正如其名,相当于一棵树,不过这棵树与自然界中的树稍有不同,二叉树从树干开始分杈,树枝上又有分杈,但每次都只会分成两杈,在每个分杈点上有一片叶子(相当于数据)(如图6.7所示)。稍后就会了解到二叉树其实是链表的特殊形态
1700415321
1700415322
图6.7 二叉树示意图
1700415323
1700415324
1700415325
1700415326
1700415327
1700415328
1700415329
1700415331
计算机是怎样跑起来的 6.5 要点5:了解栈和队列的实现方法
1700415332
1700415333
栈和队列的相似点在于,它们都可以把不能立即处理的数据暂时存储起来;不同点在于栈对所存储数据的存取方式是LIFO,而队列对所存储数据的存取方式是FIFI。既然已经了解了栈和队列的概念,接下来开始讲解如何用程序表示这两种数据结构。同样是数组,处理手段不同,得到的数据结构也会不同,数组有时可以转化为栈,有时可以转化为队列。
1700415334
1700415335
在实现栈这种数据结构时,首先要定义一个数组和一个变量,数组中所包含的元素个数就是栈的大小(栈中最多能存放多少个数据)。变量中则存储着一个索引,指向存储在栈中最顶端的数据,该变量被称为”栈顶指针“。栈的大小可以根据程序的需求任意指定。假设最多有100个数据,那么定义一个能把它们都存储下来的栈就可以了,这样的话就可以定义一个元素数为100的数组,这个数组就是栈的基础。接下来编写两个函数,一个函数用于把数据存入栈(压入栈中);另一个函数用于从栈中把数据取出来(从栈中弹出)。在这两个函数中,都需要更新栈中所存储的数据的总数以及更新栈顶指针的位置。也就是说通过使用由数组、栈顶指针以及入栈函数和出栈函数所构成的集合,就能实现栈这种数据结构了(如代码清单6.6和图6.8所示)
1700415336
1700415337
代码清单6.6 使用数组、栈顶指针、入栈函数和出栈函数实现栈
1700415338
1700415339
char Stack[100]; /*作为栈本质的数组*/
1700415340
1700415341
char StackPointer=0; /*栈顶指针*/
1700415342
1700415343
/*入栈函数*/
1700415344
1700415345
void Push(char Data){
1700415346
1700415347
/*把数据存储到栈顶指针所指的位置上*/
1700415348
[
上一页 ]
[ :1.700415299e+09 ]
[
下一页 ]