經(jīng)典數(shù)據(jù)結(jié)構(gòu)上機(jī)題—答案

1、.數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)題目實(shí)驗(yàn)一線性表的順序存儲(chǔ)結(jié)構(gòu)實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)背景知識(shí):順序表的插入、刪除及應(yīng)用。目的要求：1掌握順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。2掌握順序存儲(chǔ)結(jié)構(gòu)的常見算法。實(shí)驗(yàn)內(nèi)容1輸入一組整型元素序列，建立順序表。2實(shí)現(xiàn)該順序表的遍歷。3在該順序表中進(jìn)行順序查找某一元素,查找成功返回1,否則返回0。4判斷該順序表中元素是否對(duì)稱,對(duì)稱返回1,否則返回0。5實(shí)現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。6輸入整型元素序列利用有序表插入算法建立一個(gè)有序表。7利用算法6建立兩個(gè)非遞減有序表并把它們合并成一個(gè)非遞減有序表。8. 利用該順序結(jié)構(gòu)實(shí)現(xiàn)循環(huán)隊(duì)列的入隊(duì)、出隊(duì)操作。8編寫一個(gè)主函數(shù),

2、調(diào)試上述算法。*include <stdio.h>*include <stdlib.h>*define OVERFLOW 0*define MAXSIZE 100typedef int ElemType;typedef struct listElemType elemMAXSIZE; int length;Sqlist;void Creatlist(Sqlist &L)int i; printf("請(qǐng)輸入順序表的長(zhǎng)度：");/輸入一組整型元素序列，建立一個(gè)順序表。 scanf("%d",&L.length); fo

3、r(i=0;i<L.length;i+) scanf("%d",&L.elemi);void printlist(Sqlist &L)/以輸出的形式實(shí)現(xiàn)對(duì)該順序表的遍歷int i; for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");void Searchlist(Sqlist &L,int x)/在順序表中進(jìn)行順序查找某一元素x，查找成功則返回其存儲(chǔ)位置i，否則返回錯(cuò)誤信息int i,k=-1; for(i=0;i<L.leng

4、th;i+) if(L.elemi=x) k=i+1;printf("%d ",k); if(k=-1) printf("error!"); printf("n");void Inseri(Sqlist &L,int i,int x)/在順序表的第i個(gè)位置上插入一個(gè)元素xint j; for(j=L.length;j>=i;j-)L.elemj=L.elemj-1; L.elemj=x; L.length+;void Delete(Sqlist &L,int i)/刪除順序表中第i個(gè)元素int j;for(j=i

5、;j<L.length;j+)L.elemj-1=L.elemj;L.length-;void Insert(Sqlist &L,int x)/輸入一個(gè)元素x，把它插入到有序表中，使順序表依然有序。int i,j; if(L.length=MAXSIZE) exit(OVERFLOW);/表滿，不能插入 for(i=1;i<=L.length&&L.elemi-1<=x;i+); for(j=L.length;j>=i;j-) L.elemj=L.elemj-1; L.elemi-1=x; L.length+;void Creatlist_sor

6、ted(Sqlist &L)/利用有序表插入算法建立一個(gè)有序表int i,num; ElemType x; L.length=0; printf("請(qǐng)輸入順序表的長(zhǎng)度："); scanf("%d",&num); for(i=1;i<=num;i+) scanf("%d",&x); Insert(L,x); void Merger(Sqlist &p,Sqlist &r,Sqlist &c) /建立兩個(gè)非遞減有序表，并把它們合并成一個(gè)非遞減有序表 ElemType *a,*b,i=0

7、,j=0,k=0; a=&p.elem0; b=&r.elem0; c.length=p.length+r.length; while(i<p.length&&j<r.length) if(*a>=*b) c.elemk=*b;b+;k+;j+; else c.elemk=*a;a+;k+;i+; if(j=r.length) for(;k<c.length;k+) c.elemk=*a;a+; else if(i=p.length) for(;k<c.length;k+)c.elemk=*b;b+;void main()Sqlis

