数据结构算法

1、/三章算法/说明/listack链栈sqstack顺序栈liqueue链队/sqqueue_k顺序队列(环形队列)sqqueue_unk顺序队列(非环形队列)/目录/算法1:判断一个字符串是否是对称串(sqstack.cpp)/算法2:判断表达式中的括号是否配对(listack.cpp<string.h>)/算法3:用队中元素个数代替队尾指针的环形队列(<stdio.h><malloc.h>)/算法4:用只有尾结点指针rear的循环单链表作为链队(<stdio.h><malloc.h>)/算法5:双端队列算法(sqqueue_k.cp

2、p)/算法6:求简单表达式的值(<stdio.h><stdlib.h>)/算法7:用栈求解迷宫问题(<stdio.h><malloc.h>)/算法8:用队列求解迷宫问题(<stdio.h><malloc.h>)/算法9:求解报数问题(<stdio.h><malloc.h>)/算法/算法1:判断一个字符串是否是对称串#include"sqstack.cpp"boolsymmetry(ElemTypestr)inti;ElemTypee;SqStack*st;/初始化栈'0&

3、#39;i+)/将串所有元素进栈/元素进栈InitStack(st);for(i=0;stri!=Push(st,stri);for(i=0;stri!='0'i+)/退栈元素e/若e与当前串元素不同则不是对称串Pop(st,e);if(stri!=e)DestroyStack(st);/销毁栈returnfalse;DestroyStack(st);/销毁栈returntrue;intmain()(ElemTypestr="1234321"if(symmetry(str)printf("%s是对称串n",str);elseprintf(

4、"%s不是对称串n",str);return1;)/算法2:判断表达式中的括号是否配对#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+;/当前字符为左括号，将其进栈/当前字符为右括号/栈顶元素不为'('时表示不匹配/将栈顶元素出栈/无法取栈顶元素时表示不匹配/继续处理其他字符)if(!StackEmpty(st)/栈不空时表示不匹配/销毁栈match=falseDestroyStack(st);returnmatch;intmain()(charexp="(1+2*(5+3)/2)”;if(Match(exp,strlen(exp)=1)print

6、f("表达式s括号配对n",exp);elseprintf("表达式s括号不配对n",exp);return1;)/算法3:用队中元素个数代替队尾指针的环形队列#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefintElemType;typedefstruct(ElemTypedataMaxSize;intfront;/队头指针intcount;/队列中元素个数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/初始化队运算算法/进队运算算法/临时队尾指针/队满上溢出(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("出队顺序:");while(!QueueEmpty(q)(DeQueue(q,e);printf("%d",e);)printf("n");DestroyQueue(q);/求队尾位置/队尾循环增1/元素个数增1/出队运算算法/队空下溢出/队头循环增1/元素个数减1/判队空运算算法return1;rear的循环单链表作为链队算法4:用只有尾结点指针#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)/初始化队运算算法/进队运算算法/创建新结点/原链队为空/构成循环链表/将p结点插入到rear结点之后/让rear指向这个新插入的结点/出队运算算法/队空/原队中只有一个结点e=rear->data;free(rear);rear=NULL;)else/原队中有两个或以上的结点(q=rear->next;e=q->data;rear->next=q->next;free(

12、q);)returntrue;)boolqueueEmpty(LinkNode*rear)/判队空运算算法(return(rear=NULL);)intmain()(LinkNode*q;ElemTypee;initQueue(q);enQueue(q,1);enQueue(q,2);enQueue(q,3);enQueue(q,4);printf("出队顺序:");while(!queueEmpty(q)(deQueue(q,e);printf("%d",e);)printf("n");return1;)/算法5:双端队列算法#in

13、clude"sqqueue_k.cpp"booldeQueue1(SqQueue*&q,ElemType&e)/从队尾删除/队空(if(q->front=q->rear)returnfalse;e=q->dataq->rear;/提取队尾元素q->rear=(q->rear-1+MaxSize)%MaxSize;/修改除尾指针returntrue;boolenQueue1(SqQueue*&q,ElemTypee)/从队头插入if(q->rear+1)%MaxSize=q->front)/队满retur

14、nfalse;q->dataq->front=e;/e元素进队q->front=(q->front-1+MaxSize)%MaxSize;/修改队头指针returntrue;intmain()ElemTypee;inti;SqQueue*q;InitQueue(q);printf("从队尾插入a,b,从队头插入c,d,从队尾插入en");enQueue(q,'a');/从队尾插入"a'enQueue(q,'b');/从队尾插入"b"enQueue1(q,"c")

15、;/从队头插入"c"enQueue1(q,'d");/从队头插入"d"enQueue(q,"e");/从队尾插入"e"printf("从队头出队两个元素:");for(i=1;i<=2;i+)deQueue(q,e);/从队头删除printf("%c",e);printf("n从队尾出队其他元素:");while(!QueueEmpty(q)deQueue1(q,e);/从队尾删除printf("%c",e);p

16、rintf("n");return1;算法6:求简单表达式的值#include<stdio.h>#include<stdlib.h>#defineMaxSize100/-运算符栈基本运算/typedefstructchardataMaxSize;/存放运算符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;销毁栈/判断栈是否为空进栈元素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);/将算术表达式exp转换成后缀表达式postexp/定义运算符栈/初始化运算符栈/i作为postexp的下标/exp表达式未扫描完时循环/判定为左括号/左括号进栈/继续扫描其他字符/判定为右括号/出栈元素e/不为'('时循环/将e存放到postexp中/继续出栈元素e/继续扫描其他字符/判

20、定为加或减号/栈不空循环/取栈顶元素e/e不是'('/将e存放到postexp中/出栈元素ecase)elsebreak;)Push(Optr,*exp);exp+;break;1*1./e是'（时退出循环/将'+'或'-'进栈/继续扫描其他字符/判定为'*'或'/'号while(!StackEmpty(Optr)GetTop(Optr,e);if(e='*'|e='/')postexpi+=e;Pop(Optr,e);)elsebreak;)Push(Optr,*exp);

