第一篇：《數(shù)據(jù)結(jié)構(gòu)》課程設計報告-封面及摘要

課程設計(論文)

題 目 名 稱

一元多項式的計算

課 程 名 稱

數(shù)據(jù)結(jié)構(gòu)課程設計

學 生 姓 名

周靈

學

號

0941301095

系、專

業(yè)

信息工程系、信息類

指 導 教 師

申壽云

2010年 12 月 22 日

摘 要

設計一個簡單程序，來計算一元多項式的加法、減法。首先在設計的時候就想了一下，應該運用到那些知識點，不管是C語言還是數(shù)據(jù)結(jié)構(gòu)的。首先我們想到的是應該運用到線性表的相關知識，運用到單鏈表（數(shù)據(jù)域+指針域）的存取結(jié)構(gòu)，方便存儲和查找，將兩個多項式y(tǒng)1和y2分別用鏈表進行存放，可以設置兩個指針coef和exp,分別從多項式y(tǒng)1和y2的首結(jié)點移動，比較coef和expn所指結(jié)點的指數(shù)項，此課程設計分為五各部分（多項式存儲結(jié)構(gòu)的定義，輸入構(gòu)成多項式的項，多項式的建立，多項式的打印輸出，多項式的相加），本課程我將用源代碼和流程圖來說明和設計我的論文。

關鍵詞：線性表；單鏈表；選擇；循環(huán)

第二篇：數(shù)據(jù)結(jié)構(gòu)課程設計報告 封面

Harbin Institute of Technology at Weihai

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

設計題目：

院

系：

班

級：

學

號：

組

號：

設 計 者：

哈爾濱工業(yè)大學（威海）計算機科學與技術學院

哈爾濱工業(yè)大學（威海）《數(shù)據(jù)結(jié)構(gòu)課程設計》報告

前 言

數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的必修、主干課程之一，它旨在使讀者學會分析研究數(shù)據(jù)對象的特性，學會數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及相應的運算(操作)，把現(xiàn)實世界中的問題轉(zhuǎn)化為計算機內(nèi)部的表示和處理，這是一個良好的程序設計技能訓練的過程。在整個教學或?qū)W習過程中，解題能力和技巧的訓練是一個重要的環(huán)節(jié)。

本課題設計要求學生分組進行（每組1-2人），自行選題，選題的思想是根據(jù)實際需要進行調(diào)研，以組為單位提交課程設計任務書，給出所選項目的背景和意義，由導師確定選題的級別，主要是以實用性為主，開發(fā)一個具有實際價值的項目，經(jīng)過2周的課程設計后接受課程設計組老師的解題驗收。

第三篇：數(shù)據(jù)結(jié)構(gòu)課程設計報告

數(shù)據(jù)結(jié)構(gòu)課程設計

散列表的應用:插隊買票

專業(yè) 計算機科學與技術（網(wǎng)絡技術）

金玲 計算機131 1310704114 張靜林 2015年1月23日 學生姓名 班學級 號

指導教師 完成日期

目錄概述……………………………………………………………………………………1 1.1 課程設計目的……………………………………………………………………….1 1.2 課程設計內(nèi)容……………………………………………………………………….1 2 系統(tǒng)需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統(tǒng)概要設計…………………………………………………………………………2 3.1 系統(tǒng)流程圖………………………………………………………………………….2 4 系統(tǒng)詳細設計…………………………………………………………………………3 5 測試……………………………………………………………………………………5 5.1 測試方案…………………………………………………………………………….5 5.2 測試結(jié)果…………………………………………………………………………….5 6 小結(jié)……………………………………………………………………………………5 參考文獻…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述

1.1 課程設計目的

數(shù)據(jù)結(jié)構(gòu)課程設計是為數(shù)據(jù)結(jié)構(gòu)課程獨立開設的實踐性教學環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設計對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強學生的實際動手能力和提高學生綜合素質(zhì)是十分必要的。課程設計的目的：

1．要求學生達到熟練掌握C語言的基本知識和技能。

