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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告姓 名： 學(xué) 號(hào)： 班 級(jí)： 設(shè)計(jì)時(shí)間： 審閱教師： 目錄第一章 設(shè)計(jì)目的3第二章 設(shè)計(jì)任務(wù)及要求4一、基本要求:4二、內(nèi)容：4第三章 題目分析與解答5一、通訊錄管理系統(tǒng)51)題目要求52)應(yīng)用程序功能53)主要算法模塊描述64)源程序代碼9二、停車場(chǎng)管理系統(tǒng)161)題目要求16要求設(shè)計(jì)停車管理系統(tǒng)，實(shí)現(xiàn)車輛的進(jìn)入、離開并根據(jù)停車時(shí)間計(jì)費(fèi)。172)應(yīng)用程序功能173)主要算法模塊描述184)源程序代碼18三、猴子選大王241)題目要求242)應(yīng)用程序功能243)主要算法模塊描述244)源程序代碼25四、二叉樹運(yùn)算271)題目要求272)應(yīng)用程序功能273)主要算法模塊描述274)源程序代碼27第四章 設(shè)計(jì)心得31第五章 參考文獻(xiàn)32第一章 設(shè)計(jì)目的1、培養(yǎng)學(xué)生運(yùn)用算法與數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)解決實(shí)際編程中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)問題。2、培養(yǎng)學(xué)生獨(dú)立設(shè)計(jì)程序與解決問題的能力，培養(yǎng)學(xué)生團(tuán)隊(duì)協(xié)作集成程序模塊及調(diào)試能力。3、培養(yǎng)學(xué)生初步的軟件設(shè)計(jì)及軟件測(cè)試的能力。第二章 設(shè)計(jì)任務(wù)及要求一、 基本要求:學(xué)生必須仔細(xì)閱讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)書，認(rèn)真主動(dòng)完成課設(shè)的要求。有問題及時(shí)主動(dòng)通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要一周時(shí)間完成，一周中每天（按每周5天）至少要上3-4小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序15小時(shí)。根據(jù)設(shè)計(jì)報(bào)告要求編寫設(shè)計(jì)報(bào)告，主要內(nèi)容包括目的、意義、原理和實(shí)現(xiàn)方法簡(jiǎn)介、過程分析及說明、實(shí)驗(yàn)結(jié)果情況說明、結(jié)論。每個(gè)人必須有可運(yùn)行的程序，學(xué)生能對(duì)自己的程序面對(duì)教師提問并能熟練地解釋清楚，學(xué)生回答的問題和程序運(yùn)行的結(jié)果作為評(píng)分的主要衡量標(biāo)準(zhǔn)；（周二下午開始逐一檢查）二、 內(nèi)容：本次課程設(shè)計(jì)完成如下模塊（共11個(gè)模塊，學(xué)生可以在其中至少挑選4個(gè)功能塊完成，但有*號(hào)的模塊是必須要選擇的,多做可以加分）第三章 題目分析與解答一、 通訊錄管理系統(tǒng)1) 題目要求通訊錄一般包括通訊者的編號(hào)、姓名、性別、電話及地址等信息，設(shè)計(jì)一個(gè)通訊錄要求實(shí)現(xiàn)通訊者的插入、查詢、刪除、更新、排序操作。 struct node char num5; /編號(hào) char name8; /姓名 char sex; /性別 char tel8; /電話 char address100; /地址;2) 應(yīng)用程序功能明確用戶的需求，如操作界面需求，系統(tǒng)功能需求，數(shù)據(jù)的具體流程等。添加界面：顯示界面：刪除界面：修改界面： 3) 主要算法模塊描述 工作流程圖：添加：添加通訊錄記錄顯示：顯示通訊錄記錄刪除：刪除通訊錄記錄查詢：查詢通訊錄記錄先選擇查詢方式，以姓名查詢方式為例修改：修改通訊錄記錄4) 源程序代碼#include<stdio.h> #include<stdlib.h>#include<string.h> typedef struct char score; /*編號(hào)*/char name10; /*姓名*/ char num15; /*號(hào)碼*/ char email20;/*郵箱*/char age8;/*年齡*/char adds20;/*住址*/Person; Person pe80; int menu_select() char c; do system("cls"); printf("tt *通訊錄* n"); printf("ttn"); printf("tt 1. 添加記錄 n"); printf("tt 2. 顯示記錄 n"); printf("tt 3. 刪除記錄 n"); printf("tt 4. 查詢記錄 n"); printf("tt 5. 修改記錄 n"); printf("tt 6. 保存記錄 n");printf("tt 0. 退出程序 n"); printf("ttn"); printf("tt請(qǐng)您選擇(0-6):"); c=getchar(); while(c<0|c>6); return(c-0); int Input(Person per,int n) int i=0; char sign,x10; while(sign!=n&&sign!=N) printf("t編號(hào):"); scanf("t%d",&pern+i.score); printf("t姓名:"); scanf("t%s",pern+i.name); printf("t年齡:"); scanf("t%s",pern+i.age);printf("t電話號(hào)碼:"); scanf("t%s",pern+i.num); printf("t通訊住址:"); scanf("t%s",pern+i.adds);printf("t電子郵箱:");scanf("t%s",pern+i.email);gets(x); printf("nt是否繼續(xù)添加?(Y/N)"); scanf("t%c",&sign); i+; return(n+i); void Display(Person per,int n) int i; printf("-n"); /*格式*/ printf("編號(hào) 姓名 年齡 電話號(hào)碼 通訊地址 電子郵箱n"); printf("-n"); for(i=1;i<n+1;i+) printf("%-5d%-8s%-6s%-13s%-15s%-15sn",peri-1.score,peri-1.name,peri-1.age,peri-1.num,peri-1.adds,peri-1.email); if(i>1&&i%10=0) printf("t-n"); printf("t"); system("pause"); printf("t-n"); printf("-n");system("pause"); int Delete_a_record(Person per,int n) char s20; int i=0,j; printf("t請(qǐng)輸入想刪除記錄中的名字:"); scanf("%s",s); while(strcmp(peri.name,s)!=0&&i<n) i+; if(i=n) printf("t通訊錄中沒有此人!n"); return(n); for(j=i;j<n-1;j+) strcpy(perj.num,perj+1.num); strcpy(perj.name,perj+1.name); strcpy(perj.age,perj+1.age);strcpy(perj.adds,perj+1.adds);strcpy(perj.email,perj+1.email);perj.score=perj+1.score; printf("ttt已經(jīng)成功刪除!n"); return(n-1); void Query_a_record(Person per,int n) int m;printf("tn請(qǐng)選擇查詢方式:n"); printf("tn"); printf("t1-姓名 n"); printf("t2-電話 n"); printf("t3-地址 n"); printf("t4-返回 n"); printf("tn"); printf("請(qǐng)選擇:"); scanf("%d",&m); while(m!=1&&m!=2&&m!=3&&m!=4) printf("輸入錯(cuò)誤，請(qǐng)重新選擇:");scanf("%d",&m);if(m=1)char s20; int i=0; printf("t請(qǐng)輸入想查詢的姓名:"); scanf("t%s",s); while(strcmp(peri.name,s)!=0&&i<n) i+; if(i=n) printf("t通訊錄中沒有此人!n"); return; printf("t此人編號(hào): %dn",peri.score);printf("t此人年齡: %sn",peri.age); printf("t電話號(hào)碼: %sn",peri.num); printf("t通訊地址: %sn",peri.adds);printf("t電子郵箱: %sn",peri.email); ;if(m=2)char s20; int i=0; printf("t請(qǐng)輸入想查詢的電話:"); scanf("t%s",s); while(strcmp(peri.num,s)!=0&&i<n) i+; if(i=n) printf("t通訊錄中沒有此人!n"); return; printf("t此人編號(hào): %dn",peri.score);printf("t此人姓名: %sn",peri.name);printf("t此人年齡: %sn",peri.age); printf("t通訊地址: %sn",peri.adds);printf("t電子郵箱: %sn",peri.email); ;if(m=3)char s20; int i=0; printf("t請(qǐng)輸入想查詢的地址:"); scanf("t%s",s); while(strcmp(peri.adds,s)!=0&&i<n) i+; if(i=n) printf("t通訊錄中沒有此人!n"); return; printf("t此人編號(hào): %dn",peri.score);printf("t此人姓名: %sn",peri.name);printf("t此人年齡: %sn",peri.age); printf("t電話號(hào)碼: %sn",peri.num); printf("t電子郵箱: %sn",peri.email); ;void Change(Person per,int n) char s20; int i=0; printf("t請(qǐng)輸入想修改的記錄中的名字:"); scanf("%s",s); while(strcmp(peri.name,s)!=0&&i<n) i+; if(i=n) printf("t通訊錄中沒有此人!n"); return; printf("t編號(hào):"); scanf("t%d",&peri.score); printf("t姓名:"); scanf("t%s",peri.name); printf("t年齡:"); scanf("t%s",peri.age);printf("t電話號(hào)碼:"); scanf("t%s",peri.num); printf("t通訊住址:"); scanf("t%s",peri.adds);printf("t電子郵箱:");scanf("t%s",peri.email);printf("t修改成功！");void WritetoText(Person per,int n) int i=0; FILE *fp; /*定義文件指針*/ char filename20; /*定義文件名*/ printf("t保存到文件n"); /*輸入文件名*/ printf("t請(qǐng)輸入所保存的文件名:"); scanf("t%s",filename); if(fp=fopen(filename,"w")=NULL) printf("t無法打開文件n"); system("pause"); return; fprintf(fp,"*通訊錄*n");fprintf(fp,"編號(hào) 姓名 年齡 電話號(hào)碼 通訊地址 電子郵箱n");fprintf(fp,"-n");while(i<n) fprintf(fp,"%-3dt%-6st%-3st%-13st%-20st%-20sn",peri.score,peri.name,peri.age,peri.num,peri.adds,peri.email); i+; fprintf(fp,"-n");fprintf(fp,"*共有%d條記錄*n",n); fclose(fp); /*關(guān)閉文件*/ printf("保存成功!n"); void main() /*主函數(shù)*/ int n=0; for(;) switch(menu_select() case 1: printf("nt添加記錄到通訊錄n"); /*添加記錄*/ n=Input(pe,n); break; case 2: printf("nttt 通訊錄記錄表n"); /*顯示記錄*/ Display(pe,n); break;case 3: printf("nt從通訊錄中刪除記錄n"); n=Delete_a_record(pe,n); /*刪除記錄*/ printf("t"); system("pause"); break; case 4: printf("nt在通訊錄中查找記錄n"); Query_a_record(pe,n); /*查找記錄*/ printf("t"); system("pause"); break;case 5: printf("nt修改通訊錄中的記錄n"); Change(pe,n); /*修改數(shù)據(jù)*/ printf("t"); system("pause"); break; case 6: printf("nt保存功能n"); WritetoText(pe,n); /*保存數(shù)據(jù)*/ printf("t"); system("pause"); break; case 0: printf("ntt謝謝使用，再見!n"); /*結(jié)束程序*/ printf("ntt"); system("pause"); exit(0); 二、 停車場(chǎng)管理系統(tǒng)1) 題目要求某停車場(chǎng)可以停放n輛汽車，該停車場(chǎng)只有一個(gè)大門， 每輛汽車離開停車場(chǎng)都要求之前的汽車必須先退出停車場(chǎng)為它讓道，而后讓道的汽車再次駛?cè)胪＼噲?chǎng)，停車場(chǎng)示意圖如下：要求設(shè)計(jì)停車管理系統(tǒng)，實(shí)現(xiàn)車輛的進(jìn)入、離開并根據(jù)停車時(shí)間計(jì)費(fèi)。2) 應(yīng)用程序功能 明確用戶的需求，如操作界面需求，系統(tǒng)功能需求，數(shù)據(jù)的具體流程等。運(yùn)行時(shí)界面如下：車輛到達(dá)：車場(chǎng)信息：3) 主要算法模塊描述4) 源程序代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include <conio.h>#define MAX 10 /*車庫容量*/ #define price 3 /*每車每時(shí)刻費(fèi)用*/typedef struct node int num; int reachtime; int leavetime; CarNode; /*車輛信息結(jié)點(diǎn)*/ typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*模擬車站*/typedef struct car CarNode *data; struct car *next; QueueNode; typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar; /*模擬通道*/*-*/ /*函數(shù)聲明部分*/ void InitStack(SeqStackCar *); /*初始化棧*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*車輛到達(dá)*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*車輛離開*/ void List(SeqStackCar,LinkQueueCar); /*顯示存車信息*/ void PRINT(CarNode *p) ;/*-*/ void option() int i; char choice; printf("nnnn"); printf(" 停車場(chǎng)管理系統(tǒng)"); printf("nnnn"); printf("n*"); printf("t1.車輛到達(dá)-1 2.車輛離開-2 3.車輛信息-3 4.退出程序-4"); printf("n*"); printf("nnnt 是否進(jìn)入該系統(tǒng)（y/n）？ "); choice=getchar(); if(choice=N|choice=n) exit(0); void main() SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; system("graftabl 936"); option();InitStack(&Enter); /*初始化車站*/ InitStack(&Temp); /*初始化讓路的臨時(shí)棧*/ InitQueue(&Wait); /*初始化通道*/ while(1) system("cls"); printf("nnttt1. 車輛到達(dá) 請(qǐng)選擇 1"); printf("nnttt2. 車輛離開 請(qǐng)選擇 2"); printf("nnttt3. 車輛信息 請(qǐng)選擇 3"); printf("nnttt4. 退出程序 請(qǐng)選擇 4"); printf("nnttt現(xiàn)在請(qǐng)選擇以上信息 : ");while(1) scanf("%d",&ch); printf("n"); if(ch>=1&&ch<=4)break; else printf("nttt錯(cuò)誤！請(qǐng)?jiān)俅巫龀鲞x擇！nnttt"); switch(ch) case 1:Arrival(&Enter,&Wait); break; /*車輛到達(dá)*/ case 2:Leave(&Enter,&Temp,&Wait); break; /*車輛離開*/ case 3:List(Enter,Wait); break; /*列表打印信息*/ case 4:exit(0); /*退出主程序*/ default: break; /*-*/ void InitStack(SeqStackCar *s) /*初始化棧*/ int i; s->top=0; for(i=0;i<=MAX;i+) s->stacks->top=NULL; int InitQueue(LinkQueueCar *Q) /*初始化便道*/ Q->head=(QueueNode *)malloc(sizeof(QueueNode); if(Q->head!=NULL) Q->head->next=NULL; Q->rear=Q->head; return(1); else return(-1); void PRINT(CarNode *p) /*打印出站車的信息*/ int A1,A2; printf("nttt請(qǐng)輸入離開時(shí)間: "); scanf("%d",&(p->leavetime); printf("nttt離開車輛的車牌號(hào): %d",p->num); printf("nnttt離開車輛到達(dá)時(shí)間: %d ",p->reachtime); printf("nnttt離開車輛離開時(shí)間: %d",p->leavetime); A1=p->reachtime; A2=p->leavetime; printf("nnttt停車場(chǎng)管理費(fèi)用: %d",(A2-A1)*price); free(p); int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*車輛到達(dá)*/ CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); flushall(); printf("ttt請(qǐng)輸入到達(dá)車輛車牌號(hào): "); scanf("%d",&(p->num); if(Enter->top<MAX) /*車場(chǎng)未滿，車進(jìn)車場(chǎng)*/ Enter->top+; printf("nttt該車輛在停車場(chǎng)的位置是: %dn",Enter->top); printf("nttt請(qǐng)輸入該車輛到達(dá)的時(shí)間: "); scanf("%d",&(p->reachtime); Enter->stackEnter->top=p; return(1); else /*車場(chǎng)已滿，車進(jìn)便道*/ printf("nttt停車場(chǎng)已滿 該車輛需在便道上等待！"); getch(); t=(QueueNode *)malloc(sizeof(QueueNode); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) /*車輛離開*/ int i, room; CarNode *p,*t; QueueNode *q; /*判斷車場(chǎng)內(nèi)是否有車*/ if(Enter->top>0) /*有車*/ while(1) /*輸入離開車輛的信息*/ printf("ttt停車場(chǎng)里停放的車輛總數(shù): %d",Enter->top); printf("nnttt請(qǐng)輸入要離開車輛的位置: "); scanf("%d",&room); if(room>=1&&room<=Enter->top) break; while(Enter->top>room) /*車輛離開*/ Temp->top+; Temp->stackTemp->top=Enter->stackEnter->top; Enter->stackEnter->top=NULL; Enter->top-; p=Enter->stackEnter->top; Enter->stackEnter->top=NULL; Enter->top-; while(Temp->top>=1) Enter->top+; Enter->stackEnter->top=Temp->stackTemp->top; Temp->stackTemp->top=NULL; Temp->top-; PRINT(p);/*判斷通道上是否有車及車站是否已滿*/ if(W->head!=W->rear)&&Enter->top<MAX) /*便道的車輛進(jìn)入車場(chǎng)*/ q=W->head->next; t=q->data; Enter->top+; printf("nnttt便道的%d號(hào)車進(jìn)入車場(chǎng)第%d位置.",t->num,Enter->top); printf("nnttt請(qǐng)輸入現(xiàn)在的時(shí)間:"); scanf("%d",&(t->reachtime); W->head->next=q->next; if(q=W->rear) W->rear=W->head; Enter->stackEnter->top=t; free(q); else printf("nnttt便道里沒有車.n"); else printf("nnttt車場(chǎng)里沒有車."); /*沒車*/ void List1(SeqStackCar *S) /*列表顯示車場(chǎng)信息*/ int i; if(S->top>0) /*判斷車站內(nèi)是否有車*/ printf("nttt車場(chǎng):"); printf("nnttt位置 到達(dá)時(shí)間 車牌號(hào)n"); for(i=1;i<=S->top;i+) printf("%26d",i); printf("%6d",S->stacki->reachtime); printf("%10d",S->stacki->num); printf("n"); else printf("nttt車場(chǎng)里沒有車"); void List2(LinkQueueCar *W) /*列表顯示便道信息*/ QueueNode *p; p=W->head->next; if(W->head!=W->rear) /*判斷通道上是否有車*/ printf("nttt等待車輛的號(hào)碼為: "); while(p!=NULL) printf("%-10d",p->data->num); p=p->next; printf("n"); else printf("nttt便道里沒有車."); void List(SeqStackCar S,LinkQueueCar W) int flag,tag; flag=1; while(flag) printf("nttt請(qǐng)選擇 1|2|3:"); printf("nnttt1.車場(chǎng)nnttt2.便道nnttt3.返回nnttt"); while(1) scanf("%d",&tag); if(tag>=1|tag<=3) break; else printf("nttt請(qǐng)選擇 1|2|3:"); switch(tag) case 1:List1(&S);break; /*列表顯示車場(chǎng)信息*/ case 2:List2(&W);break; /*列表顯示便道信息*/ case 3:flag=0;break; default: break; 三、 猴子選大王1) 題目要求任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能 2) 應(yīng)用程序功能運(yùn)行界面如下：3) 主要算法模塊描述4) 源程序代碼#include"stdio.h"#include"stdlib.h"typedef struct Node int data; struct Node *next;Node,*LinkList;void CreatLinkList(LinkList *L,int m)/ 創(chuàng)建循環(huán)鏈表 m為猴子總數(shù) Node *p, *q; int i; (*L) = (LinkList)malloc(sizeof(Node); if (*L) = NULL) printf("Memory allocation failed,goodbye"); exit(1); p = (*L); p->data = 1; for (i = 2; i <= m; i+) q = (LinkList)malloc(sizeof(Node); if (q = NULL) printf("Mmory allocation failed,goodbye"); exit(1); q->data = i; p->next = q; p = q; p->next =(*L);void King(LinkList *L, int n, int m) Node *p, *q; int k; int j = 1; p = (*L); printf("n"); for (; m > 1; m-) k = 1; while (k != n) p = p->next; k+; printf("第%d個(gè)出隊(duì)的是%d號(hào)猴子，n", j+, p->data); p->data = p->next->data; q = p->next; p->next = p->next->next; free(q); printf("n最終結(jié)果：大王是第%d號(hào)猴子n",p->data);int main(void) int m, n;LinkList L; printf("請(qǐng)輸入猴子總數(shù)m，和數(shù)到第幾個(gè)猴子出隊(duì)n：");scanf("%d%d",&m,&n);/在這后面加判斷、提示部分。for循環(huán)判斷.CreatLinkList(&L, m); King(&L, n, m); return 0;四、 二叉樹運(yùn)算1) 題目要求任務(wù)：求二叉樹中指定兩個(gè)結(jié)點(diǎn)共同的最近祖先。2) 應(yīng)用程序功能運(yùn)行程序，界面如下：3) 主要算法模塊描述4) 源程序代碼#include <stdio.h>#include <stdlib.h>#define max 50typedef struct liuyu int data; struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;void FindLowestCommonAncestor(test *root, int value1, int value2);int sum=0;int m=sizeof(test); int insert_data(int x) /*生成二叉排序樹*/ liuyu *p,*q,*s; s=(test*)malloc(m); s->data=x; s->lchild=NULL; s->rchild=NULL; if(!root) root=s; p=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/ q=p; if(p->data=x) return 0; if(x<p->data) p=p->lchild; else p=p->rchild; if(x<q->data) q->lchild=s; else q->rchild=s; return 1;void main() /*先生成二叉排序樹*/ int i,x; int v1,v2; i=1; root=NULL; do printf("請(qǐng)輸入節(jié)點(diǎn)數(shù)據(jù)（輸入00結(jié)束）%d:",i); i+; scanf("%d",&x); /*從鍵盤采集數(shù)據(jù)，以00表示輸入結(jié)束*/ if(x=00) printf("n建立二叉樹成功n"); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/ while(x!=00); printf("n請(qǐng)輸入兩個(gè)結(jié)點(diǎn):"); scanf("%d%d",&v1,&v2); FindLowestCommonAncestor(root, v1, v2);void FindLowestCommonAncestor(test *root, int value1, int value2)