题目描述
思路:从题目可以看出这是数据结构算法的线性表的插入,查找,获取,删除,遍历等功能。
首先创建一个类class(线性表)
class SeqList
{
public:
//构造函数
SeqList()
{
length = 0;
int data[20] = {0};
}
//按位查找
void Seek(int Data);
//获取某个位置
void Get(int location);
//插入
void Insert(int location,int Data);
//删除
void Delete(int location);
//输出数据
void Vshow();
private:
int data[20];
int length;
};
第一个算法: 插入算法
但是插入之前我们会手动输入插入的位置(location),之后从该位置后的每一个数组单元进行后移一个位置,再把值插入即可,长度(length)加1。如果之前表为空,插入时则无需后移数组单元。还需要注意的是表满,输入位置不正确情况。
void SeqList::Insert(int location, int Data)
{
int i;
if(length > 20 )
{
cout << "上溢";
}
else if(location < 0 || location > 20)
{
cout << "位置不正确";
}else
{
if(length == 0)
{
data[location-1] = Data;
}
else
{
for( i =length; i>= location; i--)
{
data[i] = data[i-1];
}
data[location-1] = Data;
}
}
length++;
}
由代码可以看出首先判断是否表满,输入是否正确情况,再判断是不是之前列表为空,为空则直接插入第一个位置,不为空则从插入位置之后数组单元进行后移(从后往前移)
第二个算法: 查找(按值查找)
用查找的元素值在表中遍历的同时比对查找,查到即可输出该位置。注意:如有查不到情况则输出None
void SeqList::Seek(int Data)
{
int i;
int k = 0;
int location = 0;
for(i = 0; i < length; i++)
{
if(Data == data[i])
{
location = i+1;
}else
{
k++;
}
}
if(k == length)
{
cout <<"None";
}
cout << location;
}
这里k指的是在表中找不到则k会跟长度(length)一样,由此判断找不到。
第三个算法: 获取某个元素值(按位置)
这个算法就更简单了,直接输出该位置元素即可。注意:要判断查找的位置存不存在。
void SeqList::Get(int location)
{
if(location < 0 || location >20)
{
cout <<"位置不正确";
}else
{
cout << data[location-1];
}
}
第四个算法: 删除某个位置的元素
输入删除的位置之后,输出该位置删除的元素值,再从该位置后的每一个数组单元进行前移一个位置即可(从前往后),长度(length)减1。注意:还需判断表是否为空,删除位置是否正确。
void SeqList::Delete(int location)
{
int i;
if(length == 0)
{
cout << "下溢";
}else if(location < 0 || location > length)
{
cout << "位置不正确";
}else
{
cout << data[location-1];
for(i = location-1; i < length; i++)
{
data[i] = data[i+1];
}
length--;
}
}
最后可以按照题目要求写出主函数,进行算法的拼接(拼接过程省略),接下来就看看整体代码吧:
#include <iostream>
using namespace std;
class SeqList
{
public:
//构造函数
SeqList()
{
length = 0;
int data[20] = {0};
}
//按位查找
void Seek(int Data);
//获取某个位置
void Get(int location);
//插入
void Insert(int location,int Data);
//删除
void Delete(int location);
//输出数据
void Vshow();
private:
int data[20];
int length;
};
void SeqList::Vshow()
{
int i;
for(i = 0; i < length; i++)
{
cout << data[i];
}
}
void SeqList::Seek(int Data)
{
int i;
int k = 0;
int location = 0;
for(i = 0; i < length; i++)
{
if(Data == data[i])
{
location = i+1;
}else
{
k++;
}
}
if(k == length)
{
cout <<"None";
}
cout << location;
}
void SeqList::Get(int location)
{
if(location < 0 || location >20)
{
cout <<"位置不正确";
}else
{
cout << data[location-1];
}
}
void SeqList::Insert(int location, int Data)
{
int i;
if(length > 20 )
{
cout << "上溢";
}
else if(location < 0 || location > 20)
{
cout << "位置不正确";
}else
{
if(length == 0)
{
data[location-1] = Data;
}
else
{
for( i =length; i>= location; i--)
{
data[i] = data[i-1];
}
data[location-1] = Data;
}
}
length++;
}
void SeqList::Delete(int location)
{
int i;
if(length == 0)
{
cout << "下溢";
}else if(location < 0 || location > length)
{
cout << "位置不正确";
}else
{
cout << data[location-1];
for(i = location-1; i < length; i++)
{
data[i] = data[i+1];
}
length--;
}
}
int main(int argc, char** argv) {
SeqList D;
char letter;
int k;
int i;
int data;
int location;
cin >> letter;
while (letter != 'E')
{
switch (letter)
{
case 'I':
cin >> k;
for(i = 0; i < k; i++)
{
cin >> location;
cin >> data;
D.Insert(location, data);
}
break;
case 'S':
cin >> data;
D.Seek(data);
break;
case 'G':
cin >> location;
D.Get(location);
break;
case 'D':
cin >> location;
D.Delete(location);
break;
case 'V':
D.Vshow();
break;
default:
break;
}
cin >> letter;
}
return 0;
}