8、t L,M,N; int x,i,n; printf("1.建立一個(gè)順序表.n"); printf("2.以輸出的形式對(duì)該順序表遍歷.n"); printf("3.在順序表中進(jìn)行順序查找某一元素x.n"); printf("4.在順序表的第i個(gè)位置上插入一個(gè)元素x.n"); printf("5.刪除順序表中第i個(gè)元素.n"); printf("6.利用有序表插入算法建立一個(gè)有序表.n"); printf("7.建立兩個(gè)非遞減有序表，并把它們合并成一個(gè)非遞減有序表.n

9、"); printf("8.輸入一個(gè)元素x，把它插入到有序表中，使順序表依然有序.n"); while(1) printf("請(qǐng)選擇："); scanf("%d",&n); switch(n) case 1:Creatlist(L);break; case 2:printlist(L);break; case 3:printf("請(qǐng)輸入要查找的元素x:"); scanf("%d",&x); Searchlist(L,x);break; case 4:printf(&qu

10、ot;請(qǐng)輸入要插入的位置i:"); scanf("%d",&i); if(i<1|i>L.length+1) printf("error!n");break; printf("請(qǐng)輸入要插入的值x:"); scanf("%d",&x); Inseri(L,i,x); printlist(L);break; case 5:printf("請(qǐng)輸入要?jiǎng)h去的元素的位置i:"); scanf("%d",&i); if(i<1|i>

11、L.length) printf("error!n");break; Delete(L,i); printlist(L);break; case 6:Creatlist_sorted(L); printlist(L);break; case 7:Creatlist_sorted(L); Creatlist_sorted(M); Merger(L,M,N); printlist(N);break; case 8:Creatlist_sorted(L); printf("請(qǐng)輸入要插入的元素x:"); scanf("%d",&x);

12、 Insert(L,x); printlist(L);break; 實(shí)驗(yàn)二鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（一）-單向鏈表的有關(guān)操作實(shí)驗(yàn)學(xué)時(shí)3學(xué)時(shí)背景知識(shí)：?jiǎn)蜗蜴湵淼牟迦?、刪除及應(yīng)用。目的要求1掌握單向鏈表的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。2掌握單向鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)內(nèi)容1隨機(jī)產(chǎn)生或鍵盤輸入一組元素，建立一個(gè)帶頭結(jié)點(diǎn)的單向鏈表（無序）。2遍歷單向鏈表。3把單向鏈表中元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。4在單向鏈表中刪除所有的偶數(shù)元素結(jié)點(diǎn)。5編寫在非遞減有序鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個(gè)非遞減有序單向鏈表。6利用算法5建立兩個(gè)非遞減有序單向鏈表，然后合并成一個(gè)非遞增鏈

13、表。7利用算法5建立兩個(gè)非遞減有序單向鏈表，然后合并成一個(gè)非遞減鏈表。8利用算法1建立的鏈表，實(shí)現(xiàn)將其分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量利用已知的存儲(chǔ)空間）。* 9采用單向鏈表實(shí)現(xiàn)一元多項(xiàng)式的存儲(chǔ)并實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加并輸出結(jié)果。10在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。 *11綜合訓(xùn)練：利用鏈表實(shí)現(xiàn)一個(gè)班級(jí)學(xué)生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲(chǔ)到文件中）/*單向鏈表的有關(guān)操作示例*/*類型定義及頭文件部分,文件名為sllink.h*/ *include <stdio.h> *include <stdlib.h&

14、gt; typedef int ElemType;/元素實(shí)際類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /定義結(jié)點(diǎn)、指針類型名 /頭插法建立無序鏈表 void CreateList(LinkList &L) LinkList p; ElemType e; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; printf("頭插法建立鏈表，以0結(jié)束n"); scanf("%d",&e)

