數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)論文-基礎(chǔ)軟件設(shè)計(jì)

1、課程設(shè)計(jì) (論文 )任務(wù)書信息學(xué)院計(jì)算機(jī)專業(yè) 2014-1 班一、課程設(shè)計(jì)(論文)題目基礎(chǔ)軟件設(shè)計(jì)二、課程設(shè)計(jì)(論文)工作自2015年12月28日起至2016年 1月 8日止。三、課程設(shè)計(jì)(論文)地點(diǎn) : 5-205四、課程設(shè)計(jì)(論文)內(nèi)容要求：1本課程設(shè)計(jì)的目的1、 使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們在程序中的使用方法。2、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和

2、技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；2課程設(shè)計(jì)的任務(wù)及要求1）基本要求：1. 分析題目，查閱相關(guān)資料；2. 算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3. 編寫代碼并調(diào)試；4. 完成課程設(shè)計(jì)報(bào)告。2）創(chuàng)新要求：在基本要求達(dá)到后，可進(jìn)行創(chuàng)新設(shè)計(jì)。3）課程設(shè)計(jì)論文編寫要求（ 1）要按照書稿的規(guī)格打印謄寫論文（ 2）論文包括目錄、緒論、正文、小結(jié)、參考文獻(xiàn)、謝辭、附錄等（ 3）課程設(shè)計(jì)論文裝訂按學(xué)校的統(tǒng)一要求完成4）答辯與評分標(biāo)準(zhǔn)：（ 1）完成問題的解決方法分析： 20 分；（ 2）算法思想（流程）： 20 分；（ 3）數(shù)據(jù)結(jié)構(gòu)： 20 分；1（ 4）測試數(shù)據(jù)： 20 分（ 5）回答問

3、題： 20 分。5）參考文獻(xiàn)： C 程序設(shè)計(jì)（第二版）譚浩強(qiáng)著清華大學(xué)出版社出版 C+ 程序設(shè)計(jì)譚浩強(qiáng)著清華大學(xué)出版社出版數(shù)據(jù)結(jié)構(gòu)（C 語言版）嚴(yán)蔚敏、吳偉民著 清華大學(xué)出版社出版6）課程設(shè)計(jì)進(jìn)度安排內(nèi)容天數(shù)地點(diǎn)構(gòu)思及收集資料圖書館編程與調(diào)試實(shí)驗(yàn)室撰寫論文學(xué)生簽名 :_2015年 12月 28 日課程設(shè)計(jì) ( 論文 ) 評審意見（ 1）完成問題分析（ 20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（ 2）算法思想（ 20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（ 3）數(shù)據(jù)結(jié)構(gòu)（ 20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（ 4）測試數(shù)據(jù)（ 20分）：優(yōu)（）、良（）、中（

4、）、一般（）、差（）；（ 5）回答問題（ 20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（ 6）格式規(guī)范性及考勤是否降等級：是（）、否（）評閱人：趙海霞職稱：講師22016年1 月 10 日目錄一、綜合軟件設(shè)計(jì)目的二、綜合軟件設(shè)計(jì)內(nèi)容1、課程設(shè)計(jì)的題目及簡介2、設(shè)計(jì)說明3、程序部分清單三、測試數(shù)據(jù)：四、總結(jié)（寫出心得和總結(jié)）五、參考文獻(xiàn)3一、綜合軟件設(shè)計(jì)目的1、使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、 存儲結(jié)構(gòu)和操作實(shí)現(xiàn)算法， 以及它們在程序中的使用方法。2、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資

5、料， 提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。 初步掌握軟件開發(fā)過程的問題分析、 系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；二、綜合軟件設(shè)計(jì)內(nèi)容1.課程題目及簡介題目：基礎(chǔ)軟件設(shè)計(jì)簡介：使用 C 語言實(shí)現(xiàn)編碼，實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)各種功能。全面性涉及到所有內(nèi)容，系統(tǒng)的總結(jié)了數(shù)據(jù)結(jié)構(gòu)各個(gè)方面。2.設(shè)計(jì)說明：此程序采用多菜單分布執(zhí)行的方式，可以簡潔、方便的控制程序的運(yùn)行。主菜單下含有多個(gè)子菜單對應(yīng)著不同類型的數(shù)據(jù)結(jié)構(gòu)內(nèi)容。分別是：線性表、棧、串、隊(duì)列、樹與森林、圖、排序和查找。各個(gè)子菜單下的每項(xiàng)功能均與數(shù)據(jù)結(jié)構(gòu)內(nèi)容相關(guān)。線性表菜單涉及到綜述數(shù)據(jù)、 數(shù)據(jù)

