线性表类型定义

注意区分指针变量和结点变量这两个不同的概念。 P为动态变量，它是通过标准函数生成的，即 p=(struct node*)malloc(sizeof(struct node)); 函数malloc分配了一个类型为node的结点变量的空 间，并将其首地址放入指针变量p中。一旦p所指 的结点变量不再需要了，又可通过标准函数 free(p)释放所指的结点变量空间。
页数
插入和删除操作会移动大量的结点.为避免大量结点的移 动，我们介绍线性表的另一种存储方式， 链式存储结构，简称为链表(Linked List)。 2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性 表的结点，这组存储单元即可以是连续的，也可以是不 连续的，甚至是零散分布在内存中的任意位臵上的。因 此，链表中结点的逻辑次序和物理次序不一定相同。为 了能正确表示结点间的逻辑关系，在存储每个结点值的 同时，还必须存储指示其后继结点的地址（或位臵）信 息，这个信息称为指针(pointer)或链(link)。这两部 分组成了链表中的结点结构：
单链表是由表头唯一确定，因此单链表可以用头 指针的名字来命名。 例如：若头指针名是head，则把链表称为表head。 用C语言描述的单链表如下： typedef char ElemType;
struct node{
ElemType data;
struct node *next;
};
页数
typedef struct{ struct node *head; int count; }LinkList;
p1=p2=p3=…=pn=1/n 由此可得： Ede(n)= (n-i)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结 点，平均时间复杂度也是O(n)。

