【C语言数据结构】线性表-链式存储(单链表)

蔚落 2024-02-28 06:16 64阅读 0赞

--------------------

#### 线性表-链式存储-单链表 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //定义元素数据类型
    #define ElemType int
    
    //定义结点结构体
    typedef struct LNode {
        
        //数据域，说白了就是存放当前节点的数据的。
        ElemType data;
        //指针域，就是存放这个节点指向的下一个节点的地址
        struct LNode *next;
    } LNode, *LinkList;   //LinkList就是LNode的代指
    
    //函数声明
    bool Empty(LinkList L);
    
    //初始化链表
    void InitList(LinkList *L) {
        
        //给链表的开头的结点分配一个LNode结构体大小的内存空间
        *L = (LinkList) malloc(sizeof(LNode));
        //将后继结点设置为NULL，也就是现在只有这一个节点
        (*L)->next = NULL;
    }
    
    //头插法建立单链表
    LinkList ListInsert_Head(LinkList *L) {
        
        InitList(L);
        ElemType Elem;
        printf("请输入要插入的元素数据(输入0结束):");
        scanf("%d", &Elem);
        while (Elem != 0) {
        
            //建立一个新的节点
            LinkList newNode = (LinkList) malloc(sizeof(LNode));
            newNode->data = Elem;
            newNode->next = (*L)->next;
            (*L)->next = newNode;
            scanf("%d", &Elem);
        }
        return *L;
    }
    
    //尾插法建立单链表
    LinkList ListInsert_Tail(LinkList *L) {
        
        InitList(L);
        ElemType Elem;
        LNode *p,*r = (*L);
        printf("请输入要插入的元素(输入0结束):");
        scanf("%d", &Elem);
        while (Elem != 0) {
        
            p = (LinkList) malloc(sizeof(LNode));
            p->data = Elem;
            p->next = NULL;
            r->next = p;
            r = p;
            scanf("%d", &Elem);
        }
        return *L;
    }
    
    //求单链表表长
    int Length(LinkList L) {
        
        //新建一个移动结点，负责遍历链表，因为有头结点，所以移动结点从头结点的下一个结点算起
        LNode *p = L->next;
        //定义int变量，用于统计链表长度
        int num = 0;
    
        while (p != NULL) {
        
            num++;
            p = p->next;
        }
    
        return num;
    }
    
    //按值查找操作
    //int LocateElem(LinkList L, ElemType Elem) {
        
    //    //定义移动指针，指向头结点的下一个位置
    //    LNode *p = L->next;
    //
    //    //定义当前索引，初始值为1，因为头结点为0
    //    int index = 1;
    //
    //    //如果当前节点数据不为要寻找的那个值，就继续循环
    //    while (p != NULL && p->data != Elem) {
        
    //        index++;
    //        p = p->next;
    //    }
    //    if (p == NULL) {
        
    //        return -1;
    //    }
    //    return index;
    //}
    /*------------------------上面写了个返回位置，其实应该返回结点----------------------------*/
    
    //按值查找操作(返回结点)
    LNode *LocateElem(LinkList L, ElemType Elem) {
        
        LNode *p = L->next;
    
        while (p != NULL && p->data != Elem) {
        
            p = p->next;
        }
    
        return p;
    }
    
    //按位查找操作(返回结点)
    LNode *GetElem(LinkList L, int index) {
        
        LNode *p = L->next;
        if (index > Length(L)) {
        
            printf("索引超出链表长度！\n");
            return NULL;
        }
    
        //为什么要大于1呢，因为0是头结点。
        while (index > 1) {
        
            p = p->next;
            index--;
        }
        return p;
    }
    
    //插入操作
    void ListInsert(LinkList *L, int index, ElemType Elem) {
        
        if (index > Length(*L)) {
        
            printf("索引超出链表长度！\n");
            return;
        }
        //建立临时移动结点
        LNode *p = (*L);
        //建立新节点
        LinkList new;
        InitList(&new);
        new->data = Elem;
        //先找到index位置的上一个节点
        while (index > 1) {
        
            p = p->next;
            index--;
        }
        //把插入位置的上一个节点的下一个节点赋值给新节点
        new->next = p->next;
        p->next = new;
    }
    
    //删除操作
    void ListDelete(LinkList *L, int index) {
        
        if (index > Length(*L)) {
        
            printf("索引超出链表长度！\n");
            return;
        }
    
        //其实前面有索引判断了，这个判空好像没用
        if (Empty(*L)) {
        
            printf("删除失败，链表为空！\n");
            return;
        }
    
        LNode *p = (*L);
        //找到删除位置的上一个节点
        while (index > 1) {
        
            p = p->next;
            index--;
        }
        p->next = p->next->next;
    }
    
    //判空函数
    bool Empty(LinkList L) {
        
        if (L == NULL || L->next == NULL) {
        
            return true;
        }
        return false;
    }
    
    //销毁单链表
    void DestroyList(LinkList *L) {
        
        //定义移动结点
        LNode *p = (*L);
    
        while (p != NULL) {
        
            //定义一个地址信息保存p
            LNode *temp = p;
            p = p->next;
            free(temp);
        }
    
        //将头结点设置为空
        *L = NULL;
    
    }
    
    //打印链表数据
    void PrintList(LinkList L) {
        
        if (Empty(L)) {
        
            printf("链表为空！\n");
            return;
        }
        //新建一个LNode结点结构体p，并将链头结点的后继设置为这个结点的后继
        LNode *p = L->next;
        printf("链表中的元素为：");
        //当下一个结点不为空的时候，一直打印
        while (p != NULL) {
        
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    int main() {
        
        //定义头结点
        LinkList head;
    
        //定义元素值
        ElemType Elem;
    
        //定义索引
        int index;
    
        //头插法建立链表
    //    head = ListInsert_Head(&head);
    
        //尾插法建立链表
        head = ListInsert_Tail(&head);
        //打印链表
        PrintList(head);
    
        //输出链表长度
        printf("链表长度为:%d\n", Length(head));
    
        //查找指定元素值的对应值(搁这搁这呢)
        printf("请输入要查找的元素的值:");
        scanf("%d", &Elem);
        printf("值为%d的元素的值为%d\n", Elem, LocateElem(head, Elem)->data);
    
        //查找指定位置的对应值
        printf("请输入要查找的元素的位置:");
        scanf("%d", &index);
        printf("位置为%d的元素的值为%d\n", index, GetElem(head, index)->data);
    
        //插入元素
        printf("请输入要插入的元素的位置:");
        scanf("%d", &index);
        printf("请输入要插入的元素的值:");
        scanf("%d", &Elem);
        ListInsert(&head, index, Elem);
        printf("插入元素后的链表:\n");
        PrintList(head);
    
        //删除元素
        printf("请输入要删除的元素的位置:");
        scanf("%d", &index);
        ListDelete(&head, index);
        printf("删除元素后的链表:\n");
        PrintList(head);
    
        //销毁链表
        DestroyList(&head);
        printf("销毁后的链表:\n");
        PrintList(head);
    }