15、; while(e) p=(LinkList)malloc(sizeof(LNode); p->data=e; p->next=L->next; L->next=p; scanf("%d",&e); /*非遞減有序單向鏈表L插入元素e序列仍有序*/ void Insert_Sort(LinkList &L,ElemType e) LinkList p,s; s=(LinkList)malloc(sizeof(LNode); s->data=e; p=L; while(p->next&&p->next-

16、>data<=e) p=p->next;/*查找插入位置*/ s->next=p->next; /*插入語句*p結(jié)點(diǎn)后插入*s結(jié)點(diǎn)*/ p->next=s; /*建立遞增有序的單向鏈表*/ void Create_Sort(LinkList &L) ElemType e; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; printf("建立有序表，輸入任意個(gè)整型數(shù)據(jù)以0結(jié)束n"); scanf("%d",&e); while(e) Insert_So

17、rt(L,e); scanf("%d",&e); /*單向鏈表的遍歷*/ void Traverse(LinkList L) LinkList p; printf("遍歷鏈表"); for(p=L->next;p;p=p->next) printf("%5d",p->data); printf("n"); /*在單向鏈表刪除元素e*/ void Delete(LinkList &L,ElemType e) LinkList p,q; p=L; q=L->next; while

18、(q&& q->data!=e)/查找元素的刪除位置 p=q; q=q->next; if(!q) printf("nnot deleted");/*未找到元素e*/ else p->next=q->next;/*找到刪除*/ free(q); /*單向鏈表的逆置*/ void exch(LinkList &L) LinkList p,s; p=L->next; L->next=NULL; while(p) s=p; p=p->next; s->next=L->next; L->next=s

19、; /*兩個(gè)非遞減有序單向鏈表合并后仍為非遞減序列*/ void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc) LinkList p,q,s,rear; p=La->next; q=Lb->next; Lc=rear=La; free(Lb); while(p&&q) if (p->data<q->data) s=p;p=p->next; else s=q;q=q->next; rear->next=s;/*較小元素插入表尾*/ rear=rear->next

20、; if (p) rear->next=p; else rear->next=q實(shí)驗(yàn)三 迷宮問題求解實(shí)驗(yàn)學(xué)時(shí)3學(xué)時(shí)背景知識(shí)：棧的操作。目的要求1掌握棧的存儲(chǔ)特點(diǎn)及其實(shí)現(xiàn)。2掌握棧的出棧和入棧操作。實(shí)驗(yàn)內(nèi)容： 以一個(gè)mxn的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)順序或鏈表做存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i, j, d)的形式輸出，其中：(i, j)表示迷宮的坐標(biāo)，d表示走到下一坐標(biāo)的方向。如對(duì)下面的迷宮，輸出的一條通路為：（1，1，

21、1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），.迷宮約定， x方向?yàn)樾蟹较?，y方向?yàn)榱蟹较颍詫m開始坐標(biāo)(左上角)為（1,1）。*include <stdio.h>*include <stdlib.h>*include <malloc.h>struct node int sign;/標(biāo)識(shí),0什么都不在,1在open中,2在closed中 int flag;/標(biāo)志位 0/1,0可以走,1不可以走 int f,g,h;/判斷函數(shù) int x,y;/坐標(biāo) int old;/是否old節(jié)點(diǎn),0非,1是;struct link node fno

