線性結構數據結構線性結構數據結構什么是數據結構？

數據結構(DataStructure),用于描述計算機中數據的存儲、組織形式。合理的數據結構可以給程序帶來更高的存儲和運行效率。常用的數據結構有哪些？1.線性結構2.樹型結構3.圖型結構棧、隊列、鏈表什么是數據結構？數據結構(DataStruct棧

棧(stack)是一種特殊的線性結構，它只能在一端進行插入和刪除操作。能插入和刪除的一端棧頂（top），另一端稱為棧底

(bottom)。不含任何元素的棧稱為空棧。只允許在棧頂進行插入和刪除，所以棧的操作是按“后進先出”（LastInFirstOut）的原則進行的。棧底(bottom)棧頂(top)棧棧(stack)是一種特殊的線性結構，它只棧的實例1：漢諾塔棧的實例1：漢諾塔棧的實例2：彈夾棧頂(top)裝彈、出彈棧的實例2：彈夾棧頂(top)裝彈、出彈285top（棧頂）用數組模擬棧的“后進先出”加入一個數7取出棧頂元素再取出棧頂元素9bottom（棧底,值為0）數組（棧）123456下標棧為空的條件是：top==bottomtop始終指向棧頂一般情況下，top的值就表示了棧中的元素個數285top（棧頂）用數組模擬棧的“后進先出”加入一個數7取//插入（壓棧）voidpush(charx){

if(top==maxn)cout<<"full";else

{

top++;stack[top]=x;

}}//刪除(彈棧)void

pop(){

if(top==0)

cout<<"empty";

else

{

cout<<stack[top];

top--;

}}constintmaxn=1000char

stack[maxn+1];inttop=0;4321constintmaxn=10004使用棧進行算術表達式求值表達式：3×(5–2)+7@數字運算符3×(5–23+975–2=33×3=97+9=16結果便是16！16棧的實例2：混合運算使用棧進行算術表達式求值表達式：3×(5–2)考題（初賽）

若S是一個大小為4的棧，若元素1，2，3，4，5，6，7按順序依次進棧，則這7個元素的出棧順序可能為（）

A.1,2,3,4,5,6,7B.1,4,3,5,7,2,6C.1,3,2,4,7,5,6D.2,3,7,6,5,4,1

考題（初賽）若S是一個大小為4的棧，若元素1，2，3，4棧的實例3：火車調度(NKOJ1914)

某城市有一個火車站，如下圖所示，現有n（n<=10000）節火車車廂，順序編號為1,2,3,...,n，按編號連續依次從A方向的鐵軌駛入車站，從B方向鐵軌駛出。一旦車廂進入車站就不能再回到A方向的鐵軌上；在車站的門口有工人可以將車廂拖出車站，工人一次只能拖一節車廂，并且只能將車廂拖入B方向的鐵軌。一旦車廂出了車站就不能再回到車站。車站一開始為空，最多能停放10000節車廂。為了方便裝貨，調度員需要將車廂從新排列，問能否將車廂編號排列成A1,A2,......,An。也就是使車廂從B方向駛出的編號是A1,A2,......,An。如果能輸出"yes"，否則輸出"no"。輸入格式：第一行，一個整數n第二行，n個用空格間隔的整數，表示出站時車廂編號要排列成的順序A1,A2,......,An輸出格式：一行，一個單詞"yes"或者"no"樣例輸入1：532541樣例輸出1:yes樣例輸入2：531542樣例輸出2:no車站AB駛入駛出棧的實例3：火車調度(NKOJ1914)某城//將題目要求的出站序列讀入a數組，然后通過棧從左到右依次去匹配a數組#include<iostream>#include<cstdio>usingnamespacestd;ints[10001],a[10001],n,i,j,top=0;//s數組用于模擬棧intmain(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);i=j=1;while(i<=n)//依次討論火車進站的編號1到n{//將第i輛車入站(棧)，把編號存入棧頂top++;s[top]=i;//while討論如果棧頂的編號與當前要匹配的a的編號相同，則表示可以出站while((s[top]==a[j])&&(top>0)){top--;j++;}i++;//討論下一輛車}

//如果棧不為空，表示有編號無法匹配if(top==0)printf("yes\n");elseprintf("no\n");return0;}//將題目要求的出站序列讀入a數組，然后通過棧從左到右依次去隊列隊列（queue）是另一種特殊的線性表，它的特點是刪除操作在一頭進行，插入操作在另一頭進行。允許刪除的一端稱為隊首（head）,允許插入的一端稱為隊尾(tail)。不含任何元素的隊稱為空隊。隊列的修改是按先進先出(FirstInFirstOut)的原則進行隊首（head）隊尾（tail）隊列隊列（queue）是另一種特殊的線性表，它的特點是用數組模擬隊列的“先進先出”C12345678數組（隊列）數組下標head(隊首)tail(隊尾)FXM1.插入數據：2.插入數據：3.插入數據：4.刪除數據4.刪除數據5.插入數據：當head==tail時表示隊列為空head指向隊首tail指向下一個空位在隊首進行刪除在隊尾進行插入用數組模擬隊列的“先進先出”C12345678數組（隊列）數隊列的代碼實現#definemaxn101charqueue[maxn];inthead,tail;//入隊（插入元素）voidinsert(charx){

if(tail>maxn)

cout<<"full";

else

{queue[tail]=x;

tail++;

}}//出隊(刪除元素)voiddel(){

