问题 A: 算法2-8~2-11：链表的基本操作

题目描述

链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。
下面给你基本的算法描述：

输入

输入数据只有一组，第一行有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<string.h>
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode;
typedef struct
{
    char mark[10];
}Mark;
void InitList(LNode *&L,ElemType number)//初始化
{
    //1.申请新节点
    //2.插入到头结点
    LNode *s;///新节点
    int i;

    ///申请新节点空间并且存入数据
    s= (LNode * )malloc(sizeof(LNode));
    s->data = number;
    ///插入到头结点（头插法）
    s->next = L->next;
    L->next = s;
}
void printList(LNode *L)
{
    L=L->next;
    while(L!=NULL)///不是写成L->next为NULL
    {
        printf("%d ",L->data);
        L=L->next;
    }
    printf("\n");
}
void deletelist(LNode *&L,int i)///删除
{
    //1.找前驱节点
    //2.排除不合理的位置
    //3.删除 0.1
    LNode *qlen,*q,*qfree;
    qlen=L;
    q=L;
    int length=0;
    while(qlen->next!=NULL)//求出L长度
    {
        qlen=qlen->next;
        ++length;
    }
    //printf("当前L长度为%d\n",length);
    if(i<=0||i>length)
    {
        printf("delete fail\n");
        return ;
    }
    else
    {
        //q是要删除部分的前驱节点
        int j=1;
        while(q->next!=NULL)
        {
            if(j==i)
            {
                qfree = q->next;
                q->next = q->next->next;
                free(qfree);
                printf("delete OK\n");
                return ;///少了这一步，会崩溃....
            }
            ++j;
            q=q->next;
        }
        return ;
    }
}
int GetElem(LNode *L,int number)
{
    LNode *qlen,*q;
    qlen=L;
    q=L;
    int length=0;
    while(qlen->next!=NULL)
    {
        qlen=qlen->next;
        ++length;
    }
    if(number<=0||number>length)
    {
        return -1;
    }
    int j=0;///这里又是j=0不是j=1
    while(q->next!=NULL)
    {
       q=q->next;
       ++j;
       if(j==number)
       {
           return q->data;
       }
    }
}
int insertlist (LNode *&L,int i,int number)
{
    LNode *q,*qlen,*s;
    int length=0;
    q=L;
    qlen=L;
    while(qlen->next!=NULL)
    {
        qlen=qlen->next;
        ++length;
    }
    if(i<=0||i>length+1)
    {
        return -1;
    }
    int j=0;
    while(q!=NULL)
    {
        ++j;
        if(j==i)
        {
            s=(LNode *)malloc(sizeof(LNode));
            s->data=number;
            s->next=q->next;
            q->next=s;
            //printList(L);
            return 1;
        }
        q=q->next;
    }
}
int main (void)
{
    int n;
    ElemType number;
    LNode *L,*q;///声明链表要带*号

    ///把L表置为空表
    L= (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&number);
        InitList(L,number);
    }
    int linenumber;
    scanf("%d",&linenumber);
    Mark a;
    for(int i=1;i<=linenumber;i++)
    {
        scanf("%s",a.mark);
        if(strcmp(a.mark,"show")==0)
        {
            if(L->next==NULL)
                printf("Link list is empty\n");
            else
                printList(L);
        }
        else if(strcmp(a.mark,"delete")==0)
        {
            int number;
            scanf("%d",&number);
            deletelist(L,number);
        }
        else if(strcmp(a.mark,"get")==0)
        {
            int number;
            scanf("%d",&number);
            int x = GetElem(L,number);
            if(x==-1)
                printf("get fail\n");
            else
                printf("%d\n",x);
        }
        else if(strcmp(a.mark,"insert")==0)
        {
            int i,number;
            scanf("%d%d",&i,&number);
            int x = insertlist(L,i,number);
            if(x==1)
                printf("insert OK\n");
            else
                printf("insert fail\n");
        }
    }
    return 0;
}