1.1 数据结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了1.1 数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023/6/7

1.1数据结构

数据元素是数据的基本单位。一个数据元素由若干个数据项组成。数据项又分为简单数据项及符合数据项两种。简单数据项不能再分割，符合数据项由若干个数据项组成。

类型是一组值的集合。抽象数据类型（ADT）用一种类型和定义再该类型上的一组操作来定义。数据结构是抽象数据类型的实现，可以使用二次元组表示；数据结构=（D,R）

其中，D是数据对象，即数据元素的有限集；R是该数据对象中所有数据元素之间关系的有限集。

1.1线性表

线性表是最简单的一种线性结构，有很广泛的应用，同时也是其他非线性结构的基础。线性表种各元素的类型是一致的。

由任意元素组成的表称为广义表，广义表是对线性表的扩展，线性表是大纲中数据结构部分的重要内容，对广义表不做要求。

要深入理解线性表的概念，了解线性表基本操作中各参数的含义，正确给出操作的结果，能正确实现基于线性表应用的程序。

1.1.1 线性表的定义和基本操作

1.线性表的定义线性表是最常用且基本的一种数据结构，是由成为元素的数据项组成的一种有限且有序的序列。表中元素可以是任意类型。由n（n≥0）个元素组成的线性表记为（a0,a1,…,an-1）。

其中，a0称为表头，an-1称为表尾。元素的个数n称为表长。时称为空表，记为（）。

线性表各元素的位置关键是确定的。线性表中常使用整数表示各元素的位置，表头a0的位置为0，a1的位置为1，一般地，ai的位置称为i。

2.线性表的基本操作

线性表的基本操作包括：

（1）创建一个空表Create();返回一个空的线性表L。

（2）在表的指定位置插入一个元素Insert(L,i,e):在表L的位置I插入元素e。

（3）删除表中指定位置的元素Delete(L,i):删除表L中位置i的元素。

（4）访问表中指定位置元素GetElem(L,i):返回表L中位置i的元素。

除此之外，还有一下一些操作：

判定表空ISEmpth(L):如果表为空返回真，否则返回假。
判定表满IsFull(L):如果表已满返回真，否则返回假。
求表常length(L):返回表中元素的个数。
求表中指定元素的直接前驱Prev(L,e):返回表L中元素e的直接前驱。
求表中指定元素的直接后继Next(L,e):返回表L中元素e的直接后继。

1.1.2线性表的实现

线性表可以采用不同的储存结构保存，主要存储结构有两种：数组及链表。

采用数据保存的线性表称为顺序表，这种存储结构称为顺序存储结构或静态存储结构。

采用指针方式保存的线性表称为链表，相应的存储结构称为链式存储结构或动态存储结构。

结合两种存储结构的特点，将线性表以动态存储的策略保存在数组中，得到静态链表。
1. 顺序存储
  
  顺序存储方式下，线性表采用一维数组保存，采用数组保存的线性表称为顺序表。线性表中各元素一次保存在数组各存储单元中，表中逻辑上相邻的两个元素，其实际的存储位置也相邻。
  
  若线性表每个元素占用L个存储单元，线性表中元素ai的存储地址表示为LOC(ai),则有下列关系：
  
  Loc(ai)=Loc(a0) +i*l
  
  只要确定了顺序表存储的其实位置（数组首址），根据上式可以立即得到线性表中唯一元素的存储位置。由于数组能够按照下标直接访问元素，所以顺序表可实现随机存取。
  
  设顺序表元素类型表示为ElemType，使用C语言定义的顺序表如下：
  
  typedef struct{
  
  Elemtype * list Array；//指向Elemtype类型数组的指针
  
  }

typedef struct{
    Elemtype * list Array；//指向Elemtype类型数组的指针
    int length; //数组长度
    int listSize; //数组最大容量
    }SeqList;

数组一经分配，其大小不可改变，数组空间大小由listSize表示，顺序表中当前元素个数保存在length中。

实现顺序表插入Insert(L,i,e)的代码描述为：

Status Insert(Seqlist &L,int i , ElemType e)
{ int k =0;
  if(i<0||i>L.length) return ERROR;
  for(k=L.length;K>i;k--)
      L.listArray[K]=L.listARRAY[k-1];
 L.listArray[k] =e;
 L.length++;
    return OK;
}

实现顺序表删除Delete(L,i,e)的代码描述为

Status Delet(SeqList & L, int i, Elemtype *e)
{ int K= 0;
  if(i<0||i>=L.length)returnERROR;
   * e =L.listARRAY[i];
 for(k=i;k<l.length-1;k++)
     L.listArray[K]=L.listArray[K+1];
 L.length--;
 renturn OK;
    }

顺序表保存在数组中，数组的特点要求数据必须保存在一段连续的地址空间内。在顺序表中插入，删除元素时不可避免地要或多或少的元素移动。在顺序表中插入一个新元素，删除指定位置元素时，最优时间复杂度为O（1），最差时间复杂度和平均时间复杂度均为O(n)。所列的其他基本操作的时间复杂度均为O(1)。由此可见，插入，删除操作的开销较大。

