顺序存储结构的表示

计算机二级公共基础部分：线性表及其顺序存储结构:1.3.1线性表的基本概念：线性表:由n(n≥20)个相同类型数据元素构成的有限序列n定义为线性表的表长;n=时的线性表被称为空表。

称i为在线性表中的位序。

例如:英文大写字母表(A,B,C,D,E,F,...X,Y,Z)同一花色的13张扑克牌。

(2,3,4,5,6,7,8,9,10,J,Q,K,A)线性表的结构特征:数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；对于一个非空线性表，有且只有一个根节点a1,它无前件，有且只有一个终端结点a n, 它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

线性表的存储结构：顺序存储链式存储两个基本特点:线性表中所有元素所占的存储空间是连续的。

线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

该内容考点：重点：插入，删除，查找，排序难点：1分多分解，合并n合1，copy,逆转顺序表的插入和删除分析插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动的元素个数为：E is=1n+1∑p i(n−i+1)=n2 n+1i=1删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：E dl=1n∑p i(n−i)=n+12 ni=1分析结论顺序存储结构表示的线性表，在做插入或删除时，平均需要移动大约一半的数据元素。

当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点值得考虑。

队列的顺序存储结构及其运算队列是一种常用的数据结构，它具有先进先出（FIFO）的特性。

在队列中，元素的插入和删除操作分别在两端进行。

队列可以用顺序存储结构和链式存储结构来实现。

一、顺序存储结构顺序存储结构是指将队列中的元素按照顺序存放在一块连续的存储空间中。

通常使用数组来实现顺序存储的队列。

在顺序存储结构中，队列的头部指针front指向队列的第一个元素，队列的尾部指针rear指向队列的最后一个元素。

队列的初始化操作是将front和rear都置为-1，表示队列为空。

当有元素入队时，首先将rear加1，然后将元素存放在rear所指向的位置上。

当有元素出队时，首先将front加1，然后返回front 所指向的元素。

顺序存储结构的队列运算包括初始化队列、判断队列是否为空、判断队列是否已满、元素入队、元素出队、获取队列长度等操作。

队列的初始化操作是将front和rear都置为-1，表示队列为空。

判断队列是否为空的操作是通过判断front和rear是否相等来实现的。

如果front等于rear，则表示队列为空。

判断队列是否已满的操作是通过判断rear是否等于队列的最大长度减1来实现的。

如果rear等于队列的最大长度减1，则表示队列已满。

元素入队的操作是将rear加1，然后将元素存放在rear所指向的位置上。

如果队列已满，则无法入队。

元素出队的操作是将front加1，然后返回front所指向的元素。

如果队列为空，则无法出队。

获取队列长度的操作是通过rear和front的差值加1来实现的。

二、顺序存储结构的优缺点顺序存储结构的优点是实现简单、操作高效。

由于元素在内存中是连续存放的，所以可以通过下标直接访问元素，插入和删除操作只需要移动指针，效率较高。

顺序存储结构的缺点是需要预先分配一定的存储空间，当队列的元素个数超过存储空间时，会导致队列溢出。

此外，由于插入和删除操作需要移动指针，当元素较多时，效率会逐渐降低。

三、队列的应用场景队列的先进先出特性使得它在很多实际应用中得到了广泛的应用。

顺序存储结构、链式存储结构、索引存储结构、散列存储结构介绍存储结构是指数据在计算机内存或磁盘等存储介质中的组织方式。

在数据结构中，常见的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

下面将分别对这四种存储结构进行详细介绍。

一、顺序存储结构（Sequential Storage Structure）：顺序存储结构是将数据元素按照其逻辑次序依次存储在一片连续的存储空间中，即在内存或磁盘上连续存放数据元素。

数据元素之间的逻辑关系通过其在存储空间中的物理位置来表示。

特点：顺序存储结构的存取速度较快，可以通过下标直接访问元素。

插入和删除操作需要移动大量元素，效率较低。

适用于元素数量固定、随机访问频繁的场景，如数组。

二、链式存储结构（Linked Storage Structure）：链式存储结构通过使用指针将数据元素存储在不连续的存储空间中，并通过指针将它们连接起来。

每个数据元素中都包含一个指向下一个元素的指针，从而构成了一个链表结构。

特点：链式存储结构的插入和删除操作效率较高，只需要修改指针的指向。

访问某个元素需要从头节点开始遍历，效率较低。

适用于元素数量不固定、插入和删除频繁的场景，如链表。

三、索引存储结构（Indexed Storage Structure）：索引存储结构是在顺序存储结构的基础上，为数据元素建立一个索引表，该索引表中的每个索引项包含了一个关键字和对应数据元素在存储空间中的地址。

特点：索引存储结构可以通过索引表快速定位数据元素，减少了遍历的时间。

