线性表的基本概念.

线性表的概念线性表是数据结构中最基本的一种，它是由n个具有相同数据类型的数据元素组成的有限序列。

线性表的特点是数据元素之间的关系是一对一的，即每个数据元素都只有一个直接前驱和一个直接后继。

线性表可以用顺序存储结构或链式存储结构来实现。

顺序存储结构是将线性表中的数据元素按其逻辑顺序依次存储在一组地址连续的存储单元中，这样就可以通过元素在存储器中的相对位置来表示元素之间的逻辑关系。

而链式存储结构则是通过指针来实现数据元素之间的逻辑关系，每个数据元素都有一个指针域，指向其直接后继元素的存储位置。

线性表的应用十分广泛，它在计算机科学领域中有着重要的地位。

下面我们将从几个方面来探讨线性表的应用。

首先，线性表可以用来实现栈和队列。

栈是一种先进后出的数据结构，而队列是一种先进先出的数据结构。

它们都可以通过线性表来实现，栈可以用顺序存储结构或链式存储结构来实现，而队列通常使用链式存储结构来实现。

其次，线性表可以用来实现线性表。

在实际的软件开发中，经常需要对数据进行排序操作，而线性表提供了一个非常方便的数据结构来实现排序算法。

常见的排序算法有冒泡排序、选择排序、插入排序、快速排序等，它们都可以通过线性表来实现。

另外，线性表还可以用来实现线性表。

线性表可以用来表示多项式，多项式的加法、减法、乘法等运算都可以通过线性表来实现。

这在数学计算和科学计算中有着重要的应用。

此外，线性表还可以用来实现图的邻接表。

图是一种非线性的数据结构，它由顶点的有限集合和顶点之间边的集合组成。

图的邻接表是一种常用的表示方法，它可以通过线性表来实现。

邻接表中的每个顶点都对应一个线性表，用来存储与该顶点相邻的顶点。

总的来说，线性表作为数据结构中最基本的一种，它在计算机科学领域中有着广泛的应用。

通过线性表，我们可以实现栈和队列、排序算法、多项式运算、图的邻接表等功能。

因此，对线性表的深入理解和掌握对于计算机科学领域的学习和工作都是非常重要的。

希望通过本文的介绍，读者能对线性表有一个更深入的理解，并能够在实际的应用中灵活运用线性表。

计算机二级公共基础部分：线性表及其顺序存储结构: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分析结论顺序存储结构表示的线性表，在做插入或删除时，平均需要移动大约一半的数据元素。

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

线性表线性表的基本概念线性表的定义线性表是由n(n>=0) 个相同类型的数据元素组成的有限序列，标记为:L=(a1,a2,...,a i,...,a n)线性表中元素的个数n定义为线性表的长度，当n=0时为空表。

当n>0时，线性表的逻辑结构如图所⽰:线性表的⼏个概念：逻辑特征：若⾄少含有⼀个元素，则只有唯⼀的起始元素若⾄少含有⼀个元素，则只有唯⼀的尾元素除了起始元素外，其他元素有且仅有⼀个前驱元素除了尾元素外，其余元素有且只有⼀个后继元素线性表中的每个元素有唯⼀的序号（逻辑序号），同⼀个线性表中可以有多个相同的元素，但他们的序号是不同的。

线性表的基本运算1、初始化InitList(L)。

其作⽤是建⽴⼀个空表L（即建⽴线性表的构架，但不含任何数据元素）。

2、销毁线性表DestroyList(L)。

其作⽤是释放线性表L的内存空间。

3、求线性表的长度ListLength(L)。

其作⽤是返回线性表L的长度。

4、求线性表中第i个元素GetElem(L,i,e)。

其作⽤是返回线性表L的第i个数据元素。

5、按值查找LocateElem(L,x)。

若L中存在⼀个或多个值与x相等的元素，则其作⽤是返回第⼀个值为x的元素的逻辑序号。

6、插⼊元素ListInsert(L,i,x)。

其作⽤是在线性表L的第i个位置上增加⼀个以x为值的新元素7、删除元素ListDelete(L,i)。

其作⽤是删除线性表L的第i个元素ai。

8、输出元素值DispList(L)。

