结点定义

    typedef struct node
    {
        DataType data;     //每个元素数据信息
        struct node *next; //存放后继元素的地址
    } LNode, *LinkList;

创建空单链表

    LinkList Creat_LinkList(void)
    {
        /*创建空单链表,入口参数:无,返回值:单链表的头指针,0代表创建失败,非0代表创建成功 */
        LinkList H;
        H = (LinkList)malloc(sizeof(LNode)); //申请内存空间
        if (H)                               //确认创建头结点是否成功,成功则修改单链表头结点的指针域为NULL代表空表
            H->next = NULL;
        return H;
    }

销毁单链表

    void Destroy_LinkList(LinkList *H)
    { //将头指针作为参数进行销毁
    /*销毁单链表,入口参数:单链表头指针的地址 */
        LinkList p, q;
        p = *H;
        while (p) //释放单链表的所有结点
        {
            q = p;
            p = p->next;
            free(q);
        }
        *H = NULL;
    }

求表长

    int Length_LinkList(LinkList H)
    {
    /*求单链表表长,入口参数:单链表头指针,出口参数:表长,-1表示单链表不存在 */
        LinkList p = H; //*p指向头结点
        int count = -1; //*H带头节点所以从-1开始
        while (p)       //*p所知的是第count+1个结点
        {
            p = p->next;
            count++;
        }
        return count;
    }

查询操作-按序号查找

    LinkList Locate_LinkList(LinkList H, int i)
    {
    /*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
        LinkList p;
        int j;
        p = H;
        j = 0;
        while (p && j < i) //查找第i个结点
        {
            p = p->next;
            j++;
        }
        if (j != i || !p)
        {
            printf("参数i错误或者单链表不存在\n");
            return NULL;
        } //第i个结点不存在
        return p;
    }

查找操作——按值查找

    LinkList Locate_LinkList_Value(LinkList H, DataType x)
    {
    /*在单链表中查找值为x的结点,入口参数:单链表指针,检索元素 */
    /*出口参数:找到后返回其指针,否则返回:NULL */
        LinkList p = H->next;
        while (p && p->data != x)
        {
            p = p->next;
        }
        return p;
    }

插入操作

    int Insert_LinkList(LinkList H, int i, DataType x)
    {
    /*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
        LinkList p, q;
       p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
        if (!p)
        {
            printf("i有误\n");
            return 0;
        }
        q = (LinkList)malloc(sizeof(LNode));
        if (!q)
        {
            printf("申请空间失败\n"); //申请空间失败,不能插入
            return 0;
        }
       q->data = x;
        q->next = p->next; //新节点插入在第i-1个结点后面
        p->next = q;
        return 1;
    }

删除操作

    int Delete_LinkList(LinkList H, int i)
    {
    /*删除单链表H上的第i个结点,入口参数:单链表,删除元素序号,返回参数:0失败,1成功 */
        LinkList p, q;
        if (H == NULL || H->next == NULL)
        {
            printf("链表不存在或者空表不能删除\n");
            return 0;
        }
        p = Locate_LinkList(H, i - 1); //找到第i-1个结点
        if (p == NULL || p->next == NULL)
        {
            printf("参数i错误\n"); //第i个参数不存在
            return 0;
        }
        q = p->next;       //q指向第i个结点
        p->next = q->next; //从链表中删除
       free(q);           //释放q
       return 1;
    }

