楊輝三角
楊輝三角的特點(diǎn)是售貌，兩腰都是1冕房，中間的數(shù)=上面兩個(gè)數(shù)之和。
使用隊(duì)列思想實(shí)現(xiàn)楊輝三角的流程
- 首先趁矾，需要初始化一個(gè)隊(duì)列。
- 將第一行的元素1入隊(duì)给僵，接著操作第二行（第一二行不需要求和操作毫捣，直接將元素入隊(duì)即可）
- 從第三行開始，現(xiàn)在的隊(duì)首指向N-1行帝际，先將每行的固定元素1入隊(duì)蔓同，然后循環(huán)操作求和過程：
將隊(duì)首元素出隊(duì)并保存其值tmp；
獲取當(dāng)前隊(duì)首的元素x蹲诀，并進(jìn)行tmp=tmp+x斑粱，且將tmp入隊(duì)； - 循環(huán)結(jié)束后脯爪，隊(duì)首在N-1行的最后一個(gè)元素處则北，現(xiàn)在將其出隊(duì)，然后在每行最后的固定元素1入隊(duì);
- 循環(huán)3痕慢、4步尚揣，最后打印最后一行的元素就可以輸出楊輝三角了。
實(shí)現(xiàn)
Node
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class Node<T>
{
T data;
Node<T> next;
/// <summary>
/// 構(gòu)造器
/// </summary>
public Node()
{
this.Data = default(T);
this.Next = null;
}
/// <summary>
/// 構(gòu)造器
/// </summary>
/// <param name="data"></param>
public Node(T data)
{
this.Data = data;
this.Next = null;
}
public T Data { get => data; set => data = value; }
internal Node<T> Next { get => next; set => next = value; }
}
}
LQueue
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class LQueue<T>
{
Node<T> font; // 隊(duì)首
Node<T> rear; // 隊(duì)尾
/// <summary>
/// 構(gòu)造器
/// </summary>
public LQueue()
{
font = new Node<T>();
rear = font;
font.Next = null;
}
/// <summary>
/// 在表尾入隊(duì)
/// </summary>
/// <param name="data"></param>
public void Put(T data)
{
//新建節(jié)點(diǎn)
Node<T> tmp = new Node<T>(data);
//掛載節(jié)點(diǎn)到隊(duì)尾
rear.Next = tmp;
//更新隊(duì)尾
rear = tmp;
}
/// <summary>
/// 在表頭出隊(duì)
/// </summary>
public T Get()
{
if (font.Next == null) return default(T);
//保存隊(duì)首元素
Node<T> tmp = font.Next;
//懸空隊(duì)首元素
font.Next = font.Next.Next;
return tmp.Data;
}
/// <summary>
/// 判空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return font.Next == null;
}
/// <summary>
/// 讀隊(duì)列頭元素
/// </summary>
/// <returns></returns>
public T GetHead()
{
return font.Next.Data;
}
}
}
Program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class Program
{
static void Main(string[] args)
{
LQueue<int> lq = new LQueue<int>();
int N = 5; //行數(shù)
int x;
lq.Put(1); //第一行元素入隊(duì)
//從第二行元素開始
for (int n = 2; n <= N; n++)
{
lq.Put(1); //第n行第一個(gè)元素入隊(duì)
//處理第1到n-1個(gè)元素
for (int j = 1; j <= n-2; j++)
{
int tmp = lq.Get(); //棧頂元素出隊(duì)
Console.Write(tmp); //打印第n-1行的元素
x = lq.GetHead();
tmp = tmp + x; //利用隊(duì)中第n-1行元素產(chǎn)生第n行元素
lq.Put(tmp);
}
x =lq.Get();
Console.WriteLine(x);
lq.Put(1); //將第n行尾的1入隊(duì)
}
//打印最后一行的元素
while (!lq.IsEmpty())
{
Console.Write(lq.Get());
}
}
}
}
