算法学习之数据结构线性表、堆、栈

c/c++

浏览数:146

2019-3-30

AD:资源代下载服务

一、喜欢单挑线性表

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链栈

链栈是指栈的链式存储结构,是没有附加头节点的、运算受限的单链表,栈顶指针是链表的头指针。