大二学生的 C++数据结构 有部分Openjudge提交的代码没有删除
邮箱：liu_772021@yeah.net
欢迎交流讨论~
有用的话，点赞留言就可以表示感谢啦
//
// main.cpp
// Search
//
// Created by Liu_77 on 2021/12/14.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
//表最大长度
#define MAXSIZE 100
const double EPS = 1e-3;
typedef int KeyType;
typedef int ElemType;
typedef struct {
KeyType key;
ElemType data;
}SqType;
//创建一个顺序表
//A是顺序表的元素，length是长度，R是待创建的顺序表数组
void CreateSqList(int A[MAXSIZE], int length, SqType R[]) {
for (int i = 0; i < length; i++) {
R[i].data = A[i];
R[i].key = i;
}
}
//打印顺序表
void DispSqList(SqType R[]) {
cout << "打印顺序表：\n";
for (int i = 0; i < 10; i++) {
printf(" %4d:%4d\n", R[i].key+1, R[i].data);
}
cout << "\n打印结束；\n";
}
//顺序查找；返回关键字在表中所在位置
int SqSearch(SqType R[], int n, KeyType k) {
int i = 0;
while (i < n && R[i].key != k)
i++;
if (i > n)
return 0;
else
return i + 1;
}
//折半查找——关键字查找：k-关键字；返回序号
int BinSearch(SqType R[], int n, KeyType k) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (R[mid].key == k)
return mid + 1;
else if (R[mid].key > k)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
//元素查找：k-元素；
//输出：这个元素 这个元素在表中位置 共二分查找了几次
int BinSearch_2(SqType R[], int n, ElemType k) {
int low = 0, high = n - 1, mid;
int time = 0;
while (low <= high) {
time++;
mid = (low + high) / 2;
if (R[mid].data == k) {
printf("%d %d %d", k, R[mid].key+1, time);
return 1;
}
else if (R[mid].data > k)
high = mid - 1;
else
low = mid + 1;
}
//没找到输出0，返回0
printf("%d 0 %d",k,time);
return 0;
}
//查找、返回数组中指定元素的下标
int SearchDemo1(int a[], int length, int k) {
int i = 0;
while (i < length && a[i] != k)
i++;
if (i > length)
return 0;
else
return i + 1;
}
//按如下方法查找一个为key的整数：先在a中进行折半查找，或者查找成功，或者当折半后的待查找数据长度小于等于m时直接进行顺序查找。
//a[]待查找数组；n元素个数；m顺序查找阀值；key查找对象；counter查找次数
int FindElem(int a[], int n, int m, int key, int& counter) {
int low = 0, high = n - 1, mid;
counter = 0;
int left;
while (low <= high) {
counter++;
mid = (low + high) / 2;
//找到了：
if (a[mid] == key) {
return 1;
}
//否则，折半
else if (a[mid] > key)
high = mid - 1;
else
low = mid + 1;
left = high - low + 1;
//判断剩余元素是否小于等于m
//小于等于m，直接进行顺序查找
if (left <= m) {
for (int i = low; i <= high; i++) {
counter++;
if (a[i] == key) {
return 1;
}
}
//没找到，返回-1
//这里错了：如果进这个 【大if】（118line），就说明要么在这个区间里，要么没有了。不需要再折半查了！
return -1;
}
}
return -1;
}
KeyType BubbleSort_FindMid(SqType R[],int n){
int i, j, exchange;
SqType tmp;
int num = 0;
for (i = 0; i < n-1; i++) {
exchange = 0;
for (j = n - 1; j > i; j--) {
//后面元素比前面小，交换二者
if (R[j].key < R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
num++;
if (num == (n-1)/2){
break;
return R[(n-1)/2].key;
}
if (exchange == 0) return R[(n-1)/2].key;
}
return -1;
}
//--------------索引查找--------------------
//定义学生类型
typedef struct{
int no;
char name[10];
int score;
}SqType_Stu;
//索引表中元素类型
typedef struct{
//存放关键字
KeyType key;
//存放当前关键字元素在主数据表中的物理序号
int pos;
}IdxType;
//折半查找在索引表中查找关键字k的元素并返回其逻辑序号
int BinSearch_Id(IdxType I[],int n,KeyType k){
int low = 0,high = n-1,mid;
while(low <= high){
mid = (low+high)/2;
if(I[mid].key == k){
return mid+1;
}
if(I[mid].key > k){
high = mid-1;
}
else{
low = mid+1;
}
return 0;
}
return -1;
}
//在整个索引存储结构中查找并返回关键字为k的元素在主数据表中的逻辑序号
int IdxSearch(SqType R[],IdxType I[],int n,KeyType k){
int i;
i = BinSearch_Id(I, n, k);
if(i > 0) return I[i-1].pos+1;
else return 0;
}
//块索引表的类型定义
typedef struct{
//块 关键字
KeyType key;
//块 标识
int low,high;
}IdxType_Block;
//分块查找算法
//n为主数据表中元素个数；b为索引表中元素个数
int BlkSearch(SqType R[],int n,IdxType_Block I[],int b,KeyType k){
//在主数据表R[0..n-1]中，索引表为I[0..b-1]中找k所在的元素的逻辑序号
int low = 0,high = b-1,mid,i;
//s为每块的元素个数，应为n/b的上界
int s = (n+b-1)/b;
printf("s = %d\n",s);
while(low<=high){
mid = (low+high)/2;
if(I[mid].key >= k){
high = mid-1;
}
else low = mid+1;
}
//应在索引表的high+1块中，再在顺序表的该块中顺序查找；
i= I[high+1].low;
while(i <= I[high+1].high && R[i].key != k){
i++;
}
if(i <= I[high+1].high) return i+1;
else return 0;
}
//-----------------一些函数-------------------
//插入排序：直接插入排序、折半插入排序、希尔排序
//递增排序
void BubbleSort(SqType R[], int n) {
int i, j, exchange;
SqType tmp;
for (i = 0; i < n - 1; i++) {
exchange = 0;
for (j = n - 1; j > i; j--) {
if (R[j].key < R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
if (exchange == 0) return;
}
}
int HalfBubbleSort(SqType R[], int n) {
int i, j, exchange;
SqType tmp;
int num = -1;
int half = (n-1)/2;
for (i = 0; i < n - 1; i++) {
exchange = 0;
for (j = n - 1; j > i; j--) {
if (R[j].key < R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
num++;
if(num == half) return R[half].key;
if(exchange == 0) return R[half].key;
}
return -1;
}
//可选递增递减的冒泡排序
void BubbleSort_UD(SqType R[], int n, int way) {
int i, j, exchange;
SqType tmp;
switch (way) {
//way == 1，升序排列；
case 1: {
for (i = 0; i < n - 1; i++) {
exchange = 0;
for (j = n - 1; j > i; j--) {
//后面元素比前面小，交换二者
if (R[j].key < R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
if (exchange == 0) return;
}
}break;
//way == 2，降序排列
case 2: {
for (i = 0; i < n - 1; i++) {
exchange = 0;
for (j = n - 1; j > i; j--) {
//后面元素比前面大，交换二者
if (R[j].key > R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
if (exchange == 0) return;
}
}break;
}
}
//冒泡排序算法分析：
//最好情况O(n) 最坏情况O(n^2) 平均情况O(n^2) 空间复杂度O(1) 稳定性:稳定
//最好情况是已经顺序。
//双向递减排序
void BiBubbleSort(SqType R[], int n) {
int i = 0, j, exchange = 0;
SqType tmp;
int big = 0, small = 0;
while (i != n) {
//i为偶数，从后向前排序将最大元素放到前面
if (i % 2 == 0) {
for (j = n - 1; j > big; j--) {
if (R[j].key > R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
big++;
}
//i为奇数，从前向后排序，将最小元素放到后面
else {
for (j = 1; j < n - 1 - small / 2; j++) {
if (R[j].key > R[j - 1].key) {
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
exchange = 1;
}
}
small++;
}
if (exchange == 0) break;
i++;
}
}
void DispSqList(SqType R[], int length) {
for (int i = 0; i < length; i++) {
cout << R[i].key << ' ';
}
cout << endl;
}
//二分法--关键字查找：k-关键字；返回序号
//递增序列查找
int BinSearch_U(SqType R[], int n, KeyType k,int &time) {
int low = 0, high = n - 1, mid;
time = 0;
while (low <= high) {
time++;
mid = (low + high) / 2;
if (R[mid].key == k)
return mid + 1;
else if (R[mid].key > k)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
//递减序列查找
int BinSearch_D(SqType R[], int n, KeyType k, int& time) {
int low = 0, high = n - 1, mid;
time = 0;
while (low <= high) {
time++;
mid = (low + high) / 2;
if (R[mid].key == k)
return mid + 1;
else if (R[mid].key < k)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
//------------------插入排序------------------
//插入排序基本思路：每趟将一个待排序元素，按关键字值的大小插入到已排序的部分文件中的适当位置，直到全部插入完成
//直接插入排序--降序排列
void InsertSort_D(SqType R[], int n) {
int i, j;
SqType tmp;
for (i = 1; i < n; i++) {
if (R[i - 1].key < R[i].key) {
tmp = R[i];
j = i - 1;
do {
R[j + 1] = R[j];
j--;
} while (j >= 0 && R[j].key < tmp.key);
R[j + 1] = tmp;
}
DispSqList(R, n);
}
}
//直接插入排序--升序排列
void InsertSort_U(SqType R[], int n) {
int i, j;
SqType tmp;
for (i = 1; i < n; i++) {
if (R[i - 1].key > R[i].key) {
tmp = R[i];
j = i - 1;
do {
R[j + 1] = R[j];
j--;
} while (j >= 0 && R[j].key > tmp.key);
R[j + 1] = tmp;
}
DispSqList(R, n);
}
}
//最好情况O(n)(不进入内循环，元素移动次数为0，关键字比较次数n-1)
//最坏情况：O(n^2)（反序，关键字比较次数O(n^2),元素移动次数O(n^&2)）
//平均移动次数O(n^2) 空间复杂度O(1) 稳定的
//折半插入排序
//对R[0..n-1]进行折半插入排序
void BinInsertSort(SqType R[],int n){
int i,j,low,high,mid;
SqType tmp;
for(i = 1;i<n;i++){
if(R[i-1].key > R[i].key){
//基准R[i]保存到tmp中
tmp = R[i];
low = 0;high = i-1;
//在R[low..high]中【折半查找】有序插入位置（直到找到插入位置）
while(low <= high){
//取中间位置
mid = (low+high)/2;
if(tmp.key < R[mid].key){
high = mid-1;
}
else{
low = mid+1;
}
}
//元素后移
for(j = i-1;j>=high;j--){
R[j+1] = R[j];
}
//插入原来的R[i]
R[high+1] = tmp;
}
}
}
//由于有序区的有序性，可以用折半查找找到插入位置
//平均关键字比较次数：log2(i+1) 平均移动元素次数：i/2+2
//平均时间复杂度O(n^2)
//空间复杂度O(1) 稳定性——稳定 优于直接插入排序
//希尔排序
void ShellSort(SqType R[],int n){
int i,j,d;
SqType tmp;
d = n/2;
while(d > 0){
//对所有相隔为d位置的所有元素组采用直接插入排序
for(i = d;i<n;i++){
tmp = R[i];
j = i-d;
//对相距为d的元素组进行排序
while(j >= 0 && tmp.key < R[i].key){
R[j+d] = R[j];
j = j-d;
}
R[j+d] = tmp;
}
//减小增量
d = d/2;
}
}
//思路：分组插入，取定一个小于n的整数d1作为第一个增量，把表中全部元素划分为d1个组，所有距离为d1的倍数的元素放在同一组中；
//快排
void QuickSort(SqType R[],int s,int t){
int i = s,j = t;
SqType tmp;
//区间内存在两个及以上元素
if(s<t){
//以区间内第一个元素为基准
tmp = R[s];
//从区间两端交替向中间扫描，直到i=j
while(i != j){
//从右向左扫描，找到第一个关键字小于tmp.key的R[j]
while(j > i && R[j].key >= tmp.key){
j--;
}
//将R[j]前移动到R[i]的位置
R[i] = R[j];
//从左向右扫描，找到第一个关键字大于tmp.key的R[i]
while(i < j && R[i].key <= tmp.key){
i++;
}
//将R[i]后移动到R[j]的位置
R[j] = R[i];
}
//将基准值置入R[i]
R[i] = tmp;
//对左子序列递归排序
QuickSort(R, s, i-1);
//对右子序列递归排序
QuickSort(R,i+1,t);
}
}
//每次将基准元素归位，再递归调用，对归位的基准元素两边的元素快排。
//最好情况：O(nlog2n) 最坏情况(On^2) 平均情况O(nlog2n) 空间复杂度O(log2n) 不稳定
//每层至多对n个元素进行划分，时间O(n)；正序或反序——最坏情况，O(n^2);随机分布，每次两个子列长度大致相等，最好情况。
//递归树平均高度为O(log2n),对应着空间复杂度。
void swap(KeyType *a, KeyType *b){
KeyType c = 0;
c = *a;
*a = *b;
*b = c;
}
// 快速排序函数代码，使得输入参数desc为0时实现升序，desc为1时实现降序
void QuickSort(SqType R[], int s, int t, int desc){
int first = s, last = t;
int key = first;
if (s < t) {
// 在此处补充你的代码
switch(desc){
//desc == 0,升序排列
case 0:{
if (first >= last){
return;
}
while (first < last){
//右边找比标量小的数
while (first < last && R[last].key >= R[key].key){
last--;
}
//左边找比标量大的数
while (first < last && R[first].key <= R[key].key){
first++;
}
//分析交换找出来的值
if(first < last){
swap(R[first].key, R[last].key);
}
}
if (first == last){
int mite = key;//交换标量到它应该到的位置上，重新选取标量
swap(R[mite].key, R[last].key);
}
};
break;
//desc == 1，降序排列
case 1:{
if (first >= last){
return;
}
while (first < last){
//右边找比标量大的数
while (first < last && R[last].key <= R[key].key){
last--;
}
//左边找比标量小的数
while (first < last && R[first].key >= R[key].key){
first++;
}
//分析交换找出来的值
if(first < last){
swap(R[first].key, R[last].key);
}
}
if (first == last){
int mite = key;//交换标量到它应该到的位置上，重新选取标量
swap(R[mite].key, R[last].key);
}
}
break;
}
QuickSort(R, s, last - 1, desc);
QuickSort(R, last + 1, t, desc);
}
}
//--------------------选择排序--------------------
//思路：每步从待排序元素中选出关键字最小的元素，按顺序放在已排序的元素序列的左后，直到排完为止
void SeleteSort(SqType R[],int n){
int i,j,k;
SqType tmp;
for(i = 0;i<n-1;i++){
k = i;
//从待排序区找最小元素
for(j = i+1;j<n;j++){
//找到更小元素，记录下标
if(R[j].key < R[k].key){
k = j;
}
}
//如果最小元素不是第一个元素，交换二者位置
if(k != i){
tmp = R[i];
R[i] = R[k];
R[k] = tmp;
}
}
}
//
//堆排序
//对R[low..high]进行堆筛选
void Sift(SqType R[],int low,int high){
//R[j]是R[i]的左孩子
int i = low,j = 2*i;
//tmp是双亲结点
SqType tmp = R[i];
while(j <= high){
if(j < high && R[j].key < R[j+1].key){
//如果右孩子较大，把j指向右孩子
j++;
}
//如果孩子结点大于双亲结点：
if(tmp.key < R[j].key){
//将R[j]调整到双亲结点位置上
R[i] = R[j];
//修改i、j的值，以继续向下筛选
i = j;
j = 2*i;
}
//已是大根堆，筛选结束
else break;
}
//被筛选结点的值放入嘴中位置。
R[i] = tmp;
}
void HeapSort(SqType R[],int n){
int i;
SqType tmp;
//n/2次循环建立初始堆（大根堆）
for(i = n/2;i>=1;i--){
Sift(R,i,n);
}
//进行n-1次循环，完成堆排序
for(i = n;i>=2;i--){
//交换R[1]和R[i](交换最末元素与根结点)（最末元素是最大的，由大根堆）
tmp = R[1];
R[1] = R[i];
R[i] = tmp;
//生成新的大根堆
Sift(R,1,i-1);
}
}
//创建数组时从1开始！！
//-------------------归并排序-------------------
void Merge(SqType R[],int low,int mid,int high){
SqType *R1;
int i = low,j = mid+1,k = 0;
R1 = (SqType *)malloc((high-low+1)*sizeof(SqType));
while(i <= mid && j <= high){
if(R[i].key <= R[j].key){
R1[k] = R[i];
i++;k++;
}
else{
R1[k] = R[j];
j++;k++;
}
}
while(i <= mid){
R1[k] = R[i];
i++;k++;
}
while(j <= high){
R1[k] = R[j];
j++;k++;
}
for(k = 0,i = low;i<=high;k++,i++){
R[i] = R1[k];
}
free(R1);
}
//一趟二路归并
void MergePass(SqType R[],int length,int n){
int i;
for(i = 0;i+2*length-1<n;i = i+2*length){
Merge(R,i,i+length-1,i+2*length-1);
}
if(i+length-1 < n){
Merge(R,i,i+length-1,n-1);
}
}
//二路归并排序算法：
void MergeSort(SqType R[],int n){
int length;
for(length = 1;length < n;length = 2*length){
MergePass(R, length, n);
}
}
//-----------------OJ题目--------------------
void main_2(){
int a[10] = { 2,4,7,9,10,14,18,26,32,40 };
SqType A[10];
//给A赋值：创建SqList A
CreateSqList(a, 10, A);
//DispSqList(A);
int key;
cin >> key;
BinSearch_2(A, 10, key);
}
void main_3(){
//第三题
int a[] = { 0,1,2,3,4,10,11,12,13,20,21,22,23,30,31,32,33,52,53,54,55 };
int n = sizeof(a) / sizeof(a[0]);
int key, m, counter;
scanf("%d", &m);
scanf("%d", &key);
int j = FindElem(a, n, m, key, counter);
printf("%d %d\n", (j != -1) ? 1 : -1, counter);
//return 0;
}
void main_04() {
/*
KeyType A[] = { 9,8,7,6,0,-1,10,-5,-32,66 };
int length = sizeof(A) / sizeof(KeyType);
//printf("length = %d\n", length);
SqType *R = (SqType *)malloc(sizeof(SqType)*length);
for (int i = 0; i < length; i++) {
R[i].key = A[i];
}
//排序标识
int way;
cin >> way;
BubbleSort_UD(R, length, way);
//DispSqList(R, length);
//输入待查找的数，输入非整数或^Z时，结束输入。
double target[11];
int i = 0;
while(cin >> target[i] && target[i] - (int)target[i] < EPS) {
i++;
}
int time = 0;
for (int j = 0; j < i; j++) {
switch (way){
case 1: {
if (BinSearch_U(R, length, target[j], time)) {
cout << time << endl;
}
else cout << "-1\n";
}break;
case 2: {
if (BinSearch_D(R, length, target[j], time)) {
cout << time << endl;
}
else cout << "-1\n";
}break;
default:
break;
}
}
return 0;
*/
}
void main_05() {
/*
//第五题
int length;
cin >> length;
int a[21];
for (int i = 0; i < length; i++) {
cin >> a[i];
}
if (BiSearch_test05(a, length)) {
cout << "exist";
return 0;
}
cout<<"non-exist";
return 0;
*/
}
void main_06() {
/*
int length;
cin >> length;
int a[21], b[21];
for (int i = 0; i < length; i++) {
cin >> a[i];
}
for (int i = 0; i < length; i++) {
cin >> b[i];
}
//二路归并
cout<<TwoMerger(a, b, length);
return 0;
*/
}
void main_7_8() {
/*
KeyType A[10];
SqType R[10];
for (int i = 0; i < 10; i++) {
cin >> A[i];
R[i].key = A[i];
}
//U为第八题，D为第七题
InsertSort_U(R, 10);
*/
}
void main_10() {
/*
int length;
cin >> length;
KeyType A[MAXSIZE];
SqType R[MAXSIZE];
for (int i = 0; i < length; i++) {
cin >> A[i];
R[i].key = A[i];
}
BiBubbleSort(R, length);
DispSqList(R, length);
return 0;
*/
}
void main_11(){
//快速中位数
KeyType A[9];
SqType R[9];
for (int i = 0; i < 9; i++) {
cin >> A[i];
R[i].key = A[i];
}
//cout<<"input down\n";
//DispSqList(R, 9);
int half = HalfBubbleSort(R, 9);
//DispSqList(R, 9);
cout<<half<<endl;
}
void main_09(){
SqType a[MAXSIZE];
SqType b[MAXSIZE];
int n = 0, an = 0, bn = 0, m;
cin >> n;
for (int i=0; i<n; i++) {
cin >> m;
//偶数，存进a数组
if (m % 2 == 0) {
a[an].key = a[an].data = m;
an++;
}
//奇数，b数组
else {
b[bn].key = b[bn].data = m;
bn++;
}
}
cout<<"奇数序列：";
DispSqList(b, bn);
cout<<"偶数序列：";
DispSqList(a, an);
cout<<"\n";
//奇数升序排列
QuickSort(b, 0, bn - 1, 0);
//偶数降序排列
QuickSort(a, 0, an - 1, 1);
cout<<"排序后：\n";
cout<<"奇数序列：";
DispSqList(b, bn);
cout<<"偶数序列：";
DispSqList(a, an);
cout<<"\n";
//依次输入基数和偶数。
for (int i=0; i<bn; i++) {
cout << b[i].key << " ";
}
for (int i=0; i<an; i++) {
cout << a[i].key << " ";
}
//return 0;
}
void MERGE(){
SqType R[MAXSIZE];
KeyType A[] = {75,87,68,92,88,61,77,96,80,72};
int i,n = 10;
for(i = 0;i<n;i++){
R[i].key = A[i];
}
MergeSort(R, n);
printf("排序结果：");
for(i = 0;i<n;i++){
printf("%3d",R[i].key);
}
printf("\n");
}
void HEAP(){
SqType R[MAXSIZE];
KeyType A[] = {75,87,68,92,88,61,77,96,80,72};
int i,n = 10;
//注意这里从下标第一开始存
for(i = 0;i<n;i++){
R[i+1].key = A[i];
}
HeapSort(R, n);
printf("排序结果：");
//注意这里从下标第一开始，至n结束
for(i = 1;i<=n;i++){
printf("%3d",R[i].key);
}
printf("\n");
}
int main() {
SqType R[MAXSIZE];
KeyType A[] = {75,87,68,92,88,61,77,96,80,72};
int i,n = 10;
//注意这里从下标第一开始存
for(i = 0;i<n;i++){
R[i].key = A[i];
}
SeleteSort(R, n);
printf("排序结果：");
//注意这里从下标第一开始，至n结束
for(i = 0;i<n;i++){
printf("%3d",R[i].key);
}
printf("\n");
}
版权声明：本文为catlv77原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。