其作⽤是按前后次序输出线性表L的所有元素值我们通过以下实例进⾏分析：1、利⽤两个线性表LA，LB分别表⽰两个集合A&B，要求⼀个新集合A=A∪Bvoid Union(SqList &La,SqList Lb){ElemType e;int la_len,lb_len;int i;la_len = ListLength(La)//ListLength 返回长度lb_len = ListLength(Lb)//ListLength 返回长度for(i = 1;i <= lb_len ;i++){GetElem(Lb,i,e)//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal))ListInsert(La,++la_len,e);//// La中不存在和e相同的元素，则插⼊之}}线性表LA和LB，其元素均按⾮递减有序排列，编写⼀个算法将它们合并成⼀个线性表LC，且LC的元素也是按⾮递减有序排列。

【数据结构】线性表的基本操作【数据结构】线性表的基本操作1：定义1.1 线性表的概念1.2 线性表的特点2：基本操作2.1 初始化操作2.1.1 空表的创建2.1.2 非空表的创建2.2 插入操作2.2.1 在指定位置插入元素2.2.2 在表头插入元素2.2.3 在表尾插入元素2.3 删除操作2.3.1 删除指定位置的元素2.3.2 删除表头的元素2.3.3 删除表尾的元素2.4 查找操作2.4.1 按值查找元素2.4.2 按位置查找元素2.5 修改操作2.5.1 修改指定位置的元素 2.5.2 修改指定值的元素3：综合操作3.1 反转线性表3.2 合并两个线性表3.3 排序线性表3.4 删除重复元素3.5 拆分线性表4：线性表的应用场景4.1 数组的应用4.2 链表的应用4.3 栈的应用4.4 队列的应用附件：无法律名词及注释：- 线性表：根据某种规则排列的一组元素的有限序列。

- 初始化操作：创建一个空的线性表，或者创建一个已经包含一定元素的线性表。

- 插入操作：在线性表的指定位置或者表头、表尾插入一个新元素。

- 删除操作：从线性表中删除掉指定位置或者表头、表尾的元素。

- 查找操作：在线性表中按照指定的元素值或者位置查找元素。

- 修改操作：更改线性表中指定位置或者值的元素。

- 反转线性表：将线性表中的元素顺序颠倒。

- 合并线性表：将两个线性表合并成一个新的线性表。

- 排序线性表：按照某种规则对线性表中的元素进行排序。

- 删除重复元素：将线性表中重复的元素删除，只保留一个。

- 拆分线性表：将一个线性表分成多个不重叠的子线性表。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、线性表的应用1.程序语言中的数组：数组是一种典型的顺序存储结构的线性表，常用于存储具有相同类型的数据元素。

线性表Content线性表的基本概念1线性表的顺序存储结构2线性表的链式存储结构3线性表的基本概念数据结构包括三个方面逻辑结构存储结构运算(a)集合结构(b)线性结构(c)树形结构(d)图结构四种基本的结构关系线性表的定义线性表是零个或多个数据元素构成的线性序列，记为（a0，a1，…，a n-1）。

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

当n=0 时，此线性表为空表。

设线性表（a0，a1，…a i-1,a i,a i+1，… a n-1），其中a i-1是a i的直接前驱a i+1是a i的直接后继a0没有直接前驱a n-1没有直接后继除a0和a n-1外，其他元素有且仅有一个直接前驱和一个直接后继学号姓名性别964501王小红女964502林悦女964503陈菁菁女964504张可可男1.字母表（A,B,C……Z ）线性表举例2.学生信息表线性表的抽象数据类型（描述规范）ADT List{数据：零个或多个数据元素构成的线性序列(a0, a1, …, a n−1)。

数据元素之间的关系是一对一关系。

运算：Init(L)：初始化运算。

构造一个空的线性表L，若初始化成功，则返回OK，否则返回ERROR。

Destroy(L)：撤销运算。

判断线性表L 是否存在，若已存在，则撤销线性表L；否则，返回ERROR。

IsEmpty(L)：判空运算。

判断线性表L 是否为空，若为空，则返回OK；否则返回ERROR。

Length(L)：求长度运算。

若线性表L 已存在，返回线性表L 的元素个数；否则返回ERROR。

；否则，返回ERROR。

Find(L,i):查找运算。

若线性表L 已存在且0≤i≤n-1，则返回元素aiInsert(L,i, x):插入运算。

若线性表L 已存在且-1≤i≤n-1，则在元素ai之后插入新元素x，插入成功后返回OK，否则返回ERROR。

）线性表的抽象数据类型（描述规范，删除成功后返回OK，否则Delete(L,i):删除运算。

数据结构(线性表)习题与答案数据结构(线性表)习题与答案1. 线性表的定义线性表是一种常用的数据结构，它由一系列元素组成，并且每个元素具有前驱和后继关系。

线性表可以通过顺序存储或链式存储来实现。

2. 线性表的实现方式2.1 顺序存储顺序存储是利用数组来实现线性表的一种方式。

数组的每个元素可以存储一个数据项，通过下标可以快速访问和操作其中的元素。

2.2 链式存储链式存储是通过节点之间的指针关联来实现线性表的一种方式。

每个节点包含数据域和指针域，指针域指向下一个节点。

3. 线性表的基本操作3.1 初始化线性表初始化线性表需要给表头节点分配内存空间，并将头节点的指针域置为空。

3.2 插入元素在线性表的某个位置插入元素，需要先找到插入位置的前一个节点，然后将新节点插入到该位置。

调整节点之间的指针关联即可完成插入操作。

3.3 删除元素删除线性表中的某个元素，需要找到待删除元素的前一个节点，然后将该节点的指针指向待删除节点的下一个节点，释放待删除节点的内存空间即可。

3.4 查找元素查找线性表中某个元素的位置，可以从表头节点开始逐个比较节点的数据域，直到找到目标元素或者遍历结束。

4. 线性表的习题与答案4.1 习题1已知线性表L中的元素按非递减顺序排列，设计一个算法，将元素x插入到L中，保持L的有序性。

解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个大于等于x的节点的前一个节点，记为p。

2) 创建新的节点node，将x赋值给node的数据域。

3) 将node的指针域指向p的下一个节点。

