2024年王道数据结构考研复习指导第二章：线性表的顺序表示——课后综合应用题个人学习的相关运行代码。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define InitSize 10 //表长度的初始定义
#define INT_MAX 0x7fffffff
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表类型定义-动态分配
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0; i<L.length; i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //顺序表的最大长度增加 len
free(p); //释放原来的内存空间
}
//创建一个顺序表
void CreateList(SeqList &L){
int num;
printf("\n\t请输入所需顺序表的长度：");
scanf("%d", &num);
printf("\n\t请输入顺序表内容：");
for(int k=0; k<num; k++){
scanf("%d", &L.data[k]);
L.length++;
}
}
//按值查找
int LocateElem(SeqList &L, int e){
int i;
for(i=0; i<L.length; i++){
if(L.data[i]==e){
return i+1;
}
}
return 0;
}
//折半查找法
void SearchExchangeInsert(SeqList &L, int x){
int low=0, high=L.length-1, mid, t, i;
while(low<=high){
mid=(low+high)/2;
if(L.data[mid]==x) break;
else if(L.data[mid]<x) low=mid+1;
else high=mid-1;
}
if(L.data[mid]==x&&mid!=L.length-1){
t=L.data[mid];
L.data[mid]=L.data[mid+1];
L.data[mid+1]=t;
}
else if(low>high){
L.length++;
for(i=L.length-2; i>high; i--) L.data[i+1]=L.data[i];
L.data[i+1]=x;
}
}
//插入函数
bool ListInsert(SeqList &L, int i, int e){
if(i<1||i>L.length+1){
printf("输入的位序无效！\n");
return false;
}
if(L.length>=L.MaxSize){
printf("当前存储空间已满，无法插入。\n");
return false;
}
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
//输出函数
void PrintList(SeqList &L){
printf("\n\t顺序表内容为：");
for(int i=0; i<L.length; i++){
printf("%d ", L.data[i]);
}
printf("\n");
}
//删除最小值
bool Del_Min(SeqList &L, int &min){
if(L.length==0){
printf("\n\t表空，无法删除元素。\n");
return false;
}
min=L.data[0];
int pos=0;
for(int i=1; i<L.length; i++){
if(L.data[i]<min){
min=L.data[i];
pos=i;
}
}
L.data[pos]=L.data[L.length-1];
L.length--;
return true;
}
//逆置整个顺序表
void Reverse(SeqList &L){
int temp;
for(int i=0; i<L.length/2; i++){
temp=L.data[i];
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
printf("\n\t成功逆置顺序表内容！\n");
PrintList(L);
}
//逆置从from到to的内容
void Reverse_from_to(SeqList &L, int from, int to){
int i, temp;
for(i=0; i<(to-from+1)/2; i++){
temp=L.data[from+i];
L.data[from+i]=L.data[to-i];
L.data[to-i]=temp;
}
}
//序列可左移p个位置
void Converse(SeqList &L, int n, int p){
Reverse_from_to(L, 0, p-1);
Reverse_from_to(L, p, n-1);
Reverse_from_to(L, 0, n-1);
}
//删除所有值为x的数据元素
void Del_x(SeqList &L, int x){
int k=0, i;
for(i=0; i<L.length; i++){
if(L.data[i]!=x){
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
printf("\n\t成功删除x！\n");
PrintList(L);
}
//删除表中s-t之间的所有元素
bool Del_s_t(SeqList &L, int s, int t){
int k=0, i;
if(L.length==0){
printf("\n\t顺序表内容为空，无法删除！\n");
return false;
}if(s>=t|| L.data[L.length-1]<s|| L.data[0]>t){
printf("\n\t给定值s、t不合理，无法删除！\n");
return false;
}for(i=0; i<L.length; i++){
if(L.data[i]<s||L.data[i]>t){
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
printf("\n\t成功删除s-t之间数据元素！\n");
return true;
}
//删除表中重复的元素
bool Del_Same(SeqList &L){
if(L.length==0){
printf("\n\t顺序表内容为空，无法删除！\n");
return false;
}
int i, j;
for(i=0, j=1; j<L.length; j++) //查找下一个与上个元素不同的值
if(L.data[i]!=L.data[j])
L.data[++i]=L.data[j];
L.length=i+1;
printf("\n\t成功删除重复的数据元素！\n");
return true;
}
//合并两个有序表并输出
bool Merge(SeqList A, SeqList B, SeqList &C){
if(A.length+B.length>C.MaxSize){
printf("\n\t合并后长度超过限度，无法合并！\n");
return false;
}
int i=0, j=0, k=0;
while(i<A.length&&j<B.length){ //循环比较，小者先存入结果表
if(A.data[i]<=B.data[j])
C.data[k++]=A.data[i++];
else
C.data[k++]=B.data[j++];
}
while(i<A.length)
C.data[k++]=A.data[i++];
while(j<B.length)
C.data[k++]=B.data[j++];
C.length=k; //已经k++过所以长度为k
printf("\n\t合并成功！合并后表内容如下：\n");
return true;
}
//交换线性表位置
bool Exchange(SeqList &A, SeqList &B, SeqList &C){
int nb=B.length;
for(int k=0; k<C.length; k++){
if(nb!=0){
C.data[k]=B.data[k];
nb--;
}else{
C.data[k]=A.data[k-C.length+A.length];
}
}
C.length=A.length+B.length;
printf("\n\t成功交换线性表位置！\n");
return true;
}
//求序列A和B的中位数
int M_Search(SeqList &A, SeqList &B){
int s1=0, d1=A.length-1, m1, s2=0, d2=B.length-1, m2;
//分别表示序列A和B的首位数、末位数和中位数
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A.data[m1]==B.data[m2])
return A.data[m1]; //两个序列中位数相等，取任一为中位数，结束
if(A.data[m1]<B.data[m2]){ //若a<b则舍弃A中较小一半和B中较大一半，且舍弃长度相等
if((s1+d1)%2==0){ //若元素个数为奇数
s1=m1; //舍弃A中间点以前的部分且保留中间点
d2=m2; //舍弃B中间点以后的部分且保留中间点
}
else{ //元素个数为偶数
s1=m1+1; //舍弃A中间点及中间点以前部分
d2=m2; //舍弃B中间点以后部分且保留中间点
}
}
else{ //若a>b则舍弃A中较大一半和B中较小一半，且舍弃长度相等
if((s2+d2)%2==0){ //若元素个数为奇数
d1=m1; //舍弃A中间点以后的部分且保留中间点
s2=m2; //舍弃B中间点以前的部分且保留中间点
}
else{ //元素个数为偶数
d1=m1; //舍弃A中间点以后部分且保留中间点
s2=m2+1; //舍弃B中间点及中间点以前部分
}
}
}
//较小者为中位数
return A.data[s1]<B.data[s2]?A.data[s1]:B.data[s2];
}
//摩尔投票法-找>n/2主元素
int Majority(SeqList &A){
int i, c, count=1; //c用来保存候选主元素，count用来计数
c=A.data[0]; //设置A.data[0]为主元素
for(i=1; i<A.length; i++){ //查找主元素
if(A.data[i]==c)
count++; //对A的候选主元素计数
else
if(count>0) //处理不是候选主元素的情况
count--;
else{ //更换候选主元素，重新计数
c=A.data[i];
count=1;
}
}
if(count>0)
//统计候选主元素实际出现次数
for(i=count=0; i<A.length; i++)
if(A.data[i]==c)
count++;
if(count>A.length/2) return c; //确认候选主元素
else return -1; //不存在主元素
}
//寻找最小正整数
int FindMinPosInt(SeqList &L){
int i;
int B[L.length];
memset(B,0,sizeof(B)); //创建数组并赋初值为0
for(i=0; i<L.length; i++)
if(L.data[i]>0&&L.data[i]<=L.length)
B[L.data[i]-1]=1; //若L.data[i]的值介于1~n则标记数组B
for(i=0; i<L.length; i++) //扫描数组B，找到目标值
if(B[i]==0) break;
return i+1; //返回结果
}
//三元组找最小距离D
//计算绝对值
int abs_(int a){
if(a<0) return -a;
else return a;
}
//a是否是三个数中的最小值
bool xls_min(int a, int b, int c){
if(a<=b&&a<=c) return true;
return false;
}
//寻找最小距离
int FindMinofTrip(SeqList &A, SeqList &B, SeqList &C){
//D_min用于记录三元组的最小距离，初值赋为INT_MAX
int D_min=INT_MAX, i=0, j=0, k=0, D;
while(i<A.length&&j<B.length&&k<C.length&&D_min>0){
D=abs_(A.data[i]-B.data[j])+abs_(B.data[j]-C.data[k])+abs_(C.data[k]-A.data[i]); //计算D
if(D<D_min) D_min=D; //更新D
if(xls_min(A.data[i], B.data[j], C.data[k])) i++; //更新a
else if(xls_min(B.data[j], C.data[k], A.data[i])) j++;
else k++;
}
return D_min;
}
int main(){
SeqList L; //声明一个顺序表
SeqList a, b;
SeqList S1, S2, S3;
InitList(L); //初始化顺序表
int i=1, choice;
int c, na;
while(i)
{
printf("\n\t***************顺 序 表****************");
printf("\n\t* *");
printf("\n\t* 0--创建一个顺序表 *");
printf("\n\t* 1--删除最小元素并输出 *");
printf("\n\t* 2--逆置顺序表内容 *");
printf("\n\t* 3--删除所有值为x的数据元素 *");
printf("\n\t* 4--删除有序表s-t之间元素 *");
printf("\n\t* 5--删除表中重复的元素 *");
printf("\n\t* 6--合并两个有序表并输出 *");
printf("\n\t* 7--合并两表并交换位置 *");
printf("\n\t* 8--折半查值或插入有序表 *");
printf("\n\t* 9--序列可左移p个位置 *");
printf("\n\t* 10--求序列A和B的中位数 *");
printf("\n\t* 11--摩尔投票法找>n/2主元素 *");
printf("\n\t* 12--寻找最小正整数 *");
printf("\n\t* 13--三元组找最小距离D *");
printf("\n\t* -1--返 回 *");
printf("\n\t* *");
printf("\n\t*****************************************");
printf("\n\t请选择菜单号（0--10）：");
scanf("%d",&choice);
switch(choice)
{
case 0:
CreateList(L);
break;
case 1:
int min;
if(Del_Min(L, min)){
printf("\n\t被删除的最小元素为：%d\n", min);
PrintList(L);
}
break;
case 2:
Reverse(L);
break;
case 3:
int x;
printf("\n\t请输入所需删除的数据元素x：");
scanf("%d", &x);
Del_x(L, x);
break;
case 4:
int s, t;
printf("\n\t请输入所需删除的范围s-t：");
scanf("%d %d", &s, &t);
Del_s_t(L, s, t);
PrintList(L);
break;
case 5:
Del_Same(L);
PrintList(L);
break;
case 6:
SeqList A, B; //声明一个顺序表
InitList(A);
InitList(B);
printf("\n\t开始建表A\n");
CreateList(A);
printf("\n\t开始建表B\n");
CreateList(B);
Merge(A, B, L);
PrintList(L);
break;
case 7:
InitList(a);
InitList(b);
printf("\n\t开始建线性表a\n");
CreateList(a);
printf("\n\t开始建线性表b\n");
CreateList(b);
c=a.length+b.length;
na=a.length;
for(int k=0; k<c; k++){
if(na!=0){
L.data[k]=a.data[k];
na--;
}else{
L.data[k]=b.data[k-c+b.length];
}
}
L.length=a.length+b.length;
printf("\n\t原一维数组A[m+n]的内容合并完成！\n");
PrintList(L);
Exchange(a, b, L);
PrintList(L);
break;
case 8:
int e;
printf("\n\t请输入所需查找的数据元素e：");
scanf("%d", &e);
c=LocateElem(L, e);
if(c!=0){
na=L.data[c-1];
L.data[c-1]=L.data[c];
L.data[c]=na;
printf("\n\t找到了e值，并成功交换！\n");
PrintList(L);
}else{
//na=L.length+1;
//for(int k=0; k<L.length; k++){
// if(e<L.data[k]){
// na=k+1;
// return na;
// }
//}
//ListInsert(L, na, e);
SearchExchangeInsert(L, e);
printf("\n\t没有找到e值，成功插入表中！\n");
PrintList(L);
}
break;
case 9:
int p;
printf("\n\t请输入所需左移的位数p：");
scanf("%d", &p);
Converse(L, L.length, p);
PrintList(L);
break;
case 10:
InitList(a);
InitList(b);
printf("\n\t开始建升序序列A\n");
CreateList(a);
printf("\n\t开始建升序序列B\n");
CreateList(b);
c=M_Search(a, b);
printf("\n\t两个升序序列的中位数为：%d\n", c);
break;
case 11:
c=Majority(L);
if(c==-1)
printf("\n\t不存在主元素！\n");
else
printf("\n\t主元素为：%d\n", c);
break;
case 12:
c=FindMinPosInt(L);
printf("\n\t找到最小正整数为：%d\n", c);
break;
case 13:
InitList(S1);
InitList(S2);
InitList(S3);
printf("\n\t开始建非空升序数组S1\n");
CreateList(S1);
printf("\n\t开始建非空升序数组S2\n");
CreateList(S2);
printf("\n\t开始建非空升序数组S3\n");
CreateList(S3);
c=FindMinofTrip(S1, S2, S3);
printf("\n\t找到三元组最小距离D为：%d\n", c);
break;
case -1:
i=0;
break;
}
}
return 0;
}