if(tail==head)

cout<<"empty";

else

{

cout<<queue[head];

head++;

}}隊列的代碼實現#definemaxn101//入隊（插入試題（初賽）設棧S和隊列Q初始狀態為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q,若出隊的順序為e2,e4,e3,e6,e5,e1,則棧S的容量至少應該為().

A)2B)3C)4D)5

試題（初賽）設棧S和隊列Q初始狀態為空,元素e1,e2例：紙牌游戲（NKOJ1917）

桌上有一疊紙牌，共n張牌。從位于頂端的紙牌開始從上往下依次編號為1到n。現在反復進行以下操作：把位于頂端的牌扔到，然后把新的位于頂端的牌放到整疊牌的底部。直到只剩下一張牌。輸入n(<=100)，輸出每次扔掉的牌的編號以及最后剩下的牌的編號。樣例輸入：7樣例輸出：1357426例：紙牌游戲（NKOJ1917）桌上有一疊紙牌，共nintq[201],head,tail,i,n;intmain(){

cin>>n;for(i=1;i<=n;i++)q[i]=i;//隊列賦初值

head=1;//隊首指針指向位于頂端的牌的位置tail=n+1;//對尾指針指向下一個空位

while(head<tail)

//如果隊列不為空{

printf("%d",q[head]);//輸出隊首，即扔到最頂端的牌head++

//隊首指針指向新的位于頂端的牌

q[tail]=q[head];//將位于最頂端的牌移到隊尾tail++;

//對尾指針指向下一個可用空位head++;//隊首指針指向新的位于頂端的牌}return0;}

intq[201],head,tail,i,n;鏈表甲乙丙丁戊左：無右：甲左：丙右：戊左：甲右：乙左：戊右：丁左：乙右：無

鏈表（list），由多個結點連接而成的鏈狀結構。每個結點包含兩部分，數值和存放結點間的相互關系

右圖中，每個人看做一個節點，數值就是每個人自己的名字。同時記錄下左邊是誰，右邊是誰，這就是節點間的關系。鏈表甲乙丙丁戊左：無左：丙左：甲左：戊左：乙鏈表（061423152380

鏈表（list），由多個結點連接而成的鏈狀結構。每個結點包含兩部分，數值和存放結點間的相互關系。編號1編號2編號3編號4雙向鏈表：12113315222

0編號1編號2編號3編號4單向鏈表：061423152380鏈表（list），由多個結點連左A右DBC在1和2間插入4號點D1.讓4的左手牽2的左手牽的對象

list[4].left=list[2].left;2.讓4的右手牽1的右手牽的對象

list[4].right=list[1].right3.讓1的右手放開2，然后牽4

list[1].right=4;4.讓2的左手放開1，然后牽4

list[2].left=4;刪除B1.讓4的右手牽2的右手牽的對象

list[4].right=list[2].right;2.讓3的左手牽2的左手牽的對象

list[3].left=list[2].left;3.讓2的右手放開

list[2].right=0;4.讓2的左手放開

list[2].left=0;structnode{

charname;

intleft,right;

};nodelist[10];123list[1].right=2;list[1].left=0;list[2].right=3;list[2].left=1;list[3].right=0;list[3].left=2;4head左A右DBC在1和2間插入4號點D1.讓4的左手牽2的左手牽鏈表的代碼實現nodelist[100];//把編號x的元素插到p號點之后voidinsert(intp,intx){

list[x].right=list[p].right;

list[x].left=p;

list[list[p].right].left=x;

list[p].right=x;}//刪除編號為x的結點void

