下载掌阅APP，畅读海量书库
立即打开
在了解了线性表的基本概念和逻辑结构之后，接下来就需要将线性表的逻辑结构转化为计算机能识别的存储结构，以便实现线性表的操作。线性表的存储结构主要有顺序存储结构和链式存储结构两种。本节的主要介绍线性表的顺序存储结构及顺序存储结构下的操作实现。
线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。
假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个元素的存储位置LOC（a i+1 ）和第i个元素的存储位置LOC（a i ）之间满足关系LOC（a i+1 ）=LOC（a i ）+m。
线性表中第i个元素的存储位置与第一个元素a 1 的存储位置满足以下关系。
LOC（a i ）=LOC（a 1 ）+（i-1）*m
其中，第一个元素的位置LOC（a 1 ）称为起始地址或基地址。
线性表的这种机内表示称为线性表的顺序存储结构或顺序映像（sequential mapping），通常将这种方法存储的线性表称为 顺序表 。顺序表逻辑上相邻的元素在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数（见图3-2）。只要确定了第一个元素的起始位置，线性表中的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。
图3-2 线性表存储结构
由于C语言的数组具有随机存取特点，因此可采用数组来描述顺序表。顺序表的存储结构描述如下。
#define ListSize 100
typedef struct
{
DataType list[ListSize];
int length;
}SeqList;
其中，DataType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。
如果要定义一个顺序表，代码如下。
SeqList L;
如果要定义一个指向顺序表的指针，代码如下。
SeqList *L;
在顺序存储结构中，线性表的基本运算如下（以下算法的实现保存在文件“SeqList.h”中）。
①初始化线性表。
void InitList(SeqList *L)
/*
初始化线性表*/
{
L->length=0; /*
把线性表的长度置为0*/
}
②判断线性表是否为空。
int ListEmpty(SeqList L)
/*
判断线性表是否为空，线性表为空返回1
，否则返回0*/
{
if(L.length==0) /*
线性表的长度若为0*/
return 1; /*
返回1*/
else /*
否则*/
return 0; /*
返回0*/
}
③按序号查找。先判断序号是否合法，如果合法，把对应位置的元素赋给e，并返回1表示查找成功；否则返回-1表示查找失败。按序号查找的算法实现如下。
int GetElem(SeqList L,int i,DataType *e)
/*
查找线性表中第i
个元素。查找成功将该值返回给e
，并返回1
表示成功；否则返回-1
表示失败。*/
{
if(i<1||i>L.length) /*
在查找第i
个元素之前，判断该序号是否合法*/
return -1;
*e=L.list[i-1]; /*
将第i
个元素的值赋值给e*/
return 1;
}
④按内容查找。从线性表中的第一个元素开始，依次与e比较，如果相等，返回该序号表示成功；否则返回0表示查找失败。按内容查找的算法实现如下。
int LocateElem(SeqList L,DataType e)
/*
查找线性表中元素值为e
的元素*/
{
int i;
for(i=0;i<L.length;i++) /*
从第一个元素开始与e
进行比较*/
if(L.list[i]==e) /*
若存在与e
值相等的元素*/
return i+1; /*
返回该元素在线性表中的序号*/
return 0; /*
否则，返回0*/
}
⑤插入操作。插入操作就是在线性表L中的第i个位置插入新元素e，使线性表{a 1 ，a 2 ，…，a i-1 ，a i ，…，a n }变为{a 1 ，a 2 ，…，a i-1 ，e，a i ，…，a n }，线性表的长度也由n变成n+1。
要在顺序表中的第i个位置上插入元素e，首先将第i个位置以后的元素依次向后移动1个位置，然后把元素e插入第i个位置。移动元素时要从后往前移动元素，先移动最后1个元素，再移动倒数第2个元素，依次类推。
例如，在线性表{9，12，6，15，20，10，4，22}中，要在第5个元素之前插入1个元素28，需要将序号为8、7、6、5的元素依次向后移动1个位置，然后在第5号位置插入元素28，这样，线性表就变成了{9，12，6，15，28，20，10，4，22}，如图3-3所示。
图3-3 在顺序表中插入元素28的过程
插入元素之前要判断插入的位置是否合法，顺序表是否已满，在插入元素后要将表长增加1。插入元素的算法实现如下。
int InsertList(SeqList *L,int i,DataType e)
/*
在顺序表的第i
个位置插入元素e
，插入成功返回1
，如果插入位置不合法返回-1
，顺序表满返回0*/
{
int j;
if(i<1||i>L->length+1) /*
在插入元素前，判断插入位置是否合法*/
{
printf("
插入位置i
不合法！\n");
return -1;
}
else if(L->length>=ListSize) /*
在插入元素前，判断顺序表是否已经满，不能插入元素*/
{
printf("
顺序表已满，不能插入元素。\n");
return 0;
}
else
{
for(j=L->length;j>=i;j--) /*
将第i
个位置以后的元素依次后移*/
L->list[j]=L->list[j-1];
L->list[i-1]=e; /*
插入元素到第i
个位置*/
L->length=L->length+1; /*
将顺序表长增1*/
return 1;
}
}
插入元素的位置i的合法范围应该是1≤i≤L->length+1。当i=1时，插入位置是在第一个元素之前，对应C语言数组中的第0个元素；当i=L->length+1时，插入位置是最后一个元素之后，对应C语言数组中的最后一个元素之后的位置。当插入位置是i=L->length+1时，不需要移动元素；当插入位置是i=0时，则需要移动所有元素。
⑥删除第i个元素。删除第i个元素之后，线性表{a 1 ，a 2 ，…，a i-1 ，a i ，a i+1 ，…，a n }变为{a 1 ，a 2 ，…，a i-1 ，a i+1 ，…，a n }，线性表的长度由n变成n-1。
为了删除第i个元素，需要将第i+1后面的元素依次向前移动一个位置，将前面的元素覆盖。移动元素时要先将第i+1个元素移动到第i个位置，再将第i+2个元素移动到第i+1个位置，依次类推，直到最后一个元素移动到倒数第二个位置。最后将顺序表的长度减1。
例如要删除线性表{9，12，6，15，28，20，10，4，22}的第4个元素，需要依次将序号为5、6、7、8、9的元素向前移动一个位置，并将表长减1，如图3-4所示。
图3-4 删除元素15的过程
在进行删除操作时，先判断顺序表是否为空，若不空，接着判断序号是否合法，若不空且合法，则将要删除的元素赋给e，并把该元素删除，将表长减1。删除第i个元素的算法实现如下。
int DeleteList(SeqList *L,int i,DataType *e)
{
int j;
if(L->length<=0)
{
printf("
顺序表已空不能进行删除!\n");
return 0;
}
else if(i<1||i>L->length)
{
printf("
删除位置不合适!\n");
return -1;
}
else
{
*e=L->list[i-1];
for(j=i;j<=L->length-1;j++)
L->list[j-1]=L->list[j];
L->length=L->length-1;
return 1;
}
}
删除元素的位置i的合法范围应该是1≤i≤L->length。当i=1时，表示要删除第一个元素，对应C语言数组中的第0个元素；当i=L->length时，要删除的是最后一个元素。
⑦求线性表的长度，代码如下。
int ListLength(SeqList L)
{
return L.length;
}
⑧清空顺序表，代码如下。
void ClearList(SeqList *L)
{
L->length=0;
}
在顺序表的实现算法中，除了按内容查找运算、插入和删除操作外，算法的时间复杂度均为O（1）。
在按内容查找的算法中，若要查找的是第一个元素，则仅需要进行一次比较；若要查找的是最后一个元素，则需要比较n次才能找到该元素（设线性表的长度为n）。
设P
i
表示在第i个位置上找到与e相等的元素的概率，若在任何位置上找到元素的概率相等，即P
i
=1/n，则查找元素需要的平均比较次数为
，因此，按内容查找的平均时间复杂度为O（n）。
在顺序表中插入元素时，时间主要耗费在元素的移动上。若插入的位置在第一个位置，则需要移动元素的次数为n次；如果要将元素插入倒数第二个位置，则仅需把最后一个元素向后移动；若要将元素插入最后一个位置，即第n+1个位置，则不需要移动元素。设P
i
表示在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即P
i
=1/（n+1）。则在顺序表的第i个位置插入元素时，需要移动元素的平均次数为
，因此，插入操作的平均时间复杂度为O（n）。
在顺序表的删除算法中，时间主要耗费仍在元素的移动上。如果要删除的是第一个元素，则需要移动元素次数为n-1次；如果要删除的是最后一个元素，则需要移动0次。设P
i
表示删除第i个位置上的元素的概率，假设在任何位置上找到元素的概率相等，即P
i
=1/n。则在顺序表中删除第i个元素时，需要移动元素的平均次数为
，因此，删除操作的平均时间复杂度为O（n）。
线性表的顺序存储结构的优缺点如下。
（1）无须为表示表中元素之间的关系而增加额外的存储空间。
（2）可以快速地存取表中任一位置的元素。
（1）插入和删除操作需要移动大量的元素。
（2）使用前须事先分配好存储空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需要。
在掌握了顺序表的基本操作之后，本小节通过几个具体实例来加强对顺序表的知识点掌握。
【例3-1】
假设线性表LA和LB分别表示两个集合A和B，利用线性表的基本运算实现新的集合
，即扩大线性表LA，将存在于线性表B中且不存在于A中的元素插入A中。
【分析】 只有依次从线性表LB中取出每个数据元素，并依次在线性表LA中查找该元素，如果LA中不存在该元素，则将该元素插入LA中。程序的实现代码如下所示。
#include<stdio.h> /*
包含输入输出头文件*/
#define ListSize 100
typedef int DataType; /*
定义元素类型为整型*/
#include"SeqList.h"
void UnionAB(SeqList *A,SeqList B); /*
将LB
中但不在LA
中的元素插入到LA
中*/
void main()
{
int i,flag;
DataType e;
DataType a[]={2,3,17,20,9,31};
DataType b[]={8,31,5,17,22,9,48,67};
SeqList LA,LB; /*
声明顺序表LA
和LB*/
InitList(&LA); /*
初始化顺序表LA*/
InitList(&LB); /*
初始化顺序表LB*/
for(i=0;i<sizeof(a)/sizeof(a[0]);i++) /*
将数组a
中的元素插入到表LA
中*/
{
if(InsertList(&LA,i+1,a[i])==0)
{
printf("
位置不合法");
return;
}
}
for(i=0;i<sizeof(b)/sizeof(b[0]);i++) /*
将数组a
中的元素插入到表LB
中*/
{
if(InsertList(&LB,i+1,b[i])==0)
{
printf("
位置不合法");
return;
}
}
printf("
顺序表LA
中的元素：\n");
for(i=1;i<=LA.length;i++) /*
输出顺序表LA
中的每个元素*/
{
flag=GetElem(LA,i,&e); /*
返回顺序表LA
中的每个元素到e
中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("
顺序表LB
中的元素：\n");
for(i=1;i<=LB.length;i++) /*
输出顺序表LB
中的每个元素*/
{
flag=GetElem(LB,i,&e); /*
返回顺序表LB
中的每个元素到e
中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("
将LB
中但不在LA
中的元素插入到LA
中：\n");
UnionAB(&LA,LB); /*
将LB
中但不在LA
中的元素插入到LA
中*/
for(i=1;i<=LA.length;i++) /*
输出LA
中所有元素*/
{
flag=GetElem(LA,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
void UnionAB(SeqList *LA,SeqList LB)
/*
删除A
中出现B
的元素的函数实现*/
{
int i,flag,pos;
DataType e;
for(i=1;i<=LB.length;i++)
{
flag=GetElem(LB,i,&e); /*
依次把LB
中每个元素取出赋给e*/
if(flag==1)
{
pos=LocateElem(*LA,e); /*
在LA
中查找和LB
中取出的元素e
相等的元素*/
if(!pos)
InsertList(LA,LA->length+1,e); /*
如果找到该元素，将元素插入到LA
中*/
}
}
}
程序运行结果如图3-5所示。
图3-5 顺序表A∪B程序运行结果
说明 在设计程序时需要用到头文件“SeqList.h”，而在顺序表的类型定义中包含DataType数据类型和顺序表长度，所以在包含#include"SeqList.h"之前首先进行宏定义。宏定义、类型定义和包含文件语句的次序如下。
#define ListSize 100 typedef int DataType; #include"SeqList.h"
【例3-2】 编写一个算法，把一个顺序表分拆成两个部分，使顺序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如顺序表（-12，3，-6，-10，20，-7，9，-20）经过分拆调整后变为（-12，-20，-6，-10，-7，20，9，3）。
【分析】 设置两个指示器i和j，分别扫描顺序表中的元素，i和j分别从顺序表的左端和右端开始扫描。如果i遇到小于等于0的元素，略过不处理，继续向前扫描；如果遇到大于0的元素，暂停扫描。如果j遇到大于0的元素，略过不处理，继续向前扫描；如果遇到小于等于0的元素，暂停扫描。如果i和j都停下来，则交换i和j指向的元素。重复执行直到i≥j为止。
算法描述如下。
void SplitSeqList(SeqList *L)
/*
将顺序表L
分成两个部分：左边是小于等于0
的元素，右边是大于0
的元素*/
{
int i,j; /*
定义两个指示器i
和j*/
DataType e;
i=0,j=(*L).length-1; /*
指示器i
和j
分别指示顺序表的左端和右端元素*/
while(i<j)
{
while(L->list[i]<=0) /*i
遇到小于等于0
的元素*/
i++; /*
略过*/
while(L->list[j]>0) /*j
遇到大于0
的元素*/
j--; /*
略过*/
if(i<j) /*
交换i
和j
指向的元素*/
{
e=L->list[i];
L->list[i]=L->list[j];
L->list[j]=e;
}
}
}
测试程序如下。
#include<stdio.h>
#include"SeqList.h"
void SplitSeqList(SeqList *L);
void main()
{
int i,flag,n;
DataType e;
SeqList L;
int a[]={-12,3,-6,-10,20,-7,9,-20};
InitList(&L); /*
初始化顺序表L*/
n=sizeof(a)/sizeof(a[0]);
for(i=1;i<=n;i++) /*
将数组a
的元素插入到顺序表L
中*/
{
if(InsertList(&L,i,a[i-1])==0)
{
printf("
位置不合法");
return;
}
}
printf("
顺序表L
中的元素：\n");
for(i=1;i<=L.length;i++) /*
输出顺序表L
中的每个元素*/
{
flag=GetElem(L,i,&e); /*
返回顺序表L
中的每个元素到e
中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("
顺序表L
调整后(
左边元素<=0,
右边元素>0):\n");
SplitSeqList(&L); /*
调整顺序表*/
for(i=1;i<=L.length;i++) /*
输出调整后顺序表L
中所有元素*/
{
flag=GetElem(L,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
程序运行结果如图3-6所示。
图3-6 程序运行结果
【例3-3】 试设计一种表示任意长的整数的数据结构，计算任意给定的两个整数之和的算法。
【分析】 C语言提供的整数范围为-2 31 ～2 31 -1，超出这个范围的整数该如何表示呢？可以利用数组来存储，数组中的每一个元素存放一个数字，数组A和B分别存储两个整数，在将两个整数相加时，从低位到高位依次将对应位相加，如果和大于9，则将高位上加上进位1，并将和减去10后存储到当前位。具体实现代码如下。
#include<stdio.h>
#define MaxLen 100
typedef int sqlist[MaxLen];
int input(sqlist A)
{
int i;
for(i=0;i<MaxLen;i++)
A[i]=0;
printf("
输入一个正整数的各位(
输入-1
结束)\n");
i=0;
while(1)
{
scanf("%d",&A[i]);
if(A[i]<0)
break;
i++;
}
return i;
}
void output(sqlist A,int low,int high)
{
int i;
for(i=low;i<high;i++)
printf("%d",A[i]);
printf("\n");
}
void move(sqlist A,int na)
{
int i;
for(i=0;i<na;i++)
A[MaxLen-i-1]=A[na-i-1];
}
int add(sqlist *A,int na,sqlist B,int nb)
{
int nc,i,j,length=0;
if(na>nb)
nc=na;
else
nc=nb;
move(*A,na);
move(B,nb);
for(i=MaxLen-1;i>=MaxLen-nc;i--)
{
j=(*A)[i]+B[i];
if(j>9)/*
和大于9*/
{
(*A)[i-1]=(*A)[i-1]+1; /*
高位加上1*/
(*A)[i]=j-10; /*
和减去10
后存储到当前位*/
}
else
(*A)[i]=j;
if(i==MaxLen-nc)/*
处理最高位*/
{
if(j>9)
{
(*A)[i-1]=1;
length=nc+1;
}
else
length=nc;
}
}
return length;
}
void main()
{
sqlist A,B;
int na,nb,nc;
na=input(A);
nb=input(B);
printf("
整数A:");
output(A,0,na);
printf("
整数B:");
output(B,0,nb);
nc=add(&A,na,B,nb);
printf("
相加后的结果:");
output(A,MaxLen-nc,MaxLen);
}
程序的运行结果如图3-7所示。
图3-7 两个整数相加的程序运行结果
【考研真题】 设将n（n>1）个整数存放到一维数组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即把R中的数据序列由（x 0 ，x 1 ，…，x n-1 ）变换为（x p ，x p+1 ，…，x n-1 ，x 0 ，x 1 ，…，x p-1 ）。要求如下。
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C语言描述算法。
（3）说明所设计算法的时间复杂度和空间复杂度。
【分析】 该题目主要考查对顺序表的掌握情况，具有一定的灵活性。
（1）先将这n个元素序列（x 0 ，x 1 ，…，x p ，x p+1 ，…，x n-1 ）就地逆置，得到（x n-1 ，x n-2 ，…，x p ，x p-1 ，…，x 0 ），然后再将前n-p个元素（x n-1 ，x n-2 ，…，x p ）和后p个元素（x p-1 ，x p-2 ，…，x 0 ）分别就地逆置，得到最终结果（x p ，x p+1 ，…，x n-1 ，x 0 ，x 1 ，…，x p-1 ）。
（2）算法实现，可用Reverse和LeftShift两个函数实现。
void Reverse(int R[],int left,int right)
{
int k=left,j=right,t;
while(k<j)
{
t=R[k];
R[k]=R[j];
R[j]=t;
k++;
j--;
}
}
void LeftShift(int R[],int n,int p)
{
If(p>0 && p<n)
{
Reverse(R,0,n-1); //
将全部元素逆置
Reverse(R,0,n-p-1); //
逆置前n-p
个元素
Reverse(R,n-p,n-1); //
逆置后n
个元素
}
}
（3）上述算法的时间复杂度为O（n），空间复杂度为O（1）。