学步园

简介
线性表是数据结构中最简单、最重要的结构形式之一，是最经常遇到的一种操作对象，在程序设计语言和程序设计中广泛使用。本章将系统地讨论其存储、运算及应用。

学习重点
（1）了解线性表的逻辑结构是数据元素之间存在着线性关系，在计算机中表示这种关系的两种不同的存储结构是顺序存储结构和链式存储结构。
（2）熟练掌握线性表的两种存储结构:顺序存储结构和链式存储结构.
（3）熟练掌握线性表的两种存储结构的基本算法:查找、插入、删除等.

线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结构。

线性表的概念

1． 线性表的定义
线性表（linear list）是具有相同类型的n（n≥0）个数据元素a0，a1，…an-1组成的有限序列。其中n 称为线性表的长度，当n=0时称为空线性表，n>0时称为非空表。

二、说明
1、一个线性表可以一个标识符来命名，如：
A=(a0,a1,a2,...,an-1)

2、线性表中的数据元素要求具有相同类型，它的数据类型可以根据具体情况而定，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。它可以是一个数、一个字符或一个字符串，也可以由若干个数据项组成。

3、特征
从线性表的定义可以看出线性表的特征：
（1）有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;
（2）有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱;
（3）其它结点都有一个直接前驱和直接后继；
（4）元素之间为一对一的线性关系。
4、线性表中数据元素的相对位置是确定的，如果把一个线性表中的数据元素的位置做改动，那么变动后的线性表与原来的线性表是两个不同的线性表。

a1,a2,...ai-1, ai ,ai+1,...,an

线性表是一种典型的线性结构，对应的逻辑结构图如图2-1所示。

实例：
例1：某小从1996到2002年的计算机拥有量可表示为线性表：
（123，234，333，444，456，567，677）
例2：26个英文字母 (A,B,C……,Z)
例3：某中学的成绩表

线性表的链接存储结构

一、 存储方法
线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有单链表、循环链表和双向链表、多重链表等。

结点：线性表的每个元素除了需要存储自身的信息外,还需要存储一至两个指示其直接后续元素或直接前驱元素的地址(称为链接指针),这两部分信息组成了一个数据元素的存储结构,称为结点。如下图：

1、单链表结构
在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。

单链表可用Ｃ描述为:
struct node
{ elemtype data; /*元素类型*/
node *link; /*指针类型,存放下一个元素地址*/
}

2、循环链表结构

单链表上的访问是一种顺序访问，从其中某一个结点出发，可以找到它的直接后继，但无法找到它的直接前驱。因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存贮空间，仅对表的链接方式稍作改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又没有增加额外的存贮空间，称这们的链表为单循环链表，在不引起混淆时称为循环表(后面还要提到双向循环表)

循环链表上的运算与单链表上运算基本一致，区别只在于最后一个结点的判断(即循环的条件不同)，但利用循环链表实现某些运算较单链表方便(从某个结点出发能求出它的直接前驱，而单链表是不行的，只能从头出发)。图示

非空表:

空表:

3、双向链表结构
在单链表中，从某个结点出发可以直接找到它的直接后继，时间复杂度为O(1) ，但无法直接找到它的直接前驱；在单循环链表中，从某个结点出发可以直接找到它的直接后继，时间复杂仍为O(1)，直接找到它的直接前驱，时间复杂为O(n)。有时，希望能快速找到一个结点的直接前驱，这时，可以在单链表中的结点中增加一个指针域指向它的直接前驱，这样的链表，就称为双向链表(一个结点中含有两个指针)。如果每条链构成一个循环链表，则会得双向循环链表。


双向链表可用C描述如下：
struct node
{
elemtype data; /*结点的数据域,类型设定为 elemtype*/
node *link1,*link2; /*定义指向直接后继和直接前驱的指针*/
}

二、 数据元素的位置确定

在线性链表中每个结点的逻辑关系是通过指针来表示的，结点与结点间的存储单元可以不连续；要确定链表中任意结点的存储位置，必须从head开始，顺着链接指针进行遍历就可得到。

三、 线性链表的创建

1、结点的表示
typedef strude node
{
elemtype data;
struct node *link1;
struct node *link2*双向链表需要*/
}NODE;

2、线性链表的创建程序
NODE *create_link_list(int n)
{ int i;
NODE *head,*p,*q;
if(n==0)return(NULL);
head=(NODE *)malloc(sizeof(NODE));
p=head;
for(i=1;i<n;i++)
{ ......./*输入数据域的内容*/
q=(NODE *)malloc(sizeof(node));
p->link=q;
p=q;
}
......./*输入最后元素数据域的内容*/

p->link=NULL;
return(head);
}
注意:熟练掌握指针操作!

顺序存储结构

线性表的顺序存储结构

一、 存储方法

线性表的顺序存储结构,也称为顺序表。它是线性表的一种最简单的存储结构。其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度和线性表中一个元素所需要的存储字节数的乘积，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。数据元素之间前趋与后继关系体现在存放位置的前后关系上。

二、 数据元素的位置确定

假设线性表中元素为（a0，a1，….,an-1），设第一个元素a0的内存地址为LOC(a0)（在图2-2中表示为b），而每个元素在计算机内占d个存贮单元,则第i个元素ai-1的地址为LOC(ai-1)=LOC(a0)+(i-1)×d (其中0≤i≤n-1)

注意：
　在顺序表中，每个结点a_i的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。

可用数组存放线性表，用C语言描述为:
#define MAXSIZE 100
elemtype list[MAXSIZE];
int n;/* n是线性表的当前长度*/
elemtype可以是int,char,float,struct student等。

三、 线性表顺序存储的创建程序
void creat_sr_list(int n,elemtype list[])
{
int i;
for(i=0;i<n;i++)
.../* 输入每个数据元素 例：scanf(“%d”,&list[i]) */ ;
}

