2024王道数据结构课后习题代码

2024王道数据结构课后习题代码

文章目录

• **2024王道数据结构课后习题代码**
• 前言
• • • 这篇文章中的题都是2024年王道考研数据结构中的题，2.2.1即为第2.2课的课后第一题。我是代码小白，希望可以和各位大佬交流学习！
• 第二章、线性表
• • 2.1课程里的顺序表初始化，动/静态分配内存
  • • 2.1.1 顺序表初始化（静态）
    • 2.1.2 顺序表初始化（动态）
    • 2.1.3 顺序表上插入和删除
  • 2.2综合题
  • • 2.2.1 顺序表删最小值
    • 2.2.2 顺序表O(1)逆序
    • 2.2.3 顺序表删特定值
    • 2.2.4 删除给定值之间
    • 2.2.5 删除值在给定值之间
    • 2.2.6 删重复元素
    • 2.2.7 合并有序顺序表
    • 2.2.8数组中交换顺序表位置
    • 2.2.9 查找并插入
    • 2.2.10 向左循环移动
    • 2.2.11 两个序列的中位数
    • 2.2.12
    • 2.2.13
  • 朋友们，我来更新了，有没有想我😊
  • 2.2单链表
  • • 2.2.1 单链表的建立
• 未完待续... 2023年五月末之前将更新完本书所有习题

前言

这篇文章中的题都是2024年王道考研数据结构中的题，2.2.1即为第2.2课的课后第一题。我是代码小白，希望可以和各位大佬交流学习！

第二章、线性表

2.1课程里的顺序表初始化，动/静态分配内存

2.1.1 顺序表初始化（静态）

#include 
#define MaxSize 100
struct Sqlist {int data[MaxSize];int length = 0;
};
void InitList(Sqlist &l)
{for (int i = 0;i < MaxSize;i++){l.data[i] = 0;}l.length = 0;
}
int main()
{Sqlist L;InitList(L);for (int i = 0;i < MaxSize;i++){printf("第%d个数据元素是：%d\n", i+1, L.data[i]);}return 0;
}

2.1.2 顺序表初始化（动态）

#include
#include
#define InitSize 10
typedef struct {int *data;int MaxSize;int length;
}SqList;
void InitList(SqList &l) {l.data = (int*)malloc(InitSize * sizeof(int));l.MaxSize = InitSize;l.length = 0;
}
void  IncreaseSize(SqList& l, int morespace)
{int* p = l.data;l.data = (int*)malloc((InitSize + morespace) * sizeof(int));for (int i = 0;i < InitSize;i++){l.data[i] = p[i];}l.MaxSize = InitSize + morespace;free(p);
}
int main()
{SqList L;InitList(L);IncreaseSize(L,5);for (int i = 0;i < L.MaxSize;i++){printf("第%d个数据元素是:%d\n", i + 1, L.data[i]);S}return 0;
}

2.1.3 顺序表上插入和删除

