链表的基本操作（C语言以带头结点的单链表为例）

前言：

　　最近在忙着专业课的复习，准确的来说是预习，加上自己比较懒，而且由于网站的备案问题得重新备案，比较麻烦，就一直拖到现在，挺长时间没更新博客了。刚好这几天临近清明假期，时间比较多，就想来这里写点东西。由于这几天刚好复习到数据结构中的链表，这里就以带头结点的单链表为例，熟悉一下单链表的基本操作（其实是一开始连反转单链表都不会，很难受，就想着一定要弄懂），由于近些年来408只能用C/C++（不能用Java是真的难受），由于C++不熟练，故以后涉及到考研相关的代码都用C。

#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <stdbool.h>

//链表定义
typedef struct LinkList
{
    int data;
    struct LinkList* next;
}Lnode, *LinkList;

//创建一个data为n,next域为NULL的节点
Lnode* createNode(int n){
    Lnode *s = (Lnode*)malloc(sizeof(LinkList));
    s->data = n;
    s->next = NULL;
    return s;
}

//尾插法创建链表
LinkList createLinkList(){
    Lnode* head = (Lnode*)malloc(sizeof(Lnode));
    Lnode* p = head;
    p->next = NULL;
    int n;
    scanf("%d",&n);
    while(n != 9999){
        Lnode* s = (Lnode*)malloc(sizeof(Lnode));
        s->data = n;
        s->next = NULL;
        p->next = s;
        p = p->next;
        scanf("%d", &n);
    }
    return head;
}

//打印链表
void printLinkList(LinkList L){
    Lnode *p = L->next;
    while(p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
}

//回收链表
void destoryLinkList(LinkList L){
    Lnode *p = L->next, *q;
    while(p != NULL){
        if(p->next == NULL){
            free(p);
            return;
        }else{
            q = p->next;
            free(p);
            p = q;
        }
    }
}

//删除绝对值相同的节点，仅保留首次出现的
void deleteSameAbsNode(LinkList L, int n){
    int i = 0, *isExist;
    isExist = (int *)malloc(sizeof(int) * (n + 1));
    for(i;i <= n;i++){
        *(isExist + i) = 0;
    }
    Lnode *p = L, *r;
    while(p->next != NULL){
        if(*(isExist + abs(p->next->data)) == 0){
            * (isExist + abs(p->next->data)) = 1;
            p = p->next;
        }else{//删除p的后继节点
            r = p->next;
            p->next = p->next->next;
            free(r);
        }
    }
    free(isExist);
    return;
}

//获取表长
int getLength(LinkList L){
    int n = 0;
    Lnode *p = L->next;
    while(p != NULL){
        n ++;
        p = p->next;
    }
    return n;
}

//按值查找
Lnode* LocateElem(LinkList L, int target){
    Lnode *p = L->next;
    while(p != NULL && p->data != target){
        p = p->next;
    }
    return p;
}


//按序号查找
Lnode* getElem(LinkList L, int i){
    if(i == 0) return L;
    if(i < 1) return NULL;
    int t = 1;
    Lnode *p = L->next;
    while(p && t < i){
        p = p->next;
        t ++;
    }
    return p;
}

//指定位置插入一个节点
bool listInsert(LinkList L, int i, Lnode *s){
    if(i < 1 || i > getLength(L) + 1){
        printf("输入不合法，插入失败！");
        return false;
    }
    Lnode *p = getElem(L,i-1);
    s->next = p->next;
    p->next = s;
}

//删除指定位置节点
bool listDelete(LinkList L, int i){
    if(i < 1 || i > getLength(L)){
        printf("输入不合法，删除失败！");
        return false;
    }
    Lnode *p, *q;
    p = getElem(L, i - 1);//查找删除位置的前驱结点
    q = p->next;//q指向被删除节点
    p->next = q->next;
    free(q);
    return true;
}

//反转链表
void reverseLinklist(LinkList L){
    Lnode *q = L->next,*p = q->next, *r;
    while(p->next != NULL){
        r = p->next;
        p->next = q;
        q = p;
        p = r;
    }
    p->next = q;
    L->next->next = NULL;
    L->next = p;
    return;
}

int main(){
    LinkList L = createLinkList();
    /*
    **测试代码
    **
    */

    destoryLinkList(L);
    return 0;
}