數(shù)據(jù)結(jié)構(gòu)算法

1、/三章算法/說(shuō)明/listack鏈棧sqstack順序棧liqueue鏈隊(duì)/sqqueue_k順序隊(duì)列(環(huán)形隊(duì)列)sqqueue_unk順序隊(duì)列(非環(huán)形隊(duì)列)/目錄/算法1:判斷一個(gè)字符串是否是對(duì)稱串(sqstack.cpp)/算法2:判斷表達(dá)式中的括號(hào)是否配對(duì)(listack.cpp<string.h>)/算法3:用隊(duì)中元素個(gè)數(shù)代替隊(duì)尾指針的環(huán)形隊(duì)列(<stdio.h><malloc.h>)/算法4:用只有尾結(jié)點(diǎn)指針rear的循環(huán)單鏈表作為鏈隊(duì)(<stdio.h><malloc.h>)/算法5:雙端隊(duì)列算法(sqqueue_k.cp

2、p)/算法6:求簡(jiǎn)單表達(dá)式的值(<stdio.h><stdlib.h>)/算法7:用棧求解迷宮問(wèn)題(<stdio.h><malloc.h>)/算法8:用隊(duì)列求解迷宮問(wèn)題(<stdio.h><malloc.h>)/算法9:求解報(bào)數(shù)問(wèn)題(<stdio.h><malloc.h>)/算法/算法1:判斷一個(gè)字符串是否是對(duì)稱串#include"sqstack.cpp"boolsymmetry(ElemTypestr)inti;ElemTypee;SqStack*st;/初始化棧'0&

3、#39;i+)/將串所有元素進(jìn)棧/元素進(jìn)棧InitStack(st);for(i=0;stri!=Push(st,stri);for(i=0;stri!='0'i+)/退棧元素e/若e與當(dāng)前串元素不同則不是對(duì)稱串Pop(st,e);if(stri!=e)DestroyStack(st);/銷毀棧returnfalse;DestroyStack(st);/銷毀棧returntrue;intmain()(ElemTypestr="1234321"if(symmetry(str)printf("%s是對(duì)稱串n",str);elseprintf(

4、"%s不是對(duì)稱串n",str);return1;)/算法2:判斷表達(dá)式中的括號(hào)是否配對(duì)#include"listack.cpp'#include<string.h>boolMatch(charexp,intn)(inti=0;chare;boolmatch=true;LinkStNode*st;InitStack(st);while(i<n&&match)/初始化棧/掃描exp中所有字符(if(expi='(')Push(st,expi);elseif(expi=')')(if(GetTop