2.链式存储

线性表中的各元素也可以不必保存在一段连续的地址空间中，而是放在任意的存储单元内。为了能方便地找到这些存储单元，采用指针结构将这些存储单元串在一起，形成链表。这种存储方式称为链式存储，采用链式存储结构的线性表称为链表。这样的表示法也称为动态表示法。

链表由一系列的结点构成，每个结点包括数据域和指针域，其中数据域中保存线性表的一个数据元素的信息，指针域中保存指向该数据元素后继结点的指针信息，表尾结点指针域中保存NuLL,表示表的结束。指针也称为链，链表的名称由此得来。

每个结点中除数据域外只包含一个指针域，这样的链表称为单链表。单链表中各元素位置仍然用整数表示，通常使用一个指针（称为表头指针）指向表头元素结点，使用另外一个指针（称为当前工作指针）来只是操作位置，如图1-1所示为一个单链表，指针head指向表头元素，指针P指向操作位置。表尾结点的指针域保存NULL，使用符号向下的括号表示。

为了操作上的方便，常常在单链表的表头添加一个空结点，称为表头结点，得到带表头的单链表,如图1-2所示。

3.线性表的应用

1）多项式操作多项式是数学经常用到的概念。设有n次一元多项式如下；

Pn(x) =P0 +P1X+P2x2 +…+pnxn

2）freelist(空闲块)管理

多项式中表结点的结构定义如下：

typedf struct Pnode{     //定义一个保存多项式的表的结点
    float coefficient;   //系数
    int exponent;        //指数
    PNode * next;        //下一结点的指针
}

当链表中频繁赠删结点时，很大程度上会影响到运行效率。一是申请，释放空间都会进行系统化调用，二是可能会产生大量的碎片，不方便以后的再分配。

可以在程序中额外建立一个freelist链表，与程序中正常的链表L类型一致。当L 中删除一个结点 Node时，将Node链到freelist 中；而当L 需要一个新结点时，若freelist不空，则将freelist中的结点转移到L 中，仅当freelist中已没有结点时，才真正向系统申请一个新空间。 freelist 的插入与删除都在表头进行，时间复杂度都是O（1）的。freelist只是临时管理程序中用到的空间，空间中的数据没有意义，各块的次序不重要，所以这个表不需要表头结点。它实现的方式与链栈是类似的。

3）静态链表

可以在数组中保存一个链表，这样的链表称为静态链表，如表1-1所示。

data	link
618	4
205	0
103	3
501	1
781	5
910	2

4.线性表两种实现方式的比较。

线性表的两种实现各有特色。

顺序表的缺点是大小不能改变。如果不能预知表中元素最多个数，则分配数组空间就很盲目。数组空间已经分配不论表中元素实际个数有多少，空间全部占用。另外，当有元素的插入及删除时，除在顺序表尾进行操作以外，其他位置的操作都会带来元素的移动，系统开销较大。但它的优点是能够实现随机访问，数组空间全部用来存放数据，没有指针开销。

链表的特点与顺序表不同。它的空间可以随时按需申请，空间大小随元素个数的多少而改变，元素多则占空间打，元素少则占空间少。但每个元素都配有指针开销，所以并不是申请的全部空间均用于保存数据。若当前工作指针已指向操作位置时，元素插入及删除的时间复杂度均为O（1），且不需要数据元素的移动。有些应用中，移动数据元素的开销较大，俩表就是个很好的选择。但链表只能实现顺序访问，时间复杂度为O（n）。

表格1-2列出了在顺序表及单链表实现方式下，几张比较典型操作的对比。

操作、应用	单链表	顺序表	说明
在尾端添加或删除元素	O（n）	O(1)	对单链表，必须遍历整个表。对顺序表，只需赋值
在头部插入或删除元素	O(1)	O(n)	对顺序表，必须将每个元素向后移动一个位置，以将第一个位置腾空。单链表只需调整指针
对关键字进行线性查找	O(n)	O(n)	最坏情形下，必须朝朝整个单链表或顺序表
在有序表的当前位置的插入元素(a)找到插入位置（b）插入元素	O(n)O（1）	O(n)O(log2n)	在单链表中插入，只需要指针调整。对于顺序表，二分查找找到插入位置；然后可能会移动n个元素来腾空单元
从表中删除某个值的所有出现	O（n）	O（n）	对于单链表，重复进行：找到值并调整指针，一直到表尾。对于顺序表，若找到一次值就调整一次元素，则需要O（n2）;若找到值后，调整元素的同时也进行判断，则是O(n)的

1.2 栈，队列和数组

栈，队列都是线性表，并且是操作受阻的线性表。所谓操作受限，是指插入，删除操作的位置不再是线性表中任何合理的地方，而是只局限于线性表的两端。其中，栈只允许在表一端操作，表的另一端及中间位置是不可见的；队列允许在表的两端分别进行操作，中间位置也是不可见的。

