数据结构算法题（C++）

数据结构算法题（C++） 0 准备工作

在线C++运行工具

使用方法：复制每题中代码到上面的在线运行网站上便可以运行

第1章：线性表的顺序表示 01

题目：假设顺序表非空。从顺序表中找到最小值，及其下标，通过引用方式返回

思路：

①申请变量value，pos初始化value为顺序表第一个元素的值，pos=0

②从顺序表第二位开始遍历，遇见比value更小的元素，就更新value为当前元素，pos为当前元素的下标

#define MaxSize 50
#include 
#include 
#include  

using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

// 假设顺序表非空，从顺序表中找到最小的只，及其下标，通过引用的方式返回 
void findMin(SqList &L, ElemType &value, int &pos) {
//	表中第一个元素的值 
	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;
		}
	}
//	退出之后
//	pos:是最小元素在数组中的下标
//	value:是最小元素的值 
}
//测试findMin函数 
void test_findMin() {
	SqList L = getRandomSqList(10);     
	printList(L);   
	cout << "--------------------------------" << endl;   
	ElemType value;
	int pos;
	findMin(L, value, pos);
	cout << "最小值：" << value << ",下标：" << pos << endl; 
}

int main() {
	test_findMin();
	return 0;
}

02

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

思想：

①表空时：返回

②表非空

一：找到最小元素

二：然后用表尾元素覆盖，表长减去1

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

// 假设顺序表非空，从顺序表中找到最小的只，及其下标，通过引用的方式返回 
void findMin(SqList &L, ElemType &value, int &pos) {
//	表中第一个元素的值 
	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;
		}
	}
//	退出之后
//	pos:是最小元素在数组中的下标
//	value:是最小元素的值 
}

//删除顺序表中最小值的元素，并有函数返回最小值，空出的位置由最后一个元素补充
bool delMin(SqList &L, ElemType &value) {
//	空表判断 
	if(L.length == 0) {
		return false;
	}
//	找到最小元素，最小元素下标 
	int pos;
	findMin(L, value, pos);
//	最后一位 
	int end = L.length - 1;
//	执行覆盖 
	L.data[pos] = L.data[end];
//	表长减一 
	L.length--;
	return true;
} 
//测试findMin函数 
void test_delMin() {
	SqList L = getRandomSqList(10);     
	printList(L);   
	cout << "--------------------------------" << endl;   
	ElemType value;
	int value1;
	delMin(L, value1);
	cout << "最小值：" << value1 << endl; 
	cout << "--------------------------------" << endl; 
	printList(L);   
}

int main() {
	test_delMin();
	return 0;
}

03

题目：交换ab元素值

思想：

申请变量C，先让c = a， 再让a = b，再让b = c，交换完成

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//交换ab的值 
void swap(ElemType &a, ElemType &b) {
	ElemType c = a;
	a = b;
	b = c;
}

void test_swap() {
	ElemType a = 10, b = 20;
	cout << "a = " << a << ", b = " << b << endl;
	swap(a, b);
	cout << "a = " << a << ", b = " << b << endl;
}

int main() {
	test_swap(); 
	return 0;
}

04

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

思想：双指针，交换n/2次

①表长为偶数，头尾交换

②表长为奇数，中间的数不用交换

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//交换ab的值 
void swap(ElemType &a, ElemType &b) {
	ElemType c = a;
	a = b;
	b = c;
}

//将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)
void reverse(SqList &L) {
	for(int i = 0; i < L.length/2; i++) {
//		末尾元素下标 
		int end = L.length - i - 1;
//		交换 
		swap(L.data[i], L.data[end]);
	}
} 

void test_reverse() {
	SqList L = getRandomSqList(11);
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	reverse(L);
	cout << "逆L:";
	printList(L);	 
}

int main() {
	test_reverse();
	return 0;
}

05

题目：用顺序表，实现简单选择排序

思想：

①第i趟：每一趟都可以确定一个元素的最终位置，从L[i...n]中选择关键字最小的元素与L[i]交换

②经过n-1唐排序就可以是的整个排序表有序

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//交换ab的值 
void swap(ElemType &a, ElemType &b) {
	ElemType c = a;
	a = b;
	b = c;
}

//用顺序表实现简单选择排序
//找到下标start...end中的最小值下标，并返回
int findMinIndex(SqList A, int start, int end) {
	int minIndex = start;
	for(int j = start+1; j <= end; j++) {
		if(A.data[minIndex] > A.data[j]) {
			minIndex = j;
		}
	}
	return minIndex;
} 
//进行选择排序
//表分为两部分，前面有序，后面无序
//在i~end之间找到最小的元素，若是最小的元素的值与i不相等，则将i与最小元素的调换
//i从0~length-1 
//A必须进行引用，否则数组，length将会被复制一份 
void selectSort(SqList &A) {
	for(int i = 0; i < A.length; i++) {
//		第i趟，找出无序部分最小值下标 
		int minIndex = findMinIndex(A, i, A.length-1);
//		将无序部分最小值放到有序部分尾巴 
		if(minIndex != i) {
			swap(A.data[i], A.data[minIndex]);
		}
	}
}

