1、目 錄 引 言41 需求分析41.1任務與分析41.2測試數據52 概要設計52.1 adt描述52.2程序模塊結構62.3各功能模塊73詳細設計73.1結構體定義83.2 初始化83.3 插入操作83.4創建113.5查詢123.6修改153.7統計173.8刪除184 調試分析224.1問題分析和解決224.2算法的時間復雜度分析224.3經驗和體會225用戶使用說明236測試結果23結 論32致 謝33數據結構課與算法課程 設 計 任 務 書學院名稱： 課程代碼：_ _專 業： 年 級： 一、設計題目高校社團管理二、 主要內容在高校中，為了豐富學生的業余生活，在學校的幫助下，會成立許多社

2、團，少則幾個，多則幾十個。為了有效管理這些社團，要求編寫程序實現以下功能：具體操作：1.畫出社團結構的二叉樹2給出數據結構 應考考慮樹中結點如何表示社團和成員3實現下列操作（1）初始化存儲社團和會員的二叉樹;(2)建立以二叉鏈存儲的社團； （3）查詢：輸入社團名稱或社團中團員姓名，在二叉樹中進行查找，若找到則顯示相應信息；否則顯示未找到信息； （4）修改：輸入社團名稱或社團中團員姓名，修改找到的社團或會員的相關信息； （5）插入：輸入新的社團名稱，在二叉樹中增加一個社團；（6）會員插入：輸入新的會員姓名，在指定的社哮中增加一個會員；（7）統計:統計每個社團中的成員數，并顯示結果；（8）刪除：輸

3、入會員，刪除相關社團中指定的會員；(9)社團刪除：輸入社團名稱，刪除指定的社團。三、具體要求及應提交的材料用c/c+語言編程實現上述內容，并按數學與計算機學院對課程設計說明書規范化要求，寫出課程設計說明書，并提交下列材料：1)課程設計說明書打印稿一份2)課程設計說明書電子稿一份；3)源程序電子文檔一份。四、主要技術路線提示社團管理部門、社團和社團成員構成了完整的二叉樹，二叉樹選用二叉鏈表作為存儲結構。五、進度安排按教學計劃規定，數據結構與算法課程設計為2周，其進度及時間大致分配如下：序號設計內容天數1分析問題，給出數學模型，選擇數據結構22設計算法，給出算法描述13給出源程序清單24編輯、編譯

4、、調試源程序25編寫課程設計報告3總 計10六、推薦參考資料1 嚴蔚敏，吳偉民.數據結構.清華大學出版社出版。 2 嚴蔚敏，吳偉民. 數據結構題集(c語言版) .清華大學出版社.2003年5月。3唐策善，李龍澎.數據結構(作c語言描述) .高等教育出版社.2001年9月4 朱戰立.數據結構(c+語言描述)（第二版本）.高等出版社出版.2004年4月5胡學鋼.數據結構(c語言版) .高等教育出版社.2004年8月指導教師 簽名日期 年 月 日系 主 任 審核日期 年 月 日摘 要 隨著計算機的普及，計算機的應用越來越廣泛，多用于復雜事物的管理。該說明書主要是對高校社團管理系統進行描述，準確清楚的

5、闡述了本系統的功能。本次課程設計實現了對社團和會員的錄入、查詢、修改、插入、統計、刪除等功能，功能詳細全面。關鍵詞：社團；功能；管理； 引 言數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。課程設計是實踐性教學中的一個重要環節，它是以課程為基礎可以涉及和課程相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。1 需求分析1.1任務與分析在高校中，為了豐富學生的業余生活，

6、在學校的幫助下，會成立許多社團，少則幾個，多則幾十個。為了有效管理這些社團，要求編寫程序實現以下功能：具體操作：1.畫出社團結構的二叉樹2給出數據結構 應考考慮樹中結點如何表示社團和成員3實現下列操作（1）初始化存儲社團和會員的二叉樹;(2)建立以二叉鏈存儲的社團； （3）查詢：輸入社團名稱或社團中團員姓名，在二叉樹中進行查找，若找到則顯示相應信息；否則顯示未找到信息； （4）修改：輸入社團名稱或社團中團員姓名，修改找到的社團或會員的相關信息； （5）插入：輸入新的社團名稱，在二叉樹中增加一個社團；（6）會員插入：輸入新的會員姓名，在指定的社哮中增加一個會員；（7）統計:統計每個社團中的成員數