del(intx){intp,q;if(head==x)head=list[x].left;

p=list[x].left;q=list[x].right;list[p].right=list[x].right;list[q].left=list[x].left;list[x].left=0;list[x].right=0;}//查找鏈表中的名為helang的結點的編號voidsearchList(strings){intp;p=head;

while((p!=0)&&(list[p].name!="helang"))p=list[p].right;

if(list[p].name=="helang")

cout<<p;

else

cout<<"notfound";}structnode{

charname;

intleft,right;

};鏈表的代碼實現nodelist[100];//把編號x的17世紀的法國數學家加斯帕在《數目的游戲問題》中講了這樣一個故事：25個基督教徒和25個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：50個人圍坐成一圓圈，從第一個人開始順時針依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余25個人為止。問怎樣排座位，才能使每次投入大海的都是非教徒。17世紀的法國數學家加斯帕在《數目的游戲問題》structpeople{//right為上一個人的編號intleft,right;//left為下一個人的編號booldead;//如果dead為true表示要被扔下海};peopleren[51];inti,n,p,x,y;intmain(){for(i=1;i<=50;i++){ren[i].left=i+1;ren[i].right=i-1;ren[i].dead=false;}ren[1].right=50;ren[50].left=1;n=50;p=50;while(n>25){for(i=1;i<=9;i++)p=ren[p].left;x=ren[p].right;y=ren[p].left;ren[x].left=y;ren[y].right=x;ren[p].dead=true;n--;}for(i=1;i<=50;i++)if(ren[i].dead==false)cout<<i<<"";cout<<endl;return0;}123要刪除2號節點leftleftrightrightrightleftxystructpeople123要刪除2號節點leftlef課后練習：1085課后練習：1085網頁瀏覽NKOJ1085網頁瀏覽器都包含有前進和后退功能，以此來快速打開之前你訪問過的網頁。你的任務就是實現這個功能。實現此功能的常用方法是通過forword和back兩個棧來保存前進和后退時要打開的網頁。下列命令是你需要實現的：BACK:把當前顯示的網頁壓入到forword棧中。然后把back棧棧頂的網頁彈出作為當前顯示的網頁。如果back棧為空，那么這條命令就不執行。FORWARD:把當前顯示的網頁壓入到back棧中。然后把forward棧棧頂的網頁彈出作為當前顯示的網頁。如果forward棧為空，那么這條命令就不執行。VISIT:把當前顯示的網頁壓入到back棧中。然后瀏覽器顯示用戶新輸入的網址對應的網頁。清空forward棧QUIT:關閉瀏覽器假設只要瀏覽器一打開就會自動打開網頁/輸入格式：包含若干條命令，這些命令由BACK,FORWARD,VISIT和QUIT構成。每條命令占一行，長度不超過70。命令的總條數不超過100。一旦出現QUIT表示結束輸入命令。輸出格式：對于每個命令，如果它不是QUIT，那么輸出命令執行后瀏覽器顯示的網頁。如果該命令無法執行，則輸出"Ignored",除QUIT命令外，每一個輸入命令對應一行輸出結果。樣例輸入VISIT/VISIT/acmicpc/BACKBACKBACKFORWARDVISIT/BACKBACKFORWARDFORWARDFORWARDQUIT樣例輸出//acmicpc///Ignored//////Ignored何老板傾情翻譯網頁瀏覽NKOJ1085網頁瀏覽器都包含有前#definemaxn101stringfwd[maxn],bak[maxn],now,cmd;intfTop=0,bTop=0;intmain(){now="/";//打開瀏覽器會自動登錄到getline(cin,cmd);//輸入的命令中可能包含空格，所以用getline()讀入while(cmd!="QUIT"){if(cmd=="BACK"){if(bTop!=0)//back棧不為空則執行BACK命令{fTop++;fwd[fTop]=now;//把當前顯示的網頁加入forword棧棧頂now=bak[bTop];bTop--;//彈出back棧棧頂網頁作為當前要顯示的網頁cout<<now<<endl;}elsecout<<"Ignored"<<endl;}elseif(cmd=="FORWARD"){if(fTop!=0){bTop++;bak[bTop]=now;now=fwd[fTop];fTop--;cout<<now<<endl;}elsecout<<"Ignored"<<endl;}else//用戶新輸入了一個網址{bTop++;bak[bTop]=now;//把當前網頁壓入到back棧中now=cmd;//now為當前要顯示的網頁now.erase(0,6);//去掉命令前的"VISIT"fTop=0;//清空forward棧cout<<now<<endl;}getline(cin,cmd);}return0;}#definemaxn101鏈表的實現一般采用結構體struct類型輸入n(<=100)個學生，每個學生有姓名，性別，語文數學成績，請按語文數學成績總分的由高到低順序打印出每個學生的信息。樣例輸入:3tomf9988jimm67.577.5alexm85.590樣例輸出：tomf9988alexm85.590jimm67.577.5stringname[101];charxb[101];floatmath[101],chinese[101];for(i=1;i<=n;i++)cin>>name[i]>>xb[i]>math[i]>chinese[i];......structchid{stringname;charxb;floatmath,chinese;};childstudent[101];for(i=1;i<=n;i++)cin>>student[i].name>>student[i].xb>>student[i].math>>student[i].chinese;一個結構體是可以包含多種不同的數據類型。它是用戶根據需要自己定義的數據類型。用.去訪問結構體中的不同數據。結構體類型的數據可之間當成變量使用。比如：childx,y;x.[name]="helang";x.xb='m';x.math=100;x.chinese=100;y=x;x.xb='f';x.math=150;cout<<y.math<<x.xb<<x.math<<endl;鏈表的實現一般采用結構體struct類型輸入n(<=100循環隊列處理轉圈：

