2021王道数据结构——线性表课后大题_1

2023-10-21 05:38
文章标签 数据结构 王道 线性表 2021 课后 大题

本文主要是介绍2021王道数据结构——线性表课后大题_1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表的顺序表示课后大题——P19–P21
有几个必须掌握的算法

  1. 归并排序
    P19.7
    P20.11
  2. 用空间换时间——有n个元素就开一个大小为n的数组
    P20.12
    P21.13
  3. 离散数学中的矩阵的预算规则
    P19.8
    P20.10

全部代码如下，代码中已给出题目

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;#define MAX 30
#define _for(i,a,b) for( int i=(a); i<(b); ++i)
#define _rep(i,a,b) for( int i=(a); i<=(b); ++i)typedef struct {int data[MAX];int length;
}List;void swap(int* a, int* b) {int t;t = *a;*a = *b;*b = t;
}//给定一个List，传入List的大小，要逆转的起始位置
void Reserve(List* list, int start, int end, int size) {if (end <= start || end >= size) {return;}int mid = (start + end) / 2;_rep(i, 0, mid - start) {swap(&list->data[start + i], &list->data[end - i]);}/*  _for(i, 0, list->length) {printf("%d ", list->data[i]);}*/
}//P19.1
//从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位
//置由最后一个元素填补, 若顺序表为空则显示出错信息并退出运行
int FindMin(List* list)
{if (!(*list).length) {printf("Error!\n");return -1;}int Min = 9999;int point;for (int i = 0; i < (*list).length; i++){if ((*list).data[i] < Min){Min = (*list).data[i];point = i;}}(*list).data[point] = (*list).data[(*list).length - 1];(*list).length -= 1;return Min;
}//P19.2
//设计一个高效算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O⑴
void reverse(List* list) {if (!list->length)return;for (int i = 0; i < (*list).length / 2; i++) {swap(&(list->data[i]), &(list->data[list->length - i - 1]));}
}//P19.3
//对长度为n的顺序表L, 编写一个时间复杂度为O(m)空间复杂度为O(1)的算法,
//该算法删除线性表中所有值为x的数据元素
void DeleteX(List* list, int X) {for (int i = 0; i < (*list).length; i++) {if ((*list).data[i] == X) {for (int j = i + 1; j < (*list).length; j++) {(*list).data[j - 1] = (*list).data[j];}(*list).length -= 1;break;}}
}//P19.4
//从有序顺序表中删除其值在给定值s与t之间(要求s < t)的所有元素, 如果s或t不合
//理或顺序表为空, 则显示出错信息并退出运行
void OrderlyDelete(List* list, int X, int T) {int i = 0, j = 0;for (i; i < (*list).length; i++)if ((*list).data[i] >= X)break;for (j; j < (*list).length; j++) {if ((*list).data[j] > T)break;}int len = j - 1;for (i; i < (*list).length; i++, j++) {list->data[i] = list->data[j];}list->length -= len;
}//P19.5
//从顺序表中删除其值在给定值s与t之间(包含s和t, 要求s < t)的所有元素,
//如果s或t不合理或顺序表为空, 则显示出错信息并退出运行
void DeleteS_T(List* list, int S, int T) {if (S >= T || !list->length)return;for (int i = 0; i < (*list).length; i++) {if ((*list).data[i] >= S && (*list).data[i] <= T) {for (int j = i + 1; j < (*list).length; j++) {(*list).data[j - 1] = (*list).data[j];}//要重新回退一个位置，重新检测，否则会跳过某些数字if (i)i -= 1;(*list).length -= 1;}}
}//P19.6
//从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同void OlderlyDeleteSame(List* list) {for (int i = 0; i < list->length; i++) {if (list->data[i + 1] == list->data[i]) {for (int j = i + 1; j < list->length; j++) {list->data[j] = list->data[j + 1];}list->length -= 1;if (i)i -= 1;}}
}//P19.7
//将两个有序顺序表合并为一个新的有序顺序表, 并由函数返回结果顺序表List MergeList(List A, List B) {int i = 0, j = 0;List C;int k = 0;while (i < A.length && j < B.length) {if (A.data[i] >= B.data[j]) {C.data[k++] = B.data[j++];}else {C.data[k++] = A.data[i++];}}while (i < A.length) {C.data[k++] = A.data[i++];}while (j < B.length) {C.data[k++] = B.data[j++];}C.length = k;return C;
}//P19.8
//已知在一维数组A[m + n]中依次存放两个线性表(a1, a2, a3…, am)和(b, b2, b3, …, bn)。试编
//写一个函数, 将数组中两个顺序表的位置互换, 即将(b1,b2,b3,…, bn)放在(a1，a2, a3, …, am)的前面void swaplist(List* A, int m, int n, int size) {Reserve(A, 0, m + n - 1, size);Reserve(A, 0, n - 1, size);Reserve(A, n, m + n - 1, size);
}//P20.9线性表(a1,a2,a3,..,an)中的元素递增有序且按顺序存储于计算机内。
//要求设计一算法, 完成用最少时间在表中查找数值为x的元素, 若找到则将其与后继元素位置相交换,
//若找不到则将其插入表中并使表中元素仍递增有序//我的方法 大力出奇迹
void CheckAndSwap(List* A, int x) {bool flag = true;_for(i, 0, A->length) {if (A->data[i] == x) {swap(&A->data[i], &A->data[i + 1]);printf("Find it\n");flag = false;break;}}if (flag) {printf("Not find\n");int i = 0;for (i = 0; i < A->length && A->data[i] <= x; i++);if (i < A->length){for (int j = A->length; j >= i; j--) {A->data[j + 1] = A->data[j];}}A->data[i] = x;A->length += 1;}
}//答案方法 折半查找
void SearchExchangeInsert(List* A, int x) {int low = 0, mid = A->length / 2, high = A->length - 1;bool Isfind = false;while (low <= high) {mid = (low + high) / 2;if (x == A->data[mid]) {Isfind = true;printf("Find\n");break;}if (x > A->data[mid]) {low = mid + 1;}if (x < A->data[mid]) {high = mid - 1;}}if (Isfind && mid != A->length - 1) {printf("Swap\n");swap(&A->data[mid], &A->data[mid + 1]);}if (!Isfind) {int i = 0;printf("%d", low);for (i = A->length - 1; i > high; i--) {A->data[i + 1] = A->data[i];}A->data[i + 1] = x;A->length += 1;}
}//P20.10
//〖2010统考真题〗设将n(n > 1)个整数存放到一维数组R中。设计一个在时间和空间两
//方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置, 即将R中的
//	数据由(X0,X1,…,Xn-1)变换为(Xp+Xp+1…,Xn-1,X0,X1…,Xp - 1)。要求
//	1)给出算法的基本设计思想
//	2)根据设计思想, 采用C或C++ + 或Java语言描述算法, 关键之处给出注释
//	3)说明你所设计算法的时间复杂度和空间复杂度void MoveList(List* list, int MoveStep) {//BA=(A^-1*B^-1)^-1Reserve(list, 0, MoveStep - 1, MAX);Reserve(list, MoveStep, list->length - 1, MAX);Reserve(list, 0, list->length - 1, MAX);
}//P20.11
//〖2011统考真题】一个长度为L(L≥1)的升序序列S, 处在第[L/2]个位置的数称为S的
//中位数。例如, 若序列S1 = (1, 13, 15, 17, 19), 则S1的中位数是15, 两个序列的中位数
//是含它们所有元素的升序序列的中位数。例如, 若S2 = (2, 4, 6, 8, 20), 则S1和S2的中位
//数是11。现在有两个等长升序序列A和B, 试设计一个在时间和空间两方面都尽可能
//高效的算法, 找出两个序列A和B的中位数。要求
//1)给出算法的基本设计思想
//2)根据设计思想, 采用C或C++或Java语言描述算法, 关键之处给出注释
//3)说明你所设计算法的时间复杂度和空间复杂度//改编的归并排序
int FindMid(List A, List B) {int i = 0, j = 0;while (i + j != (A.length + B.length) / 2 - 1) {if (A.data[i] <= B.data[j]) {i++;}else {j++;}}return A.data[i] < B.data[j] ? A.data[i] : B.data[j];
}//P20.12
//〖2013统考真题〗已知一个整数序列A = (a0, a1…, an-1), 其中0 ≤ ai < n(0 ≤i < n)。若
//	存在 ap1 = ap2 = ... = apm = x 且 m > n / 2   (0≤ Pk < n,1≤ k ≤ m), 则称x为A的主元素。
//	例如A=(0,5,5,3,5,7,5,5)，则5为主元素; 又如A = (0, 5, 5, 3, 5, 1, 5, 7), 则A中没有主
//	元素。假设A中的n个元素保存在一个一维数组中, 请设计一个尽可能高效的算法, 找
//	出A的主元素。若存在主元素, 则输岀该元素; 否则输出 - 1。要求:
//1)给出算法的基本设计思想
//2)根据设计思想, 采用C或C十或Java语言描述算法, 关键之处给出注释
//3)说明你所设计算法的时间复杂度和空间复杂度//次优算法，用空间换时间，类似桶排
int  FindMain(List A, int n) {int m_num = 0;int* Box = new int[n](); //动态申请一个大小为n的数组_for(i, 0, A.length) {Box[A.data[i]]++;}_for(i, 0, n) {if (Box[i] > n / 2) {return A.data[i];}}return -1;
}//P21.13
//〖2018统考真题】给定一个含n(n≥1)个整数的数组, 请设计一个在时间上尽可能高效
//的算法, 找出数组中未出现的最小正整数。例如, 数组{ -5,3,2,3 }中未出现的最小正整数
//是1; 数组{ 1,2,3 }中未出现的最小正整数是4。要求
//1)给出算法的基本设计思想
//2)根据设计思想, 采用C或C艹语言描述算法, 关键之处给出注释
//3)说明你所设计算法的时间复杂度和空间复杂度//用空间换时间
int FindMinNum(List A, int n) {int* Box = new int[n + 1]();_for(i, 0, A.length) {if (A.data[i] > 0 && A.data[i] <= n)Box[A.data[i]]++;}_for(i, 1, n) {if (!Box[i])return i;}
}int main()
{List list1;List list2;list1.length = 4;list2.length = 5;int Data1[] = { 1,3,2,3 };int Data2[] = { 22,43,64,87,180 };for (int i = 0; i < list1.length; i++)list1.data[i] = Data1[i];for (int i = 0; i < list2.length; i++)list2.data[i] = Data2[i];printf("%d", FindMinNum(list1, 4));
}

源代码链接

如有不足，请多多指教~

这篇关于2021王道数据结构——线性表课后大题_1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/252295。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
GPU 计算 CMPS224 2021 学习笔记 02

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 （1）任务并行 （2）数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间，需要在两者之间相互传输数据。 （1）分配GPU内存 （2）将CPU上的数据复制到GPU上 （3）在GPU上对数据进行计算操作 （4）将计算结果从GPU复制到CPU上 （5）释放GPU内存 CUDA内存管理API （1）分配内存 cudaErro
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
2021-8-14 react笔记-2 创建组件 基本用法

2021-8-14 react笔记-2 创建组件 基本用法

1、目录解析 public中的index.html为入口文件 src目录中文件很乱，先整理文件夹。 新建components 放组件 新建assets放资源   ->/images      ->/css 把乱的文件放进去  修改App.js 根组件和index.js入口文件中的引入路径 2、新建组件 在components文件夹中新建[Name].js文件 //组件名首字母大写
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2