一、喜欢单挑线性表
1.线性表的特性
线性表是一个线性结构,它是一个含有n≥0个节点的有限序列。在节点中,有且仅有一个开始节点没有前驱并有一个后继节点,有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且仅有一个前驱和一个后继节点。通常可以把一个线性表表示成一个线性序列:k1,k2,…,kn,其中k1是开始节点,kn是终端节点。
1.1 线性结构的特征
在编程领域中,线性结构具有如下两个基本特征。
(1)集合中必存在唯一的一个“第一元素”和唯一的一个“最后元素”;
(2)除最后一个元素之外,均有唯一的后继(后件)和唯一的前驱(前件);
由n(n≥0)个数据元素(节点)a1,a2,…,an组成的有限序列,数据元素的个数n定义为表的长度。当n=0时称为空表,我们通常将非空的线性表(n>0)记作:
(a1,a2,…an)
数据元素ai(1≦i≦n)没有特殊含义,大家不必去“剖根问底”的研究它,它只是一个抽象的符号,其具体含义在不同的情况下可以不同。
1.2 线性表的基本操作过程
线性表虽然只是一对一的单挑,但是其操作功能非常强大,具备了很多操作技能。
1.3 线性表的结构特点
均匀性:虽然不同数据表的数据元素是各种各样的,但同一线性表的各数据元素必须有相同的类型和长度;
有序性:各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的,即存在唯一的“第一个”和“最后一个”的数据元素,除了第一个和最后一个外,其他元素前面只有一个数据元素直接前趋,后面只有一个直接后继二、
2.顺序表操作
在现实应用中,有两种实现线性表数据元素存储功能的方法,分别是顺序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法,此方式的主要操作功能如下所示。
(1)计算顺序表的长度
(2)清空操作
(3)判断线性表是否为空
(4)判断顺序表是否为满
(5)附加操作
(6)插入操作
(7)删除操作
(8)获取表元
(9)按值进行查找
3.链表操作
链比顺序表要复杂一点,对于同一个数据,它可以和不相邻的数据发生关系。例如农民通常将收获的水果卖给商贩,商贩将收购的水果卖给加工厂。这是一条水果加工产业链,可以得出商贩是农民的财神、加工厂是商贩的财神这一论调。在那一年的某一天,老实的农民发现利润较低,于是拉着自己的水果不远万里的亲自卖给了加工厂。这样农民伯伯获得了更大的利润,而商贩也不能怎么着,这个产业链还得继续下去。
由此可见,链式存储结构不需要用地址连续的存储单元来实现,而是通过“链”建立起数据元素之间的次序关系。所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻,在插入和删除时无需移动元素就而提高了运行效率。链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。
二、守规矩的先进先出的队列
1.队列基础
队列和栈一样,只允许在断点处插入和删除元素,循环队的入队算法如下所示。
(1)tail=tail+1;
(2)如果tail=n+1,则tail=1;
(3)如果head=tai,即尾指针与头指针重合,则表示元素已装满队列,会施行上溢出错处理;否则Q(tail)=X,结束整个过程,其中X表示新入出元素。
2.链队列和循环队列
使用C语言定义链队列的格式如下所示。
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front; /* 队头指针,指向头元素 */
QueuePtr rear; /* 队尾指针,指向队尾元素 */
}LinkQueue;
3.队列的基本操作
(1)初始化队列Q的目的是创建一个队列
(2)入队的目的是将一个新元素添加到队尾,相当于到队列最后排队等候。
(3)出队的目的是取出队头的元素,并同时删除该元素,使后一个元素成为队头。
(4)获取队列第1个元素,即将队头的元素取出,不删除该元素,队头仍然是该元素。
(5)判断队列Q是否为空
4.队列的链式存储
当使用链式存储结构表示队列时,需要设置队头指针和队尾指针,这样做的好处是可以设置队头指的针和队尾的指针。在入队时需要执行如下三条语句。
s->next=NULL;
rear->next=s;
rear=s;
在C语言中,实现队列链式存储结构类型的代码如下所示。
type struct linklist { //链式队列的节点结构
Elemtype Entry; //队列的数据元素类型
struct linklist *next; //指向后继节点的指针
}LINKLIST;
typedef struct queue{ //链式队列
LINKLIST *front; //队头指针
LINKLIST *rear; //队尾指针
}QUEUE;
三、后进先出的栈
1.什么是栈
栈允许在同一端进行插入和删除操作,允许进行插入和删除操作的一端称为栈顶(top),另一端称为栈底(bottom)。栈底是固定的,而栈顶浮动的;如果栈中元素个数为零则被称为空栈。插入操作一般被称为进栈(PUSH),删除操作一般被称为退栈(POP)。
在栈中有两种基本操作,分别是入栈和出栈。
(1)入栈(Push)
将数据保存到栈顶。在进行入栈操作前,先修改栈顶指针,使其向上移一个元素位置,然后将数据保存到栈顶指针所指的位置。入栈(Push)操作的算法如下:
①如果TOP≥n,则给出溢出信息,作出错处理。在进栈前首先检查栈是否已满,如果满则溢出;不满则进入下一步骤②;
②设置TOP=TOP+1,使栈指针加1,指向进栈地址;
③S(TOP)=X,结束操作,X为新进栈的元素。
(2)出栈(Pop)
将栈顶的数据弹出,然后修改栈顶指针,使其指向栈中的下一个元素。出栈(Pop)操作的算法如下:
①如果TOP≤0,则输出下溢信息,并实现出错处理。在退栈之前先检查是否已为空栈,如果是空则下溢信息,如果不空则进入下一步骤②;
②X=S(TOP),退栈后的元素赋给X;
③TOP=TOP-1,结束操作,栈指针减1,指向栈顶。
2.栈的基本操作
2.1 顺序栈
顺序栈是栈的顺序存储结构的简称,它是一个运算受限的顺序表。假设S是SeqStack类型的指针变量,如果栈底位置在向量的低端,则S->data[0]是栈底元素。
2.2链栈
链栈是指栈的链式存储结构,是没有附加头节点的、运算受限的单链表,栈顶指针是链表的头指针。