顺序表

数据结构是计算机科学专业的核心课程之一，面向对象方法已经成为目前系统开发和程序设计的主流模式，而C++是目前使用的最广泛的面向对象程序设计语言之一。

知识点
1、顺序表的概念
顺序表是线性表的顺序存储结构，加按顺序存储方式构造的线性表的存储结构。
说明：对于n个元素的顺序表A，可以表示为A[1..n](适合Pascal),其下标从1到n，A[1]称为第1个元素，A[2]称为第2个元素，……，A[n]称为第n个元素；也可以表示为A[0...n-1]（适合C/C++)，其中下标0到n-1，A[0]称为第1个元素，A[1]称为第2个元素，……，A[n-1]称为第n个元素。
本教程采用后者。

2、顺序表的存储结构
顺序表节点类型的定义如下：
#define max 50 //顺序表中最多元素个数
typedef int elemtype;//定义elemtype为int类型
typedef elemtype sqlist[max];
在顺序表中，每个节点ai的存储地址是该节点在表中的位置的i的线性函数，只要知道基地址和每个节点的大小，就可在相同的时间内求出任一节点的存储地址。因此顺序表是一种随机存储结构。

假设表中每个节点占用c个存储单元，并设用中开始节点a1的存储地址（简称为基础地址）是LOC(ai)，那么节点ai的存储地址LOC(ai）可通过下式计算：
LOC(ai)=LOC(a1)+(i-1)*c(1≤i≤n)

3、顺序表的运算
●create(sqlist A)：创建顺序表A，并返回其中的元素个数。
●disp(sqlist A,int n):输出一个具有n个元素的顺序表A。
●ins(sqlist A,int I,elemtype x)：在顺序表A的第i个元素前插入一个元素x。若i=0,则新元素作为第1个元素；若i=n，则插入在顺序表的最后。
●del(sqlist A,int n,int i)：在顺序表A中删除第i个元素。
●find(sqlist A,int n,elemtype x)：在一个有n个元素的顺序表A中查找元素值为x的元素。

题目：实现两个链表的合并

（1） 建立两个链表A和B，链表元素个数分别为m、n
（2） 假设元素分别为（x1,x2,……,xm），和（y1,y2,……,yn）。把它们合并成一个线性表C，使得：
当m>=n时，C=x1,y1,x2,y2, ……,xn,yn, ……,xm
当n>=m时，C=y1,x1,y2,x2, ……,ym,xm, ……,yn
输出线性表C
（3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D

测试数据：
（1）A表 （30，41，15，12，56，80）
B表 （23，56，78，23，12，33，79，90，55）
（2）A表 （30，41，15，12，56，80，23，12，34）
B表 （23，56，78，23，12）


报告要求：
1、方案设计
2、程序框图
3、程序代码
4、程序调试过程和结果
5、总结

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

#include\"iostrea.h\"
#define max 50 //顺序表中最多元素个数
typedef int elemtype;
typedef elemtype sqlist[max];
int create(sqlist A)//创建顺序表
{
int I,n;
cout<<\"创建一个顺序表\"<cout<<\" 输入元素个数：\";
cin>>n;
for(i=0;i{
cout<<\" 输入第\"<cin>>A[i];
}
return n;
}
void disp(sqlist A,int n)//输出一个顺序表
{
int I;
cout<<\"输出一个顺序表\"<if(n==0)
cout<<\"空表\";
for(i=0;icout<cout<}
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值下溢或上溢\"<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值下溢或上溢\"<else
{
for(j=i-1;jA[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(ielse 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{
if(A[i]<0)
{
B[x]=A[i];x++;
}
else
{
B[y]=A[i];y--;
}
for(i-0;iA[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]{
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{
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]（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<<\"上溢\"<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)【解】算法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(ii--;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\"<case 1:cout<<\"A>B\"<case 3:cout<<\"A}
}

看了这么多例题，那该来几道题练习练习啦
【题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参数不正确\"<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{
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(mif(n==0||A[n-1]{
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;iA[i]=0;
cout<<\"输入一个正整数的各位（以-1结束)\"<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;icout<cout<}
void move(sqlist A,int na)
//将A中存放的数字移到后面
{
int I;
for(i=0;iA[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);
}