22、de; link *next; link *pri;link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;int maze_flag77= 0,1,0,0,0,0,0, 0,1,0,1,0,1,0, 0,1,0,0,0,1,0, 0,1,0,1,0,1,0, 0,0,0,1,0,0,0, 1,1,0,1,0,1,0, 0,0,0,0,0,1,0;/表示迷宮的數(shù)組,0可以走,1不可以走node maze77;int judge(node n)/判斷函數(shù),判斷n節(jié)點(diǎn)是否可以走 if(n.flag=1) return(1); else return(

23、0);void in_open(node n)/將n節(jié)點(diǎn)放入open表 p=open; while(p->next!=open) if(n.f>=p->fnode.f) p->next->pri=(link *)malloc(sizeof(link); p->next->pri->pri=p; p=p->next; p->pri->next=p; p->pri->pri->next=p->pri; p=p->pri; p->fnode.flag=n.flag; p->fnode.f=n.

24、f; p->fnode.g=n.g; p->fnode.h=n.h; p->fnode.x=n.x; p->fnode.y=n.y; p->fnode.old=n.old; p->fnode.sign=n.sign=1; else p=p->next; open->pri=(link *)malloc(sizeof(link); open->pri->pri=p; open->pri->next=open; p->next=open->pri; p=p->next; p->fnode.flag=n.

25、flag; p->fnode.f=n.f; p->fnode.g=n.g; p->fnode.h=n.h; p->fnode.x=n.x; p->fnode.y=n.y; p->fnode.old=n.old; p->fnode.sign=n.sign=1;void out_open(node n)/將n節(jié)點(diǎn)從open表中移出 p=open; while(p->next!=open) if(n.f=p->fnode.f) link *p1; p1=p->next; p->next=p->next->next; p-&

26、gt;next->pri=p; free(p1); n.sign=0; else p=p->next; void in_closed(node n)/將n節(jié)點(diǎn)放入closed表 while(q->next!=closed) if(n.f>=q->fnode.f) q->next->pri=(link *)malloc(sizeof(link); q->next->pri->pri=q; q=q->next; q->pri->next=p; q->pri->pri->next=q->pri; q

27、=q->pri; q->fnode.flag=n.flag; q->fnode.f=n.f; q->fnode.g=n.g; q->fnode.h=n.h; q->fnode.x=n.x; q->fnode.y=n.y; q->fnode.old=n.old; q->fnode.sign=n.sign=2; else q=q->next; closed->pri=(link *)malloc(sizeof(link); closed->pri->pri=q; closed->pri->next=close

28、d; q->next=closed->pri; q=q->next; q->fnode.flag=n.flag; q->fnode.f=n.f; q->fnode.g=n.g; q->fnode.h=n.h; q->fnode.x=n.x; q->fnode.y=n.y; q->fnode.old=n.old; q->fnode.sign=n.sign=2;void out_closed(node n)/將n節(jié)點(diǎn)從closed表中移出 q=closed; while(q->next!=closed) if(n.f=q-&g

29、t;fnode.f) link *q1; q1=q->next; q->next=q->next->next; q->next->pri=q; free(q1); n.sign=0; else q=q->next; void in_bestnode(node n)/將n節(jié)點(diǎn)設(shè)為bestnode節(jié)點(diǎn) while(r->next!=bestnode) if(n.f>=r->fnode.f) r->next->pri=(link *)malloc(sizeof(link); r->next->pri->pri=

30、r; r=r->next; r->pri->next=r; r->pri->pri->next=r->pri; r=r->pri; r->fnode.flag=n.flag; r->fnode.f=n.f; r->fnode.g=n.g; r->fnode.h=n.h; r->fnode.x=n.x; r->fnode.y=n.y; r->fnode.old=n.old; else r=r->next; bestnode->pri=(link *)malloc(sizeof(link); be

31、stnode->pri->pri=r; bestnode->pri->next=bestnode; r->next=bestnode->pri; r=r->next; r->fnode.flag=n.flag; r->fnode.f=n.f; r->fnode.g=n.g; r->fnode.h=n.h; r->fnode.x=n.x; r->fnode.y=n.y; r->fnode.old=n.old;void out_bestnode(node n)/將n節(jié)點(diǎn)的bestnode去掉 r=bestnode;

32、 while(r->next!=bestnode) if(n.f=p->fnode.f) link *r1; r1=r->next; r->next=r->next->next; r->next->pri=r; free(r1); else r=r->next; void in_successor(node n)/將n節(jié)點(diǎn)設(shè)置為successor節(jié)點(diǎn) s=successor; while(s->next!=successor) if(n.f>=s->fnode.f) s->next->pri=(link *)m

33、alloc(sizeof(link); s->next->pri->pri=s; s=p->next; s->pri->next=s; s->pri->pri->next=s->pri; s=s->pri; s->fnode.flag=n.flag; s->fnode.f=n.f; s->fnode.g=n.g; s->fnode.h=n.h; s->fnode.x=n.x; s->fnode.y=n.y; s->fnode.old=n.old; else s=s->next; s

34、uccessor->pri=(link *)malloc(sizeof(link); successor->pri->pri=s; successor->pri->next=successor; s->next=successor->pri; s=s->next; s->fnode.flag=n.flag; s->fnode.f=n.f; s->fnode.g=n.g; s->fnode.h=n.h; s->fnode.x=n.x; s->fnode.y=n.y; s->fnode.old=n.old;v

35、oid out_successor(node n)/將n節(jié)點(diǎn)的successor去掉 s=successor; while(s->next!=successor) if(n.f=p->fnode.f) link *s1; s1=s->next; s->next=s->next->next; s->next->pri=s; free(s1); else s=s->next; void print(link *n)/輸出link類型的表n link *forprint; forprint=n; printf("the key is &

36、quot;); while(forprint->next!=n) printf("(%d,%d)n",forprint->fnode.x,forprint->fnode.y);int main()/初始化部分/這部分的功能是將二維的整形數(shù)組賦值給node型的二維數(shù)組 int i=0,j=0; for(i=0;i<7;i+) for(j=0;j<7;j+) mazeij.x=i; mazeij.y=j; mazeij.flag=maze_flagij; if(mazeij.flag=0) mazeij.h=6-i+6-j; mazeij.sign

37、=mazeij.f=mazeij.g=mazeij.old=0; else mazeij.h=-1; for(i=0;i<7;i+)/輸出迷宮示意圖 for(j=0;j<7;j+) printf("%2d",maze_flagij); printf("n"); /這部分的功能是將open,closed,bestnode表初始化,都置為空表 p=open=(link *)malloc(sizeof(link); open->next=open; open->pri=open; q=closed=(link *)malloc(size

38、of(link); closed->next=closed; closed->pri=closed; r=bestnode=(link *)malloc(sizeof(link); bestnode->next=bestnode; bestnode->pri=bestnode;/將第一個(gè)元素即(0,0)節(jié)點(diǎn)放入open表,開始算法 in_open(maze00); maze00.f=maze00.h; link *s2; s2=successor; if(open->next!=open)/open表為空時(shí)則失敗退出 while(1) in_bestnode(op

39、en->fnode);/將open表的第一個(gè)元素放入bestnode中 in_closed(mazeopen->fnode.xopen->fnode.y);/將open表的第一個(gè)元素放入closed中 mazeopen->fnode.xopen->fnode.y.g+;/將open表的第一個(gè)元素的g值加一,表示已經(jīng)走了一步 out_open(mazeopen->fnode.xopen->fnode.y);/將open表的第一個(gè)元素刪除 if(bestnode->fnode.x=6&&bestnode->fnode.y=6)/

40、若bestnode是目標(biāo)節(jié)點(diǎn),則成功退出 printf("succes!nthen print the key:n"); print(closed); break; else/若bestnode不是目標(biāo)節(jié)點(diǎn),則擴(kuò)展其臨近可以走的節(jié)點(diǎn)為successor if(i=0|j=0|i=6|j=6) if(i=0&&j=0)/若為(0,0),則判斷右邊和下邊的元素 if(judge(mazeij+1)=0) in_successor(mazeij+1); if(judge(mazei+1j)=0) in_successor(mazei+1j); else if(i=

41、0&&j=6)/若為(0,6),則判斷左邊和下邊的元素 if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge(mazei+1j)=0) in_successor(mazei+1j); else if(i=6&&j=0)/若為(6,0),則判斷左邊和上邊的元素 if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge(mazeij-1)=0) in_successor(mazeij-1); else if(i=6&&j=6)/若為(6,6),

42、則判斷左邊和上邊的元素 if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge(mazeij-1)=0) in_successor(mazeij-1); else if(i=0)/若為第一行的元素(不在角上),則判斷左邊,下邊和右邊 if(judge(mazeij+1)=0) in_successor(mazeij+1); if(judge(mazeij-1)=0) in_successor(mazeij-1); if(judge(mazei+1j)=0) in_successor(mazei+1j); else if(i=6)/若為第七行

43、的元素(不在角上),則判斷左邊,上邊和右邊 if(judge(mazeij+1)=0) in_successor(mazeij+1); if(judge(mazeij-1)=0) in_successor(mazeij-1); if(judge(mazei-1j)=0) in_successor(mazei-1j); else if(j=0)/若為第一列的元素(不在角上),則判斷右邊,下邊和上邊 if(judge(mazei+1j)=0) in_successor(mazei+1j); if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge

44、(mazeij+1)=0) in_successor(mazeij+1); else if(j=6)/若為第七列的元素(不在角上),則判斷左邊,上邊和上邊 if(judge(mazei+1j)=0) in_successor(mazei+1j); if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge(mazeij-1)=0) in_successor(mazeij-1); else/若為中將的元素,則判斷四個(gè)方向的節(jié)點(diǎn) if(judge(mazeij-1)=0) in_successor(mazeij-1); if(judge(mazei

45、j+1)=0) in_successor(mazeij+1); if(judge(mazei-1j)=0) in_successor(mazei-1j); if(judge(mazei+1j)=0) in_successor(mazei+1j); while(s2->next!=successor)/對(duì)所有的successor節(jié)點(diǎn)進(jìn)行下列操作 mazes2->fnode.xs2->fnode.y.g=bestnode->fnode.g+bestnode->fnode.h;/計(jì)算g(suc)=g(bes)+h(bes,suc) if(s2->fnode.sig

46、n=1)/若在open表中,則置為old,記下較小的g,并從open表中移出,放入closed表中 s2->fnode.old=1; if(s2->fnode.g<mazes2->fnode.xs2->fnode.y.g) mazes2->fnode.xs2->fnode.y.g=s2->fnode.g; mazes2->fnode.xs2->fnode.y.f=mazes2->fnode.xs2->fnode.y.g+mazes2->fnode.xs2->fnode.y.h; out_open(mazes2-

47、>fnode.xs2->fnode.y); in_closed(mazes2->fnode.xs2->fnode.y); mazes2->fnode.xs2->fnode.y.old=0; else continue; else if(s2->fnode.sign=2)/若在closed表中,則置為old,記下較小的g,并將old從closed表中移出,將較小的g的節(jié)點(diǎn)放入closed表中 s2->fnode.old=1; if(s2->fnode.g<mazes2->fnode.xs2->fnode.y.g) mazes

48、2->fnode.xs2->fnode.y.g=s2->fnode.g; mazes2->fnode.xs2->fnode.y.f=mazes2->fnode.xs2->fnode.y.g+mazes2->fnode.xs2->fnode.y.h; out_closed(mazes2->fnode.xs2->fnode.y); in_closed(mazes2->fnode.xs2->fnode.y); mazes2->fnode.xs2->fnode.y.old=0; else continue; el

49、se/若即不再open表中也不在closed表中,則將此節(jié)點(diǎn)放入open表中,并計(jì)算此節(jié)點(diǎn)的f值 in_open(mazes2->fnode.xs2->fnode.y); mazes2->fnode.xs2->fnode.y.f=mazes2->fnode.xs2->fnode.y.g+mazes2->fnode.xs2->fnode.y.h; s2=s2->next; s2=successor; else printf("error!This maze does not have the answer!"); retu

50、rn(0); 實(shí)驗(yàn)內(nèi)容：以一個(gè)m × n的長(zhǎng)方陣表示迷宮，0 和1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)順序或鏈表做存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i, j, d)的形式輸出，其中：(i, j)表示迷宮的坐標(biāo)，d 表示走到下一坐標(biāo)的方向。如對(duì)下面的迷宮，輸出的一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），.迷宮約定， x 方向?yàn)樾蟹较?，y 方向?yàn)榱蟹较?，迷宮開始坐標(biāo)(左上角)為（1,1）?；鞠嗤?incl

51、ude <stdio.h> *include <stdlib.h> *include <malloc.h> typedef struct QElemType  int x,y; struct QElemType *parent;/用于存儲(chǔ)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)  QElemType; typedef struct QNode/隊(duì)列節(jié)點(diǎn)  QElemType *data; struct QNode *next;  QNode, *QueuePtr;

52、 typedef struct  QueuePtr front; QueuePtr rear;  LinkQueue; void InitQueue(LinkQueue *Q)/創(chuàng)建隊(duì)列  Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode); Q->rear->next = NULL; /Q->front=Q->rear=NULL;  void EnQueue(LinkQueue *Q, QEle

53、mType *e)/將元素入隊(duì)  QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p;  QElemType *DeQueue(LinkQueue *Q)/將元素出對(duì)  QElemType *e; QueuePtr p; p=Q->front->next; e=p->

