链队写杨辉三角（再附一个数组的）

杨辉三角

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

举例

第一步： 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); }

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