(2)链表
单链表结点的定义：
typedef struct LNode//单链表结点类型，LNode不能省略，因为结构体内使用了LNode
{
    ElemTpye data;//数据域
    struct LNode *next;//指针域
}LNode,*LinkList; 
头指针：链表第一个结点的存储位置，用来标识单链表。
头结点：在单链表第一个结点之前附加的一个结点，为了操作上的方便。
若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，他标识一个链表。
头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。但头结点不是必须的。
L为链表的头指针，则L->next为链表的第一个实质性元素，及L头指针指向头结点，然后L->可以理解为头结点的指针域，指向链表的第一个实质性元素。

链表优点：插入和删除不需要移动元素，只需要修改指针。
        不需要大量的连续的存储空间。
链表缺点：单链表附加指针域，也存在浪费存储空间的缺点。
        查找操作时需要从表头开始遍历，依次查找，不能随机存取。

//链表插入
//创建新结点
q=(LNode*)malloc(sizeof(LNode));
q->data=x;
//头部和中间插入方法
q->next=p->next;//p为插入的q前的数据
p->next=q;
//尾部插入方法
p->next=q;
q->next=NULL;
//链表删除

p=GetElem(L,i-1);
p->next=q->next;
free(q);

//链表按位置查找
LNode *p=L->next;//L为头指针，L->指向链表的第一个实质性元素
int j=1;
while(p&&j<i)//p为非末尾元素时为非空，i为查到的元素序号，直至j=i时p查找到
{
    p=p->next;
    j++
}
return p;

//链表按值查找
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
{
    p=p->next;
}
return p;
//头插法新建链表
开始->定义链表头指针->头结点申请空间->scanf读取第一个元素值->开启while循环建链表->打印链表->结束
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
//LNode*是结构体指针和LinkList是完全等价的
void list_head_insert(LNode* &L)
{
    L=(LinkList)malloc(sizeof (LNode));//申请头结点空间,头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);//头结点不存放数据，所以x放在第一个数据元素里面
    LNode* s;//用来申请新的结点
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof (LNode));
        s->data=x;
        s->next=L->next;//s的next指向原本链表的第一个结点
        L->next=s;
        scanf("%d",&x);
    }
}
void print_list(LinkList L)//L前没有&，所以函数内L的改变不会引起函数外L改变
{
    L=L->next;
    while(L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}
int main() {
    LinkList L;//L是链表头指针你
    list_head_insert(L);
    print_list(L);
    return 0;
}

//尾插法新建链表
开始->定义链表头指针->头结点申请空间，定义尾指针r，指向头结点L->scanf读取第一个元素值->开启while循环建链表->打印链表->结束
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

void list_tail_insert(LinkList &L)
{
    L=(LinkList) malloc(sizeof (LNode));
    L->next=NULL;
    ElemType x;
    LNode *s,*r=L;//s用来指向新结点,r始终指向链表尾
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LinkList) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;//新结点给尾结点的next指针
        r=s;//r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;//让尾结点的next为NULL
}
void print_list(LinkList L)
{
    L=L->next;
    while(L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}
int main()
{
    LinkList L;
    list_tail_insert(L);
    print_list(L);
    return 0;
}

//链表按位置查找及按值查找
//链表中L头结点是位置0，第一个元素值是位置1
LinkList GetElem(LinkList L,int SearchPos)//链表按位置查找
{
    int i=0;
    if (SearchPos<0)
    return 0;
    while(L&&i<SearchPos)
    {
        L=L->next;
        i++;
    }
    return L;
}
int main()
{
    LinkList L;
    list_tail_insert(L);
    LinkList search;//用来存储拿到的某个结点
    search=GetElem(L,2);
    printf("%d",search->data);
    return 0;
}

//链表按值查找
LinkList LocatElem(LinkList L,ElemType SearchVal)//链表按值查找
{
    while(L)
    {
        if(L->data==SearchVal)
        return L;
        else
        L=L->next;
    }
    return NULL;
}
int main()
{
    LinkList L;
    list_tail_insert(L);
    LinkList search;
    search= LocatElem(L,2);
    printf("%d",search->data);
    return 0;
}

//往第i个位置插入元素
开始->定义链表头指针->尾插法新建链表->要插入第i个位置，我们通过GetElem按位置查找函数拿到第i-1个位置的元素地址->把新结点放到i-1元素的后面->结束
bool ListFrontInsert(LinkList L,int i,ElemType InsertVal)
{
    LinkList p = GetElem(L,i-1);
    if(p==NULL)
        return false;
    LinkList q=(LinkList) malloc(sizeof (LNode*));//为新结点申请空间
    q->data=InsertVal;
    q->next=p->next;
    p->next=q;
}