用数组来实现表时，我们利用了数组单元在物理位置上的邻接关系来表示表中元素之间的逻辑关系。由于这个原因，用数组来实现表有如下的优缺点。
优点是：
无须为表示表中元素之间的逻辑关系增加额外的存储空间；
可以方便地随机访问表中任一位置的元素。
缺点是：
插入和删除运算不方便，除表尾的位置外，在表的其他位置上进行插入或删除操作都必须移动大量元素，其效率较低；

由于数组要求占用连续的存储空间，存储分配只能预先进行静态分配。因此，当表长变化较大时，难以确定数组的合适的大小。确定大了将造成浪费。

顺序表上实现的基本运算

与数据结构密切相关的是定义在其上的一组基本运算，其它复杂的运算（应用）需要调用基本运算来完成。

常见线性表的运算有：

1．置空表 SETNULL（&L）将线性表L置成空表
2．求长度 LENGTH（L） 求给定线性表L的长度
3．取元素 GET（L，i） 若1≤i≤length(L),则取第i个位置上的元素，否则取得的元素为NULL。
4．求直接前趋 PRIOR（L，X）求线性表L中元素值为X的直接前趋，若X为第一个元素，前驱为NULL。
5．求直接后继 NEXT（L，X）求线性表L中元素值为X直接后继，若X为最后一个元素，后继为NULL。
6．定位函数 LOCATE（L，X） 在线性表L中查找值为X的元素位置，若有多个值为X，则以第一个为准，若没有，位置为0。
7．插入 INSERT（&L，X，i）在线性表L中第i个位置上插入值为X的元素。
8．删除 DELETE（&L，i） 删除线性表L中第i个位置上的元素。

插入运算:在长度为n的线性表(a0,a1,a2,...an-1)中,插入一个新的数据元素x到线性表的第i(0<=i<=n)个位置,使其变为长度为n+1的线性表(a0,a1,a2,...,ai-1,x,ai,...an-1).

删除运算:在长度为n的线性表(a0,a1,a2,...an-1)中,删除线性表的第i(0<=i<=n)个位置上的数据元素,使其变为长度为n-1的线性表(a0,a1,a2,...,ai-1,ai+1,...an-1).

线性表的插入运算（顺序存储结构）
算法：
1、将ai,ai+1,...,an-1依次后移一个位置，使第i位置留空
2、将新元素x放在空出的位置上。
3、线性表长度加1。

程序：：：：：：：；
int sq_ins(elemtype list[],int *pn,int i,elemtype x)
{
int j;
if (i<0||i>*pn) return(1);
if(*pn==MAXSIZE) return(2);
for(j=*pn;j>i;j--)
list[j]=list[j-1];
list[i]=x;
(*pn)++;
return(0);
}
#define MAXSIZE 100
elemtype list[MAXSIZE];
int n;
main()
{
int i,n,x;
scanf(“%d”,&n);
create_sq_list(n,list);
scanf(“%d,%d”,&i,&x);
m=sq_ins(list,&n,i,x);
if(m==1) printf(“i error”);
if(m==2) printf(“Overflow”);
if(m==0) printf(“ins success”);
for(i=0;i<n;i++)
printf(“%d”,list[i]);
}

插入算法花费的时间，主要在于循环中元素的后移（其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=0时，全部元素都得移动，需n次移动，当i=n时，不需移动元素，也就是说该算法在最好情况下需要Ο(1)时间，在最坏情况下需要Ο(n)时间。由于插入可能在表中任何位置上进行，因此，有必要分析算法的平均性能。设在长度为n的表中进行插入运算所需的元素移动次数的平均值为EIN(n)。由于在表中第i个位置上插入元素需要的移动次数为n-i+1，故

其中，pi表示在表中第i个位置上插入元素的概率。考虑最简单的情形即假设在表中任何合法位置i (1≤i≤n+l)上插入元素的机会是均等的，从而，在等概率插入的情况下，EIN(n)=n/2也就是说，用数组实现表时，在表中做插入运算，平均要移动表中一半的元素，因而算法所需的平均时间仍为Ο(n)。

删除
（1）删除运算的逻辑描述
　线性表的删除运算是指将表的第i（1≤i≤n）个结点删去，使长度为n的线性表
（a₁，…，a_i-1，a_i，a_i+1，…，a_n）
　变成长度为n-1的线性表
（a₁，…，a_i-1，a_i+1，…，a_n）
注意：
　当要删除元素的位置i不在表长范围（即i＜1或i＞L-＞length）时，为非法位置，不能做正常的删除操作

（2）顺序表删除操作过程
　在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。其删除过程【参见动画演示】
线性表的删除运算
算法：
1、将ai+1,...,an-1依次前移一个位置
2、线性表长度减1。
程序：
int sq_del(elemtype list[],int *pn,int i)
{
int j;
if (i<0||i>*pn) return(1);
for(j=i+1;j<*pn;j++)
list[j-1]=list[j];
(*pn)--;
return(0);
}
删除算法花费的时间，主要在于循环中元素的前移（其它语句花费的时间可以省去），即从删除位置到最后位置的所有元素都要前移一位.但是，删除的位置是不固定的，当删除位置i=0时，全部元素都得移动，需n-1次移动，当i=n-1时，不需移动元素删除运算的平均性能分析与插入运算类似。设在长度为n的表中删除一个元素所需的平均移动次数为EDE(N)。由于删除表中第i个
位置上的元素需要的移动次数为n-i，故
其中，pi表示删除表中第i个位置上元素的概率。在等概率的假设下，
这时
也就是说用数组实现表时，在表中做删除运算，平均要移动表中约一半的元素，因而删除运算所需的平均时间为O(n)。