单链表的完整代码

    /*
     *  单链表相关操作
     */
    #include "stdio.h"
    typedef char DataType;

    //定义节点
    typedef struct node
    {
        DataType data;     //每个元素数据信息
        struct node *next; //存放后继元素的地址
    } LNode, *LinkList;

    //创建空单链表
    LinkList Creat_LinkList(void)
    {
        /*创建空单链表,入口参数:无,返回值:单链表的头指针,0代表创建失败,非0代表创建成功 */
        LinkList H;
        H = (LinkList)malloc(sizeof(LNode)); //申请内存空间
        if (H)                               //确认创建头结点是否成功,成功则修改单链表头结点的指针域为NULL代表空表
            H->next = NULL;
        return H;
    }

    //销毁单链表
    void Destroy_LinkList(LinkList *H)
    { //将头指针作为参数进行销毁
        /*销毁单链表,入口参数:单链表头指针的地址 */
        LinkList p, q;
        p = *H;
        while (p) //释放单链表的所有结点
        {
           q = p;
           p = p->next;
           free(q);
        }
        *H = NULL;
    }

    //求表长
    int Length_LinkList(LinkList H)
    {
        /*求单链表表长,入口参数:单链表头指针,出口参数:表长,-1表示单链表不存在 */
        LinkList p = H; //*p指向头结点
        int count = -1; //*H带头节点所以从-1开始
       while (p)       //*p所知的是第count+1个结点
        {
            p = p->next;
            count++;
        }
        return count;
    }

    //查找操作——按序号查找
    LinkList Locate_LinkList(LinkList H, int i)
    {
        /*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
        LinkList p;
        int j;
        p = H;
        j = 0;
        while (p && j < i) //查找第i个结点
        {
            p = p->next;
            j++;
        }
        if (j != i || !p)
        {
            printf("参数i错误或者单链表不存在\n");
            return NULL;
        } //第i个结点不存在
        return p;
    }

    //查找操作——按值查找
    LinkList Locate_LinkList_Value(LinkList H, DataType x)
    {
        /*在单链表中查找值为x的结点,入口参数:单链表指针,检索元素 */
        /*出口参数:找到后返回其指针,否则返回:NULL */
        LinkList p = H->next;
        while (p && p->data != x)
        {
            p = p->next;
        }
        return p;
    }

    //插入操作
    int Insert_LinkList(LinkList H, int i, DataType x)
    {
        /*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
        LinkList p, q;
        p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
        if (!p)
        {
            printf("i有误\n");
            return 0;
        }
        q = (LinkList)malloc(sizeof(LNode));
        if (!q)
        {
            printf("申请空间失败\n"); //申请空间失败,不能插入
            return 0;
        }
        q->data = x;
        q->next = p->next; //新节点插入在第i-1个结点后面
        p->next = q;
        return 1;
    }
    
    //删除操作
    int Delete_LinkList(LinkList H, int i)
    {
        /*删除单链表H上的第i个结点,入口参数:单链表,删除元素序号,返回参数:0失败,1成功 */
        LinkList p, q;
        if (H == NULL || H->next == NULL)
        {
            printf("链表不存在或者空表不能删除\n");
            return 0;
        }
        p = Locate_LinkList(H, i - 1); //找到第i-1个结点
        if (p == NULL || p->next == NULL)
        {
            printf("参数i错误\n"); //第i个参数不存在
            return 0;
        }    
        q = p->next;       //q指向第i个结点
        p->next = q->next; //从链表中删除
        free(q);           //释放q
        return 1;
    }

    //主函数
    int main()
    {
        LinkList H;
        int i = 1;
        char x = '0';
        H = Creat_LinkList(); //创建链表
        printf("请问需要插入几个元素:");
        scanf("%d", &i);
        getchar(); //接收回车字符,不可缺
        printf("请输入字符:");
        for (int j = 1; j <= i; j++)
        {
            scanf("%c", &x);          //不能写在函数里面,否则会出错
            getchar();                //接收回车字符,不可缺
            Insert_LinkList(H, j, x); //插入结点数据——如果不确定i的大小而用i++,最后表长会错误(表长大于i的实际值)
        }
        for (int j = 1; j <= i; j++)    //输出所有结点数据
        {
            printf("%c\t", Locate_LinkList(H, j)->data);
        }

        printf("\n请输入您想查询的结点位置:\n"); //位置查找
        scanf("%d", &i);
        printf("结点元素为:%c\n", Locate_LinkList(H, i)->data);
        getchar();                            //接受回车字符
        printf("请输入您想查询的结点的值:"); //值查找
        scanf("%c", &x);
        if (Locate_LinkList_Value(H, x))
        {    
            printf("查询成功\n");
        }
        else
        {
            printf("查询失败\n");
        }
        printf("表长为:%d\n", Length_LinkList(H)); //求表长
        printf("请输入想要删除结点的位置:");
        scanf("%d", &i);
        int m = Delete_LinkList(H, i); //删除结点
        if (m == 1)
            printf("删除成功\n");
        Destroy_LinkList(&H); //销毁链表
        return 0;
    }

应用

这里的应用是用单链表解决约瑟夫问题

