AI 助理
备案控制台
开发者社区 云计算 文章 正文

苏嵌实训——day9（下）

2023-01-29 177
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 苏嵌实训——day9（下）

1.2.12 直接插入排序


//直接插入排序
void LinkListInsertSort(linklist *head,DataType value)
{
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    linklist *p = head;
    while(p->next != NULL && p->next->data < tmp->data)
    {
        p = p->next;
    }
    tmp->next = p->next;
    p->next = tmp;
}


练习：实现单链表的反转

h1: 10->20->30->40->NULL

…

h2:40->30->20->10->NULL


//单链表翻转
void LinkListReverse(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("链表为空，无需翻转！\n");
        return;
    }
    linklist *h1 = LinkListCreate();
    linklist *p = head;
    DataType value;
    while(p->next != NULL)
    {
        value = LinkListDeleteHead(head);
        LinkListInsertHead(h1,value);
    }
    head->next= h1->next;
}


//单链表翻转2
void LinkListReverse2(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("链表为空，无需翻转！\n");
        return;
    }
    //定义两个指针变量来执行链表的翻转
    linklist *p = NULL, *q = NULL;
    //p指针保存第一个结点的地址
    p = head->next;
    //头结点指向NULL
    head->next = NULL;
    while(p != NULL)
    {
        //q指针保存p指向的结点的地址
        q = p;
        p = p->next;
        //头插法将q插入到head链表中
        q->next = head->next;
        head->next = q;
    }
}


练习:单链表的整表删除


//单链表的整表删除
void LinkListClear(linklist *head)
{
    linklist *p = NULL,*q = NULL;
    p = head->next;
    while(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    head->next = NULL;
}


1.3 整体代码


1.3.1 linklist.h


//头文件
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int DataType;
//定义结点结构体
typedef struct linklist
{
    DataType data; //数据域
    struct linklist *next; //指针域，为了能够操作后面结点
                            //所以指针的类型为当前结构体的类型
}linklist;
//创建一个空的单链表
linklist* LinkListCreate();
//头插法插入数据
void LinkListInsertHead(linklist *head,DataType value);
//遍历单链表
void LinkListPrint(linklist *head);
//尾插法插入数据
void LinkListInsertTail(linklist *head,DataType value);
//判断单链表是否为空
int LinkListIsEmpty(linklist *head);
//头删法，返回删除的数据
DataType LinkListDeleteHead(linklist *head);
//按照数据修改数据
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue);
//按照位置查找数据
DataType LinklistSearchData(linklist *head,int pos);
//按照数据查找位置
int LinkListSearchPos(linklist *head,DataType value);
//按照位置插入数据
void LinkListInsertByPos(linklist *head,int pos,DataType value);
//直接插入排序
void LinkListInsertSort(linklist *head,DataType value);
//单链表翻转
void LinkListReverse(linklist *head);
//单链表翻转2
void LinkListReverse2(linklist *head);
//单链表的整表删除
void LinkListClear(linklist *head);
#endif


1.3.2 linklist.c