head=(head-1)%n+1;tail=(tail-1)%n+1;循環隊列處理轉圈：

head=(head-1)%n+1;人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋。”通過閱讀科技書籍，我們能豐富知識，培養邏輯思維能力；通過閱讀文學作品，我們能提高文學鑒賞水平，培養文學情趣；通過閱讀報刊，我們能增長見識，擴大自己的知識面。有許多書籍還能培養我們的道德情操，給我們巨大的精神力量，鼓舞我們前進。人有了知識，就會具備各種分析能力，數據結構之線性結構講義課件線性結構數據結構線性結構數據結構什么是數據結構？

數據結構(DataStructure),用于描述計算機中數據的存儲、組織形式。合理的數據結構可以給程序帶來更高的存儲和運行效率。常用的數據結構有哪些？1.線性結構2.樹型結構3.圖型結構棧、隊列、鏈表什么是數據結構？數據結構(DataStruct棧

棧(stack)是一種特殊的線性結構，它只能在一端進行插入和刪除操作。能插入和刪除的一端棧頂（top），另一端稱為棧底

(bottom)。不含任何元素的棧稱為空棧。只允許在棧頂進行插入和刪除，所以棧的操作是按“后進先出”（LastInFirstOut）的原則進行的。棧底(bottom)棧頂(top)棧棧(stack)是一種特殊的線性結構，它只棧的實例1：漢諾塔棧的實例1：漢諾塔棧的實例2：彈夾棧頂(top)裝彈、出彈棧的實例2：彈夾棧頂(top)裝彈、出彈285top（棧頂）用數組模擬棧的“后進先出”加入一個數7取出棧頂元素再取出棧頂元素9bottom（棧底,值為0）數組（棧）123456下標棧為空的條件是：top==bottomtop始終指向棧頂一般情況下，top的值就表示了棧中的元素個數285top（棧頂）用數組模擬棧的“后進先出”加入一個數7取//插入（壓棧）voidpush(charx){

if(top==maxn)cout<<"full";else

{

top++;stack[top]=x;

}}//刪除(彈棧)void