首先创建循环单链表

        //定义节点
    typedef struct node
    {
        DataType data;     //每个元素数据信息
        struct node *next; //存放后继元素的地址
    } LNode, *LinkList;

    //创建循环单链表
    LinkList Creat_LinkList(int n)
    {
        LinkList head;
        LinkList p;
        LinkList q;
        p = (LinkList)malloc(sizeof(LNode));
        p->data = 1;
        head = p;
        for(int i=2;i<=n;i++)
        {
            q = (LinkList)malloc(sizeof(LNode));
            q->data = i;
            p->next = q;
            p = q; //p永远指向最后一个节点
        }
        p->next = head;
        return head;
    }

约瑟夫问题的单链表完整代码

        /*
        约瑟夫问题——单链表
    */
    #include "stdio.h"
    typedef int DataType;

    //定义节点
    typedef struct node
    {
        DataType data;     //每个元素数据信息
        struct node *next; //存放后继元素的地址
    } LNode, *LinkList;

    //创建循环单链表
    LinkList Creat_LinkList(int n)
    {
        LinkList head;
        LinkList p;
        LinkList q;
        p = (LinkList)malloc(sizeof(LNode));
        p->data = 1;
        head = p;
        for (int i = 2; i <= n; i++)
        {
            q = (LinkList)malloc(sizeof(LNode));
            q->data = i;
            p->next = q;
            p = q; //p永远指向最后一个节点
        }
        p->next = head;
        return head;
    }

    //查找操作——按序号查找
    LinkList Locate_LinkList(LinkList H, int i)
    {
        /*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
        LinkList p;
        int j;
        p = H;
        j = 0;
        while (p && j < i) //查找第i个结点
        {
            p = p->next;
            j++;
        }
        if (j != i || !p)
        {
            printf("参数i错误或者单链表不存在\n");
            return NULL;
        } //第i个结点不存在
        return p;
    }

    //插入操作
    int Insert_LinkList(LinkList H, int i, DataType x)
    {
        /*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
        LinkList p, q;
        p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
        if (!p)
        {
            printf("i有误\n");
            return 0;
        }
        q = (LinkList)malloc(sizeof(LNode));
        if (!q)
        {
            printf("申请空间失败\n"); //申请空间失败,不能插入
            return 0;
        }
        q->data = x;
        q->next = p->next; //新节点插入在第i-1个结点后面
        p->next = q;
        return 1;
    }

    //约瑟夫问题-链表解决(这里需要循环链表)
    int josephus_LinkList(LinkList josephus_Link, int s, int m)
    {
        /*求约瑟夫问题得出列元素序列,入口参数:已经存放数据的链表头指针,起始位置s,从1报数到m,出口参数:1成功,0表示表中没有元素 */
        LinkList pre, p; //p表示当前结点,pre指向其前驱结点
        int count;
        if (!josephus_Link)
        {
            printf("表中无元素!\n");
            return 0;
        }
        /*找到第i个元素 */
        p = josephus_Link;
        for (count = 1; count < s; count++) //查找第s个结点,用p作为第s个结点的指针
        {
            p = p->next;
        }
        printf("输出约瑟夫序列:\n");
        while (p != p->next) //输出n-1个结点
        {
            pre = p->next;
            while (pre->next != p)
            {
                pre = pre->next; //pre指针初始化,pre是p的前驱指针(单链表,使之让pre成为p的前驱结点)
            }
            for (count = 1; count < m; count++)
            {
                pre = p;
                p = p->next;
            }
            printf("%d\t", p->data);
            pre->next = p->next; //进行删除操作
            free(p);
            p = pre->next;
        }
        printf("%d\t", p->data); //输出最后一个结点
        free(p);
        return 1;
    }

    //主函数
    int main()
    {
        LinkList H;
        LinkList pre;
        int s, m, x;
        int i = 1;
        printf("请问需要插入几个元素:");
        scanf("%d", &i);
        H = Creat_LinkList(i); //创建链表
        pre = H->next;
        while (pre->next != H)
        {
            pre = pre->next; //pre指针初始化,pre是H的前驱指针(单链表,使之让pre成为H的前驱结点)
        }
        for (int j = 1; j <= i; j++) //输出所有结点数据
        {
            printf("%d\t", Locate_LinkList(pre, j)->data); //如使查询顺序正确,第一个数据的结点应该是头结点的前驱结点
        }
        printf("\n请输入起始的序列号s、以及计数值m:\n");
        scanf("%d%d", &s, &m);
        josephus_LinkList(H, s, m);
    }
最后修改:2020 年 03 月 20 日 11 : 49 PM
如果觉得我的文章对你有用,请随意赞赏~