【我的漫漫跨考路】数据结构·队列的链表实现

正文之前

今天看无穷级数这个数学内容实在看得头疼,索性看到八点多就不看了。愉快的写起了码,对我来说这个可有趣了!虽然有时候莫名其妙的就会Run success,有时候也是不知为啥Bug连连,不过好在都能克服,我还是很开心的!写出了链表形式的队列,我去,我总感觉我的队列是乱七八糟的那种,完全按照我自己的想法在写,没有看书上的,后面复习还要规范一下,现在的话,还是先写了再说!书上只要几十行,我的花了整整140,可悲可叹,路漫漫其修远兮~~

正文

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  4
//注:定义队列结构体及其指针
typedef struct Queue
{
    char Data;
    struct Queue *next;

} Queue, *PtrQ;
//注:定义队首队尾的指针以及队列的大小指数
typedef struct {
    PtrQ front;
    PtrQ rear;
    int size;
} *Pointer;

//注:初始化队列函数,申请内存建立一个空表头,成为入口和链表的接口
//注:此处一次性的把六个存储空间全部整合摆好,然后形成了后面的图解中的内存分布形式,一个表头,五个队列内存块
PtrQ InitQueue()
{
    Queue *ptrQ;
    ptrQ=(Queue *)malloc(sizeof(Queue));
    int len=MAXSIZE;
    PtrQ head=ptrQ;
    while(len--)
    {
        //注:采用的是尾插法的链表生成模式
        PtrQ p=(Queue *)malloc(sizeof(Queue));
        p->next=head->next;
        head->next=p;
        head=p;
    }
    head->next=ptrQ->next;
    //注:将初始化后的链表队列传回
    return ptrQ;
}


//注:插入数值函数,先预判需要插入内存是否已经满了
void Putin(PtrQ ptrQ,Pointer queue,char item)
{
    if (queue->size==MAXSIZE)
    {
        printf("\n队列已经满了!!~~\n");
    }
    else
    {
        //注:如果队列未满,分为两种情况,第一次入值和后面的入值
        if (queue->rear==queue->front&&queue->size==0)
        {
            PtrQ L=ptrQ->next;
            //注:此时如果是第一次插入数值,那么头指针也要跟着跑一下!
            printf("\n队列空间刚刚空空如也!~终于等到你!~\n");
            queue->front=L;
            queue->rear=L;
        }
        else
        {
            //注:后面的入值就不需要考虑那么多,因为是循环的链表,所以不存在先后关系,只要向前走已经可以从头到尾,
            PtrQ L=queue->rear;
            queue->rear=L->next;
        }
        queue->rear->Data=item;
        queue->size++;
        printf("\n成功插入!数值是:|\t%c\t|,当前队列内有%d个数!!\n",item,queue->size);
    }

}

//注:抛出数值函数,先预判是否还有数值可以抛出,抛出后头指针向前走1位
char Putout(PtrQ ptrQ,Pointer queue)
{
    if (queue->size==0)
    {
        printf("\n我大清!亡了!!!\n" );
    }
    else
    {
        //注:抛出函数的内容很简单,头指针向后走一位,size-- 然后抛出数值即可
        char out;
        PtrQ L=queue->front;
        out=L->Data;
        queue->front=L->next;
        queue->size--;
        printf("\n抛出后当前只有%d个数\t",queue->size);
        printf("被抛出来的是:| \t%c\t|\n ",out);
        return 0;
    }
    return 0;
}


//注:遍历函数,简单易懂,因为是循环体,所以不存在夏先先后,从头到尾跑一遍,一定是整个队列的输出,只要用size控制输出长度即可
void ShowQueue(PtrQ ptrq,Pointer queue)
{

    PtrQ L=queue->front;
    int X=queue->size;
    while(X--)
    {
        char out;
        out=L->Data;
        L=L->next;
        printf("\n现在整个队列中的情况是:|\t%c  \t |\n",out);
    }
    printf("\n******遍历完成!******\n\n");
}



int main()
{
    //注:初始化整个链表
    Pointer queue;
    PtrQ ptrQ;
    ptrQ=InitQueue();
    queue->front=ptrQ;
    queue->rear=ptrQ;
    queue->size=0;
    //注:为了测试所有函数的性能,先压入四个值,然后全部抛出,再请求抛出,会回复:大清亡了!
    Putin(ptrQ, queue, 'a');
    Putin(ptrQ, queue, 'c');
    Putin(ptrQ, queue, 'd');
    Putin(ptrQ, queue, 'Z');
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    //注:然后再次压入数值,在抛出
    Putin(ptrQ, queue, 'G');
    Putin(ptrQ, queue, 'H');
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putin(ptrQ, queue, 'D');
    //注:最后遍历
    ShowQueue(ptrQ,queue);
    return 0;
}

阿西吧,我对面的小妹妹还没醒过来,九点钟跟我说睡半个小时~然而

运行结果:

队列空间刚刚空空如也!~终于等到你!~

成功插入!数值是:|    a   |,当前队列内有1个数!!

成功插入!数值是:|    c   |,当前队列内有2个数!!

成功插入!数值是:|    d   |,当前队列内有3个数!!

成功插入!数值是:|    Z   |,当前队列内有4个数!!

抛出后当前只有3个数    被抛出来的是:|    a   |

抛出后当前只有2个数    被抛出来的是:|    c   |

抛出后当前只有1个数    被抛出来的是:|    d   |