pop(){

if(top==0)

cout<<"empty";

else

{

cout<<stack[top];

top--;

}}constintmaxn=1000char

stack[maxn+1];inttop=0;4321constintmaxn=10004使用棧進行算術表達式求值表達式：3×(5–2)+7@數字運算符3×(5–23+975–2=33×3=97+9=16結果便是16！16棧的實例2：混合運算使用棧進行算術表達式求值表達式：3×(5–2)考題（初賽）

若S是一個大小為4的棧，若元素1，2，3，4，5，6，7按順序依次進棧，則這7個元素的出棧順序可能為（）

A.1,2,3,4,5,6,7B.1,4,3,5,7,2,6C.1,3,2,4,7,5,6D.2,3,7,6,5,4,1

考題（初賽）若S是一個大小為4的棧，若元素1，2，3，4棧的實例3：火車調度(NKOJ1914)

某城市有一個火車站，如下圖所示，現有n（n<=10000）節火車車廂，順序編號為1,2,3,...,n，按編號連續依次從A方向的鐵軌駛入車站，從B方向鐵軌駛出。一旦車廂進入車站就不能再回到A方向的鐵軌上；在車站的門口有工人可以將車廂拖出車站，工人一次只能拖一節車廂，并且只能將車廂拖入B方向的鐵軌。一旦車廂出了車站就不能再回到車站。車站一開始為空，最多能停放10000節車廂。為了方便裝貨，調度員需要將車廂從新排列，問能否將車廂編號排列成A1,A2,......,An。也就是使車廂從B方向駛出的編號是A1,A2,......,An。如果能輸出"yes"，否則輸出"no"。輸入格式：第一行，一個整數n第二行，n個用空格間隔的整數，表示出站時車廂編號要排列成的順序A1,A2,......,An輸出格式：一行，一個單詞"yes"或者"no"樣例輸入1：532541樣例輸出1:yes樣例輸入2：531542樣例輸出2:no車站AB駛入駛出棧的實例3：火車調度(NKOJ1914)某城//將題目要求的出站序列讀入a數組，然后通過棧從左到右依次去匹配a數組#include<iostream>#include<cstdio>usingnamespacestd;ints[10001],a[10001],n,i,j,top=0;//s數組用于模擬棧intmain(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);i=j=1;while(i<=n)//依次討論火車進站的編號1到n{//將第i輛車入站(棧)，把編號存入棧頂top++;s[top]=i;//while討論如果棧頂的編號與當前要匹配的a的編號相同，則表示可以出站while((s[top]==a[j])&&(top>0)){top--;j++;}i++;//討論下一輛車}

//如果棧不為空，表示有編號無法匹配if(top==0)printf("yes\n");elseprintf("no\n");return0;}//將題目要求的出站序列讀入a數組，然后通過棧從左到右依次去隊列隊列（queue）是另一種特殊的線性表，它的特點是刪除操作在一頭進行，插入操作在另一頭進行。允許刪除的一端稱為隊首（head）,允許插入的一端稱為隊尾(tail)。不含任何元素的隊稱為空隊。隊列的修改是按先進先出(FirstInFirstOut)的原則進行隊首（head）隊尾（tail）隊列隊列（queue）是另一種特殊的線性表，它的特點是用數組模擬隊列的“先進先出”C12345678數組（隊列）數組下標head(隊首)tail(隊尾)FXM1.插入數據：2.插入數據：3.插入數據：4.刪除數據4.刪除數據5.插入數據：當head==tail時表示隊列為空head指向隊首tail指向下一個空位在隊首進行刪除在隊尾進行插入用數組模擬隊列的“先進先出”C12345678數組（隊列）數隊列的代碼實現#definemaxn101charqueue[maxn];inthead,tail;//入隊（插入元素）voidinsert(charx){

if(tail>maxn)

cout<<"full";

else

{queue[tail]=x;

tail++;

}}//出隊(刪除元素)voiddel(){

