[toc]
王道后面的编程题
第一部分
1
image-20210330165049293
注意由于用最后一个元素填补了前面删去的位置,答案里长度减一了.
见仁见智吧,我觉得不减一也可以.
for(int i = 1;i<l.length;i++) 假如只有1个数,不满足i<长度1,不进行循环
int deleteMin(Dynamiclist &l){
if(l.length==0){
cout<<"表空"<<endl;
return -999;
}
int min=l.data[0];//最小元素初始为第一个
int index=0;//最小位置下标
for(int i = 1;i<l.length;i++){//假如只有1个数,不满足i<长度1,不进行循环
if(min>l.data[i]){
min=l.data[i];
index=i;
}
}
l.data[index]=l.data[l.length-1];
l.length--;
return min;
}
2
image-20210330165633458
要求空间复杂度为1,就不能在重新生成一个顺序表
void backwardOrder(Dynamiclist &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;
}
}
==3==
image-20210330165745611
注意要求的时间复杂度和空间复杂度
我感觉这个思想还是很重要的,count来计数x出现的次数,不等于值的数往前移count的位置
void deleteAllValue(Dynamiclist &l,int x){
int count=0;//与x相等的数的个数
for(int i=0;i<l.length;i++){
if(l.data[i]==x){
count++;
}
else{
l.data[i-count]=l.data[i];
}
}
l.length-=count;
}
前四个题运行
void test_Test(){
Dynamiclist l;
initDynamicList(l);
for(int i=0;i<10;i++){
insertList(l,i+1,i);
}
printList(l);
cout<<"--------------------"<<endl;
cout <<"最小的是"<<deleteMin( l)<<endl;
cout <<"删除最小的"<<endl;
printList(l);
cout<<"--------------------"<<endl;
backwardOrder(l);
cout <<"逆序后"<<endl;
printList(l);
cout<<"--------------------"<<endl;
deleteAllValue(l,4);
cout <<"删除4后"<<endl;
printList(l);
cout<<"--------------------"<<endl;
Dynamiclist l2;
initDynamicList(l2);
for(int i=0;i<8;i++){
insertList(l2,i+1,4);
}
insertList(l2,9,99);
printList(l2);
cout<<"--------------------"<<endl;
deleteAllValue(l2,4);
cout <<"删除4后"<<endl;
printList(l2);
cout<<"--------------------"<<endl;
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是3
第5个元素是4
第6个元素是5
第7个元素是6
第8个元素是7
第9个元素是8
第10个元素是9
--------------------
最小的是0
删除最小的
第1个元素是9
第2个元素是1
第3个元素是2
第4个元素是3
第5个元素是4
第6个元素是5
第7个元素是6
第8个元素是7
第9个元素是8
--------------------
逆序后
第1个元素是8
第2个元素是7
第3个元素是6
第4个元素是5
第5个元素是4
第6个元素是3
第7个元素是2
第8个元素是1
第9个元素是9
--------------------
删除4后
第1个元素是8
第2个元素是7
第3个元素是6
第4个元素是5
第5个元素是3
第6个元素是2
第7个元素是1
第8个元素是9
--------------------
第1个元素是4
第2个元素是4
第3个元素是4
第4个元素是4
第5个元素是4
第6个元素是4
第7个元素是4
第8个元素是4
第9个元素是99
--------------------
删除4后
第1个元素是99
--------------------
第二部分
==4==
image-20210330170014220
注意是顺序表,删除的一定是一块元素,不过我感觉还不如第三题的方法快
这里我的方法和答案不太一样,主要是定位的方法一个是++我用的赋值
void deleteValueScopefromOrdered(Dynamiclist &l,int s,int t){
if(l.length==0||s>=t){
cout <<"有误"<<endl;
return;
}
int begin;//大于等于s的初始下标
int last; //小于等于t的第一个下标
for(int i=0;i<l.length;i++){
if(l.data[i]<=s){
begin=i;
}
if(l.data[i]<=t){
last=i;
}
}
//假如最后一位都小于s,那么begin=l.length也就是指向最后一个的下一个,退出循环
if(s>=l.length){
return;
}
for(int i=last+1;i<l.length;i++){
//last-begin+1 是中间数的数量
l.data[i-(last-begin+1)]=l.data[i];
}
l.length-=(last-begin+1);
}
5
image-20210330230133728
和第三题的思想差不多
void deleteValueScope(Dynamiclist &l,int s,int t){
if(l.length==0||s>=t){
cout <<"有误"<<endl;
return;
}
int count=0;
for(int i=0;i<l.length;i++){
if(l.data[i]>=s&&l.data[i]<=t){
count++;
}
l.data[i-count]=l.data[i];
}
}
4,5运行结果
注意这里第五个展示的时候还用到了动态分配的顺序表的自动增长
Dynamiclist l;
initDynamicList(l);
for(int i=0;i<10;i++){
insertList(l,i+1,i);
}
printList(l);
deleteValueScopefromOrdered(l,3,5);
cout<<"顺序表中删除3到5之间的数"<<endl;
printList(l);
cout<<"--------------------"<<endl;
for(int i=0;i<10;i++){
insertList(l,i+1,i);
}
printList(l);
deleteValueScope(l,3,5);
cout<<"删除3到5之间的数"<<endl;
printList(l);
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是3
第5个元素是4
第6个元素是5
第7个元素是6
第8个元素是7
第9个元素是8
第10个元素是9
顺序表中删除3到5之间的数
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是6
第5个元素是7
第6个元素是8
第7个元素是9
--------------------
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是3
第5个元素是4
第6个元素是5
第7个元素是6
第8个元素是7
第9个元素是8
第10个元素是9
第11个元素是0
第12个元素是1
第13个元素是2
第14个元素是6
第15个元素是7
第16个元素是8
第17个元素是9
删除3到5之间的数
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是6
第5个元素是7
第6个元素是8
第7个元素是9
第8个元素是0
第9个元素是1
第10个元素是2
第11个元素是6
第12个元素是7
第13个元素是8
第三部分
==6==
image-20210330230121973
1
因为有序只需要比较前一个与后一个是否相同
注意这里的思想
void orderedListDeleteRepeat(Dynamiclist &l){
int i;
for( int j=1,i=0;j<l.length;j++){
if(l.data[i]!=l.data[j]){
l.data[++i]=l.data[j];
}
}
l.length=i+1;
}
演示
Dynamiclist l;
initDynamicList(l);
for(int i=0;i<10;i++){
insertList(l,i+1,1);
}
insertList(l,11,9);
insertList(l,12,99);
printList(l);
cout<<"删除重复的"<<endl;
orderedListDeleteRepeat(l);
printList(l);
第1个元素是1
第2个元素是1
第3个元素是1
第4个元素是1
第5个元素是1
第6个元素是1
第7个元素是1
第8个元素是1
第9个元素是1
第10个元素是1
第11个元素是9
第12个元素是99
删除重复的
第1个元素是1
==7==
image-20210330230105931
因为有序,依次比较,最后剩下的直接放到新顺序表后面
Dynamiclist l;
initDynamicList(l);
Dynamiclist ll;
initDynamicList(ll);
Dynamiclist lll;
initDynamicList(lll);
for(int i=0;i<10;i++){
insertList(l,i+1,i);
}
for(int i=0;i<10;i++){
insertList(ll,i+1,i+i/2);
}
printList(l);
printList(ll);
cout<<"合并"<<endl;
increaseList(lll,20);//增大容量
combineTwoOrderedList(l,ll,lll);
printList(lll);
结果
第1个元素是0
第2个元素是1
第3个元素是2
第4个元素是3
第5个元素是4
第6个元素是5
第7个元素是6
第8个元素是7
第9个元素是8
第10个元素是9
第1个元素是0
第2个元素是1
第3个元素是3
第4个元素是4
第5个元素是6
第6个元素是7
第7个元素是9
第8个元素是10
第9个元素是12
第10个元素是13
合并
第1个元素是0
第2个元素是0
第3个元素是1
第4个元素是1
第5个元素是2
第6个元素是3
第7个元素是3
第8个元素是4
第9个元素是4
第10个元素是5
第11个元素是6
第12个元素是6
第13个元素是7
第14个元素是7
第15个元素是8
第16个元素是9
第17个元素是9
第18个元素是10
第19个元素是12
第20个元素是13
==8==
image-20210331102944806
typedef int DataType;
//left左边开始的下标 right结束的下标,从left到right交换
//注意是下标,所以不用减一
void reverse(DataType a[],int left,int right){
//注意判别条件必须是中间的减去左边的 另外取等号
int mid=(left+right)/2;
for(int i=0;i<=mid-left;i++){
DataType temp;
//注意这一段,写错了
temp=a[left+i];
a[left+i]=a[right-i];
a[right-i]=temp;
}
}
void exchange(DataType a[],int m,int n){
//左边m个元素,右边n个元素
reverse(a,0,m+n-1);
reverse(a,0,n-1);
//注意 划分区间
//0 n-1 n m+n-1
reverse(a,n,m+n-1);
}
两个函数组成,前面的复杂翻转,后面的控制翻转
reverse(a,0,m+n-1); //整个翻转 AB--->B-A-
reverse(a,0,n-1); //前面翻转 B----->B
reverse(a,m,m+n-1); //后面翻转 A------>A
实现了AB-->BA
int a[7]={1,2,3,4,7,8,9};
exchange(a,4,3);
for(int i=0;i<7;i++){
cout <<a[i]<<endl;
}
结果
7
8
9
1
2
3
4
==9==
image-20210331110514583
快速查找,只能用二分法
//--------9
//找到元素的位置 表 元素的值
void exchange2(int mid,Dynamiclist & l){
if( mid!=l.length-1){
int temp;
temp=l.data[mid];
l.data[mid]=l.data[l.length-1];
l.data[l.length-1]=temp;
}
}
void insert(Dynamiclist &l,int index,int x){
for(int i=l.length;i>index+1;i--){
l.data[i]=l.data[i-1];
}
l.data[index+1]=x;
//别忘了长度
l.length++;
}
//那么这里传入的必须是引用类型,因为后面insert也要用这个参数
void search(Dynamiclist &l,int x){
int low=0;
int high=l.length-1;
int mid;
while(low<=high){
mid=(low+high)/2;
if(l.data[mid]==x){
//找到了
break;
}
if(l.data[mid]<x){
low=mid+1;
}
else{
high=mid-1;
}
}
//是否需要插入
if(low>high){
//插入在high的后面
insert(l,high,x);
}
else exchange2(mid,l);
}
运行
//9
Dynamiclist p;
initDynamicList(p);
insertList(p,1,1);
insertList(p,2,3);
insertList(p,3,5);
insertList(p,4,6);
insertList(p,5,7);
insertList(p,6,9);
printList(p);
cout<<"---------"<<endl;
//查找不存在的8
search(p,8);
cout<<"查找不存在的8"<<endl;
printList(p);
cout<<p.length<<endl;
cout<<"---------"<<endl;
//查找6
search(p,6);
cout<<"查找6"<<endl;
printList(p);
结果
第1个元素是1
第2个元素是3
第3个元素是5
第4个元素是6
第5个元素是7
第6个元素是9
---------
查找不存在的8
第1个元素是1
第2个元素是3
第3个元素是5
第4个元素是6
第5个元素是7
第6个元素是8
第7个元素是9
7
---------
查找6
第1个元素是1
第2个元素是3
第3个元素是5
第4个元素是9
第5个元素是7
第6个元素是8
第7个元素是6
第四部分
10
image-20210331113512486
要求空间和时间都高效,就没有新建一个顺序表的做法了
循环左移,和之前那个翻转的很像
这里和前面那个不同,用的是位序,而不是下标
//10
//翻转的位序从begin到last
void reverse2(int a[],int begin,int last){
int mid=(begin+last)/2;
for(int i=0;i<=(mid-begin);i++){
int temp=a[begin+i-1];
a[begin+i-1]=a[last-1-i];
a[last-1-i]=temp;
}
}
//前一部分m个 后一部分n个 注意这里翻转用的是位序所以不用0到m+n-1
void exchange3(int a[],int m,int n){
reverse2(a,1,m+n);
reverse2(a,1,n);
reverse2(a,n+1,m+n);
}
运行
//10
int a[7]={1,2,3,4,7,8,9};
exchange3(a,4,3);
for(int i=0;i<7;i++){
cout <<a[i]<<endl;
}
结果
7
8
9
1
2
3
4
时间复杂度o(n) 空间复杂度o(1)
解法2
void ten(int a[],int m,int n){
// int b[m];栈溢出
int* b = new int[m];
//把a数组的前面m个放到新数组b里
for(int i=0;i<m;i++){
b[i]=a[i];
}
//a数组前移m个位置 注意n只是后面的个数,所以用m来定位
for(int i=m,j=0;i<m+n;){
a[j++]=a[i++];
}
//把b数组里面的放回来
for(int i=0;i<m;i++ ){
a[n+i]=b[i];
}
演示
cout<<"解法2"<<endl;
int b[7]={1,2,3,4,7,8,9};
ten(b,4,3);
for(int i=0;i<7;i++){
cout <<b[i]<<endl;
}
结果
解法2
7
8
9
1
2
3
4
==11==
image-20210331132228050
如果排序后,再找中间的位置,比较麻烦
注意这里的中间位置指L/2向下取整
两个找中位数的序列长度相等
image-20210331134819630
理解一下.若分别求出的中文数不相同,那么说明,小的前一半以及大的那一半中,一定找不到中位数,n (n n) n
注意排除的长度要相等
int searchMid(int a[],int b[],int n){
int a1=0; //a数组的头 下标
int a2=n-1; //尾下标
int m1; //中间位置下标
int b1=0;
int b2=n-1;
int m2;
while(a1!=a2&&b1!=b2){
m1=(a2+a1)/2;//注意是+号
m2=(b2+b1)/2;
if (a[m1]==b[m2]){
return a[m1];
}
else if(a[m1]>b[m2]){ //舍弃a的后半部分b的前半部分
if((a2-a1+1)%2==0){ //长度为偶数
//a保留中间的删除后面的
//b保留后面的不包括中间
//实现删除的长度相同
a2=m1;
b1=m2+1;
}else{
a2=m1;
b1=m2;
}
}else {
//if(n%2==0){ 典型错误,不是总表的长度,而是新表
if((a2-a1+1)%2==0){
//长度为偶数
//a保留中间的删除后面的
//b保留后面的不包括中间
//实现删除的长度相同
b2=m2;
a1=m1+1;
}else{
b2=m2;
a1=m1;
}
}
}
return a[a1]<b[b1]?a[a1]:b[b1]; //升序,注意是a[a1]而不是a[m1]
}
运行
int a[]={1,3,5,7};
int b[]={2,4,6,8};
cout<<"中位数是"<<searchMid(a,b,4)<<endl;
int a2[]={1,3,5,7,9};
int b2[]={2,4,6,8,11};
cout<<"中位数是"<<searchMid(a2,b2,5)<<endl;
结果
中位数是4
中位数是5
第五部分
==12==
image-20210401090330048
image-20210401090600098
int findMost(int a[],int n){
int count=1;
int c=a[0];
//int n=(sizeof(a)/sizeof(a[0])) ;//数组长度
for(int i=1;i<n;i++){
if(a[i]==c){
count++;
}
else{
if(count>0){
count--;
}
else{
c=a[i];
//别忘了这句
count =1;
}
}
}
if(count>0){
count=0;
for(int i=0;i<n;i++){
if(c==a[i]){
count ++;
}
}
}
if(count>n/2){
return c;
}
return -1;
}
运行
//12
int a[]={1,2,3,4,4,7,4};
int b[]={1,2,3,4,4,7,4,4,4};
int n1=sizeof(a)/sizeof(a[0]);
//注意由于数组其实是个指针,无法在函数内求长度,求的是指针的长度
int n2=sizeof(b)/sizeof(b[0]);
cout<<"a的主元素"<<findMost(a,n1)<<endl;
cout<<"b的主元素"<<findMost(b,n2)<<endl;
结果
a的主元素-1
b的主元素4
时间复杂度o(n) 空间复杂度o(1)
==13==
image-20210401090546189
空间换时间
void *memset(void *str, int c, size_t n)
- str -- 指向要填充的内存块。
- c -- 要被设置的值。该值以 int 形式传递，但是函数在填充内存块时是使用该值的无符号字符形式。
- n -- 要被设置为该值的字符数。
复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。由于只有一个字符,所以常用来初始化
int findMissMin(int a[],int n){
int i;
int *b=(int *)malloc(sizeof(int)*n);
//初始化
memset(b,0,sizeof(int)*n);//string.h
for( i=0;i<n;i++){
if(a[i]>0){
b[a[i]-1]=1;
}
}
for( i=0;i<n;i++){
if(b[i]==0){
//return i+1; 后面就返回n+1
//优化 返回i+1
break;
}
}
return i+1;
}
运行
int a[]={1,2,3,4,4,7,4};
int b[]={-1,-2,-3,-4,4,7,4};
int n1=sizeof(a)/sizeof(a[0]);
int n2=sizeof(b)/sizeof(b[0]);
cout<<"a缺少的最小正元素"<<findMissMin(a,n1)<<endl;
cout<<"b缺少的最小正元素"<<findMissMin(b,n2)<<endl;
结果
a缺少的最小正元素5
b缺少的最小正元素1
bug
编译运行无故出现 Cannot open output file：Permission denied可尝试的解决办法
关掉vscode,重新打开
变量未初始化----->变量重复定义