#include 
#include
#define maxsize 20
struct SqList{int data[maxsize];int length=0;};
void InitList(SqList &l)
{for(int i=0;i<maxsize;i++){l.data[i]=0;}l.length=0;
}
void print(SqList &l)
{printf("\n");printf("\n该顺序表元素为：\n");for(int i=0;i<l.length;i++){printf(" %d ",l.data[i]);}printf("\n共有%d个元素\n",l.length);}
void DenifyList(SqList &l)
{int n,a,b;//顺序表长度 printf("请输入你的顺序表数据元素数量：\n");scanf("%d",&n);
//	printf("请输入数据范围a-b：\n");
//	scanf("%d,%d",&a,&b);for(int i=0;i<n;i++){l.data[i]=1+rand()%10;//成1-10随机数 m-n m+rand()%(n-m+1);//scanf("%d",&l.data[i]);l.length++;}print(l);}
void deleteList(SqList &l,int loc)
{printf("\n你要删的是第%d个数据，%d",loc,l.data[loc-1]);for(int i=loc;i<l.length;i++){l.data[i-1]=l.data[i];}l.length--;
}
void increaseList(SqList &l,int loc,int num)
{printf("\n你要在第%d位置插入数%d",loc,num);for(int i=l.length;i>=loc;i--){l.data[i]=l.data[i-1];}l.data[loc-1]=num;l.length++;}int main()
{SqList L;InitList(L);DenifyList(L);deleteList(L,3);increaseList(L,3,3);print(L);return 0;}

2.2综合题

这些题是王道教材的p18-p19的1-14题，2.2.1即为综合题第一题

2.2.1 顺序表删最小值

从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

bool test1(SqList &l)
{if(l.length==0)return false;print(l);int value=l.data[0],pos=0;//设置擂主的值和位置for(int i=1;i<l.length;i++){if(l.data[i]<value){value=l.data[i];pos=i;}} printf("最小的数据是%d,他在第%d个位置",value,pos+1);l.data[pos]=l.data[l.length-1];l.length--;print(l);} 

2.2.2 顺序表O(1)逆序

02．设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

void test2(SqList &l)
{print(l);int temp=0;//交换对称位置的数for(int i=0;i<=(l.length-1)/2;i++)//需要小于等于 ？ 如果<，中间两个换不过来 {temp=l.data[i];l.data[i]=l.data[l.length-1-i];l.data[l.length-1-i]=temp; 		} print(l);
}

2.2.3 顺序表删特定值

03.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

void test3(SqList &l,int key)
{printf("进入test3！\n");int mark=0;//标记几处有key值 for(int i=0;i<l.length;i++){if(l.data[i]==key){mark++;continue;}//printf("mark值为：%d\n",mark);l.data[i-mark]=l.data[i];  }l.length-=mark;print(l);} 

2.2.4 删除给定值之间

04、从有序顺序表中删除其值在给定值s与t之间(要求s

bool test4(SqList &l){int s,t;//范围 int i,j;//定位 printf("请输入s和t的值：");scanf("%d%d",&s,&t);if(l.length==0||s>t)return false;for(i=0;l.data[i]<s&&i<l.length;i++);//用i定位第一个大于等于s的元素的位置printf("\n%d",i);if(i>l.length)return false;for(j=i;j<l.length&&l.data[j]<=t;j++);//用j定位第一个小于t的元素的位置printf("\n%d,%d",i,j);  for(;j<l.length;i++,j++)//将j后的元素都覆盖到i后  l.data[i]=l.data[j];//j的最后一次覆盖是j=l.lenth-1,jl.length=i;//i在刚才的循环中被加到当前表长 ,print(l);return true;}

2.2.5 删除值在给定值之间

05．从顺序表中删除其值在给定值s与t之间(包含s和t，要求s

bool test5(SqList &l){int s,t;//范围 int mark=0;//标记符合范围的数据元素 printf("请输入s和t的值：");scanf("%d%d",&s,&t);if(l.length==0||s>t)return false;for(int i=0;i<l.length;i++){if(l.data[i]>=s&&l.data[i]<=t){mark++;continue; }l.data[i-mark]=l.data[i];}l.length-=mark;print(l);return true;  	}

2.2.6 删重复元素

06．从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

 void test6(SqList &l){int mark=0;for(int i=0;i<l.length;i++){if(l.data[i]==l.data[i+1]){mark++;continue;}l.data[i-mark]=l.data[i];}l.length-=mark;print(l);
}

2.2.7 合并有序顺序表

07．将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

bool test7(SqList l1,SqList l2,SqList &l3)
{if (l1.length+l2.length>maxsize)//顺序表的最大长度return false;int i=0,j=0,k=0;while(i<l1.length&&j<l2.length)//一个到头了就停止{if(l1.data[i]<=l2.data[j]) l3.data[k++]=l1.data[i++];elsel3.data[k++]=l2.data[j++];} while(i<l1.length)l3.data[k++]=l1.data[i++];while(j<l2.length)l3.data[k++]=l2.data[j++];l3.length=k;print(l3);return true;
}

2.2.8数组中交换顺序表位置

08.已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3,…, am)和(b1, b2, b3,…,bn)。编写一个函数,将数组中两个顺序表的位置互换,即将(b1, b2, b3…,bn
,)放在(a1, a2 a3…,am")的前面。

bool reverse(int start,int end,SqList &l)//翻转 （参考第二题方法） 
{if(end>=l.length||start>=end)return false;int temp=0;//交换对称位置的数int mid=(start+end)/2;for(int i=0;i<=mid-start;i++)//需要小于等于 ？ 如果<，中间两个换不过来 {temp=l.data[start+i];l.data[start+i]=l.data[end-i];l.data[end-i]=temp; 		} print(l);return true;
}
void test8(SqList l,int n) //顺序表是m+n把n的部分放到m的前面，相当于顺序表整体反转，m和n的部分再各自翻转 
{reverse(0,l.length-1,l);//整体翻转 reverse(0,n-1,l);//翻转m部分 reverse(n,l.length-1,l);//翻转n部分 }

2.2.9 查找并插入

09.线性表(a, a2s a3,s…, an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。

bool test9(SqList &l)
{int x; printf("请输入你要查找的数；");scanf("%d",&x) ;for(int i=0;i<l.length;i++){if(l.data[i]==x){printf("找到了！他在第%d个位置",i+1); int temp=0;temp=l.data[i+1];l.data[i+1]=l.data[i];l.data[i]=temp;print(l);return true;}else if(l.data[i]<x&&l.data[i+1]>x){for(int j=l.length-1;j>=i+1;j--) {l.data[j+1]=l.data[j];}l.data[i+1]=x;l.length++;printf("没找到，已插入！");print(l);return true;}}} 

2.2.10 向左循环移动

10.【2010统考真题】设将n (n >1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0 1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。

//和第8题一样
bool reverse(int start,int end,SqList &l)//翻转 （参考第二题方法） 
{if(end>=l.length||start>=end)return false;int temp=0;//交换对称位置的数int mid=(start+end)/2;for(int i=0;i<=mid-start;i++)//需要小于等于 ？ 如果<，中间两个换不过来 {temp=l.data[start+i];l.data[start+i]=l.data[end-i];l.data[end-i]=temp; 		} print(l);return true;
}
void test10(SqList l,int n) //n为循环向左移的数量,顺序表是p+n把n的部分放到p的前面，相当于顺序表整体反转，p和n的部分再各自翻转 
{reverse(0,l.length-1,l);//整体翻转 reverse(0,n-1,l);//翻转p部分 reverse(n,l.length-1,l);//翻转n部分 }

2.2.11 两个序列的中位数

11.【2011统考真题】一个长度为L(L≥1)的升序序列S，处在第[L/2个位置的数称为S的中位数。例如，若序列S=(11,13,15,17,19)，则S的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S1=(2,4,6,8,20)，则S和S1的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求:
1)给出算法的基本设计思想。
2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。

void test11(SqList l1,SqList l2)//时间复杂度O(n),空间复杂度O(1)
{int i=0,j=0; for(int k=0;k<(l1.length+l2.length)/2-1;k++)//直接找到中位数所在位置的那个数 {if(l1.data[i]>l2.data[j])j++;elsei++;	}printf("中位数为：%d",l1.data[i]);
}

最优算法：
算法的基本设计思想如下。
分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下:
若a= b，则a或b即为所求中位数，算法结束。
若a 长度相等。
③若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的
长度相等。
在保留的两个升序序列中，重复过程①、②、③，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。

int test11_best(SqList l1,SqList l2)//时间复杂度为O(log2(n)),空间复杂度为O(1)
{int start1=0,end1=l1.length-1,mid1,start2=0,end2=l2.length-1,mid2;//start,end,mid分别是首位数，末位数，中位数 while(start1!=end1||start2!=end2){mid1=(start1+end1)/2;mid2=(start2+end2)/2;if(l1.data[mid1]==l2.data[mid2]) return l1.data[mid1];//两个中位数相等，结束 if(l1.data[mid1]<l2.data[mid2])//l1的中位数比l2的中位数小 {if((start1+end1)%2==0)//l1+l2偶数个 {start1=mid1;//l1中间点之前的舍弃，保留中间点 end2=mid2;//l2中间点之后的舍弃，保留中间点 }else{start1=mid1+1;//l1不保留中间点 end2=mid2;} } else//l1的中位数比l2的中位数大 {if((start1+end1)%2==0)//l1+l2偶数个 {end1=mid1;//l1中间点之后的舍弃，保留中间点 start2=mid2;//l2中间点之前的舍弃，保留中间点 }else{start2=mid2+1;//l2不保留中间点 end1=mid1;} }}return l1.data[start1]<l2.data[start2]?l1.data[start1]:l2.data[start2]; 
}

2.2.12

12.【2013统考真题】已知一个整数序列A=(a0, a1,… , an-1)，其中0≤ain/2 ( 0≤p; 1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法,关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

在这里插入代码片

2.2.13

13.【2018统考真题】给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高
效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:
1)给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。

在这里插入代码片

14.【2020统考真题】定义三元组(a, b, c) ( a,b, c均为整数）的距离D= |a-b| + |b-c| +|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b, c) (a属于S1，b属于S2，c属于S3）中的最小距离。例如S1={-1,0,9}，S2={-25,-10,10,11}，S3={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10, 9)。要求:
1）给出算法的基本设计思想。
2）根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

在这里插入代码片

朋友们，我来更新了，有没有想我😊

2.2单链表

2.2.1 单链表的建立

1.尾插法

 //尾插法建立单链表LinkList List_tailInsert(LinkList &L){int x;L=(LinkList)malloc(sizeof(LNode));//建立头节点LNode *s,*r=L;L->length=0;printf("\n请输入第一个结点的值：");scanf("%d", &x);	while(x!=99){//99是自己设的，一旦输入99，链表就会停止插入 L->length++;s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;//尾指针指向新的结点printf("\n请输入下一个结点的值：");scanf("%d", &x);  	}r->next=NULL; //尾结点指针为空 return L;}

2.头插法
头插法就是不断地对头结点进行尾插（你品，你细品）

 //头插法建立链表,头插法适合考虑将数表逆转 
LinkList List_headInsert(LinkList &L){LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));L->next=NULL; printf("\n请输入结点的值：");scanf("%d", &x);while(x!=99){//99是自己设的，一旦输入99，链表就会停止插入 L->length++;s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;//头节点更新位置 printf("\n请输入下一个结点的值：");scanf("%d", &x);  	}return L; } 

3.单链表的插入与删除

未完待续… 2023年五月末之前将更新完本书所有习题

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！