if(tail==head)

cout<<"empty";

else

{

cout<<queue[head];

head++;

}}隊列的代碼實現#definemaxn101//入隊（插入試題（初賽）設棧S和隊列Q初始狀態為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q,若出隊的順序為e2,e4,e3,e6,e5,e1,則棧S的容量至少應該為().

A)2B)3C)4D)5

試題（初賽）設棧S和隊列Q初始狀態為空,元素e1,e2例：紙牌游戲（NKOJ1917）

桌上有一疊紙牌，共n張牌。從位于頂端的紙牌開始從上往下依次編號為1到n。現在反復進行以下操作：把位于頂端的牌扔到，然后把新的位于頂端的牌放到整疊牌的底部。直到只剩下一張牌。輸入n(<=100)，輸出每次扔掉的牌的編號以及最后剩下的牌的編號。樣例輸入：7樣例輸出：1357426例：紙牌游戲（NKOJ1917）桌上有一疊紙牌，共nintq[201],head,tail,i,n;intmain(){

cin>>n;for(i=1;i<=n;i++)q[i]=i;//隊列賦初值

head=1;//隊首指針指向位于頂端的牌的位置tail=n+1;//對尾指針指向下一個空位

while(head<tail)

//如果隊列不為空{

printf("%d",q[head]);//輸出隊首，即扔到最頂端的牌head++

//隊首指針指向新的位于頂端的牌

q[tail]=q[head];//將位于最頂端的牌移到隊尾tail++;

//對尾指針指向下一個可用空位head++;//隊首指針指向新的位于頂端的牌}return0;}

intq[201],head,tail,i,n;鏈表甲乙丙丁戊左：無右：甲左：丙右：戊左：甲右：乙左：戊右：丁左：乙右：無

鏈表（list），由多個結點連接而成的鏈狀結構。每個結點包含兩部分，數值和存放結點間的相互關系

右圖中，每個人看做一個節點，數值就是每個人自己的名字。同時記錄下左邊是誰，右邊是誰，這就是節點間的關系。鏈表甲乙丙丁戊左：無左：丙左：甲左：戊左：乙鏈表（061423152380

鏈表（list），由多個結點連接而成的鏈狀結構。每個結點包含兩部分，數值和存放結點間的相互關系。編號1編號2編號3編號4雙向鏈表：12113315222

0編號1編號2編號3編號4單向鏈表：061423152380鏈表（list），由多個結點連左A右DBC在1和2間插入4號點D1.讓4的左手牽2的左手牽的對象

list[4].left=list[2].left;2.讓4的右手牽1的右手牽的對象

list[4].right=list[1].right3.讓1的右手放開2，然后牽4

list[1].right=4;4.讓2的左手放開1，然后牽4

list[2].left=4;刪除B1.讓4的右手牽2的右手牽的對象

list[4].right=list[2].right;2.讓3的左手牽2的左手牽的對象

list[3].left=list[2].left;3.讓2的右手放開

list[2].right=0;4.讓2的左手放開

list[2].left=0;structnode{

charname;

intleft,right;

};nodelist[10];123list[1].right=2;list[1].left=0;list[2].right=3;list[2].left=1;list[3].right=0;list[3].left=2;4head左A右DBC在1和2間插入4號點D1.讓4的左手牽2的左手牽鏈表的代碼實現nodelist[100];//把編號x的元素插到p號點之后voidinsert(intp,intx){

list[x].right=list[p].right;

list[x].left=p;

list[list[p].right].left=x;

list[p].right=x;}//刪除編號為x的結點void