6、結(jié)構(gòu)和抽象數(shù)據(jù)類型。 其余各子菜單也各自涉及到各種數(shù)據(jù)結(jié)構(gòu)的基本類型及其功能。43.核心代碼/頭文件#include#include#include#include#include#include#include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MaxLength 50typedef int Status;void chuanshun();void xianshun();void zhan();void xianxingbiao();void paixu();/void dui();void san

7、lie();void chu();void chazhao();5/棧定義typedef int SElemType;typedef structSElemType dataMaxLength;int top;SqStack;Status InitStack(SqStack *S);Status PushStack(SqStack *S,SElemType e); void TraverseStack(SqStack S);Status GetTop(SqStack S,SElemType *e); Status PopStack(SqStack *S,SElemType *e); Statu

8、s ClearStack(SqStack *S);typedef struct StackNodeSElemType data;struct StackNode *next;StackNode,*LinkStackPtr;typedef structLinkStackPtr top;int count;LinkStack;Status InitStack1(LinkStack *S);Status PushStack1(LinkStack *S,SElemType e); void TraverseStack1(LinkStack S);Status PopStack1(LinkStack *

9、S,SElemType *e); Status ClearStack1(LinkStack *S);6typedef char SElemTypec;typedef structchar data50;int top;SqStackc;Status InitStackc(SqStackc *S);Status PushStackc(SqStackc *S,SElemTypec e); void TraverseStackc(SqStackc S);Status ClearStackc(SqStackc *S);Status PopStackc(SqStackc *S,SElemTypec *e

10、);void shuzhizhuanhuan();void migongwenti();void hangbianji();void biaodashi();void kuohaopipei();void zhanshun();void zhanlian();void cheng();/線性表定義typedef int LElemType;typedef structLElemType dataMaxLength;int Length;7SeqList;Status InitList(SeqList *L);Status ListInsert(SeqList *L,int i,LElemTyp

11、e e); SeqList CreatList(SeqList L); void TraverseList(SeqList *L);Status DeleteList(SeqList *L,int n);Status FindList(SeqList *L,LElemType e);Status AddList(SeqList *L,LElemType e);LElemType FindnumList(SeqList *L,int n);Status DestroyList(SeqList *L);typedef struct NodeLElemType data;struct Node *n

12、ext;Node;typedef struct Node *LinkList;Status InitList1(LinkList *L);Status ListLength1(LinkList L);Status ListInsert1(LinkList *L,int n,LElemType e); void TraverseLint1(LinkList L);/Status ListDelete1(LinkList *L,intListTraverse1 n); Status ListDelete1(LinkList *L,int i,LElemType *e); Status Findnu

13、mList1(LinkList *L,int n,LElemType *e); Status LocateElem1(LinkList *L,LElemType e); Status CreatListHead1(LinkList *L); Status ClearList1(LinkList *L);Status CreateListTail1(LinkList *L,int n);8void xianlian();void shuanglian();void er();/串定義typedef char StringMaxLength+1;Status CreatStr(String T,c

14、har *chars);void OutputStr(String T);Status LengthStr(String T);Status CompareStr(String S,String T);Status ConcatStr(String T,String S1,String S2); Status SubString(String sub,String S1,int n,int m); int Index(String S, String T, int pos);Status StrInsert(String S,int pos,String T);Status StrDelete

