經(jīng)典數(shù)據(jù)結構上機題—答案

數(shù)據(jù)結構上機實驗題目實驗一 線性表的順序存儲結構 實驗學時 2學時 背景知識:順序表的插入、刪除及應用。 目的要求： 1掌握順序存儲結構的特點。 2掌握順序存儲結構的常見算法。 實驗內(nèi)容 1輸入一組整型元素序列，建立順序表。 2實現(xiàn)該順序表的遍歷。 3在該順序表中進行順序查找某一元素,查找成功返回1,否則返回0。 4判斷該順序表中元素是否對稱,對稱返回1,否則返回0。 5實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。 6輸入整型元素序列利用有序表插入算法建立一個有序表。 7利用算法6建立兩個非遞減有序表并把它們合并成一個非遞減有序表。 8. 利用該順序結構實現(xiàn)循環(huán)隊列的入隊、出隊操作。8編寫一個主函數(shù),調(diào)試上述算法。 #include #include #define OVERFLOW 0#define MAXSIZE 100typedef int ElemType;typedef struct listElemType elemMAXSIZE; int length;Sqlist;void Creatlist(Sqlist &L)int i; printf(請輸入順序表的長度：);/輸入一組整型元素序列，建立一個順序表。 scanf(%d,&L.length); for(i=0;iL.length;i+) scanf(%d,&L.elemi);void printlist(Sqlist &L)/以輸出的形式實現(xiàn)對該順序表的遍歷int i; for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n);void Searchlist(Sqlist &L,int x)/在順序表中進行順序查找某一元素x，查找成功則返回其存儲位置i，否則返回錯誤信息int i,k=-1; for(i=0;i=i;j-)L.elemj=L.elemj-1; L.elemj=x; L.length+;void Delete(Sqlist &L,int i)/刪除順序表中第i個元素int j;for(j=i;jL.length;j+)L.elemj-1=L.elemj;L.length-;void Insert(Sqlist &L,int x)/輸入一個元素x，把它插入到有序表中，使順序表依然有序。int i,j; if(L.length=MAXSIZE) exit(OVERFLOW);/表滿，不能插入 for(i=1;i=L.length&L.elemi-1=i;j-) L.elemj=L.elemj-1; L.elemi-1=x; L.length+;void Creatlist_sorted(Sqlist &L)/利用有序表插入算法建立一個有序表int i,num; ElemType x; L.length=0; printf(請輸入順序表的長度：); scanf(%d,&num); for(i=1;i=num;i+) scanf(%d,&x); Insert(L,x); void Merger(Sqlist &p,Sqlist &r,Sqlist &c) /建立兩個非遞減有序表，并把它們合并成一個非遞減有序表 ElemType *a,*b,i=0,j=0,k=0; a=&p.elem0; b=&r.elem0; c.length=p.length+r.length; while(ip.length&j=*b) c.elemk=*b;b+;k+;j+; else c.elemk=*a;a+;k+;i+; if(j=r.length) for(;kc.length;k+) c.elemk=*a;a+; else if(i=p.length) for(;kc.length;k+)c.elemk=*b;b+;void main()Sqlist L,M,N; int x,i,n; printf(1.建立一個順序表.n); printf(2.以輸出的形式對該順序表遍歷.n); printf(3.在順序表中進行順序查找某一元素x.n); printf(4.在順序表的第i個位置上插入一個元素x.n); printf(5.刪除順序表中第i個元素.n); printf(6.利用有序表插入算法建立一個有序表.n); printf(7.建立兩個非遞減有序表，并把它們合并成一個非遞減有序表.n); printf(8.輸入一個元素x，把它插入到有序表中，使順序表依然有序.n); while(1) printf(請選擇：); scanf(%d,&n); switch(n) case 1:Creatlist(L);break; case 2:printlist(L);break; case 3:printf(請輸入要查找的元素x:); scanf(%d,&x); Searchlist(L,x);break; case 4:printf(請輸入要插入的位置i:); scanf(%d,&i); if(iL.length+1) printf(error!n);break; printf(請輸入要插入的值x:); scanf(%d,&x); Inseri(L,i,x); printlist(L);break; case 5:printf(請輸入要刪去的元素的位置i:); scanf(%d,&i); if(iL.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(請輸入要插入的元素x:); scanf(%d,&x); Insert(L,x); printlist(L);break; 實驗二 鏈式存儲結構（一）-單向鏈表的有關操作 實驗學時 3學時 背景知識：單向鏈表的插入、刪除及應用。 目的要求 1掌握單向鏈表的存儲特點及其實現(xiàn)。 2掌握單向鏈表的插入、刪除算法及其應用算法的程序實現(xiàn)。 實驗內(nèi)容 1隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結點的單向鏈表（無序）。 2遍歷單向鏈表。 3把單向鏈表中元素逆置（不允許申請新的結點空間）。 4在單向鏈表中刪除所有的偶數(shù)元素結點。 5編寫在非遞減有序鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單向鏈表。 6利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞增鏈表。 7利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞減鏈表。 8利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。* 9采用單向鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相加并輸出結果。10在主函數(shù)中設計一個簡單的菜單，分別調(diào)試上述算法。 *11綜合訓練：利用鏈表實現(xiàn)一個班級學生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠實現(xiàn)將數(shù)據(jù)存儲到文件中）/*單向鏈表的有關操作示例*/*類型定義及頭文件部分,文件名為sllink.h*/ #include #include typedef int ElemType;/元素實際類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /定義結點、指針類型名 /頭插法建立無序鏈表 void CreateList(LinkList &L) LinkList p; ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(頭插法建立鏈表，以0結束n); scanf(%d,&e); 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-datanext;/*查找插入位置*/ s-next=p-next; /*插入語句*p結點后插入*s結點*/ p-next=s; /*建立遞增有序的單向鏈表*/ void Create_Sort(LinkList &L) ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(建立有序表，輸入任意個整型數(shù)據(jù)以0結束n); scanf(%d,&e); while(e) Insert_Sort(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(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; /*兩個非遞減有序單向鏈表合并后仍為非遞減序列*/ 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-datadata) s=p;p=p-next; else s=q;q=q-next; rear-next=s;/*較小元素插入表尾*/ rear=rear-next; if (p) rear-next=p; else rear-next=q實驗三 迷宮問題求解實驗學時 3學時 背景知識：棧的操作。 目的要求 1掌握棧的存儲特點及其實現(xiàn)。 2掌握棧的出棧和入棧操作。實驗內(nèi)容： 以一個mxn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。要求：首先實現(xiàn)一個順序或鏈表做存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i, j, d)的形式輸出，其中：(i, j)表示迷宮的坐標，d表示走到下一坐標的方向。如對下面的迷宮，輸出的一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），.迷宮約定， x方向為行方向，y方向為列方向，迷宮開始坐標(左上角)為（1,1）。 #include #include #include struct node int sign;/標識,0什么都不在,1在open中,2在closed中 int flag;/標志位 0/1,0可以走,1不可以走 int f,g,h;/判斷函數(shù) int x,y;/坐標 int old;/是否old節(jié)點,0非,1是;struct link node fnode; 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é)點是否可以走 if(n.flag=1) return(1); else return(0);void in_open(node n)/將n節(jié)點放入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.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.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é)點從open表中移出 p=open; while(p-next!=open) if(n.f=p-fnode.f) link *p1; p1=p-next; p-next=p-next-next; p-next-pri=p; free(p1); n.sign=0; else p=p-next; void in_closed(node n)/將n節(jié)點放入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=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=closed; 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é)點從closed表中移出 q=closed; while(q-next!=closed) if(n.f=q-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é)點設為bestnode節(jié)點 while(r-next!=bestnode) if(n.f=r-fnode.f) r-next-pri=(link *)malloc(sizeof(link); r-next-pri-pri=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); bestnode-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é)點的bestnode去掉 r=bestnode; 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é)點設置為successor節(jié)點 s=successor; while(s-next!=successor) if(n.f=s-fnode.f) s-next-pri=(link *)malloc(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; successor-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;void out_successor(node n)/將n節(jié)點的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 ); 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;i7;i+) for(j=0;j7;j+) mazeij.x=i; mazeij.y=j; mazeij.flag=maze_flagij; if(mazeij.flag=0) mazeij.h=6-i+6-j; mazeij.sign=mazeij.f=mazeij.g=mazeij.old=0; else mazeij.h=-1; for(i=0;i7;i+)/輸出迷宮示意圖 for(j=0;jnext=open; open-pri=open; q=closed=(link *)malloc(sizeof(link); closed-next=closed; closed-pri=closed; r=bestnode=(link *)malloc(sizeof(link); bestnode-next=bestnode; bestnode-pri=bestnode;/將第一個元素即(0,0)節(jié)點放入open表,開始算法 in_open(maze00); maze00.f=maze00.h; link *s2; s2=successor; if(open-next!=open)/open表為空時則失敗退出 while(1) in_bestnode(open-fnode);/將open表的第一個元素放入bestnode中 in_closed(mazeopen-fnode.xopen-fnode.y);/將open表的第一個元素放入closed中 mazeopen-fnode.xopen-fnode.y.g+;/將open表的第一個元素的g值加一,表示已經(jīng)走了一步 out_open(mazeopen-fnode.xopen-fnode.y);/將open表的第一個元素刪除 if(bestnode-fnode.x=6&bestnode-fnode.y=6)/若bestnode是目標節(jié)點,則成功退出 printf(succes!nthen print the key:n); print(closed); break; else/若bestnode不是目標節(jié)點,則擴展其臨近可以走的節(jié)點為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=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),則判斷左邊和上邊的元素 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)/若為第七行的元素(不在角上),則判斷左邊,上邊和右邊 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(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/若為中將的元素,則判斷四個方向的節(jié)點 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); if(judge(mazei+1j)=0) in_successor(mazei+1j); while(s2-next!=successor)/對所有的successor節(jié)點進行下列操作 mazes2-fnode.xs2-fnode.y.g=bestnode-fnode.g+bestnode-fnode.h;/計算g(suc)=g(bes)+h(bes,suc) if(s2-fnode.sign=1)/若在open表中,則置為old,記下較小的g,并從open表中移出,放入closed表中 s2-fnode.old=1; if(s2-fnode.gfnode.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-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é)點放入closed表中 s2-fnode.old=1; if(s2-fnode.gfnode.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_closed(mazes2-fnode.xs2-fnode.y); in_closed(mazes2-fnode.xs2-fnode.y); mazes2-fnode.xs2-fnode.y.old=0; else continue; else/若即不再open表中也不在closed表中,則將此節(jié)點放入open表中,并計算此節(jié)點的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!); return(0); 實驗內(nèi)容：以一個m n的長方陣表示迷宮，0 和1 分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。要求：首先實現(xiàn)一個順序或鏈表做存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i, j, d)的形式輸出，其中：(i, j)表示迷宮的坐標，d 表示走到下一坐標的方向。如對下面的迷宮，輸出的一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），.迷宮約定， x 方向為行方向，y 方向為列方向，迷宮開始坐標(左上角)為（1,1）。基本相同；#include #include #include typedef struct QElemTypeint x,y;struct QElemType *parent;/用于存儲節(jié)點的前一個節(jié)點 QElemType;typedef struct QNode/隊列節(jié)點QElemType *data;struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear; LinkQueue;void InitQueue(LinkQueue *Q)/創(chuàng)建隊列Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);Q-rear-next = NULL;/Q-front=Q-rear=NULL;void EnQueue(LinkQueue *Q, QElemType *e)/將元素入隊QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;QElemType *DeQueue(LinkQueue *Q)/將元素出對QElemType *e;QueuePtr p;p=Q-front-next;e=p-data;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);return (e);int QueueEmpty(LinkQue