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

2016-08-07 23:07:00

一、喜欢单挑线性表

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≥ｎ，则给出溢出信息，作出错处理。在进栈前首先检查栈是否已满，如果满则溢出；不满则进入下一步骤②；
②设置TOP=TOP+1，使栈指针加１，指向进栈地址；
③S(TOP)=X，结束操作，X为新进栈的元素。
（2）出栈（Pop）
将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。出栈（Pop）操作的算法如下：
①如果TOP≤0，则输出下溢信息，并实现出错处理。在退栈之前先检查是否已为空栈，如果是空则下溢信息，如果不空则进入下一步骤②；
②X=S(TOP)，退栈后的元素赋给X；
③TOP=TOP-1，结束操作，栈指针减１，指向栈顶。