DS|顺序表

2023-12-17 18:47:00

问题一:DS顺序表--存储结构与操作

题目描述:

实现顺序表的存储结构和操作

属性包括:数组、实际长度、最大长度(设定为1000)

操作包括:创建、插入、删除、查找

输入要求:

第1行先输入n表示有n个数据,即n是实际长度;接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置

输出要求:

数据之间用空格隔开

第1行输出创建后的顺序表内容,包括顺序表实际长度和数据

每成功执行一次操作(插入或删除),输出执行后的顺序表内容

每成功执行一次查找,输出查找到的数据

如果执行操作失败(包括插入、删除、查找等失败),输出字符串error,不必输出顺序表内容

输入样例:

6 11 22 33 44 55 66
3 777
1 888
1
9
0
5

输出样例:

6 11 22 33 44 55 66 
7 11 22 777 33 44 55 66 
8 888 11 22 777 33 44 55 66 
7 11 22 777 33 44 55 66 
error
error
44

代码示例:

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class SList {
public:
	SList();
	~SList();
	void InitList(int arr[], int n);
	int Insert(int x, int pos);
	int Delete(int pos);
	int Get(int i);
	void Display();
	void Operation();
private:
	int* data;
	int lenth;
	int listsize;
};
//无参构造
SList::SList(){
	data = new int[MAX_SIZE];
	listsize = MAX_SIZE;
	lenth = 0;
}
//初始化链表
void SList::InitList(int arr[], int n){
	for (int i = 0; i < n; i++)	data[i] = arr[i];
	lenth = n;
}
//插入数据
int SList::Insert(int x, int pos){
	if ((pos < 1) || (pos > lenth + 1)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = lenth; i >= pos; i--) data[i] = data[i - 1];
		data[pos - 1] = x;
		lenth++;
		return 1;
	}
}
//删除数据
int SList::Delete(int pos){
	if ((pos < 1) || (pos > lenth)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = pos; i < lenth; i++) data[i - 1] = data[i];
		lenth--;
		return 1;
	}
}
//获取数据
int SList::Get(int pos){
	if ((pos < 1) || (pos > lenth)) return 0;
	else return data[pos - 1];
}
//打印链表
void SList::Display(){
	cout << lenth << " ";
	for (int i = 0; i < lenth; i++) cout << data[i] << " ";
	cout << endl;
}
//执行操作
void SList::Operation() {
	int number, site;

	//插入两个数
	for (int i = 0; i < 2; i++) {
		cin >> site >> number;
		if (Insert(number, site)) Display();
	}
	//删除两个数
	for (int i = 0; i < 2; i++) {
		cin >> number;
		if (Delete(number)) Display();
	}
	//查找两个数
	for (int i = 0; i < 2; i++) {
		cin >> site;
		if (Get(site) != NULL)cout << Get(site);
		else cout << "error" << endl;
	}
}

SList::~SList(){
	delete[]data;
}

int main() {
	SList slist;
	int n;
	cin >> n;
	int* array = new int[n];
	for (int i = 0; i < n; i++) cin >> array[i];
	slist.InitList(array, n);
	slist.Display();
	slist.Operation();
	return 0;
}

问题二:DS顺序表--连续操作

题目描述:

建立顺序表的存储结构,属性包括:数组、实际长度、最大长度(设定为1000)

编写如下函数

实现顺序表的初始化函数。

插入多个数据的multiinsert(int i, int n, int item[])函数,实现在第i个位置,连续插入来自数组item的n个数据,即从位置i开始插入多个数据。

删除多个数据的multidel(int i, int n)函数,实现从第i个位置开始,连续删除n个数据,即从位置i开始删除多个数据。

编写main函数测试该顺序表。

输入要求:

第1行先输入n表示有n个数据,即n是实际长度;接着输入n个数据

第2行先输入i表示插入开始的位置,再输入k表示有k个插入数据,接着输入k个数据

第3行先输入i表示删除开始的位置,再输入k表示要删除k个数据

输出要求:

顺序表内容包括顺序表的实际长度和数据,数据之间用空格隔开

第1行输出创建后的顺序表内容

第2行输出执行连续插入后的顺序表内容

第3行输出执行连续删除后的顺序表内容

输入样例:

6 11 22 33 44 55 66
2 3 99 88 77
4 5