//功能函数
#include "linklist.h"
//创建一个空的单链表
linklist* LinkListCreate()
{
    //定义一个头结点，在堆区开辟空间
    linklist *head = (linklist *)malloc(sizeof(linklist));
    //初始化指针域标识为空
    head->next = NULL;
    return head;
}
//头插法插入数据
void LinkListInsertHead(linklist *head,DataType value)
{
    //开辟空间，分配一个新的结点
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    //将要插入的结点的指针域指向第一个结点
    //第一个结点的地址：head->next
    //新插入结点的指针域：tmp->next
    tmp->next = head->next;
    //头结点的指针域保存要插入的结点的地址
    //头结点的指针域：head->next
    //新插入结点的地址：tmp
    head->next = tmp;
    return;
}
//遍历单链表
void LinkListPrint(linklist *head)
{
    //定义一个指针保存第一个结点的地址
    linklist *p = head->next;
    while(p != NULL)
    {
        //打印数据
        printf("%d ",p->data);
        //p指向下一个结点（p保存下一个结点的地址）
        p = p->next;
    }
    putchar(10);
}
//尾插法插入数据
void LinkListInsertTail(linklist *head,DataType value)
{
    //申请空间，分配结点结构体
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    //找到最后一个结点
    linklist *p = head;
    while(p->next != NULL)
    {
        p = p->next;
    }
    //将新插入的结点保存在最后一个结点的后面
    p->next = tmp;
    //将新插入的结点的指针域指向NULL
    tmp->next = NULL;
    return;
}
//判断单链表是否为空
int LinkListIsEmpty(linklist *head)
{
    return head->next == NULL ? 1 : 0;
}
//头删法，返回删除的数据
DataType LinkListDeleteHead(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("删除失败，单链表为空！\n");
        return (DataType)-1;
    }
    DataType value = head->next->data;
    linklist *tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    tmp = NULL;
    return value;
}
//按照数据修改数据
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue)
{
    if(LinkListIsEmpty(head))
    {
        printf("修改数据失败，链表为空");
        return;
    }
    linklist *p = head;
    int flags = 0;
    while(p->next != NULL)
    {
        p = p->next;
        if(p->data == OldValue)
        {
            p->data = NewValue;
            flags = 1;
        }
    }
    if(flags == 0)
    {
        printf("数据%d不存在，修改失败\n",OldValue);
    }
    return;
}
//按照位置查找数据
DataType LinklistSearchData(linklist *head,int pos)
{
    if(LinkListIsEmpty(head))
    {
        printf("查找失败，链表为空！\n");
    }
    if(pos < 1)
    {
        printf("位置有误！\n");
    }
    linklist *p = head;
    int i;
    for(i = 1; i <= pos;i++)
    {
        if(p == NULL)
        {
            printf("输入位置有误！\n");
            return (DataType)-1;
        }
        p = p->next;
    }
    return p->data;
}
//按照数据查找位置
int LinkListSearchPos(linklist *head,DataType value)
{
    if(LinkListIsEmpty(head))
    {
        printf("查找位置失败，链表为空！\n");
        return (DataType)-1;
    }
    linklist *p = head;
    int pos = 0;
    while(p->next != NULL)
    {
        p = p->next;
        pos++;
        if(p->data == value)
        {
            return pos;
        }
    }
    printf("查找位置失败！\n");
    return (DataType)-1;
}
//按照位置插入数据
void LinkListInsertByPos(linklist *head,int pos,DataType value)
{
    if(pos < 1)
    {
        printf("按照位置插入数据有误");
        return;
    }
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    if(LinkListIsEmpty(head))
    {
        tmp->next = head->next;
        head->next = tmp;
    }
    else
    {
        int i;
        linklist *p = head;
        for(i = 0 ; i < pos ;i++)
        {
            if(p->next == NULL)
            {
                printf("位置有误！\n");
                return;
            }
            p = p->next;
        }
        tmp->next = p->next;
        p->next = tmp;
    }
}
//直接插入排序
void LinkListInsertSort(linklist *head,DataType value)
{
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    linklist *p = head;
    while(p->next != NULL && p->next->data < tmp->data)
    {
        p = p->next;
    }
    tmp->next = p->next;
    p->next = tmp;
}
//单链表翻转
void LinkListReverse(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("链表为空，无需翻转！\n");
        return;
    }
    linklist *h1 = LinkListCreate();
    linklist *p = head;
    DataType value;
    while(p->next != NULL)
    {
        value = LinkListDeleteHead(head);
        LinkListInsertHead(h1,value);
    }
    head->next= h1->next;
}
//单链表翻转2
void LinkListReverse2(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("链表为空，无需翻转！\n");
        return;
    }
    //定义两个指针变量来执行链表的翻转
    linklist *p = NULL, *q = NULL;
    //p指针保存第一个结点的地址
    p = head->next;
    //头结点指向NULL
    head->next = NULL;
    while(p != NULL)
    {
        //q指针保存p指向的结点的地址
        q = p;
        p = p->next;
        //头插法将q插入到head链表中
        q->next = head->next;
        head->next = q;
    }
}
//单链表的整表删除
void LinkListClear(linklist *head)
{
    linklist *p = NULL,*q = NULL;
    p = head->next;
    while(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    head->next = NULL;
}


1.3.3 main.c


//main.c
#include "linklist.h"
int main(int argc, char const *argv[])
{
    linklist *head = LinkListCreate();
    int i;
    for(i= 0 ; i < 10;i++)
    {
        LinkListInsertHead(head,i + 1);
    }
    LinkListPrint(head);
    for(; i < 20;i++)
    {
        LinkListInsertTail(head,i + 1);
    }
    LinkListPrint(head);
    for(i = 0 ; i < 5;i++)
    {
        LinkListDeleteHead(head);
    }
    LinkListPrint(head);
    LinkListUpdate(head,11,999);
    LinkListPrint(head);
    printf("位置4的数据为%d\n",LinklistSearchData(head,4));
    printf("数据为999的位置为%d\n",LinkListSearchPos(head,9999));
    LinkListInsertByPos(head,3,777);
    LinkListPrint(head);
    LinkListInsertSort(head,9);
    LinkListInsertSort(head,188);
    LinkListInsertSort(head,12);
    LinkListInsertSort(head,0);
    LinkListInsertSort(head,6);
    LinkListPrint(head);
    LinkListReverse(head);
    LinkListPrint(head);
    LinkListReverse2(head);
    LinkListPrint(head);
    LinkListClear(head);
    LinkListInsertSort(head,9);
    LinkListInsertSort(head,188);
    LinkListInsertSort(head,12);
    LinkListInsertSort(head,0);
    LinkListInsertSort(head,6);
    LinkListPrint(head);
    return 0;
}


二 单向循环链表

2.1 概念


0a2653c851af460fa595bd959398a8f1.png

2.2 单向循环链表的操作


定义结点结构体

创建一个空的单向循环链表

插入数据

打印数据

删除头结点

打印数据


2.2.1 定义结点结构体


//定义数据类型
typedef int DataType;
//定义结点结构体
typedef struct looplist
{
    DataType data;
    struct looplist *next;
}looplist;


2.2.2 创建空的单向循环链表


//创建一个空的单向循环链表
looplist* LoopListCreate()
{
    looplist *head = (looplist *)malloc(sizeof(looplist));
    //初始状态就为循环
    //头结点的指针域保存头结点的地址
    head->next = head;
    return head;
}


2.2.3 插入数据


//插入数据
void LoopListInsert(looplist *head,DataType value)
{
    looplist *tmp = (looplist *)malloc(sizeof(looplist));
    tmp->next = NULL;
    tmp->data = value;
    tmp->next = head->next;
    head->next = tmp;
    return;
}


2.2.4 遍历单向循环链表


//遍历单向循环链表
void LoopListPrint(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        p = p->next;
        printf("%d ",p->data);
    }
    putchar(10);
}