数组即是一种数据类型，也是一种存储结构。数据本身也属于线性表的范畴。

1.2.1栈和队列的基本概念

1.栈的基本概念

栈是一种受限的线性表，只允许在线性表的一端进行插入和删除操作。进行操作的一端称为栈顶，另一端称为栈底。插入操作称为入栈（push）,删除操作称为出栈（pop）。入栈和出栈都是O（1）操作。栈的处理方式为后进先出（Last In,First Out,LIFO）。

栈中没有元素时，称为空栈。当栈不空时，允许出栈操作；出栈不满时，允许入栈操作。最后入栈的元素是栈定元素。其所处位置是栈顶，一般地，使用一个变量标记栈顶位置，通常记为top。

栈的特点是后进先出，也可以说是先进后出。不能简单地理解为先入栈的元素一定后出战，后入栈的元素一定先出栈。例如，给定入栈序列1，2，3，4，5，即可以得到5，4，3，2，1的出栈序列，也可以的得到1，2，3，4，5的出栈序列，甚至是3，2，1，4，5这样的出栈序列。元素1比元素5先入栈，1即可以先于5出栈也可以在5之后出栈。

那么如何正确理解后进先出特点呢？这是同时在栈中的元素之间具有的特性。对于栈中的两个元素ai于aj，如果ai先于aj入栈，则ai 一定先于ai出栈。因为入栈于出栈操作是随机的，只要栈不空即可出栈，站不满即可入栈。若元素ai刚入栈后就出栈，在ai之后入栈的元素aj都在ai出栈后出栈，ai与aj不同时在栈中，他们之间就不具备先进后出的特点了。

2.队列的基本概念

队列也是一种受限的线性表，它允许在线性表的一端进行插入，而在另一端进行删除。插入操作称为入队，允许入队的一端称为队尾。删除操作称为出队，允许出队的一端称为队头。

队列中没有元素时，称为空队列。当队列不空时，允许出队操作，正等待出队的元素是队头元素，使用front标记队头位置：当队列不满时，允许入队操作，刚入队的元素是队尾元素，使用rear标记队尾元素后的一个空位置。

队列中出队次序与如对次序永远保持一致，先入队的元素一定先出队。队列的处理方式是先进先出（First In, First Out, FIFO）.

3.双端队列

双端队列结合了栈与队列的特性，在线性表的两端均可以插入及删除。双端队列可以看成是对底线，即两个栈的栈底连在一起，两端分别是两个栈的栈顶，且两个栈底户通。双端队列中从一端入队的元素即允许在本端出队，也允许在另一端出队。

1.2.2 栈和队列的顺序存储结构

1.栈的顺序存储结构

使用数组保存的栈称为顺序栈。

在顺序栈中，入栈及出栈均不需要移动元素，操作的时间复杂度都是O（1）的。

2。队列的顺序存储结构

采用数组作为队列的存储结构时，为避免入队，出队时带来的元素移动，需要采用循环存储的方式。

1.2.3 栈和队列的链式存储结构

顺序表有两个不足之处：第一，元素插入和删除时，都可能导致数组中元素的移动。因为栈与队列只允许在线性表的端点处进行插入和删除，所以避免了数据的移动：第二，顺序表的大小受数组空间的限制。这个问题在顺序栈及循环队列中仍存在。一旦数组分配了空间，栈及队列的最大空间就确定下来。同时保存在栈及队列中的元素个数不能超出数组大小的限制。

当不能预知同时保存在栈活队列中的元素个数时，通常使用链式存储结构。

1.栈的链式存储结构

使用链式保存的栈称为链式栈。栈顶指针top也是表头指针，入栈和出栈均操作在表头位置，所以时间复杂度都是O（1）的。

链式栈实际上是俩表的一个简化版本。

2.队列的链式存储结构。

使用链表保存的队列称为链式队列。队列的操作位置在其两端，队头指针front指向队头元素，队尾指针rear指向队尾元素，入队和出队时，通过两个指针可快速找到操作位置，故入会操作和出队操作的时间复杂度也是O(1)的。

链式队列实际上是带头尾指针的链表的一个简化版本。

1.2.4栈和队列的应用。

栈的应用非常广泛，例如，使用键盘输入时调用回退键，在程序中调用跟其他方法，中缀表达式转变为后缀表达式，后缀表达式的计算，表达式中括号的匹配检查，迷宫程序的实现，树的遍历，图的深度优先搜索等。

1.表达式中括号的匹配检查

编译程序设计程序中表达式的结果时，要先检查表达式的正确性，其中的一项是检查括号匹配的正确性。一对括号的左半部分称为开活号，右半部分称为闭括号，若开括号与闭括号的个数相等且且套正确，表示括号匹配正确：否则匹配错误。检查过程中使用栈来保存开阔好，从左往右依次扫描表达式中的符号ch,并进行判断：