输出样例:

6 11 22 33 44 55 66 
9 11 99 88 77 22 33 44 55 66 
4 11 99 88 66

代码示例:

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class SList {
public:
	SList();
	~SList();
	void InitList(int arr[], int n);
	int Insert(int x, int pos);
	int Delete(int pos);
	int Get(int pos);
	int multInsert(int pos, int n, int arr[]);
	int multiDel(int i, int n);
	void Display();
	void Operation();
private:
	int* data;
	int lenth;
	int listsize;
};
//无参构造
SList::SList(){
	data = new int[MAX_SIZE];
	listsize = MAX_SIZE;
	lenth = 0;
}
//初始化链表
void SList::InitList(int arr[], int n){
	for (int i = 0; i < n; i++)	data[i] = arr[i];
	lenth = n;
}
//插入数据
int SList::Insert(int x, int pos){
	if ((pos < 1) || (pos > lenth + 1)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = lenth; i >= pos; i--) data[i] = data[i - 1];
		data[pos - 1] = x;
		lenth++;
		return 1;
	}
}
//删除数据
int SList::Delete(int pos){
	if ((pos < 1) || (pos > lenth)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = pos; i < lenth; i++) data[i - 1] = data[i];
		lenth--;
		return 1;
	}
}
//获取数据
int SList::Get(int pos){
	if ((pos < 1) || (pos > lenth)) return 0;
	else return data[pos - 1];
}
//插入多个数据
int SList::multInsert(int pos, int n, int arr[]) {
	if (pos < 1 || pos > lenth + 1){
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = lenth + n - 1; i >= pos + n - 1; i--) data[i] = data[i - n];
		for (int i = 0; i < n; i++)data[pos + i - 1] = arr[i];
		lenth += n;
		return 1;
	}
}
//删除多个数据
int SList::multiDel(int pos, int n) {
	if (pos < 1 || pos > lenth) {
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = 0; i < n; i++) {
			data[pos - 1 + i] = data[pos - 1 + i + n];
		}
		lenth -= n;
		return 1;
	}
}
//打印链表
void SList::Display(){
	cout << lenth << " ";
	for (int i = 0; i < lenth; i++) cout << data[i] << " ";
	cout << endl;
}
//执行操作
void SList::Operation() {
	int number, site;
	cin >> site >> number;
	int* array = new int[number];
	for (int i = 0; i < number; i++) {
		cin >> array[i];
	}
	if (multInsert(site, number, array)) Display();
	else cout << "error" <<  endl;

	cin >> site >> number;
	if (multiDel(site, number)) Display();
	else cout << "error" << endl;
}

SList::~SList(){
	delete[]data;
}

int main() {
	SList slist;
	int n;
	cin >> n;
	int* array = new int[n];
	for (int i = 0; i < n; i++) cin >> array[i];
	slist.InitList(array, n);
	slist.Display();
	slist.Operation();
	return 0;
}

问题三:DS顺序表--合并操作

题目描述:

建立顺序表数据类型,属性包括:数组、实际长度、最大长度(设定为1000)

已知两个递增序列,把两个序列的数据合并到顺序表中,并使得顺序表的数据递增有序

输入要求:

第1行先输入n表示有n个数据,接着输入n个数据,表示第1个序列,要求数据递增互不等

第2行先输入m表示有m个数据,接着输入m个数据,表示第2个序列,要求数据递增互不等

输出要求:

顺序表内容包括顺序表的实际长度和数据,数据之间用空格隔开

第1行输出创建后的顺序表内容

输入样例:

3 11 33 55
5 22 44 66 88 99

输出样例:

3 11 33 55
5 22 44 66 88 99

