单链表的实现

矫情吗；* 2022-03-27 05:18 250阅读 0赞

学习编程也有一段时间了，但是总是感觉，自己缺少一些什么东西。编程一味的学习照着别人写的习惯，没有自己的思想，是不能有质的提升的。总是感觉自己不能做什么，对待代码还是缺少基本的实现的能力，更不用说什么技巧算法了。还需要的大量的联系。

我打算好好把数据结构的算法，实现以下，总是感觉自己，看起来会了，但是实际动手机就写不出来了。

自己只有不断的总结，把该记住的东西理解了，才能得心应手。。。。

公共的头文件：\#include "common.h"

#include<string.h>
    #include<ctype.h>
    #include<malloc.h> /* malloc()等 */
    #include<limits.h> /* INT_MAX等 */
    #include<stdio.h> /* EOF(=^Z或F6),NULL */
    #include<stdlib.h> /* atoi() */
    #include<io.h> /* eof() */
    #include<math.h> /* floor(),ceil(),abs() */
    #include<process.h> /* exit() */
    /* 函数结果状态代码 */
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1  //infeasible
    /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
    typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

\#include "SingleList.h"

#pragma once
    #include "common.h"
    
    typedef int ElemType;
    
    //线性表的单链表存储结构
    struct LNode
    {
        ElemType data;
        LNode* next;
    };
    typedef struct LNode* LinkList;
    
    
    class SingleList
    {
    public:
        SingleList();
        ~SingleList();
    public:
        //基本操作12个
        Status InitList(LinkList*);
        Status DestroyList(LinkList*);
        Status ClearList(LinkList);
        Status ListEmpty(LinkList);
        Status ListLength(LinkList);
        Status GetElem(LinkList, int i, ElemType* e);
        Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType));
        Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e);
        Status NextElem(LinkList L, ElemType cur_e,ElemType* next_e);
        Status ListInsert(LinkList L,int i,ElemType e);
        Status ListDelete(LinkList L,int i,ElemType* e);
        Status ListTraverse(LinkList L,void(*vi)(ElemType));
    };

"SingleList.cpp"

#include "SingleList.h"
    
    
    SingleList::SingleList()
    {
    }
    
    
    SingleList::~SingleList()
    {
    }
    
    Status SingleList::InitList(LinkList* L)
    {
        /*操作结果：构造一个空的线性表L*/
        *L = (LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向次头结点
        if (!*L)
        {
            exit(OVERFLOW);
        }
        (*L)->next = nullptr;//指针域空
        return OK;
    }
    
    Status SingleList::DestroyList(LinkList*L)
    {
        /*初始条件：线性表L已经存在。操作结果：销毁线性表*/
        LinkList q;
        while (*L)
        {
            q = (*L)->next;
            free(*L);
            *L = q;
        }
        return OK;
    }
    
    Status SingleList::ClearList(LinkList L) /*不改变L*/
    {
        /*初始条件：线性表L已经存在。操作结果：将L置为空表*/
        LinkList p, q;
        p = L->next;/*p指向第一个结点*/
        while (p)   
        {
            q = p->next;  //先记录下一结点，然后释放当前结点
            free(p);
            p = q;
        }
        L->next = nullptr;  /*头结点指针域为空*/
        return OK;
    }
    
    Status SingleList::ListEmpty(LinkList L)
    {
        if (L->next==nullptr)
        {
            return OK;
        }
        else
        {
            return ERROR;
        }
    }
    
    Status SingleList::ListLength(LinkList L)
    {
        int length=0;
        LinkList q=L->next;
        while (q)
        {
            length++;
            q = q->next;
        }
        return length;
    }
    
    Status SingleList::GetElem(LinkList L, int i, ElemType* e)
    {
        /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
        LinkList q;
        q = L->next;
        int j = 1; /* j为计数器 */
        while (q&&j<i)  /* 顺指针向后查找,直到p指向第i个元素或p为空 */
        {
            j++;
            q = q->next;
        }
        if (!q || j>i)  /*第i个元素不存在*/
        {
            return ERROR;
        }
        *e = q->data;   /*取第i个元素*/
        return OK;
    }
    
    int SingleList::LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))
    { /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */
        /* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
        /*           若这样的数据元素不存在,则返回值为0 */
        int i = 0;
        LinkList p = L->next;
        while (p)
        {
            i++;
            if (compare(p->data, e)) /* 找到这样的数据元素 */
                return i;
            p = p->next;
        }
        return 0;
    }
    
    Status SingleList::PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e)
    { /* 初始条件: 线性表L已存在 */
        /* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
        /*           返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
        LinkList q, p = L->next; /* p指向第一个结点 */
        while (p->next) /* p所指结点有后继 */
        {
            q = p->next; /* q为p的后继 */
            if (q->data == cur_e)
            {
                *pre_e = p->data;
                return OK;
            }
            p = q; /* p向后移 */
        }
        return INFEASIBLE;
    }
    
    Status SingleList::NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
    { /* 初始条件：线性表L已存在 */
        /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
        /*           返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */
        LinkList p = L->next; /* p指向第一个结点 */
        while (p->next) /* p所指结点有后继 */
        {
            if (p->data == cur_e)
            {
                *next_e = p->next->data;
                return OK;
            }
            p = p->next;
        }
        return INFEASIBLE;
    }
    
    Status SingleList::ListInsert(LinkList L, int i, ElemType e) /* 算法2.9。不改变L */
    { /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
        int j = 0;
        LinkList p = L, s;
        while (p&&j<i - 1) /* 寻找第i-1个结点 */
        {
            p = p->next;
            j++;
        }
        if (!p || j>i - 1) /* i小于1或者大于表长 */
            return ERROR;
        s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
        s->data = e; /* 插入L中 */
        s->next = p->next;
        p->next = s;
        return OK;
    }
    
    Status SingleList::ListDelete(LinkList L, int i, ElemType *e) /* 算法2.10。不改变L */
    { /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */
        int j = 0;
        LinkList p = L, q;
        while (p->next&&j<i - 1) /* 寻找第i个结点,并令p指向其前趋 */
        {
            p = p->next;
            j++;
        }
        if (!p->next || j>i - 1) /* 删除位置不合理 */
            return ERROR;
        q = p->next; /* 删除并释放结点 */
        p->next = q->next;
        *e = q->data;
        free(q);
        return OK;
    }
    
    Status SingleList::ListTraverse(LinkList L, void(*vi)(ElemType))
    /* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */
    { /* 初始条件：线性表L已存在 */
        /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
        LinkList p = L->next;
        while (p)
        {
            vi(p->data);
            p = p->next;
        }
        printf("\n");
        return OK;
    }

