链表,栈,队列、树四种结构的构建方式的简单理解

开个坑,有空填,方便自己考前速看一下


两种储存结构 链式和顺式

比较一下链表的链式储存结构、栈和队列的顺式储存结构(不代表他们只有链式/顺式,只是着重强调)

假设所有的储存数据都是int型

  • 顺序栈的结构构建

两个参数:初始容量、每次增加的容量

struct stack

{

int base,top;

int length;

};

base指向栈底,top指向栈顶

length表明现在栈的容量

初始化的时候,需要初始化一个初始容量大小的空间。base指向第一个位置,top指向顶位置

base和top是指针,代表指向的位置,要储存的数据储存在『top指针当时指向的那一个位置』

当到达栈顶,开辟新空间

  • 循环队列的结构构建

参数: 最大容量

struct queen

{

int *base;

int front,rear;

};

其实顺序结构实际上是个数组。数组和指针在用法上有非常多的相似,这里用指针的操作方式建立了一个数组,

base是指向数组头的指针;base手动开辟一段最大容量大小的空间

front和rear是数组的下标,front在第一位数,rear在最后一个存放数据的位置的后一位

要储存的内容即存放在该数组中

这里,可以使用数组操作了。 比如base[a]

front-base即为队列长度

但是对于普通的一长列,可以用后-前来算长度,但由于这是循环的队列,所以有一些数学上的东西要修正:

若为不循环的表,b在a后面,那么b-a即可

若为一个循环列表 a到b中间空了多少格?

1、假设b在a前面,那么这就尴尬了。b-a为负数,这时候求个补,即加一个总长,b-a+length,这时候假设2-4=-2 ,那么就变成了-2+6(总长)=4,这即为他们之间的距离(注意:距离是朝顺方向的距离)。但是如果b-a>0的话,这tm就又尴尬了,4-2+6=8了,再结合2、处理

2、若为一个循环链表,一个数到达顶端了要跳回第一个数怎么处理?

对它加一然后求余即可,故在循环链表中,表示一个数进一位用(a+1)%length表示。对于循环列表中的数,下标%length即为其该在的位置

  • 链表

struct linknode

{

int data;

int *next;

};

链表的内容储存在每一个节点中,每一个节点都是一个struct,而栈和队列都只有一个struct,即为栈、队列本身。

串珠子,很容易理解

{对所有数据结构}一个易错点,struct sim;在主函数创建一个 sim a 还是 sim* a 要注意,两者皆可以但用法不同

建议链式结构 sim*a 顺式结构 sim a

  • 二叉树

栈的递归运用之–二叉树

注意这里和链表的感觉很像,实则不然,创建方式和遍历方式是不同的,栈的创建需要至少两个指针p,q,像爬梯子一样创建。而二叉树的创建只需要一个根,然后递归创建

TBC

image

  • 本文作者: aisaka
  • 本文链接: 82.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!