单链表的各种操作实现（带头结点）

最近复习数据结构，链表的各种操作都得重新敲一遍，带头结点链表更易于理解与实现，今天就先敲下带头结点的单链表实现。

1.注意事项

代码中LNode* 和LinkList是一样的结构，只是强调作用不同。
使用LinkList强调这是一个单链表，使用LNode*强调这是一个结点。

2.代码实现

代码含增，删，查，头插法建表，尾插法建表，逆置等操作

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

typedef struct LNode{
    int data; //数据域
    struct LNode *next; //指针域
}LNode,*LinkList;

bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //分配空间得到头结点L，注意形式
    if(L==NULL)
        return false;
    L->next = NULL;
    return true;
}

bool Empty(LinkList L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

LNode * GetElem(LinkList L,int i){ //可以封装在增，删函数中
    if(i<0)
        return NULL;
    LNode *p;
    int j = 0;
    while(p != NULL && j<i){ //找到第i个结点
        p = p->next;
        j++;
    }
    return p;
}

// 带头结点尾插法建表 链表中数据顺序正向
LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));//建立头结点
    LNode *s,*r = L;//r为表尾指针,最后以r结尾指向NULL，故此处不对L->next设NULL
    scanf("%d\n",&x);
    while(x!=9999){
        s =(LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;// r指向新的表尾结点s
        scanf("%d\n",&x);
    }
    r->next = NULL;
    return L;
}

//带头结点头插法建表 表中数据顺序逆向
LinkList List_HeadInsert(LinkList &L){
    int x;
    LNode *s;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d\n",&x);
    while(x!=9999){ //此处与后插操作逻辑一致
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d\n",&x);
    }

    return L;
}

// 将链表数据逆置，使用头插法新建一个表，数据用旧表
LinkList ListRerverse(LinkList L,LinkList &G){
    LNode *s;
    G = (LinkList)malloc(sizeof(LNode));
    G->next = NULL;
    while(L->next!=NULL){
        s = (LNode*)malloc(sizeof(LNode));
        L = L->next;
        s->data = L->data;
        s->next = G->next;
        G->next = s;
    }
    return G;
}


// 指定结点后插操作，数据给i
bool InserNextNode(LNode *p,int e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 指定结点前插操作，数据给i-1，i-1的数据给新建的节点i
bool InserPriorNode(LNode *p,int e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data; //交换两结点数据，实现逻辑上前插
    p->data = e;
    return true;
}


bool ListInsert(LinkList &L,int i,int e){ //在第i个位置插入元素e
    if(i<1)
        return false;
    LNode *p;
    int j = 0;// 当前p指向的是第几个结点
    p = L;// 头结点是第0个结点，不存数据
    while(p!=NULL && j<i-1){ //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p==NULL) //i值不合法,就是结点没这么多，你输的位序超了，指向了NULL
        return false;

    return InserNextNode(p,e);//后插
}


bool ListDelete(LinkList &L, int i, int &e){ // 删除第i个元素
    if(i<1)
        return false;
    LNode *p;
    int j = 0;// 当前p指向的是第几个结点
    p = L;// 头结点是第0个结点，不存数据
    while(p!=NULL && j<i-1){ //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p==NULL)
        return false;

    LNode *q = p->next;// 让q指向被删除结点
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}


bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q = p->next;
    p->data = p->next->data;// 把删除结点的数据用后面结点数据覆盖，就删除了，所以要删去后面一个结点，做题的时候画个图
    p->next = q->next;
    free(q);
    return true;
}

LNode * LocateElem(LinkList L, int e){ //按值查找
    LNode*p = L->next;// 从第1个结点开始
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;
}

int Length(LinkList L){ //求表长
    int len = 0;
    LNode *p = L->next;
    while(p != NULL){
        p = p->next;
        len++;
    }
    return len;
}

bool PrintList(LinkList L,int i){ //可以封装在增，删函数中
    if(i<0)
        return false;
    int j = 0;
    while(L != NULL && j<i){ //找到第i个结点

        L = L->next;
        printf("%d ",L->data);
        j++;
    }
    printf("\n");
    return true;
}

int main(){
    LinkList L,G;
    printf("please enter numbers:");
    List_TailInsert(L);
//    List_HeadInsert(L);

    printf("the list len is:%d\n",Length(L));
    PrintList(L,Length(L));

    ListRerverse(L,G);
    PrintList(G,Length(G));
    printf("the list len is:%d\n",Length(G));

//    ListInsert(L,2,10);
//    PrintList(L,Length(L));
//    printf("the list len is:%d\n",Length(L));

    int e=-1;
    while(L->next!=NULL){
        int i=1;
        ListDelete(L,i,e);
        i++;
    }

    return 0;
}