2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，具備初步的獨立分析和設計能力。3．提高程序設計和調(diào)試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。

4．培養(yǎng)算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。

5．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能。

1.2課程設計內(nèi)容

本課程設計的任務是寫一個程序模擬這種情況。每個隊伍都允許插隊。如果你在排隊，有一個以上的朋友要求插隊，則你可以安排他們的次序。每次一個人入隊，并且如果這個入隊的人發(fā)現(xiàn)隊伍中有自己的朋友，則可以插入到這個朋友的后面；當隊伍中的朋友不止一個的時候，這個人會排在最后一個朋友的后面；如果隊伍中沒有朋友，則他只能夠排在這個隊伍的最后面。每一個入隊的人都先進行上述的判斷。當隊伍前面的人買到車票之后，依次出隊。系統(tǒng)需求分析

2.1 主體功能

程序從“input.txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數(shù)目n（1<=n<=1000)。對于一個朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個數(shù)以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過四個字母，由{A，B，...，Z，a，b，...，z}組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數(shù)據(jù)結(jié)束。

下面是一些具體命令：.ENQUEUE——X入隊;.DEQUEUE——排隊頭的人買票，離開隊伍，即出隊；.STOP——一個測試用例結(jié)束。

測試結(jié)果輸出到“output.txt”文件中。每個測試用例第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個出隊命令，輸出剛買票離開隊伍的人名。兩個測試試用例 之間隔一空行，最后一個用例結(jié)束不輸出空行。系統(tǒng)概要設計

3.1 系統(tǒng)流程圖 系統(tǒng)詳細設計

本題目主要解決兩個問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

用散列表來存放和查找數(shù)據(jù)。由于最多有1000個朋友組，每組最多有1000人，使用平方探測法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素數(shù)）。同一個組內(nèi)的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個組group，另外用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計算一個以64為階的多項式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。

#define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標志位，該單元是否被占用*/ };圖4.1數(shù)據(jù)結(jié)構(gòu)：散列表

Int Hash(char *key,int TableSize){

Int HashVal=0;

While(key!=NULL)

HashVal=(HashVal<<6)+*key;

Return HashVal%TableSize;} 圖4.2散列函數(shù)

Long int Find(PtrToHash hash,char *c){

key=c;

CurrentPos=Hash(key,TableSize);

CollisionNum=0;

While((單元被占用)and(單元內(nèi)的名字與查找的名字不同))

{

CurrentPos+=2*(++CollisionNum)-1;

If(CurrentPos>=TabSize)

CurrentPos=TabSize;

}

Return CurrentPos;} 圖4.3用平方探測法解決沖突

第二個問題是關于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊列來模擬。由于有插隊現(xiàn)象的存在，不能單純的用一個數(shù)組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標記來表示當前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖4.4所示。不用鏈表是因為鏈表存放指針也需要空間，并且鏈表插入、刪除的效率沒有數(shù)組高。

typedef struct Que *PtrToQue;struct Que

