链队写杨辉三角(再附一个数组的)

杨辉三角

链队写杨辉三角,其主要思想就是先用链队保存杨辉三角的第一层,再通过前一项加后一项算出下一层的元素,故每次算完一层,链队就保存这层的数据。

举例

第一步: 1 0; 1+0=1,输出1,换行,结果1 替换 结点中的1
第二步: 1 0; 在链队最前面插入一个值为0的结点形成0 1 0;
第三步:0 1 0; 这里便储存了第一层杨辉三角的值,然后重复一二步操作;
以下不再说明步骤,直接写出每步链队信息;
由0 1 0开始,接着
1 1 0
1 1 0
0 1 1 0
第二层输出完毕;
1 1 1 0
1 2 1 0
1 2 1 0
0 1 2 1 0
第三层输出完毕;

链队代码

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define true 1
#define false 0

typedef int QElemType;

typedef struct QNode
{
    QElemType date;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
    QueuePtr front; //队头指针
    QueuePtr rear;  //队尾指针
} LinkQueue;

int InitQueue(LinkQueue *Q);
void InitYangHuiTriangle(LinkQueue *Q);
int EnQueueRear(LinkQueue *Q, QElemType e);
int EnQueueFront(LinkQueue *Q, QElemType e);
int Dequeue(LinkQueue *Q, QElemType *e);
QElemType GetHead(LinkQueue *Q);
void OutputYangHuiTriangle(LinkQueue *Q, int layer);
int TraverseQueue(LinkQueue *Q);
int DestroyQueue(LinkQueue *Q);

int main()
{
    LinkQueue *q = (LinkQueue *)malloc(sizeof(LinkQueue));
    InitYangHuiTriangle(q);
    
    int layer=0;
    printf("请输入杨辉三角的层数:");
    scanf("%d",&layer);

    OutputYangHuiTriangle(q, layer);

    DestroyQueue(q);
    return 0;
}

void InitYangHuiTriangle(LinkQueue *Q)
{
    InitQueue(Q);
    EnQueueRear(Q, 1);
    EnQueueRear(Q, 0);
}

void OutputYangHuiTriangle(LinkQueue *Q, int layer)
{
    for (int i = 0; i < layer; i++)
    {
        QueuePtr f = Q->front;
        f = f->next;
        while (f != Q->rear)
        {
            int date = f->date + f->next->date;
            printf("%-4d ", date);
            f->date = date;
            f = f->next;
        }
        putchar(10);
        //TraverseQueue(Q);
        EnQueueFront(Q, 0);
    }
}

int InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front)
    {
        printf("构造空队列失败,系统内存不足!\n");
        return false;
    }
    Q->front->next = NULL;
    return true;
}

//增加队尾结点
int EnQueueRear(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->date = e;
    p->next = NULL;
    Q->rear->next = p; //相当于Q->rear->next=p,rear和front指向同一区域
    Q->rear = p;
    return true;
}

//增加队头结点
int EnQueueFront(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->date = e;
    p->next = Q->front->next;
    Q->front->next = p;
    return true;
}

//删除队头元素,用e返回其值
int Dequeue(LinkQueue *Q, QElemType *e)
{
    if (Q->front == Q->rear)
    {
        return false;
    }
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p = Q->front->next;
    *e = p->date;
    Q->front->next = p->next;
    //最后一个节点被删除,会导致尾指针丢失
    if (Q->rear == p)
    {
        Q->rear = Q->front;
    }
    free(p);
    return true;
}

//输出队列
int TraverseQueue(LinkQueue *Q)
{
    QueuePtr f = Q->front;
    while (f != Q->rear)
    {
        f = f->next;
        printf("%d ", f->date);
    }
    putchar(10);
}

//获得队头的值
QElemType GetHead(LinkQueue *Q)
{
    if (Q->front != Q->rear)
    {
        return Q->front->next->date;
    }
}

int DestroyQueue(LinkQueue *Q)
{ 
  while(Q->front)
  {
    Q->rear=Q->front->next;
    free(Q->front);
    Q->front=Q->rear;
  }
  free(Q);
  //printf("成功销毁该队列!\n");
  return true;
}

运行结果
在这里插入图片描述

程序应该还是有不足之处,如果有兴趣的话,你可以自己改改。
最后附一个代码草稿吧,数组写的。

#include<stdio.h>
#include<malloc.h>
#include<string.h>

void move1index(int * q,int len);
void output(int *q,int len);

int main()
{
    
    int len=13;
    int queue[20];
    memset(queue,0,sizeof(int)*20);
    queue[0]=0;queue[1]=1;queue[2]=0;
    for (int i = 0; i < len; i++)
    {
        printf("%d ",queue[i]);
    }
    putchar(10);
    int n=2;
    for (int i = 0; i < 10; i++)
    {
        //printf("当n=%d:\n",n);
        for (int j = 0; j < n; j++)
        {
            int num=queue[0]+queue[1];
            printf("%d ",num);
            queue[(n+1)%20]=num;
            move1index(queue,len);
            //printf("移动后的队列:");
            //output(queue,len);
        }
        putchar(10);
        n++;
        queue[n]=0;
    }
    
    return 0;
}

void move1index(int * q,int len)
{
    for (int i = 0; i < len-1; i++)
    {
        q[i]=q[i+1];
    }
}

void output(int *q,int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ",q[i]);
    }
    putchar(10);
}

本来想用循环队列写的,后来发现思想就那样,就这样吧。

版权声明:本文为qq_42311935原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42311935/article/details/90578487

智能推荐

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

猜你喜欢

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...

创建一个Servlet项目流程(入门)

版本 IDEA 2020.2 JDK1.8 apache-tomcat-9.0.36 项目流程 一、IDEA中新建JaveEE项目 项目起名,选择项目存放地址,点击finish创建成功 进入项目后,右键选择项目,选择add Framework Support 选择Web Application,点击OK 此时项目文件夹 在WEB-INF下创建两个目录classes和lib 按ctrl+alt+sh...

Docker部署SpringCloud ELK+RabbitMQ日志

Docker部署SpringCloud ELK+RabbitMQ日志  Im_Coder 原文:https://www.jianshu.com/p/f773f23096a9 一、效果图 image.png 二、ELK是什么? ELK由ElasticSearch、Logstash和Kiabana三个开源工具组成。 其中Elasticsearch是个开源分布式搜索引擎,它的特点有:分布式,索...