第 3章 线性表线性表及逻辑结构线性表的顺序存储线性表的链式存储链式存储结构的应用线性表及逻辑结构线性表,由 n(n>0)个性质相同的数据元素组成的有限序列。
线性表的长度即为线性表中元素的个数 n(?0)，当
n＝ 0时，称该线性表为空表。
线性表举例：
英文字母表就是一个线性表：
(A,B,C,〃〃〃〃〃〃,Z)
我国的省、市、自治区，可以组成一个线性表：
(北京,天津,上海,〃〃〃〃〃〃,宁夏,台湾）
线性表的有关概念位序,在一个非空表 (a1,a2,…,ai,…,an-1,an)
中的每个数据元素都有一个确定的位置，如 a1是第一个数据元素,an是最后一个数据元素,ai是第 i个数据元素，称 i为数据元素 ai在线性表中的位序。
前驱 /后继元素,若将线性表记为,(a1,...,ai-1,
ai,ai+1,...,an )，则表中 ai-1先于 ai,ai先于 ai+1，
就称 ai-1是 ai的直接前驱元素,ai+1是 ai的直接后继元素。
注意：
除第一个元素 a1元素以外，每一个数据元素有且仅有一个前趋元素。
除最后一个元素以外，每个数据元素有且仅有一个后继元素。
有关线性表的运算初始化,创建一个空的线性表 L。
计数,求线性表 L的长度。
存取,存取第 i个数据元素。
插入,在第 i个数据元素之前，插入一个新的数据元素；或在第 i个元素后，插入一个新的数据元素。
删除,删去第 i个数据元素。
归并,把两个或两个以上的线性表合并在一起，形成一个新的线性表。
分拆,把一个线性表拆成两个或多个线性表。
查找,按某个特定的值查找线性表中的某个元素。
排序,对线性表中的某个元素按某个数据项的值递增
（或递减）的顺序进行重新排序。
根据实例给出线性表归并的算法实例 3-1,已知线性表 LA和 LB中的数据元素按值非递减有序排列，现要求将 LA和 LB归并为一个新的线性表
LC←LA∪LB,且 LC中的数据元素仍按值非递减有序排列。
设
LA＝（ 1,5,7,15）
LB＝（ 3,6,8,9,13,15,17）
则
LC＝（ 1,3,5,6,7,8,9,13,15,15,17）
设 LC为空表。
将 LA或 LB中的元素逐个插入到 LC中即可。
具体方法,为使 LC中元素按值非递减有序排列，可设两个指针 i和 j分别指向 LA和 LB中某个元素，若设 i当前所指的元素为 a,j当前所指的元素为 b，则当前应插入到 LC中的元素 c为：
算法的时间复杂度为：
O(ListLength(La)+ListLength(Lb))
算法思想：
归并算法
Void MergeList（ List *La,List *Lb,List *LC）
{
InitList（ Lc）； /*构造一个空的线性表 Lc*/
i=j=1； k=0； /*指针 i和 j初始值为 1*/
La_len=ListLength（ La）；
Lb_len=ListLength（ Lb）；
while（（ i<=La_len）＆＆（ j＜ =Lb_1en）
{ /* La和 Lb均非空 */
GetElem（ La,i,ai）；
GetElem（ Lb,j,bj）；
if （ ai ＜ bj）
{
Listlnsert（ Lc,++k,ai）；
++i；
} /*将 La中的元素插入到表 Lc中 */
else
if (ai = bj )
{ Listlnsert（ Lc,++k,bj）； ++i； ++j;}
else
{ Listlnsert（ Lc,++k,bj）； ++j;}
}
While（ i <＝ La_len）
{
/*如果表 La没有取完，则将表 La中的所剩元素插入到表 lc中 */
GetElem（ La,i++,ai）；
Listlnsert（ Lc,++k,ai）；
}
While（ j＜＝ Lb_len）
{
GetElem（ Lb,j++,bj）；
Listlnsert（ Lc,++k,bj）；
}
}/*MergeList*/
实例 3-2,利用线性表的基本运算来实现清除线性表 LA
中多余的重复结点，生成一个新的表 LB。如有表
LA=(2,3,4,3,5,6,7,4,8,9)
存在多余的重复结点，则
LB=(2,3,4,5,6,7,8,9)
利用算法实现。
算法思想,从表 LA的第一个结点 i=1开始，逐个检查结点 i以后的位置为 k的任一元素，若两点相同，则从表 LA
中将位置 k上数据元素删除掉，当遍历了 i后面的所有元素后,i就成为表 LA中无重复的结点，然后将 i向后移动一个位置。重复上述过程，直到 i移到表 LA的最后一个元素为止。
算法的时间复杂度,(n-1)+(n-2)+(n-3)+…..+1,即算法实现,
PURGE（ LA） /*清除线性表中重复出现的多余结点 */
List *LA;
{
int i=1,k,x,y;
int L=lenth(LA);
while(i<L)
{
x=get(LA,i);/*取当前第 i个结点 */
k=i+1;
while(k<=L)
{
y=get(LA,k);/*取当前第 k个结点 */
if(x==y)
{
Delete(LA,k);/*删除 */
L--;
}
Else k++;
}
i++;
}
}/*PURGE*/
线性表的顺序存储线性表的顺序存储,把线性表的各个数据元素依次存储在一组地址连续的存储单元里 ；用这种方法存储的线性表简称为顺序表。
数据元素的存储位置：
第 i＋ 1个数据元素的存储位置 LOC（ ai+1）和第 i
个数据元素的存储位置 LOC（ ai）之间的关系：
LOC（ ai+1）＝ LOC（ ai） +m。
线性表的第 i个数据元素 ai的存储位置为：
LOC（ ai）＝ LOC（ a1） +(i-1)*m。
顺序表的特点,表中相邻的元素 ai 和 ai+1 赋以相邻的存储位置。
C语言中用一维数组表示顺序表
typedef int datatype； /*定义 datatype类型为 int*/
#define List_MaxSize 100 /*顺序表的最大长度 */
typedef struct{
datatype data[list_maxsize]; /*将线性表定义为一个数组 */
Int length; /*线性表当前的大小 */
}SqList;
顺序结构线性表的运算表的初始化：
void InitList（ SqList *L）
{\\顺序表的初始化即将表的长度设为 0
L.Length=0；
}
求表长：
int ListLength（ SqList *L）
{ \\求表长只需返回 L.Length
return L.Length;
}
取表中第 i个结点：
datatype GetNode（ L,i）
{\\取表中第 i个结点只需返回 L.data[i-1]即可
if (i<1||i> L.Length-1)
Error("position error")；
return L.data[i-1]； }
顺序表的结点查询操作,
Int search( int x,sqlist *L,int n )
{/*在表长为 n 的顺序表中查找结点 x在表中的位置 */
int i;
for(i=0;i<n;i++)
if(x==L.s[i]) break; /*查询到跳出循环 */
return(i+1); /*返回查询结果 */
if(i==n) return(0); }
顺序表的结点插入操作,在线性表的第 i-1个数据元素和第 i个数据元素之间插入一个新的数据元素，就是要使长度为 n的线性表 变成长度为
n+1的线性表 。
例：
顺序表的结点删除操作删除操作,使长度为 n的线性表
（ a1,…,ai-1,ai,,ai+1,…,an ）
变成长度为 n-1的线性表
（ a1,…,ai-1,ai+1,…,an ）
图示：
顺序存储结构的特点优点：
无须为表示结点间的逻辑关系而增加额外的存储空间。
可以方便地随机存取表中的任一结点。
缺点：
要占用连续的存储空间，并需要静态分配 。
在插入操作和删除操作时需要移动大量数据 。
线性表的链式存储线性表的链式存储结构,用一组任意的存储单元来存储线性表的数据元素。
结点结构：
数据域,存储数据元素信息的域。
指针域,存放直接后继结点或前驱结点地址的域。
图示：
单链表图示：
实例：
结点存储结构：
typedef struct Lnode
{/*线性表的单链表存储结构 */
Datatype data;
Struct Lnode * next;
}LinkList;
带头结点的单链表示意图：
带头结点单链表初始化算法
Initlist（ LinkList *L）
{
L = (LinkList*)malloc(sizeof(LNode));
L->next = NULL;
}
建立单链表的算法
Create_L（ LinkList *L,int n）
{
LinkList*p;int i;
initlist（ LinkList *L） /*建立一个带头结点的单链表 */
for(i = n;i>0;--i)
{
p = (LinkList*)malloc(sizeof(LNode)); /*生成新结点 */
scanf(&p->data); /*输入元素值 */
p->next =L->next;
L->next = p; /*插入到表头 */
} }/* Create_L */
线性链表的运算单链表的查找操作单链表的插入操作单链表的删除操作单链表的查找操作单链表的查找操作算法
VisitElem_L(LinkList *L,int i,Datatype &e )
{
LinkList *p,int j;
p = L->next； j=1；
While（ p！ =null ＆＆ j<i ）
{/*顺指针向后查找，直到 p指向第 i个元素或 p为空 */
p=p->next;
++j;
}
if（ p=null || j>i ） return ERROR； /*第 i个元素不存在 */
e＝ p-＞ data； /*取第 i个元素 */
return OK;
}/*VisitGetElem_L*/
按值查找链表
ListNode* LocateNode (LinkList head,DataType
key)
{
ListNode *p=head->next;
while(p&&p->data!=key)//直到 p为 NULL或
p->data为 key为止
p=p->next;
return p;
} 返回单链表的插入操作插入位置：
将结点插入在链表的第一个结点位置。
将结点插入在两个结点之间。
将结点插入在链表的最后一个结点。
插入前后指针变化：
单链表的结点前插算法
Insert_Link（ LinkList *L,int i,Datatype e）
{
LinkList*p,*s;
int j;
s = (LinkList*)malloc(sizeof(LNode)); /*生成新结点 */
s->data = e; s->next =null;
p = L ; j = 0;
While(p && j < i-1)
{
p = p->next;
++j;
} /*寻找第 i-1个结点 */
if(!p||j>i-1) return ERROR; /*i小于 1或者大于表长
*/
s->next = p->next; p->next = s;
return OK;
}/*Insert_Link*/
单链表的结点后插算法
Insert_Link（ LinkList *L,int i,Datatype e）
{
LinkList*p,*s;
int j;
p = L ; j = 0;
s = (LinkList*)malloc(sizeof(LNode)); /*生成新结点 */
s->data = e; s->next =null;
While(p && j < i)
{
p = p->next;
++j;
} /*寻找第 i-1个结点 */
if(!p||j>i) return ERROR; /*i小于 1或者大于表长 */
s->next = p->next; /*插入 L中 */
p->next = s;
return OK;
}/*Insert_Linnk*/
删除前后指针变化：
单链表的删除操作单链表删除算法
Delete_Link（ LinkList *L,int i,Datatype ＆ e）
{
Linklist*p,*q;
int j;
p = L; j = 0;
while(p->next && j<i-1)
{/*寻找第 i个结点，并令 p指向其前趋 */
p = p->next;
++j;
}
if(!(p->next)||j>i-1)
return ERROR; /*删除位置不合理 */
q = p->next; p->next = q->next; /*删除结点 */
e = q->data;
free(q); /*释放结点 */
return OK;
}/*Delete_Link*/
实例,逆序带头结点的单链表,使表
（ a1,…,ai-1,ai,,ai+1,…,an ）
转换成为
（ an,…,ai+1,ai,,ai-1,…,a1）
算法：
void InvertLink(LinkList *Head)
{ LinkList *P;
P = Head->Next; /*P指向原表中第一个待逆置的结点 */
Head->Next = NULL; /*逆表 Head初值为空表 */
while (P != NULL) /* 原表中还有未逆置的结点 *P */
{
S = P; P = P->Next;
S->Next = Head->Next;
Head->Next = S /*将 *S 插到逆表 Head的头上 */
}
} /*InvertLink*/
循环链表循环链表,使其最后一个结点的指针指向链表的第一个结点，使链表呈环状，这种形式的线性表叫做循环链表 。
图示：
结点结构描述：
struct Cnode
{
Int data;
struct Cnode *next;
}Clinklist;
循环链表的运算循环链表中查找元素为 e的结点
VisitElem_L(CLinklist *L,Datatype e )
{
Clinklist*p;
p = L->next； /*初始化,P指向第一个结点 */
While（ p->next!=L ＆＆ p->data!=e） p=p->next;
if（ p->next=L ＆＆ p->data!=e） return ERROR；
/*元素 e不存在 */
Return (p);
}/*VisitGetElem_L*/
循环链表的合并操作图示：
两个循环链表的链接算法
CLinkList *Connect（ CLinklist *rearA,CLinklist *rearB）
{
CLinklist *p；
p=rearA->next;
rearA ->next=rearB->next->next; /*rearB表的第一个结点接在 reaA的表尾 */
free(rearB->next);
rearB->next=p;/*将链表 rearB的第一个结点链接到 rearA的最后一个结点之后 */
return rearB;/*返回连接后的循环链表尾指针 */
}/*Connect*/
链式存储结构的特点优点：
结点空间的动态申请和动态释放，克服了顺序存储结构数据元素最大个数需要预先设定的缺点。
链式存储结构中数据元素之间的次序是使用指针来控制的，在插入删除时需要移动大量的数据。
缺点：
每个结点的指针域需要另外加存储空间。
链式存储是一种非随机存储结构，对于任意结点的操作都要首先从开始指针顺链查找该结点，增加了一些操作的算法时间复杂度。
链式存储结构的应用约瑟夫问题问题描述,设有 n个人坐在圆桌周围，从第 s个人开始报数，数到 m的人出列，然后再从下一个人开始报数，数到 m的人又出列,……,如此重复，直到所有的人都出列为止。要求按出列的先后顺序输出每个人的信息。
算法：
typedef struct Lnode
{
Datatype data;
Struct Lnode * next;
}LinkList;
void Joseph（ int n,int s,int m）
{/*约瑟夫问题 */
int I,j；
LinkList *creatlinklist（ int）；
LinkList *h,* p,*q,*r;
if (n<s) return error;
h= creatlinklist（ int）； /*建立一个带头结点的单链表 */
q=h；
for（ I=1； I<s;I++） q=q->next;/*找出 s结点 */
p=q->next;
for(I=1;I<n;I++)
{
for(j=1;j<m;j++) /*报数，找出数 m的结点 */
if(q->next!=null)&& (p->next!=null)
{
q=q->next;
p=p->next;
}
else if (p->next= =null)
{ q=q->next; p=h->next;}
else
{ q=h->next; p=p->next;}
printf(“%c \n”,p ->data);/*一个元素出列 */
r=p；
if （ p->next= =null）
{ p=h->next; q->next=null;}
else
{ p=p->next;
if (q->next!=null) q->next=p;
else h->next=p; }
free(r);
}
printf(“%c \n”,(h ->next)->data);
}