DS|顺序表

发布时间：2023年12月17日

问题一：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的几个知识点：

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

文章来源:https://blog.csdn.net/2203_75720729/article/details/135044213
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！