测试main()

#include "common.h"
    #include "SingleList.h"
    
    
    Status comp(ElemType c1, ElemType c2)
    {
        //数据元素判定函数（相等为True,否则为FALSE）
        if (c1 == c2)
        {
            return TRUE;
        }
        else
            return FALSE;
    }
    void visit(ElemType c)
    {
        printf("%d", c);
    }
    
    int main()
    {
        LinkList L;
        ElemType e, e0;
        Status i;
        int  k;
        SingleList s;
        i = s.InitList(&L);
        for (int j = 1; j <= 5;j++)
        {
            i = s.ListInsert(L, 1, j);
        }
        printf("在L的表头依次插入1~5后：L=");
        s.ListTraverse(L, visit);
        i = s.ListEmpty(L);
        printf("L是否空：i=%d(1:是 0：否)\n", i);
        for (int j = 1; j <= 10;j++)
        {
            s.ListInsert(L,j+5,j);
        }
        printf("在L的表尾依次插入1~10后：L=");
        s.ListTraverse(L,visit);
        s.GetElem(L,5,&e);
        printf("第5个元素的值为：%d\n", e);
        for (int j = 0; j <= 1; j++)
        {
            k = s.LocateElem(L, j, comp);
            if (k)
                printf("第%d个元素的值为%d\n", k, j);
            else
                printf("没有值为%d的元素\n", j);
        }
        for (int j = 1; j <= 2; j++) /* 测试头两个数据 */
        {
            s.GetElem(L, j, &e0); /* 把第j个数据赋给e0 */
            i = s.PriorElem(L, e0, &e); /* 求e0的前驱 */
            if (i == INFEASIBLE)
                printf("元素%d无前驱\n", e0);
            else
                printf("元素%d的前驱为：%d\n", e0, e);
        }
        for (int j = s.ListLength(L) - 1; j <= s.ListLength(L); j++)/*最后两个数据 */
        {
            s.GetElem(L, j, &e0); /* 把第j个数据赋给e0 */
            i = s.NextElem(L, e0, &e); /* 求e0的后继 */
            if (i == INFEASIBLE)
                printf("元素%d无后继\n", e0);
            else
                printf("元素%d的后继为：%d\n", e0, e);
        }
        k = s.ListLength(L); /* k为表长 */
        for (int j = k + 1; j >= k; j--)
        {
            i = s.ListDelete(L, j, &e); /* 删除第j个数据 */
            if (i == ERROR)
                printf("删除第%d个数据失败\n", j);
            else
                printf("删除的元素为：%d\n", e);
        }
        printf("依次输出L的元素：");
        s.ListTraverse(L, visit);
        s.DestroyList(&L);
        printf("销毁L后：L=%u\n", L);
    
        return 0;
    }