/*隊列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };圖4.4數(shù)據(jù)結(jié)構(gòu)：隊列

輸入ENQUEUE命令，如果隊伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊尾。入隊時，用一個數(shù)組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數(shù)組被稱為“插隊數(shù)組”。

輸入DEQUEUE命令，則根據(jù)“先進先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列重的第一個。程序結(jié)構(gòu)如圖4.5所示。

While(讀測試文件){

if(輸入”ENQUEUE”)

{

讀入名字；

插入散列表；

插入隊列；

}

else if(輸入”DEQUEUE”)

{

刪除隊列第一個名字；

將該名字輸出到文件；

}

else stop;} 圖4.5入隊、出隊操作 測試

5.1 測試方案 按輸入要求輸入正常測試數(shù)據(jù)，測試程序是否能正確解決問題，得到正確答案。應注意邊界測試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時需寫程序生成測試用例。

不按輸入要求輸入數(shù)據(jù)，測試程序能否對輸入內(nèi)容進行數(shù)據(jù)合法性檢測并進行相應的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過4個字母等情況下的測試用例。5.2 測試結(jié)果 小結(jié)

在前面的學習過程中我們學到了很多知識而這次課程設計又是對我們所學的 一次總結(jié)，剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關于程序方面的，可這遠遠不夠，這只是小小的開始。我們必須掌握很多已學的知識才能很好的完成本次的課程設計。在這次課程設計中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經(jīng)驗不足，有時雖然是一個很小的問題但解決起來卻花費了我不少的時間，值得欣慰的是，當自己苦思冥想或者和其它同學一起探討把問題解決的時候我還是覺得獲益非淺，這就是在摸索中尋求到的知識。在設計時也免不了存在著些不足，所以在今后的學習中我會努力取得更大的進步。雖然對著電腦做程序，有些累，可當看到勞動成果時，卻有另一番滋味。

參考文獻

[1]范策，周世平，胡曉琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：機械工業(yè)出版社，2004 [2]嚴蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.北京：清華大學出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結(jié)構(gòu)與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數(shù)據(jù)結(jié)構(gòu)實用教程（第二版）》.北京：清華大學出版社，2006

附錄

附錄1 源程序清單

#include #include #include #define TabSize 2000003

/*散列表大小TabSize 是大于表最大空間的素數(shù)*/ #define Max 1000001

/*隊列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que

/*隊列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };

int hashedx=0;

/*標記元素是否已經(jīng)在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum;

key=c;for(CurrentPos=0;*key;++key)

/*散列函數(shù)，計算散列值*/

CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;

/*散列值*/ CollisionNum=0;/*如果當前單元被占用：單元內(nèi)的元素與當前操作的名字不同，使用平方探測法解決沖突；與當前操作的名字相同，則直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)))

{

/*平方探測法*/

CurrentPos+=2*(++CollisionNum)-1;

if(CurrentPos>=TabSize)

CurrentPos-=TabSize;}

if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))

/*元素已經(jīng)在散列表里*/

hashedx=1;else /*元素不在散列表里*/

hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ }

int main(){ long int Find(PtrToHash hash,char *c);

/*查找在散列表中的位置*/

PtrToHash hash;

/*散列表*/ PtrToQue queue;

/*隊列*/ int *grouppos;

/*記錄每個朋友組的最后一位，即插隊數(shù)組*/ int n;

/*測試用例數(shù)目*/ int num;

/*當前測試用例序號*/ long int i,ii,j,key,temp;long int head,last;

/*隊列的頭和尾*/ char c[8],tempc[8];

/*名字*/ FILE *fpin,*fpout;

/*輸入、輸出文件指針*/

if(!(fpin=fopen(“input.txt”,“r”)))

/*打開測試文件*/ {

printf(“fopen error!”);

/*文件打開錯誤*/

return-1;} if(!(fpout=fopen(“output.txt”,“w”)))

/*打開輸出文件*/ {

printf(“fopen error!”);

return-1;}

hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*為散列表申請空間*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*為隊列申請空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請空間記錄每個朋友組的最后一位*/ for(i=0,j=1;i

queue[i].Index=j;queue[i-1].Index=0;/*最后一個單元的后繼單元是第0個，形成環(huán)*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當前測試用例的朋友組數(shù)*/ {

if(n<1||n>1000)

/*處理異常輸入n*/

{

fprintf(fpout,“n is out of rangen”);

return-1;

}

num++;

if(num!=1)

/*兩個測試用例間輸入一空行*/

fprintf(fpout,“n”);

for(i=0;i

hash[i++].info=0;

/*初始化散列表，標記位置0*/

for(i=0;i

/*對每一組朋友*/

{

fscanf(fpin,“%d”,&j);

/*當前組里的人數(shù)*/

if(j<1||j>1000)

/*處理異常輸入j*/

{

fprintf(fpout,“j is out of rangen”);

return-1;

}

for(;j;--j)

{

fscanf(fpin,“%s”,c);

/*輸入名字*/

for(ii=0;ii

tempc[ii]='