4线性表-顺序存储结构

线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。

2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。

3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。

4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。

线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。

2. 插入操作：将一个新元素插入到线性表中的指定位置。

3. 删除操作：将线性表中的某个元素删除。

4. 更新操作：将线性表中的某个元素更新为新的值。

线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。

线性表的顺序存储结构通常采用数组来实现。

数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。

但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。

线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。

每个元素包含数据和指向下一个元素的指针。

链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。

但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。

线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。

2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。

3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。

线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。

2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。

线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。

2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。

第一章测试1【单选题】(2分)图书馆的数目检索系统采用关系的数据结构。

A.树形B.图状C.集合D.线性2【单选题】(2分)是相互之间存在一种或多种特定关系的数据元素的集合。

A.数据项B.数据结构C.数据元素D.数据3【单选题】(2分)（）是一个值的集合和定义在这个值集上的一组操作的总称。

A.数据项B.数据类型C.数据元素D.数据结构4【单选题】(2分)算法的确定性是指（）A.算法中没有逻辑B.在任何情况下，算法不会出现死循环C.算法中的每一条指令必须有确切的含义D.当输入数据非法时，算法也能作出反应或进行处理第二章测试1【单选题】(2分)线性表中的数据元素有一个前驱多个后继。

A.错B.对2【单选题】(2分)用顺序结构存储，删除最后一个结点时，（）A.其它B.会移动其它结点位置C.可能会移动其它结点位置D.一定不会移动其它结点位置3【单选题】(2分)链表中逻辑上相邻的元素的物理地址__________相邻。

A.一定不B.必定C.其它D.不一定4【单选题】(2分)1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。

//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头A->next=qa;}else{qb=pb;pb=pb->next;()//将当前最小结点插入B表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}A.qa->next=A->nextB.qa->next=A;C.qb->next=A->nextD.qb->next=A;5【单选题】(2分)假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

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

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

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 }这⾥有⼀个疑问，因为前⾯我们提到了：在任意时刻，线性表的长度应该⼩于数组的长度。

数据结构实验报告课程名称数据结构学院信息工程专业班级信工二班学号姓名20 17 年 4月16日实验一：线性表的存储结构与顺序表的存储实现#include <stdio.h>#include <stdlib.h>#define OK 1#define LIST_INIT_SIZE 100#define OVERFLOW 0typedefintElemType;typedefint Status;typedefstruct{ElemType*elem;int length;intlistsize;}SqList;intInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}voidCreate_Sq(SqList&L){inti,n;printf("创建一个有序表:\n");printf("输入有序表中元素个数:");scanf("%d",&n);L.length=n;for(i=0;i<n;i++){printf("输入第%d个元素的值:",i+1);scanf("%d",&L.elem[i]);printf("\n");}}voidDisp_Sq(SqList L){inti,n;n=L.length;for(i=0;i<n;i++)printf("%5d",L.elem[i]);printf("\n");}void Combine(SqList&La,SqListLb) {inti,j,t;i=La.length;La.length=La.length+Lb.length;for(j=0;j<=Lb.length;i++,j++){La.elem[i]=Lb.elem[j];}for(i=0,j=0;i<La.length;i++){for(j=i+1;j<La.length;j++){if(La.elem[j]<La.elem[i]){t=La.elem[i];La.elem[i]=La.elem[j];La.elem[j]=t;}}}}void main(){SqListLa,Lb;InitList_Sq(La);InitList_Sq(Lb);Create_Sq(La);Disp_Sq(La);printf("\n");Create_Sq(Lb);Disp_Sq(Lb);printf("\n合并之后:");Combine(La,Lb); Disp_Sq(La);system("pause");}运行结果截图：。

线性表的顺序存储——顺序表之前我们讲了线性表, 本篇来阐述下线性表的顺序存储——顺序表定义线性表的顺序存储⼜称为顺序表, 它是⽤⼀组地址连续的存储单元依次存储线性表中的数据元素. 逻辑上相邻的两个数据元素在物理位置上同样相邻.规律顺序表中逻辑顺序与物理顺序相同L = ($a_{1}$, $a_{2}$, ..., $a_{i}$, $a_{i + 1}$, ..., $a_{n}$)其中在逻辑上相邻的两个数据元素，在顺序表中也存放在相同的存储单元当中，每⼀个⼩格⼦就代表⼀个存储单元。

注线性表中的元素的位序是从1开始, ⽽数组中元素下标是从0开始的若线性表存储的起始位置为Loc(A), sizeof(ElemType)为每个数据元素所占⽤的存储空间⼤⼩, 那么根据这⼀特点，我们可以计算出每⼀个数据元素存储的地址。

第⼀个元素的地址是 LOC(A)，计算第⼆个元素的地址就可以⽤第⼀个元素的地址加上第⼀个数据元素 $a_{1}$ 所消耗的存储空间，⽤ sizeof 可求得该数据元素所消耗的存储空间⼤⼩。

这⾥需要注意的⼀点是，n 与 MaxSize 是有含义上的不同的，其中 $a_{n}$ 代表的是顺序表中最后⼀个数据元素，⽽ MaxSize 代表的是数组的最后⼀个存储单元。

顺序表的两种实现⽅法顺序表可以⽤数组来实现。

根据数组的两种分配⽅式，也就有两种描述顺序表的⽅法。

分别是静态描述分配顺序表的⽅法和动态描述分配顺序表的⽅法。

⾸先来看数组静态分配时时如何描述⼀个顺序表的。

静态描述分配顺序表#define MaxSize 50typedef struct{ElemType data[MaxSize];int length;}SqList;这就是描述顺序表的语句。

第⼀句是定义了⼀个宏，也就是定义线性表的最⼤长度为 50，同时这也是数组的最⼤容量。

接着定义了⼀个结构体。

结构体就是把多个基本数据类型组合到⼀起构成⼀个新的数据类型。