21、exp+;break;/栈不空循环/取栈顶元素e/将栈顶'*'或'/'运算符出栈并存放到/将e存放到postexp中/出栈元素e/e为非'*'或'/'运算符时退出循环/将'*'或'/'进栈/继续扫描其他字符postexp中default:/处理数字字符while(*exp>='0'&&*exp<='9')/判定为数字postexpi+=*exp;exp+;)postexpi+='#'/用雨识一个数值串结束)while(!St

22、ackEmpty(Optr)/此时exp扫描完毕，栈不空时循环Pop(Optr,e);/出栈元素epostexpi+=e;/将e存放至Upostexp中)postexpi='0'/给postexp表达式添加结束标识DestroyStack(Optr);/销毁栈)/-操作数栈基本运算/typedefstructdoubledataMaxSize;inttop;SqStack1;voidInitStack1(SqStack1*&s)/存放数值栈顶指针初始化栈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)/销毁栈判断栈是否为空进栈元素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)(/计算后缀表达式的值/定义操作数栈/初始化操作数栈doubled,a,b,c,e;SqStack1*Opnd;InitStack1(Opnd);while(*postexp!='0')/postexp字符串未扫描完时循环(switch(*postexp)(case

25、'+':/判定为'+'号Pop1(Opnd,a);/出栈元素aPop1(Opnd,b);/出栈元素bc=b+a;/计算cPush1(Opnd,c);/将计算结果c进栈break;case'-':/判定为'-'号Pop1(Opnd,a);/出栈元素aPop1(Opnd,b);/出栈元素bc=b-a;/计算cPush1(Opnd,c);/将计算结果c进栈break;case'*':/判定为'*'号Pop1(Opnd,a);/出栈元素aPop1(Opnd,b);/出栈元素bc=b*a;/计算cPush1(

26、Opnd,c);/将计算结果c进栈break;case'/':/判定为'/'号Pop1(Opnd,a);/出栈元素aPop1(Opnd,b);/出栈元素bif(a!=0)(c=b/a;/计算cPush1(Opnd,c);/将计算结果c进栈break;)elseprintf("nt除零错误!n");exit(0);/异常退出)break;default:/处理数字字符d=0;/将连续的数字字符转换成对应的数值存放到d中while(*postexp>='0'&&*postexp<='9'

27、)/判定为数字字符(d=10*d+*postexp-'0'postexp+;)Push1(Opnd,d);/将数值d进栈break;)postexp+;/继续处理其他字符)GetTop1(Opnd,e);/取栈顶元素eDestroyStackl(Opnd);/销毁栈returne;/返回e)intmain()(charexp="(56-20)/(4+2)"charpostexpMaxSize;trans(exp,postexp);printf("中缀表达式：sn",exp);printf("后缀表达式：sn",post

28、exp);printf("表达式的值：gn",compvalue(postexp);return1;)/算法7:用栈求解迷宫问题#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);/-迷宫栈基本运算/typedefstruct(inti;/当前方块的行号intj;/当前方块的列号intdi;/di是下一可走相邻方位的方位号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)/销毁栈/判断栈是否为空/进栈元素e求解路径为:(xi,yi)->(xe,ye)/定义栈st/初始化栈顶指针/设置e为入口/方块e进栈/入口的迷宫值置为-1避免重复走到该方块/栈不空时循环/取栈顶方块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数组中)while(k>=1)(k-;printf("t(%d,%d)”,pathk.i,pathk.j);if(k

33、+2)%5=0)/每输出每5个方块后换一行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)/找到一个相邻可走方块，设置find我真/找到了一个相邻可走方块(i1,j1)/修改原栈顶元素的di值/相邻可走方块e进栈/(i1,j1)的迷宫值置为-1避免重复走到该方块/没有路径可走，则退栈/将栈顶方块退栈/让退栈方块的位置变为其他路径可走方块/销毁栈表示没有可走路径，返回false)DestroyStack(st);returnfalse;)intmain()(m

35、gpath(1,1,M,N);return1;)/算法8:用队列求解迷宫问题#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);/-非环形队列的基本运算算法/typedefstruct(inti,j;/方块的位置intpre;/本路径中上一方块在队列中的下标Box;/方块类型typedefstruct(BoxdataMaxSize;intfront,rear;QuType;/队头指针和队尾指针顺序队类型voidInitQueue(QuType*&q)/初始化队列(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;/销毁队列/判断队列是否为空/进队列/队满上溢出/返回假/队尾增1/rear位置插入元素e/返回真/出队列/队空下溢出voidprint(QuType*qu,intfront)/从队列qu中输出路径(intk=front,j,ns=0;printf("n");-1do/反向找到最短路径，将该路径上的方块的pre成员设置成j=k;k=qu->datak.pre;qu->dataj.pre=-1;while(k!=0);printf("一条迷宫路径如下：n");k=0;while(k<MaxSize)/正

39、向搜索到pre为-1的方块，即构成正向的路径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个方块后换一行/搜索路径为:(xi,yi)->(xe,ye)/定义顺序队指针qu/初始化队列qu/(xi,yi)进队将其赋值-1,以避免回过来重复搜索/队不空且循环/出队方块e,由于不是环形队列，该出队元素仍在队列中/找到了出口，输出路径调用print函数输出路径/销毁队列/找到一条路径时返回真/循环扫描每个方位，把每个可走的方块插入队列中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;/指