数据结构：顺序表、单链表、栈和队列的简单总结

时间：2022-06-17 10:26:20

首先，顺序表、链表、栈和队列都属于线性表，都可以采用两种基本的存储结构：顺序存储结构和链式存储结构来存储。结构中的元素之间存在一对一的线性关系。既然，顺序表、链表、栈和队列都属于线性表，那么有必要简单的谈一谈线性表。

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

  • ① 存在一个唯一的被称为“第一个”的数据元素；
  • ② 存在一个唯一的被称为“最后一个”的数据元素；
  • ③ 除第一个元素外，每个元素均有唯一一个直接前驱；
  • ④ 除最后一个元素外，每个元素均有唯一一个直接后继。

线性表的存储结构

线性表的存储结构可分为顺序存储结构和链式存储结构，顺序栈，顺序队列使用顺序存储结构来实现其存储，而链栈和链式队列使用链式存储结构存储。

顺序存储结构

用一组连续的存储单元依次存储线性表中的各个数据元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中。可以简单的理解为顺序存储结构使用一维数组存储线性表中的元素。

顺序存储的线性表的特点：

◆ 线性表的逻辑顺序与物理顺序一致;

◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

链式存储结构

链式存储结构是一种动态存储方式。采用一组任意的存放单元来存放线性表的元素。这组存储单元可以是连续的也可以是不连续的。采用链式存储线性表可以克服线性表：（1）插入和删除操作需要移动大量元素（2）采用顺序存储事先必须分配还内存单元，即定义线性表的长度，而事先分配好的大小不一定可以刚好满足需求（当然这一缺点可以通过扩容来克服，但相对比较麻烦）的缺点。可以采用链式存储线性表。采用链式存储的线性表称为线性了链表。下面详细总结顺序表、单链表、栈和队列。

Ⅰ ）顺序表

        顺序表是采用顺序存储结构的线性表，顺序表可理解为采用一维数组存储的线性结构（数组也是一种数据结构）顺序表的存储结果如下图所示：

数据结构：顺序表、单链表、栈和队列的简单总结

       假设线性表中有n个元素，每个元素占k个存储单元，第一个元素的地址为Loc(a1),则第i个元素的地址Loc(ai):

       Loc(ai) = Loc(a1) + (i-1) * k; 
其中Loc(a1)称为基地址。

        用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，利用C语言的结构类型来定义顺序表类型。

#define ListSize 100            //线性表的最大长度
typedef int DataType;

typedef struct
{
    DataType data[ListSize];   //用数组存储线性表中的元素
    DataType length;           //顺序表中元素的个数
}SeqList, *PSeqList;

          DataType是数据元素类型，可以根据需要定义，可以使用SeqList定义数据表类型变量，使用*PSeqList定义数据表指针变量;

          顺序表、单链表、栈和队列的基本操作前边的文章中已经讲过，这里就不赘述了，在后面的文章中给出了相关连接，可供参考：

顺序表的基本操作，点击打开链接


Ⅱ）单链表

单链表是采用链式存储结构的线性表。数据元素存储在非连续的内存单元中，通过指针将各个内存单元链接在一起，最有一个节点的指针指向 NULL 。单链表不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中。

单链表是由一系列结点组成的，通过指针域把结点按照线性表中的逻辑元素连接在一起。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构，单链表的结点结结构如下图：

数据结构：顺序表、单链表、栈和队列的简单总结

        使用箭头表示链表中的指针，单链表的可以表示成用箭头连接起来的结点序列，如下图所示：

数据结构：顺序表、单链表、栈和队列的简单总结

       图示为带头结点的单链表，实际上单链表是没有头结点的，头结点只是为了操作方便，在单链表的第一个结点前附设的一个结点使用头指针指向头结点。不带头结点的单链表，头指针指向第一个结点，判空条件为pHead == NULL；

//使用C语言的结构类型来定义单链表表类型。
typedef int DataType;          //数据类型

typedef struct Node
{
    DataType Data;            //数据元素
    struct Node* Next;        //指向结点直接后继的指针
}Node, *LinkList;

带头结点的单链表的基本操作，点击打开链接

不带头结点的单链表的基本操作，点击打开链接

Ⅲ）栈

      栈是一种先进后出的线性结构。只允许在栈的一端进行插入和删除操作，称为栈顶，栈的另一端称为栈底。栈顶的当前位置是动态变化的，由栈顶指针的位置指示，栈底指向栈的末尾。顺序栈使用顺序表实现，亦或者说是采用数组实现。顺序栈的示意图如下：

