题目要求: 请你定义一个顺序表,可以对顺序表进行如下操作:
(1)在某个元素之前插入一些元素 (2)删除某个位置的元素 (3)查找某元素 (4)获取某个位置的元素 (5)遍历输出所有元素 键盘输入一些命令,可以执行上述操作。本题中,顺序表元素为整数,顺序表的第一个元素位置为1,顺序表的最大长度为20。
输入描述 各个命令以及相关数据的输入格式如下:
在某个位置之前插入操作的命令:I,接下来的一行是插入的元素个数n, 下面是n行数据,每行数据有两个值,分别代表插入位置与插入的元素值
查找某个元素:S x,x是要查找的元素值
获取某个位置的元素:G i,i是需要获取的元素位置
删除某个位置的元素:D i,i是被删除的元素位置
遍历输出所有元素:V
当输入的命令为E时,程序结束 输出描述 当输入的命令为S时,请输出要查找元素的位置,如果没找到,请输出None
当输入的命令为G时,请输出获取的元素值,如果输入的元素位置不正确, 输出“位置不正确”
当输入的命令是D时,请输出被删除的那个元素值,如果表空,输出“下溢”, 如果输入的位置不正确,输出“位置不正确”
当输入命令是I时,如果表满,输出“上溢”,如果输入的位置不正确, 输出“位置不正确” 注意,所有的元素均占一行 输入样例 I 2 1 1 2 2 S 2 D 1 I 2 1 3 2 4 G 2 V E 输出样例 2 1 4 3 4 2
解题思路: 操作数组,重点为通过移动数组元素实现线性表的插入,删除操作。 然后,注意细节 !
通关代码:
#include <iostream>
#define MAXSIZE 20
using namespace std;
class SeqList {
public:
SeqList():len_(0) {}
public:
void Insert(int pos, int val);
int Delete(int pos);
int Search(int val);
int Get(int pos);
void Print();
private:
int arr_[MAXSIZE];
int len_;
};
void SeqList::Insert(int pos, int val) {
if (len_ == MAXSIZE) throw "上溢";
if (pos < 1 || pos > MAXSIZE) throw "位置不正确";
for (int i = len_; i > pos - 1; i--) {
arr_[i] = arr_[i - 1];
}
arr_[pos - 1] = val;
len_++;
}
void SeqList::Print() {
for (int i = 0; i < len_; i++) {
cout << arr_[i] << endl;
}
}
int SeqList::Delete(int pos) {
if (len_ == 0) throw "下溢";
if (pos < 1 || pos > len_ + 1) throw "位置不正确";
int deletedVal = arr_[pos - 1];
for (int i = pos; i < len_; i++) {
arr_[i - 1] = arr_[i];
}
len_--;
return deletedVal;
}
int SeqList::Get(int pos) {
if (pos < 1 || pos > len_ + 1) throw "位置不正确";
return arr_[pos - 1];
}
int SeqList::Search(int val) {
bool isFind = false;
int pos;
for (int i = 0; i < len_; i++) {
if (arr_[i] == val) {
isFind = true;
pos = i + 1;
break;
}
}
if (isFind == false) throw "None";
return pos;
}
int main() {
SeqList list;
char command;
int n, pos, val;
while (cin >> command) {
if (command == 'E') break;
try {
switch (command) {
case 'I':
cin >> n;
for (int i = 0; i < n; i++) {
cin >> pos >> val;
list.Insert(pos, val);
}
break;
case 'D':
cin >> pos;
cout << list.Delete(pos) << endl;
break;
case 'S':
cin >> val;
cout << list.Search(val) << endl;
break;
case 'G':
cin >> pos;
cout << list.Get(pos) << endl;
break;
case 'V':
list.Print();
break;
}
} catch (const char* str) {
cout << str << endl;
}
}
return 0;
}
题目要求: 同上。
解题思路: 水。
通关代码:
#include <iostream>
using namespace std;
struct Node {
int _val;
Node* _next;
Node(int val):_val(val), _next(NULL) {}
};
class List {
public:
List();
~List();
public:
void Insert(int pos, int val);
int Search(int val);
int Get(int pos);
int Delete(int pos);
int getLength();
void Print();
private:
Node* head_;
int length_;
};
List::List() {
head_ = new Node(-1);
length_ = 0;
}
List::~List() {
Node* previousNext = NULL;
for (Node* p = head_; p != NULL; p = previousNext) {
previousNext = p->_next;
delete p;
}
}
void List::Insert(int pos, int val) {
if (pos < 1) throw "位置不正确";
int count = 0;
Node* node = new Node(val);
for (Node* p = head_; p != NULL; p = p->_next) {
if (count + 1 == pos) {
node->_next = p->_next;
p->_next = node;
}
count++;
}
length_++;
}
int List::Search(int val) {
int count = 0;
int pos;
bool isFind = false;
for (Node* p = head_; p != NULL; p = p->_next) {
if (p->_val == val) {
isFind = true;
pos = count;
break;
}
count++;
}
if (isFind == false) throw "None";
return pos;
}
int List::Delete(int pos) {
if (length_ == 0) throw "下溢";
if (pos < 1 || pos > length_) throw "位置不正确";
int count = 0;
int val;
Node* DeletedNode = NULL;
for (Node* p = head_; p != NULL; p = p->_next) {
if (count + 1 == pos) {
DeletedNode = p->_next;
val = DeletedNode->_val;
p->_next = p->_next->_next;
delete DeletedNode;
break;
}
count++;
}
length_--;
return val;
}
int List::Get(int pos) {
if (pos < 1 || pos > length_) throw "位置不正确";
int count = 0;
int val;
for (Node* p = head_; p != NULL; p = p->_next) {
if (count == pos) {
val = p->_val;
break;
}
count++;
}
return val;
}
int List::getLength() {
return length_;
}
void List::Print() {
for (Node* p = head_->_next; p != NULL; p = p->_next)
cout << p->_val << endl;
}
int main() {
List list;
char command;
int n, pos, val;
while (cin >> command) {
if (command == 'E') break;
try {
switch (command) {
case 'I':
cin >> n;
for (int i = 0; i < n; i++) {
cin >> pos >> val;
list.Insert(pos, val);
}
break;
case 'S':
cin >> val;
cout << list.Search(val) << endl;
break;
case 'G':
cin >> pos;
cout << list.Get(pos) << endl;
break;
case 'D':
cin >> pos;
cout << list.Delete(pos) << endl;
break;
case 'L':
cout << list.getLength() << endl;
break;
case 'V':
list.Print();
break;
}
} catch (const char* str) {
cout << str << endl;
}
}
return 0;
}
毕。