第二章 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
2.1 线性表的逻辑结构
线性表 (Linear List),由 n(n≧ 0)个数据元素 (结点 )a1，
a2,…a n组成的有限序列。其中数据元素的个数 n定义为表的长度。当 n=0时称为空表，常常将非空的线性表 (n>0)记作：
(a1,a2,…a n)
数据元素之间的关系是：
ai-1领先于 ai,ai领先于 ai+1。
称 ai-1是 ai的直接 前驱 元素； ai+1是 ai的直接 后继 元素。
除 a1外，每个元素有且仅有一个直接前驱元素，
除 an外，每个元素有且仅有一个直接后继元素。
线性表中数据元素的个数 n(n>=0)称为线性表的 长度,
当 n=0时，称为 空表 。
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。
例 1,26个英文字母组成的字母表
（ A,B,C,…,Z）
例 2、某校从 1978年到 1983年各种型号的计算机拥有量的变化情况。
（ 6,17,28,50,92,188）
例 3、一副扑克的点数
（ 2,3,4,…,J,Q,K,A）
例 4、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
从以上例子可看出线性表的逻辑特征是：
在非空的线性表，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；
有且仅有一个终端结点 an，它没有直接后继，
而仅有一个直接前趋 a n-1；
其余的内部结点 ai(2≦ i≦ n-1)都有且仅有一个直接前趋 a i-1和一个直接后继 a i+1。
线性表是一种典型的线性结构。
数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。
抽象数据类型的定义为,P19
算法 2.1
例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A和 B，
现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb) {
La_len=listlength(La);
Lb_len=listlength(Lb);
for(I=1;I<=lb_len;I++)
{
getelem(lb,I,e);
if (!locateelem(la,e,equal)) listinsert(la,++la_en,e)
}
}
算法 2.2
例 2-2 巳知线性表 LA和线性表 LB中的数据元素按值非递减有序排列，现要求将
LA和 LB归并为一个新的线性表 LC，且 LC
中的元素仍按值非递减有序排列。
此问题的算法如下：
void mergelist(list la,list lb,list &lc)
{ initlist(lc);
I=j=1;k=0;
la_len=listlength(la);
lb_len=listlength(lb);
while((I<=la_len)&&(j<=lb_len))
{ getelem(la,I,ai);
getelem(lb,j,bj);
if(ai<=bj)
{listinsert(lc,++k,ai);++I;}
else
{listinsert(lc,++k,bj);++j;}
}
while(I<=la_len)
{ getelem((la,I++,ai);
listinsert(lc,++k,ai); }
while(j<=lb_len)
{
getelem((lb,j++,bj);
listinsert(lc,++k,bi);
}
}
2.2 线性表的顺序存储结构
2.2.1 线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，
并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置
LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l
由于 C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。
又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。
# define ListSize 100
typedef int DataType;
typedef struct{
DataType data[ListSize];
int length;
} Sqlist;
2.2.2 顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第 i个元素的访问。
注意,C语言中的数组下标从,0”开始，
因此，若 L是 Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
以下主要讨论线性表的插入和删除两种运算。
1、插入线性表的插入运算是指在表的第
i(1≦ i≦ n+1)个位置上，插入一个新结点 x，
使长度为 n的线性表
(a1,…a i-1,ai,…,an)
变成长度为 n+1的线性表
(a1,…a i-1,x,ai,…,an)
算法思想：
① 进行合法性检查,1<=i<=n+1；
② 判断线性表是否已满；
③ 将第 n个至第 i个元素逐一后移一个单元；
④ 在第 i个位置处插入新元素；
⑤ 将表的长度加 1。
算法 2.3 在顺序结构的线性表中第 i个 DE之前插入 x
Void InsertList(Sqlist *L,DataType x,int I)
{ int j;
if (I<1 || I>L.length+1)
{ printf(“Position error”); return ERROR }
if (L.length>=ListSize)
{ printf(“overflow”); exit(overflow); }
for (j=L.length-1;j>=I-1;j--)
L.data[j+1]=l.data[j];
L.data[I-1]=x;
L.length++; }
现在分析算法的复杂度。
这里的问题规模是表的长度，设它的值为 n。
该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）
是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。
当 I=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度 O（ 1）；
当 I=1时，结点后移语句将循环执行 n次，需移动表中所有结点，这是最坏情况，其时间复杂度为 O（ n）。
由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表示移动结点的期望值（即移动的平均次数），则在第 i个位置上插入一个结点的移动次数为 n-I+1。故
Eis(n)= pi(n-I+1)
不失一般性，假设在表中任何位置 (1≦ i≦ n+1)
上插入结点的机会是均等的，则
p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
Eis(n)= (n-I+1)/(n+1)=n/2
也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然 Eis(n)中 n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为 O(n)。
2、删除线性表的删除运算是指将表的第
i(1≦ i≦ n)结点删除，使长度为 n的线性表：
(a1,…a i-1,ai,a i+1…,an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…,an)
算法思想：
① 进行合法性检查,I是否满足 1<=I<=n；
② 判线性表是否已空,L.length=0；
③ 将第 I+1至第 n个元素逐一向前移一个位置；
④ 将表的长度减 1。
Void deleteList(Sqlist*L,int I)
{ int j;
if(I<1 || I>L.length)
{ printf(“Position error”); return ERROR }
for(j=i;j<=L.length-1;j++)
l.data[j-1]=L.data[j];
L.length--;}
该算法的时间分析与插入算法相似，结点的移动次数也是由表长 n和位置 i决定。
若 I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；
若 I=1，则前移语句将循环执行 n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
删除算法的平均性能分析与插入算法相似。
在长度为 n的线性表中删除一个结点，令 Ede(n)
表示所需移动结点的平均次数，删除表中第 i个结点的移动次数为 n-i，故
Ede(n)= pi(n-I)
式中,pi表示删除表中第 i个结点的概率。在等
概率的假设下，
p1=p2=p3=…=p n=1/n
由此可得：
Ede(n)= (n-I)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是 O(n)。
3,线性表顺序存储结构的特点
(1),逻辑上相邻的元素，其物理位置也相邻；
(2),可随机存取表中任一元素；
(3),必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构 ；
(4),插入删除时，需移动大量元素，平均移动元素为 n/2。
2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，
但它也使得插入和删除操作会移动大量的结点,为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表 (Linked List)。
2.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位臵上的。因此，链表中结点的逻辑次序和物理次序不一定相同。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位臵）信息，这个信息称为指针 (pointer)或链 (link)。这两部分组成了链表中的结点结构：
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接后继的地址（或位臵）。链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（ Single Linked)。
显然，单链表中每个结点的存储地址是存放在其前趋结点 next域中，而开始结点无前趋，故应设头指针 head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即
null（图示中也可用 ^表示 )。
例 1、线性表,(bat,cat,eat,fat,hat,jat,lat，
mat)
data link
单链表的示意图如下：
……
110
……
130
135
……
160
头指针 head 165
170
……
200
205
……
……
…
……
hat 200
……,……
cat 135
eat 170
…,……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
head
bat cat eat mat ^ …
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head。
用 C语言描述的单链表如下：
Typedef char datatype;
Typedef struct node{
datatype data;
struct node *next;
} listnode;
typedef listnode * linklist;
listnode *p;
linklist head;
注意区分指针变量和结点变量这两个不同的概念。
P为动态变量，它是通过标准函数生成的，即
p=( listnode * ) malloc ( sizeof ( listnode ) );
函数 malloc分配了一个类型为 listnode的结点变量的空间，并将其首地址放入指针变量 p中。一旦
p所指的结点变量不再需要了，又可通过标准函数
free(p)
释放所指的结点变量空间。
指针变量 P 和（其值为结点地址）和结点变量 *P之间的关系。
空表时,head=Null
一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘ \n’
为输入结束标记。动态地建立单链表的常用方法有如下两种：
1、头插法建表该方法从一个空表开始，重复读入数据，
生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，
直到读入结束标志为止。
linklist createlistf(void)
{ char ch; linklist head; listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′) {
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch; p–>next=head; head=p;
ch=getchar( );
}
return (head);
}
listlink createlist(int n)
{ int data; linklist head; listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞,&p–>data);
p–>next=head; head=p;
}
return(head);
}
2,尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。例：
linklist creater( )
{
char ch; linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
while ((ch=getchar( )!=‵ \n′) {
p=(listnode *)malloc(sizeof(listnode));
p–>data=ch;
if (head=NULL) head=p;
else r–>next=p;
r=p; }
if (r!=NULL)
r–>next=NULL;
return(head);
}
说明：
第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位臵上插入，该位臵上的插入操作和链表中其它位臵上的插入操作处理是不一样的，原因是开始结点的位臵是存放在头指针（指针变量）中，而其余结点的位臵是在其前趋结点的指针域中。
算法中的第一个 if语句就是用来对第一个位臵上的插入操作做特殊处理。算法中的第二个 if
语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，
则链表 head是空表，尾指针 r亦为空，结点 *r不存在；否则链表 head非空，最后一个尾结点 *r是终端结点，应将其指针域臵空。
如果我们在链表的开始结点之前附加一个结点，并称它为 头结点,那么会带来以下两个优点：
a、由于开始结点的位臵被存放在头结点的指针域中，所以在链表的第一个位臵上的操作就和在表的其它位臵上的操作一致，无需进行特殊处理；
b、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。
其算法如下：
linklist createlistr1( )
{
char ch;
linklist
head=(linklist)malloc(sizeof(listnode));
listnode *p,*r;
r=head;
While ((ch=getchar( ))!=‵ \n′)
{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p;
}
r–>next=NULL;
return(head);
}
上述算法里动态申请新结点空间时未加错误处理，可作下列处理：
p=(listnode*)malloc(sizeof(listnode));
if (p==NULL)
{
printf(―No space for node can be obtained‖);
return ERROR;
}
以上算法的时间复杂度均为 O(n)。
二、查找运算
1、按序号查找在链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从链表的头指针出发，顺链域 next逐个结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结点，仅当 1<=i<=n时,i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第 0 个结点，其算法如下：
Listnode * getnode(linklist head,int i)
{
int j;
listnode * p;
p=head–>next;j=1;//p=head;j=0;
while(p && j<i) //while(p–>next && j<i)
{ p=p–>next;
j++;
}
if (i==j) return p;
else return NULL;
}
循环条件分析：
p=head–>next;j=1;
while(p && j<i){p=p–>next; j++;}
条件１防止 i>表长，条件２控制取第 i个，并防止了 i<1．
两个条件有６种组合：
1,P=NIL AND j<i 空表且 i>1 或 i>表长 +1，异常，返回 NULL
2,P=NIL AND j=i 空表且 i=1 或 i=表长 +1,异常，返回 NULL
3,P=NIL AND j>i 空表且 i<1,异常，返回 NULL
4,P<>NIL AND j<i 继续循环
5,P<>NIL AND j=i 确定第 i个结点,正常出循环
6,P<>NIL AND j>i i<1,异常，返回 NULL
2、按值查找按值查找是在链表中，查找是否有结点值等于给定值 key的结点，若有的话，
则返回首次找到的其值为 key的结点的存储位置；否则返回 NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值 key作比较。其算法如下：
Listnode *locatenode(linklist head,int key)
{
listnode * p=head–>next;
while( p && p–>data!=key)
p=p–>next;
return p;
}
该算法的执行时间亦与输入实例中的的取值 key有关，其平均时间复杂度的分析类似于按序号查找，也为 O(n)。
三、插入运算插入运算是将值为 x的新结点插入到表的第 i个结点的位置上，即插入到 ai-
1与 ai之间。因此，我们必须首先找到 ai-1
的存储位置 p，然后生成一个数据域为 x
的新结点 *p，并令结点 *p的指针域指向新结点，新结点的指针域指向结点 ai。
从而实现三个结点 ai-1,x和 ai之间的逻辑关系的变化，插入过程如：
设在单链表结点 b和 结点 y（第 i个结点） 之间 插入新结点 x，已知 p为指向结点 b的指针，
q为指向新结点 x的指针。
插入前,插入后：
插入运算可以由定位和修改指针来完成：
定位：得到指向 y的前驱的指针 p；
修改指针,q –> next＝ p –> next；
p –> next=q； {顺序不可换 }
b yp
xq
b
x
y
q
p
具体算法如下：
void insertnode(linklist head,datetype x,int i)
{
listnode * p,*q;
p=getnode(head,i-1);
if (p==NULL)
printf(〝 position error〞 );
q=(listnode *)malloc(sizeof(listnode));
q–>data=x;
q–>next=p–next;
p–>next=q;
}
设链表的长度为 n，合法的插入位置是 1≦i≦n+1 。
注意当 i=1时,getnode找到的是头结点，当
i=n+1时,getnode找到的是结点 an。因此，用 i-1做实参调用 getnode时可完成插入位置的合法性检查。
算法的时间主要耗费在查找操作 getnode上，故时间复杂度亦为 O(n)。
四、删除运算删除运算是将表的第 i个结点删去。因为在单链表中结点 ai的存储地址是在其直接前趋结点 a i-1的指针域 next中，所以我们必须首先找到
a i-1的存储位置 p。然后令 p–>next指向 ai的直接后继结点，即把 ai从链上摘下。最后释放结点 ai的空间，将其归还给,存储池,。此过程为：
删除前删除后删除运算可以由定位和修改指针来完成：
定位：得到指向 第 i个元素 的前驱的指针 p；
修改指针：
p –> next＝ p –> next –> next ；
p
p
具体算法如下,
void deletelist(linklist head,int i)
{
listnode * p,*r;
p=getnode(head,i-1);
if(p= =NULL || p–>next= =NULL)
return ERROR;
r=p–>next;
p–>next=r–>next;
free( r ) ;
}
设单链表的长度为 n，则删去第 i个结点仅当 1≦i≦n 时是合法的。注意，当 i=n+1时，
虽然被删结点不存在，但其前趋结点却存在，
它是终端结点。因此被删结点的直接前趋 *p
存在并不意味着被删结点就一定存在，仅当
*p存在（即 p!=NULL）且 *p不是终端结点
（即 p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是 O(n)。
从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。
五,线性表链式存储结构的特点
(1),逻辑上相邻的元素，其物理位置不一定相邻；元素之间的邻接关系由指针域指示。
(2),链表是非随机存取存储结构；对链表的存取必须从头指针开始。
(3),链表是一种动态存储结构； 链表的结点可调用 malloc()申请 和 free()释放。
(4),插入删除运算非常方便；只需修改相应指针值 。
2.3.2 循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活 。
单循环链表：在单链表中，将终端结点的指针域 NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。
为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：
a1 an….head
⑴ 非空表
⑵ 空表在用头指针表示的单链表中，找开始结点 a1
的时间是 O(1)，然而要找到终端结点 an，则需从头指针开始遍历整个链表，其时间是 O(n)
在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便,如果改用尾指针
rear来表示单循环链表，则查找开始结点 a1
和终端结点 an都很方便，它们的存储位置分别是 (rear–>next) —>next和 rear，显然，
查找时间都是 O(1)。因此，实际中多采用尾指针表示单循环链表。
由于循环链表中没有 NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p或 p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。
例、在链表上实现将两个线性表 (a1,a2，
a3,… an)和 (b1,b2,b3,… bn)链接成一个线性表的运算。
linklist connect(linklist heada,linklist headb)
{
linklist p=heada—>next;
heada—>next=(headb—next)—>next
free(headb—>next);
headb—>next=p;
return(headb);
}
2.3.3 双链表双向链表 (Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域
prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：
typedef struct dlistnode{
datatype data;
struc dlistnode *prior,*next;
}dlistnode;
typedef dlistnode * dlinklist;
dlinklist head;
和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。
设指针 p指向某一结点，则双向链表结构的对称性可用下式描述：
(p—>prior)—>next=p=(p—>next)—>prior
即结点 *p的存储位置既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放 在它的后继结点 *(p—>next)的直接前趋指针域中。
双向链表的前插操作算法如下：
void dinsertbefor(dlistnode *p,datatype x)
{
dlistnode *q=malloc(sizeof(dlistnode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
}
双向链表的删除操作算法如下：
void ddeletenode(dlistnode *p)
{
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
}
注意：与单链表的插入和删除操作不同的是，
在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为 O(1)。
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
2.1 线性表的逻辑结构
线性表 (Linear List),由 n(n≧ 0)个数据元素 (结点 )a1，
a2,…a n组成的有限序列。其中数据元素的个数 n定义为表的长度。当 n=0时称为空表，常常将非空的线性表 (n>0)记作：
(a1,a2,…a n)
数据元素之间的关系是：
ai-1领先于 ai,ai领先于 ai+1。
称 ai-1是 ai的直接 前驱 元素； ai+1是 ai的直接 后继 元素。
除 a1外，每个元素有且仅有一个直接前驱元素，
除 an外，每个元素有且仅有一个直接后继元素。
线性表中数据元素的个数 n(n>=0)称为线性表的 长度,
当 n=0时，称为 空表 。
这里的数据元素 ai(1≦ i≦ n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。
例 1,26个英文字母组成的字母表
（ A,B,C,…,Z）
例 2、某校从 1978年到 1983年各种型号的计算机拥有量的变化情况。
（ 6,17,28,50,92,188）
例 3、一副扑克的点数
（ 2,3,4,…,J,Q,K,A）
例 4、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
从以上例子可看出线性表的逻辑特征是：
在非空的线性表，有且仅有一个开始结点 a1，
它没有直接前趋，而仅有一个直接后继 a2；
有且仅有一个终端结点 an，它没有直接后继，
而仅有一个直接前趋 a n-1；
其余的内部结点 ai(2≦ i≦ n-1)都有且仅有一个直接前趋 a i-1和一个直接后继 a i+1。
线性表是一种典型的线性结构。
数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。
抽象数据类型的定义为,P19
算法 2.1
例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A和 B，
现要求一个新的集合 A=A∪ B。
void union(List &La,List Lb) {
La_len=listlength(La);
Lb_len=listlength(Lb);
for(I=1;I<=lb_len;I++)
{
getelem(lb,I,e);
if (!locateelem(la,e,equal)) listinsert(la,++la_en,e)
}
}
算法 2.2
例 2-2 巳知线性表 LA和线性表 LB中的数据元素按值非递减有序排列，现要求将
LA和 LB归并为一个新的线性表 LC，且 LC
中的元素仍按值非递减有序排列。
此问题的算法如下：
void mergelist(list la,list lb,list &lc)
{ initlist(lc);
I=j=1;k=0;
la_len=listlength(la);
lb_len=listlength(lb);
while((I<=la_len)&&(j<=lb_len))
{ getelem(la,I,ai);
getelem(lb,j,bj);
if(ai<=bj)
{listinsert(lc,++k,ai);++I;}
else
{listinsert(lc,++k,bj);++j;}
}
while(I<=la_len)
{ getelem((la,I++,ai);
listinsert(lc,++k,ai); }
while(j<=lb_len)
{
getelem((lb,j++,bj);
listinsert(lc,++k,bi);
}
}
2.2 线性表的顺序存储结构
2.2.1 线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
假设线性表的每个元素需占用 l个存储单元，
并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置
LOC(a i )之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第 i个数据元素 ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l
由于 C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。
又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。
# define ListSize 100
typedef int DataType;
typedef struct{
DataType data[ListSize];
int length;
} Sqlist;
2.2.2 顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第 i个元素的访问。
注意,C语言中的数组下标从,0”开始，
因此，若 L是 Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
以下主要讨论线性表的插入和删除两种运算。
1、插入线性表的插入运算是指在表的第
i(1≦ i≦ n+1)个位置上，插入一个新结点 x，
使长度为 n的线性表
(a1,…a i-1,ai,…,an)
变成长度为 n+1的线性表
(a1,…a i-1,x,ai,…,an)
算法思想：
① 进行合法性检查,1<=i<=n+1；
② 判断线性表是否已满；
③ 将第 n个至第 i个元素逐一后移一个单元；
④ 在第 i个位置处插入新元素；
⑤ 将表的长度加 1。
算法 2.3 在顺序结构的线性表中第 i个 DE之前插入 x
Void InsertList(Sqlist *L,DataType x,int I)
{ int j;
if (I<1 || I>L.length+1)
{ printf(“Position error”); return ERROR }
if (L.length>=ListSize)
{ printf(“overflow”); exit(overflow); }
for (j=L.length-1;j>=I-1;j--)
L.data[j+1]=l.data[j];
L.data[I-1]=x;
L.length++; }
现在分析算法的复杂度。
这里的问题规模是表的长度，设它的值为 n。
该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）
是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。
当 I=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度 O（ 1）；
当 I=1时，结点后移语句将循环执行 n次，需移动表中所有结点，这是最坏情况，其时间复杂度为 O（ n）。
由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表示移动结点的期望值（即移动的平均次数），则在第 i个位置上插入一个结点的移动次数为 n-I+1。故
Eis(n)= pi(n-I+1)
不失一般性，假设在表中任何位置 (1≦ i≦ n+1)
上插入结点的机会是均等的，则
p1=p2=p3=…=p n+1=1/(n+1)
因此，在等概率插入的情况下，
Eis(n)= (n-I+1)/(n+1)=n/2
也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然 Eis(n)中 n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为 O(n)。
2、删除线性表的删除运算是指将表的第
i(1≦ i≦ n)结点删除，使长度为 n的线性表：
(a1,…a i-1,ai,a i+1…,an)
变成长度为 n-1的线性表
(a1,…a i-1,a i+1,…,an)
算法思想：
① 进行合法性检查,I是否满足 1<=I<=n；
② 判线性表是否已空,L.length=0；
③ 将第 I+1至第 n个元素逐一向前移一个位置；
④ 将表的长度减 1。
Void deleteList(Sqlist*L,int I)
{ int j;
if(I<1 || I>L.length)
{ printf(“Position error”); return ERROR }
for(j=i;j<=L.length-1;j++)
l.data[j-1]=L.data[j];
L.length--;}
该算法的时间分析与插入算法相似，结点的移动次数也是由表长 n和位置 i决定。
若 I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；
若 I=1，则前移语句将循环执行 n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为 O(1)和 O(n)。
删除算法的平均性能分析与插入算法相似。
在长度为 n的线性表中删除一个结点，令 Ede(n)
表示所需移动结点的平均次数，删除表中第 i个结点的移动次数为 n-i，故
Ede(n)= pi(n-I)
式中,pi表示删除表中第 i个结点的概率。在等
概率的假设下，
p1=p2=p3=…=p n=1/n
由此可得：
Ede(n)= (n-I)/n=(n-1)/2
即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是 O(n)。
3,线性表顺序存储结构的特点
(1),逻辑上相邻的元素，其物理位置也相邻；
(2),可随机存取表中任一元素；
(3),必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构 ；
(4),插入删除时，需移动大量元素，平均移动元素为 n/2。
2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，
但它也使得插入和删除操作会移动大量的结点,为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表 (Linked List)。
2.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位臵上的。因此，链表中结点的逻辑次序和物理次序不一定相同。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位臵）信息，这个信息称为指针 (pointer)或链 (link)。这两部分组成了链表中的结点结构：
其中,data域是数据域，用来存放结点的值。
next是指针域（亦称链域），用来存放结点的直接后继的地址（或位臵）。链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（ Single Linked)。
显然，单链表中每个结点的存储地址是存放在其前趋结点 next域中，而开始结点无前趋，故应设头指针 head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即
null（图示中也可用 ^表示 )。
例 1、线性表,(bat,cat,eat,fat,hat,jat,lat，
mat)
data link
单链表的示意图如下：
……
110
……
130
135
……
160
头指针 head 165
170
……
200
205
……
……
…
……
hat 200
……,……
cat 135
eat 170
…,……
mat Null
bat 130
fat 110
…… ……
jat 205
lat 160
…… ……
165
head
bat cat eat mat ^ …
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
例如：若头指针名是 head，则把链表称为表 head。
用 C语言描述的单链表如下：
Typedef char datatype;
Typedef struct node{
datatype data;
struct node *next;
} listnode;
typedef listnode * linklist;
listnode *p;
linklist head;
注意区分指针变量和结点变量这两个不同的概念。
P为动态变量，它是通过标准函数生成的，即
p=( listnode * ) malloc ( sizeof ( listnode ) );
函数 malloc分配了一个类型为 listnode的结点变量的空间，并将其首地址放入指针变量 p中。一旦
p所指的结点变量不再需要了，又可通过标准函数
free(p)
释放所指的结点变量空间。
指针变量 P 和（其值为结点地址）和结点变量 *P之间的关系。
空表时,head=Null
一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘ \n’
为输入结束标记。动态地建立单链表的常用方法有如下两种：
1、头插法建表该方法从一个空表开始，重复读入数据，
生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，
直到读入结束标志为止。
linklist createlistf(void)
{ char ch; linklist head; listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′) {
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch; p–>next=head; head=p;
ch=getchar( );
}
return (head);
}
listlink createlist(int n)
{ int data; linklist head; listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞,&p–>data);
p–>next=head; head=p;
}
return(head);
}
2,尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。例：
linklist creater( )
{
char ch; linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
while ((ch=getchar( )!=‵ \n′) {
p=(listnode *)malloc(sizeof(listnode));
p–>data=ch;
if (head=NULL) head=p;
else r–>next=p;
r=p; }
if (r!=NULL)
r–>next=NULL;
return(head);
}
说明：
第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位臵上插入，该位臵上的插入操作和链表中其它位臵上的插入操作处理是不一样的，原因是开始结点的位臵是存放在头指针（指针变量）中，而其余结点的位臵是在其前趋结点的指针域中。
算法中的第一个 if语句就是用来对第一个位臵上的插入操作做特殊处理。算法中的第二个 if
语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，
则链表 head是空表，尾指针 r亦为空，结点 *r不存在；否则链表 head非空，最后一个尾结点 *r是终端结点，应将其指针域臵空。
如果我们在链表的开始结点之前附加一个结点，并称它为 头结点,那么会带来以下两个优点：
a、由于开始结点的位臵被存放在头结点的指针域中，所以在链表的第一个位臵上的操作就和在表的其它位臵上的操作一致，无需进行特殊处理；
b、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。
其算法如下：
linklist createlistr1( )
{
char ch;
linklist
head=(linklist)malloc(sizeof(listnode));
listnode *p,*r;
r=head;
While ((ch=getchar( ))!=‵ \n′)
{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p;
}
r–>next=NULL;
return(head);
}
上述算法里动态申请新结点空间时未加错误处理，可作下列处理：
p=(listnode*)malloc(sizeof(listnode));
if (p==NULL)
{
printf(―No space for node can be obtained‖);
return ERROR;
}
以上算法的时间复杂度均为 O(n)。
二、查找运算
1、按序号查找在链表中，即使知道被访问结点的序号 i，
也不能象顺序表中那样直接按序号 i访问结点，
而只能从链表的头指针出发，顺链域 next逐个结点往下搜索，直到搜索到第 i个结点为止。
因此，链表不是随机存取结构。
设单链表的长度为 n，要查找表中第 i个结点，仅当 1<=i<=n时,i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第 0 个结点，其算法如下：
Listnode * getnode(linklist head,int i)
{
int j;
listnode * p;
p=head–>next;j=1;//p=head;j=0;
while(p && j<i) //while(p–>next && j<i)
{ p=p–>next;
j++;
}
if (i==j) return p;
else return NULL;
}
循环条件分析：
p=head–>next;j=1;
while(p && j<i){p=p–>next; j++;}
条件１防止 i>表长，条件２控制取第 i个，并防止了 i<1．
两个条件有６种组合：
1,P=NIL AND j<i 空表且 i>1 或 i>表长 +1，异常，返回 NULL
2,P=NIL AND j=i 空表且 i=1 或 i=表长 +1,异常，返回 NULL
3,P=NIL AND j>i 空表且 i<1,异常，返回 NULL
4,P<>NIL AND j<i 继续循环
5,P<>NIL AND j=i 确定第 i个结点,正常出循环
6,P<>NIL AND j>i i<1,异常，返回 NULL
2、按值查找按值查找是在链表中，查找是否有结点值等于给定值 key的结点，若有的话，
则返回首次找到的其值为 key的结点的存储位置；否则返回 NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值 key作比较。其算法如下：
Listnode *locatenode(linklist head,int key)
{
listnode * p=head–>next;
while( p && p–>data!=key)
p=p–>next;
return p;
}
该算法的执行时间亦与输入实例中的的取值 key有关，其平均时间复杂度的分析类似于按序号查找，也为 O(n)。
三、插入运算插入运算是将值为 x的新结点插入到表的第 i个结点的位置上，即插入到 ai-
1与 ai之间。因此，我们必须首先找到 ai-1
的存储位置 p，然后生成一个数据域为 x
的新结点 *p，并令结点 *p的指针域指向新结点，新结点的指针域指向结点 ai。
从而实现三个结点 ai-1,x和 ai之间的逻辑关系的变化，插入过程如：
设在单链表结点 b和 结点 y（第 i个结点） 之间 插入新结点 x，已知 p为指向结点 b的指针，
q为指向新结点 x的指针。
插入前,插入后：
插入运算可以由定位和修改指针来完成：
定位：得到指向 y的前驱的指针 p；
修改指针,q –> next＝ p –> next；
p –> next=q； {顺序不可换 }
b yp
xq
b
x
y
q
p
具体算法如下：
void insertnode(linklist head,datetype x,int i)
{
listnode * p,*q;
p=getnode(head,i-1);
if (p==NULL)
printf(〝 position error〞 );
q=(listnode *)malloc(sizeof(listnode));
q–>data=x;
q–>next=p–next;
p–>next=q;
}
设链表的长度为 n，合法的插入位置是 1≦i≦n+1 。
注意当 i=1时,getnode找到的是头结点，当
i=n+1时,getnode找到的是结点 an。因此，用 i-1做实参调用 getnode时可完成插入位置的合法性检查。
算法的时间主要耗费在查找操作 getnode上，故时间复杂度亦为 O(n)。
四、删除运算删除运算是将表的第 i个结点删去。因为在单链表中结点 ai的存储地址是在其直接前趋结点 a i-1的指针域 next中，所以我们必须首先找到
a i-1的存储位置 p。然后令 p–>next指向 ai的直接后继结点，即把 ai从链上摘下。最后释放结点 ai的空间，将其归还给,存储池,。此过程为：
删除前删除后删除运算可以由定位和修改指针来完成：
定位：得到指向 第 i个元素 的前驱的指针 p；
修改指针：
p –> next＝ p –> next –> next ；
p
p
具体算法如下,
void deletelist(linklist head,int i)
{
listnode * p,*r;
p=getnode(head,i-1);
if(p= =NULL || p–>next= =NULL)
return ERROR;
r=p–>next;
p–>next=r–>next;
free( r ) ;
}
设单链表的长度为 n，则删去第 i个结点仅当 1≦i≦n 时是合法的。注意，当 i=n+1时，
虽然被删结点不存在，但其前趋结点却存在，
它是终端结点。因此被删结点的直接前趋 *p
存在并不意味着被删结点就一定存在，仅当
*p存在（即 p!=NULL）且 *p不是终端结点
（即 p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是 O(n)。
从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。
五,线性表链式存储结构的特点
(1),逻辑上相邻的元素，其物理位置不一定相邻；元素之间的邻接关系由指针域指示。
(2),链表是非随机存取存储结构；对链表的存取必须从头指针开始。
(3),链表是一种动态存储结构； 链表的结点可调用 malloc()申请 和 free()释放。
(4),插入删除运算非常方便；只需修改相应指针值 。
2.3.2 循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活 。
单循环链表：在单链表中，将终端结点的指针域 NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。
为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：
a1 an….head
⑴ 非空表
⑵ 空表在用头指针表示的单链表中，找开始结点 a1
的时间是 O(1)，然而要找到终端结点 an，则需从头指针开始遍历整个链表，其时间是 O(n)
在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便,如果改用尾指针
rear来表示单循环链表，则查找开始结点 a1
和终端结点 an都很方便，它们的存储位置分别是 (rear–>next) —>next和 rear，显然，
查找时间都是 O(1)。因此，实际中多采用尾指针表示单循环链表。
由于循环链表中没有 NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p或 p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。
例、在链表上实现将两个线性表 (a1,a2，
a3,… an)和 (b1,b2,b3,… bn)链接成一个线性表的运算。
linklist connect(linklist heada,linklist headb)
{
linklist p=heada—>next;
heada—>next=(headb—next)—>next
free(headb—>next);
headb—>next=p;
return(headb);
}
2.3.3 双链表双向链表 (Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域
prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：
typedef struct dlistnode{
datatype data;
struc dlistnode *prior,*next;
}dlistnode;
typedef dlistnode * dlinklist;
dlinklist head;
和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。
设指针 p指向某一结点，则双向链表结构的对称性可用下式描述：
(p—>prior)—>next=p=(p—>next)—>prior
即结点 *p的存储位置既存放在其前趋结点
*(p—>prior)的直接后继指针域中，也存放 在它的后继结点 *(p—>next)的直接前趋指针域中。
双向链表的前插操作算法如下：
void dinsertbefor(dlistnode *p,datatype x)
{
dlistnode *q=malloc(sizeof(dlistnode));
q—>data=x;
q—>prior=p—>prior;
q—>next=p;
p—>prior—>next=q;
p—>prior=q;
}
双向链表的删除操作算法如下：
void ddeletenode(dlistnode *p)
{
p–>prior–>next=p–>next;
p–>next–>prior=p–>prior;
free(p);
}
注意：与单链表的插入和删除操作不同的是，
在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为 O(1)。