插入和删除操作需要同时修改索引表和存储空间，效率相对较低。

适用于大型数据库等场景，可以提高查询效率。

四、散列存储结构（Hash Storage Structure）：散列存储结构是通过将数据元素的关键字映射到一个散列地址来进行存储和访问的。

具体的映射函数称为散列函数，它将关键字转换为一个固定长度的散列地址。

特点：散列存储结构可以快速定位数据元素，查找效率高。

线性表的顺序存储结构线性表的顺序存储结构相关概念举个栗⼦：⼤学的时候，宿舍有⼀个同学，帮⼤家去图书馆占座。

他每次去图书馆，挑⼀个好地⼉，把他书包⾥的书，⼀本⼀本按座位放好，若书不够，再把⽔杯，⽔笔都⽤上，长长⼀排，九个座硬是被他占了。

1. 顺序存储的定义线性表的顺序存储结构，指的是⽤⼀段地址连续的存储单元依次存储线性表的数据元素。

⽰意图：2. 顺序存储⽅式线性表的顺序存储结构，其实就和刚才图书馆占座的例⼦⼀样，就是在内存中找了块地⼉，通过占位的形式，把⼀定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。

既然线性表的每个数据元素的类型都相同，所以可以⽤⼀维数组来实现顺序存储结构，即把第⼀个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

这⾥有⼏个关键的地⽅：1）为了建⽴⼀个线性表，要在内存中找⼀块地，这块地的第⼀位置就⾮常关键，他是存储空间的起始位置2）数组的长度就是这个最⼤存储容量3）线性表的当前长度3. 数据长度与线性表长度区别1）数组的长度是存放线性表的存储空间的长度，存储分配后这个量⼀般是不变的。

当然，⼀般⾼级语⾔是可以通过编程⼿段实现动态分配数组，不过这会带来性能上的损耗。

2）线性表的长度是线性表中数据元素的个数，随着线性表插⼊和删除操作的进⾏，这个量是变化的。

在任意时刻，线性表的长度应该⼩于等于数组的长度。

4. 地址计算⽅法数组是从0开始第⼀个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系：存储器中的每个存储单元都有⾃⼰的编号，这个编号称为地址。

假设每个数据元素占⽤的都是c个存储单元，那么每个数据元素地址可通过公式计算得到: LOC(ai)=LOC(a1)+(i-1)*c它的存取时间性能为O(1)。

我们通常把具有这⼀特点的存储结构称为随机存取结构。

相关操作1. 获得元素操作（GetElem）获取元素的思路：1）考虑边界问题，顺序线性表L已存在（⾮空表），并且i必须在1<=i<=ListLength(L)范围内，否则抛出异常2）将数值下标为i-1的值返回即可C语⾔的实现如下：1// 获得元素操作2#define OK 13#define ERROR 04#define TRUE 15#define FALSE 06 typedef int Status;7/*Status是函数的类型,其值是函数结果状态代码，如OK等*/8/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/9/*操作结果：⽤e返回L中第i个数据元素的值*/1011 Status GetElem(SqList L, int i, ElemType *e)12 {13if (L.length == 0 || i < 1 || i > L.length)14return ERROR;15 *e = L.data[i-1];16return OK;17 }PHP的实现如下：1 <?php2class Seqlist{34private$seq_list; //顺序表5/**6 * 顺序表初始化7 *8 * @param mixed $seq_list9 * @return void10*/11public function __construct($seq_list=array()){12$this->seq_list = $seq_list;13 }1415/**16 * 返回顺序表元素个数17 *18 * @return int19*/20public function listLength(){21return count($this->seq_list);22 }2324/**25 * 返回顺序表中下标为i的元素值26 *27 * @param int i28 * @return mixed 如找到返回元素值，否则返回false29*/30public function getElem($i){31if ($this->seq_list && $i > 0 && $i <= $this->listLength()) {32return$this->seq_list[$i-1];33 }else{34return false;35 }36 }37 }2. 插⼊操作插⼊算法的思路：1）如果插⼊位置不合理（1<=i<=ListLength(L)+1），抛出异常说明：最好的情况就是，插⼊的位置为末尾：ListLength(L)+1（不是数组下标）,这个时候不⽤移动元素，时间复杂度是O(1) 2）如果线性表长度⼤于等于数组长度，则抛出异常或动态增加容量3）从最后⼀个元素开始向前遍历到第i个位置，分别将它们都向后移动⼀个位置4）将要插⼊元素填⼊位置 i 处5）表长加1C语⾔的实现如下：1// 插⼊操作2#define OK 13#define ERROR 04#define TRUE 15#define FALSE6 typedef int Status;7/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/8/*操作结果：在L中第i个位置之前插⼊新的数据元素e,L的长度加1*/910 Status ListInsert(SqList *L, int i, ElemType e)11 {12int k;13if (L->length == MAXSIZE) /*顺序线性表已经满*/14return ERROR;15if (i < 1 || i > L->length + 1) /*当i不在范围内时*/16return ERROR;1718if (i <= L->length) /*若插⼊数据位置不在表尾*/19 {20for (k = L->length - 1; k >= i - 1; k--) /*将要插⼊位置后数据元素向后移动⼀位*/21 {22 L->data[k + 1] = L->data[k];23 }24 }25 L->data[i - 1] = e; /*将新元素插⼊*/26 L->length++;27return OK;28 }PHP的实现如下：1 <?php2class Seqlist{34private$seq_list; //顺序表5/**6 * 顺序表初始化7 *8 * @param mixed $seq_list9 * @return void10*/11public function __construct($seq_list=array()){12$this->seq_list = $seq_list;13 }1415/**16 * 在指定位置 i 插⼊⼀个新元素 $value17 *18 * @param int $i19 * @param mixed $value20 * @return bool 插⼊成功返回 true, 否则返回 false21*/22public function listInsert($i, $value){23// 三种情况：插⼊位置不合理24if ($i > $this->listLength()+1 || $i < 1) {25return false;26 }elseif ($i == $this->listLength()+1) {27// 最好的情况：元素插⼊到最后⼀个位置，不需要移动元素，时间复杂度为O(1)28$this->seq_list[$i-1] = $value;29 }else{30// 从 $i-1 到最后的元素位置向后移动⼀位31for ($k = $this->listLength()-1; $k >= $i-1; $k--) {32$this->seq_list[$k+1] = $this->seq_list[$k];33 }34$this->seq_list[$i-1] = $value;35 }3637return true;38 }39 }这⾥有⼀个疑问，因为前⾯我们提到了：在任意时刻，线性表的长度应该⼩于数组的长度。

