3线性表及其顺序存储结构

线性表的顺序存储结构是一种什么存储结构线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。

比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。

我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。

在数据结构逻辑层次上细分，线性表可以分成通常线性表和受到限制线性表。

通常线性表也就是我们通常所说的“线性表”，可以民主自由的删掉或嵌入结点。

受到限制线性表主要包含栈和队列，受到限制则表示对结点的操作方式受限制。

线性表的逻辑结构简单，便于实现和操作。

因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

线性表就是一种常用的数据结构，以下了解线性表及其顺序存储，并对栈和队列及它们的顺序同时实现得出了详尽的设计叙述。

在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。

由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。

线性表就是一个线性结构，它就是一个所含n≥0个结点的非常有限序列，对于其中的结点，存有且仅有一个已经开始结点没前驱但存有一个后继结点，存有且仅有一个终端结点没后继但存有一个前驱结点，其它的结点都存有且仅有一个前驱和一个后继结点。

通常地，一个线性表可以则表示成一个线性序列：k1,k2,…,kn，其中k1就是已经开始结点，kn就是终端结点。

是一个数据元素的有序(次序)集1、子集中必存有唯一的一个“第一元素”;2、集合中必存在唯一的一个“最后元素” ;3、除最后一个元素之外，均存有唯一的后继(后件);4、除第一个元素之外，均有唯一的前驱(前件)。

由n(n≥0)个数据元素(结点)a1,a2,…,an共同组成的非常有限序列。

计算机二级Office知识点：数据结构与算法整理计算机二级Office知识点：数据结构与算法整理计算机二级Office知识点有哪些？下面是店铺为大家搜集整理的计算机二级Office知识点：数据结构与算法整理，希望能对大家有所帮助！1.1算法1.算法的基本概念（1）概念：算法是指一系列解决问题的清晰指令。

（2）4个基本特征：可行性、确定性、有穷性、拥有足够的情报。

（3）两种基本要素：对数据对象的运算和操作、算法的控制结构（运算和操作时问的顺序）。

（4）设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2.算法的复杂度（1）算法的时间复杂度：执行算法所需要的计算工作量。

（2）算法的空间复杂度：执行算法所需的内存空间。

1.2数据结构的基本概念数据结构指相互有关联的数据元素的集合，即数据的组织形式。

其中逻辑结构反映数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为：（1）线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。

（2）非线性结构：不满足线性结构的数据结构。

1.3线性表及其顺序存储结构1.线性表的基本概念线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。

2.线性表的顺序存储结构元素所占的存储空间必须连续。

元素在存储空间的位置是按逻辑顺序存放的。

