P17
08
#include <stdio.h>
#include<iostream>
using namespace std;
void reverse(int a[],int n,int m,int size)
{
for(int i=0;i<size;i++){
a[i]=i+1;
}
for(int i=0;i<size;i++)
cout<<a[i]<<" ";
cout<<endl;
int temp[n];
for(int i=0;i<n;i++)
{
temp[i]=a[i];
}
for(int j=n;j<size;j++){
//TODO
a[j-n]=a[j];
//cout<<a[j]<<" ";
}
//cout<<endl;
for(int k=m,i=0;k<size;k++)
a[k]=temp[i++];
for(int i=0;i<size;i++)
cout<<a[i]<<" ";
}
int main(){
int n=8;
int m=9;
int size=n+m;
int a[size];
reverse(a,n,m,size);
return 0;
}
10(2010统考真题)
基本设计思想:
1.先用一个临时数组用来存储需要往后移的部分数据
2.再将P后面的数据往前移
3.最后将放在临时数组中的元素移动到原数组的后面
#include<iostream>
using namespace std;
void left_p(int a[],int p,int n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
int temp[p];
for(int i=0;i<p;i++)//用另外一个数组暂存要往后移的数
{
temp[i]=a[i];
}
for(int j=p;j<n;j++)//p后面的数据前移
{
a[j-p]=a[j];
}
for(int k=n-p,i=0;k<n;k++)//将原来的p个数移到后面
{
a[k]=temp[i++];
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
int main(){
int n,p;
scanf("%d%d",&n,&p);
int a[n];
for(int i=0;i<n;i++)
{
a[i]=i+1;
}
left_p(a,p,n);
return 0;
}
时间复杂度:O(n)
空间复杂度:O(p)?
11(2011统考真题)
基本思想:
1.先将两个数组进行按序合并
2.再找出中位数进行输出
#include<iostream>
using namespace std;
void search_z(int a[],int b[],int c[],int L)
{
int i=0,j=0,k=0;
while(i<L && j<L)//将两个数组进行按序合并
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
}
while(i<L)
c[k++]=a[i++];
while(j<L)
c[k++]=b[j++];
for(int g=0;g<2*L;g++)//测试结果是否已按序排列
cout<<c[g]<<" ";
cout<<endl;
int z=(2*L+1)/2;//生成中位数
cout<<c[z-1];
}
int main(){
int L=5;
//scanf("%d",&L);
int a[L]={11,13,15,17,19};
int b[L]={2,4,6,8,20};
int c[2*L];
search_z(a,b,c,L);
return 0;
}
时间复杂度O(n)
空间复杂度O(n)
12(2013统考真题)
基本思想:用一个变量来对出现的次数进行统计,再用另一个变量来统计出现最多的次数
用这个统计最多次数的变量与n/2进行比较来确定是不是主元素
每次统计最多次数的变量变化时,就将相应的元素记录下来,可以在后续进行输出
#include<iostream>
#include<algorithm>
using namespace std;
void main_elem(int a[],int n)
{
sort(a,a+n);//这里排序算法还没学,暂时用sort来排序
int max_count=0,max_elem=-1;//用max_count变量来记录出现最多的次数,max_elem记录出现次数最多的元素
int count=1;
for(int i=0;i<n;i++)
{
if(a[i+1]==a[i]) count++;//count统计出现次数
else count=1;
if(count>max_count)
{
max_count=count;
max_elem=a[i];
//count=1;
}
}
for(int i=0;i<n;i++){
//TODO
cout<<a[i]<<" ";
}
cout<<endl;
//cout<<max_count<<endl;
if(max_count>n/2) cout<<max_elem;
else cout<<-1;
}
int main()
{
int n=8;
int a[n]={0,5,5,3,5,7,5,5};//{0,5,5,3,5,1,5,7}
main_elem(a,n);
return 0;
}
时间复杂度O(n)
空间复杂度O(n)
13(2018统考真题)
基本思想:
新建一个数组,将原来数组中出现的值映射为新数组的下标,并将该下标位置的值赋为1
最后遍历新数组,值不为1就是未出现的最小整数
有一种特殊情况就是刚好完全映射,所以也要考虑到这种情况
#include<iostream>
#include<algorithm>
using namespace std;
void find_min(int a[],int n)
{
int b[n];
for(int i=1;i<=n;i++)//初始化新数组
{
b[i]=0;
}
for(int j=0;j<n;j++)//将原数组的值映射为新数组的下标
{
if(a[j]>0) b[a[j]]=1;
}
for(int i=1;i<=n+1;i++)
{
if(i==n+1)//刚好完全映射,输出n+1
{
cout<<n+1;
return ;
}
if(b[i]==0) //输出最小正整数
{
cout<<i;
return ;
}
}
}
int main()
{
int n;
cout<<"输入数组长度:";
scanf("%d",&n);
int a[n];
cout<<"输入数组元素:";
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
find_min(a,n);
return 0;
}
时间复杂度:O(n)
空间复杂度:O(n)----开辟了一个新的数组
14(2020统考真题)
基本思想:
三重for循环,暴力依次算出各个三元组的距离,然后输出最小的距离
#include<iostream>
#include<algorithm>
using namespace std;
void find_min(int a[],int an,int b[],int bn,int c[],int cn)
{
int min=999999999;
for(int i=0;i<an;i++)
{
for(int j=0;j<bn;j++)
{
for(int k=0;k<cn;k++)
{
int temp=abs(a[i]-b[j])+abs(b[j]-c[k])+abs(c[k]-a[i]);
if(temp<min) min=temp;
}
}
}
cout<<min;
}
int main()
{
int an=3,bn=4,cn=4;
int a[an]={-1,0,9};
int b[bn]={-25,-10,10,11};
int c[cn]={2,9,17,30,41};
find_min(a,an,b,bn,c,cn);
return 0;
}
时间复杂度O(n^3)
空间复杂度O(n)
P39
22(2009统考真题)
基本思想:
1.用两个指针p和q分别指向链表头结点的下一个结点
2.p指针先向后移动,当p指针到达k个位置时,q指针也开始向后扫描
3.设置一个变量count用来判断指针p是否已到达k的位置
4.如果count到达了k,说明能够找到倒数第k个值,返回1;否则说明链表长度小于k,查找失败,返回0
函数代码:
int search_k(LinkList list,int k)
{
LNode *p=list->link,*q=list->link;//p,q都指向头结点的下一个结点
int count=0;//count初始为0用来计数
while(p!=NULL)
{
//TODO
if(count<k) count++;
else q=q->link;//count到达k之后,p指针才开始向后移动
p=p->link;//p从刚开始就一直向后移
}
if(count<k) return 0;//如果count的值没有到达k,说明链表长度小于k,查找失败
else
{
cout<<q->data;
return 1;
}
}
完整代码:
#include<iostream>
using namespace std;
typedef struct LNode{
int data;
struct LNode* link;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL) return false;
L->link=NULL;
return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
if(i<1) return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i-1)
{
p=p->link;
j++;
}
if(p==NULL)
{
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->link=p->link;
p->link=s;
return true;
}
int search_k(LinkList list,int k)
{
LNode *p=list->link,*q=list->link;
int count=0;
while(p!=NULL)
{
//TODO
if(count<k) count++;
else q=q->link;
p=p->link;
}
if(count<k) return 0;
else
{
cout<<q->data;
return 1;
}
}
int main()
{
LinkList L;
InitList(L);
for(int i=1;i<=7;i++)
{
ListInsert(L,i,i);
}
search_k(L,2);
return 0;
}
23(2012统考真题)
基本思想:
1.定义两个指针分别指向两个单词所在单链表的头结点
2.计算两个单链表长度,让长的单链表的指针先行移动,直到两个指针所在的结点到表尾的长度相同
3.然后两个指针再开始同时移动,直到两个指针指向同一位置时停止,即共同后缀的起始位置
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*Linklist;
int length(LinkList L)
{
int len=0;
LNode *p=L;
while(p->next!=NULL)
{
p=p->next;
len++;
}
return len;
}
LNode* find_add(LinkList str1,LinkList str2)
{
int m=length(str1);
int n=length(str2);
LNode *p=str1,*q=str2;
for(;m>n;m--)
{
p=p->next;
}
for(;m<n;n--)
{
q=q->next;
}
while(p->next!=NULL && p->next!=q->next)
{
p=p->next;
q=q->next;
}
return p->next;
}
时间复杂度:O(max(len1,len2))
24(2015统考真题)
基本思想:
采取空间换时间的思想,和之前一道题(p17的13(2018统考真题))的想法差不多,就是将原链表中的值映射为一个新数组的下标,如果第一次出现,就把该下标对应的位置的值赋为1,如果不是第一次出现,就把该结点删除
void del_repeat(LinkList L,int n)
{
LNode *p=L,*r;
int *q,m;
q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n,算上0就是n+1
for(int i=0;i<=n;i++)//数组元素初值为0,初始化
{
*(q+i)=0;
}
while(p->link!=NULL)
{
m=p->link->data>0?p->link->data:-p->link->data;//避免使用abs函数,用一个三目运算符实现取反
if(*(q+m)==0)//为0表示,该结点的值是第一次出现,然后赋值为1
{
*(q+m)=1;
p=p->link;
}
else//如果不是第一次出现,就删除结点
{
r=p->link;
p->link=r->link;
free(r);
}
}
free(q);
}
时间复杂度O(m)
空间复杂度O(n)
完整试验代码:
#include<iostream>
using namespace std;
typedef struct LNode{
int data;
struct LNode* link;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL) return false;
L->link=NULL;
return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
if(i<1) return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i-1)
{
p=p->link;
j++;
}
if(p==NULL)
{
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->link=p->link;
p->link=s;
return true;
}
int length(LinkList L)
{
int len=0;
LNode *p=L;
while(p->link!=NULL)
{
p=p->link;
len++;
}
return len;
}
void ListTraver(LinkList L)
{
LNode *p=L->link;
while(p->link!=NULL)
{
cout<<p->data<<" ";
p=p->link;
}
cout<<p->data<<endl;
}
bool Del_node(LNode *p)
{
if(p==NULL) return false;
LNode *q=p->link;
p->data=q->data;
p->link=q->link;
free(q);
return true;
}
void del_repeat(LinkList L,int n)
{
LNode *p=L,*r;
int *q,m;
q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n,算上0就是n+1
for(int i=0;i<=n;i++)//数组元素初值为0,初始化
{
*(q+i)=0;
}
while(p->link!=NULL)
{
m=p->link->data>0?p->link->data:-p->link->data;//避免使用abs函数,用一个三目运算符实现取反
if(*(q+m)==0)
{
*(q+m)=1;
p=p->link;
}
else
{
r=p->link;
p->link=r->link;
free(r);
}
}
free(q);
}
int main()
{
LinkList L;
InitList(L);
ListInsert(L,1,3);
ListInsert(L,2,-3);
ListInsert(L,3,4);
ListInsert(L,4,5);
ListInsert(L,5,-5);
int n=5;
ListTraver(L);
del_repeat(L,n);
ListTraver(L);
// cout<<length(L);
return 0;
}
25(2019年统考真题)
基本思想:
1.先用两个指针p,q指向第一个结点(头结点的下一个结点),然后p每次移动一个位置,q移动两个位置,从而找到中间的位置
2.接着将后半部分的链表以头插法的形式进行逆置(相当于一个链表拆分成两个)
3.将后半部分的元素逐个插入到前半部分中
函数代码:
void change_list(LinkList L)
{
LNode *p,*q,*r,*s;
p=L,q=L;
while(q->next!=NULL)//寻找中间结点
{
p=p->next;
q=q->next;
if(q->next!=NULL) q=q->next;//q每次走两步
}
q=p->next;
p->next=NULL;
while(q!=NULL)//单链表逆置,先插进去的会在后面
{
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
s=L->next;//s指向单链表的第一个位置
q=p->next;//p一直指向的都是中间位置没有变化
p->next=NULL;
while(q!=NULL)
{
r=q->next;
q->next=s->next; //将q插入到第一个结点的后面
s->next=q;
s=q->next; //s指向下一个插入点
q=r;
}
}
完整试验代码:
#include<iostream>
using namespace std;
typedef struct LNode{
int data;
struct LNode* next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL) return false;
L->next=NULL;
return true;
}
bool ListInsert(LinkList &L,int i,int e)
{
if(i<1) return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i-1)
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
int length(LinkList L)
{
int len=0;
LNode *p=L;
while(p->next!=NULL)
{
p=p->next;
len++;
}
return len;
}
void ListTraver(LinkList L)
{
LNode *p=L->next;
while(p->next!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<p->data<<endl;
}
//bool Del_node(LNode *p)
//{
// if(p==NULL) return false;
// LNode *q=p->next;
// p->data=q->data;
// p->next=q->next;
// free(q);
// return true;
//}
void del_repeat(LinkList L,int n)
{
LNode *p=L,*r;
int *q,m;
q=(int *)malloc(sizeof(int)*(n+1));//因为data的值不超过n,算上0就是n+1
for(int i=0;i<=n;i++)//数组元素初值为0,初始化
{
*(q+i)=0;
}
while(p->next!=NULL)
{
m=p->next->data>0?p->next->data:-p->next->data;//避免使用abs函数,用一个三目运算符实现取反
if(*(q+m)==0)
{
*(q+m)=1;
p=p->next;
}
else
{
r=p->next;
p->next=r->next;
free(r);
}
}
free(q);
}
LinkList Reverse(LinkList L)
{
LNode *p,*r;
p=L->next;
L->next=NULL;
while(p!=NULL)
{
r=p->next;
p->next=L->next;
L->next=p;
p=r;
}
return L;
}
void change_list(LinkList L)
{
LNode *p,*q,*r,*s;
p=L,q=L;
while(q->next!=NULL)//寻找中间结点
{
p=p->next;
q=q->next;
if(q->next!=NULL) q=q->next;//q每次走两步
}
q=p->next;
p->next=NULL;
while(q!=NULL)//单链表逆置,先插进去的会在后面
{
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
s=L->next;//s指向单链表的第一个位置
q=p->next;//p一直指向的都是中间位置没有变化
p->next=NULL;
while(q!=NULL)
{
r=q->next;
q->next=s->next; //将q插入到第一个结点的后面
s->next=q;
s=q->next; //s指向下一个插入点
q=r;
}
}
int main()
{
LinkList L;
InitList(L);
int n=6;
for(int i=1;i<=n;i++)
{
ListInsert(L,i,i);
}
ListTraver(L);
change_list(L);
ListTraver(L);
return 0;
}
时间复杂度:O(n)
标签:LNode,int,next,LinkList,link,习题,NULL,线性表 From: https://www.cnblogs.com/Jinx8823/p/17467535.html