数据结构：队列的顺序存储结构（循环队列）队列的定义：队列是只允许在⼀端进⾏插⼊操作，⽽在另⼀端进⾏删除操作的线性表。

队列的抽象数据类型：ADT 队列(Queue)Data同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。

OperationInitQueue(*Q): 初始化操作，建⽴⼀个空队列。

DestroyQueue(*Q): 若队列Q存在，则销毁它。

ClearQueue(*Q): 将队列清空。

QueueEmpty(Q): 判断队列是否为空。

GetHead(Q,*e): 若队列存在且⾮空，⽤e返回Q的队头元素。

EnQueue(*Q,e): 若队列Q存在，插⼊新元素e到队列Q中并成为队尾元素。

DeQueue(*Q,*e): 删除队列中的队头元素，并⽤e返回。

QueueLength(Q): 返回队列Q的元素的个数。

endADT线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储⽅式，有顺序栈和链栈。

同样队列作为⼀种特殊的线性表，也存在这两种存储⽅式。

先来看队列的顺序存储结构。

队列的顺序存储结构同线性表的顺序存储结构存在着同样的问题，队头出队列要后⾯的元素依次向前移动，时间复杂度为O(n)。

因为队列的每次删除元素都是从队头，所以每次删除都有⼤量的元素要移动，这样算法的效率很不好。

于是改进⼀下，队头不⼀定要在数组的下标为0的位置。

也就是说删除⼀个元素，仅需要把队头指针向后移动⼀次。

同时让front指针指向队头元素，rear指针指向队尾元素的下⼀个位置。

这样当front等于rear时，队列就为空。

但是此时还有问题，会有假溢出的现象。

解决这种问题的办法就是循环队列。

让上⾯的队尾指针rear指向数组的下标0位置。

队列的这种头尾相接的顺序存储结构称为循环队列。

但是还存在⼀个问题：当队列空或者满的时候都是front==rear。

那么这个要怎么判断呢？（1）设置⼀个标志变量flag，当fron==rear且flag==0时，队列为空；当front==rear且flag==1时队列满。

线性表之顺序存储结构数据结构和算法是程序设计的灵魂。

坦诚的说，我在这方面是弱的可以。

虽然工作这么多年了，因为种种借口，这块知识一直是我的痛处。

曾经在面试时大言不惭的说，这些知识在工作中很少用到，所以当年学习的东西早就还给学校了。

其实不然，失去了灵魂的程序员如我，总是要逆袭的。

所以以后的学习中会有一些如孩童笔记般的文章出现在我的blog中，请大师们不要嘲笑，要提携。

定义线性表可以说是最简单的数据结构，它的描述为：n个数据元素的有限序列。

记为：L=(a1,a2,...,an)按照存储结构它又可以分为顺序存储结构和链式存储结构。

