线性表的链式存储结构

先上代码：

#ifndef _LIST_H_
#define _LIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef  int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node* next;
} Node;
typedef struct Node* LinkList;

void CreateListHead(LinkList *L,int n);

int TraveList(LinkList L);

int getElem(LinkList L,int i,ElemType* e);

int ListInsert(LinkList* L,int i,ElemType e);

int ListDelete(LinkList* L,int i,ElemType* e);

int ClearList(LinkList* L);
#endif // _LIST_H_

#include "list.h"

void CreateListHead(LinkList* L,int n){
    LinkList p;
    int i;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    srand(time(0));//初始化随机数种子
    for(i = 0;i < n;i++){
        p = (LinkList)malloc(sizeof(Node));//为新节点开辟空间
        p->data = rand()%100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;
    }

}

int TraveList(LinkList L)
{
    int i = 0;
    LinkList p;
    p = L;
    while(p->next)
    {
        i++;
        p=p->next;
        printf("the number is %d,the data is %d\n",i,p->data);
    }
    return i;
}

int getElem(LinkList L,int i,ElemType* e){

    int j = 1;
    LinkList p;
    p = L->next;
    while(p && j<i)
    {
        p = p->next;
        j++;
    }

    if(!p || j>i)
        return -1;
    *e = p->data;
    return 0;
}

int ListInsert(LinkList *L,int i,ElemType e)
{
    int j = 1;
    LinkList p,s;
    p = *L;
    if(i < 1)
        return -1;
    while(p && j<i)
    {
        p = p->next;
        j++;
    }
    if(!p || j>i)
        return -1;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 0;
}

int ListDelete(LinkList* L,int i,ElemType* e)
{
    int j = 1;
    LinkList p,q;
    p = *L;
    while(p->next && j < i)
    {
        p = p->next;
        j++;
    }
    if(!p->next || j>i)
        return -1;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return 0;
}

int ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    printf("List is clear");
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

int main()
{
    LinkList L;
    int x;

    CreateListHead(&L,8);

    TraveList(L);

    getElem(L,5,&x);
    printf("the number 5 element is %d\n",x);

    ListInsert(&L,6,100);
    TraveList(L);

    ListDelete(&L,7,&x);
    printf("the number 7 element is %d\n",x);
    TraveList(L);

    ClearList(&L);

    return 0;
}

正文：

N个节点链接成一个链表，即为线性表的链式存储结构，除本身的信息之外，还需存储一个指示其直接后继的信息即地址。
链表中第一个节点的存储位置叫做头指针，第一个节点前设一个头节点。
创建链表关键步骤
```
p->next = (*L)->next;
(*L)->next = p;
```
该方法是头插法：首先使插入节点指向头节点所指向的下一节点，再使头节点指向要插入的节点。

遍历链表

p = L;
    while(p->next)
    {
        i++;
        p=p->next;
        printf("the number is %d,the data is %d\n",i,p->data);
    }

一定要使用工作指针p，做为参数传入的指针L不能参与循环，会改变其指向。

插入节点
```
s->next = p->next;
    p->next = s;
```
首先使要插入的节点指向要插入位置的后继节点，再使前一节点指向要插入的节点。
删除节点
```
q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
```
首先使工作节点q指向工作节点p的后继节点，再使p指向后继节点的后继节点，最后释放q。

注意

代码有些地方使用了二级指针，注意理解。

线性表的链式存储结构

线性表的链式存储结构

先上代码：

正文：

注意