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

2、技能；3.提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；2課程設計的任務及要求1）基本要求：1. 分析題目，查閱相關資料；2. 算法設計、數據結構設計；3. 編寫代碼并調試；4. 完成課程設計報告。2）創新要求：在基本要求達到后，可進行創新設計。3）課程設計論文編寫要求（ 1）要按照書稿的規格打印謄寫論文（ 2）論文包括目錄、緒論、正文、小結、參考文獻、謝辭、附錄等（ 3）課程設計論文裝訂按學校的統一要求完成4）答辯與評分標準：（ 1）完成問題的解決方法分析： 20 分；（ 2）算法思想（流程）： 20 分；（ 3）數據結構： 20 分；1（ 4）測試數據： 20 分（ 5）回答問

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

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

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

6、結構和抽象數據類型。 其余各子菜單也各自涉及到各種數據結構的基本類型及其功能。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);/隊列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( 該節點不存在！ 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