5、(st,e)=true)(if(e!='(')match=false;elsePop(st,e);)elsematch=false;)i+;/當(dāng)前字符為左括號(hào)，將其進(jìn)棧/當(dāng)前字符為右括號(hào)/棧頂元素不為'('時(shí)表示不匹配/將棧頂元素出棧/無(wú)法取棧頂元素時(shí)表示不匹配/繼續(xù)處理其他字符)if(!StackEmpty(st)/棧不空時(shí)表示不匹配/銷毀棧match=falseDestroyStack(st);returnmatch;intmain()(charexp="(1+2*(5+3)/2)”;if(Match(exp,strlen(exp)=1)print

6、f("表達(dá)式s括號(hào)配對(duì)n",exp);elseprintf("表達(dá)式s括號(hào)不配對(duì)n",exp);return1;)/算法3:用隊(duì)中元素個(gè)數(shù)代替隊(duì)尾指針的環(huán)形隊(duì)列#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefintElemType;typedefstruct(ElemTypedataMaxSize;intfront;/隊(duì)頭指針intcount;/隊(duì)列中元素個(gè)數(shù)QuType;voidInitQueue(QuType*&qu)(qu=(QuType*)mal

7、loc(sizeof(QuType);qu->front=0;qu->count=0;voidDestroyQueue(QuType*&qu)(free(qu);boolEnQueue(QuType*&qu,ElemTypex)(intrear;if(qu->count=MaxSize)returnfalse;else/初始化隊(duì)運(yùn)算算法/進(jìn)隊(duì)運(yùn)算算法/臨時(shí)隊(duì)尾指針/隊(duì)滿上溢出(rear=(qu->front+qu->count)%MaxSize;rear=(rear+1)%MaxSize;qu->datarear=x;qu->count

8、+;returntrue;)boolDeQueue(QuType*&qu,ElemType&x)(if(qu->count=0)returnfalse;else(qu->front=(qu->front+1)%MaxSize;x=qu->dataqu->front;qu->count-;returntrue;)boolQueueEmpty(QuType*qu)(return(qu->count=0);)intmain()(QuType*q;ElemTypee;InitQueue(q);EnQueue(q,1);EnQueue(q,2);

9、EnQueue(q,3);EnQueue(q,4);printf("出隊(duì)順序:");while(!QueueEmpty(q)(DeQueue(q,e);printf("%d",e);)printf("n");DestroyQueue(q);/求隊(duì)尾位置/隊(duì)尾循環(huán)增1/元素個(gè)數(shù)增1/出隊(duì)運(yùn)算算法/隊(duì)空下溢出/隊(duì)頭循環(huán)增1/元素個(gè)數(shù)減1/判隊(duì)空運(yùn)算算法return1;rear的循環(huán)單鏈表作為鏈隊(duì)算法4:用只有尾結(jié)點(diǎn)指針#include<stdio.h>#include<malloc.h>typedefintElem

10、Type;typedefstructnodeElemTypedata;structnode*next;LinkNode;voidinitQueue(LinkNode*&rear)rear=NULL;voidenQueue(LinkNode*&rear,ElemTypee)LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode);p->data=e;if(rear=NULL)p->next=p;rear=p;elsep->next=rear->next;rear->next=p;rear=p;booldeQueu

11、e(LinkNode*&rear,ElemType&e)LinkNode*q;if(rear=NULL)returnfalse;elseif(rear->next=rear)/初始化隊(duì)運(yùn)算算法/進(jìn)隊(duì)運(yùn)算算法/創(chuàng)建新結(jié)點(diǎn)/原鏈隊(duì)為空/構(gòu)成循環(huán)鏈表/將p結(jié)點(diǎn)插入到rear結(jié)點(diǎn)之后/讓rear指向這個(gè)新插入的結(jié)點(diǎn)/出隊(duì)運(yùn)算算法/隊(duì)空/原隊(duì)中只有一個(gè)結(jié)點(diǎn)e=rear->data;free(rear);rear=NULL;)else/原隊(duì)中有兩個(gè)或以上的結(jié)點(diǎn)(q=rear->next;e=q->data;rear->next=q->next;free(

12、q);)returntrue;)boolqueueEmpty(LinkNode*rear)/判隊(duì)空運(yùn)算算法(return(rear=NULL);)intmain()(LinkNode*q;ElemTypee;initQueue(q);enQueue(q,1);enQueue(q,2);enQueue(q,3);enQueue(q,4);printf("出隊(duì)順序:");while(!queueEmpty(q)(deQueue(q,e);printf("%d",e);)printf("n");return1;)/算法5:雙端隊(duì)列算法#in

13、clude"sqqueue_k.cpp"booldeQueue1(SqQueue*&q,ElemType&e)/從隊(duì)尾刪除/隊(duì)空(if(q->front=q->rear)returnfalse;e=q->dataq->rear;/提取隊(duì)尾元素q->rear=(q->rear-1+MaxSize)%MaxSize;/修改除尾指針returntrue;boolenQueue1(SqQueue*&q,ElemTypee)/從隊(duì)頭插入if(q->rear+1)%MaxSize=q->front)/隊(duì)滿retur

14、nfalse;q->dataq->front=e;/e元素進(jìn)隊(duì)q->front=(q->front-1+MaxSize)%MaxSize;/修改隊(duì)頭指針returntrue;intmain()ElemTypee;inti;SqQueue*q;InitQueue(q);printf("從隊(duì)尾插入a,b,從隊(duì)頭插入c,d,從隊(duì)尾插入en");enQueue(q,'a');/從隊(duì)尾插入"a'enQueue(q,'b');/從隊(duì)尾插入"b"enQueue1(q,"c")

15、;/從隊(duì)頭插入"c"enQueue1(q,'d");/從隊(duì)頭插入"d"enQueue(q,"e");/從隊(duì)尾插入"e"printf("從隊(duì)頭出隊(duì)兩個(gè)元素:");for(i=1;i<=2;i+)deQueue(q,e);/從隊(duì)頭刪除printf("%c",e);printf("n從隊(duì)尾出隊(duì)其他元素:");while(!QueueEmpty(q)deQueue1(q,e);/從隊(duì)尾刪除printf("%c",e);p

16、rintf("n");return1;算法6:求簡(jiǎn)單表達(dá)式的值#include<stdio.h>#include<stdlib.h>#defineMaxSize100/-運(yùn)算符棧基本運(yùn)算/typedefstructchardataMaxSize;/存放運(yùn)算符inttop;/棧頂指針SqStack;voidInitStack(SqStack*&s)/初始化棧s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;voidDestroyStack(SqStack*&s)/free(s);boolSt

17、ackEmpty(SqStack*s)return(s->top=-1);boolPush(SqStack*&s,chare)/if(s->top=MaxSize-1)returnfalse;s->top+;s->datas->top=e;returntrue;boolPop(SqStack*&s,char&e)/if(s->top=-1)returnfalse;e=s->datas->top;s->top-;returntrue;銷毀棧/判斷棧是否為空進(jìn)棧元素e出棧元素e/取棧頂元素eboolGetTop(SqSt

18、ack*s,char&e)(if(s->top=-1)returnfalse;e=s->datas->top;returntrue;/voidtrans(char*exp,charpostexp口)(chare;SqStack*Optr;InitStack(Optr);inti=0;while(*exp!=''0')(switch(*exp)(case'(':Push(Optr,'(');exp+;break;case')':Pop(Optr,e);while(e!='(')(po

19、stexpi+=e;Pop(Optr,e);exp+;break;case'+':case'-':while(!StackEmpty(Optr)(GetTop(Optr,e);if(e!='(')(postexpi+=e;Pop(Optr,e);/將算術(shù)表達(dá)式exp轉(zhuǎn)換成后綴表達(dá)式postexp/定義運(yùn)算符棧/初始化運(yùn)算符棧/i作為postexp的下標(biāo)/exp表達(dá)式未掃描完時(shí)循環(huán)/判定為左括號(hào)/左括號(hào)進(jìn)棧/繼續(xù)掃描其他字符/判定為右括號(hào)/出棧元素e/不為'('時(shí)循環(huán)/將e存放到postexp中/繼續(xù)出棧元素e/繼續(xù)掃描其他字符/判

20、定為加或減號(hào)/棧不空循環(huán)/取棧頂元素e/e不是'('/將e存放到postexp中/出棧元素ecase)elsebreak;)Push(Optr,*exp);exp+;break;1*1./e是'（時(shí)退出循環(huán)/將'+'或'-'進(jìn)棧/繼續(xù)掃描其他字符/判定為'*'或'/'號(hào)while(!StackEmpty(Optr)GetTop(Optr,e);if(e='*'|e='/')postexpi+=e;Pop(Optr,e);)elsebreak;)Push(Optr,*exp);

21、exp+;break;/棧不空循環(huán)/取棧頂元素e/將棧頂'*'或'/'運(yùn)算符出棧并存放到/將e存放到postexp中/出棧元素e/e為非'*'或'/'運(yùn)算符時(shí)退出循環(huán)/將'*'或'/'進(jìn)棧/繼續(xù)掃描其他字符postexp中default:/處理數(shù)字字符while(*exp>='0'&&*exp<='9')/判定為數(shù)字postexpi+=*exp;exp+;)postexpi+='#'/用雨識(shí)一個(gè)數(shù)值串結(jié)束)while(!St

22、ackEmpty(Optr)/此時(shí)exp掃描完畢，棧不空時(shí)循環(huán)Pop(Optr,e);/出棧元素epostexpi+=e;/將e存放至Upostexp中)postexpi='0'/給postexp表達(dá)式添加結(jié)束標(biāo)識(shí)DestroyStack(Optr);/銷毀棧)/-操作數(shù)?；具\(yùn)算/typedefstructdoubledataMaxSize;inttop;SqStack1;voidInitStack1(SqStack1*&s)/存放數(shù)值棧頂指針初始化棧s=(SqStackl*)malloc(sizeof(SqStack1);s->top=-1;voidDestr

23、oyStack1(SqStack1*&s)free(s);boolStackEmpty1(SqStack1*s)return(s->top=-1);boolPush1(SqStack1*&s,doublee)/銷毀棧判斷棧是否為空進(jìn)棧元素eif(s->top=MaxSize-1)returnfalse;s->top+;s->datas->top=e;returntrue;boolPop1(SqStack1*&s,double&e)/出棧元素eif(s->top=-1)returnfalse;e=s->datas->

24、top;s->top-;returntrue;boolGetTop1(SqStack1*s,double&e)if(s->top=-1)/取棧頂元素returnfalse;e=s->datas->top;returntrue;/doublecompvalue(char*postexp)(/計(jì)算后綴表達(dá)式的值/定義操作數(shù)棧/初始化操作數(shù)棧doubled,a,b,c,e;SqStack1*Opnd;InitStack1(Opnd);while(*postexp!='0')/postexp字符串未掃描完時(shí)循環(huán)(switch(*postexp)(case

25、'+':/判定為'+'號(hào)Pop1(Opnd,a);/出棧元素aPop1(Opnd,b);/出棧元素bc=b+a;/計(jì)算cPush1(Opnd,c);/將計(jì)算結(jié)果c進(jìn)棧break;case'-':/判定為'-'號(hào)Pop1(Opnd,a);/出棧元素aPop1(Opnd,b);/出棧元素bc=b-a;/計(jì)算cPush1(Opnd,c);/將計(jì)算結(jié)果c進(jìn)棧break;case'*':/判定為'*'號(hào)Pop1(Opnd,a);/出棧元素aPop1(Opnd,b);/出棧元素bc=b*a;/計(jì)算cPush1(

26、Opnd,c);/將計(jì)算結(jié)果c進(jìn)棧break;case'/':/判定為'/'號(hào)Pop1(Opnd,a);/出棧元素aPop1(Opnd,b);/出棧元素bif(a!=0)(c=b/a;/計(jì)算cPush1(Opnd,c);/將計(jì)算結(jié)果c進(jìn)棧break;)elseprintf("nt除零錯(cuò)誤!n");exit(0);/異常退出)break;default:/處理數(shù)字字符d=0;/將連續(xù)的數(shù)字字符轉(zhuǎn)換成對(duì)應(yīng)的數(shù)值存放到d中while(*postexp>='0'&&*postexp<='9'

27、)/判定為數(shù)字字符(d=10*d+*postexp-'0'postexp+;)Push1(Opnd,d);/將數(shù)值d進(jìn)棧break;)postexp+;/繼續(xù)處理其他字符)GetTop1(Opnd,e);/取棧頂元素eDestroyStackl(Opnd);/銷毀棧returne;/返回e)intmain()(charexp="(56-20)/(4+2)"charpostexpMaxSize;trans(exp,postexp);printf("中綴表達(dá)式：sn",exp);printf("后綴表達(dá)式：sn",post

28、exp);printf("表達(dá)式的值：gn",compvalue(postexp);return1;)/算法7:用棧求解迷宮問(wèn)題#include<stdio.h>#include<malloc.h>#defineMaxSize100#defineM8#defineN8intmgM+2N+2=(1,1,1,1,1,1,1,1,1,1),(1,0,0,1,0,0,0,1,0,1),(1,0,0,1,0,0,0,1,0,1),(1,0,0,0,0,1,1,0,0,1),(1,0,1,1,1,0,0,0,0,1),(1,0,0,0,1,0,0,0,0,1),

29、(1,0,1,0,0,0,1,0,0,1),(1,0,1,1,1,0,1,1,0,1),(1,1,0,0,0,0,0,0,0,1),(1,1,1,1,1,1,1,1,1,1);/-迷宮?；具\(yùn)算/typedefstruct(inti;/當(dāng)前方塊的行號(hào)intj;/當(dāng)前方塊的列號(hào)intdi;/di是下一可走相鄰方位的方位號(hào)Box;typedefstruct(BoxdataMaxSize;/存放方塊inttop;/棧頂指針/初始化棧StType;/定義棧類型voidInitStack(StType*&s)(s=(StType*)malloc(sizeof(StType);s->top=

30、-1;voidDestroyStack(StType*&s)(free(s);boolStackEmpty(StType*s)(return(s->top=-1);boolPush(StType*&s,Boxe)/銷毀棧/判斷棧是否為空/進(jìn)棧元素e求解路徑為:(xi,yi)->(xe,ye)/定義棧st/初始化棧頂指針/設(shè)置e為入口/方塊e進(jìn)棧/入口的迷宮值置為-1避免重復(fù)走到該方塊/棧不空時(shí)循環(huán)/取棧頂方塊e/找到了出口，輸出該路徑if(s->top=MaxSize-1)returnfalse;s->top+;s->datas->top=e

31、;returntrue;boolPop(StType*&s,Box&e)/出棧元素eif(s->top=-1)returnfalse;e=s->datas->top;s->top-;returntrue;boolGetTop(StType*s,Box&e)/取棧頂元素if(s->top=-1)returnfalse;e=s->datas->top;returntrue;/boolmgpath(intxi,intyi,intxe,intye)/BoxpathMaxSize,e;inti,j,di,i1,j1,k;boolfind;

32、StType*st;InitStack(st);e.i=xi;e.j=yi;e.di=-1;Push(st,e);mgxiyi=-1;while(!StackEmpty(st)GetTop(st,e);i=e.i;j=e.j;di=e.di;if(i=xe&&j=ye)printf("一條迷宮路徑如下：n");k=0;while(!StackEmpty(st)Pop(st,e);/出棧方塊epathk+=e;/將e添加到path數(shù)組中)while(k>=1)(k-;printf("t(%d,%d)”,pathk.i,pathk.j);if(k

33、+2)%5=0)/每輸出每5個(gè)方塊后換一行printf("n");)printf("n");DestroyStack(st);returntrue;)find=false;while(di<4&&!find)(di+;switch(di)(case0:i1=i-1;j1=j;break;case1:i1=i;j1=j+1;break;case2:i1=i+1;j1=j;break;case3:i1=i;j1=j-1;break;)if(mgi1j1=0)find=true;)if(find)(st->datast->to

34、p.di=di;e.i=i1;e.j=j1;e.di=-1;Push(st,e);mgi1j1=-1;)else(Pop(st,e);mge.ie.j=0;)/銷毀棧/輸出一條迷宮路徑后返回true/找相鄰可走方塊(i1,j1)/找到一個(gè)相鄰可走方塊，設(shè)置find我真/找到了一個(gè)相鄰可走方塊(i1,j1)/修改原棧頂元素的di值/相鄰可走方塊e進(jìn)棧/(i1,j1)的迷宮值置為-1避免重復(fù)走到該方塊/沒(méi)有路徑可走，則退棧/將棧頂方塊退棧/讓退棧方塊的位置變?yōu)槠渌窂娇勺叻綁K/銷毀棧表示沒(méi)有可走路徑，返回false)DestroyStack(st);returnfalse;)intmain()(m

35、gpath(1,1,M,N);return1;)/算法8:用隊(duì)列求解迷宮問(wèn)題#include<stdio.h>#include<malloc.h>#defineMaxSize100#defineM8#defineN8intmgM+2N+2=(1,1,1,1,1,1,1,1,1,1),(1,0,0,1,0,0,0,1,0,1),(1,0,0,1,0,0,0,1,0,1),(1,0,0,0,0,1,1,0,0,1),(1,0,1,1,1,0,0,0,0,1),(1,0,0,0,1,0,0,0,0,1),(1,0,1,0,0,0,1,0,0,1),(1,0,1,1,1,0,1

36、,1,0,1),(1,1,0,0,0,0,0,0,0,1),(1,1,1,1,1,1,1,1,1,1);/-非環(huán)形隊(duì)列的基本運(yùn)算算法/typedefstruct(inti,j;/方塊的位置intpre;/本路徑中上一方塊在隊(duì)列中的下標(biāo)Box;/方塊類型typedefstruct(BoxdataMaxSize;intfront,rear;QuType;/隊(duì)頭指針和隊(duì)尾指針順序隊(duì)類型voidInitQueue(QuType*&q)/初始化隊(duì)列(q=(QuType*)malloc(sizeof(QuType);q->front=q->rear=-1;voidDestroyQueu

37、e(QuType*&q)(free(q);boolQueueEmpty(QuType*q)(return(q->front=q->rear);boolenQueue(QuType*&q,Boxe)(if(q->rear=MaxSize-1)returnfalse;q->rear+;q->dataq->rear=e;returntrue;booldeQueue(QuType*&q,Box&e)(if(q->front=q->rear)returnfalse;q->front+;e=q->dataq->

38、;front;returntrue;/銷毀隊(duì)列/判斷隊(duì)列是否為空/進(jìn)隊(duì)列/隊(duì)滿上溢出/返回假/隊(duì)尾增1/rear位置插入元素e/返回真/出隊(duì)列/隊(duì)空下溢出voidprint(QuType*qu,intfront)/從隊(duì)列qu中輸出路徑(intk=front,j,ns=0;printf("n");-1do/反向找到最短路徑，將該路徑上的方塊的pre成員設(shè)置成j=k;k=qu->datak.pre;qu->dataj.pre=-1;while(k!=0);printf("一條迷宮路徑如下：n");k=0;while(k<MaxSize)/正

39、向搜索到pre為-1的方塊，即構(gòu)成正向的路徑if(qu->datak.pre=-1)ns+;printf("t(%d,%d)",qu->datak.i,qu->datak.j);if(ns%5=0)printf("n");/k+;printf("n");boolmgpath1(intxi,intyi,intxe,intye)Boxe;inti,j,di,i1,j1;QuType*qu;InitQueue(qu);e.i=xi;e.j=yi;e.pre=-1;enQueue(qu,e);mgxiyi=-1;while(

40、!QueueEmpty(qu)deQueue(qu,e);i=e.i;j=e.j;if(i=xe&&j=ye)print(qu,qu->front);/DestroyQueue(qu);returntrue;for(di=0;di<4;di+)每輸出每5個(gè)方塊后換一行/搜索路徑為:(xi,yi)->(xe,ye)/定義順序隊(duì)指針qu/初始化隊(duì)列qu/(xi,yi)進(jìn)隊(duì)將其賦值-1,以避免回過(guò)來(lái)重復(fù)搜索/隊(duì)不空且循環(huán)/出隊(duì)方塊e,由于不是環(huán)形隊(duì)列，該出隊(duì)元素仍在隊(duì)列中/找到了出口，輸出路徑調(diào)用print函數(shù)輸出路徑/銷毀隊(duì)列/找到一條路徑時(shí)返回真/循環(huán)掃描每個(gè)方位，把每個(gè)可走的方塊插入隊(duì)列中switch(di)case0:i1=i-1;j1=j;break;case1:i1=i;j1=j+1;break;case2:i1=i+1;j1=j;break;case3:i1=i;j1=j-1;break;)if(mgi1j1=0)(e.i=i1;e.j=j1;/指