题意:题目的意思就是insert 是在一个地方插入一个字符串,然后delete是删除一个字符串,show是展示当前存在的所有字符串,然后search 是查找字符串然后输出字符串存在的序号。
思路: 我们要插入字符串的话,需要给他腾出一个空间,并且其余的都往后移动一格,所以我们先遍历移动腾出空间然后我们在把需要插入的字符串插入。 我们删除字符串的话跟插入差不多,我们要先找到,不过删除并不是实际意义上的删除,而是当前要删除的那个元素的后一个,往前面移动将其覆盖! 展示的话就是遍历输出即可 查找的话也就是遍历找到即可
#include<bits/stdc++.h>
#define maxn 10010
using namespace std;
string a[maxn];
int num = 0;//记录当前数组元素的个数
int main(){
string s,ss;
int n;
while(cin>>s){//题目意思可当做多组string输入
if(s == "insert"){//插入操作
cin>>n;
cin>>ss;
for(int i=num+1;i>n;i--){//我们先把要输入的位置空出来,其余元素后移
a[i] = a[i-1];
}
num++;//个数++,并把元素插入
a[n] = ss;
}
else if(s == "show"){//展示操作
for(int i=1;i<=num;i++){
cout<<a[i]<<" ";
}
cout<<"\n";
}
//删除操作
else if(s == "delete"){
cin>>ss;
int pos;//记录找到的位置
for(int i=1;i<=num;i++){
if(a[i] == ss){
pos = i;
break;
}
}
for(int i=pos;i<num;i++){
a[i] = a[i+1];//直接给覆盖了
}
num--;//个数--
}
//查找操作
else if(s == "search"){
cin>>ss;
for(int i=1;i<=num;i++){
if(a[i] == ss){
cout<<i<<endl;
break;
}
}
}
}
return 0;
}
那么接下来我们着重理解下线性表的做法。
注意事项:
1)插入时判断位置是否合法
2)插入后表长度加1
3)删除后表长度减去1
4)插入前判断表是否满了,满了的话重分配空间
5)输出的时候人名用空格隔开
6)每个输出占一行
7)表为空的时候,没名字,也要空一行
8)该代码没有考虑输入人名重复的问题
#include<bits/stdc++.h>
#define SIZE 100 /*列表初始长度*/
#define ADD 10 /*列表满了后增加的长度*/
typedef struct People_{
char name[20];//这里用来存字符串人名
}*People,PEOPLE;
typedef struct List_{
struct People_ *person;
int length;//存下每一个字符串的长度以及当前线性表的元素个数
int listsize;
}*List,LIST;
//这里我们要声明所有的函数。
void insert_(List L,int n,char *name);
int search_(List L,char *name);/*找到后返回其位置,下标*/
void delete_(List L,char *name);
void show_(List L);
int compare_(char *order);
void creat_List(List L);
int main(){
int n,c;
char name[20],order[7];
LIST L;
creat_List(&L);//建表
while(scanf("%s",order)!=EOF){
c=compare_(order);
switch(c){
case 1:{
/*插入名字*/
/*输入位置和名字*/
scanf("%d",&n);
scanf("%s",name);
/*判断插入位置是否合法*/
/*n=1插入到下标为0,故可插入位置为下标从0到length
故n为1到length+1*/
if(n>=1&&n<=L.length+1)
insert_(&L,n,name);
break;
}
case 2:{
/*删除名字*/
/*输入名字*/
scanf("%s",name);
delete_(&L,name);
break;
}
case 3:{
/*输出list中所有名字*/
show_(&L);
break;
}
case 4:{
/*查找位置*/
/*输入查找的名字*/
scanf("%s",name);
int d=search_(&L,name);
/*找到的话输出*/
if(d!=-1)
printf("%d\n",d+1);
break;
}
}
}
return 0;
}
/*==========================================================*/
/*用于返回数字选择功能*/
int compare_(char *order)
{
if(!strcmp(order,"insert"))
return 1;
else
if(!strcmp(order,"delete"))
return 2;
else
if(!strcmp(order,"show"))
return 3;
else
return 4;
}
/*==========================================================*/
/*建立空名单*/
void creat_List(List L)
{
L->person=(People)malloc(SIZE*sizeof(PEOPLE));
L->length=0;
L->listsize=SIZE;
}
/*==========================================================*/
void insert_(List L,int n,char *name)
{
/*判断列表是否满了*/
if(L->length==L->listsize)
L->person=(People)realloc(L->person,(L->listsize+ADD)*sizeof(PEOPLE));
/*腾出插入空间*/
for(int i=L->length-1;i>=n-1;i--)
L->person[i+1]=L->person[i];
/*插入名字*/
strcpy((L->person[n-1].name),name);
/*列表长度加1*/
L->length++;
return ;
}
/*==========================================================*/
void delete_(List L,char *name)
{
/*找出名字的位置*/
/*这里返回的直接是下标*/
int n=search_(L,name);
/*没找到返回*/
if(n==-1)
return ;
/*删除名字*/
for(int i=n;i<L->length-1;i++)
strcpy(L->person[i].name,L->person[i+1].name);
/*删除完毕,长度减去1*/
L->length--;
return ;
}
/*==========================================================*/
int search_(List L,char *name)
{
int n=-1;/*-1表示没找到*/
for(int i=0;i<L->length;i++)
{
if(!strcmp(L->person[i].name,name))
{n=i;break;}
}
return n;
}
/*==========================================================*/
void show_(List L)
{ /*如果表空,输出换行*/
if(L->length==0)
printf("\n");
else
for(int i=0;i<L->length-1;i++)
printf("%s ",L->person[i].name);
puts(L->person[L->length-1].name);
return ;
}
总体来讲,线性表的做法稍微复杂点,但是考虑更加周全,并且插入删除比较方便,这在数据量很大的情况下会有更优的效果以及效率。