數(shù)據(jù)結(jié)構(gòu)與算法基本程序目錄

線性表及其操作

1、尾插法建立一個(gè)單鏈表，并按順序輸出

2、單鏈表的元素查找，按內(nèi)容查找

3、元素插入操作

4、按內(nèi)容元素刪除操作

5、按位置刪除元素

6、建立雙向鏈表

7,單鏈表就地逆置

8、約瑟夫環(huán)問題

—?、棧及其操作

1、建立堆棧

2、進(jìn)棧與出棧

3、棧的應(yīng)用，括號匹配

,、隊(duì)及其操作

1、鏈隊(duì)列的建立

2、入隊(duì)和出隊(duì)

3、循環(huán)隊(duì)列建立

4、循環(huán)隊(duì)列的入隊(duì)和出隊(duì)操作

四、串及其操作

1、串的樸素匹配

五、樹(二叉樹)及其操作

1、二叉排序樹

2、哈夫曼編碼

六、排序

1、冒泡排序

2、直接選擇排序法

一、線性表及其操作

//Allcopyrightarepreservedbycobby

/*尾插法建立一個(gè)單鏈表，并按順序輸出*/

defineNULL0/*宏定義*/

typedefstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(

charc;/*數(shù)據(jù)域，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}*L;/*類型重定義，即Node和*L和structnode等

價(jià)*/

main()

(

L/木用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針木/

charch;

1=(L)mallocJsizeof(L));/*分配內(nèi)存空間*/

l->c=\0J;，*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

1->next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

q二l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用*/

printf(^Inputacharacter:\n，z);

scanf(〃％c〃，&ch);

getchar();〃此語句用來吸收鍵盤輸入的回車符，沒

有其它含義

while(ch!=，/)/*輸入!表示輸入結(jié)束x/

(

p=(L)malloc(sizeof(L));/*為新輸入的數(shù)據(jù)分配內(nèi)

存空間*/

p->c=ch;

p->next=NULL;/*新輸入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

q=p:/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf&ch);

getchar();

)

q=i;/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

printf(〃枇一>”,q->next->c):/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

)

}

//Allcopyrightarepreservedbycobby

/*單鏈表的元素查找，按內(nèi)容查找*/

^defineNULL0/*宏定義*/

typedefstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(

charc;/*數(shù)據(jù)域，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}*L;/*類型重定義，即Node和*L和structnode等

價(jià)*/

main()

(

L1,p,q；/*用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針*/

charch;

intn;

l=(L)mallocIsizeof(L));/*分配內(nèi)存空間*/

l->c八O';/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

l->next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

q=l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用*/

printf(z，Tnputacharacter:\n，z);

scanf&ch);

getchar();

while(ch!=，:')/*輸入!表示輸入結(jié)束x/

(

p=(L)malloc(sizeof(L));/*為新輸入的數(shù)據(jù)分配內(nèi)

存空間*/

p->c=cll;

p->next=NULL;/*新輸入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

q二p:/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf(*%c，z,&ch);

getchar();

)

q二l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->ncxt!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

printfC%c—>”,q->next->c):/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

/*-------以上為建立一個(gè)單鏈表-------------*/

printf("\nlnputacharacteryouwannafind\n，/);

scanf("%c〃，&ch);

printf(〃\nthecharacteryouwannafindis%c\n〃，ch);

q=l->next;/*q移至頭結(jié)點(diǎn)的后一個(gè)元素，即實(shí)際第

一個(gè)數(shù)據(jù)點(diǎn)*/

n=l;〃位置計(jì)數(shù)器

while(q!=NULL)/*若q不為空，即該結(jié)點(diǎn)存在*/

(

if(q->c=ch)/*字符匹配*/

printf(^characterfoundinposition%d\n〃，n);

q=q->next;/*移至下一個(gè)元素繼續(xù)查找*/

n++:

}

}

//Al1copyrightarepreservedbycobby

/*元素插入操作*/

^defineNULL0/*宏定義*/

t.ypedofstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(

charc;/*數(shù)據(jù)域，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}Node,*L;/*類型重定義，即Node和*L和struct

node等價(jià)*/

main()

(

Ll,p,q；/*用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針*/

charch;

intpos,n;

1=(L)mallocJsizeof(Node));/*分配內(nèi)存空間*/

\0';/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

l->next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

Q-l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用*/

printf("Inputacharacter:Xn^);

scanf(〃%c”,&ch);

gctchar();

while(ch!=，:')/*輸入!表示輸入結(jié)束X/

(

p=(L)malloc(sizeof(Node));/*為新輸入的數(shù)據(jù)分

配內(nèi)存空間*/

p->c=ch;

p->next=NULL;/*新愉入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

Q=P：/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf&ch);

getchar();

}

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

printfC%c->〃，q->next->c):/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

/*以上為建立一個(gè)單鏈表*/

printf("Inputthecharacteranditsposition,suchass,3\n\n");

scanf(，z%c,%d”,&ch,&pos);

q二l；

n=l;

while(n!=pos&&q->next!=NULL)/*未找到插入位置，

且后面還有元素承

(

q=q->next;

n++：

}

/*退出循環(huán)后，要么找到插入位置，要么表已到最后，輸入的插入位置

過大*/

if(n<pos)/*表已讀完，仍未找到插入位置*/

printf('AnXnincorrectposition,insertfailed\n\n");

else/*找到插入位置x/

/*將進(jìn)行插入操作*/

p=(L)malloc(sizeof(Node));/*給新輸入的數(shù)據(jù)分

配內(nèi)存空間*/

p->c=ch;

p->next=q->next;

q->next=p;

)

/*操作完成，然后輸出新表*/

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

{_

printf(，z%c-q->next->c);/*q->next->c表不q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

)

}

//Allcopyrightarepreservedbycobby

/*按內(nèi)容元素刪除操作*/

#include<malloc.h>

#include<stdio.h>

#defineNULL0/*宏定義*/

typedefstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(charc;/*數(shù)據(jù)域，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}Node,*L;/*類型重定義，即Node和*L和struct

node等價(jià)*/

main()

(

L1,p,q;/*用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針*/

charch;

intn;

1=(L)mal1oc；sizeof(Node));/*分配內(nèi)存空間*/

l->c^\0,;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

1一〉next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

q=l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用*/

printf("Inputacharacter:Xn^);

scanf("%c”,&ch);

getchar();

while(ch!=,)/*偷入!表示愉入結(jié)束x/

(

p=(L)malloc(sizeof(Node));/*為新輸入的數(shù)據(jù)分

配內(nèi)存空間*/

p->c=ch;

p->next=NULL;/*新輸入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

q=p：/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf(〃％c〃,&ch);

getchar();

}

qT;/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

(

printf(，z%c->〃，q->next->c);/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

/*以上為建立單鏈表*/

printf(,zinputthecharacteryouwannadcletc\n\n〃)；

scanf(〃%c〃,&ch);

z，，，

printf(theelementyouwannadeleteis%c\n\n,ch);

q=l->next;

P=l；

n=l;

while(q!=NULL&&q->c!=ch)

p=q;

q=q->next;

n++：

/*退出循環(huán)時(shí)可能找到指定元素，也可能表讀完，需要進(jìn)一步判斷*/

if(q==NULL)

printf(^elementnotfound,deletefailed\n\n，，);

else

p->next=q->next;

q=l->next;/*輸入整個(gè)鏈表前，先

將q移到鏈表頭，1一般不動(dòng)*/

while(q!=NULL)/*若q所指向的元素后面還有其它

元素，則將該元素的數(shù)據(jù)輸出*/

{_

printf(〃％c—q->c);/*q->ncxt->c表示q所指向

的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

}

)

//Allcopyrightarepreservedbycobby

/*按位置刪除元素*/

ttdefineNULL0/*宏定義*/

typedefstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(

charc;/*數(shù)據(jù)域，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}Node,*L;/*類型重定義，即Node和*L和struct

node等價(jià)*/

main()

(

Ll,p,q；/*用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針*/

charch;

intpos,n;

1=(L)mallocJsizeof(Node));/*分配內(nèi)存空間*/

l->c=\0J;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

l->next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

q=l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用木/

printf("Inputacharacter:Xn^);

scanf(〃%c”,&ch);

gctchar();

while(ch!=，:')/*輸入!表示輸入結(jié)束X/

(

p=(L)malloc(sizeof(Node));/*為新輸入的數(shù)據(jù)分

配內(nèi)存空間*/

p->c=ch;

p->next=NULL;/*新愉入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

Q=P：/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf&ch);

getchar();

}

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

printfC%c->〃，q->next->c):/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

/*以上為建立單鏈表*/

printf("Inputtheposition\n〃)；

scanf(〃%d〃,&pos);

P二l；

n=l;

while(p->next!=NULL&&n!=pos)

(

p=p->next;

n++:

)

/*退出循環(huán)后，可能找到刪除的元素位置，可能表讀完，需要進(jìn)一步判

斷*/

if(n-pos)/*刪除位置找到，刪除該位置上的元素*/

p->next=p->next->next;

//free(p);

)

else

printf(/zincorrectposition,deletefailed\n，/);

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

{_

printf(，z%c->〃，q->next->c);/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

)

)

//建立雙向鏈表

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

^defineNULL0

typedefstructdlnode

(

charch;

structdlnode*pri,*next;

}dnode,*dl;

main()

(

dl1,p,q；

charc;

l=(dl)malloc(sizeof(dnode)):

l->ch=\0,;

l->next=NULL;

l->pri=NULL:

q=l；

printf(〃輸入字符建立雙向鏈表\n〃);

scanf&c);

getchar();

while(c!=，!*)

(

p=(dl)malloc(sizcof(dnode)>;

p->ch=c;

p->pri=q;

p->next=NULL;

q->next=p;

q=P；

scanf&c);

getchar0;

)

q二l；

while(q->next!=NULL)

(

q=q->next;

printf(〃枇一>”,q->ch);

printf(〃\n〃)；

while(q->pri!=NULL)

(

printfC%c->〃,q->ch);

q=q->pri;

}

printf(〃\n〃)；

)

/單鏈表就地逆置

#defineNULL0/*宏定義*/

typedefstructnode/*定義結(jié)點(diǎn)類型的數(shù)據(jù)結(jié)構(gòu)*/

(

charc;/*數(shù)據(jù)域.，類型為字符型*/

structnode*next;/*指針域，類型為本結(jié)構(gòu)體類型*/

}Node,*L;/*類型重定義，即Node和*L和struct

node等價(jià)木/

main()

(

L1,p,q,r;/*用指針類型定義三個(gè)結(jié)點(diǎn)類型的指針

*/

charch;

1=(L)maHocJsizeof(Node));/*分配內(nèi)存空間*/

l->c=，\0*;/*為頭結(jié)點(diǎn)的數(shù)據(jù)域賦值，值為

空*/

l->next=NULL;/*指明下一個(gè)結(jié)點(diǎn)目前不存

在*/

q=l；/*q為游動(dòng)指針，鏈表結(jié)點(diǎn)的

連結(jié)要用*/

printf(，zInputacharacter:Xn^);

scanf(〃%c〃,&ch);

getchar();

while(ch!=，:')/*輸入!表示輸入結(jié)束x/

{

p=(L)malloc(sizeof(Node));/*為新輸入的數(shù)據(jù)分

配內(nèi)存空間*/

p->c=ch;

p->next=NULL;/*新輸入的結(jié)點(diǎn)在

鏈表的最后，即它的后面沒有其它元素*/

q->next=p;/*q用于將上一個(gè)元

素鏈接至當(dāng)前新元素*/

q=p；/*q自己移到當(dāng)前

最后一個(gè)元素，以備繼續(xù)鏈接所用*/

scanf&ch);

getchar();

)

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->ncxt!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

printf(,z%c-q->next->c):/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

printf(〃\n〃；；

〃以上完成了單鏈表的創(chuàng)建

q=l->next;

p=q->next;

r=p->next;

q->next=NULL;

while(r!=NULL)

(

p->next=q;

q=p;

p=r;

if(r->next!=NULL)//r后面還有結(jié)點(diǎn)，則逆置繼續(xù)

r=r->next;

else

break;

}

r->next=q;

l->next=r;〃頭結(jié)點(diǎn)由向最后一個(gè)結(jié)點(diǎn)

q=l；/*輸入整個(gè)鏈表前，先將q

移到鏈表頭，1一般不動(dòng)*/

while(q->next!=NULL)/*若q所指向的元素后面還

有其它元素，則將該元素的數(shù)據(jù)輸出*/

{_

printf(，z%c->〃，q->next->c);/*q->next->c表示q

所指向的下一個(gè)元素的數(shù)據(jù)*/

q=q->next;/*完成該元素的輸出

后，q移至下一個(gè)元素重復(fù)輸出操作*/

)

printf(〃\n〃);

)

//約瑟夫環(huán)問題

#include<stdio.h>

#include<malloc.h>

typedofstruct1node

(

intnum;

structInode*next;

}node,*L;

main()

(

intamount,start,circle,n,c;

Lp,1,q;

printf(〃一共有幾個(gè)人圍成一圈？\n〃);

scanf("%d〃,&amount);

getchar();

printf(〃從第幾個(gè)開始計(jì)數(shù)?\n〃)；

scanf(〃%d〃,&start);

getchar();

printf("每幾人一次循環(huán)？\n");

scanf(〃%d〃,&circle);

getchar();

1=(L)mallocisizeof(node));〃頭結(jié)點(diǎn)

l->next=NULL;

l->num=0;

q=l；

n=0;

while(n++<anount)

(

p=(L)malloc(sizeof(node));

p->ncxt=NULL;

p->num=n;

q->next=p;

q=p:

}

q->next=l->next：〃形成循環(huán)鏈表

〃以上完成了單向循環(huán)鏈表的建立

p=l->next;

q二1；

n=l;

while(n++<start)

(

p=p->next;

q=q->next;

}

〃退出循環(huán)時(shí)P,q分別位于指定位置

〃接下去進(jìn)行周期性結(jié)點(diǎn)刪除，直到鏈表只余一個(gè)結(jié)點(diǎn)為止

n=l;〃n計(jì)算被刪除的結(jié)點(diǎn)的數(shù)量，當(dāng)n=amountT

時(shí)刪除結(jié)束

while(n++<anount)

(

c=l://c作為循環(huán)臨時(shí)變量

while(c++<circle)

(

p=p->next;

q=q->next;

)

〃刪除當(dāng)前p指向的結(jié)點(diǎn)

printf(〃刪除結(jié)點(diǎn)用d\t〃，p->num);

q->next=p->next;

p=p->next;

printf("\n最后剩下%d\n",p->num);

)

二、棧及其操作

//Allcopyrightarepreservedbycobby

/*建立堆棧*/

#include<stdio.h>

#include<malloc.h>

^defineNULL0

typedefstructnode

(

charch;

structnode*next;

}Snode,*stack;

main()

{

stacks,top,p;

charch;

s二(stack)malloc(sizeof(Snode));

s->ch=，\0*;

s->next=NULL;/*建立棧底指針*/

top=s;

scanf(〃%c”,&ch);

getchar();

while(ch!二'1)

(

p=(stack)malloc(sizeof(Snode));

p->ch=ch;

p->next=top;

top二P；

scanf(，，%c/，,&ch);

getchar();

}

while(top->next!=NULL)

(

printf(z，%c->〃,top->ch);

top=top->next;

printf("\n〃)；

}

//Allcopyrightarepreservedbycobby

/*進(jìn)棧與出棧*/

#include<stdio.h>

#include<malloc.h>

^defineNULL0

typedcfstructnode

(

charch;

structnode*next;

}Snode,*stack;

main()

(

stacks,top,p;

charch;

intchoice;

s=(stack)ma'loc(sizeof(Snode));

s->ch='！'；

s->next=NULL;/*建立棧底指針*/

top=s;

scanf(〃%c”,&ch);

getchar();

while(ch!='：')

(

p=(stack)malloc(sizeof(Snode));

p->ch=ch;

p->next=top;

top二P；

scanf(，/%c/，,&ch);

getchar();

}

while(p->next!=NULL)〃此處p可用top代替

printf(z，%c->〃,p->ch);

p=p->next;

printf(〃\n〃);

/*以上建立了一個(gè)堆棧*/

printf(〃進(jìn)?；虺鰲?？輸入“1”為進(jìn)棧,輸入“2”為出棧,其它則退

出程序\n〃)；

scanf(〃%d〃,&choice);

getchar();

while(choice—11|choice~2)〃若不是輸入1或2,則不做

任何操作

(

if(choice==l)

{

/*進(jìn)棧*/

printf("\n輸入要入棧的元素\n〃)；

scanfC%^,&ch);

getchar();

p=(stack)malloc(sizcof(Snodc));

p->ch=ch;

p->next=top;

top=p;

)

elseif(choice==2)

(

if(top->next!-NULL)

top=top->next;

else

(

printf(〃棧已清空\n〃);

exit();

)

/*出棧*/

)

//printfC%c―>z/,top->ch);

P=top;

while(p->next!二NULL)

(

printfC%c—>〃,p->ch);

p=p->next;

}

printf(〃\n");

printf(〃進(jìn)棧或出棧?輸入'T為進(jìn)棧,輸入“2”為出棧,

其它則退出程序\n〃)；

scanf&choice);

getchar0;

)

)

//Allcopyrightarepreservedbycobby

//棧的應(yīng)用，括號匹配

#include<stdio.h>

#include<malloc.h>

ftdefineNULL0

typedefstructnode

(

charch;

structnode*next;

}snode,*stack;

main()

(

stacks,top,p;

char*string,ch[100]=”〃；

s=(stack)malloc(sizeof(snode));〃建立棧底元素

s->ch=,\0f;

s->next=NULL;

top=s;

printf(〃輸入一個(gè)含括號的四則運(yùn)算表達(dá)式：\n〃)；

scanf(〃%s〃,ch);

slring=ch;

while(*string!=>\0J)

(

if(^string二二‘(’||"string=二'['||"string=二'{')/

/遇到左括號，入棧

{

p=(stack)malloc(sizcof(snodc));

p->ch=*string;

p->ncxt=top;

top=p;

}

else

if(*string二二'||*string=='|*string=二'}')〃遇到右括號

if(*string==，)')

if(top->ch==,(*)〃括號匹配

top=top->next;

else

(

pr：ntf(〃小括號不匹配〃)；

exit(0);

}

elseif(*string-，Y)

if(top->ch==f)〃括號匹配

top=top->next;

else

(

pr：ntf(〃中括號不匹配〃)；

exit(0);

)

else

if(top>ch==,f)〃括號匹配

top=top->next;

else

(

pr：ntf(〃大括號不匹配〃)；

exit(0);

)

}

strmg++;

}

if(top->ch!=,\0,)

printf(〃多出左括號％八11〃，top->ch);

)

三、隊(duì)及其操作

//Allcopyrightarepreservedbycobby

〃鏈隊(duì)列的建立

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

^defineNULL0

typedefstructnode〃隊(duì)列結(jié)點(diǎn)的基本數(shù)據(jù)結(jié)閻,

即隊(duì)列中每個(gè)結(jié)點(diǎn)的類型

charc;

structnode*next;

Jqnode,*basic_node;

typedefstruct〃隊(duì)列實(shí)際上由頭、尾兩個(gè)結(jié)點(diǎn)指針

構(gòu)成，即頭指針和尾指針唯一確定時(shí)，隊(duì)列也被唯一確定

(

qnode*head:

qnode*rear;

}queue,*Q;

main()

(

Qq；〃定義隊(duì)列，結(jié)構(gòu)體變量q中含有頭指針head和尾由針

rear,所以q是一個(gè)完整的隊(duì)列(只不過隊(duì)列為空)

〃事實(shí)上，任何由Q定義的結(jié)構(gòu)體變量都是一個(gè)獨(dú)立

完整的隊(duì)列

basic_nodep,1;//basic_node是基本結(jié)點(diǎn)類型，即

是獨(dú)立的結(jié)點(diǎn)，它是組成隊(duì)列的基本元素。

〃基本結(jié)點(diǎn)P,1和隊(duì)列q的關(guān)系可由下圖表示：

//(q->head)--->p--->1--->p--->1--->....>p--->1--->；q->

rear)

charch;

q=(Q)mallocJsizeof(queue));

q->head=NULL;〃初始化時(shí)隊(duì)列為空

q->rear=NULL;

printf(“輸入隊(duì)列元素:\n〃)；

scanf(*%c/z,&ch);

getchar();

while(ch!=，:)

(

p二(qnode*)malloc(sizeof(qnode));

p->c=ch;

p->next=NULL;〃新來的元素一定在隊(duì)列的

最后，它的后面沒有其它元素

if(q->head二二NULL)

(

q->head=p;〃第一個(gè)元素入隊(duì)時(shí),

隊(duì)頭指針指向它

l=q->head;//I指向第一個(gè)元素

)

l->next=p;〃使前一個(gè)元素指向

當(dāng)前入隊(duì)的新元素

1=P：//I移動(dòng)到當(dāng)前新

元素，以備用下次入隊(duì)操作

q->rear=p;〃修改隊(duì)尾指針，使其

總是指向當(dāng)前最后一個(gè)隊(duì)列元素

scanf(〃％c〃，&ch);

getchar();

)

l=q->hcad;

while(l!=NULL)

(

printf(，z%c<―l->c);

l=l->next;

}

printf("\n");

printf(〃頭指針指向元素為%c\t尾指針指向元素

^J%c\n，/,q>head>c,q>rear->c);

}

//Allcopyrightarepreservedbycobby

//入隊(duì)和出隊(duì)

#include<stdio.h>

tjinclude<stdlib.h>

#include<malloc.h>

ttdefineNULL0

typedefstructnode〃隊(duì)列結(jié)點(diǎn)的基本數(shù)據(jù)結(jié)陶，

即隊(duì)列中每個(gè)結(jié)點(diǎn)的類型

(

charc;

structnode*next;

}qnode,*basicnode;

typedefstruct〃隊(duì)列實(shí)際上由頭、尾兩個(gè)結(jié)點(diǎn)指針

構(gòu)成，即頭指針和尾指針唯一確定時(shí)，隊(duì)列也被唯一確定

(

qnode*head:

qnode*rear:

}queue,*Q;

main()

Qq；〃定義隊(duì)列，結(jié)構(gòu)體變量q中含有頭指針head和尾韋針

rear,所以q是一個(gè)完整的隊(duì)列(只不過隊(duì)列為空)

〃事實(shí)上，任何由Q定義的結(jié)構(gòu)體變量都是一個(gè)獨(dú)立

完整的隊(duì)列

basic_nodep,1;//basic_node是基本結(jié)點(diǎn)類型，即

是獨(dú)立的結(jié)點(diǎn)，它是組成隊(duì)列的基本元素。

〃基木結(jié)點(diǎn)P,1和隊(duì)列q的關(guān)系可由下國表示：

//(q->hcad)--->p--->1--->p--->1--->....>p--->1--->tq->

rear)

charch;

intchoice;

q=(Q)mallocJsizeof(queue));

q->head=NULL;〃初始化時(shí)隊(duì)列為空

q->rear=NULL;

printf(〃輸入隊(duì)列元素：\n");

scanf&ch);

getchar();

while(ch!=，)

(

p=(qnode*)malloc(sizeof(qnode));

p->c=ch;

p->next-NULL;//新來的元素一定在隊(duì)列的

最后，它的后面沒有其它元素

if(q->head==NULL)

(

q->head=p;〃第一個(gè)元素入隊(duì)時(shí)，

隊(duì)頭指針指向它

l=q->head;//I指向第一個(gè)元素

)

l->next=p;〃使前一個(gè)元素指向

當(dāng)前入隊(duì)的新元素

1=P：//I移動(dòng)到當(dāng)前新

元素，以備用下次入隊(duì)操作

q->rear=p;〃修改隊(duì)尾指針，使其

總是指向當(dāng)前最后一個(gè)隊(duì)列元素

scanf&ch);

getchar();

l=q->head;

while(1!=NULL)

printf(，z%c<—”,J->c);