3.线性表的`插入运算在第i个元素之前插入一个新元素的步骤如下：步骤一：把原来第n个节点至第i个节点依次往后移一个元素位置。

步骤二：把新节点放在第i个位置上。

步骤三：修正线性表的节点个数。

在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。

4.线性表的删除运算删除第i个位置的元素的步骤如下：步骤一：把第i个元素之后不包括第i个元素的n—i个元素依次前移一个位置；步骤二：修正线性表的结点个数。

《数据结构》作业习题班级：学号：姓名：习题一绪论1、数据结构主要研究的三个内容为、以及定义在该结构上的。

2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。

3、数据结构被形式地定义为（D，R），其中D是的有限集，R是D上的有限集。

4、程序作用是利用swap函数，实现main函数中变量a与b的值的交换。

填写空缺使代码完整。

void swap( ) { int temp;;;; } int main( ){ int a=7,b=11;printf("a=%d,b=%d\n",a,b);swap( );printf("a=%d,b=%d\n",a,b); }5、函数triangleArea的作用是：根据三角形的三条边a、b、c，求三角形的面积。

求三角形面积的公式为)cs)(bs)(as(s---，其中s=(a+b+c)/2。

要求函数返回值类型定义为状态类型（Status 类型），当给定的三条边不能构成三角形时，函数返回ERROR；否则函数返回OK，并利用引用类型参数返回三角形的面积。

填写空缺使代码完整。

triangleArea( double a, double b, double c, area) { double s;if(a+b<=c||a+c<=b||b+c<=a) return ;else{ s=(a+b+c)/2;=sqrt(s*(s-a)*(s-b)*(s-c));return ;}6、设有定义如下：typedef struct stuInfo{int num;char name[20];char sex;struct stuInfo *next;} stuType;（1）利用指针变量stus,实现一个能容纳40个stuType类型元素动态数组。

实现该功能正确的代码为：stuType *stus;stus=( )malloc( );（2）从内存中分配两个stuType类型的结点空间，其指针分别为p、q。

数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。

A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。

A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。

logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。

int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。

该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。

6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。

7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。

一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化；. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；. 利用最少的空间实现顺序表元素的逆转；. 实现顺序表的各个元素的输出；. 彻底销毁顺序线性表，回收所分配的空间；. 对顺序线性表的所有元素删除，置为空表；. 返回其数据元素个数；. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；. 判断顺序表中是否有元素存在，对判断结果进行返回；. 编写主程序，实现对各不同的算法调用。

2．实现要求：对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价；. “初始化算法”的操作结果：构造一个空的顺序线性表。

对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；. “位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；. “逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；. “输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；. “销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；. “置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；. “求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；. “判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

数据结构线性表一、引言数据结构是计算机存储、组织数据的方式，它决定了数据访问的效率和灵活性。

在数据结构中，线性表是一种最基本、最常用的数据结构。

线性表是由零个或多个数据元素组成的有限序列，其中数据元素之间的关系是一对一的关系。

本文将对线性表的概念、分类、基本操作及其应用进行详细阐述。

二、线性表的概念1.数据元素之间具有一对一的关系，即除了第一个和一个数据元素外，其他数据元素都是首尾相连的。

2.线性表具有唯一的第一个元素和一个元素，分别称为表头和表尾。

3.线性表的长度是指表中数据元素的个数，长度为零的线性表称为空表。

三、线性表的分类根据线性表的存储方式，可以将线性表分为顺序存储结构和链式存储结构两大类。

1.顺序存储结构：顺序存储结构是将线性表中的数据元素按照逻辑顺序依次存放在一组地质连续的存储单元中。

顺序存储结构具有随机访问的特点，可以通过下标快速访问表中的任意一个元素。

顺序存储结构的线性表又可以分为静态顺序表和动态顺序表两种。

2.链式存储结构：链式存储结构是通过指针将线性表中的数据元素连接起来，形成一个链表。

链表中的每个节点包含一个数据元素和一个或多个指针，指向下一个或前一个节点。

链式存储结构具有动态性，可以根据需要动态地分配和释放节点空间。

链式存储结构的线性表又可以分为单向链表、双向链表和循环链表等。

四、线性表的基本操作线性表作为一种数据结构，具有一系列基本操作，包括：1.初始化：创建一个空的线性表。

2.插入：在线性表的指定位置插入一个数据元素。

3.删除：删除线性表中指定位置的数据元素。

4.查找：在线性表中查找具有给定关键字的数据元素。

5.更新：更新线性表中指定位置的数据元素。

6.销毁：释放线性表所占用的空间。

7.遍历：遍历线性表中的所有数据元素，进行相应的操作。

8.排序：对线性表中的数据元素进行排序。

9.合并：将两个线性表合并为一个线性表。

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

计算机二级公共基础线性表及其顺序存储结构1.设顺序表的长度为n。

下列算法中，最坏情况下比较次数小于n的是______。

A 寻找最大项B 堆排序C 快速排序D 顺序查找法2.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为______。

A 6B 96C 48D 73.设顺序表的长度为n。

下列算法中，最坏情况下比较次数等于n(n-1)/2的是______。

A 堆排序B 快速排序C 顺序查找D 寻找最大项4. 要在具有n个元素的有序顺序表中插入一个元素，插入后仍是有序顺序表，则在最坏情况下需要移动的元素个数为______。

A n-1B nC n/2D n+15. 要在具有n个元素的有序顺序表中删除一个元素，删除后仍是有序顺序表，则在最坏情况下需要移动的元素个数为______。

A n-1B nC n/2D n+16.线性表的长度为n。

在最坏情况下，比较次数为n-1的算法是______。

A 顺序查找B 同时寻找最大项与最小项C 寻找最大项D 有序表的插入7.下列叙述中正确的是______。

A 能采用顺序存储的必定是线性结构B 所有的线性结构都可以采用顺序存储结构C 具有两个以上指针的链表必定是非线性结构D 循环队列是队列的链式存储结构8.在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为______。

A nB (n+1)/2C 3n/4D n/49.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是______。

A 在顺序存储的线性表中寻找最大项B 在顺序存储的线性表中进行顺序查找C 在顺序存储的有序表中进行对分查找D 在链式存储的有序表中进行查找10.在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。

第2章线性表一、填空题1、线性结构反映结点间的逻辑关系是一对一的。

2、线性结构的特点：1）只有一个首结点和尾结点2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继3、线性表的顺序表示又称为顺序存储结构。

4、结点只有一个指针域的链表，称为单链表。

5、首尾相接的链表称为循环链表。

6、线性表的链式表示又称为非顺序映像。

7、指向链表中第一个结点的指针称为头指针。

8、链表中存储第一个数据元素的结点称为首元结点。

二、判断题1、线性表的逻辑顺序与存储顺序总是一致的。

（╳）2、顺序存储的线性表可以按序号随机存取。

（√）3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

（╳）4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

（╳）6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（√）7、线性表的链式存储结构优于顺序存储结构。

（╳）8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

（√）9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（√）10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（╳）11、线性表的特点是每个元素都有一个前驱和一个后继。

（╳）三、单项选择题1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。

A．110 B．108 C．100 D．120解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

1.3 线性表及其顺序存储结构1.3.1 线性表的基本概念1.线性表的定义在数据结构中，线性表（Linear List）是最简单也是最常用的一种数据结构。

线性表是由n（n≥0）个数据元素a1, a2, …, a n组成的有限序列。

其中，数据元素的个数n定义为表的长度。

当n=0时称为空表，记作( )或 ，若线性表的名字为L，则非空的线性表（n>0）记作：L=（a1，a2，…，a n）这里a i（i=1，2，…，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。

线性表的相邻元素之间存在着前后顺序关系，其中第一个元素无前驱，最后一个元素无后继，其他每个元素有且仅有一个直接前驱和一个直接后继。

可见，线性表是一种线性结构。

例如，英文字母表（A, B, C, …, Z）就是一个长度为26的线性表，表中的每一个英文字母是一个数据元素，四季（春、夏、秋、冬）是一个长度为4的线性表，其中每一个季节是一个数据元素。

矩阵也是一个线性表，只不过它是一个比较复杂的线性表。

在矩阵中，既可以把每一行看成一个数据元素（既每一行向量为一个数据元素），也可以把每一列看成一个数据元素（即每一列向量为一个数据元素）。

其中每一个数据元素（一个行向量或者一个列向量）实际上又是一个简单的线性表。

在复杂的线性表中，一个数据元素由若干数据项组成，此时，把数据元素称为记录（record），而由多个记录构成的线性表又称为文件（file）。

例如，一个按照姓名的拼音字母为序排列的通信录就是一个复杂的线性表，见表1-4，表中每个联系人的情况为一个记录，它由姓名、性别、电话号码、电子邮件和住址5个数据项组成。

表1-4 复杂线性表2.非空线性表的特征非空线性表具有以下一些结构特征：●有且只有一个根结点，它无前件；●有且只有一个终端结点，它无后件；●除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

结点个数n称为线性表的长度，当n=0时，称为空表。

全国计算机二级考试公共基础知识(数据结构与算法)线性表及其顺序存储结构1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。

线性表中数据元素的个数称为线性表的长度。

线性表可以为空表。

*：线性表是一种存储结构，它的存储方式：顺序和链式。

2、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i个结点的存储地址。

3、顺序表的插入、删除运算（学吧学吧独家稿件）（1）顺序表的插入运算：在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。

插入结束后，线性表的长度就增加了1。

*：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。

（2）顺序表的删除运算：在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。

删除结束后，线性表的长度就减小了1。

*：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。

插入、删除运算不方便。

栈及其基本运算栈是限定在一端进行插入与删除运算的线性表。

在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。

即栈是按照“先进后出”或“后进先出”的原则组织数据的。

线性表的顺序存储结构实验报告总结一、目的1.做实验的目的加深对线性表的理解，学会定义线性表的存储结构，掌握线性表的基本操作。

2.撰写实验报告的目的对本次实验情况进行总结,加强对实验内容的理解,对实验过程有一-个系统的认识，从中获得本次试验的经验，并对实验结果进行适当的分析,加深对栈和队列的理解和认识。

二、内容1.说明实验次数及实验内容本次实验用一次实验课时完成实验内容:节点定义:typedef struct node{int idx: int age: struct node *next:}Node, *List;本次实验的对象的存储内容包括功D和AGE,所以定义了如上的结构体，idx用于存储ID号，age用于存储年龄，next用于形成链式结构，Node定义了该类型的一一个节点，List定义了该类型的--个链表。

(1)、编写函数CreateList ()和PrintList(),从给定数组创建链表,打印链表。

int idx[8] = {1,2,3,4,5,6, 7,8}:int age[8] = {15, 18, 13, 22, 50, 18, 30, 20} :List CreatList(int idx[]，int age[], int 1en) {}int PrintList(List L) {}(2)、编写函数DeleteNode(List L, int delete_ age)，完成以下操作。

int DeleteNodeAge(List L, intdelete_ age) {}该函数传入List L,可以直接修改链表的节点，建议返回值为int 或void类型，无需为List类型，3,题同上。

2.1删除年龄为18的成员，打印链表。

2.2删除年龄为20的成员，打印链表。

2.3删除年龄为15的成员，打印链表。

2.4 (可选)删除年龄为21的成员(因无此成员，报错) ,打印链表。

.(3)、编写函数Inser tNodeByIdx(List L, Node nd)，完成以下操作。