啊哈磊老師的《啊哈！演算法》學習記錄，
書中寫到了一個“解密QQ號”的栗子，大意是：“我們有一組資料，現在把第一個數洗掉，然后第二個數移動到這組資料的末尾，然后再把第三個數字洗掉，第四個數移動到這組資料的末尾，最后，我們把洗掉的資料連起來，就是我們想要的結果，”
這里便用到了佇列的知識：
佇列的本質是先進先出，先存入的資料先輸出，
思路：
先定義一個陣列，并初始化這個陣列，即 int book[101]= {0,6,3,1,7,5,8,9,2,4};（ 此處初始化可以多寫了一個 0，用來填充 book[0]，然后在book[1]開始會看起來更直觀，）
然后我們可以讓后面的元素向前面移動一位，達到覆寫第一個數的目的，引入兩個整型變數 head 和 tail，head 用來記錄我們佇列的隊首（即第一位），tail 用來記錄我們佇列的隊尾（即最后一位）的下一個位置，這是因為當佇列中只剩下一個元素時，隊首和隊尾 重合會帶來一些麻煩，我們這里規定隊首和隊尾重合時，佇列為空，
#include<stdio.h>
int main()
{
int book[101]={0,6,3,1,7,5,8,9,2,4},head,tail;
head=1;
tail=10;//指向隊尾的下一個位置
while(head<tail)//不為空的時候
{
printf("%d ",book[head]);
head++;
book[tail]=book[head];
tail++;
head++;
}
getchar();getchar();
return 0;
}
我們也可以封裝為一個結構體結構：
#include<stdio.h>
struct queue
{
int book[101];
int head;
int tail;
};
int main()
{
int i;
struct queue q;//定義一個結構的變數
q.head=1;//初始化佇列
q.tail=1;
for(i=1;i<=9;i++)//此處不再同上考慮 0
{
scanf("%d",&q.book[q.tail]); //&q.book[q.tail];
q.tail++;
}
while(q.head<q.tail)
{
printf("%d ",q.book[q.head]);//先把隊首輸出
q.head++;
q.book[q.tail]=q.book[q.head];//移動到最后一位
q.tail++;
q.head++;
}
getchar();getchar();
return 0;
}
對于我們的堆疊而言，正好與佇列相反，佇列是先進先出，而我們的堆疊是后進先出，
書上寫到了一個例子：
利用堆疊來判斷一個字串是不是回文數
我們先創建一個陣列，把這個字串存入到里面：
char book[101];
int len;
gets(book);
len=strlen(book);
然后，我們中間求出中間的點來：
mid=len/2 - 1;
我們把mid之前的數全部入堆疊：
for(i=0;i<=mid;i++)
{
array[++top]=book[i];
}
然后進行比較：
for(i=mid+1;i<=len-1;i++)
{
if(book[i]!=array[top])
{
break;
}
top--;
}
if(top==0)
{
printf("YES ");
}
else
printf("NO");
然后匯總到一起：
#include<stdio.h>
#include<string.h>
int main()
{
int i,len,mid,next,top;
char book[101],array[101];
gets(book);//gets()
len=strlen(book);
mid=len/2-1;//求中間
top=0;//堆疊的初始化
for(i=0;i<=mid;i++)
{
array[++top]=book[i]; //mid前面的字符依次入堆疊
}
if(len%2==0)//如果長度為偶數
{
next=mid+1;
}
else
{
next=mid+2;
}
for(i=next;i<=len-1;i++)//后面的半部分
{
if(book[i]!=array[top])
break;
top--;
}
if(top==0)
{
printf("yes");
}
else
{
printf("no");
}
getchar();getchar();
return 0;
}
書中舉了一個栗子，叫做 “小貓釣魚” ，題干是這樣的：
星期天小哼和小哈約在一起玩桌游，他們正在玩一個非常古怪的撲克游戲——“小貓釣魚”，游戲的規則是這樣的：將一副撲克牌平均分成兩份，每人拿一份，小哼先拿出手中的第一張撲克牌放在桌上，然后小哈也拿出手中的第一張撲克牌，并放在小哼剛打出的撲克牌的上面，就像這樣兩人交替出牌，出牌時，如果某人打出的牌與桌上某張牌的牌面相同，即可將兩張相同的牌及其中間所夾的牌全部取走，并依次放到自己手中牌的末尾，當任意一人
手中的牌全部出完時，游戲結束，對手獲勝，
假如游戲開始時，小哼手中有 6 張牌，順序為 2 4 1 2 5 6，小哈手中也有 6 張牌，順序為 3 1 3 5 6 4，最終誰會獲勝呢？現在你可以拿出紙牌來試一試，接下來請你寫一個程式來自動判斷誰將獲勝，這里我們做一個約定，小哼和小哈手中牌的牌面只有 1~9，
小哼的出牌和贏牌恰好對應佇列的兩個操作，出牌就是出隊，贏牌就是入隊，小哈的操作和小哼是一樣的，而桌子就是一個堆疊，每打出一張牌放到桌上就相當于入堆疊，當有人贏牌的時候，依次將牌從桌上拿走，這就相當于出堆疊，
贏牌的規則是：如果某人打出的牌與桌上的某張牌相同，即可將兩張牌以及中間所夾的牌全部取走，
那如何知道桌上已經有哪些牌了呢？
最簡單的方法就是列舉桌上的每一張牌，
也就是說現在需要佇列和堆疊，
//佇列
struct queue
{
int book[1000];
int head;
int tail;
};
//堆疊
struct stack
{
int book[10];//牌面1-9
int top;//top 堆疊頂
};
/*定義兩個佇列變數 q1 和 q2，q1 用來模擬小哼手中的牌，q2 用來模擬小
哈手中的牌，定義一個堆疊變數 s 用來模擬桌上的牌*/
struct queue q1,q2;
struct stack s;
將佇列和堆疊初始化
//初始化佇列q1和q2為空，此時兩人手中都還沒有牌
q1.head=1; q1.tail=1;
q2.head=1; q2.tail=1;
//初始化堆疊s為空，最開始的時候桌上也沒有牌
s.top=0;
分兩次讀取他們各自的牌，分兩次存入：
//先讀入6張牌，放到小哼手上
for(i=1;i<=6;i++)
{
scanf("%d",&q1.book[q1.tail]); //讀入一個數到隊尾
q1.tail++;//隊尾往后挪一位
}
//再讀入6張牌，放到小哈手上
for(i=1;i<=6;i++)
{
scanf("%d",&q2.book[q2.tail]); //讀入一個數到隊尾
q2.tail++;//隊尾往后挪一位
}
然后小哼先出牌：
t=q1.book[q1.head]; //小哼先亮出一張牌,把它存入到一個臨時變數里面，
然后列舉法判斷是否有一樣的：
flag=0;
for(i=1;i<=top;i++)
{
if(t==s[i]) { flag=1; break; }
}
//如果 flag 的值為 0 就表明小哼沒能贏得桌上的牌，將打出的牌留在桌上，
if(flag==0)
{
//小哼此輪沒有贏牌
q1.head++; //小哼已經打出一張牌，所以要把打出的牌出隊
s.top++;
s.book[s.top]=t; //再把打出的牌放到桌上，即入堆疊
}
//如果flag的值是1，就代表贏得了桌上的牌
if(flag==1)
{
//小哼此輪可以贏牌
q1.head++;//小哼已經打出一張牌，所以要把打出的牌出隊
q1.book[q1.tail]=t; //因為此輪可以贏牌，所以緊接著把剛才打出的牌又放到手中牌的末尾
q1.tail++;
while(s.book[s.top]!=t) //把桌上可以贏得的牌（從當前桌面最頂部一張牌開始取，直至取到與打出的牌相同為止）依次放到手中牌的末尾
{
q1.book[q1.tail]=s.book[s.top]; //依次放入隊尾
q1.tail++;
s.top--; //堆疊中少了一張牌，所以堆疊頂要減1
}
}
//判斷輸贏
if(q2.head==q2.tail)
{
printf("小哼贏了\n");
printf("小哼當前手中的牌是: ");
for(i=q1.head;i<=q1.tail-1;i++)
printf("%d ",q1.book[i]);
if(s.top>0) //如果桌上有牌則依次輸出桌上的牌
{
printf("\n桌上的牌是：");
for(i=1;i<=s.top;i++)
printf("%d ",s.book[i]);
}
else
printf("\n桌上已經沒有牌了");
}
}
小哈的仿寫即可，
上面對于桌面上的牌是一個個列舉，也可以存入到一個陣列里面，用一個陣列記錄有哪些牌，因為牌面只有 1~9，因此只需開一個大小為 10 的陣列來記錄當前桌上已經有哪些牌面就可以了，
可以先定義一個陣列，然后把它的每個元素初始為0，然后比如當打出一張牌面為5的牌時，那么我就在5對應的陣列位置加一，當這張牌被取出時，陣列里的數又回歸了0，類似于桶排序
t=q1.book[q1.head]; //小哼先亮出一張牌
if(shuzu[t]==0) // 表明桌上沒有牌面為t的牌
{
//小哼此輪沒有贏牌
q1.head++; //小哼已經打出一張牌，所以要把打出的牌出隊
s.top++;
s.book[s.top]=t; //再把打出的牌放到桌上，即入堆疊
shuzu[t]=1; //標記桌上現在已經有牌面為t的牌
}
總的代碼：
#include <stdio.h>
struct queue
{
int book[1000];
int head;
int tail;
};
struct stack
{
int book[10];
int top;
};
int main()
{
struct queue q1,q2;
struct stack s;
int shuzu[10];
int i,t;
//初始化佇列
q1.head=1; q1.tail=1;
q2.head=1; q2.tail=1;
//初始化堆疊
s.top=0;
//初始化用來標記的陣列，用來標記哪些牌已經在桌上
for(i=1;i<=9;i++)
shuzu[i]=0;
//依次向佇列插入6個數
//小哼手上的6張牌
for(i=1;i<=6;i++)
{
scanf("%d",&q1.book[q1.tail]);
q1.tail++;
}
//小哈手上的6張牌
for(i=1;i<=6;i++)
{
scanf("%d",&q2.book[q2.tail]);
q2.tail++;
}
while(q1.head<q1.tail && q2.head<q2.tail ) //當佇列不為空的時候執行回圈
{
t=q1.book[q1.head];//小哼出一張牌
//判斷小哼當前打出的牌是否能贏牌
if(shuzu[t]==0) //表明桌上沒有牌面為t的牌
{
//小哼此輪沒有贏牌
q1.head++; //小哼已經打出一張牌，所以要把打出的牌出隊
s.top++;
s.book[s.top]=t; //再把打出的牌放到桌上，即入堆疊
shuzu[t]=1; //標記桌上現在已經有牌面為t的牌
}
else
{
//小哼此輪可以贏牌
q1.head++;//小哼已經打出一張牌，所以要把打出的牌出隊
q1.book[q1.tail]=t;//緊接著把打出的牌放到手中牌的末尾
q1.tail++;
while(s.book[s.top]!=t) //把桌上可以贏得的牌依次放到手中牌的末尾
{
shuzu[s.book[s.top]]=0;//取消標記
q1.book[q1.tail]=s.book[s.top];//依次放入隊尾
q1.tail++;
s.top--; //堆疊中少了一張牌，所以堆疊頂要減1
}
}
t=q2.book[q2.head]; //小哈出一張牌
//判斷小哈當前打出的牌是否能贏牌
if(shuzu[t]==0) //表明桌上沒有牌面為t的牌
{
//小哈此輪沒有贏牌
q2.head++; //小哈已經打出一張牌，所以要把打出的牌出隊
s.top++;
s.book[s.top]=t; //再把打出的牌放到桌上，即入堆疊
shuzu[t]=1; //標記桌上現在已經有牌面為t的牌
}
else
{
//小哈此輪可以贏牌
q2.head++;//小哈已經打出一張牌，所以要把打出的牌出隊
q2.book[q2.tail]=t;//緊接著把打出的牌放到手中牌的末尾
q2.tail++;
while(s.book[s.top]!=t) //把桌上可以贏得的牌依次放到手中牌的末尾
{
shuzu[s.book[s.top]]=0;//取消標記
q2.book[q2.tail]=s.book[s.top];//依次放入隊尾
q2.tail++;
s.top--;
}
}
}
if(q2.head==q2.tail)
{
printf("小哼贏了\n");
printf("小哼當前手中的牌是：");
for(i=q1.head;i<=q1.tail-1;i++)
printf(" %d",q1.book[i]);
if(s.top>0) //如果桌上有牌則依次輸出桌上的牌
{
printf("\n桌上的牌是：");
for(i=1;i<=s.top;i++)
printf(" %d",s.book[i]);
}
else
printf("\n桌上已經沒有牌了");
}
else
{
printf("小哈贏了\n");
printf("小哈當前手中的牌是：");
for(i=q2.head;i<=q2.tail-1;i++)
printf(" %d",q2.book[i]);
if(s.top>0) //如果桌上有牌則依次輸出桌上的牌
{
printf("\n桌上的牌是：");
for(i=1;i<=s.top;i++)
printf(" %d",s.book[i]);
}
else
printf("\n桌上已經沒有牌了");
}
getchar();getchar();
return 0;
}
純手打，喜歡點贊，有問題可以在評論區留言，總代碼參考的書上的代碼，自己打了幾次有不少問題，明天再多打幾遍吧…
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296679.html
標籤：其他