线性链表的创建，添加数据，销毁，清空，判断是否为空，插入，删除，遍历，搜索数据，链表合并奇数在前偶数在后，链表合并大数在前小数在后----C指针链表

Love The Way You Lie 2022-11-22 00:03 19阅读 0赞

#include <iostream>
    #include"stdio.h"
    #include"stdlib.h"
    
    #define OK 1
    #define ERROR 0
    #define True 1
    #define FALSE 0
    #define infeasible -1//不可实行的
    #define OVERFLOW -2//数据溢出
    
    typedef int ElemType;//便于更改数据类型
    typedef int Status;//用于表示函数状态关系
    
    typedef struct LNode
    {
        ElemType data;
        struct LNode* next;
    }LNode, * LinkList;//单链表
    
    void CreatList(LinkList& L, int n)//创建链表，填充数据，插入到表头
    {
        int i;
        LinkList p;
        L = (LinkList)malloc(sizeof(LNode));//产生头结点，并将L指向此头结点
        L->next = NULL;
        for (i = 0; i < n; i++)//n表示要添加的元素个数
        {
            p = (LinkList)malloc(sizeof(LNode));
            printf("输入一个数据：");
            scanf_s("%d",&(p->data));
            p->next = L->next;//后面的地址赋给p
            L->next = p;//同插入，p地址插入到表头，
        }
    }
    
    Status InitList(LinkList &L)//创建一个空的线性表L
    {
        L = (LinkList)malloc(sizeof(LNode));//产生头结点，并将L指向此头结点
        if (L==NULL)//储存空间分配失败
        {
            exit(OVERFLOW);
        }
        else
        {
            L->next = NULL;//指针域为空
            printf("线性链表创建成功！\n");
            return OK;
        }
    }
    
    Status DestoryList(LinkList& L)//销毁线性列表
    {
        LinkList q;
        while (L != NULL)
        {
            q = L->next;//头结点不断改变，向后移动
            free(L);//前面的头结点所在空间被销毁了，指针像后移动，
            L = q;
        }
        L = NULL;
        printf("线性链表销毁成功！\n");
        return OK;
    }
    
    Status ClearList(LinkList& L)//表L已存在，将表重置为空表，但保留空间
    {
        LinkList p, q;//销毁和清空区别在q的存在，保存了L的地址，头结点始终存在
        p = L->next;
        while (p != NULL)//循环整个链表
        {
            q = p->next;//q不断向前移动，p再跟进
            free(p);
            p = q;
        }
        L->next = NULL;//头结点所指向的一片指针域为空
        printf("线性链表清空成功！\n");
        return OK;
    }
    
    Status ListEmpty(LinkList& L)//判断是否为空表
    {
        if (L->next)
        {
            return ERROR;//是一个非空链表
        }
        else
        {
            return OK;//是一个空链表
        }
    }
    
    int ListLength(LinkList& L)//返回线性表中元素个数
    {
        int i = 0;
        LinkList p = L->next;
        while (p)
        {
            i++;//i=1,计数器
            p = p->next;
        }
        return i;
    }
    
    Status GetElem(LinkList L, int i, ElemType& e)
    //L为带头结点的单链表的头指针，当找到第i个元素时，其值赋给e，并返回OK，没找到返回ERROR
    {
        int j = 1;//j为计数器
        LinkList p = L->next;//p指向第一个结点
        while (p&&j < i) // 顺指针向后查找，直到p指向第i个元素，或没找到第i个元素，此时p为空
        {//没有p不能发现错误，p&&j寻找结点的一种方式
            p = p->next;
            j++;
        }
        if (j > i || !p)//要找的元素大于元素个数，即第i个元素不存在
        {
            return ERROR;
        }
        else
        {
            e = p->data;//取第i个元素的值
            return OK;
        }
    }
    
    int LocatedElem(LinkList L, ElemType e)//找到和e位置相同的点，并返回他的位置
    {
        int i = 0;
        LinkList p = L->next;
        while (p)
        {
            i++;//位置+1，元素不向后移，直接返回i
            if (p->data == e)
            {
                return i;
            }
            p = p->next;
        }
        return ERROR;//没找到元素e
    }
    
    Status ListInsert(LinkList L, int i, ElemType e)
    {//在带头结点单链表L中第I个元素之前插入元素e
        int j = 1;//j为计数器
        LinkList p = L, s;
        while (p && j < i-1) // 顺指针向后查找，直到p指向第i-1个元素，或没找到第i-1个元素，此时p为空
        {//没有p不能发现错误,寻找第i-1个结点
            p = p->next;//P最终指向i-1个元素的地址
            j++;
        }
        if (j > i-1 || !p)//要找的元素大于元素个数，即第i个元素不存在
        {
            return ERROR;//GetElem
        }
        s = (LinkList)malloc(sizeof(LNode));//生成新节点
        s->data = e;//吧要插入的e的值赋给新的结点指针
        s->next = p->next;//i后面元素的地址赋给新节点保存
        p->next = s;//吧新节点的地址赋给i前面的元素的指针
        return OK;
    }
    
    Status ListDelete(LinkList L, int i, ElemType& e)
    {//删除第i个元素的值，并返回被删除元素e的值
        int j = 0;//j为计数器
        LinkList p = L, q;
        while (p->next && j < i-1) // 顺指针向后查找，直到p指向第i个元素，或没找到第i个元素，此时p为空
        {//没有p不能发现错误,寻找第i个结点,使p指向他的前驱,也就是i-1的后继
            p = p->next;
            j++;
        }
        if (j > i - 1 || !p->next)//要找的元素大于元素个数，即第i个元素不存在
        {
            return ERROR;//GetElem
        }
        q = p->next;//删除并释放结点
        p->next = q->next;//指向被删除元素的下个位置的结点
        e = q->data;//返回被删除元素的值
        free(q);
        return OK;
    }
    
    Status ListTraverse(LinkList L)
    {
        LinkList p = L->next;
        while (p != NULL)
        {
            printf("%d  ", p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }
    
    void MergeList(LinkList &L, LinkList Lb, LinkList &Lc)
    {//归并两个线性链表，得到新的单链线性链表，量表中的元素也按照值奇数在前，偶数在后
        LinkList p = L->next;
        LinkList pb = Lb->next;
        LinkList pc=Lc;//指针不能指向空指针域，不能写LC->next
        LinkList Lou,r;
        InitList(Lou);//用于保存偶数地址，创建一个偶数表格用于装两个表中的偶数
        LinkList q = Lou;//指针不能指向空指针域，不能写Lou->next
        while (p)
        {
            if (p->data % 2 == 1)
            {
                pc->next = p;//吧奇数填到pc中
                pc = pc->next;
                if (p->next == NULL)//防止链表的最后一个元素是奇数p->=NULL，出现异常
                {
                    p->next = NULL;
                    break;
                }
                else
                {
                    p = p->next;
                }
            }
            if (p->data % 2 == 0)
            {
                q->next = p;//把偶数装在Lou中保存
                q = q->next;
                if (p->next == NULL)
                {
                    break;
                }
                else
                {
                    p = p->next;
                }
            }
        }
        while(pb)
        {
            if (pb->data % 2 == 1)
            {
                pc->next = pb;
                pc = pc->next;
                if (pb->next == NULL)
                {
                    break;
                }
                else
                {
                    pb = pb->next;
                }
            }
            if (pb->data % 2 == 0)
            {
                q->next = pb;//把偶数装在Lou中保存
                q = q->next;
                if (pb->next == NULL)
                {
                    break;
                }
                else
                {
                    pb = pb->next;
                }
            }
        }
        r = Lou->next;//由于不断插入新元素，Q指针不断后移，将新定义的r重新指向LOU的头结点
        while (r)//插入剩余字段
        {
            pc->next = r;//偶数插入到表格中
            r = r->next;
            pc = pc->next;
        }
            free(Lb);//释放pb空间
            free(Lou);//释放已经无用偶数链表空间
    }
    
    void MergeListCompare(LinkList& L, LinkList Lb, LinkList& Lc)
    {//现有两个链表，他们的值都是按照递增排列，且各不相同，归并两个线性链表，得到新的单链线性链表，量表中的元素也按照值递增排列
        LinkList p = L->next;
        LinkList pb = Lb->next;
        LinkList pc = Lc;//指针不能指向空指针域，不能写LC->next
        while (p && pb)//一个链表插入完成后，；另一个按照顺序插入即可
        {
            if (p->data >= pb->data)
            {
                pc->next = pb;//小数字插入到新链表中，
                pc = pc->next;
                pb = pb->next;
            }
            else
            {
                pc->next = p;//注意插入数据时是逆序插入
                pc = pc->next;
                p = p->next;
            }
        }
        if (pc->next == p)//插入剩余字段，P已经插入完成p=NULL，pc->next=NULL,
        {
            while (pb)
            {
                pc->next = pb;
                pc = pc->next;
                pb = pb->next;
            }
        }
        else
        {
            while (p)
            {
                pc->next = p;
                pc = pc->next;
                p = p->next;
            }
        }
        free(pb);
    }
    
    
    int main()
    {
        LinkList L,Lb,Lc;
        int n,i;
        ElemType e1, e2, e3, e4, e5, e6, e7 ,e8;
        InitList(L);
        printf("请输入需要添加的单向链表元素个数：");
        scanf_s("%d", &n);
        CreatList(L, n);
        ListTraverse(L);
        e1 = ListEmpty(L);
        if (e1 == ERROR)
        {
            printf("此链表是一个非空链表！\n");
        }
        else
        {
            printf("此链表是一个空链表！\n");
        }
        e2 = ListLength(L);
        printf("此链表的长度是：%d\n", e2);
        printf("请输入想要查询的元素的位置："); 
        scanf_s("%d", &i);
        e4=GetElem(L, i, e3);
        if (e4 == OK) 
        {
            printf("第%d个元素的值为%d.\n", i, e3);
        }
        if(e4==ERROR)
        {
            printf("查询错误！您想要查询的元素位置可能大于链表元素个数\n");
        }
        printf("请输入您想要查询位置的元素的值：");
        scanf_s("%d", &e6);
        e5 = LocatedElem(L, e6);
        if (e5 == ERROR)
        {
            printf("线性链表中不存在这个元素！\n");
        }
        else
        {
            printf("元素%d的位置是%d.\n", e6, e5);
        }
        printf("请输入想要插入的元素的位置：");
        scanf_s("%d", &i);
        printf("请输入想要插入的元素的值：");
        scanf_s("%d", &e7);
        ListInsert(L, i, e7);
        ListTraverse(L);
        printf("请输入想要删除的元素的位置：");
        scanf_s("%d", &i);
        ListDelete(L, i, e8);
        printf("第%d的元素是%d,现在已被删除。\n", i, e8);
        ListTraverse(L);
        printf("现在要执行操作：归并两个线性链表，得到新的单链线性链表，两表中的元素也按数值奇数在前，偶数在后\n");
        InitList(Lb);
        InitList(Lc);
        printf("请输入需要添加的单向链表元素个数：");
        scanf_s("%d", &n);
        CreatList(Lb, n);
        ListTraverse(Lb);
        MergeList(L, Lb, Lc);
        printf("合并后的新链表是：\n");
        ListTraverse(Lc);
        printf("现在要执行操作:现有两个链表，他们的值都是按照递增排列，且各不相同，归并两个线性链表，得到新的单链线性链表，量表中的元素也按照值递增排列\n");
        InitList(Lb);
        InitList(Lc);
        printf("请输入需要添加的单向链表元素个数：");
        scanf_s("%d", &n);
        CreatList(Lb, n);
        ListTraverse(Lb);
        MergeListCompare(L, Lb, Lc);
        printf("合并后的新链表是：\n");
        ListTraverse(Lc);
        ClearList(L);
        e1 = ListEmpty(L);
        if (e1 == ERROR)
        {
            printf("此链表是一个非空链表！\n");
        }
        else
        {
            printf("此链表是一个空链表！\n");
        }
        DestoryList(L);