隊列演算法
『壹』 數據結構 隊列
作業
第一章
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為隊頭),也就是用了隊列的先進先出與棧的後進先出這個特性吧.