void test_selectSort() {
	SqList L = getRandomSqList(10);
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	selectSort(L);
	cout << "序L:";
	printList(L);
}

int main() {
	test_selectSort(); 
	return 0;
}

06

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

思路：遍历整个表，记录所有当前不等于x的元素的个数，假设为k。将不等于x的元素放在下标为k上，最后修改表长为k

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//对长度为n的顺序表L，时间复杂度O(n),空间复杂度O(1),删除L中所有x的数据元素
//将表L分为三个部分，第一部分为不是20的元素，第二部分为20， 第三部分为待排序的元素
//因为第二部分是在逻辑上的，实际操作上是被覆盖的 
void delX(SqList &L, ElemType x) {
//	记录表中值不等于x的元素的个数
//	最终也是表长 
	int k = 0;
//	遍历，执行处理 
	for(int i = 0; i < L.length; i++) {
		if(L.data[i] != x) {
//			把当前元素放在下标k处 
			L.data[k] = L.data[i];
//			k递增 
			k += 1;
		}
//		else:等于x的元素直接略过 
	}
//	表长最终等于k 
	L.length = k;
} 

void test_delX() {
	SqList L = getRandomSqList(10);
//	随机将L中的三个元素设置为20
	for(int i = 0; i < 3; i++) {
		L.data[rand() % 10] = 20;
	} 
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	delX(L, 20);
	cout << "表L:";
	printList(L);	
}

int main() {
	test_delX();
	return 0;
}

07

题目：从顺序表中删除位序位于i,j之间的所有元素

思路：如果i，j不合法，返回false，否则，把位序j之后的元素，依次移动到从位序i开始的位置上，最后修改表长为L.length-(j-i+1)，返回true

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//从顺序表L中删除位序i和j之间的元素
//位序是从1~length 
//将L分为三段，其中0~i-2是第一段，i-1~j-1是第二段，j~length-1是第三段
//第一段是加1的，第三段是减1的，第二段不需要管
bool deli2j(SqList &L, int i, int j) {
//	首先先对i和j和合法性进行判断
	if(i < 1 || j > L.length || j < i) {
		return false;
	} 
//	位序转换为下标 
	i--;
	j--;
//	将indexJ出元素移动到indexI处
//	到表尾时停止
//	移动一个元素后就后退一位 
	for(int indexI = i, indexJ = j+1; indexJ < L.length; indexI++, indexJ++) {
//		移动 
		L.data[indexI] = L.data[indexJ];
	} 
//	修改表长
	L.length -= j - i + 1;
	return true; 
} 

void test_deli2j() {
	SqList L = getRandomSqList(16);
	
	cout << "注意位序和下标有1的差距" << endl;
	cout << "表L:";
	printList(L);
	cout << "----------------------------------------------------------------" << endl; 
	cout << "原来表长：" << L.length << endl;
	deli2j(L, 4, 8);
	cout << "现在表长：" << L.length << endl;
	cout << "表L:";
	printList(L);
}


int main() {
	test_deli2j();
	return 0;
}

08

题目：找出有序表中值在给定值s和t之间的所有元素，返回下标范围

思想：确定值在[s,t]之间的元素的下标

①从头到尾遍历，第一个出现的元素值大于等于s的元素

②从头到尾遍历，第一个出现的元素值大于t的元素的前一个元素

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

//交换ab的值 
void swap(ElemType &a, ElemType &b) {
	ElemType c = a;
	a = b;
	b = c;
}

void bubbSort(SqList &L) {
	int n = L.length;
	for(int i = 0; i < n - 1; i++) {
//		用于标记本轮冒泡排序是否进行了交换 
		bool isBubble = false;
//		从后往前冒泡 
		for(int j = n - 1; j > i; j--) {
//			前面的更大，则需要交换 
			if(L.data[j - 1] > L.data[j]) {
				swap(L.data[j - 1], L.data[j]);
				isBubble = true;
			}
		}
//		如果没有交换则证明已经有序了
		if(!isBubble) {
			return;
		} 
	}
}

//找到有序顺序表中值在给定s与t之间(要求s= t || L.length == 0) {
		return false;
	} 
	
	int indexS;
	for(indexS = 0; indexS < L.length && L.data[indexS] < s; indexS++);
	if(indexS >= L.length) {
		return false;
	}
	int indexT;
	for(indexT = indexS; indexT < L.length && L.data[indexT] <= t; indexT++);
	start = indexS;
	end = indexT - 1;
	return true;
}

void test_finds2t() {
	SqList L = getRandomSqList(10);
	bubbSort(L);
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	ElemType s = 10, t = 40;
	int start, end;
	cout << "寻找[" << s << ", " << t << "]之间的元素: ";
	bool isSuccess =  finds2t(L, s, t, start, end);
	cout << "[" << start << ", " << end << "]" << endl;	
}

int main() {
	test_finds2t();
	return 0;
}

09

题目：从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s或t不合理或顺序表为空，则显示出错信息并退出运行

