1 第2章 线性表
线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：
线性表的逻辑结构特征
线性表的顺序存储和链式存储两种存储结构的特点
在两种存储结构下基本操作的实现
2-1 重点难点指导
2-1-1 相关术语
1．线性表
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,an)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表
顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表
用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表
每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针
要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。
6．头结点
要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
2 7．头结点的作用
要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储
1．顺序表
1 第2章 线性表辅导
本章通过实例给出线性表的定义，介绍线性表的逻辑结构、顺序存储结构和链式存储结构，讨论线性表在两种不同存储结构下对应的顺序表和链表的相关操作，介绍线性表的简单应用。
通过本章学习，要求同学们：
1.掌握线性表的定义和逻辑结构。
2.掌握线性表的顺序存储结构的有关概念，能利用C语言的数组和指针实现对顺序表的相关操作。
3.掌握线性表的链式存储结构的有关概念，并重点掌握单向链表的特点和访问方式，能利用C语言的结构变量和指向结构体的指针实现对链表的相关操作。
4.正确理解线性表两种存储结构各自的特点和应用场合，能利用所学知识和按照相关要求设计算法、编制程序，利用线性表解决简单的应用问题。
一、本章知识点
1. 线性表的定义及特点
线性表是一种最简单、最常用的一种数据结构。线性表中的元素存在着一对一的相互关系。
线性表是n（n≥0)个数据元素的有限序列。其中n为数据元素的个数，定义为数据表的长度。当n为零时的表称为空表。当n>0时，一般将线性表记为：（a1,a2,…ai-1,ai,…an），其中ai（i=1,2,3,…,n)是属于某个数据对象的元素，由线性表的定义，若线性表至少包含2个元素，则线性表中的数据元素之间存在以下关系：
1.表中存在称作“第一个”的元素，例如上表中的a1，存在称作“最后一个”的数据元素，例如上表中的an。
2.表中第一个元素a1前面没有元素和它相邻，称它没有直接前驱，它后面有且只有一个元素a2与它相邻，称它有且只有一个直接后继。而表中“最后一个”元素an有且只有一个直接前驱an-1，没有直接后继。
3．除“第一个”元素和“最后一个”元素外，其它每个元素均有且只有一个直接前驱和一个直接后继。
2.线性表的顺序存储结构
用一组地址连续的存储单元依次存放线性表的数据元素，该结构的特点是逻辑上相邻的数据元素在物理上也相邻，可以随机访问，一对一的关系。
用顺序存储结构存储的线性表称为顺序表
数据结构与算法
华东师范大学计算机系
杨沛第二章线性表
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 顺序表
顺序表（sequential list）就是顺序存贮的线性表，即用一组连续的存贮单元依次、连续地存贮线性表中的结点。
如果每个结点占用s个存贮单元，并假设存放结点ki（0≤i≤n-1）的开始地址为loc(k0)，则结点ki的地址loc(ki)可表示成
Loc(ki) =loc(k0) + i*s。2.2.1 线性表2.2 顺序表
在C语言中，可用数组表示线性表：
#defineMAXN100
intlist[MAXN];
intn;线性表的结点k0,k1,…,kn-1依次存放在数组单元list[0]，list[1]，…，list[n-1]。2.2.1 线性表最大表长
实际表长线性表2.2 顺序表
假设s=sizeof(int)，则可得到计算ki的地址的公式，
因loc(ki)=&list[i]，而&list[i]=&list[0]+i·s，
故loc(ki)=&list[0]+i·s。2.2.1 线性表2.2 顺序表
（1）初始化：初始长度置为0即可（n=0;），数组空间在编译时分配。
（2)顺序表的插入：
插入算法的C函数SqListInsert()：若插入位置i不在可以插入的位置上，即i＜0或i>n，则返回0；若n=MAXN，即线性表已满，此时数组list[]没有多余的存贮单元可以存放新结点，则返回-1；若插入成功，则返回12.2.2 顺序表的操作2.2 顺序表
1
数
据
结
构
导
论
算法汇总
2
第2章 线性表
void error(char ch_1[])/*['erə] */
{
printf("\t%s\n",ch_1);
return;
}
1、顺序表
（1）类型定义
const maxsize=顺序表的容量; /*const n. 常量，常数*/
typedef struct
{ datatype data[maxsize];
int last;
}sqlist;
/* sequence ['si:kwəns] vt.按顺序排好. list [list] n. 列表*/
（2）插入
void insert_sqlist(sqlist *L,datatype x,int i) /*改成*L后就变成了值传递方式，这样才成功*/
{
int j;
if((*L).last==maxsize) error("biao man");
if((i<1)||(i>(*L).last+1)) error("fei fa wei zhi");
for(j=(*L).last;j>=i;j--)
(*L).data[j]=(*L).data[j-1];
(*L).data[i-1]=x;
(*L).last++;
} /*最坏情况时间复杂性n，平均时间复杂性n/2，平均时间复杂性量级O(n)*/
（3）删除
void delete_sqlist(sqlist *L,int i)
{
int j;
if((i<1)||(i>L->last)) error("fei fa wei zhi");
for(j=i+1;j<=L->last;j++) 3
L->data[j-2]=L->data[j-1];
L->last--;