4) 将p的指针域指向node。

5) 插入完成。

4.2 习题2已知线性表L中的元素按递减顺序排列，设计一个算法，删除L中所有大于x的元素。

解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个小于等于x的节点的前一个节点，记为p。

2) 将p的指针域指向p的下一个节点，删除p的后继节点。

3) 重复执行步骤2，直到遍历结束。

数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。

线性表的概念
线性表是计算机科学中一种重要的数据结构，广泛应用于各种计算任务的解决。

它定义为一种有序的存储结构，由一系列相同数据类型的元素组成，可以顺序访问和操作，元素可以通过索引来查找和修改。

线性表的数据结构特征主要有以下几点：
（1）顺序存储。

线性表中元素是有序排列的，每个元素在内存中都有一个固定的地址。

（2）单向链接。

线性表中的元素只有一个指针，只能指向它的下一个元素，形成一个单向链表，使其更容易进行插入和删除操作。

（3）元素类型。

线性表中的元素类型可以是任何类型的数据，甚至可以是结构体或联合体。

（4）存储量受限。

线性表只能存储有限数量的元素，超出它的存储量后可能要重新分配存储空间，降低程序的效率。

线性表有很多应用场景，比如用于存储处理图形信息的图算法，编码解码软件，操作系统的程序管理，数据库的索引查询等。

线性表的应用场景受到数据结构的影响，有时需要考虑复杂度和存储空间等问题。

近年来，有关线性表的研究也取得了显著进展。

举例来说，基于线性表的静态分析和动态编程技术，利用静态分析技术可以更好地识别和分析程序代码中的控制流和数据流，有效提高程序的性能。

而动态编程技术则可以在线性表中根据元素间的函数关系来构造更加高
效的程序。

总之，线性表是计算机科学中一种重要的数据结构，具有良好的灵活性，可以满足各种程序处理的需求。

由于线性表的易学性和多样性，它被广泛用于计算任务的实现中。

数据结构实验报告线性表数据结构实验报告：线性表引言：数据结构是计算机科学中的重要概念，它涉及到如何组织和存储数据，以及如何有效地操作和管理这些数据。

线性表是数据结构中最基本的一种，它是一种有序的数据元素集合，其中的元素之间存在着一对一的关系。

一、线性表的定义和特点线性表是由n个数据元素组成的有限序列，其中n为表的长度。

这些数据元素可以是相同类型的，也可以是不同类型的。

线性表中的数据元素按照一定的顺序排列，并且每个数据元素都有唯一的前驱和后继。

线性表的特点有以下几个方面：1. 数据元素之间是一对一的关系，即每个数据元素只有一个直接前驱和一个直接后继。

2. 线性表中的元素是有序的，每个元素都有一个确定的位置。

3. 线性表的长度是有限的，它的长度可以是0，也可以是任意正整数。

