【数据结构】链表及相关操作（C语言实现）

心已赠人 2022-09-27 13:28 176阅读 0赞

***Talk is cheap, show you the code.***

#include <stdio.h>
    typedef struct Node{
        int date;
        struct Node *Next;
    } List;
    
    List * CreateList() //创建一个带有空头结点的空链表
    {
        List *p;
        p = (List*)malloc(sizeof(List));
        p->Next = NULL;
        return p;
    }
    
    int Length(List *PtrL) //求表长
    {
        List *p = PtrL;
        int i = 0;
        while(p != NULL){
            p = p->Next;
            i++;
        }
        return i-1;
    }
    
    void Append1(int x, List *PtrL) //向链表的头部添加值为x的新节点
    {
        List *s;
        s = (List*)malloc(sizeof(List));
        s->date = x;
        s->Next = PtrL->Next;
        PtrL->Next = s;
    }
    
    void Append2(int x, List *PtrL) //向链表的尾部添加值为x的新节点
    {
        List *p, *s;
        p = PtrL;
        while(p->Next) p = p->Next;
        s = (List*)malloc(sizeof(List));
        s->date = x;
        s->Next = p->Next;
        p->Next = s;
    }
    
    List * FindKth(int k, List *PtrL) //查找第k个节点，返回对应指针
    {
        List *p = PtrL;
        int i = 0;
        while(p!=NULL && i<k){
            p = p->Next;
            i++;
        }
        if(i==k && p!=NULL)
            return p;
        else
            return NULL;
    }
    
    List * Find(int x, List *PtrL) //查找链表中第一个值为x的节点，返回指向该节点的指针
    {
        List *p = PtrL;
        while(p != NULL && p->date != x)
            p = p->Next;
        if(!p)
            printf("该节点不存在");
        return p;
    }
    
    void Insert(int x, int i, List *PtrL) //在链表第i个节点的位置插入值为x的新节点
    {
        List *p, *s;
        p = FindKth(i-1,PtrL);
        if(p){
            s = (List*)malloc(sizeof(List));
            s->date = x;
            s->Next = p->Next;
            p->Next = s;
        }
        else
            printf("该位置不存在\n");
    }
    
    void Delete1(int i, List *PtrL) //删除第i个节点
    {
        List *p,*s;
        p = FindKth(i-1,PtrL);
        if(!p || p->Next == NULL){
            printf("第%d个节点不存在\n", i);
            return;
        }
        else{
            s = p->Next;
            p->Next = s->Next;
            free(s);
        }
    }
    void Delete2(int x, List *PtrL) //删除所有值为x的节点
    {
        List *p, *s;
        p = PtrL->Next;
        while(p->Next){
            if(p->Next->date == x){
                s = p->Next;
                p->Next = s->Next;
                free(s);
                continue; //删除操作后指针不能向后移动，防止后面相邻的节点有相同的值
            }
            else
                p = p->Next; //若未进行删除操作，指针移向下一个节点
        }
    }
    
    void ShowList(List *PtrL) //正序输出链表中所有节点的值
    {
        List *p;
        p = PtrL;
        while(p->Next){
            printf("%d ", p->Next->date);
            p = p->Next;
        }
        printf("\n");
    }