客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
3.1 比较线性表、栈和队列这三种数据结构的相同点和不同点。 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。
首先这是个卡特兰数，有2n个人排成一队进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票可找零，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。 对于这个例子，剧院要想总有零钱可找，那么目前进入剧院的人数中，揣着10元钞票的人数必须少于等于揣着5元钞票的，不然肯定在某个人那出现没零钱找的情况。 现在回到正题上来对于一个给定入栈序列，怎么求它的出栈序列呢？ 我们可以把入栈记为1，出栈记为0.那么前缀子序列中1的个数必须大于等于0的个数，即入栈次数要大于等于出栈次数,如1 1 0 1 0 0，它的任意前缀序列中1的个数是大于等于0的个数的。 我们来看个例子:对于1 2 3这个入栈序列，1 1 0 1 0 0就是一个入栈出栈序列，第一个1代表元素1入栈，然后第二个1代表元素2入栈，然后第三个是0，代表出栈，即元素2出栈，然后第四个是1，代表元素3入栈，然后第五个是0，代表出栈，即元素3出栈，然后第六个是0，代表元素1出栈。最后1 1 0 1 0 0就代表了出栈序列2 3 1。 那么现在的问题就转换为如何求出所有符合条件的0 1序列了。其实这和以下问题相同:给定括号对数，输出所有符合要求的序列。如2对括号，输出有()()或者(())两种。1可以看成'('，0可以看成‘)’。 卡特兰数 首先是卡特兰数的定义：令h(0)=1,h(1)=1，catalan数满足递推式： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)。 可以根据上面的递推公式，写出递归的计算方案。 public static int Catalan(int n) { int nCount = 0; if ( n < 0 ) { return 0; } if ( 0 == n || 1 == n ) { return 1; } for (int i = 0; i < n; ++i ) { nCount += Catalan(i) * Catalan(n - i - 1); } return nCount; }
D,C,E,F,A,B 不能得到，把A 和B的位置换一下可以 A,C,E,D,B,F 可以。A进栈A出栈 B进，C进，C出，D进E进，E出，D出，B出，F进F出
将栈的元素倒置呗，我们考虑将栈元素弹出后放入另一个栈，然后输出 // 写一算法将一顺序栈的元素依次取出，并打印元素值。
public static void ReverseStack(int _n)
{
if ( _n < 0 )
{
return;
}
SeqStack<int> stack = new SeqStack<int>(_n);
SeqStack<int> revStack = new SeqStack<int>(_n);
for (int i = 0; i < _n; ++i)
{
stack.Push(i+1);
}
for (int i = 0; i < _n; ++i )
{
revStack.Push(stack.Pop());
}
for (int i = 0; i < _n; ++i)
{
Console.WriteLine("栈的元素依次为" + revStack.Pop());
}
}
当有数据元素入队时，队尾指示器rear加1，当有数据元素出队时，队头指示器front加1。当front=rear时，表示队列为空，队尾指示器rear到达数组的上限处而front为-1时，队列为满。 如上图再有一个数据元素入队就会出现溢出。但事实上队列中并未满，还有空闲空间，把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。 //求循环顺序队列的长度 public int GetLength() { return (rear-front+maxsize) % maxsize; } //清空循环顺序队列 public void Clear() { front = rear = -1; } //判断循环顺序队列是否为空 public bool IsEmpty() { if (front == rear) { return true; } else { return false; } } //判断循环顺序队列是否为满 public bool IsFull() { if ((rear + 1) % maxsize==front) { return true; } else { return false; } }
//入队 public void Enqueue(T item) { if (IsFull()) { Console.WriteLine("队列已满"); return; } data[++rear] = item; } //出队 public T Dequeue() { T tmp = default(T); if (IsEmpty()) { Console.WriteLine("队列为空"); return tmp; } tmp = data[++front]; return tmp; } //获取队头数据元素 public T GetFront() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } return data[front + 1]; }
public static void PrintLinkQueue(int _n) { LinkQueue<int> queue = new LinkQueue<int>(); for (int i = 0; i < _n; ++i) { queue.Enqueue(i + 1); Console.WriteLine("队列的元素依次为" + queue.Dqueue()); } }
好了就写到这里，至于优先级的问题，以后有时间再说 |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论