2.2.5 删除头结点


//删除头结点
looplist* LoopListCutHead(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        p = p->next;
    }
    p->next = head->next;
    free(head);
    head = NULL;
    return p->next;
}


2.2.6 去头结点遍历


//去头结点遍历单向循环链表
void LoopListPrint2(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("%d\n",p->data);
}


2.3 作业 joseph问题


设编号分别为：1，2…n个人围成一圈，约定序号为k（1 <=k<=n）的人从头开始计数，数到m的人出列，他的下一位又从1开始计数，数到m的人又出列，依次类推，直到所有人出列为止

例如：n = 8,k = 3,m = 4


void Joseph(int n,int k,int m)
{
    if(n < k || n < m)
    {
        printf("k或者M输入有误！,k = %d,m = %d\n",k,m);
        return;
    }
    //创建一个空的单向循环链表
    looplist *h1 = LoopListCreate();
    int i;
    for(i = n ; i >=1;i--)
    {
        LoopListInsert(h1,i);
    }
    h1 = LoopListCutHead(h1);
    LoopListPrint2(h1);
    //找到编号为k的人
    for(i = 1; i < k;i++)
    {
        h1 = h1->next;
    }
    //循环删除数到m的那个结点
    looplist *tmp = NULL;
    while(h1->next != h1)
    {
        //为了删除指定的结点，所以h1指针保存数到m-1的结点
        for(i = 1; i < m-1;i++)
        {
            h1 = h1->next;
        }
        //删除h1后面的结点
        tmp = h1->next;
        h1->next = tmp->next;
        printf("%d ",tmp->data);
        free(tmp);
        tmp = NULL;
        //从下一个结点开始数数
        h1 = h1->next;
    }
    printf("%d\n",h1->data);
    free(h1);
    h1 = NULL;
    return;
}


2.4 完整代码


2.4.1 looplist.h


#ifndef _LOOPLIST_H_
#define _LOOPLIST_H_
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int DataType;
//定义结点结构体
typedef struct looplist
{
    DataType data;
    struct looplist *next;
}looplist;
//创建一个空的单向循环链表
looplist* LoopListCreate();
//插入数据
void LoopListInsert(looplist *head,DataType value);
//遍历单链表
void LoopListPrint(looplist *head);
//删除头结点
looplist* LoopListCutHead(looplist *head);
//去头结点遍历单向循环链表
void LoopListPrint2(looplist *head);
#endif


2.4.2 main.c


//main.c
#include "looplist.h"
int main(int argc, char const *argv[])
{
    looplist *head = LoopListCreate();
    int i;
    for(i = 0 ; i < 10;i++)
    {
        LoopListInsert(head,i + 1);
    }
    LoopListPrint(head);
    head = LoopListCutHead(head);
    LoopListPrint2(head);
    return 0;
}


2.4.3 looplist.c