二、线性表的实现方式线性表可以使用不同的数据结构来实现，常见的实现方式有数组和链表。

1. 数组实现线性表：数组是一种连续存储的数据结构，它可以用来存储线性表中的元素。

数组的优点是可以快速访问任意位置的元素，但是插入和删除操作需要移动其他元素，效率较低。

2. 链表实现线性表：链表是一种非连续存储的数据结构，它通过指针将线性表中的元素链接起来。

链表的优点是插入和删除操作简单高效，但是访问任意位置的元素需要遍历链表，效率较低。

三、线性表的基本操作线性表的基本操作包括插入、删除、查找和修改等。

1. 插入操作：插入操作用于向线性表中插入一个新元素。

具体步骤是先将插入位置后面的元素依次后移，然后将新元素插入到指定位置。

2. 删除操作：删除操作用于从线性表中删除一个元素。

具体步骤是先将删除位置后面的元素依次前移，然后将最后一个元素删除。

3. 查找操作：查找操作用于在线性表中查找指定元素。

具体步骤是从线性表的第一个元素开始逐个比较，直到找到匹配的元素或者到达线性表的末尾。

4. 修改操作：修改操作用于修改线性表中的某个元素的值。

具体步骤是先查找到要修改的元素，然后将其值更新为新值。

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时，称为空表。

数据结构与算法华东师范大学计算机系杨沛第二章线性表2.1 线性表的基本概念线性表是具有相同数据类型的数据元素的有限序列。

由n（n≥0）个数据元素k0,k1,…,kn-1组成的线性表记为（k0 ,k1 ,…,kn-1），线性表中包含的数据元素的个数n称为线性表的长度（length），称长度为零的线性表为空的线性表（简称为空表）。

相关概念：表头、表尾、前驱、后继有序线性表：数据元素的相对位置与它们的值有联系。

无序线性表：数据元素的相对位置与它们的值没有联系。

第二章线性表例小于20的质数组成的线性表(2,3,5,7,11,13, 17,19)；英文字母表也是线性表，表中每个字母是一个数据元素：(A,B,C,……,Z)；2.2 顺序表2.2.1 线性表顺序表（sequential list）就是顺序存贮的线性表，即用一组连续的存贮单元依次、连续地存贮线性表中的结点。

如果每个结点占用s个存贮单元，并假设存放结点ki（0≤i≤n-1）的开始地址为loc(k0)，则结点ki的地址loc(ki)可表示成Loc(ki) =loc(k0) + i*s。

2.2 顺序表在C 语言中，可用数组表示线性表：#define MAXN 100int list[MAXN];int n;线性表的结点k 0,k 1,…,k n-1依次存放在数组单元list[0]，list[1]，…，list[n-1]。

2.2.1 线性表最大表长实际表长线性表2.2 顺序表2.2.1 线性表假设s=sizeof(int)，则可得到计算ki的地址的公式，因loc(ki)=&list[i]，而&list[i]=&list[0]+i·s，故loc(ki)=&list[0]+i·s。

2.2 顺序表2.2.2 顺序表的操作（1）初始化：初始长度置为0即可（n=0;），数组空间在编译时分配。

（2)顺序表的插入：插入算法的C函数SqListInsert()：若插入位置i不在可以插入的位置上，即i＜0或i>n，则返回0；若n=MAXN，即线性表已满，此时数组list[]没有多余的存贮单元可以存放新结点，则返回-1；若插入成功，则返回12.2 顺序表实际表长（2）顺序表的插入：int SqListInsert(int list[],int*p_n,int i,int x) {int j;if(i<0||i>*p_n）return(0);//i不是合法的插入位置if(*p_len==MAXN)return(-1);//线性表已满2.2 顺序表for(j=*p_n;j>i;j--)list[j]=list[j-1];//结点右移list[i]=x;(*p_n)++;//表长加1return(1);｝2.2 顺序表（2）顺序表的插入：对于存放在数组list[]中的、具有n个结点的顺序表，为了把值为x的结点插在表的位置i（0≤i≤n）上，可调用如下的语句：k=SqListInsert(list, &n, i, x);注：结点移动是本算法的关键操作2.2 顺序表（3）顺序表的删除：删除算法的C函数SqListDelete()：在具有n个结点的顺序表中，删除第i（0≤i≤n-1）个位置上的结点，使线性表长度减1，若删除位置不合法，即i＜0或i≥n，则返回0；若删除位置合法，即0≤i≤n-1，则删除成功，返回1。