【算法笔记第7.3节 】问题 A: 算法2-8~2-11：链表的基本操作
题目描述
链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。
下面给你基本的算法描述：
图1：链表类型的定义以及获得链表元素的算法描述
图2：链表的插入算法描述
图3：链表的删除算法描述
图4：链表的创建算法描述
输入
输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；“show”之后没有整数。
输出
如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”，否则输出“insert fail”。如果是“show”则输出列表中的所有元素，如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。
样例输入
3 3 2 1 21 show delete 1 show delete 2 show delete 1 show delete 2 insert 2 5 show insert 1 5 show insert 1 7 show insert 2 5 show insert 3 6 show insert 1 8 show get 2
样例输出
1 2 3 delete OK 2 3 delete OK 2 delete OK Link list is empty delete fail insert fail Link list is empty insert OK 5 insert OK 7 5 insert OK 7 5 5 insert OK 7 5 6 5 insert OK 8 7 5 6 5 7
提示
提示：
1、因为输入数据中含有大量的插入和删除操作（不管你信不信，反正我信了），所以必须使用链表，否则很可能会超时。这也是考查链表的特性吧。
2、初始化链表的元素是倒序的，这个使用题目中创建列表的方法（从头部插入）就可以了。
总结：
这题考查的是链表的特性。顺序表中，怎样判断何时使用顺序表何时使用链表呢？就要看它们的特点了。顺序表的特点是随机存取、随机访问，也就是说如果存取和查询比较频繁的话使用顺序表比较合适；链表的特点是插入和删除时不必移动其后的节点，如果插入和删除操作比较频繁的话使用链表比较合适。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int data;
node* next;
};
void creat(node *&head, int pos, int x)
{
node *temp = head;
for(int i=1; i<=pos-1; i++)
temp = temp->next;
node * newnode = new node;
newnode->data = x;
newnode->next = temp->next;
temp->next = newnode;
}
void insert(node *&head, int pos, int x)
{
node *temp = head,*t;
t = head->next;
int sum=1;
while(t!=NULL)
{
sum++;
t=t->next;
}
if(pos<1||pos>sum)//注意，链表位置是从1开始计数的
{
printf("insert fail\n");
return;
}
else
{
for(int i=0; i<pos-1; i++)
temp = temp->next;
node * newnode = new node;
newnode->data = x;
newnode->next = temp->next;
temp->next = newnode;
printf("insert OK\n");
}
}
void get(node *head, int x)
{
int cnt = 0;
node *temp = head->next;
while(temp!=NULL)
{
cnt++;
if(cnt==x)
{
printf("%d\n", temp->data);
return;
}
temp = temp->next;
}
printf("get fail\n");
}
void show(node *head)
{
node *now;
now = head->next;
if(now==NULL)
{
printf("Link list is empty\n");
}
else
{
while(now!=NULL)
{
printf("%d", now->data);
if(now->next==NULL)
printf("\n");
else
printf(" ");
now = now->next;
}
}
delete(now);
}
void del(node *&head, int x)
{
node *now = head->next;
node *pre = head;
int flag = 0;
int cnt = 0;
while(now!=NULL)
{
cnt++;
if(cnt==x)
{
flag = 1;
pre->next = now->next;
delete(now);
now = pre->next;
}
else
{
pre = now;
now = now->next;
}
}
if(flag==1)
printf("delete OK\n");
else
printf("delete fail\n");
}
int main()
{
int n;
scanf("%d",&n);
int m;
node *head, *temp;
head = new node;
head->next = NULL;//头结点
for(int i=0; i<n; i++)//建表
{
scanf("%d",&m);
creat(head, 1, m);
}
int num;
scanf("%d",&num);
getchar();
char a[100];
while(num--)
{
gets(a);
if(a[0]=='s')
show(head);
else if(a[0]=='g')
{
int x = 0;
for(int i=4; i<strlen(a); i++)
x = x*10+(a[i]-'0');
//printf("%d\n",x);
get(head,x);
}
else if(a[0]=='i')
{
int n1=0, n2=0, i;
for(i=7; a[i]!=' ';i++)
n1 = n1 * 10 + a[i] - '0';
for(int j=i+1; j<strlen(a); j++)
n2 = n2 * 10 + a[j] - '0';
insert(head, n1, n2);
}
else if(a[0]=='d')
{
int x=0;
for(int i=7; i<strlen(a); i++)
x = x * 10 + a[i] -'0';
del(head, x);
}
}
}