|
请你定义一个链表，可以对链表进行“在某个元素之前插入一些元素”、“删除某个位置的元素”、“查找某元素”、“获取某个位置的元素”、“遍历输出所有元素”、“求链表的长度”等操作。键盘输入一些命令，可以执行上述操作。本题中，链表元素为整数，链表的第一个元素位置为1，链表的最大长度为20。
输入描述
各个命令以及相关数据的输入格式如下：
在某个位置之前插入操作的命令：I，接下来的一行是插入的元素个数n，
下面是n行数据，每行数据有两个值，分别代表插入位置与插入的元素值
查找某个元素：S ?x，x是要查找的元素值
获取某个位置的元素：G ?i，i是需要获取的元素位置
删除某个位置的元素：D ?i，i是被删除的元素位置
求链表的长度：L
遍历输出所有元素：V
当输入的命令为E时，程序结束。
输出描述
当输入的命令为S时，输出要查找元素的位置，如果没找到，输出None
当输入的命令为G时，输出获取的元素值，如果输入的元素位置不正确，
输出“位置不正确”
当输入的命令是D时，输出被删除的那个元素值，如果表空，输出“下溢”，
如果输入的位置不正确，输出“位置不正确”
当输入命令是I时，如果输入的位置不正确，输出“位置不正确”
当输入的命令是L时，输出链表的长度
注意，所有的元素均占一行。
输入样例
I
2
1 1
2 2
S 2
D 1
I
2
1 3
2 4
G 2
L
V
E
输出样例
2
1
4
3
3
4
2
注意:本校oj貌似不给"endl"过.....
#include<iostream>
using namespace std;
const int N = 21;
struct Node {
int data;
Node* next;
};
class Link_list {
public:
Node* head;
int lenth;
Link_list() {
lenth = 0;
head = new Node;//★
head->next = NULL;
}
void AddNode(int site, int data);//I
void GetValue(int site);//G
int SearchSite(int num);//S
void Delete(int site);//D
void PrintList();//V
};
void Link_list::AddNode(int site, int data)
{
if (site < 1) {
cout << "位置不正确" ;
return;
}
//cout << site << data << endl;
Node* p = head;
Node* node = NULL;
int cnt = 0;
while (p && cnt < site - 1)
{
p = p->next;
cnt++;
}
node = new Node;
node->data = data;
node->next = p->next;
p->next = node;
lenth++;
}
void Link_list::PrintList()
{
Node* p = head->next;
int cnt=0;
while (p)
{
cnt++;
cout << p->data ;
// if(cnt!=lenth){
// cout << endl;
// }
p = p->next;
}
}
int Link_list::SearchSite(int num)
{
int cnt = 0;
Node* p = head;
while (p->next)
{
p = p->next;
cnt++;
if (p->data == num) {
return cnt;
}
}
return -1;
}
void Link_list::GetValue(int site)
{
Node* p = head;
int cnt = 0;
while (p->next && cnt < site)
{
p = p->next;
cnt++;
}
if (site < 1 || p == NULL)
{
cout << "位置不正确" ;
}
else {
cout << p->data ;
}
}
//根据坐标删节点
void Link_list::Delete(int site)
{
Node* p = head;
int cnt = 0;
while (p && cnt < site-1)
{
p = p->next;
cnt++;
}
int value;
if (head->next == NULL) {
cout << "下溢" ;
}
else if (p == NULL || site < 1) {
cout << "位置不正确" ;
}
else {
Node* q = p->next;
value = q->data;
p->next = q->next;
delete q;
lenth--;
cout << value ;
}
}
int main()
{
Link_list list;
char ch;
int isContinue = 1;
while (isContinue)
{
cin >> ch;
switch (ch)
{
case 'I':
int n;
int site, data;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> site >> data;
list.AddNode(site, data);
}
break;
case 'V':
list.PrintList();
break;
case 'D':
int delSite;
cin >> delSite;
list.Delete(delSite);
break;
case 'L':
//int len = list.lenth;
cout << list.lenth ;
break;
case 'S':
int num, t;
cin >> num;
t = list.SearchSite(num);
if (t > 0) {
cout << t ;
}
else {
cout << "None";
}
break;
case 'G':
int pos;
cin >> pos;
list.GetValue(pos);
break;
case 'E':
isContinue = 0;
break;
}
}
return 0;
}
|