7、，并顯示結果；（8）刪除：輸入會員，刪除相關社團中指定的會員；(9)社團刪除：輸入社團名稱，刪除指定的社團。ruanjian11.2測試數據 ayingyu10fedcb00000圖1-1測試數據2 概要設計2.1 adt描述 adt leaguemanage數據對象：d具有相同特征的數據元素的有限集合;數據關系：rh; r如d為空，則r也為空，leaguemanage為空二叉樹。 否則d不為空，則r=h，h詳細描述如下：1. d中存在唯一的稱之為跟root的節點，它在關系h下無前驅；2. 若d-root不為空，則d-root=d1,dr，切d1,dr互不相交；3. （d1，h1）和（dr，h

8、r）都是二叉樹，分別是跟root的左子樹和右子樹。基本操作： face():選擇用戶要執行的操作；creatbtree（）：創建社團，錄入會員；find():查找社團和會員；alter():修改社團和會員；insert():插入社團和會員；statistic(member *):統計社團中的成員數；deletenode():刪除社團和會員2.2程序模塊結構圖1-2程序模塊結構圖2.2.1結構體定義 struct memberelemtype name;int tag;member *lch;member *rch;2.3各功能模塊face():選擇用戶要執行的操作；creatbtree（）：創

9、建社團，錄入會員；find():查找社團和會員；alter():修改社團和會員；insert():插入社團和會員；statistic(member *):統計社團中的成員數；deletenode():刪除社團和會員3詳細設計3.1結構體定義 struct memberelemtype name;int tag;member *lch;member *rch;3.2 初始化 leaguemanage()root=null;3.3 插入操作 插入社團：if(order=1)char x;coutm-name;m-tag=1;m-lch=m-rch=null;while(p-lch!=null&p-

10、rch!=null)p=p-lch;if(p-lch=null)p-lch=m;elsep-rch=m;cout插入社團成功！endl;coutx;while(x!=y&x!=y&x!=n&x!=n)coutx;if(x=y|x=y)member *p,*s30;elemtype name;int tag;int i=2,j;s1=m;couttagname;while(pare(0)p=new member;p-name=name;p-tag=tag;p-lch=p-rch=null;si=p;j=i/2;if(i%2)=0)sj-lch=p;elsesj-rch=p;i+;couttagn

11、ame;cout錄入成功！endl;system(pause);system(cls); 插入會員：else if(order=2)coutm-name;m-tag=0;m-lch=m-rch=null;coutname;findleague(root,name,isfind,p);if(isfind=false)coutlch!=null&p-rch!=null)p=p-lch;if(p-lch=null)p-lch=m;elsep-rch=m;cout插入會員成功！endl;system(pause);system(cls);3.4創建void leaguemanage:creatbtre

12、e() /創建member *p,*s30;elemtype name;int tag=0;int i=1,j;cout請按照二叉樹的層序，自上而下自左至右順序輸入數據。endl;cout標識符 0：會員 1：社團,輸入會員名為0時結束錄入。endl;couttagname;while(pare(0)if(i=1)while(tag=0)couttagname;p=new member;p-name=name;p-tag=tag;p-lch=p-rch=null;si=p;if(i=1)root=p;elsej=i/2;if(i%2)=0)sj-lch=p;elsesj-rch=p;i+;co

13、uttagname;3.5查詢查詢社團： if(order=1)coutname;findleague(root,name,isfind,m);if(!isfind)cout未找到該社團！endl;elsecout社團：namelch,i);display(m-rch,i);couttag=0)findleague(p-lch,name,isfind,m);findleague(p-rch,name,isfind,m);else if(pare(p-name)findleague(p-lch,name,isfind,m);findleague(p-rch,name,isfind,m);else

14、 if(!pare(p-name)isfind=true;m=p;查詢會員：else if(order=2)coutname;findmember(root,name,isfind,e,m);if(!isfind)cout未找到該會員！tag=1)e=p-name;findmember(p-lch,name,isfind,e,m);findmember(p-rch,name,isfind,e,m);else if(pare(p-name)findmember(p-lch,name,isfind,e,m);findmember(p-rch,name,isfind,e,m);else if(!pa

15、re(p-name)isfind=true;cout會員姓名：name，所屬社團：etag=0)i+;coutnamelch,i);display(p-rch,i);3.6修改修改社團：if(order=1)coutname;findleague(root,name,isfind,m);if(!isfind)cout未找到該社團！endl;elsecout社團：namelch,i);display(m-rch,i);coutm-name;cout修改成功！endl;system(pause);system(cls);修改會員：else if(order=2)coutname;findmembe

16、r(root,name,isfind,e,m);if(!isfind)cout未找到該會員！endl;elsecoutm-name;cout修改成功！tag=0)statistic(p-lch);statistic(p-rch);elseint i=0;cout社團：namelch,i);display(p-rch,i);cout總計：i人lch);statistic(p-rch);3.8刪除刪除社團：if(order=1)coutname;findalter(name,isfind,p,q,m,n);if(isfind=false)cout沒有該社團！endl;elsecout社團：name

