线性表-顺序表
创建（初始化）
以数组的形式创建顺序表
typedef struct //理解为将定义的结构体改称为{}后的名字，如SQlist
{
Elemtype *elem； //定义顺序表具有首元素地址
int length; //定义顺序表具有表长这一属性
}SQlist;
|
初始化设置顺序表的最大存储空间，以及初始化其表长为0
bool initList(SQlist &sq) //将需要初始化的表传址
{
sq.elem=new maxsize; //为顺序表分配maxsize的空间作为最大上限
if(!sq.elem) return false; //如果空间分配失败，直接返回提示错误
sq.length=0; //如果分配空间成功，则继续初始化表长为0
return true; //返回参数提示顺序表初始化成功
}
|
取值
顺序表能够随机存取，故而方便存取指定位置的值，即可以随机存取
bool getelem(SQlist &sq,int i，elemtype &a)
//将需要初始化的表传址，并且传值需要获取的是第i个值，返回的值传给a
{
if(i<1||i>sq.length) return false; //如果i为非法位置，返回提示错误
a=sq.elem[i]; //否则返回第i个元素给a
return true; //返回提示执行正常
}
|
查找
顺序表的查找就是顺序比较表内元素和待查找元素，相同查找成功，始终不同查找失败
int find(SQlist &sq,elemtype a)
//传址需要查找的表，并传值需要查找的数值a,返回查找到的序号为int类型
{
int i;
for(i=0;i<sq.length;i++)
{
if(sq.elem[i]==a) return i;
//如果查找到了，返回该值在表中的序号，此处为数组下标，若返回第几个元素序号，则需要i+1
}
return -1; //查找失败，返回负数
}
|
插入
顺序表为紧邻的线性表，故而插入时需要向后移动较多元素，并且需要从最后一个元素开始向后移动，以免数据被覆盖
bool insert(SQlist &sq,elemtype a,int i)
//将元素a的值插入表中第i个位置，传址需要做插入的表，以及传值a，i
{
int j;
if(i<1||i>sq.length+1) return false;//如果i值不合法，则不作插入
if(sq.length==maxsize) return false;//如果表长已经达到最大，则判断表满，不作插入
for(j=sq.length-1;j>=i-1;j--)
//让j为最后一个元素的角标，循环递减，并且当j等于插入位置i的前驱时，停止循环
{
sq.elem[j+1]=sq.elem[j]; //给j+1角标的空间赋值当前j角标的值，实现后移
}
sq.elem[i-1]=a; //赋值第i个位置，即角标为i-1的空间为a
sq.length++; //表长增加
return true; //返回插入成功
}
|
删除
顺序表的删除是将待删除位置后面的全部往前覆盖，向前移动较多元素，并且需要从待删除位置的后一个开始移动，以免覆盖数据
bool delete(SQlist &sq,int i)
//传址需要删除元素的顺序表，并且传值需要删除的元素位置
{
int j;
if(i<1||i>sq.length) return false; //如果i值不合法，则不作插入
for(j=i;j<=sq.length-1;j++)
//将i位置之后的所有元素都向前移，并且循环在将最后一个元素移动到表长减一后的位置停止
{
sq.elem[j-1]=sq.elem[j]; //被删位置后的元素全部前移
}
sq.length--; //表长减少
return true;
}
|
实际题目
R7-1 顺序表的建立及遍历 (20 分)
读入n值及n个整数，建立顺序表并遍历输出。
输入格式:
读入n及n个整数
输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:
在这里给出一组输入。例如：
输出样例:
在这里给出相应的输出。例如：
解法：
#include<iostream>
using namespace std;
typedef struct
{
int *a;
int length;
}List;
int create(List &sq)
{
sq.a= new int[100];
if(!sq.a) return 0;
sq.length=0;
return 1;
}
int output(List &sq)
{
int j;
cout<<sq.a[0];
for(j=1;j<sq.length;j++)
{
cout<<" "<<sq.a[j];
}
}
int main()
{
List sqlist;
int i,n;
cin>>n;
create(sqlist);
for(i=0;i<n;i++)
{
cin>>sqlist.a[i];
sqlist.length++;
}
if(sqlist.length!=0)
output(sqlist);
return 0;
}
|
R7-2 jmu-ds-顺序表区间元素删除 (20 分)
若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
输入格式:
三行数据，第一行是顺序表的元素个数，第二行是顺序表的元素，第三行是x和y。
输出格式:
删除元素值在[x,y]之间的所有元素后的顺序表。
输入样例:
10
5 1 9 10 67 12 8 33 6 2
3 10
|
输出样例:
解法：
#include<iostream>
using namespace std;
typedef struct
{
int *a;
int length;
}sqlist;
bool create(sqlist &sq)
{
sq.a= new int[100];
if(!sq.a) return false;
sq.length=0;
return true;
}
bool del(sqlist &sq,int x,int y)
{
int j,i;
for(j=0;j<sq.length;j++)
{
if(sq.a[j]>=x&&sq.a[j]<=y)
{
for(i=j;i<sq.length;i++)
{
sq.a[i]=sq.a[i+1];
}
sq.length--;
j--;
}
}
}
int main()
{
sqlist List;
int n,i,x,y;
cin>>n;
create(List);
for(i=0;i<n;i++)
{
cin>>List.a[i];
List.length++;
}
cin>>x>>y;
del(List,x,y);
cout<<List.a[0];
for(i=1;i<List.length;i++)
{
cout<<" "<<List.a[i];
}
return 0;
}
|
