數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告25691

...wd......wd......wd...數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告書學(xué)校青島科技大學(xué)學(xué)號姓名指導(dǎo)教師劉勇課程設(shè)計(jì)的名稱：學(xué)生成績管理問題描述：學(xué)生成績管理是學(xué)校教務(wù)管理的重要組成局部，其處理信息量很大，該題目是對學(xué)生的成績管理作一個簡單的模擬，其中學(xué)生信息包括：學(xué)號、姓名與成績。成績分為課程1成績、課程2成績、課程3成績和總成績。要求設(shè)計(jì)一個簡易的成績管理系統(tǒng)，輸入各門功課的成績后能自動求出總成績，并通過菜單項(xiàng)選擇擇操作方式完成以下功能：登記學(xué)生成績；②查詢學(xué)生成績；插入學(xué)生成績；④刪除學(xué)生成績；按總成績降序排序?；疽螅涸擃}目涉及到單鏈表的各種操作，包括單鏈表的建立、結(jié)點(diǎn)的查找、插入、刪除等基本運(yùn)算。首先建立學(xué)生成績單鏈表，鏈表中每個結(jié)點(diǎn)由4個域組成，分別為：學(xué)號、姓名、成績、存放下一個結(jié)點(diǎn)地址的next域。然后將要求完成的四項(xiàng)功能寫成四個函數(shù)，登記學(xué)生成績對應(yīng)建立學(xué)生單鏈表的功能，后三個功能分別對應(yīng)單鏈表的查詢、插入與刪除三大基本操作。算法思想：Creat()函數(shù)算法思想：從0至n循環(huán)輸入n個同學(xué)的三科成績，并且計(jì)算總成績。Inquiry()函數(shù)算法思想：將學(xué)號與已輸入的所有學(xué)號做比較，一旦一樣則輸出該學(xué)號信息，否則顯示沒有該學(xué)生信息。Insert()函數(shù)算法思想：生成一個新節(jié)點(diǎn)，然后將其接到原有鏈表尾部。Delete()函數(shù)算法思想：通過ID找到該節(jié)點(diǎn)，并刪去該節(jié)點(diǎn)。Sort(函數(shù)算法思想：利用排序算法對每一個節(jié)點(diǎn)作比較并更換其在鏈表中的位置順序。模塊劃分

〔1〕LinkListCreat(LinkListT,intn)其功能是創(chuàng)造節(jié)點(diǎn)，錄入成績。〔2〕voidInquiry(LinkListT)其功能是查詢與ID一致的學(xué)生信息并展示出來?！?〕voidInsert(LinkListT,intn)其功能是添加假設(shè)干個學(xué)生的成績信息?！?〕voidDelete(LinkListT)其功能是刪除假設(shè)干個學(xué)生的成績信息?！?〕voidSort(LNode*p)其功能是排序并展示假設(shè)干個學(xué)生的成績信息。數(shù)據(jù)構(gòu)造：

數(shù)據(jù)類型LNode定義如下：

typedefstructLNode{intID;charname[20];intscore1;intscore2;intscore3;inttotal;structLNode*next;}LNode,*LinkList;源程序：源代碼//main.c#include<stdio.h>#include<stdlib.h>typedefstructLNode{intID;charname[20];intscore1;intscore2;intscore3;inttotal;structLNode*next;}LNode,*LinkList;LinkListCreat(LinkListT,intn);voidDelete(LinkListT);voidInquiry(LinkListT);voidInsert(LinkListT,intn);voidSort(LNode*p);voidInsert(LinkListT,intn){inti;LNode*r=T,*p;while((r->next)!=NULL){r=r->next;}for(i=0;i<n;i++){p=(LNode*)malloc(sizeof(LNode));printf("Pleaseenterthestudent'sstudentID:");scanf("%d",&p->ID);printf("Pleaseenterthestudent'sname:");scanf("%s",p->name);printf("Pleaseenterthestudent'sscore1:");scanf("%d",&p->score1);printf("Pleaseenterthestudent'sscore2:");scanf("%d",&p->score2);printf("Pleaseenterthestudent'sscore3:");scanf("%d",&p->score3);p->total=p->score1+p->score2+p->score3;printf("Thetotalscoreis%d\n",p->total);p->next=NULL;r->next=p;r=p;}printf("\nInsertiscomplete!");}voidInquiry(LinkListT){intid;printf("PleaseenterthestudentIDyouwanttoinquireabout:");scanf("%d",&id);LNode*p=T;p=p->next;while(p!=NULL){if(p->ID==id){printf("\nThestudentscoresinformationhasbeensuccessfullyinquired!\n");printf("ID:%d\nName:%s\nScore1:%d\nScore2:%d\nScore3:%d\n",p->ID,p->name,p->score1,p->score2,p->score3);break;}else{p=p->next;}}if(!p)printf("Sorry!Didnotinquirythestudentscoresinformation!");}voidDelete(LinkListT){intid,flag=1;printf("PleaseenterthestudentIDyouwanttodeleteabout:");scanf("%d",&id);LNode*p=T;//LNode*q;while((p->next)!=NULL){if(p->next->ID==id){//q=p->next;p->next=p->next->next;//deleteq;printf("\nThestudentscoresinformationhasbeensuccessfullydeleted!\n");flag=0;break;}else{p=p->next;}}if(flag)printf("Sorry!Didnotdeletethestudentscoresinformationyouwanttodelete!");}voidSort(LNode*p){LNode*r,*qian,*hou;qian=p->next;hou=qian->next;while(hou)if(qian->total>=hou->total){qian=hou;hou=hou->next;}//ifelse{r=p;while(r->next->total>hou->total)r=r->next;qian->next=hou->next;hou->next=r->next;r->next=hou;hou=qian->next;}//elsep=p->next;inti=1;while(p){printf("Num:%d\nID:%d\nName:%s\nScore1:%d\nScore2:%d\nScore3:%d\ntotal:%d\n\n",i,p->ID,p->name,p->score1,p->score2,p->score3,p->total);p=p->next;i++;}}LinkListCreat(LinkListT,intn){LNode*p,*r;inti;T=(LNode*)malloc(sizeof(LNode));T->next=NULL;r=T;for(i=0;i<n;i++){p=(LNode*)malloc(sizeof(LNode));printf("Pleaseenterthestudent'sstudentID:");scanf("%d",&p->ID);printf("Pleaseenterthestudent'sname:");scanf("%s",p->name);printf("Pleaseenterthestudent'sscore1:");scanf("%d",&p->score1);printf("Pleaseenterthestudent'sscore2:");scanf("%d",&p->score2);printf("Pleaseenterthestudent'sscore3:");scanf("%d",&p->score3);p->total=p->score1+p->score2+p->score3;printf("Thetotalscoreis%d\n",p->total);p->next=NULL;r->next=p;r=p;}returnT;}intmain(){LNode*p;intn;while(1){system("cls");printf("StudentScoresManagement\n\n");printf("1-Enterthestudent'sscore\n");printf("2-Querythestudent'sscore\n");printf("3-Insertthestudent'sscore\n");printf("4-Deletethestudent'sscore\n");printf("5-Sortthestudent'sscore\n");printf("0-Exitsystem\n\n");printf("Pleaseenteranumberselection(0-5):");intchoice;scanf("%d",&choice);system("cls");if(choice==0)exit(0);switch(choice){case1:printf("Pleaseenterthenumberofstudentsyouwanttoenteryourstudent'sscores:");scanf("%d",&n);p=Creat(p,n);printf("\n\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",&n);if(n)break;case2:printf("Pleaseenterthenumberofstudentsyouwanttoqueryyourstudent'sscores:");scanf("%d",&n);inti=0;while(i<n){Inquiry(p);i++;}printf("\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",&n);break;case3:printf("Pleaseenterthenumberofstudentsyouwanttoinsertyourstudent'sscores:");scanf("%d",&n);Insert(p,n);printf("\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",&n);break;case4:printf("Pleaseenterthenumberofstudentsyouwanttodeleteyourstudent'sscores:");scanf("%d",&n);i=0;while(i<n){Delete(p);i++;}printf("\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",&n);break;case5:Sort(p);printf("\nPleaseenteryourchoice(1):");printf("1-Esc");scanf("%d",&n);break;default:break;}}return0;}7.測試情況：截圖：

程序輸出為：

Num:1ID:1Name:n1Score1:78Score2:89Score3:84total:251Num:2ID:3Name:n3Score1:68Score2:89Score3:90total:247課程設(shè)計(jì)的名稱：停車場的管理問題描述：設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列〔大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端〕，假設(shè)車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)展管理的模擬程序?；疽螅壕C合利用棧和隊(duì)列模擬停車場管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問題。以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)展模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)〞或“離去〞信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)展操作后的輸出數(shù)據(jù)為：假設(shè)是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；假設(shè)是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用〔在便道上停留的時間不收費(fèi)〕。棧以順序構(gòu)造實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲構(gòu)造實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時刻。算法思想：停車場運(yùn)用棧的算法思想管理車輛信息；便道運(yùn)用隊(duì)列的算法思想管理等待進(jìn)入停車場的車輛信息；臨時停放讓路的車輛信息也用隊(duì)列算法思想管理。模塊劃分：voidPRINT(CarNode*p,introom其功能為打印出場車的信息voidArrive(SeqStackCar*Enter,LinkQueueCar*W)其功能為記錄進(jìn)場車和等待進(jìn)場車信息voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)其功能為記錄出場車信息voidList1(SeqStackCar*S)其功能為顯示存車信息5.數(shù)據(jù)構(gòu)造：〔1〕數(shù)據(jù)類型Time定義如下：typedefstructtime{inthour;intmin;}Time;〔2〕數(shù)據(jù)類型CarNode定義如下：typedefstructnode{charnum[10];Timereach;Timeleave;}CarNode;〔3〕數(shù)據(jù)類型SeqStackCar定義如下：typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;〔4〕數(shù)據(jù)類型QueueNode定義如下：typedefstructcar{CarNode*data;structcar*next;}QueueNode;〔5〕數(shù)據(jù)類型LinkQueueCar定義如下：typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;6.源程序：源代碼#include<stdio.h>#include<stdlib.h>#include<windows.h>#defineprice0.15#definemax2//=================================================================================================intflag;//=================================================================================================typedefstructtime{inthour;intmin;}Time;typedefstructnode{longnum;Timereach;Timeleave;}CarNode;//車輛信息結(jié)點(diǎn)typedefstructNODE{CarNode*stack[10];inttop;}SeqStackCar;//模擬車場typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;//模擬通道//=================================================================================================voidInitStack(SeqStackCar*s)//初始化棧{inti;s->top=0;for(i=0;i<=max;i++)s->stack[s->top]=NULL;}voidInitQueue(LinkQueueCar*Q)//初始化便道{Q->head=(QueueNode*)malloc(sizeof(QueueNode));if(Q->head!=NULL){Q->head->next=NULL;Q->rear=Q->head;return(1);}elsereturn(-1);}voidPRINT(CarNode*p,introom)//打印出場車的信息{intA1,A2,B1,B2;printf("\n請輸入離開的時間:/**:**/");scanf("%d:%d",&p->leave.hour,&p->leave.min);printf("離開車輛的車牌號為:%ld\n",p->num);printf("其到達(dá)時間為:%d:%d\n",p->reach.hour,p->reach.min);printf("離開時間為:%d:%d\n",p->leave.hour,p->leave.min);A1=p->reach.hour;A2=p->reach.min;B1=p->leave.hour;B2=p->leave.min;printf("應(yīng)交費(fèi)用為:%2.1fRMB\n",((B1-A1)*60+(B2-A2))*price);free(p);}//=================================================================================================arrivevoidArrive(SeqStackCar*Enter,LinkQueueCar*W){CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));//flushall();printf("請輸入車牌號(例:12345):\n");scanf("%ld",&p->num);if(Enter->top<max)//車輛未滿，車進(jìn)場{Enter->top++;printf("車輛請停在第%d位置.\n",Enter->top);printf("請輸入到達(dá)時間:\n");scanf("%d:%d",&p->reach.hour,&p->reach.min);Enter->stack[Enter->top]=p;}else//車輛已滿{printf("該車須在便道等待！.\n");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;}printf("Returnmainmeun(1.return0.quit)\n");scanf("%d",&flag);switch(flag){case0:system("cls");printf("Thanks,Welcometousenext\n");exit(0);case1:system("cls");}}//=================================================================================================leavevoidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W){inti,room;CarNode*p,*t;QueueNode*q;if(Enter->top>0)//盼斷車場內(nèi)是否有車{while(1){printf("請輸入車在車場的位置/1--%d/:\n",Enter->top);//請輸入車在車場的位置scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)//車輛離開{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p,room);//判斷通道上是否有車及車場是否已滿if((W->head!=W->rear)&&Enter->top<max)//便道的車輛進(jìn)場{q=W->head->next;t=q->data;Enter->top++;printf("便道的%s號車進(jìn)入車場第%d位置.\n",t->num,Enter->top);printf("請輸入現(xiàn)在的時間/**:**/:\n");scanf("%d:%d",&t->reach.hour,&t->reach.min);W->head->next=q->next;if(q==W->rear)W->rear=W->head;Enter->stack[Enter->top]=t;free(q);}elseprintf("便道；里沒有車.\n");}elseprintf("車場里沒有車.\n");//車場里沒有車printf("Returnmainmeun(1.return0.quit)\n");scanf("%d",&flag);switch(flag){case0:system("cls");printf("Thanks,Welcometousenext\n");exit(0);case1:system("cls");}}//=================================================================================================showvoidList1(SeqStackCar*S)//顯示存車信息{inti;if(S->top>0)//判斷車場內(nèi)是否有車{printf("車場\n");for(i=1;i<=S->top;i++){printf("位置%d\到達(dá)時間:%d:%d\t號碼:%ld\n",i,S->stack[i]->reach.hour,S->stack[i]->reach.min,S->stack[i]->num);}}elseprintf("車場里沒有車.\n");printf("Returnmainmeun(1.return0.quit)\n");scanf("%d",&flag);switch(flag){case0:system("cls");printf("Thanks,Welcometousenext\n");exit(0);case1:system("cls");}}voidList2(LinkQueueCar*W){QueueNode*p;p=W->head->next;if(W->head!=W->rear){printf("等待車輛的號碼為:");while(p!=NULL){printf("%ld\n",p->data->num);p=p->next;}}elseprintf("便道里沒有車.\n");printf("Returnmainmeun(1.return0.quit)\n");scanf("%d",&flag);switch(flag){case0:system("cls");printf("Thanks,Welcometousenext\n");exit(0);case1:system("cls");}}voidList(SeqStackCarS,LinkQueueCarW){inttag;printf("1.車場\n");printf("2.便道\n");printf("0.返回\n");scanf("%d",&tag);system("cls");switch(tag){case0:break;case1:List1(&S);break;case2:List2(&W);break;}}//=================================================================================================mainintmain(){SeqStackCarEnter,Temp;LinkQueueCarWait;intch;InitStack(&Enter);InitStack(&Temp);InitQueue(&Wait);AA:printf("停車場\n");printf("\n1.車輛到達(dá)\n");printf("2.車輛離開\n");printf("3.列表顯示\n");printf("0.退出系統(tǒng)\n");scanf("%d",&flag);system("cls");switch(flag){case0:printf("Thanks,Welcometousenext\n");return0;case1:Arrive(&Enter,&Wait);gotoAA;case2:Leave(&Enter,&Temp,&Wait);gotoAA;case3:List(Enter,Wait);gotoAA;}return0;}//=================================================================================================7．測試情況：截圖：程序輸出為：TheSystemofparking1.cararrive2.carleave3.showcar0.quitsystemParkingLotplace:1arrivedtime:5:45number:2place:2arrivedtime:9:14number:1Returnmainmeun(1.return0.quit)課程設(shè)計(jì)的名稱：二叉樹的基本操作的實(shí)現(xiàn)1.問題描述：在主程序中編寫一個簡單的菜單，將有關(guān)二叉樹的操作建立一棵二叉樹的存儲構(gòu)造遍歷一棵二叉樹〔包括層次遍歷〕統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)的個數(shù)求二叉樹的深度子樹交換2.基本要求：建立一棵二叉樹的存儲構(gòu)造遍歷一棵二叉樹〔包括層次遍歷〕統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)的個數(shù)求二叉樹的深度子樹交換3.算法思想：CreatBiTree()運(yùn)用遞歸創(chuàng)造二叉樹的每一個節(jié)點(diǎn)；Exchange()通過遞歸交換左右子樹；Depth()通過遞歸計(jì)算二叉樹的深度。InorderTraverse()遞歸中序遍歷二叉樹。PreOrderTraverse()遞歸先續(xù)遍歷二叉樹。PostOrderTraverse()遞歸后續(xù)遍歷二叉樹。4.模塊劃分：〔1〕BiTreeCreatBiTree(BiTreeT)其功能是創(chuàng)造一顆二叉樹；〔2〕intDepth(BiTreeT)其功能是計(jì)算一顆二叉樹的深度〔3〕voidExchange(BiTreeT)其功能是交換左右子樹〔4〕voidInorderTraverse(BiTreeT)其功能是中序遍歷〔5〕voidPreOrderTraverse(BiTreeT)其功能是前序遍歷〔6〕voidPostOrderTraverse(BiTreeT)其功能是后序遍歷5.數(shù)據(jù)構(gòu)造：〔1〕數(shù)據(jù)類型BiTNode定義如下：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;6.源程序：源代碼//main.c#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidLevelOrder(BiTreeT);voidInorderTraverse(BiTreeT);BiTreeCreatBiTree(BiTreeT);intDepth(BiTreeT);voidExchange(BiTreeT);intNodeCount(BiTreeTi);voidPostOrderTraverse(BiTreeT);voidPreOrderTraverse(BiTreeT);BiTreeCreatBiTree(BiTreeT){charch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T){exit(0);printf("error");}T->data=ch;T->lchild=CreatBiTree(T->lchild);T->rchild=CreatBiTree(T->rchild);}returnT;}intDepth(BiTreeT){intLNum,RNum;if(T==NULL){return0;}else{LNum=Depth(T->lchild);RNum=Depth(T->rchild);if(LNum>RNum)return(LNum+1);elsereturn(RNum+1);}}voidExchange(BiTreeT){BiTNode*p;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Exchange(T->lchild);Exchange(T->rchild);}}voidInorderTraverse(BiTreeT){if(T){InorderTraverse(T->lchild);printf("%c",T->data);InorderTraverse(T->rchild);}}voidLevelOrder(BiTreeT){BiTreeQueue[20],b;intfront,rear;front=rear=0;if(T){printf("LevelOrder:");Queue[rear++]=T;while(front!=rear){b=Queue[front++];printf("%2c",b->data);if(b->lchild!=NULL)Queue[rear++]=b->lchild;if(b->rchild!=NULL)Queue[rear++]=b->rchild;}}}intNodeCount(BiTreeTi){if(Ti==NULL)return0;elsereturnNodeCount(Ti->lchild)+NodeCount(Ti->rchild)+1;}voidPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}voidPreOrderTraverse(BiTreeT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}intmain(){BiTreeT=NULL;intchoice;while(1){printf("1-CreatBiTree.\n");printf("2-PreOrderTraverse.\n");printf("3-InorderTraverse.\n");printf("4-PostOrderTraverse.\n");printf("5-LevelOrderTraverse.\n");printf("6-NodeCount.\n");printf("7-BiTreeDepth.\n");printf("8-BiTreeExchange.\n");printf("0-exit\n");printf("Pleaseinputthenumofyourchoice:");scanf("%d",&choice);fflush(stdin);switch(choice){case1:{T=CreatBiTree(T);printf("CreatSucessful");break;}case2:{PreOrderTraverse(T);break;}case3:{InorderTraverse(T);break;}case4:{PostOrderTraverse(T);break;}case5:{LevelOrder(T);break;}case6:{printf("TheNodeCountis%d",NodeCount(T));break;}case7:{printf("Depthis%d",Depth(T));break;}case8:{Exchange(T);break;}case0:exit(0);break;default:break;}if(getchar())system("cls");}return0;}7.測試情況：截圖：程序輸出為：Pleaseinputthenumofyourchoice:5LevelOrder:ACBEDPleaseinputthenumofyourchoice:7Depthis3Pleaseinputthenumofyourchoice:6TheNodeCountis5課程設(shè)計(jì)的名稱：圖的基本操作的實(shí)現(xiàn)問題描述：在主程序中建立一個菜單，實(shí)現(xiàn)圖的基本操作基本要求：圖的基本操作，包括：建立圖的存儲構(gòu)造，實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷利用圖的拓?fù)渑判蝌?yàn)證圖中是否存在環(huán)算法思想：createGraph()通過for循環(huán)利用鏈表構(gòu)造錄入點(diǎn)和邊的數(shù)據(jù)。BFS()和DFS()以及TopologicalSort()利用遞歸思想實(shí)現(xiàn)遍歷和排序。模塊劃分：voidcreateGraph()其功能為錄入點(diǎn)和邊以及其關(guān)系的數(shù)據(jù)。voidBFS(ALGraph&G,intv)其功能為實(shí)現(xiàn)廣度優(yōu)先遍歷voidDFS(ALGraph&G,intv)其功能為實(shí)現(xiàn)深度優(yōu)先遍歷voidTopologicalSort(ALGraph&G)其功能為拓?fù)渑判驍?shù)據(jù)構(gòu)造：數(shù)據(jù)類型LNode定義如下：typedefstruct{intvexs[40];intarcs[40][40];intvexnum,arcnum;intkind;}MGRAPH;數(shù)據(jù)類型LNode定義如下：typedefstruct{intadjvex;structnode3*next;}EDGENODE;數(shù)據(jù)類型LNode定義如下：typedefstruct{intvertex;EDGENODE*link;intid;}VEXNODE;數(shù)據(jù)類型LNode定義如下：typedefstruct{VEXNODEadjlist[40];intvexnum,arcnum;intkind;}ADJGRAPH;源程序：源代碼：#include<cstdlib>#include<iostream>#include<stdio.h>#include<malloc.h>#include<string.h>#include<stack>#defineMaxsize30#defineINFINITY99999usingnamespacestd;intvisited[100];typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVnode{intdata;ArcNode*firstarc;}VNode;typedefVNodeAdjLis[100];typedefstructadjlist{charname[10];intindegree;ArcNode*firstarc;}adjlist;typedefstruct{intn,e;intvexnum,arcnum;adjlistver[Maxsize];}ALGraph;voidFindInDegree(ALGraph&G){intindeg,i,j;ArcNode*p;for(i=0;i<G.vexnum;i++){indeg=0;for(j=0;j<G.vexnum;j++){if(G.ver[j].firstarc!=NULL){p=G.ver[j].firstarc;while(p){if(p->adjvex==i)indeg++;p=p->nextarc;}//while}//if}//forG.ver[i].indegree=indeg;}//for}voidTopologicalSort(ALGraph&G){inti,j,e,count;stack<int>s;ArcNode*p;FindInDegree(G);for(i=0;i<G.vexnum;i++)if(!G.ver[i].indegree)s.push(i);count=0;//對頂點(diǎn)進(jìn)展計(jì)數(shù)while(!s.empty()){e=s.top();count++;s.pop();for(p=G.ver[e].firstarc;p;p=p->nextarc){if(!(--G.ver[p->adjvex].indegree))s.push(p->adjvex);}//for}//whileif(count<G.vexnum){cout<<"該有向圖有回路\n";return;}//ifelse{cout<<"該有向圖無回路\n";return;}}intLocatecity(ALGraphG,charv[]){inti;for(i=0;i<G.vexnum;i++)if(!strcmp(G.ver[i].name,v))break;returni;}voidDFS(ALGraph&G,intv){ArcNode*p;visited[v]=1;printf("%3d",v);p=G.ver[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){DFS(G,p->adjvex);}p=p->nextarc;}}voidBFS(ALGraph&G,intv){ArcNode*p;intqueue[100],front=0,rear=0;intvisited[100];intw,i;for(i=0;i<G.vexnum;i++)visited[i]=0;printf("%3d",v);visited[v]=1;rear=(rear+1)%100;queue[rear]=v;while(front!=rear){front=(front+1)%100;w=queue[front];p=G.ver[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%3d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%100;queue[rear]=p->adjvex;}p=p->nextarc;}}cout<<endl;}voidcreateGraph(){ALGraphG;cout<<"請輸入圖的頂點(diǎn)個數(shù):";cin>>G.vexnum;cout<<"請輸入邊數(shù):";cin>>G.arcnum;for(inti=0;i<G.vexnum;i++){cout<<"第"<<i+1<<"個頂點(diǎn)的名稱:";cin>>G.ver[i].name;G.ver[i].indegree=0;G.ver[i].firstarc=NULL;}intn,m;charv1[10],v2[10];for(intj=0;j<G.arcnum;j++){cout<<"請輸入第"<<j+1<<"條邊的起始位置與終止位置:";cin>>v1>>v2;n=Locatecity(G,v1);m=Locatecity(G,v2);ArcNode*p,*q,*t;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=m;p->nextarc=NULL;if(G.ver[n].firstarc==NULL)G.ver[n].firstarc=p;else{q=G.ver[n].firstarc;while(q->nextarc)q=q->nextarc;q->nextarc=p;}}cout<<"深度遍歷排序：";DFS(G,0);cout<<endl<<"廣度遍歷排序：";BFS(G,0);TopologicalSort(G);}intmain(){createGraph();return0;}測試情況：截圖：程序輸出為：請輸入圖的頂點(diǎn)個數(shù):4請輸入邊數(shù):4第1個頂點(diǎn)的名稱:a第2個頂點(diǎn)的名稱:b第3個頂點(diǎn)的名稱:c第4個頂點(diǎn)的名稱:d請輸入第1條邊的起始位置與終止位置:ab請輸入第2條邊的起始位置與終止位置:ac請輸入第3條邊的起始位置與終止位置:ad請輸入第4條邊的起始位置與終止位置:bc深度遍歷排序：0123廣度遍歷排序：0123該有向圖無回路課程設(shè)計(jì)的名稱：哈希查找的設(shè)計(jì)與實(shí)現(xiàn)問題描述：編寫一個程序?qū)崿F(xiàn)哈希表的相關(guān)運(yùn)算?；疽螅和瓿扇缦鹿δ埽骸?〕建立｛16，74，60，43，54，90。46，31，29，88，77｝哈希表A[0..12]，哈希函數(shù)為H〔k〕=key%p，并用線性探查法解決沖突；〔2〕在上述哈希表中查找關(guān)鍵字為29的記錄；〔3〕在上述哈希表中刪除關(guān)鍵字為77的記錄，再將其插入。3.算法思想：CreatHT()通過m次循環(huán)對哈希表初始化。InsertHT()通過循環(huán)體將數(shù)組內(nèi)元素放入哈希表中SearchHT()采用線性探查法找下一個地址DeleteHT()調(diào)用SearchHT()找到該關(guān)鍵字并刪除DispHT()利用循環(huán)體輸出哈希表4.模塊劃分：voidCreatHT(HashTableha,intx[],intn,intm,intp)創(chuàng)立哈希表；intInsertHT(HashTableha,intn,intk,intp)將關(guān)鍵字插入到哈希表中intSearchHT(HashTableha,intp,intk)在哈希表中查找關(guān)鍵字intDeleteHT(HashTableha,intp,intk,intn)刪除哈希表中的某一關(guān)鍵字5.數(shù)據(jù)構(gòu)造：〔1〕數(shù)據(jù)類型HashTablep[]定義如下：typedefstructHashTable{intkey;char*data;intcount;}HashTable[100];6.源程序：源代碼#include<stdio.h>#include<stdlib.h>typedefstructHashTable{intkey;char*data;intcount;}HashTable[100];intInsertHT(HashTableha,intn,intk,intp)//將關(guān)鍵字插入到哈希表中{inti,adr;adr=k%p;if(ha[adr].key==-1||ha[adr].key==-2){ha[adr].key=k;ha[adr].count=1;}