代码示例:

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class SList {
public:
	SList();
	~SList();
	void InitList(int arr[], int n);
	int Insert(int x, int pos);
	int Delete(int pos);
	int Get(int pos);
	int multInsert(int pos, int n, int arr[]);
	int multiDel(int i, int n);
	void Add(int arr[], int n, int brr[], int m);
	void Display();
	void Operation();
private:
	int* data;
	int lenth;
	int listsize;
};
//无参构造
SList::SList(){
	data = new int[MAX_SIZE];
	listsize = MAX_SIZE;
	lenth = 0;
}
//初始化链表
void SList::InitList(int arr[], int n){
	for (int i = 0; i < n; i++)	data[i] = arr[i];
	lenth = n;
}
//插入数据
int SList::Insert(int x, int pos){
	if ((pos < 1) || (pos > lenth + 1)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = lenth; i >= pos; i--) data[i] = data[i - 1];
		data[pos - 1] = x;
		lenth++;
		return 1;
	}
}
//删除数据
int SList::Delete(int pos){
	if ((pos < 1) || (pos > lenth)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = pos; i < lenth; i++) data[i - 1] = data[i];
		lenth--;
		return 1;
	}
}
//获取数据
int SList::Get(int pos){
	if ((pos < 1) || (pos > lenth)) return 0;
	else return data[pos - 1];
}
//插入多个数据
int SList::multInsert(int pos, int n, int arr[]) {
	if (pos < 1 || pos > lenth + 1){
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = lenth + n - 1; i >= pos + n - 1; i--) data[i] = data[i - n];
		for (int i = 0; i < n; i++)data[pos + i - 1] = arr[i];
		lenth += n;
		return 1;
	}
}
//删除多个数据
int SList::multiDel(int pos, int n) {
	if (pos < 1 || pos > lenth) {
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = 0; i < n; i++) {
			data[pos - 1 + i] = data[pos - 1 + i + n];
		}
		lenth -= n;
		return 1;
	}
}
//合并两个链表
void SList::Add(int arr[], int n, int brr[], int m) {
	lenth = m + n;
	int j = 0, k = 0;
	for (int i = 0; i < m + n; i++) {
		if (*(arr + j) <= *(brr + k) && j < n) *(data + i) = *(arr + j), j++;
		else if (*(arr + j) >= *(brr + k) && k < m) *(data + i) = *(brr + k), k++;
		else if (j == n) *(data + i) = *(brr + k), k++;
		else if (k == m) *(data + i) = *(arr + j), j++;
	}
}
//打印链表
void SList::Display(){
	cout << lenth << " ";
	for (int i = 0; i < lenth; i++) cout << data[i] << " ";
	cout << endl;
}
//执行操作
void SList::Operation() {}

SList::~SList(){
	delete[]data;
}

int main() {
	SList slist;
	int n;
	cin >> n;
	int* array = new int[n];
	for (int i = 0; i < n; i++) cin >> array[i];
	
	int m;
	cin >> m;
	int* brray = new int[m];
	for (int i = 0; i < m; i++) cin >> brray[i];
	slist.Add(array, n, brray, m);
	slist.Display();
	return 0;
}

问题四:DS顺序表--循环移位

题目描述:

顺序表的移位是循环移位,例如顺序表:1,2,3,4,5,6。如果左移1位,即原来的头元素移动到末尾,其它元素向左移1位,变成2,3,4,5,6,1。同理,如果右移1位,即原来的尾元素移动到头,其它元素向右移1位,变成6,1,2,3,4,5。以下是移位的多个例子:

原数据:1,2,3,4,5,6

左移3位:4,5,6,1,2,3,与原数据对比

右移4位:3,4,5,6,1,2,与原数据对比

请编写程序实现顺序表的循环移位操作

输入要求:

第1行输入n表示顺序表包含的·n个数据

第2行输入n个数据,数据是小于100的正整数

第3行输入移动方向和移动的位数,左移方向为0,右移方向为1

第4行输入移动方向和移动的位数,左移方向为0,右移方向为1

注意:移动操作是针对上一次移动后的结果进行的

输出要求:

第一行输出创建后,顺序表内的所有数据,数据之间用空格隔开

第二行输出第一次移位操作后,顺序表内的所有数据,数据之间用空格隔开

第三行输出第二次移位操作后,顺序表内的所有数据,数据之间用空格隔开

输入样例:

5
11 22 33 44 55
0 2
1 4

输出样例:

11 22 33 44 55 
33 44 55 11 22 
44 55 11 22 33 

代码示例:

#include <iostream>
using namespace std;

#define MAX_SIZE 100

