学步园

2、顺序表的存储结构
顺序表节点类型的定义如下：
#define max 50 //顺序表中最多元素个数
typedef int elemtype;//定义elemtype为int类型
typedef elemtype sqlist[max];

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

精典例题解析
【例1】设计顺序表的基本算法。
【解】 所谓顺序表，是采用一段连续的区域存储数据的线性表。实现本题功能的sq.cpp文件如下：

程序代码

#include"iostrea.h"
#define max 50 //顺序表中最多元素个数
typedef int elemtype;
typedef elemtype sqlist[max];
int create(sqlist A)//创建顺序表
{
int i,n;
cout<<"创建一个顺序表"<<endl;
cout<<" 输入元素个数：";
cin>>n;
for(i=0;i<n;i++)
{
cout<<" 输入第"<<i+1<<"个元素值";
cin>>A[i];
}
return n;
}
void disp(sqlist A,int n)//输出一个顺序表
{
int i;
cout<<"输出一个顺序表"<<endl;
if(n==0)
cout<<"空表";
for(i=0;i<n;i++)
cout<<A[i]<<" ";
cout<<endl;
}
int ins(sqlist A,int n,int i,elemtype x)
//在顺序表的第i个元素前插入一个元素x
//若i=0,则新元素作为第1个元素；若i=n，则插入在最后
{
int j;
if(i<0||i>n)
cout<<"i值下溢或上溢"<<endl;
else
{
for(j=n-1;j>=i;j--)
{
A[j+1]=A[j];//将第i个元素及其后的元素后移
A[i]=x;n++;//顺序表长度增1
}
return n;
}
int del(sqlist A,int n,int i)//在顺序表A中删除第i个元素
{
int j;
if(i<0||i>n)cout<<"i值下溢或上溢"<<endl;
else
{
for(j=i-1;j<n;j++)
A[j]=A[j+1];//将第i个元素之后的元素前移覆盖A[i]
n--;//顺序表长度减1
}
return n;
}
int find(sqlist A,int n,elemtyep x)
//在表中查找元素值为x的元素
{
int i=0;
while(i<=n&&A[i]!=x)
i++;
if(i<n)return 1;
else reutn 0;}

【例2】已知数组A[0..n-1]的元素类型为整型，设计算法调整A，使其左边的所有元素小于0，右边的所有元素大于等于0。
【解】实现本题功能的程序如下：

程序代码

#include"sq.cpp"
void adjust(sqlist A,int n)
{
sqlist B;
int i,x=0;y=n-1;
for(i=0;i<n;i++)
{
if(A[i]<0)
{
B[x]=A[i];x++;
}
else
{
B[y]=A[i];y--;
}
for(i-0;i<n;i++)
A[i]=B[i];
}
void main()
{
sqlist A;
int n;
n=create(A);
disp(A,n);
adjust(A,n);
disp(A,n);
}

【例3】编写一个算法实现两个有序（从小到大)顺序表合并为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）。
【解】两个顺序表A和B的合并过程是从A和B中的最后一个元素逐个向前进行比较，将较大的元素先定位在A中。

程序代码

#include"sq.cpp"
int comb(sqlist A,int na,sqlist B,int nb)
{
int n=na,m=nb;
if(na+nb>max)
return 0;//顺序表上溢
while(nb>0)
if((na==0)||(A[na-1]<B[nb-1])
{
A[na+nb-1]=B[nb-1];//说明A[nb-1]是第na+nb大的元素
nb--;
}
else
{
A[na+nb-1]=A[na-1];//说明A[na-1]是第na+nb大的元素
na--;
}
na=n+m;
return na;
}
void main()
{
sqlist A,B;
int na,nb;
na=create(A);
nb=create(B);
disp(A,na);
disp(B,nb);
na=comb(A,na,B,nb);
disp(A,na);
}

【例4】设有一个顺序表A，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间少再加一个附加的工作单元。
【解】对于有n个元素的A，设k=n/2（即n除2后取整）。将A[0]与A[n-1]交换，A[1]与A[n-2]交换，……，A[k]与A[n-k-1]交换，则将所有元素逆置了。实现功能的程序如下（其中只使用了一个附加的工作单元temp)：

程序代码

#include"sq.cpp"
void inver(sqlist A,int)//逆置
{
int m=n/2,i;//m为长度的一半
elemtype temp;
for(i=0;i<n;i++)//将A[i]与A[n-i-1]进行交换
{
temp=A[i];A[i]=A[n-i-1]；A[n-i-1]=temp;
}
}
void main()
{
sqlist A;
int n;
n=create(A);
disp(A,n);
invert(A,n);
disp(A,n);
}

【例5】假设有n个线性表顺序地存放在顺序表S[1...m]中，令F[i]和R[i]指向第i个元表的第1个元素和最后1个元素在S中的位置，并设定R[i]<F[i+1]。F[n+1]=m+1。试按要求写出实现算法
（1)在第i个表中的第j项后面插入1个元素，仅当整个[1..m]空间填满时，不允许进行插入操作。
（2）删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储结构。
【解】本题实质上是将n个线性表（长度可能不同）放在一个连续空间（长度为m），来解决这些线性表的插入删除。
（1）的算法：