思想：

①有序顺序表：表中元素我们假设是递增的

②确定值在[s,t]之间的元素的下标

③执行区间删除

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

void bubbSort(SqList &L) {
	int n = L.length;
	for(int i = 0; i < n - 1; i++) {
//		用于标记本轮冒泡排序是否进行了交换 
		bool isBubble = false;
//		从后往前冒泡 
		for(int j = n - 1; j > i; j--) {
//			前面的更大，则需要交换 
			if(L.data[j - 1] > L.data[j]) {
				swap(L.data[j - 1], L.data[j]);
				isBubble = true;
			}
		}
//		如果没有交换则证明已经有序了
		if(!isBubble) {
			return;
		} 
	}
}

//找到有序顺序表中值在给定s与t之间(要求s= t || L.length == 0) {
		return false;
	} 
	
	int indexS;
	for(indexS = 0; indexS < L.length && L.data[indexS] < s; indexS++);
	if(indexS >= L.length) {
		return false;
	}
	int indexT;
	for(indexT = indexS; indexT < L.length && L.data[indexT] <= t; indexT++);
	start = indexS;
	end = indexT - 1;
	return true;
}

//从顺序表L中删除位序i和j之间的元素
//位序是从1~length 
//将L分为三段，其中0~i-2是第一段，i-1~j-1是第二段，j~length-1是第三段
//第一段是加1的，第三段是减1的，第二段不需要管
bool deli2j(SqList &L, int i, int j) {
//	首先先对i和j和合法性进行判断
	if(i < 1 || j > L.length || j < i) {
		return false;
	} 
//	位序转换为下标 
	i--;
	j--;
//	将indexJ出元素移动到indexI处
//	到表尾时停止
//	移动一个元素后就后退一位 
	for(int indexI = i, indexJ = j+1; indexJ < L.length; indexI++, indexJ++) {
//		移动 
		L.data[indexI] = L.data[indexJ];
	} 
//	修改表长
	L.length -= j - i + 1;
	return true; 
} 

//从有序顺序表中删除值在s到t之间的所有元素，如果s和t不合理或顺序表为空，则显示出错信息并退出运行
bool dels2t(SqList &L, ElemType s, ElemType t) {
	int start, end;
	bool isSuccess;
	isSuccess = finds2t(L, s, t, start, end);
	if(!isSuccess) {
		return false;
	}
	return deli2j(L, start+1, end+1);
} 

void test_dels2t() {
	SqList L = getRandomSqList(10);
	bubbSort(L);
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	
	ElemType s = L.data[4], t = L.data[7];
	cout << "删除[" << L.data[4] << "," << L.data[7] << "]之间的元素" << endl;
	dels2t(L, s, t);
	cout << "删L:";
	printList(L);
}

int main() {
	test_dels2t(); 
	return 0;
}

10

题目：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同

思路：

①将表划分为A表，B表；A表是该有序顺序表的前半部分，B表是该表的后半部分

②初始化是，表A中只有一个元素，也就是有序顺序表的第一个元素，表B拥有剩下的n-1个元素

③用表A的最后一个元素与表B从头开始比较没出现不相同时，追加到表A尾巴上

④重复③，知道表B为空，再修改新表长为表A的长度

#define MaxSize 50
#include 
#include 
#include  
using namespace std;
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//打印出数组元素，以逗号隔开 
void printList(SqList L) {
	for(int i = 0; i < L.length; i++) {
		cout << L.data[i] << ", ";
	}
	cout << endl;
}
// number表示数组中的元素个数，L表示保存在L链表中
// 数组的范围是1~100 
SqList getRandomSqList(int number) {
	SqList L;
	L.length = number;
	srand((unsigned)time(NULL)); 
	for(int i = 0; i < number;i++ ) {
		int val = rand() % 100;
		L.data[i] = val;
//		cout << number << "t";
	}
//    cout << endl; 
	return L;
}

bool delSame(SqList &L) {
//	表空不存在删除 
	if(L.length == 0) {
		return false;
	}
//	在表A,B 中进行索引的指针 
	int indexA, indexB;
	for(indexA = 0, indexB = 1; indexB < L.length; indexB++) {
//		出现不同的元素，应该放到表A的尾巴上去 
		if(L.data[indexA] != L.data[indexB]) {
			L.data[++indexA] = L.data[indexB];
		}
	}
//	最终表长为表A的长度 
	L.length = indexA + 1;
//	对于是否加1.一定要弄清楚当前indexA是只想表A的最后一个元素（加1）
//	还是指向表A的最后一个元素的下一个元素（不加1） 
	return true;
}

void test_delSame() {
	SqList L;
	ElemType A[] = {1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5};
	L.length = sizeof(A) / sizeof(ElemType);
	for(int i = 0; i < L.length; i++) {
		L.data[i] = A[i];
	} 
	cout << "表L:";
	printList(L);
	cout << "--------------------------------" << endl; 
	delSame(L);
	printList(L);
} 

int main() {
	test_delSame();
	return 0;
}