class SList {
public:
	SList();
	~SList();
	void InitList(int arr[], int n);
	int Insert(int x, int pos);
	int Delete(int pos);
	int Get(int pos);
	int multInsert(int pos, int n, int arr[]);
	int multiDel(int i, int n);
	void Add(int arr[], int n, int brr[], int m);
	void TurnSequence(int dir, int amount);
	void Display();
	void Operation();
private:
	int* data;
	int lenth;
	int listsize;
};
//无参构造
SList::SList(){
	data = new int[MAX_SIZE];
	listsize = MAX_SIZE;
	lenth = 0;
}
//初始化链表
void SList::InitList(int arr[], int n){
	for (int i = 0; i < n; i++)	data[i] = arr[i];
	lenth = n;
}
//插入数据
int SList::Insert(int x, int pos){
	if ((pos < 1) || (pos > lenth + 1)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = lenth; i >= pos; i--) data[i] = data[i - 1];
		data[pos - 1] = x;
		lenth++;
		return 1;
	}
}
//删除数据
int SList::Delete(int pos){
	if ((pos < 1) || (pos > lenth)){
		cout << "error" << endl;
		return 0;
	}
	else{
		for (int i = pos; i < lenth; i++) data[i - 1] = data[i];
		lenth--;
		return 1;
	}
}
//获取数据
int SList::Get(int pos){
	if ((pos < 1) || (pos > lenth)) return 0;
	else return data[pos - 1];
}
//插入多个数据
int SList::multInsert(int pos, int n, int arr[]) {
	if (pos < 1 || pos > lenth + 1){
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = lenth + n - 1; i >= pos + n - 1; i--) data[i] = data[i - n];
		for (int i = 0; i < n; i++)data[pos + i - 1] = arr[i];
		lenth += n;
		return 1;
	}
}
//删除多个数据
int SList::multiDel(int pos, int n) {
	if (pos < 1 || pos > lenth) {
		cout << "error" << endl;
		return 0;
	}
	else {
		for (int i = 0; i < n; i++) {
			data[pos - 1 + i] = data[pos - 1 + i + n];
		}
		lenth -= n;
		return 1;
	}
}
//合并两个链表
void SList::Add(int arr[], int n, int brr[], int m) {
	lenth = m + n;
	int j = 0, k = 0;
	for (int i = 0; i < m + n; i++) {
		if (*(arr + j) <= *(brr + k) && j < n) *(data + i) = *(arr + j), j++;
		else if (*(arr + j) >= *(brr + k) && k < m) *(data + i) = *(brr + k), k++;
		else if (j == n) *(data + i) = *(brr + k), k++;
		else if (k == m) *(data + i) = *(arr + j), j++;
	}
}
//循环移位
void SList::TurnSequence(int dir, int amount) {
	int* tmp = new int[lenth];
	if (dir == 0) {
		for (int i = 0; i < lenth; i++) {
			if (i < amount) tmp[lenth - amount + i] = data[i];
			else tmp[i - amount] = data[i];
		}
	}
	else {
		for (int i = 0; i < lenth; i++) {
			if (i + amount >= lenth) tmp[amount + i - lenth] = data[i];
			else tmp[i + amount] = data[i];
		}
	}
	for (int i = 0; i < lenth; i++) data[i] = tmp[i];
}
//打印链表
void SList::Display(){
	cout << lenth << " ";
	for (int i = 0; i < lenth; i++) cout << data[i] << " ";
	cout << endl;
}
//执行操作
void SList::Operation() {
	int direction, digit;
	for (int i = 0; i < 2; i++) {
		cin >> direction >> digit;
		TurnSequence(direction, digit);
		Display();
	}
}

SList::~SList(){
	delete[]data;
}

int main() {
	SList slist;
	int n;
	cin >> n;
	int* array = new int[n];
	for (int i = 0; i < n; i++) cin >> array[i];
	slist.InitList(array, n);
	slist.Display();
	slist.Operation();
	return 0;
}

问题五:计算2支股票的M天运动平均价格

题目描述:

给定2支股票的开盘价和收盘价的N天历史数据,

要求按开盘和收盘,分别计算每支股票的每个日期对应的M天移动平均价格。

假定两个股票数据如下:

日期 ? ? ? ? ? ?开盘/收盘 ? ? ?第1支股票价格S1 ? ? ? 第2支股票价格S2

2004/7/29 close 6 4

2004/7/25 close 2 6

2004/7/26 open 8 12

2004/7/30 open 2 4

2004/7/27 close 8 10

2004/7/28 open 4 2

