| 顺序表基于静态存储习题 |
|---|
| 1.创建一个顺序表 |
| 2.从顺序表中删除第i个元素 |
| 3.在第i个元素前插入e |
| 4.从顺序表中删除最小元素，空出的位置由最后一个元素填补 |
| 5.在无序顺序表中删除值在s和t之间的所有元素 |
| 6.在非递减顺序表中删除值在区间[s,t]的所有元素 |
| 7.删除非递减顺序表中的重复元素 |
| 顺序表基于动态存储习题 |
|---|
| 8.顺序表A和B的元素个数分别为m和n，表A升序，表B降序排序，两个表中都不在相同的元素 |
| 8.1 将两表合并，两表中的元素存储到表C中(c表保持升序) |
| 8.2 表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排序 |
| 9.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解交集 |
| 10.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解A-B（差集） |
| 11.设计算法算法逆置顺序表 |
| 12.将序列L循环左移动 |
1.创建一个顺序表
// 本程序为顺序表模版
#include <iostream>
#define MAX_SIZE 100 //确定顺序表总的空间大小为100
typedef int ElemType;
typedef struct sqlist
{
ElemType list[MAX_SIZE];
int length; //记录表长
}sqlist;
void print_list(sqlist a)
{
for (int i=0; i<a.length; i++) {
printf("%d->",a.list[i]);
}
}
int main() {
sqlist a;
a.length=0; //初始化单链表表长为7
for(int i=0;i<=6;i++)
{
a.list[i]=i+1;
a.length++;
} //定义一个 1，2，3，4，5，6，7的顺序表
printf("检查顺序表的第一个元素：%d\n当前顺序表的表长为：%d\n",a.list[0],a.length);
printf("--------打印读入链表-----------\n");
print_list(a);printf("\n");
printf("-----------------------------\n");
return 1;
}
2.从顺序表中删除第i个元素
void delete_i(sqlist &a,int x)
{
for(int i=x;i<a.length;i++)
{
a.list[i-1]=a.list[i];
}
a.list[a.length-1]=0;//清空最后一个值的数据
a.length--;
}
3.在第i个元素前插入e
void insert_i(sqlist &a,int x,int e)
{
for(int i=a.length;i>=x;i--)
{
a.list[i]=a.list[i-1];
}
a.list[x-1]=e;
a.length++;
}
4.从顺序表中删除最小元素，空出的位置由最后一个元素填补
void delete_min(sqlist &a)
{
int min=100000;
int flag=0;
for(int i=0;i<a.length;i++)
{
if(a.list[i]<min)
{
min=a.list[i];
flag=i;
}
}
a.list[flag]=a.list[a.length-1];
a.length--;
}
5.在无序顺序表中删除值在s和t之间的所有元素
void deleteElem(sqlist &a,int s,int t)
{
int curlength=0;//指向表头的指针，同时也记录着新表的长度
for(int i=0;i<a.length;i++)
{
if(a.list[i]<s||a.list[i]>t)
{
a.list[curlength++]=a.list[i];
}
}
a.length=curlength;
}
6.在非递减顺序表中删除值在区间[s,t]的所有元素
从前后找到第一个s，从后往前找到最后一个t，将t后面加入到第一个s前面
//在无序顺序表中删除s和t之间的所有元素
void delete_st(sqlist &a,int s,int t)
{
int first_s=0;
int last_t=0;
int curlength1=0; //记录s前新表长度
int curlength2=0; //记录t后新表长度
for(int i=0;i<a.length;i++)
{
if(a.list[i]>=s)
{
first_s=i;
break;
}else curlength1++;
}
for(int j=a.length-1;j>=0;j--)
{
if(a.list[j]<=t)
{
last_t=j;
break;
}else curlength2++;
}
for(int i=first_s,j=last_t+1;j<a.length;j++,i++)
{
a.list[i]=a.list[j];
}
a.length=curlength1+curlength2;
printf("length=%d\n",a.length);
}
7.删除非递减顺序表中的重复元素
思想:新表表尾和旧表元素不同时，加入新表
void delete_repeat(sqlist &a)
{
int curlength=0;
for(int i=1;i<a.length;i++)
{
if(a.list[curlength]!=a.list[i])
{
a.list[++curlength]=a.list[i];
}
}
a.length=curlength+1; //长度=下标+1
}
从第8题开始，存储方式改为动态存储
8.顺序表A和B的元素个数分别为m和n，表A升序，表B降序排序，两个表中都不在相同的元素
关于动态存储顺序表
typedef int ElemType;
typedef struct SqList
{
ElemType *PList;
int length;
int listSize;
}SqList;
8.1 将两表合并，两表中的元素存储到表C中(c表保持升序)
void combine(sqList &a,sqlist &b,sqlist &c)
{
c.length=a.length+b.length;
c.list=(ElemType *)malloc(sizeof(ElemType)*c.length);
int curlength=0;
int index_a=0; //指向a第一个元素的指针
int index_b=b.length-1; //指向b最后一个元素的指针
while(index_a<a.length&&index_b>=0)
{
if(a.list[index_a]<b.list[index_b])
{
//把a加入c
c.list[curlength++]=a.list[index_a];
index_a++;
}else{
//把b加入c
c.list[curlength++]=b.list[index_b];
index_b--;
}
}
//把a或b中的剩余元素加入c中
while(index_a<a.length)
{
c.list[curlength++]=a.list[index_a];
index_a++;
}
while(index_b>=0)
{
c.list[curlength++]=b.list[index_b];
index_b--;
}
}
8.2 表A前r个元素递增有序，而表A中后n-r个元素递减有序，将表A进行升序排序
一直以最后一个元素为目标，依次的插入进前面的递增序列。不断更新最后一个元素。
void combine_a(sqList &a ,int k)
{
for(int i=0;i<a.length-1;i++)
{
if(a.list[a.length-1]<=a.list[i])
{
int temp=a.list[a.length-1];
for(int j=a.length-1;j>i;j--)//包括i在内的所有元素后移
{
a.list[j]=a.list[j-1];
}
a.list[i]=temp;
}
}
}
9.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解交集
解析:
分别设置两个指针指向两个集合开头，若集合A开头元素小于B集合开头元素，则说明B集合的其他元素都大于A，故A后移一位，反之B后移一位，每当相等的时候，加入交集，同时A和B同时后移一位，直到其中一个表为空时，退出循环。在a表中存储交集
设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9
输出：应为 5 7 9
代码如下:
void jiaoji(sqList &a,sqlist &b)
{
int curlength=0;
int index_a=0;
int index_b=0;
while (index_a<a.length||index_b<b.length) {
if(a.list[index_a]<b.list[index_b])
{
index_a++;
}
else if(a.list[index_a]==b.list[index_b])
{
a.list[curlength++]=a.list[index_a];
index_a++;
index_b++;
}else{
index_b++;
}
}
a.length=curlength;
}
10.给定两个非空集合A和B，分别用升序顺序表La和Lb存储，设计算法求解A-B（差集）
解析:
每次将A小于的元素加入进差集当中
设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9
输出：应为 1 2 15
代码如下:
void chaji(sqList &a,sqlist &b)
{
int curlength=0;
int index_a=0;
int index_b=0;
while (index_a<a.length||index_b<b.length) {
if(a.list[index_a]<b.list[index_b])
{
a.list[curlength++]=a.list[index_a++];
}
else if(a.list[index_a]==b.list[index_b])
{
index_a++;
index_b++;
}else{
index_b++;
}
}
while (index_a<a.length) {
//如果b短，将a中剩余的元素加入
a.list[curlength++]=a.list[index_a++];
}
a.length=curlength;
}
11.设计算法算法逆置顺序表
void reverse(sqList &a)
{
int low=0;
int high=a.length-1;
while (low<high) {
int temp=a.list[low];
a.list[low++]=a.list[high];
a.list[high--]=temp;
}
}
12.将序列L循环左移动
解析:使用三次逆置
void r_reverse(sqList &a,int low,int high)
{
while (low<high) {
int temp=a.list[low];
a.list[low++]=a.list[high];
a.list[high--]=temp;
}
}
void ROL(sqList &a,int r)
{
r_reverse(a,0,r-1);
r_reverse(a,r,a.length-1);
r_reverse(a, 0,a.length-1);
}