而其中线性表的顺序存储结构是最简单最常用的数据结构：用一段连续地址依次存储表中的数据元素。

看到这里，我们会自然的联想到C语言中的数组。

下面我要实现的是线性表中的元素为整型的顺序存储结构，及它的主要运算：增删查。

先来简单的定义一下这个线性表的顺序存储结构：#define MAXLENGTH 20struct sequencelist{int data[MAXLENGTH];int length;};其中data数组为这个线性表的主要部分，数据元素就存在于此数组中，而对这个线性表的操作都是基于这个数组。

length是这个线性表的一个属性，表示这个线性表包含元素的个数。

增：线性表的插入操作对线性表的插入就是对data数组的插入，然后将其length增加。

//insert oprationint insert(struct sequencelist *list,int index,int element){int length = list->length;if(length ==0 || index < 0 || index > length || length >= MAXLENGTH) return ERROR;list->data[index] = element;for(int i = length - 1;i>index;i--){list->data[i+1] = list->data[i];}list->length++;return OK;}删：线性表的删除操作类似增的相反操作。

栈和队列的顺序存储结构1. 栈的顺序存储结构栈是一种后进先出（Last In First Out，LIFO）的数据结构，它的顺序存储结构可以用数组实现。

我们可以将数组的最后一个位置作为栈顶，数组的第一个位置作为栈底。

当插入元素时，栈顶指针向上移动，指向新的元素；当删除元素时，栈顶指针向下移动，指向原来的栈顶元素。

2. 队列的顺序存储结构队列是一种先进先出（First In First Out，FIFO）的数据结构，它的顺序存储结构同样可以使用数组实现。

我们可以使用数组的第一个位置作为队头，数组的最后一个位置作为队尾。

当插入元素时，队尾指针向上移动，指向新的元素；当删除元素时，队头指针向下移动，指向原来的队头元素。

3. 栈和队列的应用场景栈和队列在计算机科学中有着广泛的应用。

栈常用于实现函数调用、递归算法、表达式求值等。

例如，在函数调用过程中，每次调用函数时，都会将函数的返回地址、局部变量等信息保存在栈中，当函数返回时，再从栈中弹出这些信息，恢复到调用函数之前的状态。

队列常用于实现任务调度、消息传递等。

例如，在操作系统中，可以使用队列来管理任务的执行顺序，保证任务按照先进先出的顺序得到执行。

4. 栈和队列的比较虽然栈和队列都是线性数据结构，但它们的特点和应用场景不同。

栈适用于后进先出的场景，例如需要倒序输出的情况；而队列适用于先进先出的场景，例如需要按照顺序处理的情况。

此外，栈和队列的操作复杂度也有所不同，栈的插入和删除操作都是O(1)的，而队列的插入和删除操作的复杂度均为O(1)。

总结：栈和队列是两种常见的数据结构，它们的顺序存储结构分别使用数组来实现。

栈适用于后进先出的场景，而队列适用于先进先出的场景。

栈和队列的应用场景广泛，可以用于函数调用、递归算法、任务调度等。

栈和队列的操作复杂度也有所不同，栈的插入和删除操作都是O(1)的，而队列的插入和删除操作的复杂度均为O(1)。

用C语言定义线性表的顺序存储结构线性表顺序存储的表示：线性表的顺序存储结构可以借助于高级程序设计语言中的一维数组来表示，一维数组的下标与元素在线性表中的序号相对应。

线性表的顺序存储结构可用C语言定义如下：#define MAXSIZE /*线性表可能达到的最大长度；*/ typedef struct{ElemType elem[MAXSIZE]；/* 线性表占用的数组空间。

*/ int last；/*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/} SeqList；说明：（1）结点类型定义中ElemType数据类型是为了描述的统一而自定的，在实际应用中，用户可以根据自己实际需要来具体定义顺序表中元素的数据类型，如int、char、float或是一种struct结构类型。

（2）从数组中起始下标为0处开始存放线性表中第一个元素。

因此需要注意区分元素的序号和该元素在数组中的下标之间的对应关系，即数据元素a1在线性表中的序号为1，其对应的elem数组的下标为0；ai在线性表中的序号为i，其对应的elem数组的下标为i-1。

利用定义的顺序表的数据类型SeqList就可以定义变量了。

变量L的定义与使用方法有两种：（1）通过变量定义语句：SeqList L将L定义为SeqList类型的变量，可通过L.elem[i-1]来访问顺序表中序号为i的元素a i；通过st 可得到顺序表中最后一个元素的下标，而st+1就是顺序表的长度。

（2）通过指针变量定义语句：SeqList *L将L定义为指向SeqList类型的指针变量，使用时，可通过L->elem[i-1]来访问顺序表中序号为i的元素a i，通过L->last+1可得到顺序表的长度。

typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。

这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）。