顺序表操作
什么是顺序表
顺序表示线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结构。
对于有n个元素的顺序表A，可以表示为A[0…n-1]，其下标从0到n-1，A[0]称为第1个元素，A[1]称为第2个元素，…A[n-1]称为第n个元素。
顺序表的存储结构
#define MaxLen 50
typedef int elemtype; //定义elemtype为int类型
typedef elemtype sqlist[MaxLen];
顺序表的创建、显示
#include<stdio.h>
#define Maxlen 20
typedef int elemtype;
typedef elemtype sqlist[Maxlen];
int create(sqlist A)
{
int i,n;
printf("创建一个顺序表：\n");
printf("输入元素个数：");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("输入第%d个元素：",i+1);
scanf("%d",&A[i]);
}
return n;
}
void display(sqlist A,int n)
{
int i;
printf("输出一个顺序表：");
if(n==0){
printf("\n空表");
return;
}
for(i=0;i<n;i++)
{
printf("%4d",A[i]);
}
printf("\n");
}
顺序表的插入
（以下程序都需要用到顺序表的创建、显示。#include "sqlist.cpp"是将顺序表的创建、显示存为sqlist.cpp文件，然后被调用。）
已知一个顺序表A中的元素按值非递减有序，编写一个函数，插入一个元素x后保持该顺序表是有序的。
#include "sqlist.cpp"
int Insert(sqlist A,int n)
{
int m=n;
int s;
int j=0;
printf("请输入插入元素：");
scanf("%d",&s);
while(j<1){
if(A[n-1]<s)
{
A[n]=s;
j--;
}
else{
A[n]=A[n-1];
n--;
}
}
n=m+1;
}
int main()
{
sqlist A;
int n;
n=create(A);
display(A,n);
n=Insert(A,n);
display(A,n);
}
顺序表的删除
设A为顺序表，试编写删除A中第i个元素起的k个元素的算法。
#include "sqlist.cpp"
int Delete(sqlist A,int n)
{
int j,k,i;
printf("请输入删除的位置j：");
scanf("%d",&j);
printf("请输入删除的个数k:");
scanf("%d",&k);
for(i=0;i<=n-k;i++)
{
A[j-1]=A[j+k-1];
j++;
}
n=n-k;
return n;
}
int main()
{
sqlist A;
int n;
n=create(A);
display(A,n);
n=Delete(A,n);
display(A,n);
}
顺序表的合并
编写一个算法，将m(m>2)个有序(从小到大)顺序表合并成一个有序顺序表。合并过程不另设新的顺序表存储。
#include"sqlist.cpp"
int comb(sqlist A,int na,sqlist B,int nb)
{
int n=na,m=nb;
if(na+nb > Maxlen) return 0; //顺序表上溢
while(nb>0)
{
if((na==0)||(A[na-1]<B[nb-1]))
{ //说明B[nb-1]是第na+nb大的元素
A[na+nb-1] = B[nb-1];
nb--;
}
else
{
A[na+nb-1] = A[na-1]; //说明A[na-1]是第na+nb大的元素
na--;
}
}
na = n + m;
return na;
}
int main(){
sqlist A,B;
int m;
printf("请输入顺序表个数：");
scanf("%d",&m);
int na,nb;
na = create(A);
display(A,na);
for(int i=1;i<m;i++)
{
nb = create(B);
na = comb(A,na,B,nb);
display(B,nb);
}
display(A,na);
}
顺序表的排列
设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中所有元素组成一个新的从小到大的有序顺序表C的算法，要求删除重复的元素。
#include"sqlist.cpp"
int comb(sqlist A,int na,sqlist B,int nb)
{
sqlist C;
int n=na,m=nb;
int temp;
if(na+nb > Maxlen) return 0; //顺序表上溢
while(nb>0)
{
if((na==0)||(A[na-1]<B[nb-1])){ //说明B[nb-1]是第na+nb大的元素
A[na+nb-1] = B[nb-1];
nb--;
}
else{
A[na+nb-1] = A[na-1]; //说明A[na-1]是第na+nb大的元素
na--;
}
}
na = n + m;
for(int i=0;i<na;i++)
{
C[i]=A[i];
if(A[i]==A[i+1])
{
for(int j=i;j<=na-i;j++)
{
A[j+1]=A[j+2];
}
na--;
}
}
for(int i=0;i<na;i++){
A[i]=C[i];
}
return na;
}
int main(){
sqlist A,B;
int na,nb;
na = create(A);
display(A,na);
nb = create(B);
display(B,nb);
na = comb(A,na,B,nb);
display(A,na);
}
顺序表的逆序
设有一个顺序表A，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元。
#include"sqlist.cpp"
void invert(sqlist A,int n){
int m=n/2;
int temp=0;
for(int i=0;i<m;i++){
temp=A[i];
A[i]=A[n-i-1];
A[n-i-1]=temp;
}
}
int main(){
sqlist A;
int n;
n = create(A);
display(A,n);
invert(A,n);
display(A,n);
return 0;
}
顺序表的调整
已知数组A[0…n-1]的元素类型为整型，设计算法调整A，使其左边的所有元素小于0，右边的所有元素大于等于0(要求算法的时间复杂度和空间复杂度均为O(n))
#include<stdio.h>
#include"sqlist.cpp"
void adjust(sqlist A,int n) //调整A
{
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];
}
}
int main()
{
sqlist A;
int n;
n = create(A);
display(A,n);
adjust(A,n);
display(A,n);
return 0;
}