2.4 一元多项式的表示
ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } { 称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系：
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
{ 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。}
i = 1; found = TRUE; while ( i<= La_len && found ) {
GetElem(LA, i, e); // 取得LA中一个元素
if (LocateElem(LB, e, equal( ))
i++;
// 依次处理下一个
else found = FALSE;
// LB中没有和该元素相同的元素
{加工型操作} ClearList( &L ) ( 线性表置空 ) PutElem( &L, i, &e ) ( 改变数据元素的值 ) ListInsert( &L, i, e ) ( 插入数据元素 ) ListDelete( &L, i, &e ) ( 删除数据元素 )
ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, e ) 初始条件： 线性表 L 已存在， 且 1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值和 e 相同。
线性结构的基本特征: 线性结构 是 一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素” 2．集合中必存在唯一的一个 “最后元素”

线性表什么是线性表？线性表是一种常见的数据结构，它由一系列具有相同数据类型的元素组成。

线性表中的元素之间存在着一对一的线性关系，即每个元素都有唯一的直接前驱和直接后继（除了第一个元素没有直接前驱和最后一个元素没有直接后继）。

线性表可以用来存储一组有序的数据，例如整数、浮点数、字符等等。

它可以通过下标来访问元素，支持插入、删除和查找操作。

线性表的分类线性表可以分为两种基本形式：顺序表和链表。

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

在顺序表中，按照元素插入顺序分为静态顺序表和动态顺序表。

静态顺序表静态顺序表是指事先申请好固定大小的存储空间，用于存储线性表的元素。

静态顺序表的大小在编译时确定，无法动态调整。

当静态顺序表已满时，如果需要插入新的元素，就无法继续插入，需要进行额外的处理。

动态顺序表动态顺序表是指不事先申请固定大小的存储空间，而在需要时进行动态扩容和缩容的顺序表。

动态顺序表的大小可以根据需要动态调整，使得线性表可以动态增长或减少。

链表链表是一种通过指针将线性表的元素链接在一起的数据结构。

链表中的每个元素都包含一个指针，指向下一个元素。

链表的存储空间可以是连续的，也可以是不连续的。

单链表单链表是链表的基本形式。

每个节点包含数据域和指针域，数据域用于存储元素的值，指针域用于指向下一个元素。

链表的头节点没有前驱节点，尾节点没有后继节点。

双链表双链表是在单链表的基础上进行扩展的。

每个节点除了有指向下一个元素的指针，还有指向前一个元素的指针。

双链表可以支持双向遍历和双向操作，但相应地增加了额外的指针域，占用更多的存储空间。

线性表的操作线性表的常用操作包括插入、删除、查找、遍历等。

插入插入操作可以在线性表的指定位置插入一个新的元素。

插入元素时，需要移动后续元素的位置来腾出空间，并调整相应的指针。

插入操作的时间复杂度为O(n)。

删除删除操作可以删除线性表中指定位置的元素。

删除元素时，需要调整前后元素的指针，使得元素之间重新链接。

Step2：数据域赋值
插入后： Step3：插入（连接）
X q
(1)式和(2)式的顺序颠倒，可以吗？
4、插入元素（在第i个元素之前插入元素e）
为什么时间复杂度不再是O(1)？
第i－1个元素
第i个元素
p
s
新插入元素
5、删除p所指元素的后继元素
P
删除前：
P->next P->next->next
删除：
五、线性表ADT的应用举例
Void mergelist(list La，list Lb,list &Lc)
{ //已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc中的元素也按值非递减排列
例: 将两个各有n个元素的有序表归并成一个有序表， 其最小的比较次数是（ ）。 A、n B、2n-1 C、2n D、n-1
三、线性表的ADT
四、线性表的分类
五、线性表ADT的应用举例
例1：已知有线性表L，要求删除所有X的出现
五、线性表ADT的应用举例
例2: 已知有两个分别有序的线性表（从小到大），要 求合并两个线性表，且合并后仍然有序。——归并 方法1: 合并，再排序O((m+n)2)
方法2： 归并，利用分别有序的特点O((m+n))
二、线性表上常见的运算
8、删除 Delete(L,i):删除线性表的第i个元素 删除前 a1 a2 … ai-1 ai ai+1 … an 删除后 a1 a2 … ai-1 ai+1 … an 9、判断是否为空 Empty(L):线性表空,则返回TRUE, 否则FALSE 10、输出线性表 Print(L):输出线性表的各个元素 11、其它操作 复制、分解、合并、分类等

顺序表类型定义
顺序表类型定义是一种数据结构，由相同类型的元素连续存储在内存中形成一个逻辑上有序的序列。

顺序表又称为线性表，它是一种可以容纳任意类型的数据的数据结构，也是计算机中最常用的数据结构之一。

顺序表的特点是：存储方式简单，因为它只需要连续的内存单元就可以存储元素；查找快，因为它具有索引，可以快速查找到需要的元素；插入和删除方便，因为顺序表本身就是一个有序的结构，只需要移动一小部分元素就可以实现插入和删除；可以随机访问，因为它具有索引，可以根据索引快速访问到指定位置的元素。

顺序表的缺点是：容量有限，因为它需要连续的内存空间，如果存储的元素太多，就会导致内存空间不够用；插入和删除效率较低，因为顺序表本身是一个有序的结构，插入和删除时需要移动大量的元素，所以效率较低。

顺序表在程序设计中有着广泛的应用，它可以用来存储数据、实现算法、实现抽象数据类型（ADT）等。

在算法设计中，顺序表可以用来实现查找、排序、插入、删除等常见的算法；在数据结构设计中，顺序表可以用来实现栈、队列、双端队列等复杂的数据结构；在ADT设计中，顺序表可以用来实现字符串、集合、图等常见的ADT。

总之，顺序表类型定义是一种简单易用的数据结构，它可以用来实现各种常见的算法和数据结构，而且可以满足大多数应用场景的需求。

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

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

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

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

（2）单向链接。

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

（3）元素类型。

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

（4）存储量受限。

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

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

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

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

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

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

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

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

数据结构---线性表线性表代码主要参考严蔚敏《数据结构（c语言版）》，有部分改动线性表的定义定义•线性表是具有相同的数据类型的n(n >= 0)个数据元素的有限序列，当n=0时线性表为一个空表•用L表示线性表则L = （a1,a2,a3,…,ano a1为表头元素，an为表尾元素o a1无直接前驱，an无直接后继特点•表中元素个数有限•表中元素具有逻辑上的顺序，表中元素有先后次序•表中元素都是数据元素•表中元素的数据类型都相同，每个元素占的空间大小一致要点数据项、数据元素、线性表的关系线性表由若干个数据元素组成，而数据元素又由若干个数据项组成，数据项是数据的不可分割的最小单位。

其中姓名，学号等就是数据项线性表的顺序表示顺序表的定义顺序表是指用一组地址连续的存储单元依次存储信息表中的数据元素，从而使得逻辑相邻的两个元素在物理位置上也相邻预先定义（为了代码可以运行）#define True 1#define False 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;第n个元素的内存地址表示为LOC(A) + (n-1)*sizeof(ElemType)假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为typedef int ElemType ;#define MaxSize 50typedef struct{ElemType data[MaxSize];int length;}SqList;一维数组可以是静态分配的，也可以是动态分配的。

静态分配后大小和空间都固定了，下面使用动态分配的形式typedef int ElemType ;#define InitSize 100 //表长度的初始大小定义#define ListIncreasement 10 //线性表存储空间的分配增量typedef struct{ElemType *data;int MaxSize,length;}SeqList;顺序表的初始化顺序表的初始化,&是C++的引用，可以使用指针代替Status InitList(SeqList &L){L.data = (ElemType *) malloc(InitSize * sizeof(ElemType));if(! L.data) exit(OVERFLOW);//存储分配失败L.length = 0;L.MaxSize = InitSize;return OK;}顺序表的插入在顺序表L的第i(1<= i <= L.length +1)个位置插入新元素e，需要将第n 个至第i (共n-i+1)个元素向后移动一个位置【最后一个到倒数第n-i+i个元素向后移动一位】。

【例2】巳知有两个按元素值递增有序的顺序表La和 Lb，设计一个算法将表La和表Lb的全部元素归并 为一个按元素值递增有序的顺序表Lc。

算法思路：用i扫描顺序表La，用j扫描顺序表Lb。 当表La和表Lb都未扫描完时，比较两者的当前元 素，将较小者插入表Lc的表尾，若两者的当前元 素相等，则将这两个元素依次插入表Lc的表尾。 最后，将尚为扫描完的顺序表的余下部分元素依 次插入表Lc的表尾。算法如下： void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)

表中ai-1领先于ai，称ai-1是ai的直接前驱，ai+1是 ai的直接后继。

线性表的抽象数据类型定义 （参见教材）
返回本章目录
2.2 线性表的顺序存储结构

线性表的顺序存储是指在内存中用地址连续的一块存储空间 依次存放线性表的数据元素，用这种存储形式存储的线性表 称其为顺序表。 假设每个数据元素占d个存储单元，且将ai的存储地址表示为 Loc(ai)，则有如下关系： Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是线性表的第一个数据元素a1的存储地址，通常 称作线性表的基地址。

【例1】 编写一算法，从顺序表中删除自第i个元素开 始的k个元素。 算法思路： 为保持顺序表的逻辑特性，需将i+k ~ n位 置的所有元素依次前移k个位置。算法如下：

int deleteK(Sqlist &sq,int i,int k)
{ if (i<1||k<1||i+k-1>sq.len) return 0; for (j=i+k-1;j<=sq.len-1;j++) sq.data[j-k]=sq.data[j]; sq.len-=k; return 1; }// deleteK

数。
第2章 线性表
2.2 线性表的顺序存储结构表示
图2-2所示为线性表在存储介质中顺序分配的情况。
第2章 线性表
逻辑地址 1 2 记录内容 a1 a2 存储地址 LOC(a ) 1 LOC(a )＋k 1 内存状况 a1 a2
…
i
…
ai LOC(a )＋(i－1)× k 1
…
ai
…
n
图2-2 线性表的顺序分配
第2章 线性表
2.3 线性表元素的操作
2.3.1 线性表元素插入操作 插入一个记录，对有序线性表结构的影响可以从以下 两个方面分析。
(1) 若插入记录关键字的值比表中所有的数据元素的
关键字值都大，那么只需在表后添加一个新记录元素，同 时使表的当前长度修正为n+1即可。
(2) 若插入记录的位置出现在线性表的中间，则情况
LOC(ai)=LOC(a1)+(i-1)×k
从以上的地址计算公式可知，只要已知线性表第 一个数据元素在内存中的存储地址，又知道每一个数 据元素所占存储单元的个数，就能计算出第i个数据元 素在内存中的位置。
第2章 线性表 例如，线性表中第一个数据元素在内存中的地址 LOC(a1)为1000，每一个数据元素占用2个存储单位，
名称“数据结构”的属性就不相同，它们分别为字符
型和数值型。
第2章 线性表 2.1.2 线性表的逻辑结构表示 在任何问题中，数据元素之间可以存在多种关系。 从数据结构的观点来看，重要的是数据元素之间的逻辑 关系。所谓逻辑关系，是指数据元素之间的关联方式或 称“邻接关系”。表2-1中数据的逻辑结构如图2-1(b)所 示，其中的圆圈称为结点。一个结点代表一个数据元素 (有时也把结点和数据元素当作同义词)，结点之间的连 线代表逻辑关系，即相应数据元素之间的邻接关系。图 2-1(b)中的逻辑结构反映了表2-1中表格作为一个数据的 组织形式，这种组织形式就是数据元素(记录)“一个接 一个地排列”。

2. 线性表的链式存储结构优于顺序存储。（× ） 3. 在单链表中，任何两个元素的存储位置之间都有固定
的联系，所以可以从头结点开始查找任何一个元素。 （×） 4. 顺序存储的线性表可以实现随机存取。（√ ）
二、单项选择题
1. 用单链表方式存储的线性表，存储每个结点需要两个域， 一个数据域，另一个是______B。
A. 当前结点所在的地址域
B. 指针域
C. 空指针域
D. 空闲域
2. 在具有n个结点的单链表中，实现__A____的操作，其算法 的时间复杂度都是O(n)。
A. 遍历链表和求链表的第i个结点
B. 在地址为p的结点之后插入一个结点
C. 删除开始结点
D. 删除地址为p的结点的后继结点
二、单项选择题
3. 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一
学习要点
3. 熟练掌握在顺序存储结构上线性表的基本操作，如查 找、插入和删除的算法。
4. 熟练掌握在各种链表结构中线性表的基本操作，能在 实际应用中选用适当的链表结构。
5. 能够从时间与空间复杂度方面综合比较线性表两种存 储结构的不同特点及其适用场合。
一、判断对错题
1. 线性表中的元素可以是各种各样的，但同一线性表中 的数据元素具有相同的特性，因此属于同一数据对象。 （ ）√
• 插入结点：移动元素次数n-i+1； • 删除结点：移动元素次数n-i。 • 决定因素：顺序表的长度以及插入、删除元素在表中
的位序。
4. 分析下述三个算法的具体功能。
ListNode *Demo1(LinkList L, ListNode *p)
{ //L是有头结点的单链表
ListNode *q=L->next;

线性表(linear list) 第二章 线性表
线性表是一种线性结构，线性结构的特点是数据元 素之间是一种线性关系，数据元素“一个接一个的 排列”。 线性结构是n（n>=0）个结点的有穷序列。对于 n>0的线性结构表示成： (a1，a2，… ai-1，ai，ai+1，…an) a1称为起始结点 an称为终端结点 起始结点， 终端结点; 起始结点 终端结点 ai-1 称为 ai 的直接前趋 i+1 称为 ai 的直接后继 直接前趋，a 直接后继。 直接前趋 直接后继
4．查找（定位） locate(L,x)： ．查找（定位） ：
依次将顺序表L中的每个元素与给定的值x进行比 较。若找到则返回其序号（下标+1），否则返回0。 int locate (sqlist L, datatype x) { int i; for ( i=0; i<st; i++) if (L.data[i]==x) return (i+1); return(0); }
void insert (sqlist *L, datatype x, int i ) { if (i<1 || i>L->last+1) error (“插入位置错误”); else if (L->last==maxsize) error (“溢出”); else { for (j=L->last-1; j>=i-1; j--) //往后移动元素 //往后移动元素 L->data[j+1]=L->data[j]; L->data[i-1]=x; //插入x L->last++; //修改表长 } }
常见的线性表的基本运算有以下几个： 常见的线性表的基本运算有以下几个：

本算法的时间复杂度为O(1)。
(5) 输出线性表DispList(L) 该运算当线性表L不为空时,顺序显示L中各元素的 值。
void DispList(SqList *L)
{
int i; if (ListEmpty(L)) return;
for (i=0;i<L->length;i++)
printf("%c",L->data[i]); printf("\n");
⑤ 将表的长度加1。
(7) 定位查找LocateElem(L,e):返回L中第1个值域 与e相等的位序。若这样的元素不存在,则返回值为0。 (8) 插 入 数 据 元 素 ListInsert(&L,i,e): 在 L 的 第 i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L 的长度增1。 (9) 删除数据元素ListDelete(&L,i,&e):删除L的第 i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度 减1。
(3) 判线性表是否为空表ListEmpty(L):若L为空 表,则返回真,否则返回假。
(4) 求线性表的长度ListLength(L):返回L中元素 个数。
(5) 输出线性表DispList(L):当线性表L不为空时, 顺序显示L中各结点的值域。 (6) 求 线 性 表 L 中 指 定 位 臵 的 某 个 数 据 元 素 GetElem(L,i,&e):用e返回L中第 i(1≤i≤ListLength(L)) 个元素的值。
线性表的存储示意图
1. 建立顺序表 其方法是将给定的含有n个元素的数组的 每个元素依次放入到顺序表中，并将n赋给顺 序表的长度成员。算法如下：

链式存储的几种形式



单链表 循环链表 双向链表
单链表的定义
typedef int DataType; class Item { public: DataType data; Item * next; Item(){next=NULL;} };
class Link { public: Item *head; Link(){head=NULL;} ～Link(){DeleteAll();} void Initiate(); void DeleteAll(); void HeadCreate(int n); void TailCreate(int n); void HeadCreateWithHead(int n); void TailCreateWithHead(int n); int Length(); Item *Locatex(DataType x); Item *Locatei(int i); DataType Get(int i); bool Insert(DataType x,int i); bool Deleted(int i); void Print(); };
Ein P i (n i 1)
i 1
n 1
在等概率情况下，Pi=1/(n+1)，则
1 n1 n Ein P (n i 1) i (n i 1) n 1 i 1 2 i 1
n 1
时间复杂度为O(n)
典型操作的算法实现
3. 删除运算
线性表的删除运算是指将表中第i个元素从线性表中删除， 使原表长为n的线性表（a1，a2，…，ai-1，ai，ai+1，…， an）变成表长为n-1的线性表 （a1，a2，…，ai-1，ai+1，…，an） i的取值范围为1≤i≤n。

顺序存储结构的优点和缺点
*
线性表的链式存储
链表定义： 采用链式存储结构的线性表称为链表 。 现在我们从两个角度来讨论链表： 从实现角度看，链表可分为动态链表和静态链表； 从链接方式的角度看，链表可分为单链表、循环链表和双链表。
*
链表
单链表 单链表上的基本运算 循环链表 双向链表 2.3.5 静态链表 顺序表和链表的比较
序号
1
2
3
4
5
6
7
8
10
9
4
9
15
21
28
30
30
42
62
51
4
9
15
21
30
30
42
51
62
删除28后
*
删除算法示意
int DelList(SeqList *L,int i,ElemType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ { int k; if((i<1)||(i>L->last+1)) { printf(“删除位置不合法！”)； return(ERROR)； } *e= L->elem[i-1]; /* 将删除的元素存放到e所指向的变量中*/ for(k=i;i<=L->last;k++) L->elem[k-1]= L->elem[k]; /*将后面的元素依次前移*/ L->last--; return(OK); }
*
头指针H
存储地址
数据域
指针域
1 D 43 7 B 13 13 C 1 19 H NULL 25 F 37 31 A 7 37 G 19 43 E 25

Data;
int
cur;
} SLinkList[MAXSIZE];
称作静态链表
与顺序表用数组存储相比，
在插入或删除时无需移元素
数据结构
28
循环链表(circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表 构成环状
特点：从表中任一结点出发均可找到表中其他结点，提高 查找效率
数据结构
6
2.2 线性表的顺序表示和实现
线性表的顺序表示是指用一组地址连续的存储单元依次存
储线性表的数据元素。这种线性表也叫顺序表。
元素地址计算方法：
LOC(ai+1)=LOC(ai)+L
LOC(ai)=LOC(a1)+(i-1)*L 其中：
L
— 一个元素占用的存储单元个数
LOC(ai) — 线性表第i个元素的地址 LOC(a1)是线性表第一个元素a1的存储地址，也叫线性表
NextElem(L, cur_e, &next_e)
ListInsert(&L, i, e)
ListDelete(&L, i, &e)
ListTraverse(L, visit())
数据结构
5
线性表的扩展操作
例:线性表La和Lb表示两个集合，现要求两集合的并，并
存放在线性表La中
例:线性表La和Lb是按元素序非递减的，合并两个线性表
的起始位置或基地址
线性表的这种内存存储表示也叫线性表的顺序存储结构，
或顺序映像(Sequential Mapping)
数据结构
7
顺序表的内存映像
特点： 实现逻辑上相邻—物理地址相邻 实现随机存取

线性表知识点总结定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。

其中n为表长。

当n=0时 线性表是⼀个空表特点：线性表中第⼀个元素称为表头元素；最后⼀个元素称为表尾元素。

除第⼀个元素外，每个元素有且仅有⼀个直接前驱。

线性表的顺序存储⼜称为顺序表。

它是⽤⼀组地址连续的存储单元（⽐如C语⾔⾥⾯的数组），依次存储线性表中的数据元素，从⽽使得逻辑上相邻的两个元素在物理位置上也相邻。

建⽴顺序表的三个属性:1.存储空间的起始位置（数组名data）2.顺序表最⼤存储容量（MaxSize）3.顺序表当前的长度（length）其实数组还可以动态分配空间，存储数组的空间是在程序执⾏过程中通过动态存储分配语句分配总结：1.顺序表最主要的特点是随机访问（C语⾔中基于数组），即通过⾸地址和元素序号可以在O(1)的时间内找到指定的元素。

2.顺序表的存储密度⾼，每个结点只存储数据元素。

⽆需给表中元素花费空间建⽴它们之间的逻辑关系（因为物理位置相邻特性决定）1.插⼊算法思路：1.判断i的值是否正确1 2 3 4 5 6#define Maxsize 50 //定义线性表的最⼤长度typedef int Elemtype // 假定表中的元素类型是整型typedef struct{Elemtype data [maxsize]; // 顺序表中的元素int lengh; // 顺序表的类型定义}Sqlist;1234567891011121314 typedef int Elemtype // 假定表中的元素类型是整型typedef struct{Elemtype *data; // 指⽰动态分配数组的指针int Maxsize,lengh; // 数组的最⼤容量和当前个数}Sqlist;//C语⾔的动态分配语句为#define InitSize 100SeqList L;L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);/*注意:动态分配并不是链式存储，同样还属于顺序存储结构，只是分配的空间⼤⼩可以在运⾏时决定*/2.判断表长是否超过数组长度3.从后向前到第i个位置，分别将这些元素都向后移动⼀位4.将该元素插⼊位置i 并修改表长代码分析：最好情况：在表尾插⼊（即i=n+1），元素后移语句将不执⾏，时间复杂度为O(1)。

824-计算机基础考试大纲计算机基础包括数据结构、计算机网络两部分内容，每部分内容各占1/2。

I 数据结构课程基本要求：数据结构是在计算机科学中是一门综合性的专业基础课。

课程主要内容包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、内排序、文件管理和外排序等。

考试的具体要求包括：1. 全面系统地掌握队列、堆、栈、树、图等基本数据结构，深刻理解和熟练掌握课程中的典型算法；2. 提高对各种数据结构与算法的程序设计能力，提高对数据结构与算法的实际运用能力。

考试内容：1. 线性表1.1. 线性表的类型定义1.2. 线性表的顺序表示与实现1.3. 线性表的链式表示与实现2. 栈和队列2.1. 栈的定义与实现2.2. 栈与递归的实现2.3. 队列的定义与实现3. 串3.1. 串的定义与实现3.2. 串的模式匹配算法4. 数组和广义表4.1. 数组的定义与实现4.2. 矩阵的压缩存储4.3. 广义表的定义与实现4.4. 广义表的递归算法5. 树和二叉树5.1. 树的定义和基本术语5.2. 二叉树的定义、性质和存储结构5.3. 遍历二叉树和线索二叉树5.4. 树和森林5.5. 赫夫曼树及其应用5.6. 回溯法与树的遍历6. 图6.1. 图的定义和术语6.2. 图的存储结构6.3. 图的遍历6.4. 最短路径7. 动态存储管理7.1. 边界标识法7.2. 伙伴系统7.3. 存储紧缩8. 查找8.1. 静态查找表8.2. 动态查找表8.3. 哈希表9. 内部排序9.1. 内部排序算法，插入排序、快速排序、选择排序、归并排序和基数排序等9.2. 内部排序算法的比较10. 外部排序10.1. 外存信息的存取10.2. 多路平衡归并的实现10.3. 选择排序10.4. 最佳归并树11. 文件11.1. 有关文件的基本概念11.2. 顺序文件与索引文件11.3. 直接存取文件（散列文件）11.4. 多关键字文件参考书目：1.《数据结构（C语言版）》作者：严蔚敏，吴伟民出版社：清华大学出版社ISBN：97873020236852.《数据结构与算法》作者：张铭，王腾蛟，赵海燕出版社：高等教育出版社ISBN：9787040239614II 计算机网络课程基本要求1.掌握计算机网络的基本概念、基本原理和基本方法。