//looplist.c
#include "looplist.h"
//创建一个空的单向循环链表
looplist* LoopListCreate()
{
    looplist *head = (looplist *)malloc(sizeof(looplist));
    //初始状态就为循环
    //头结点的指针域保存头结点的地址
    head->next = head;
    return head;
}
//插入数据
void LoopListInsert(looplist *head,DataType value)
{
    looplist *tmp = (looplist *)malloc(sizeof(looplist));
    tmp->next = NULL;
    tmp->data = value;
    tmp->next = head->next;
    head->next = tmp;
    return;
}
//遍历单向循环链表
void LoopListPrint(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        p = p->next;
        printf("%d ",p->data);
    }
    putchar(10);
}
//删除头结点
looplist* LoopListCutHead(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        p = p->next;
    }
    p->next = head->next;
    free(head);
    head = NULL;
    return p->next;
}
//去头结点遍历单向循环链表
void LoopListPrint2(looplist *head)
{
    looplist *p = head;
    while(p->next != head)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("%d\n",p->data);
}
周末不下雨
目录
相关文章
让线程再跑一会
|
存储 分布式计算 IDE
Flink（十一）【状态管理】（4）
Flink（十一）【状态管理】
让线程再跑一会
203 1
dulu~dulu
|
安全 网络协议 网络虚拟化
网工记背配置基础命令总结（4）---DHCP配置
网工记背配置基础命令总结（4）---DHCP配置
dulu~dulu
940 0
smile.初夏
|
Java 关系型数据库 MySQL
浪漫编码：手把手教你实现校园表白墙功能
浪漫编码：手把手教你实现校园表白墙功能
smile.初夏
253 0
Love-Java.
|
JavaScript 应用服务中间件 Linux
【Linux】部署单机OA项目及搭建spa前后端分离项目
【Linux】部署单机OA项目及搭建spa前后端分离项目
Love-Java.
198 0
【Linux】部署单机OA项目及搭建spa前后端分离项目
Hcoco_me
|
Linux 编译器 Go
Linux内核学习（四）：Bootloader的特种兵-Uboot（二）
Linux内核学习（四）：Bootloader的特种兵-Uboot（二）
Hcoco_me
903 0
三分钟热度的鱼
|
SQL 消息中间件 关系型数据库
Flink报错问题之cdc任务报错如何解决
Apache Flink是由Apache软件基金会开发的开源流处理框架，其核心是用Java和Scala编写的分布式流数据流引擎。本合集提供有关Apache Flink相关技术、使用技巧和最佳实践的资源。
三分钟热度的鱼
357 0
玉面大蛟龙
|
消息中间件 存储 NoSQL
RabbitMQ学习（九）：延迟队列
延时队列中，队列内部是有序的，最重要的特性就体现在它的延时属性上，延时队列中的元素是希望 在指定时间到了以后或之前取出和处理。简单来说，延时队列就是用来存放需要在指定时间内被处理的 元素的队列。 其实延迟队列就是死信队列的一种。
玉面大蛟龙
494 0
RabbitMQ学习（九）：延迟队列
IT从业者张某某
|
数据采集
指标体系构建-02-从0开始，梳理数据指标体系
指标体系构建-02-从0开始，梳理数据指标体系
IT从业者张某某
366 0
赵广陆
|
SQL 存储 关系型数据库
大数据Hive拉链表的设计与实现
大数据Hive拉链表的设计与实现
赵广陆
515 2
开发者小助理
|
人工智能 Serverless 云栖大会
云栖大会划重点！重大发布持续更新中
云栖大会三日，有哪些重磅发布？开发者精选持续更新中
开发者小助理
1886 2

热门文章

最新文章

  • 1
    上云就上阿里云背后：云计算已成为新旧动能转换关键
  • 2
    Data truncation: Out of range value
  • 3
    本地缓存之王，Caffeine保姆级教程
  • 4
    元数据驱动的 SaaS 架构与背后的技术思考
  • 5
    【云栖大会】阿里云首席架构师唐洪：飞天，互联网规模的操作系统
  • 6
    Navicat premium16注册机永久破解激活（附安装包和注册机文件）
  • 7
    58快狗打车基于Hologres的实时离线统一数据服务
  • 8
    阿里云率先达成国家绿色数据中心标准，平均PUE低于1.3
  • 9
    gitlab的使用方法
  • 10
    读书笔记《集体智慧编程》Chapter 10 : Finding Independent Features
  • 1
    为什么实时更新场景下 Doris 查询性能是 ClickHouse 的 34 倍
    50
  • 2
    蜜蜂数据的采集与处理方法-蜜蜂目标检测数据集（7000张图片已标注划分）
    26
  • 3
    Apache Doris 登顶 RTABench —— 实时分析领域的性能王者
    37
  • 4
    教育行业如何做GEO？让AI成为你的课程推荐官
    45
  • 5
    Apache Doris 是如何保障系统稳定性的？
    37
  • 6
    《游戏Bug快修手册：根因锁定与最小改动的技术实践》
    35
  • 7
    《从被动修复到免疫：游戏Bug闭环体系的深度搭建指南》
    31
  • 8
    Doris MCP Server 0.5.1 版本发布
    45
  • 9
    ZTree基本使用及本人详解 内容1
    24
  • 10
    LEANN：一个极简的本地向量数据库
    31

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    让AI单次生成4万字！WriteHERE：开源AI长文写作框架，单次生成超长文本，小说报告一键搞定！