数据结构：顺序表、单链表、栈和队列的简单总结

       图示top==0 表示栈空的顺序栈，每次，入栈时先使元素入栈，然后栈顶指针+1，出栈时，先将栈顶指针top--,然后元素出栈。还可以用top==-1表示栈空，入栈时先使栈顶指针top++，然后元素入栈；出栈时先将栈顶指针top--，然后元素出栈。顺序栈的基本操作，点击打开链接

//使用C语言的结构类型来定义顺序栈类型。
#define MAXSIZE 100                 //栈的最大元素个数
typedef int DataType;

typedef struct
{
    DataType stack[MAXSIZE];
    int top;                       //栈顶指针
}SeqStack;


       栈还可以采用链式存储结构来存储，称为链式栈。链式栈使用单链表来实现，与顺序栈相比，链栈的结点空间是动态申请的因此一般不存在栈满上溢现象。链式栈的基本操作，点击打开链接

Ⅳ）队列         

       队列是一种先进先出的线性结构，只允许在表的一端进行插入和删除操作，当然：双端队列除外，允许插入的一端称为队尾，允许删除的一端称为队头。

数据结构：顺序表、单链表、栈和队列的简单总结

//使用C语言的结构类型来定义顺序队列类型。

#define MaxSize 100  //队列的最大容量

typedef int DataType;  //队列中元素类型
typedef struct Queue
{
    DataType Queue[MaxSize];
    int fornt;   //队头指针
    int rear;    //队尾指针
}SeqQueue;

      由于在入队和出队的过程中队头指针和队尾指针只增加不减小，致使被删除元素的空间无法被重新利用，因此，可能会存在这样一种情况：尽管，队列中实际元素个数远远小于数组大小（队列长度）但可能尾指针已超出数组空间的上界，而不能进行入队操作，这种现象，称之为“假溢出”。

        为了充分利用存储空间，消除这种”假溢出”,可以采用的方法是：将为队列分配的空间看成为一个首尾相接的圆环，并称这种队列为循环队列。 在循环队列中当队尾指针rear 达到最大值Maxsize - 1 时，其队尾指针加1操作，使其指向队头指针，这一过程可以使用数学中的取余运算来实现。

//使用C语言的结构类型来定义顺序循环队列类型。
#define MaxSize 100                          //队列的最大容量
typedef int DataType;
typedef struct SeqQueue
{
    DataType Queue[MaxSize];                 //使用数组来存储队列中的元素
    int fornt;
    int rear;
}SeqCirQueue;

        循环队列在队空和队满时，都是队头指针和队尾指针指向同一个位置，即：front==rear 为了区分这两种情况，可以少用一个存储空间，队空的判断条件不变，以队尾指针rear加1等于队头指针为队列的判满条件。即：

  1.     ◆ rear所指的单元始终为空。
  2.     ◆ 循环队列为空：front=rear 。  
  3.     ◆ 循环队列满：(rear+1)%maxsize =front。

       还可以使用标志量的方法来克服队列的“假溢出”现象。即：增加一个标志位设标志位tag，初始化时将tag置为0，当入队成功时tag = 1；出队成功时tag = 0；队列为空的判断条件为：(SCQ->front == SCQ->rear) && (SCQ->tag == 0) 队列为满的判断条件为：(SCQ->front == SCQ->rear) && (SCQ->tag == 1)。使用标志量的方法可以将队列中的所有空间都用于存放队列中的元素，使用标志量克服顺序队列的假溢出现象。

       同栈一样，队列也可以采用链式存储结构来存储。采用链式存储结构存储的队列称为链式队列，使用单链表来实现。

 

//使用C语言的结构类型来定义链式队列类型。
 

typedef int DataType;                //数据类型
typedef struct Node                  //链表的结点结构
{
    DataType _data;                  
    struct Node* _next;             
}LinkQueueNode;

typedef struct
{
    LinkQueueNode* front;          //队头指针
    LinkQueueNode* rear;           //队尾指针
}LinkQueue;

         
队列的实现：顺序队列、循环队列、链式队列


        上边的参考代码中，链式队列使用带头结点的单链表实现，不带头结点的链式队列参考：点击打开链接
 

 
 
 

标签：
相关文章