抛出后当前只有0个数    被抛出来的是:|    Z   |

我大清!亡了!!!

成功插入!数值是:|    G   |,当前队列内有1个数!!

成功插入!数值是:|    H   |,当前队列内有2个数!!

抛出后当前只有1个数    被抛出来的是:|    G   |

抛出后当前只有0个数    被抛出来的是:|    H   |

成功插入!数值是:|    D   |,当前队列内有1个数!!

现在整个队列中的情况是:|    D    |

******遍历完成!******

Program ended with exit code: 0

这是在运行过程中耗费的内存。我屮艸芔茻,怎么这么多!这么小的程序吃了我将近0.5M内存?OMG!!!

我对队列的认识是就仿佛是几个箱子排在一起。然后在连续的几个箱子上,放一些东西。用一个头指针和一个尾指针指向这些装了东西的箱子的头和尾。如果把箱子围成一个圆环,那么也就是今天我写的链表队列实现了。其实链表和线性表实现的不同就在于:线性表相当于是几个摆在一起的箱子,寻找就可以了。而链表就是相当于在一大堆杂乱的箱子中,用绳子把几个要装东西的箱子牵起来。那么在散乱的箱子中也是没有办法精确的直接招到每一个箱子的,所以你就需要顺着绳子去找。这就是链表的意义所在。链表的优势就在于你在,插入或者删除一个箱子的时候,不需要整体的搬动着一个长队伍,而只要重新拿两个绳子,把你要绑的那个箱子串进来就可以了。这极大的,减小了人力的消耗,放在计算机里面就是减少了内存消耗。但是如果要查找,那就很麻烦了。至于具体麻烦在哪里?大家自己想一想,我就不赘述了大家自己想想,我就不赘述了!

如下为图解(并非完全按照上述程序来的,要细看程序可以拷贝程序打断点,或者是看我的运行结果):

初始化,也就是创建队列(此处为创建链表队列,与线性队列的区别在于,存储的内存块非线性)

给定第一个值的过程中,也就是从空队列到含有一个数值的队列转变,此处有别的别的入队出队,因为我给他加了一个front 和 rear同时运动的特例,以便彻底脱离初始化时留下的空指针,使得后面可以不用考虑链表头,只有要用的时候才用!(no.1)

再次给定数值入队(no.2)

继续入队(no.3)

第一次出队(no.-1)

第二次出队(no.-2)

第三次出队(no.-3)

第四次入队(no.4)

正文之后

如果能够把写代码当作一件快乐的事情来对待,是不是说明我有学计算机的潜力呢?当然现在还是这种很简单的代码,所以学得不亦乐乎。以后如果任务加剧的话,保不准我会烦躁,不过也得先走到那一天哪!!今天心情不是特别好,因为学数学觉得自己太菜了。明天继续战斗。现在下楼去洗澡去咯!嘿嘿,小妹子现在还没醒~看我明天怎么臭她。。。ᕕ(ᐛ)ᕗ 如果有大佬路过,觉得看我的代码不顺眼。强迫症犯了,想要帮我精简一下代码或者优化一下算法,那么请不要吝啬你的才华,咱们评论区见!

另外给大家带来一张我觉得非常好看的图!(马丹,原来那张太大了,被微信拦截了。只能换一张啦!)

原文发布于微信公众号 - 工科狗和生物喵(gh_3507b116a1f8)

原文发表时间:2017-08-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏写代码的海盗

分水岭 golang入坑系列

第三式开篇语有些负面, 所以这里就不贴了。有兴趣的自己可以去看看 https://andy-zhangtao.gitbooks.io/golang/conten...

3904
来自专栏cs

python笔记一 入门py

id()函数,是python内置函数,查看每一个对象的地址。 >>> help(id); Help on built-in function id in mod...

3766
来自专栏landv

C语言介绍

4772
来自专栏做全栈攻城狮

电脑小白学习软件开发(八)-复杂数据类型介绍使用,枚举,数组

枚举表示的是:限定只能包括列出来的值。我们这里以星期来举例子。顾名思义,星期只能包括星期一到星期日。用代码来表示下。

1034
来自专栏互联网开发者交流社区

我个人对OOP的理解

1003
来自专栏量子位

干货 | 如何写一个更好的Python函数?

《Writing Idiomatic Python》一书的作者在Medium上发表了一篇文章,给出了6个建议。

972
来自专栏令仔很忙

C#----委托和事件(一)

最近在做的项目,正在进行重构,之前的框架就是纯三层的简单调用,外加一些Session,SQLHelper等封装管理类,其他的东西,一直也想去抽象,但是奈何能力...

7411
来自专栏韩伟的专栏

OO玩法:基于对象

“基于对象”的特点 什么是“基于”对象呢?就是关注“对象之间”的关系,而不是关注对象和类的关系。“面向对象编程”(OOP)的概念已经诞生了很多年,在业界可谓深入...

3394
来自专栏斑斓

编程修炼 | Scala亮瞎Java的眼(二)

继续上一期的话题,介绍Scala有别于Java的特性。说些题外话,当我推荐Scala时,提出质疑最多的往往不是Java程序员,而是负责团队的管理者,尤其是略懂技...

3815
来自专栏Python中文社区

Python如何传递运算表达式

正小歪,Python 工程师,主要负责 Web 开发和日志数据处理。博客文章《真正的 Tornado 异步非阻塞》、《使用 JWT 让你的 RESTful AP...

1161

扫码关注云+社区

领取腾讯云代金券