数据结构02

链式表:
元素的数据项:
数据域:可以是各种类型的若干个数据项
指针域:指向下一元素
由若干个元素通过指针域连接在一起形成链式表。

不带头节点:第一个元素的数据域存储的就是有效的数据。
插入删除时可以会修改头节点指针,参数需要使用二维指针。
同时需要获取到上一个节点的指针,而头节点没有上一个节点,因此需要额外处理。

带头节点:第一个元素不使用,仅仅是为了用它来指向下一元素。
进入插入、删除操作时会比不带头节点的链表方便。
注意:其它操作要从第二节点开始

功能爱限的表:对表结构的加以限制,形成特殊的表结构。
栈:只有一个进去出口的表结构,先进后出
顺序栈:
数据域:
存储元素的内存首地址
栈的容量
栈顶位置
运算:
创建、销毁、入栈、出栈、栈满、栈空、栈顶

链式栈:
数据域:
栈顶
节点数量
运算:
创建、销毁、入栈、出栈、栈空、栈顶
栈的应用:
1、函数的调用(栈内存)
2、生产者与消费者模型(栈作为仓库)
3、表达式解决(中缀表达式转后缀表达式)
常见的笔试面试题:
某序列为入栈顺序,某序列是否是出栈顺序(边入边出)。
1 2 3 4 5
3 1 2 4 5 NO
实现一个函数,判断序列b是否是序列a的出栈顺序。
bool is_popstack(int* a,int* b,size_t len)
{
// 创建一个栈
// 按a的顺序入栈
// 按b的顺序出栈
// 最后判断如果栈为空,则b是a的出栈顺序
}
队列:一个端口进,另一个端口出,先进先出
顺序队列:
由一维数组+队头位置front+队尾位置rear组成,入队时rear+1,出队时front+1,为了让队列能反复使用,我们要把一维数组相像成一个环,因此rear和front加1后要用队列的容量求余。
rear = rear+1 % cal
front = frone+1 % cal

如何判断队列为空:front == rear
如何判断队列为满:front == rear+1
代价就是空一个位置不能用,或者添加一个数据项标记队列为空或满。
如何计算元素的数量:
(read-front+cal)%cal

数据项:
存储元素的内存首地址
容量
队头
队尾 即将入队的位置

运算:创建、销毁、入栈、出栈、队空、队满、队头、队尾、元数数量


链式队列:
由若干个节点组成的队列。
数据项:
队头指针
队尾指针
节点数量
运算:创建、销毁、队空、入队、出队、队头、队尾、数量

队列应用:
1、消息排队
2、树的层序遍历
3、图的广度优先遍历
4、封装线程池、数据池

常见的笔试面试题:
使用两个栈来模拟一个队列的功能。
从栈1到栈2一个不留
栈2不空栈1不到栈2

数据结构02

原文地址:https://www.cnblogs.com/Nxet/p/13449648.html