54、data; Q->front->next=p->next; if(Q->rear=p) Q->rear=Q->front; free(p); return (e);  int QueueEmpty(LinkQueue *Q)/判斷隊(duì)列是否為空  if(Q->front=Q->rear ) return 1; else return 0;  QElemType *NextPos(QElemType *e,int

55、 i)/節(jié)點(diǎn)的下一個(gè)位置  QElemType *t = (QElemType *)malloc(sizeof(QElemType); *t = *e; switch(i)  case 1:t->y=t->y+1;break; case 2:t->x=t->x+1;break; case 3:t->y=t->y-1;break; case 4:t->x=t->x-1;break;  return (t);  QElem

56、Type *MazePath(int maze10,LinkQueue *Q)/迷宮函數(shù)  int i; QElemType *e, *p; e = (QElemType *)malloc(sizeof(QElemType); / InitQueue(&Q); e->x=1;/入口位置，即為第一個(gè)節(jié)點(diǎn) e->y=1; e->parent=NULL; /第一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)賦值為空 EnQueue(Q, e);/將第一個(gè)節(jié)點(diǎn)入隊(duì) while(!QueueEmpty(Q)

57、  e=DeQueue(Q); /把元素出對(duì)，并賦值給e if(e->x=8&&e->y=8)/出口位置，直接返回最后一個(gè)節(jié)點(diǎn) return e; for(i=1;i<=4;i+) /將四個(gè)方向能走通的位置的節(jié)點(diǎn)入隊(duì)，并將其的parent指向上一個(gè)節(jié)點(diǎn) p=NextPos(e,i); p->parent=e; if(mazep->xp->y=1)  mazep->xp->y=2; EnQueue(Q,p);

58、60; else  free(p); p = NULL;    printf("zhao bu dao");/找不到路徑 return NULL;  void main()/主函數(shù)  LinkQueue Q; QElemType *p, *t; int maze1010=/其中1為能走通 0,0,0,0,0,0,0,0,0,0, 0,1,1,0,1,1,1,0,1,0, 0,1,1,0,1,1,1

59、,0,1,0, 0,1,1,1,1,0,0,1,1,0, 0,1,0,0,0,1,1,1,1,0, 0,1,1,1,0,1,1,1,1,0, 0,1,0,1,1,1,0,1,1,0, 0,1,0,0,0,1,0,0,1,0, 0,0,1,1,1,1,1,1,1,0, 0,0,0,0,0,0,0,0,0,0  InitQueue(&Q); p=MazePath(maze,&Q);/e即為最后一個(gè)節(jié)點(diǎn) while(p)/回溯尋找路徑  printf(&q

60、uot;(%d,%d),",p->x,p->y); t = p->parent; free(p); p = t;  getchar();  實(shí)驗(yàn)四實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)編寫一個(gè)字符串操作函數(shù)int Index( String S1, String S2, String S3, int start_Pos)，實(shí)現(xiàn)在字符母串S1中對(duì)子串S2位置的定位,并把該位置的信息返回。要求：第一個(gè)字符的下標(biāo)從1開始，如果沒有匹配項(xiàng)，返回-1.背景知識(shí)： 字符串結(jié)構(gòu)的實(shí)現(xiàn)及匹配操作目的要求：1. 掌握字符串結(jié)構(gòu)的特點(diǎn)；2.

61、 掌握字符串匹配操作的意義及實(shí)現(xiàn)；*include<stdio.h>int StrLen(char s)    int i = 0;    while(s!= '0')            i+;        return i;int FindeStrIndex(char *s1, char *s2)    int i;    int j;    int index =0;    int count = StrLen(s2); /得到s2有多少個(gè)字符    for(i = 0; s1!= '0' i+)