數(shù)據(jù)結構課程設計報告(通訊錄系統(tǒng)、倉庫管理系統(tǒng)、一元多項式的計算、猴子選大王)

《數(shù)據(jù)結構》課程設計報告姓名：學號：班級：設計時間：2010年12月23日〔星期四〕審閱教師：目錄第一章設計目的 3第二章設計任務及要求 3一、 根本要求: 3二、 內(nèi)容： 3第三章題目分析與解答 3一、 倉庫管理系統(tǒng) 31) 題目要求 32) 應用程序功能 43) 主要模塊的算法描述 44) 源程序代碼 5二、 通訊錄管理系統(tǒng) 131) 題目要求 132) 應用程序功能 133) 主要算法模塊描述 144) 源程序代碼 15三、 一元多項式計算 201) 題目要求 202) 應用程序功能 203) 主要算法模塊描述 214) 源程序代碼 21四、 猴子選大王 261) 題目要求 262) 應用程序功能 263) 主要算法模塊描述 274) 源程序代碼 27五、 二叉樹運算1〔**〕 291) 題目要求 292) 應用程序功能 293) 源程序代碼 294) 主要算法模塊描述 29第四章設計心得 29第五章參考文獻 30第一章設計目的1、培養(yǎng)學生運用算法與數(shù)據(jù)結構的根本知識解決實際編程中的數(shù)據(jù)結構設計和算法設計問題。2、培養(yǎng)學生獨立設計程序與解決問題的能力，培養(yǎng)學生團隊協(xié)作集成程序模塊及調(diào)試能力。3、培養(yǎng)學生初步的軟件設計及軟件測試的能力。第二章設計任務及要求根本要求:學生必須仔細閱讀《數(shù)據(jù)結構》課程設計指導書，認真主動完成課設的要求。有問題及時主動通過各種方式與教師聯(lián)系溝通。學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間方案，并在課設過程中不斷檢測自己的方案完成情況，及時的向教師匯報。課程設計按照教學要求需要一周時間完成，一周中每天〔按每周5天〕至少要上3-4小時的機來調(diào)試C語言設計的程序，總共至少要上機調(diào)試程序15小時。根據(jù)設計報告要求編寫設計報告，主要內(nèi)容包括目的、意義、原理和實現(xiàn)方法簡介、過程分析及說明、實驗結果情況說明、結論。每個人必須有可運行的程序，學生能對自己的程序面對教師提問并能熟練地解釋清楚，學生答復的問題和程序運行的結果作為評分的主要衡量標準；〔周二下午開始逐一檢查〕內(nèi)容：本次課程設計完成如下模塊〔共11個模塊，學生可以在其中至少挑選4個功能塊完成，但有**號的模塊是必須要選擇的,多做可以加分〕第三章題目分析與解答倉庫管理系統(tǒng)題目要求設計一個倉庫管理系統(tǒng)，可以按照順序和貨物名稱查詢倉庫的存儲情況，也可以添加或刪除貨物。structnode{intNO;//商品編號charname[max];//商品名稱intcount;//商品數(shù)量};應用程序功能明確用戶的需求，如操作界面需求，系統(tǒng)功能需求，數(shù)據(jù)的具體流程等。開始運行時界面如下：你可以根據(jù)所對應的信息提示進行操作便可對其進行數(shù)據(jù)的記錄與查詢。主要模塊的算法描述流程圖：源程序代碼#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<ctype.h>#include<string.h>#defineSIZE100typedefstruct{charname[10];charfam[10];intpay;intnum;}Store;typedefstructnode{Storeelem;structnode*next;}In;In*head=NULL;voidappendInfo();voidList();voidmenu(void);In*Init();voidStart();voidInsert();voidDel();voidrenew();voidWsave();voidRead();voidSortUp();voidPreFile();intmain(){charselect;PreFile();menu();while((select=toupper(getch()))!='0'){system("cls");switch(select){case'1':{Start();system("pause");menu();break;}case'2':{appendInfo();system("pause");menu();break;}case'3':{Insert();system("pause");menu();break;}case'4':{Del();system("pause");menu();break;}case'5':{renew();system("pause");menu();break;}case'6':{List();system("pause");menu();break;}case'7':{SortUp();system("pause");menu();break;}case'W':{Wsave();system("pause");menu();break;}case'R':{Read();system("pause");menu();break;}default:printf("Inputerror!\n");system("pause");menu();break;}}return0;}In*Init(){In*L;L=(In*)malloc(sizeof(In));L->next=NULL;returnL;}voidappendInfo(){inti,j;In*p,*s; A1:printf("請輸入要存放的記錄數(shù):");scanf("%d",&j);if(j<=0){printf("Inputerror!\n");gotoA1;}if(head==NULL){p=Init();head=p;}else{p=head->next;while(p->next!=NULL)p=p->next;}for(i=0;i<j;i++){s=Init();printf("名稱品牌單價數(shù)量\n");scanf("%s",&s->);scanf("%s",&s->elem.fam);scanf("%d",&s->elem.pay);scanf("%d",&s->elem.num);p->next=s;p=s;}}voidList(){In*p;if(head==NULL){printf("Noneofinformationaboutproducts.\n");return;}elsep=head->next;printf("名稱品牌單價數(shù)量\n");while(p!=NULL){printf("%s\t%s\t%d\t%d\n",p->,p->elem.fam,p->elem.pay,p->elem.num);p=p->next;}}voidmenu(){system("cls");printf("||\n");printf("|家電倉庫管理|\n");printf("|請輸入選項編號|\n");printf("||\n");printf("|1--數(shù)據(jù)初始化|\n");printf("|2--創(chuàng)立數(shù)據(jù)表|\n");printf("|3--數(shù)據(jù)插入|\n");printf("|4--數(shù)據(jù)刪除|\n");printf("|5--數(shù)據(jù)更新|\n");printf("|6--數(shù)據(jù)查詢|\n");printf("|7--單價升序|\n");printf("|w--數(shù)據(jù)保存|\n");printf("|r--數(shù)據(jù)讀出|\n");printf("|0--系統(tǒng)退出(exit)|\n");printf("||\n");printf("請輸入你的選擇:");}voidStart(){charcom;printf("你想清空所有資料嗎？〔Y/N〕:");fflush(stdin);com=getchar();if(com=='Y'||com=='y'){printf("已經(jīng)初始化了、、、\n");head=NULL;return;}elseprintf("資料仍在、、、\n");return;}voidInsert(){In*pi,*p;charstr[10];printf("請問要在哪個學生后面插入〔輸入姓名〕：");fflush(stdin);gets(str);pi=Init();printf("名稱品牌單價數(shù)量\n");scanf("%s",&pi->);scanf("%s",&pi->elem.fam);scanf("%d",&pi->elem.pay);scanf("%d",&pi->elem.num);if(head==NULL){printf("前面沒有數(shù)據(jù)，默認接在表頭。\n");p=Init();head=p;p->next=pi;}else{p=head->next;while((strcmp(p->,str)!=0)&&p->next!=NULL)p=p->next;if(p->next!=NULL){pi->next=p->next;p->next=pi;}elsep->next=pi;}}voidDel(){In*pi,*p,*s;charstr[10];if(head==NULL){printf("沒有商品資料。\n");return;}printf("請輸入要刪除產(chǎn)品的名稱：");fflush(stdin);gets(str);p=head->next;while((strcmp(p->,str)!=0)&&p->next!=NULL){pi=p;p=p->next;}if(strcmp(p->,str)==0){printf("所刪除的記錄為：\n");printf("%s\t%s\t%d\t%d\n",p->,p->elem.fam,p->elem.pay,p->elem.num);if(p==head->next){s=Init();head=s;s->next=p->next;}elsepi->next=p->next;free(p);}elseprintf("找不到相應的商品資料。\n");}voidrenew(){In*pi,*p,*s;charstr[10];if(head==NULL){printf("沒有商品資料。\n");return;}List();printf("請輸入要更新產(chǎn)品的名稱：");fflush(stdin);gets(str);p=head->next;while((strcmp(p->,str)!=0)&&p->next!=NULL){pi=p;p=p->next;}if(strcmp(p->,str)==0){printf("所要更新的記錄為：\n");printf("%s\t%s\t%d\t%d\n",p->,p->elem.fam,p->elem.pay,p->elem.num);printf("品牌單價數(shù)量\n");scanf("%s",&p->elem.fam);scanf("%d",&p->elem.pay);scanf("%d",&p->elem.num);printf("更新后的記錄為：\n");printf("%s\t%s\t%d\t%d\n",p->,p->elem.fam,p->elem.pay,p->elem.num);}elseprintf("找不到相應的商品資料。\n");}voidWsave(){FILE*fp;In*p;if(head==NULL){printf("你還未有資料。");return;}if((fp=fopen("store.dat","wb"))==NULL)printf("Cannotopenfile!\n");else{for(p=head->next;p!=NULL;p=p->next)if(fwrite(p,sizeof(In),1,fp)!=1)printf("Filewriteerror!\n");}printf("\t\t\t保存成功。\n\n");fclose(fp);}voidRead(){In*p;FILE*fp;if(head==NULL){printf("你還未有資料。");return;}if((fp=fopen("store.dat","rb"))==NULL){printf("CannotOpen.");return;}for(p=head->next;p!=NULL;p=p->next){p=Init();fread(p,sizeof(In),1,fp);printf("%s\t%s\t%d\t%d\n",p->,p->elem.fam,p->elem.pay,p->elem.num);}printf("\n\t\t\t讀取成功\n");fclose(fp);}voidSortUp(){In*p1,*p2,*p3;p3=(In*)malloc(sizeof(In));if(head==NULL){printf("沒有記錄，無法排序。");return;}for(p1=head->next;p1->next!=NULL;p1=p1->next)for(p2=p1->next;p2!=NULL;p2=p2->next)if(p1->elem.pay>p2->elem.pay){p3->elem=p1->elem;p1->elem=p2->elem;p2->elem=p3->elem;}printf("\n已經(jīng)排序好了。\n");List();}voidPreFile(){intFlag=0;In*he,*p,*q;FILE*fp;if((fp=fopen("store.dat","ab+"))==NULL){printf("Openfileerror!\n");exit(0);}he=Init();q=he;p=Init();he->next=p;for(;fread(p,sizeof(In),1,fp)!=0;p=Init()){he->next=p;he=p;p->next=NULL;Flag=1;}if(Flag)head=q;elsehead=NULL;fclose(fp);}通訊錄管理系統(tǒng)題目要求通訊錄一般包括通訊者的編號、姓名、性別、及地址等信息，設計一個通訊錄要求實現(xiàn)通訊者的插入、查詢、刪除、更新、排序操作。structnode{charnum[5];//編號charname[8];//姓名charsex;//性別chartel[8];//charaddress[100];//地址};應用程序功能明確用戶的需求，如操作界面需求，系統(tǒng)功能需求，數(shù)據(jù)的具體流程等。開始運行時界面如下：輸入通訊錄信息后，界面如下：你可以根據(jù)所對應的信息提示進行操作便可對其進行數(shù)據(jù)的記錄與查詢。主要算法模塊描述源程序代碼#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct{charnum[6];charname[10];charsex[5];chartel[13];charaddress[30];}datatype;typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;listnode*p;intmenu_select();linklistcreatelist(void);voidinsertnode(linklisthead,listnode*p);listnode*listfind(linklisthead);voiddelnode(linklisthead);voidprintlist(linklisthead);voidmain(){linklisthead;intm,flag;printf("\n"); printf("\n"); printf("\n"); printf("通訊錄管理系統(tǒng)\n");printf("**************通訊錄信息的建立***************\n");head=createlist();while(flag!=1){ m=menu_select(); switch(m) { case1: printf("**************通訊錄信息添加*****************\n"); printf("**編號(4)姓名(8)性別(5)(11)地址(30)**\n"); printf("***********************************************\n"); p=(listnode*)malloc(sizeof(listnode)); scanf("%s%s%s%s%s",p->data.num,p->,p->data.sex,p->data.tel,p->data.address); insertnode(head,p); break; case2: printf("******************************\n"); printf("*******通訊錄信息查詢*******\n"); printf("******************************\n"); p=listfind(head); if(p!=NULL) { printf("**編號姓名單位地址**\n"); printf("\n"); printf("%s,%s,%s,%s,%s\n",p->data.num,p->,p->data.sex,p->data.tel,p->data.address); printf("\n"); } else printf("沒有你要找的人!\n"); break; case3:printf("***********************************\n");printf("**********通訊信息的刪除***********\n");printf("***********************************\n"); delnode(head); break; case4: printf("***********************************\n"); printf("**********通訊錄鏈表的輸出*********\n"); printf("***********************************\n"); printlist(head); break; case5: flag=1; printf("\t謝謝您的使用！\n"); }}}linklistcreatelist(void){ linklisthead=(listnode*)malloc(sizeof(listnode));listnode*p,*rear; intn;rear=head; printf("初始化輸入通訊錄數(shù):"); scanf("%d",&n); printf("編號(5)姓名(8)性別(5)(11)地址(100)\n"); printf("\n");for(inti=0;i<n;i++){ p=(listnode*)malloc(sizeof(listnode));scanf("%s%s%s%s%s",p->data.num,p->,p->data.sex,p->data.tel,p->data.address);rear->next=p;rear=p;}printf("創(chuàng)立成功!\n");rear->next=NULL;returnhead;}voidinsertnode(linklisthead,listnode*p){listnode*p1,*p2;p1=head;p2=p1->next;while(p2!=NULL&&strcmp(p2->data.num,p->data.num)<0){p1=p2;p2=p2->next;}p1->next=p;p->next=p2;printf("插入成功！\n");}listnode*listfind(linklisthead){listnode*p;charnum[6];charname[10];intxz;printf("\n");printf("1.編號查詢\n");printf("2.姓名查詢\n");printf("\n");printf("請選擇:");p=head->next;scanf("%d",&xz);if(xz==1){printf("請輸入要查找的編號：");scanf("%s",num);while(p&&strcmp(p->data.num,num)<0)p=p->next;if(p==NULL||strcmp(p->data.num,num)>0)p=NULL;}elseif(xz=2){printf("請輸入要查詢者的姓名:");scanf("%s",name);while(p&&strcmp(p->,name)!=0)p=p->next;}returnp;}voiddelnode(linklisthead){intjx;listnode*p,*q;p=listfind(head);if(p==NULL){printf("沒有要刪除的通訊者!:\n");return;}printf("真的要刪除該結點嗎？(1.是/0.不):");scanf("%d",&jx);if(jx==1){q=head;while(q!=NULL&&q->next!=p)q=q->next;q->next=p->next;free(p);printf("通訊者已被刪除!\n");}}voidprintlist(linklisthead){listnode*p;p=head->next;printf("編號姓名性別地址\n");printf("\n");while(p!=NULL){printf("%s,%s,%s,%s,%s\n",p->data.num,p->,p->data.sex,p->data.tel,p->data.address);printf("\n");p=p->next;}}intmenu_select(){ for(;;){intsn;printf("\n");printf("======================\n");printf("1.通訊者的插入\n");printf("2.通訊錄的查詢\n");printf("3.通訊者的刪除\n");printf("4.通訊錄的輸出\n");printf("5.退出通管理系統(tǒng)\n");printf("======================\n");printf("請選擇操作1-5\n");printf("輸入你選擇的數(shù)字:");scanf("%d",&sn);if(sn<0||sn>5)printf("\t輸入錯誤\n");returnsn; }}一元多項式計算題目要求任務：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結果輸入；在上交資料中請寫明：存儲結構、多項式相加的根本過程的算法〔可以使用程序流程圖〕、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改良方法；應用程序功能明確用戶的需求，如操作界面需求，系統(tǒng)功能需求，數(shù)據(jù)的具體流程等。開始運行時界面如下：而后對第二個多項式進行輸入：輸入多項式a和b后，可看到有界面如下：你可以根據(jù)所對應的信息提示進行操作便可對其進行數(shù)據(jù)的記錄與查詢。主要算法模塊描述源程序代碼#include<stdio.h>#include<malloc.h>typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn為結點指針類型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0的話釋放結點else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn){//查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn){//將指數(shù)相同相合并q2->coef+=p->coef;free(p);if(!q2->coef){//系數(shù)為0的話釋放結點q1->next=q2->next;free(q2);}}else{//指數(shù)為新時將結點插入p->next=q2;q1->next=p;}}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一個頭指針為head、項數(shù)為m的一元多項式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新結點以接收數(shù)據(jù)printf("請輸入第%d項的系數(shù)與指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結點}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp){//銷毀多項式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指針后移q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//項數(shù)計數(shù)器if(!q){//假設多項式為空，輸出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項if(q->coef!=1&&q->coef!=-1){//系數(shù)非1或-1的普通情況printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多項式已空，但b多項式非空elsereturn1;//b多項式已空，但a多項式非空}//comparePolynAddPolyn(Polynpa,Polynpb){//求解并建立多項式a+b，返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結點hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case-1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//當相加系數(shù)為0時，釋放該結點}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項式a+b，返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p){//將pb的系數(shù)取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢復pb的系數(shù)p->coef*=-1;returnpd;}//SubtractPolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請輸入a的項數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項式aprintf("請輸入b的項數(shù):");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項式a//輸出菜單printf("**********************************************\n");printf("操作提示：\n\t1.輸出多項式a和b\