del(intx){intp,q;if(head==x)head=list[x].left;

p=list[x].left;q=list[x].right;list[p].right=list[x].right;list[q].left=list[x].left;list[x].left=0;list[x].right=0;}//查找鏈表中的名為helang的結點的編號voidsearchList(strings){intp;p=head;

while((p!=0)&&(list[p].name!="helang"))p=list[p].right;

if(list[p].name=="helang")

cout<<p;

else

cout<<"notfound";}structnode{

charname;

intleft,right;

};鏈表的代碼實現nodelist[100];//把編號x的17世紀的法國數學家加斯帕在《數目的游戲問題》中講了這樣一個故事：25個基督教徒和25個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：50個人圍坐成一圓圈，從第一個人開始順時針依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余25個人為止。問怎樣排座位，才能使每次投入大海的都是非教徒。17世紀的法國數學家加斯帕在《數目的游戲問題》structpeople{//right為上一個人的編號intleft,right;//left為下一個人的編號booldead;//如果dead為true表示要被扔下海};peopleren[51];inti,n,p,x,y;intmain(){for(i=1;i<=50;i++){ren[i].left=i+1;ren[i].right=i-1;ren[i].dead=false;}ren[1].right=50;ren[50].left=1;n=50;p=50;while(n>25){for(i=1;i<=9;i++)p=ren[p].left;x=ren[p].right;y=ren[p].left;ren[x].left=y;ren[y].right=x;ren[p].dead=true;n--;}for(i=1;i<=50;i++)if(ren[i].dead==false)cout<<i<<"";cout<<endl;return0;}123要刪除2號節點leftleftrightrightrightleftxystructpeople123要刪除2號節點leftlef課后練習：1085課后練習：1085網頁瀏覽NKOJ1085網頁瀏覽器都包含有前進和后退功能，以此來快速打開之前你訪問過的網頁。你的任務就是實現這個功能。實現此功能的常用方法是通過forword和back兩個棧來保存前進和后退時要打開的網頁。下列命令是你需要實現的：BACK:把當前顯示的網頁壓入到forword棧中。然后把back棧棧頂的網頁彈出作為當前顯示的網頁。如果back棧為空，那么這條命令就不執行。FORWARD:把當前顯示的網頁壓入到back棧中。然后把forward棧棧頂的網頁彈出作為當前顯示的網頁。如果forward棧為空，那么這條命令就不執行。VISIT:把當前顯示的網頁壓入到back棧中。然后瀏覽器顯示用戶新輸入的網址對應的網頁。清空forward棧QUIT:關閉瀏覽器假設只要瀏覽器一打開就會自動打開網頁/輸入格式：包含若干條命令，這些命令由BACK,FORWARD,VISIT和QUIT構成。每條命令占一行，長度不超過70。命令的總條數不超過100。一旦出現QUIT表示結束輸入命令。輸出格式：對于每個命令，如果它不是QUIT，那么輸出命令執行后瀏覽器顯示的網頁。如果該命令無法執行，則輸出"Ignored",除QUIT命令外，每一個輸入命令對應一行輸出結果。樣例輸入VISIT/VISIT/acmicpc/BACKBACKBACKFORWARDVISIT/BACKBACKFORWARDFORWARDFORWARDQUIT樣例輸出//acmicpc///Ignored//////Ignored何老板傾情翻譯網頁瀏覽NKOJ1085網頁瀏覽器都包含有前#definemaxn101stringfwd[maxn],bak[maxn],now,cmd;intfTop=0,bTop=0;intmain(){now="/";//打開瀏覽器會自動登錄到getline(cin,cmd);//輸入的命令中可能包含空格，所以用getline()讀入while(cmd!="QUIT"){if(cmd=="BACK"){if(bTop!=0)//back棧不為空則執行BACK命令{fTop++;fwd[fTop]=now;//把當前顯示的網頁加入forword棧棧頂