程序代码

void ins(i,j,x)
{
int p,k;
if(R[n]==m)
cout<<"上溢"<<endl;
else
{
for(p=n;p>=i+1;p--)//将i+1到n的线性表后移一个元素

{
for(k=R[p];k>=F[p];k--)//将第p个线性表后移一个元素
{
s[k+1]=s[k];
R[p]++;
F[p]++;//将p个线性表的首尾元素位置均增1
}
for(p=R[i];p>=j+1;p--)//将第i个线性表的第j个位置起的元素后移
s[p+1]=s[p];
s[p]=x;
R[p]++;
}
}
(2)的算法如下：
void del(i,j)
{
for(p=F[i]+j;p<=m;p++)//元素前移覆盖要删除的元素
s[p]=s[p+1];
for(p=i;p<=n;p++)//将i个及以后的线性表的R[i]值减1
R[p]--;
for(p=i+1;p<=n;p++)//第i+1个及以后的线性表的F[i]值减1
F[p]--;
}

【例6】设A=(a1,a2,...am)和B+(b1,b2,..bn）均为顺序表。若n=m且ai=bi（i=1,2,..n)，则称A=B；若ai=bi(i=1,2,...j)且a(j+1)<b(j+1)则称A<B，在其他则为A＞B.试编写一个算法，当A<B、A=B或A＞B时分别输出-1，0或1。
【解】算法comp()的思想是先找出A和B中前面对应位置相同值的节点，i和j分别为A和B中比较不同元素的下标，然后根据i和j的情况得到A和B的比较结果。实现本题功能的程序如下：

程序代码

#include"sq.cpp"
int comp(sqlist A,int na,sqlist B,int nb)
{
int i=0,j=0;
while(i<na&&j<nb&&A[i++]==B[j++]);//比较相同的部分
i--;j--;
if(i=na&&j==nb) return 0;
if(i==na&&j!=nb) return -1;
if(i!=na&&j==nb) return 1;
if(A[i]>B[j])
return 1;
else return -1;
}
void main()
{
sqlist A;
int na,nb,n;
na=create(na);
nb=create(nb);
n=comp(A,na,B,nb);
switch(N)
{
case 0:cout<<"A=B"<<endl;break;
case 1:cout<<"A>B"<<endl;break;
case 3:cout<<"A<B"<<endl;break;
}
}

看了这么多例题，那该来几道题练习练习啦
【题1】设A为顺序表，试编写删除A中第i个元素起的K个元素的算法。
【题2】编写一个算法，将一个顺序表A（有n个元素）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。
【题3】已知一个顺序表A中的元素按值非递减有序，编写一个函数，插入一个元素x后保持该顺序表是有序的。
【题4】编写一个算法，将m（m>2)个有序（从小到大）顺序表合并成一个有序顺序表。合并过程中不另设新的顺序表存储。
【题5】设某机器表示的整数不超过5位十进制数字。试设计一种表示任意长的整数的数据结构，并利用你设计的数据结构，写出计算任意给定的两个整数之和的算法。

【题1】设A为顺序表，试编写删除A中第i个元素起的K个元素的算法。
实现本题功能的程序如下:

程序代码

#include"sq.cpp"
int delk(sqlist A,int *n,int i,int k)
{
int j;
if(i<=0||i+k-1>*n)
{
cout<<"i,k参数不正确"<<endl;
return 0;
}
else
{
for(j=i+k-1;j<*n;j++)
A[j-k]=A[j];
(*n)-=k;
return 1;
}
}
void main()
{
sqlist A;
int n,i,k;
n=create(A);
disp(A,n);
cout<<"输入i,k:";
cin>>i>>k;
if(delk(A,&n,i,k)==1)
disp(A,n);
}

