队列算法
‘壹’ 数据结构 队列
作业
第一章
1． 编写一个算法，判断浮点数数组a[]中是否有值大于1000的成员。若有，则给出大于1000的成员中下标最小那个成员的下标。指出算法中的基本操作和关键操作，分析你的算法的时间复杂性，并用大O记法表示之。
2． 斐波那契数列定义为： 给出一个计算第 个斐波那契数的非递归的算法，指出算法中的基本操作，分析你的算法的时间复杂性并用大O记法表示之。
第二章
1． 对线性表（18，8，21，7，3），画出相应的带表头结点的双向循环链表。
2． 编写一个算法，在带表头结点的有序单链表中，插入值为 的结点，并使新的链表仍然有序。
第三章
1． 请编写一个算法，把一个队列逆置，在算法中可以使用栈，可以调用栈和队列的基本操作，但不允许直接处理栈和队列中的元素。
2． 对于循环队列，
（1） 试写出求队列长度的算法；
（2） 试写出判断队列是否为空的算法。
第四章
1． 假设3维数组 以列序为主序的方式顺序存储，请为它推导出地址计算公式。
2． 编写一个算法，计算子串S2在串S1中的出现次数。
第五章
1． 请给出下图所示的树的前序、后序和层次遍历序列。
2． 已知某二叉树的前序序列和中序序列分别是ABDECFGH和DBEAGFHC，请画出该二叉树，并写出其后序序列。
3． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求二叉树的高度。
4． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求出二叉树中值为x的结点的数目。
5． 已知下图所示的二叉树是由某森林转换而来的。请给出原森林。
6． 假定有八个字符，它们出现的概率分别为：0.07、0.09、0.14、0.19、0.23、0.44、0.58和0.77。
（1）请给出这8个字符的哈夫曼树和哈夫曼编码；
（2）编码树的WPL的实际意义是什么？
第六章
1． 对于如下图所示的有向图，请给出
(1) 各顶点的入度和出度
(2) 强连通分量和弱连通分量
(3) 邻接矩阵
(4) 邻接表和逆邻接表
2． 假设有向图存储为邻接矩阵，请编写一个算法，求出指定顶点的入度和出度。
3． 对于如下图所示的无向图，分别画出其深度优先搜索和广度优先搜索生成的树。
4． 对下面的无向带权图应用求最短路经的Floyd算法，求出每对顶点之间的最短路径，并写出在算法的执行过程中所求得的各个矩阵。
5． 对如下图所示的无向带权图，按照Kruskal算法求出最小生成树，并画出每一步所得到的中间结果。
第七章
1． 试比较顺序查找算法和二分查找算法的特点、优缺点。
2． 请编写一个递归的二分查找算法。
3． 从一棵空的查找树开始，依次插入键值71，32，103，66，135，82，57，91，画出每次插入后所得到的查找树，再依次删除57、82、71，画出每次删除后所得到的查找树，并对最终得到的查找树求出等概率情况下的平均成功查找长度。
4． 请编写一个判断二叉树T是否为查找树的算法，假定二叉树T是以标准形式存贮的。
5． 从一个空的散列表开始，依次为插入关键字Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec，散列函数为 为关键字key第一个字母的序号，如 散列表长度为17。分别使用
（1） 线性探测法
（2） 链地址法
建立散列表。请分别画出散列表，并求出等概率情况下的平均成功查找长度。
第八章
1． 分别用下列排序算法对关键字序列（49，7，50，5，94，16，90，29，71）进行排序，写出每一趟排序所得到的中间结果。
（1） 直接插入排序
（2） 希尔排序
（3） 改进的冒泡排序
（4） 快速排序
（5） 直接选择排序
（6） 堆排序
（7） 合并排序
2． 一种冒泡排序算法是所谓“上浮式的”，即每趟排序都把较小的关键字“浮”到上面（数组下标较小的那一边）去。请编写一个改进的“下沉式的”冒泡排序算法。
3． 举例说明直接选择排序算法、快速排序算法和堆排序算法不是稳定的。
‘贰’ 循环队列 数据结构题 【求一完整程序 ！】编写实现该循环队列的入队和出队操作的算法。
(VC6下编译通过)
#include <stdio.h>
main()
{
int a[1000],top,tail;
int i,n=1;
do
{
switch (n)
{
case 1:top=tail=0;break;
case 2:printf("输入要插入的元素：");scanf("%d",&a[++top]);break;
case 3:if (tail<top) tail++;break;
case 4:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n队头为： %d\n",a[top]);break;
case 5:printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");if (tail==top) printf("空队列\n"); else printf("非空队列.\n");
}
if (n!=5&&n!=4)
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
printf("队列现在状态：");
for (i=tail+1;i<=top;i++)
printf(" %d",a[i]);
if (tail==top)
printf("空队列");
printf("\n");
printf("\n1队列初始化\n2入队操作\n3出队操作\n4输出队头元素\n5判断队列是否为空\n0退出\n请输入代码：");
scanf("%d",&n);
} while (n!=0);
}
‘叁’ 多级队列调度算法和多级反馈队列的调度算法 优缺点
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
int time[3];
struct program { /* 定义进程控制块PCB */
char name[10];
char state;
int queue;//进程队列
int priority; // 数字越小优先级越高
int needtime;//需运行时间
int runtime; //已经运行时间
struct program *link;
}*ready=NULL;
typedef struct program PROGRAM;
PROGRAM *run=NULL,*head1=NULL,*head2=NULL,*head3=NULL,*end1=NULL,*end2=NULL,*end3=NULL;
/*PROCESS *high_priority(PROCESS *P) //选择优先级最高的进程
{
PROCESS *q,*p; //问题，入口形参中
q=p;
while(p->next!=NULL)
{
if(q->priority>p->priority)
q=p;
p=p->next;
}
return q;
}*/
void sort(PROGRAM *p)
{switch(p->queue)
{case 1:
{if(head1==NULL) {head1=p;end1=p;}
else
{end1->link=p;end1=p;p->link=NULL;}
p->state='w';
break;
}
case 2:
{if(head2==NULL)
{head2=p;end2=p;p->state='w';}
else
{end2->link=p;end2=p;p->link=NULL;}
p->state='w';
break;
}
case 3:
{if(head3==NULL)
{head3=p;end3=p;}
else
{end3->link=p;end3=p;p->link=NULL;}
p->state='w';
break;
}
}
}
void input() /* 建立进程控制块函数*/
{ PROGRAM *p;
int i,num;
/*clrscr(); 清屏*/
system("cls");
printf("\n 多级反馈队列调度算法 \n");
printf("\n 请输入进程个数:\n");
scanf("%d",&num);
//printf("\n qname \t state \t queue \t needtime \t runtime \n");
printf("\n 输入第一个进程名:");
ready=getpch(PROGRAM);
scanf("%s",ready->name);
printf("\n 输入第一个进程优先级:");
scanf("%d",&ready->priority);
printf("\n 输入第一个进程运行时间:");
scanf("%d",&ready->needtime);
printf("\n");
ready->runtime=0;ready->state='r';
ready->queue=1;
ready->link=NULL;
for(i=0;i<num-1;i++)
{ printf("\n 进程号No.%d:\n",i+2);
p=getpch(PROGRAM);
printf("\n 输入进程名:");
scanf("%s",p->name);
printf("\n 输入进程优先级:");
scanf("%d",&ready->priority);
p->queue=1;
//printf("\n 输入进程队伍数1~3:");
//scanf("%d",&p->queue);
printf("\n 输入进程运行时间:");
scanf("%d",&p->needtime);
printf("\n");
p->runtime=0;p->state='w';
p->link=NULL;
sort(p);
}
}
void disp(PROGRAM * pr) /*建立进程显示函数,用于显示当前进程*/
{
printf("\n qname\t priority\t state\t queue\t needtime\t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->priority);
printf("|%c\t",pr->state);
printf("|%d\t",pr->queue);
printf("|%d\t",pr->needtime);
printf("|%d\t",pr->runtime);
printf("\n");
}
void check()//进程查看函数
{PROGRAM *pr;
printf("\n****当前正在运行的进程%s",run->name);
disp(run);
printf("\n****当前正准备好的进程%s",ready->name);
if(ready!=NULL)
{disp(ready);
printf("\n****当前就绪的队列状态为:\n");}
pr=head1;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
pr=head2;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
pr=head3;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
//三个队伍的进程的执行函数
void runpro()
{
run=ready;
if(head1!=NULL)
{ready=head1;head1=head1->link;ready->state='r';}
else
{
if(head2!=NULL)
{ready=head2;head2=head2->link;ready->state='r';}
else
{if(head3!=NULL)
{ready=head3;head3=head3->link;ready->state='r';}
else
ready=NULL;}
}
if(run!=NULL)
{check();//显示运行及等待队列的状况
run->runtime=run->runtime+time[run->queue-1];
if(run->runtime>run->needtime)
run->runtime=run->needtime;
if(run->queue<3)
run->queue+=1;
//disp(run);
if(run->runtime<run->needtime)
sort(run);
}
}
void main() /*主函数*/
{
int h=0;
char ch;
input();
time[0]=1;
time[1]=2;
time[2]=3;
while(ready!=NULL)
{
ch=getchar();
h++;//标志执行的步骤
printf("\n The execute number:%d \n",h);
runpro();
if(run->runtime==run->needtime)
{printf("\n进程%s已经完成\n",run->name);/*run=NULL;*/}
printf("\n 按任一键继续......");
ch=getchar();
}
printf("整个进程运行完毕");
}
‘肆’ 我想知道队列算法能干什么
队列是一种先进先出的数据结构，由于这一规则的限制，使得队列有区别于栈等别的数据结构。
作为一种常用的数据结构，同栈一样，是有着丰富的现实背景的。以下是几个典型的例子。
[例5-2] 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的).给定两个城市之间的距离D1,汽车油箱的容量C(以升为单位),每升汽油能行驶的距离D2,出发点每升汽油价格P和沿途油站数N(N可以为零),油站i离出发点的距离Di,每升汽油价格Pi(i=1,2,……N).
计算结果四舍五入至小数点后两位.
如果无法到达目的地,则输出"No Solution".
样例:
INPUT
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
油站号I
离出发点的距离Di
每升汽油价格Pi
1
102.0
2.9
2
220.0
2.2
OUTPUT
26.95(该数据表示最小费用)
[问题分析]
看到这道题,许多人都马上判断出穷举是不可行的,因为数据都是以实数的形式给出的.但是,不用穷举,有什么方法是更好的呢 递推是另一条常见的思路,但是具体方法不甚明朗.
既然没有现成的思路可循,那么先分析一下问题不失为一个好办法.由于汽车是由始向终单向开的,我们最大的麻烦就是无法预知汽车以后对汽油的需求及油价变动;换句话说,前面所买的多余的油只有开到后面才会被发觉.
提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案,那就必须做到两点,即只为用过的汽油付钱;并且只买最便宜的油.如果在以后的行程中发现先前的某些油是不必要的,或是买贵了,我们就会说:"还不如当初不买."由这一个想法,我们可以得到某种启示:假设我们在每个站都买了足够多的油,然后在行程中逐步发现哪些油是不必要的,以此修改我们先前的购买计划,节省资金;进一步说,如果把在各个站加上的油标记为不同的类别,我们只要在用时用那些最便宜的油并为它们付钱,其余的油要么是太贵,要么是多余的,在最终的计划中会被排除.要注意的是,这里的便宜是对于某一段路程而言的,而不是全程.
[算法设计]由此,我们得到如下算法:从起点起(包括起点),每到一个站都把油箱加满(终点除外);每经过两站之间的距离,都按照从便宜到贵的顺序使用油箱中的油,并计算花费,因为这是在最优方案下不得不用的油;如果当前站的油价低于油箱中仍保存的油价,则说明以前的购买是不够明智的,其效果一定不如购买当前加油站的油,所以,明智的选择是用本站的油代替以前购买的高价油,留待以后使用,由于我们不是真的开车,也没有为备用的油付过钱,因而这样的反悔是可行的;当我们开到终点时,意味着路上的费用已经得到,此时剩余的油就没有用了,可以忽略.
数据结构采用一个队列:存放由便宜到贵的各种油,一个头指针指向当前应当使用的油(最便宜的油),尾指针指向当前可能被替换的油(最贵的油).在一路用一路补充的过程中同步修改数据,求得最优方案.
注意:每到一站都要将油加满,以确保在有解的情况下能走完全程.并假设出发前油箱里装满了比出发点贵的油,将出发点也看成一站,则程序循环执行换油,用油的操作,直到到达终点站为止.
本题的一个难点在于认识到油箱中油的可更换性,在这里,突破现实生活中的思维模式显得十分重要.
[程序清单]
program ex5_2(input,output);
const max=1000;
type recordtype=record price,content:real end;
var i,j,n,point,tail:longint;
content,change,distance2,money,use:real;
price,distance,consume:array[0..max] of real;
oil:array [0..max] of recordtype;
begin
write('Input DI,C,D2,P:'); readln(distance[0],content,distance2,price[0]);
write('Input N:'); readln(n); distance[n+1]:=distance[0];
for i:=1 to n do
begin
write('Input D[',i,'],','P[',i,']:');
readln(distance[i],price[i])
end;
distance[0]:=0;
for i:=n downto 0 do consume[i]:=(distance[i+1]-distance[i])/distance2;
for i:=0 to n do
if consume[i]>content then
begin writeln('No Solution'); halt end;
money:=0; tail:=1; change:=0;
oil[tail].price:=price[0]*2; oil[tail].content:=content;
for i:=0 to n do
begin
point:=tail;
while (point>=1) and (oil[point].price>=price[i]) do
begin
change:=change+oil[point].content;
point:=point-1
end;
tail:=point+1;
oil[tail].price:=price[i];
oil[tail].content:=change;
use:=consume[i]; point:=1;
while (use>1e-6) and (point=oil[point].content
then begin use:=use-oil[point].content;
money:=money+oil[point].content*oil[point].price;
point:=point+1 end
else begin oil[point].content:=oil[point].content-use;
money:=money+use*oil[point].price;
use:=0 end;
for j:=point to tail do oil[j-point+1]:=oil[j];
tail:=tail-point+1;
change:=consume[i]
end;
writeln(money:0:2)
end.
[例5-3] 分油问题:设有大小不等的3个无刻度的油桶,分别能够存满,X,Y,Z公升油(例如X=80,Y=50,Z=30).初始时,第一个油桶盛满油,第二,三个油桶为空.编程寻找一种最少步骤的分油方式,在某一个油桶上分出targ升油(例如targ=40).若找到解,则将分油方法打印出来;否则打印信息"UNABLE"等字样,表示问题无解.
[问题分析] 这是一个利用队列方法解决分油问题的程序.分油过程中,由于油桶上没有刻度,只能将油桶倒满或者倒空.三个油桶盛满油的总量始终等于开始时的第一个油桶盛满的油量.
[算法设计] 分油程序的算法主要是,每次判断当前油桶是不是可以倒出油,以及其他某个油桶是不是可以倒进油.如果满足以上条件,那么当前油桶的油或全部倒出,或将另一油桶倒满,针对两种不同的情况作不同的处理.
程序中使用一个队列Q,记录每次分油时各个油桶的盛油量和倾倒轨迹有关信息,队列中只记录互不相同的盛油状态(各个油桶的盛油量),如果程序列举出倒油过程的所有不同的盛油状态,经考察全部状态后,未能分出TARG升油的情况,就确定这个倒油问题无解.队列Q通过指针front和rear实现倒油过程的控制.
[程序清单]
program ex5_3(input,output);
const maxn=5000;
type stationtype=array[1..3] of integer;
elementtype=record
station:stationtype;
out,into:1..3;
father:integer
end;
queuetype=array [1..maxn] of elementtype;
var current,born:elementtype;
q:queuetype;
full,w,w1:stationtype;
i,j,k,remain,targ,front,rear:integer;
found:boolean;
procere addQ(var Q:queuetype;var rear:integer; n:integer; x:elementtype);
begin
if rear=n
then begin writeln('Queue full!'); halt end
else begin rear:=rear+1; Q[rear]:=x end
end;
procere deleteQ(var Q:queuetype;var front:integer;rear,n:integer;var x:elementtype);
begin
if front=rear
then begin writeln('Queue empty!'); halt end
else begin front:=front+1; x:=Q[front] end
end;
function p(w:stationtype;rear:integer):boolean;
var i:integer;
begin
i:=1;
while (i<=rear) and ((w[1]q[i].station[1]) or
(w[2]q[i].station[2]) or (w[3]q[i].station[3])) do i:=i+1;
if i0 then
begin
print(q[k].father);
if k>1 then write(q[k].out, ' TO ',q[k].into,' ')
else write(' ':8);
for i:=1 to 3 do write(q[k].station[i]:5);
writeln
end
end;
begin {Main program}
writeln('1: ','2: ','3: ','targ');
readln(full[1],full[2],full[3],targ);
found:=false;
front:=0; rear:=1;
q[1].station[1]:=full[1];
q[1].station[2]:=0;
q[1].station[3]:=0;
q[1].father:=0;
while (front begin
deleteQ(q,front,rear,maxn,current);
w:=current.station;
for i:=1 to 3 do
for j:=1 to 3 do
if (ij) and (w[i]>0) and (w[j]remain
then begin w1[j]:=full[j]; w1[i]:=w[i]-remain end
else begin w1[i]:=0; w1[j]:=w[j]+w[i] end;
if not(p(w1,rear)) then
begin
born.station:=w1;
born.out:=i;
born.into:=j;
born.father:=front;
addQ(q,rear,maxn,born);
for k:=1 to 3 do
if w1[k]=targ then found:=true
end
end
end;
if not(found)
then writeln('Unable!')
else print(rear)
end.
‘伍’ 队列初始化 入队列和出队列的算法
#include <iostream.h>
#include <stdlib.h>
void main()
{
}
#define Status bool
#define ElemType int
typedef struct list{
ElemType data;
struct list *next;
struct list *pre;
}*CLQueue;
Status InitCLQueue(CLQueue &rear)
{
CLQueue q = (CLQueue )malloc(sizeof(struct list));
rear = q;
rear->next = rear->pre = rear;
return true;
}
Status EnCLQueue(CLQueue &rear, ElemType x)
{
CLQueue q = (CLQueue)malloc(sizeof(struct list));
q->data = x;
if(rear->next == rear)
{
rear->next = rear->pre =q;
q->next = q->pre = rear;
rear = q;
}
else
{
q->pre = rear->next;
q->next = rear->next->next;
rear->next->next->pre = q;
rear->next->next = q;
}
return true;
}
Status DeCLQueue(CLQueue &rear, ElemType &x)
{
if(rear->next == rear) return false;
rear = rear->pre;
CLQueue q = rear->next;
q->next->pre = rear;
rear->next = q->next;
free(q);
return true;
}
‘陆’ 对于循环队列,试写出求队列含有多少个元素的算法,并将算法用C代码实现。
对于循环队列，求队列含有多少个元素的算法如下：
typedef struct
{
int tail,head;
int a[Max];
}queue;
void enqueue(int key,queue&q)
{
q.a[q.tail]=key;
q.tail=(q.tail+1)%Max;
}
int dequeue(queue&q)
{
int key;
key=q.a[q.head];
q.head=(q.head+1)%Max;
return key;
}
(6)队列算法扩展阅读：
计算循环队列的元素个数：(尾－头＋表长)%表长
队列头指针为来front，队列尾指针为rear，队列容量为M，则元素个数为|rear-front+M|%M,注意，这个自%是求余运算。
设f为队头，r为队尾，m为队长，a为元素个数，则1. f>r时，a=m+r-f; 2. f<=r时，a=r-f
‘柒’ 写出队列的入队及出队算法
入队算法
linklist in_queue(linklist rear,datatype x)
{
s=new lnode;
s->data=x;
s->next=rear->next;
rear->next=s;
rear=s;
return(rear );
}
出队算法
linklist out_queue(linklist rear,datatype *x)
{
if (rear->next==rear)
return(NULL);
q=rear->next->next;
if (q==rear)
{
rear=rear->next;
rear->next=rear;
}
else
{
rear->next->next=q->next;
}
*x=q->data;
delete q;
return(rear);
}
‘捌’ c语言队列排序要用什么什么算法
可以调用 系统函数
可以使用 快排 qort 函数 (头文件stdlib,h里面)，
只需要自己编写 比较函数
int cmp(const void *p1, const void *p2)
{
}
可以网络一下用法 ， 很详细的！
当然可以自己写 排序函数 快排 堆排序 。。。。 冒泡 和选择的 效率就很低了
http://ke..com/view/982231.htm
‘玖’ 用两个栈实现一个队列的功能要求给出算法和思路！
举例说明，假设我们进行以下4步：
push 1, 2
pop //此时应pop 1
push 3
pop //此时应pop 2
在运行第一个pop时，把A中的1,2全push到B中去，然后再pop得到1，此时B中还剩一个2
下一步push 3，是push到A中
最后一步pop，把B中的2给pop出去
关键点：
(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；
这里隐含了一点，如果为空，就直接从B中pop，不对A进行任何操作。很显然，需要if..else语句。
弹栈和一般的出栈不同，需要多一部检测B是否为空。
如果B不为空，则直接从B出栈，这时与一般的出栈相同。
如果B为空，则需要把A中所有的元素出栈并压栈到B中去，然后再对B进行一般的出栈操作。
‘拾’ 简述以下算法的功能（队列的元素类型为int）
proc_1
函数是将栈元素倒序..
例如
s中元素从栈底到栈顶为1,2,3,4...n调用后s中元素为n...4,3,2,1
但是这个函数有个bug,void
proc_1(stack
s)
要讲形参定义为引用类型即void
proc_1(stack
&s),这样可以修改实参...如果只是做题而已..则忽略我以上bug之说..
void
proc_2(stack
s,
int
e)
是删除栈s中元素值为e的元素.第一个while循环里将s中的非e元素值压入新栈中..例如s中有1,2,3,1,4
如果e位1,则新栈t为2,3,4(此时由于s的出栈,则s栈已经清空了)第二个while循环里,将t中元素压回s中
void
proc_3(queue
*q)是利用栈将队列q倒序
例如q中有元素1,2,3,4,...,n
(其中n为队头)则将q清空,压入栈中,此时临时栈s从栈底到栈顶为n,...,4,3,2,1然后再将s弹出到q队列里,则队列元素为n,..,4,3,2,1(其中n为队头),也就是用了队列的先进先出与栈的后进先出这个特性吧.