線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)？

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

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

(bottom)。不含任何元素的棧稱為空棧。只允許在棧頂進(jìn)行插入和刪除，所以棧的操作是按“后進(jìn)先出”（LastInFirstOut）的原則進(jìn)行的。棧底(bottom)棧頂(top)棧的實例2：彈夾棧頂(top)裝彈、出彈285top（棧頂）用數(shù)組模擬棧的“后進(jìn)先出”加入一個數(shù)7取出棧頂元素再取出棧頂元素9bottom（棧底,值為0）數(shù)組（棧）123456下標(biāo)棧為空的條件是：top==bottomtop始終指向棧頂一般情況下，top的值就表示了棧中的元素個數(shù)//插入（壓棧）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;4321使用棧進(jìn)行算術(shù)表達(dá)式求值表達(dá)式：3×(5–2)+7@數(shù)字運(yùn)算符3×(5–23+975–2=33×3=97+9=16結(jié)果便是16！16棧的實例2：混合運(yùn)算棧的實例3：火車調(diào)度(NKOJ1914)

某城市有一個火車站，如下圖所示，現(xiàn)有n（n<=10000）節(jié)火車車廂，順序編號為1,2,3,...,n，按編號連續(xù)依次從A方向的鐵軌駛?cè)胲囌?，從B方向鐵軌駛出。一旦車廂進(jìn)入車站就不能再回到A方向的鐵軌上；在車站的門口有工人可以將車廂拖出車站，工人一次只能拖一節(jié)車廂，并且只能將車廂拖入B方向的鐵軌。一旦車廂出了車站就不能再回到車站。車站一開始為空，最多能停放10000節(jié)車廂。為了方便裝貨，調(diào)度員需要將車廂從新排列，問能否將車廂編號排列成A1,A2,......,An。也就是使車廂從B方向駛出的編號是A1,A2,......,An。如果能輸出"yes"，否則輸出"no"。輸入格式：第一行，一個整數(shù)n第二行，n個用空格間隔的整數(shù)，表示出站時車廂編號要排列成的順序A1,A2,......,An輸出格式：一行，一個單詞"yes"或者"no"樣例輸入1：532541樣例輸出1:yes樣例輸入2：531542樣例輸出2:no車站AB駛?cè)腭偝鲫犃嘘犃校╭ueue）是另一種特殊的線性表，它的特點是刪除操作在一頭進(jìn)行，插入操作在另一頭進(jìn)行。允許刪除的一端稱為隊首（head）,允許插入的一端稱為隊尾(tail)。不含任何元素的隊稱為空隊。隊列的修改是按先進(jìn)先出(FirstInFirstOut)的原則進(jìn)行隊首（head）隊尾（tail）隊列的代碼實現(xiàn)#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++;

}}試題（初賽）設(shè)棧S和隊列Q初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若出隊的順序為e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該為().

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

例：紙牌游戲（NKOJ1917）

桌上有一疊紙牌，共n張牌。從位于頂端的紙牌開始從上往下依次編號為1到n。現(xiàn)在反復(fù)進(jìn)行以下操作：把位于頂端的牌扔到，然后把新的位于頂端的牌放到整疊牌的底部。直到只剩下一張牌。輸入n(<=100)，輸出每次扔掉的牌的編號以及最后剩下的牌的編號。樣例輸入：7樣例輸出：1357426intq[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)

//如果隊列不為空{(diào)

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

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

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

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

鏈表甲乙丙丁戊左：無右：甲左：丙右：戊左：甲右：乙左：戊右：丁左：乙右：無

鏈表（list），由多個結(jié)點連接而成的鏈狀結(jié)構(gòu)。每個結(jié)點包含兩部分，數(shù)值和存放結(jié)點間的相互關(guān)系

右圖中，每個人看做一個節(jié)點，數(shù)值就是每個人自己的名字。同時記錄下左邊是誰，右邊是誰，這就是節(jié)點間的關(guān)系。在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鏈表的代碼實現(xiàn)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的結(jié)點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的結(jié)點的編號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;

};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號節(jié)點leftleftrightrightrightleftxy課后練習(xí)：1085#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棧不為空則執(zhí)行BACK命令

{

fTop++;fwd[fTop]=now;

//把當(dāng)前顯示的網(wǎng)頁加入forword棧棧頂

now=bak[bTop];bTop--;

//彈出back棧棧頂網(wǎng)頁作為當(dāng)前要顯示的網(wǎng)頁

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

//用戶新輸入了一個網(wǎng)址

{

bTop++;bak[bTop]=now;

//把當(dāng)前網(wǎng)頁壓入到back棧中

now=cmd;

//now為當(dāng)前要顯示的網(wǎng)頁

now.erase(0,6);

//去掉命令前的"VISIT"

fTop=0;

//清空forward棧

cout<<now<<endl;

}

getline(cin,cmd);

}

return0;}鏈表的實現(xiàn)一般采用結(jié)構(gòu)體struct類型輸入n(<=100)個學(xué)生，每個學(xué)生有姓名，性別，語文數(shù)