【题2】编写一个算法，将一个顺序表A（有n个元素）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。
【解】本题的算法思想是：依次遍历A中的元素，比较当前的元素值，大于0者赋给B，小于0者赋给C。实现本题功能的程序如下：

程序代码

#include"sq.cpp"
void split(sqlist A,int na,sqlist B,int *nb,sqlist C,int *nc)
{
int i,j=0,k=0;
for(i=0;i<na;i++0
{
if(A[i]>0)
B[j++]=A[i];
else
C[k++]=A[i];
(*nb)=j;
(*c)=k;
}
void main()
{
sqlist A,B,C;
int na,nb,nc;
na=create(A);
disp(A,na);
split(A,na,B,&nb,C,&nc);
disp(B,nb);
disp(C,nc);
}

【题3】已知一个顺序表A中的元素按值非递减有序，编写一个函数，插入一个元素x后保持该顺序表是有序的。
【解】先找到适合当前的位置，然后后移元素空出一个位置，再将x插入。实现本题功能的程序如下：

程序代码

#include"sq.cpp"
int insert(sqlist A,int n,elemtype x)//顺序表长度为n
{
int i,j;
if(x>=A[n-1])
A[n]=x; //若x大于最后的元素，则将其作为最后一个元素
else
{
i=0;
while(x>A[i]) i++; //查找插入位置
for(j=n;j>=i;j--) A[j+1]=A[j]; //移出插入x的位置
A[i]=x;
}
return (n+1); //顺序表长度增1
}
void main()
{
sqlist A;
int n;
n=create(n);
disp(A,n);
n=insert(A,n,10); //插入元素10
disp(A,n);
}

【题4】编写一个算法，将m（m>2)个有序（从小到大）顺序表合并成一个有序顺序表。合并过程中不另设新的顺序表存储。
【解】两个顺序表A和B的合并过程是，从A的最后1个元素和B的第1个元素开始分别向前向后进行比较，将较大的元素先定位在A中。实现本题功能的程序如下：

程序代码

#include"sq.cpp"
int comb(sqlist A,int na,sqlist B,int nb)
{
int n=na,m=0;
while(m<nb)
if(n==0||A[n-1]<B[m])
{
A[n+nb-m-1]=B[m];//说明B[m]是第n+nb-m大的元素
m++;
}
else
{
A[A[n+nb-m-1]=A[n-1];//说明A[n-1]是第n+nb-m大的元素
n--;
}
return na+nb;

}
void main()
{
sqlist A,B;
int na,nb;
na=create(A);
disp(A,na);
nb=create(B);
disp(B,nb);
na=comb(A,na,B,nb);
disp(A,na);
}

【题5】设某机器表示的整数不超过5位十进制数字。试设计一种表示任意长的整数的数据结构，并利用你设计的数据结构，写出计算任意给定的两个整数之和的算法。
【解】将用户输入的正数按各位数字存放在一个顺序表中，这样就变成了两个顺序表中的数字相加。实现本题功能的程序如下:

程序代码

#include"sq.cpp"
int input(sqlist A)
{
int i;
for(i=0;i<max;i++)
A[i]=0;
cout<<"输入一个正整数的各位（以-1结束)"<<endl;
i=0;
while(1)
{
cin>>A[i];
if(A[i]<0) break;
i++;
}
return i;
}
void output(sqlist A,int low,int high)
//输出顺序表A中的A[low]到A[high]
{
int i;for(i=low;i<hight;i++)
cout<<A[i];
cout<<endl;
}
void move(sqlist A,int na)
//将A中存放的数字移到后面
{
int i;
for(i=0;i<na;i++)
A[max-i-1]=A[na-i-1];
}
int add(sqlist A,int na,sqlist B,nb)
//实现A，B相加，结果放在A中
{
int nc,i,j,length;
if(na>nb) nc=na;
else
nc=nb;
move(A,na);
move(B,nb);
for(i=max-i;i>=max-nc;i--)
{
j=A[i]+B[i];
if(j>9)
{
A[i-1]=A[i-1]+1;
A[i]=j-10;
}
else
A[i]=j;
if(i==max-nc)
{
if(j>9)
{
A[i-1]=1;
length=nc+1;
}
else
length=nc;
}
}
return length;
}
void sqlist A,B;
int na,nb,nc;
na=input(A);
nb=input(B);
cout<<"整数A：";
output(A,0,na);
cout<<"整数B：";
output(B,0,nb);
nc=add(A,na,B,nb);
cout<<"相加:";
output(A,max-nc,max);
}