17、lch,i);display(m-rch,i);coutyn;if(yn=y|yn=y)if(m=root)destroy(root);root=null;elseif(n-lch=m)destroy(m);n-lch=null;elsedestroy(m);n-rch=null;cout刪除社團成功！endl;system(pause);system(cls);刪除會員：else if(order=2)coutname;findalter(name,isfind,p,q,m,n);if(isfind=false)cout沒有該會員！endl;elsecoutyn;if(yn=y|yn=y)d

18、eletemember(root,m,n);system(pause);system(cls);void leaguemanage:deletemember(member *t,member *p,member *q) /刪除會員bool b=1;member *s,*m;if(p-lch=null)s=p-rch;else if(p-rch=null)s=p-lch;elsem=p;s=p-rch;while(s-lch!=null)m=s;s=s-lch;if(m=p)m-rch=s-rch;elsem-lch=s-rch;p-name=s-name;p-tag=s-tag;delete

19、s;b=0;if(b=1)if(p=root)t=s;else if(q-lch=p)q-lch=s;elseq-rch=s;delete p;cout刪除會員成功！name=name)isfind=true;m=p;n=q;elseq=p;findalter(name,isfind,p-lch,q,m,n);findalter(name,isfind,p-rch,q,m,n);4 調試分析4.1問題分析和解決 主要問題就是怎么區分社團和會員。我用的是一個標識符tag來區分。當tag=0時表示是會員，當tag=1時表示是社團。4.2算法的時間復雜度分析創建：因為創建是按二叉樹的層次，從上到下從

20、左到右依次錄入，唯一所消耗的時間就是計算所插入節點的雙親節點，所以時間復雜度為o（1）；插入：此算法就是找到要插入子樹的最左邊的節點，所以時間復雜度是o（n）；查詢：查詢就是查找要查詢的節點，所以時間復雜度是o（n）；修改：與查詢一樣，時間復雜度是o（n）；刪除：與查詢一樣，時間復雜度是o（n）；統計：使用遞歸來遍歷輸出，所以時間復雜度是o（n）。4.3經驗和體會 鏈表操作要注意指針，當指針沒用好，很有可能就出現錯誤。使用二叉鏈表能很容易的實現一些基本操作。而且只要能熟練的使用遞歸都能完成一些常用的算法，二叉樹的算法主要的就是遞歸的使用。5用戶使用說明用戶登錄系統后根據屏幕上的提示進行相應的操

21、作就可王城一切功能的實現。6測試結果主界面圖 1-3 主界面創建圖 1-4 創建查詢主界面圖 1-5 查詢主界面查詢社團圖 1-6 查詢社團查詢會員圖 1-7 查詢會員修改主界面圖 1-8 修改主界面修改社團圖 1-9 修改社團修改會員圖 1-10 修改會員插入主界面圖 1-11 插入主界面插入社團圖 1-12 插入社團插入會員圖 1-13 插入會員統計圖 1-14 統計界面刪除主界面圖 1-15 刪除主界面刪除社團圖 1-16 刪除社團刪除會員圖 1-17 刪除會員退出圖 1-18 退出界面結 論過本次課程設計可以得出鏈表的操作就是更改指針的指向，但就是因為就是改變指針的指向，所以才做時更應

22、該小心指針的指向位置。鏈表存儲具有非常大的優勢，在內存足夠的情況下，沒有個數限制；而且對鏈表的操作除了查找，其它的操作都非常節約時間。高校社團管理系統總體上完成了對社團的管理工作，圓滿的完成了所有要求。 致 謝在本次課程設計過程中，首先感謝周立章老師，其次感謝我的同學們。他們都給了我很多幫助，讓我順利的完成了本次課程設計。參考文獻1楊寶剛.開展企業管理信息化工作的步驟j.企業管理.2002.（11）.12152 朱戰立.數據結構(c+語言描述)（第二版本）.高等出版社出版.2004年4月3 王立柱.c/c+與數據結構.北京：清華大學出版社，20024 顧元剛.數據結構簡明教程.南京：東南大學出

23、版社等，20035 郭福順，王曉芬，李蓮治數據結構（修訂本），大連理工大學出版社，19976 美mark allen weiss，數據結構與算法分析c語言描述(英文版第2版)，人民郵電出版社，2005.87 李春葆著，數據結構教程，清華大學出版社，2005.1所有代碼：#include#includeusing namespace std;typedef string elemtype;struct memberelemtype name; /姓名int tag; /標識符,tag=0表示是會員，tage=1表示是社團member *lch;member *rch;class leaguema

