队列作业
一、队列的顺序表示和实现
要求：
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1）"下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
二、队列的链式表示和实现
要求:
编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化并建立链队列
（2）入链队列
（3）出链队列
（4）遍历链队列
分析:
队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
注意：
（1）和链栈类似，无须考虑判队满的运算及上溢。
（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。
#include
#include
#define MAXNUM 100
#define Elemtype int
#define TRUE 1
#define FALSE 0
typedef struct
{ Elemtype queue[MAXNUM];
int front;
int rear;
}sqqueue;
/*队列初始化*/
int initQueue(sqqueue *q)
{ if(!q) return FALSE;
；
return TRUE;
}
/*入队*/
int append(sqqueue *q, Elemtype x)
{ if(q->rear>=MAXNUM-1) return FALSE;
；
return TRUE;
}
/*出队*/
Elemtype Delete(sqqueue *q)
{ Elemtype x;
；
return x;
}
/*判断队列是否为空*/
int Empty(sqqueue *q)
{ ；
}
/*取队头元素*/
int gethead(sqqueue *q)
{ ；
}
/*遍历队列*/
void display(sqqueue *q)
{ int s;
s=q->front;
if (q->front==q->rear)
printf("队列空!\n");
else
{printf("\n顺序队列依次为：");
while(s
{s=s+1;
printf("%d<-", q->queue[s]);
}
printf("\n");
printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear);
printf("顺序队列的队头元素所在位置:front=%d\n",q->front);
}
}
/*建立顺序队列*/
void Setsqqueue(sqqueue *q)
{ int n,i,m;
printf("\n请输入将要入顺序队列的长度:");
scanf("%d",&n);
printf("\n请依次输入入顺序队列的元素值:\n");
for (i=0;i { ； } } main() { sqqueue *head; int x,y,z,select; head=(sqqueue*)malloc(sizeof(sqqueue)); do{printf("\n第一次使用请初始化！\n"); printf("\n请选择操作(1--7):\n"); printf("===================================\n"); printf("1 初始化\n"); printf("2 建立顺序队列\n"); printf("3 入队\n"); printf("4 出队\n"); printf("5 判断队列是否为空\n"); printf("6 取队头元素\n"); printf("7 遍历队列\n"); printf("===================================\n"); scanf("%d",&select); switch(select) {case 1: { initQueue(head); printf("已经初始化顺序队列！\n"); break; } case 2: { Setsqqueue(head); printf("\n已经建立队列！\n"); display(head); break; } case 3: { printf("请输入队的值:\n "); scanf("%d",&x); append(head,x); display(head); break; } case 4: { z=Delete(head); printf("\n队头元素%d已经出队！\n",z); display(head); break; } case 5: { if(Empty(head)) printf("队列空\n"); else printf("队列非空\n"); break; } case 6: { y=gethead(head); printf("队头元素为:%d\n",y); break; } case 7: { display(head); break; } } }while(select<=7); } #include #include #define ElemType int typedef struct Qnode { ElemType data; struct Qnode *next; }Qnodetype; typedef struct { Qnodetype *front; Qnodetype *rear; }Lqueue; /*初始化并建立链队列*/ void creat(Lqueue *q) { Qnodetype *h; int i,n,x; printf("输入将建立链队列元素的个数：n= "); ； ； for(i=1;i<=n;i++) { printf("链队列第%d个元素的值为：",i); scanf("%d",&x); Lappend(q,x); } } /*入链队列*/ void Lappend(Lqueue *q,int x) { Qnodetype *s; ； } /*出链队列*/ ElemType Ldelete(Lqueue *q) { Qnodetype *p; ElemType x; if(q->front==q->rear) { printf("队列为空!\n"); x=0; } else { ； } return(x); } /*遍历链队列*/ void display(Lqueue *q) { Qnodetype *p; p=q->front->next; /*指向第一个数据元素节点*/ printf("\n链队列元素依次为："); while(p!=NULL) { ； } printf("\n\n遍历链队列结束！\n"); } main() { Lqueue *p; int x,cord; printf("\n*****第一次操作请选择初始化并建立链队列！*****\n "); do { printf("\n 链队列的基本操作\n "); printf("=========================================\n"); printf(" 主菜单\n"); printf("=========================================\n"); printf(" 1 初始化并建立链队列\n"); printf(" 2 入链队列\n"); printf(" 3 出链队列\n"); printf(" 4 遍历链队列\n"); printf(" 5 结束程序运行\n"); printf("==========================================\n"); scanf("%d",&cord); switch(cord) { case 1: { p=(Lqueue *)malloc(sizeof(Lqueue)); creat(p); display(p); }break; case 2: { printf("请输入队列元素的值：x="); scanf("%d",&x); Lappend(p,x); display(p); }break; case 3: { printf("出链队列元素：x=%d\n",Ldelete(p)); display(p); }break; case 4: {display(p);}break; case 5: {exit (0);} } }while (cord<=5); } 链队列的基本操作（创建，销毁，查找，删除，插入等）#include 实验名称：实验四队列的基本操作 实验目的 掌握队列这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序队列或链式队列，并完成下列操作： （1）初始化队列； （2）队列是否为空； （3）出队； （4）入队。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; //链表单链表 typedef struct Node *PNode; int dui; dui =1; struct Node { int info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; （二）总体设计 程序由主函数、创建队列函数、判断是否为空队列函数、入队函数、出队函数、取数函数、显示队列函数、菜单函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 main() { PLinkQueue a; //定义链表a int b,c,e; //b 菜单选择c选择继续输入e输入元素 do { //菜单选择 mune(); scanf("%d",&b); switch(b) { case 1://初始化 a=create(); //初始化队列 case 2: //入队 do { printf("\n请输入需要入队的数："); if(e!=NULL) { scanf("%d",&e); enQueue(a,e); } printf("是否继续入队？(是:1 否：0)\n"); scanf("%d",&c); } while(c==1); break; case 3: //出队 c=frontQueue(a); deQueue(a); if(dui!=0) { printf("\n出队为:%d\n",c); } dui=1; break; case 4: //显示队中元素 showQueue(a); break; case 5: return; default: printf("输入错误，程序结束!\n"); return; } } while(a!=5); { return 0; } } （三）各函数的详细设计： Function1: PLinkQueue create(void)//创队 队列的基本操作代码： #include (烽火传递)烽火台又称烽燧 单调队列及其应用 单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。 单调队列的出现可以简化问题，队首元素便是最大(小)值，这样，选取最大(小)值的复杂度便为O(1)，由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是O(1)。 如何维护单调队列呢，以单调递增序列为例： 1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。 2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止 要特别注意头指针和尾指针的应用。 下面介绍单调队列的具体应用： 一、单调队列的直接应用 1.合并果子 【问题描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 【输入文件】 输入文件fruit.in包括两行，第一行是一个整数n(1 <= n <= 10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1 <= ai <= 20000)是第i种果子的数目。 【输出文件】 输出文件fruit.Out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】 对于30%的数据，保证有n <= 1000； 对于50%的数据，保证有n <= 5000； 对于全部的数据，保证有n <= 10000。 分析: 这个题目非常的经典，发放也很多，可以采用快排或者堆，其思想都是选取当前最小的两个堆进行合并。复杂度均为O(nlOgn)，如果用有序队列维护，时间复杂度为O(n)。 每次选取进行合并的两堆，不是最先给定的堆，就是合并最初堆若干次后得到的新堆，所以需要维护两个单调递增队列，一个队列存最初给定的堆的值(1)，一个存合并后得到的新值(2)。 每次选择时有三种状态： 《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。 2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。 实验容 题目1： 进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数 算法提示： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈输出栈顶元素 题目2： 利用队列的方式实现辉三角的输出。 算法设计分析 （一）数据结构的定义 1、栈的应用 实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。 栈抽象数据结构描述 typedef struct SqStack /*定义顺序栈*/ { int *base; /*栈底指针*/ int *top; /*栈顶指针*/ int stacksize; /*当前已分配存储空间*/ } SqStack; 2、队列的应用 由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。 队列抽象数据结构描述 typedef struct SeqQueue { int data[MAXSIZE]; int front; /*队头指针*/ int rear; /*队尾指针*/ }SeqQueue; （二）总体设计 1、栈 （1）主函数：统筹调用各个函数以实现相应功能 int main() （2）空栈建立函数：对栈进行初始化。 int StackInit(SqStack *s) （3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出辉三角函数：按一定格式输出辉三角。 void YangHui(int n) 广西工学院计算机学院 《数据结构》课程实验报告书实验四队列的基本操作及其应用 学生姓名：李四 学号：2012 班级：计Y124 指导老师：王日凤 专业：计算机学院软件学院 提交日期：2013年6月20日 1．实验目的 1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。 2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。 3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。 2.实验内容 （1）建立一个含n个数据的队列，实现队列的基本操作。包括： ?//1. 初始化,构造一个空队列 void initQueue(Queue &Q) ?//2. 判断队列空, 空则返回true bool QueueEmpty(seqQueue &Q) ?//3. 判断队列满, 满则返回true bool QueueFull(seqQueue &Q) ?//4. 取队头元素, 用x返回队头元素，返回true；空队列则返回false Bool QueueHead(seqQueue &Q, elementType &x) ?//5. 入队列，在队尾插入新元素x （流程图） bool pushQueue (seqQueue &Q, elementType x) ?//6. 出队列，用x带回队头元素，并在队头删除，返回true，队列空则返回false（流程图）bool popQueue (seqQueue &Q, elementType &x) ?//7. 输出队列,从队头到队尾依次输出 void printQueue(seqQueue Q) （2）队列应用：利用队列操作打印杨辉三角形的前n行（如n=7）。 3．实验要求 （1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。 （2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。 （3）实验课上进行答辩。 （4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。 POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______2010\4\12 【实验目的】 1.理解并掌握栈和队列的逻辑结构和存储结构； 2.理解栈和队列的相关基本运算； 3.编程对相关算法进行验证。 【实验内容】 （一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）： 1.构造一个栈S，将构造好的栈输出； 2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出； 3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。（二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）： 1.构造一个队列Q，将构造好的队列输出； 2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出； 3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。 【要求】 1.栈和队列中的元素要从终端输入； 2.具体的输入和输出格式不限； 3.算法要具有较好的健壮性，对运行过程中的错误 操作要做适当处理。 三、实验步骤 1．本实验用到的数据结构 (1)逻辑结构：线性结构 (2)存储结构：程序一、四（顺序存储结构）； 程序二、三（链式存储结构）； 2．各程序的功能和算法设计思想 程序一：顺序栈 # include 数据结构实验报告 ----试验三循环队列的基本操作及应用 一、问题描述： 熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。 二、数据结构设计： #define MAXQSIZE 10 //最大队列长度 struct SqQueue { QElemType *base; //初始化动态分配存储空间 Int front; // 头指针，若队列不空，只想对列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的 //下一个位置 }; 三、功能设计： 程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) //构造一个空队列Q Status DestroyQueue(SqQueue &Q) //销毁队列Q,Q不再存在 Status ClearQueue(SqQueue &Q) //将Q清为空队列 Status QueueEmpty(SqQueue Q) //若队列Q为空队列，则 //返回TRUE，否则返回FALSE int QueueLength(SqQueue Q) //返回Q的元素个数，即队列长度Status GetHead(SqQueue Q,QElemType &e)//若队列不空，则用e返回Q的对 //头元素，并返回OK，否则返回ERROR Status EnQueue(SqQueue &Q,QElemType e)//插入元素e为Q的新的队尾元素Status DeQueue(SqQueue &Q,QElemType &e)//若队列不空，则删除Q的队头 //元素，用e返回其值，并返回 //OK，否则返回ERROR Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))//从队头到队尾依次 //对队列Q中每个元素调用函数 //vi()。一旦vi失败，则操作失败四、源程序： // c1.h (程序名) #include 实验二栈和队列的基本操作实现及其应用 一_一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack; 设计相关函数声明： 判断函数：int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 一_三、数据结构与核心算法的设计描述 1、初始化栈 /* 函数功能：对栈进行初始化。参数：栈(SqStack S)。 成功初始化返回0,否则返回-1 */ int InitStack(SqStack &S) { S.base=(SElemType *)malloc(10*sizeof(SElemType)); if(!S.base) //判断有无申请到空间 return -1; //没有申请到内存,参数失败返回-1 S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.base=new SElemType; return 0; } 2、判断栈是否是空 /*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/ int StackEmpty(SqStack S) { if(S.top==S.base) return -1; else return 0; } 3、入栈 /*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */ int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType)); 摘抄自C博客 组合数学 计数与统计 2001 - 符文杰：《Pólya原理及其应用》 2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》 2007 - 周冬：《生成树的计数及其应用》 2008 - 陈瑜希《Pólya计数法的应用》 数位问题 2009 - 高逸涵《数位计数问题解法研究》 2009 - 刘聪《浅谈数位类统计问题》 动态统计 2004 - 薛矛：《解决动态统计问题的两把利刃》 2007 - 余江伟：《如何解决动态统计问题》 博弈 2002 - 张一飞：《由感性认识到理性认识——透析一类搏弈游戏的解答过程》2007 - 王晓珂：《解析一类组合游戏》 2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》 母函数 2009 - 毛杰明《母函数的性质及应用》 拟阵 2007 - 刘雨辰：《对拟阵的初步研究》 线性规划 2007 - 李宇骞：《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》 置换群 2005 - 潘震皓：《置换群快速幂运算研究与探讨》 问答交互 2003 - 高正宇：《答案只有一个——浅谈问答式交互问题》 猜数问题 2003 - 张宁：《猜数问题的研究:<聪明的学生>一题的推广》 2006 - 龙凡：《一类猜数问题的研究》 数据结构 数据结构 2005 - 何林：《数据关系的简化》 2006 - 朱晨光：《基本数据结构在信息学竞赛中的应用》 2007 - 何森：《浅谈数据的合理组织》 2008 - 曹钦翔《数据结构的提炼与压缩》 结构联合 2001 - 高寒蕊：《从圆桌问题谈数据结构的综合运用》 2005 - 黄刚：《数据结构的联合》 块状链表 2005 - 蒋炎岩：《数据结构的联合——块状链表》 2008 - 苏煜《对块状链表的一点研究》 动态树 2006 - 陈首元：《维护森林连通性——动态树》 2007 - 袁昕颢：《动态树及其应用》 左偏树 2005 - 黄源河：《左偏树的特点及其应用》 跳表 2005 - 魏冉：《让算法的效率“跳起来”！——浅谈“跳跃表”的相关操作及其应用》 2009 - 李骥扬《线段跳表——跳表的一个拓展》 SBT 2007 - 陈启峰：《Size Balance Tree》 线段树 2004 - 林涛：《线段树的应用》 单调队列 2006 - 汤泽：《浅析队列在一类单调性问题中的应用》 哈希表 2005 - 李羽修：《Hash函数的设计优化》 2007 - 杨弋：《Hash在信息学竞赛中的一类应用》 Splay 2004 - 杨思雨：《伸展树的基本操作与应用》 实验二栈和队列的基本操作实现及其应用 一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容（可任选或全做） 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列， 是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType; //栈类型定义 typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack; 设计相关函数声明： 判断函数：int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 题目二、编程模拟队列的管理，主要包括： 出队列、 入队、 统计队列的长度、 查找队列某个元素e、 及输出队列中元素。 [实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。 题目三、Rails Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. Input The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output 数据结构面试之四——队列的常见操作 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 四、队列的基本操作 1.用数组构造队列 队列即是满足先进先出的链表。用数组存储的话，同样需要满足队列头front出栈，队列末尾rear入栈。而对于数组来讲，rear和front可以代表数组头和尾。不能简单的固定rear 和front的大小为maxSize和0，因为可能出现中间元素为空的现象。所以，对于数组队列来讲，可以想象成环式存储，因为每一次入队后rear+1，每一次出队后front+1。这就需要控制front和rear的大小，每一次修改只要满足front=（front+1）%maxSize，rear=（rear+1）%maxSize即可满足要求。 同样需要注意：入队操作前先判定队列是否已经满；出队操作前先判定队列是否为空。 template #include #include 转载自South_wind的专栏 常见的数据结构运用总结 考虑到Obsidian三个成员的擅长领域，这段时间都在做杂题，算是学习各种算法吧，趁现在休息的时间，而且大家马上要备战今年的比赛了，写写自己专攻方面的一些心得吧 扯开线段树、平衡树这些中高级的东西，先说说基础的数据结构 栈 算是代码量最小的数据结构？出栈进栈都只有一句话而已 常见用途： 消去一个序列中的相同元素(做法大家应该都知道了吧，见过很多次了) 维护一个单调的序列(所谓的单调栈，dp的决策单调？) 表达式求值(经典的栈运用，如果使用的很熟悉的话，可以处理一元、二元运算，不过最近没见过类似的题目了) 用于辅助其他算法(计算几何中的求凸包) 队列 队列应该还是很常见的数据结构了，如果专攻图论的话，spfa应该是写烂了的 这里说到的队列，是狭义的普通的队列和循环队列，不包括后面讲的一些变形 注意循环队列的写法，尽量不要使用取模运算，不然的话，遇到不厚道的出题者，可以把取模的循环队列卡到死 常见用途： 主要用于辅助其他算法，比如说spfa，bfs等(建议习惯用stl的孩子手写queue，毕竟就几行代码而已，偷懒会付出代价的。。。) 双端队列 如果写dp写的多的话，这个东西应该还是算是比较基础的东西了，双端队列多用于维护一个满足单调性的队列 还是建议手写，stl的deque使用块状链表写的，那东西的复杂度是O(Nsqrt(N))的，不要被迷惑了。 常见用途： dp的单调性优化，包括单调队列优化和斜率优化，都要用到这个结构 计算几何中的算法优化，比如半平面交 树的分治问题中利用单调队列减少转移复杂度 链表Dancing Links 写图论的不要告诉我不会写这货，链表可以写单双向，循环非循环的，高级点儿的可以考虑十字链表，麻花链表 不过链表可以说是树形结构的基础，如果这个掌握的不好，那么树形结构写起来就会很纠结 链表的优势在于可以O(1)的插入删除，如果要求插入的位置只是在序列的两端的话，这个数据结构是最方便的了(无视双端队列) hash表就是用链表实现的，熟悉hash的同学可以试试看怎么使你的hash效率提高 单调队列在信息学竞赛中的应用 一、概念介绍 1、双端队列 双端队列是一种线性表，是一种特殊的队列，遵守先进先出的原则。双端队列支持一下4种操作： （1）从队首删除 （2）从队尾删除 （3）从队尾插入 （4）查询线性表中任意一元素的值 2、单调队列 单调队列是一种特殊的双端队列，其内部元素具有单调性。最大队列与最小队列是两种比较常用的单调队列，其内部元素分别是单调递减和单调递增的。 单调队列的常用操作如下: (1)插入:若新元素从队尾插入后会破坏单调性,则删除队尾元素,直到插入后不再 破坏单调性为止,再将其插入单调队列。 (2)获取最优（最大、最小）值:访问队首元素 二、单调队列的应用 例题1：Sliding window1 给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端， 你的任务是找出窗口在各位置时的max value,min value. 输入格式： 第1行n,k,第2行为长度为n的数组 输出格式： 2行，第1行每个位置的min value,第2行每个位置的max value 样例： window.in 8 3 1 3 -1 -3 5 3 6 7 window.out -1 -3 -3 -3 3 3 3 3 5 5 6 7 数据范围： 20%：n<=500; 50%: n<=100000; 100%: n<=1000000; [题目大意] 给定一个长度为n的数列，求长度为k的定长连续子区间{a1,a2,a3,a4,…,ak-1,ak}{a2,a3,…,ak,ak+1}……中每个区间的最大值和最小值。 【分析】 这道题的模型相当于一个序列上的问题。看到题目，第一想法应该是：先枚举起始元素ax，然后求ax到ax+k-1的最大（小）值。朴素方法为直接扫描，这样，我们就得到了一个复杂度为O（nk）的算法。显然，根据题目的数据规模，这样的算法会超时。 思考一下有没有更优秀的算法？ 这道题目有个非常重要的信息，即所有的区间都是等长且连续的，那么对于“相邻”两个区间（l,r）与（l＋1，r＋1）有些极优美的性质： al,al+1,al+2,…,ar-1,ar,ar+1 以最大值为例： 我们注意到，在区间（l，r）中 Max（al,al+1,al+2,…,ar-1,ar） ＝max（al，max（al+1,al+2,…,ar-1,ar）） 在区间（l+1，r+1）中 Max（al+1,al+2,…,ar-1,ar,ar+1） ＝max（ar＋1，max（al+1,al+2,…,ar-1,ar）） 两个式子中有相同的部分max（al+1,al+2,…,ar-1,ar），经验告诉我们，区间（l，r）中最大值落在（l+1，r）区间的概念很大。那么，在求（l+1,r＋1）的最值时，我们完全没有必要再扫描一次。只有当上一次的最大值落在了al上时才需要重新扫描，这样，算法得到了极大的优化。 继续考虑这样一个问题，以最大值为例，对于任意l<=i<=j<=r，如果aic++,链队列的基本操作(创建,销毁,查找,删除,插入等)
数据结构(C语言)队列的基本操作
队列的基本操作代码
单调队列的应用
栈和队列的基本操作
队列的基本操作及其应用
ACM经典算法及配套练习题
栈和队列的基本操作的实现
试验 --循环队列的基本操作及应用
栈和队列的基本操作实现及其应用
NOI国家集训队论文分类(至2008)(摘抄自C博客)
数据结构 栈和队列的基本操作实现及其应用
队列的常见操作
链队列基本操作的C++实现
顺序队列的基本操作
数据结构总结
单调队列在信息学竞赛中的应用