按M=2天(日期不用连续)计算移动平均价格,按先开盘,后收盘价,输出如下:(若某日期之前,没有M-1条的记录(日期不用连续),则不用输出)

2004/7/28 open 6 7

2004/7/30 open 3 3

2004/7/27 close 5 8

2004/7/29 close 7 7

其中, 2004/7/28日的S1的值为(8+4)/2 = 6, 即将2004/7/28和(最近1条记录2004/7/26,最近2条记录,最近M-1条记录)的价格,求和并计算平均。

输入要求:

第1行:N天记录 ? M天平均

第2行到N+1行:N天2支股票的开盘与收盘价格(注意日期是无序的)

6 ?2

2004/7/29 close 6 4

2004/7/25 close 2 6

2004/7/26 open 8 12

2004/7/30 open 2 4

2004/7/27 close 8 10

2004/7/28 open 4 2

输出要求:

每个日期的最近M条记录(包括该日期的价格在内)的平均价格(若某日期之前没有M-1条的记录(日期不用连续),则不用输出)

2004/7/28 open 6 7

2004/7/30 open 3 3

2004/7/27 close 5 8

2004/7/29 close 7 7

输入样例:

6  2
2004/7/29  	close      6	 4
2004/7/25  	close      2      6
2004/7/26  	open      8      12
2004/7/30  	open      2      4
2004/7/27  	close      8      10
2004/7/28  	open      4       2

输出样例:

2004/7/28 open 6 7
2004/7/30 open 3 3
2004/7/27 close 5 8
2004/7/29 close 7 7

代码示例:

#include <iostream>
using namespace std;

#define MAX_SIZE 100
int M;

struct Stock
{
	string date;
	int price1, price2;
};

class SList {
public:
	SList();
	~SList();
	void InitList(int arr[], int n);
	int Insert(int x, int pos);
	void InsertStock(Stock s);
	int findPos(Stock s);
	void Display();
	void Calculate(string type);
private:
	int* data;
	Stock* Sdata;
	int lenth;
	int listsize;
};
//无参构造
SList::SList(){
	data = new int[MAX_SIZE];
	Sdata = new Stock[MAX_SIZE];
	listsize = MAX_SIZE;
	lenth = 0;
}
//初始化链表
void SList::InitList(int arr[], int n){
	for (int i = 0; i < n; i++)	data[i] = arr[i];
	lenth = n;
}
//查找股票应插入的位置
int SList::findPos(Stock s) {
	if (!lenth) return 0;
	else {
		int idx0 = atoi(s.date.substr(s.date.length() - 2, 2).c_str());
		for (int i = 0; i < lenth; i++) {
			int idxi = atoi(Sdata[i].date.substr(Sdata[i].date.length() - 2, 2).c_str());
			if (idxi > idx0) return i;
		}
		return lenth;
	}
}
//插入股票
void SList::InsertStock(Stock s) {
	if (lenth == 0) Sdata[0] = s;
	else {
		int pos = findPos(s);
		for (int i = lenth; i > pos; i--) Sdata[i] = Sdata[i - 1];
		Sdata[pos] = s;
	}
	lenth++;
}
//计算并输出
void SList::Calculate(string type) {
	for (int i = M - 1; i < lenth; i++) {
		cout << Sdata[i].date << " " << type;
		int sum1 = 0, sum2 = 0;
		for (int j = i; j >= i - M + 1; j--) {
			sum1 += Sdata[j].price1;
			sum2 += Sdata[j].price2;
		}
		cout << " " << sum1 / M << " " << sum2 / M << endl;
	}
}

SList::~SList(){
	delete[]data;
}

int main() {
	SList olist,clist;
	int n;
	cin >> n >> M;
	for (int i = 0; i < n; i++){
		Stock stock;
		string type;
		cin >> stock.date >> type >> stock.price1 >> stock.price2;
		if (type == "open") olist.InsertStock(stock);
		else clist.InsertStock(stock);
	}

	olist.Calculate("open");
	clist.Calculate("close");

	return 0;
}

问题五复习一下关于string的几个知识点:

  1. string转int,运用atoi(str.c_str())即可完成转化;
  2. string提取字串,运用str.substr(pos, lenth),pos是被提取的字串的开始位置,lenth为被提取字串的长度。

文章来源:https://blog.csdn.net/2203_75720729/article/details/135044213
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。