24、nageprivate:member *root;public:leaguemanage()root=null;leaguemanage()destroy(root);root=null;void creatbtree(); /建立以二叉鏈存儲的社團void find(); /輸入社團名稱或社團中團員姓名查詢void alter(); /修改void insert(); /插入void statistic()statistic(root); /統計每個社團中的成員數void deletenode(); /刪除private:void findmember(member*,string,bool

25、&,elemtype,member*&); /查找會員void findleague(member*,string,bool&,member*&); /查找社團void findalter(string,bool&,member*,member*,member*&,member *&);/找雙親void insert(member*,string); /插入void statistic(member *p);void deletemember(member*,member*,member*); /刪除會員void destroy(member*); /刪除所有節點void display(me

26、mber*,int&); /遍歷輸出;void leaguemanage:creatbtree() /創建member *p,*s30;elemtype name;int tag=0;int i=1,j;cout請按照二叉樹的層序，自上而下自左至右順序輸入數據。endl;cout標識符 0：會員 1：社團,輸入會員名為0時結束錄入。endl;couttagname;while(pare(0)if(i=1)while(tag=0)couttagname;p=new member;p-name=name;p-tag=tag;p-lch=p-rch=null;si=p;if(i=1)root=p;e

27、lsej=i/2;if(i%2)=0)sj-lch=p;elsesj-rch=p;i+;couttagname;void leaguemanage:find() /查找int order=-1;int i=0;member *m=null;elemtype e;bool isfind=false;string name;cout *endl;cout * 1、查詢社團 *endl;cout * 2、查詢會員 *endl;cout * 3、退出 *endl;cout *endl;coutorder;while(order!=1&order!=2&order!=3)coutorder;if(ord

28、er=1)coutname;findleague(root,name,isfind,m);if(!isfind)cout未找到該社團！endl;elsecout社團：namelch,i);display(m-rch,i);coutendl;system(pause);system(cls);else if(order=2)coutname;findmember(root,name,isfind,e,m);if(!isfind)cout未找到該會員！tag=0)findleague(p-lch,name,isfind,m);findleague(p-rch,name,isfind,m);else

29、 if(pare(p-name)findleague(p-lch,name,isfind,m);findleague(p-rch,name,isfind,m);else if(!pare(p-name)isfind=true;m=p;void leaguemanage:findmember(member *p,string name,bool &isfind,elemtype e,member *&m) /查找會員if(p!=null)if(p-tag=1)e=p-name;findmember(p-lch,name,isfind,e,m);findmember(p-rch,name,isfi

30、nd,e,m);else if(pare(p-name)findmember(p-lch,name,isfind,e,m);findmember(p-rch,name,isfind,e,m);else if(!pare(p-name)isfind=true;cout會員姓名：name，所屬社團：eendl;m=p;void leaguemanage:alter() /修改int order=-1;int i=0;elemtype e;bool isfind=false;member *m=null;string name;cout *endl;cout * 1、修改社團 *endl;cout

31、* 2、修改會員 *endl;cout * 3、退出 *endl;cout *endl;coutorder;while(order!=1&order!=2&order!=3)coutorder;if(order=1)coutname;findleague(root,name,isfind,m);if(!isfind)cout未找到該社團！endl;elsecout社團：namelch,i);display(m-rch,i);coutm-name;cout修改成功！endl;system(pause);system(cls);else if(order=2)coutname;findmember

32、(root,name,isfind,e,m);if(!isfind)cout未找到該會員！endl;elsecoutm-name;cout修改成功！endl;system(pause);system(cls);elsesystem(cls);void leaguemanage:insert()int order;bool isfind=false;member *m=new member;member *p=root;string name;cout *endl;cout * 1、插入社團 *endl;cout * 2、插入會員 *endl;cout * 3、退出 *endl;cout *en

33、dl;coutorder;while(order!=1&order!=2&order!=3)coutorder;if(order=1)char x;coutm-name;m-tag=1;m-lch=m-rch=null;while(p-lch!=null&p-rch!=null)p=p-lch;if(p-lch=null)p-lch=m;elsep-rch=m;cout插入社團成功！endl;coutx;while(x!=y&x!=y&x!=n&x!=n)coutx;if(x=y|x=y)member *p,*s30;elemtype name;int tag;int i=2,j;s1=m;c

34、outtagname;while(pare(0)p=new member;p-name=name;p-tag=tag;p-lch=p-rch=null;si=p;j=i/2;if(i%2)=0)sj-lch=p;elsesj-rch=p;i+;couttagname;cout錄入成功！endl;system(pause);system(cls);else if(order=2)coutm-name;m-tag=0;m-lch=m-rch=null;coutname;findleague(root,name,isfind,p);if(isfind=false)coutlch!=null&p-rch!=null)p=p-lch;if(p-lch=null)p-lch=m;elsep-rch=m;cout插入會員成功！tag=0)statistic(p-lch);sta