15、(String S,int pos,int len);Status Replace(String S,String T,String V);void chuanshun();void chuanlian();void chuandui();void chaun();typedef char TElemType;typedef struct SNodechar data;struct SNode *next;SNode;typedef struct SNode *LString;Status InitStr(LString *T);9Status InsertStr(LString *T,LEl

16、emType chars);/隊(duì)列typedef int QElemType;typedef structQElemType dataMaxLength;int front;int rear;SqQueue;Status InitQueue(SqQueue *Q);Status TraverseQueue(SqQueue Q);Status InsertQueue(SqQueue *Q,QElemType e); Status DeleteQueue(SqQueue *Q,QElemType *e); Status ClearQueue(SqQueue *Q);Status EmptyQueu

17、e(SqQueue Q);int LengthQueue(SqQueue Q);void duishun();void xunhuandui();void duilie();typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePar;typedef structQueuePar front,rear;LinkQueue;10Status InitQueue1(LinkQueue *Q);void duilian();void kuaipai();void erchapaixu();void xier();void

18、zhipai();void guibing();void jishu();void xuanze();void shushun();void jian();void jia();void shu();Status InitStack(SqStack *S)S-top=-1;return OK;Status PushStack(SqStack *S,SElemType e)if(S-top=MaxLength-1)printf( 此棧已滿！ n);return ERROR;S-top+;S-dataS-top=e;return OK;11void TraverseStack(SqStack S)

19、int i;for(i=0;inext=NULL;return OK;Status ListLength1(LinkList L)int i=0;LinkList p=L-next;while(p)i+;p=p-next;return i;12Status ListInsert1(LinkList *L,int n,LElemType e)int i;LinkList p,s;p=*L;i=1;while(p&inext;i+;if(!p|in)printf( 該節(jié)點(diǎn)不存在！ n);s=(LinkList)malloc(sizeof(Node);s-data=e;s-next=p-next;p

20、-next=s;return OK;void ListTraverse1(LinkList L)LinkList p=L-next;while(p)printf(%d ,p-data);p=p-next;printf(n);13Status CreatStr(String T,char *chars)int i;if(strlen(chars)MaxLength)return ERROR;elseT0=strlen(chars);for(i=1;i=T0;i+)Ti=*(chars+i-1);return OK;void OutputStr(String T)int i;for(i=1;i=T

21、0;i+)printf(%c,Ti);printf(n);Status LengthStr(String S1)return S10;Status CompareStr(String S,String T)int i;for(i=1;i=S0&i=T0;i+)if(Si!=Ti)return Si-Ti;14return S0-T0;Status ConcatStr(String T,String S1,String S2)int i;if(S10+S20=MaxLength)for(i=1;i=S10;i+)Ti=S1i;for(i=1;i=S20;i+)TS10+i=S2i;T0=S10+

22、S20;return OK;elsefor(i=1;i=S10;i+)Ti=S1i;for(i=1;ifront=0;Q-rear=0;returnOK;15Status TraverseQueue(SqQueue Q)int i;i=Q.front;while(i+Q.front)!=Q.rear)printf(%d ,Q.datai);i=(i+1)%MaxLength;printf(n);return OK;Status InsertQueue(SqQueue *Q,QElemType e)if (Q-rear+1)%MaxLength = Q-front)return ERROR;Q-

23、dataQ-rear=e;returnOK;Status DeleteQueue(SqQueue *Q,QElemType *e)if (Q-front = Q-rear)return ERROR;*e=Q-dataQ-front;Q-front=(Q-front+1)%MaxLength;returnOK;/二叉排序樹typedef struct TNodeint data;16struct TNode *lchild;struct TNode *rchild;TNode,*BSTree;bool searchTree(BSTree T,int e,BSTree parent,BSTree

24、&p)if(!T)p=parent;return false;elseif(e=T-data)p=T;return true;else if(edata)return searchTree(T-lchild,e,T,p);elsereturn searchTree(T-rchild,e,T,p);bool InsertTree(BSTree &T,int e)BSTree p;if(!searchTree(T,e,NULL,p)BSTree pNew=(BSTree)malloc(sizeof(TNode);pNew-data=e;pNew-lchild=pNew-rchild=NULL;17if(!p)T=pNew;else if(edata)p-lchild=pNew;elsep-rchild=pNew;elsereturn false;void TraverseTree(BSTree T)if(T)if(T-lchild)TraverseTree(T-lchild);printf(%d ,T-data);if(T-r