第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——約瑟夫環(huán)報告(含代碼)

#include #include

typedef struct LNode {

//數(shù)據(jù)域

int cipher;

//密碼

int number;

//編號

struct LNode *next;

//指針域 }LNode,*LinkList;

void InitList(LinkList &L)

//創(chuàng)建一個只有頭結(jié)點鏈表 { L =(LinkList)malloc(sizeof(LNode));if(!L){

exit(1);

printf(“/n/nError!/n/n”);} L->next = L;}

void CreateList(int n,LinkList &L)//初始化循環(huán)單鏈表 { LinkList p,q;q = L;printf(“分別輸入每個人的密碼：”);for(int i = 1;i <= n;i++){

int k;

scanf(“%d”,&k);

if(k <= 0)

{

printf(“nn密碼有誤!nn”);

exit(1);

}

p =(LinkList)malloc(sizeof(LNode));

if(!p)

{

exit(1);

printf(“/n/nError!/n/n”);

}

p->cipher = k;

p->number = i;

L->next = p;

L = p;} L->next = q->next;free(q);}

void PrintList(int x,int n,LinkList L)//輸出出列順序 { LinkList p,q;p = L;for(int i = 1;i <= n;i++){

for(int j = 1;j < x;j++)

p = p->next;

q = p->next;

x = q->cipher;

printf(“%d ”,q->number);

p->next = q->next;

free(q);} }

int main(){ printf(“=============約瑟夫環(huán)==============nnn”);

int n,x;LinkList L;L = NULL;InitList(L);

//構(gòu)造空鏈表

printf(“輸入初始密碼：”);scanf(“%d”,&x);

//初始密碼為x printf(“n”);printf(“輸入?yún)⑴c總?cè)藬?shù)：”);scanf(“%d”,&n);

//總共的人數(shù)n printf(“n”);CreateList(n,L);

//建立好一個約瑟夫環(huán)

printf(“nnn===================================nn”);

printf(“出列編號為：”);PrintList(x,n,L);

//輸出出列順序

printf(“nn”);return 0;}

第二篇：數(shù)據(jù)結(jié)構(gòu)報告--約瑟夫環(huán)范文

實習(xí)報告

題目:約瑟夫環(huán)

班級：08052712學(xué)號: 08052211姓名: 葛俊峰

一、需求分析

1.本演示程序中，編號為1，2，?，n的n個人按順時針方向圍坐一圈，每個人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，如此下去，直到所有人全部出列為止。

2.演示程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入相應(yīng)數(shù)據(jù)（即總?cè)藬?shù)，m的值，每個人所持的密碼），運算結(jié)果顯示在其后。

3.程序執(zhí)行的命令包括：

（1）構(gòu)造鏈表；（2）輸入數(shù)據(jù)；（3）執(zhí)行報數(shù)，儲存出列人的序號，刪除出列人的信息以及把出列人的密碼賦給m；（4）結(jié)束。

4.測試數(shù)據(jù)：

m的初始值為20；n＝7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6，則這正確的出列順序為6，1，4，7，2，3，5。

二、概要設(shè)計

為了實現(xiàn)上述操作，應(yīng)以單向循環(huán)鏈表為存儲結(jié)構(gòu)。為此，需要1個抽象數(shù)據(jù)類型：線性表。

1.線性表的抽象數(shù)據(jù)類型為：

ADT List{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,?，n,n≥0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2,3,?,n}

基本操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個空的線性表L。

}ADT List

2.本程序包括三個模塊:

1）主程序模塊：

void main（）{

初始化；

輸入數(shù)據(jù)；

函數(shù)調(diào)用；

}

2）構(gòu)造鏈表并輸入每個人信息的模塊-----實現(xiàn)線性表的抽象數(shù)據(jù)類型；

3）運行模塊-----模擬約瑟夫環(huán)依次出列；

各模塊之間調(diào)用關(guān)系如下：

主程序模塊

↓

構(gòu)造鏈表并輸入每個人信息的模塊

↓

運行模塊

三、詳細(xì)設(shè)計

1.結(jié)點類型和指針類型

typedef struct Node{

int num;

int password;

struct Node *next;

}LNode,*LinkList;//結(jié)點類型,指針類型

Status MakeNode（LinkList &p，Elem Type e）

{

//分配由p指向的數(shù)據(jù)元素為e、后繼為“空”的特點，并返回TRUE，//若分配失敗，則返回FALSE

P=(LinkType)malloc（sizeof（NodeType））；

If（！p）return FALSE；

p->data=e；p->next=null；return TRUE；

}

viod Free Node（Link Type &p）

{

//釋放p所指結(jié)點

}

2.主函數(shù)和其他函數(shù)

int main()

{

//主函數(shù)

LinkList L = NULL;

LinkList s ,r;

int n,i,j,m;//初始化

printf(“請輸入人數(shù)nn”);

scanf(“%d”,&n);

printf(“請輸入mn”);

scanf(“%d”,&m);

printf(“請依次輸入每個人的密碼n”);//輸入數(shù)據(jù)

CreatList(L,s,r,n);//創(chuàng)建鏈表run(L,n,m);//模擬約瑟夫環(huán)并輸出

return 0;

}//main

void CreatList(LinkList &L,LinkList &s,LinkList &r,int n)

{

//創(chuàng)建鏈表

int i=1;

s=(LNode*)malloc(sizeof(LNode));//分配空間

scanf(“%d”,&s->password);//輸入密碼

s->num = i;//序號為i

if(L==NULL)

L=s;

else

r->next=s;

r=s;//為下次連接做準(zhǔn)備

for(i=2;i<=n;i++)

{

s=(LNode*)malloc(sizeof(LNode));//分配空間

scanf(“%d”,&s->password);

s->num = i;

r->next=s;//連接到下個結(jié)點

r=s;//為下次連接做準(zhǔn)備

}

r->next = L;//閉合L = r;

} // void CreatList

void run(LinkList &L,int n,int m)

{

//模擬約瑟夫環(huán)并輸出

LinkList s,r;

int i,j;

for(i = 0;i < n;i ++)

{

for(j = 1;j < m;j ++)

L = L->next;//報數(shù)

s = L->next;

r = s->next;

printf(“%dn”,s->num);//輸出序號

m = s->password;

L->next = r;

free(s);//刪除結(jié)點

}

}//run

3.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu):

main

↓↓

CreatListrun

↓↓

Make NodeFree Node

四、調(diào)試分析

1.剛開始由于使用頭結(jié)點,使得程序不符合要求。

2.在寫程序時忽略了一些變量參數(shù)的標(biāo)識“&”,使調(diào)試程序費時不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識。

3.本程序模塊劃分比較簡單且容易看懂，但頭指針賦空不太合理。

4.本實習(xí)作業(yè)采用數(shù)據(jù)抽象的設(shè)計方法，將程序劃分為3個層次，使得設(shè)計時思路清晰，實現(xiàn)調(diào)試順利

五、用戶手冊

1.本程序運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為約瑟夫環(huán).exe。

2． 進(jìn)入演示程序后出現(xiàn)提示信息：

“請輸入人數(shù)n”

輸入后，出現(xiàn)提示信息：

“請輸入m”

輸入后，出現(xiàn)提示信息：

“請依次輸入每個人的密碼”

輸入后，顯示相應(yīng)的結(jié)果。

第三篇：約瑟夫環(huán)課程設(shè)計實驗報告

《數(shù)據(jù)結(jié)構(gòu)》

課程設(shè)計報告

課程名稱：

課程設(shè)計題目：姓名： 院系： 專業(yè)： 年級： 學(xué)號： 指導(dǎo)教師： 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

joseph環(huán)

計算機(jī)學(xué)院

2011年12月18日

目 錄 課程設(shè)計的目的………………………………………………………………2 2 需求分析………………………………………………………………………2 3 課程設(shè)計報告內(nèi)容……………………………………………………………3

1、概要設(shè)計……………………………………………………………………3

2、詳細(xì)設(shè)計……………………………………………………………………3

3、調(diào)試分析……………………………………………………………………x

4、用戶手冊……………………………………………………………………x

5、測試結(jié)果……………………………………………………………………6

6、程序清單……………………………………………………………………7 4 小結(jié) …………………………………………………………………………10

1、課程設(shè)計的目的

（1）熟練使用C++編寫程序，解決實際問題；

（2）了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；（3）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；（4）提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；

2、需求分析

1、問題描述：

編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。

2、要求：

利用不帶表頭結(jié)點的單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。

3、測試數(shù)據(jù)：

m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？

輸出形式：建立一個輸出函數(shù)，將正確的輸出序列

3、課程設(shè)計報告內(nèi)容

概要設(shè)計：

在理解了題目后，我先想到的是我們所學(xué)的單鏈表，利用單鏈表先建立循環(huán)鏈表進(jìn)行存貯，建立完循環(huán)鏈表后，我將所要編寫的函數(shù)分為了兩塊，一塊是經(jīng)過學(xué)過的單鏈表改編的循環(huán)鏈表的基本操作函數(shù)，還有一塊是運行約瑟夫環(huán)的函數(shù)。

詳細(xì)設(shè)計：

我先建立一個結(jié)構(gòu)體，與單鏈表一樣，只是多了一個存密碼的code域

struct LinkNode {

int data;

//順序

int code;

//密碼

LinkNode *next;

};建立一個類LinkList ,包含的函數(shù)：

LinkList();

//構(gòu)造函數(shù)

void Creat(const int);

//創(chuàng)建循環(huán)鏈表

int Delete(LinkNode*);

//刪除報到數(shù)的結(jié)點

int Joseph(int);

// 約瑟夫環(huán) 私有成員是

LinkNode* head;

//指向第一個結(jié)點的指針 LinkNode* elem;

// 同上

int len;

//長度

我定義了一個elem指針是為了約瑟夫環(huán)里運行方便，elem只在約瑟夫環(huán)這個函數(shù)里用到，其他函數(shù)沒有特別大的用處。

構(gòu)造函數(shù)與書上的沒什么大差別，創(chuàng)建循環(huán)鏈表時，要考慮幾個問題，一個是題目要求是不帶頭結(jié)點，所以head指針直接指向了第一個結(jié)點，我在創(chuàng)建鏈表時把第一個結(jié)點初始化data為1，表明這個結(jié)點是第一個結(jié)點。具體如下：

void LinkList::Creat(const int number)

//number為結(jié)點個數(shù)，也就是參與的人數(shù) {

if(number==1)

//只有一個人的情況 {

head=elem=new LinkNode;

head->data=1;

cout<<“請輸入密碼:”<

cin>>head->code;

head->next=head;}

else {

head=elem=new LinkNode;

head->data=1;

cout<<“請依次輸入各個密碼:”<

cin>>head->code;LinkNode*q=head;

q=head;

for(int i=1;i

//將每個結(jié)點鏈接上，在鏈接時填入密碼 {

LinkNode*p=new LinkNode;

p->data=i+1;

cin>>p->code;

q->next=p;

q=p;}

q->next=head;

//構(gòu)成循環(huán)鏈表 }

len=number;}

在構(gòu)建約瑟夫環(huán)的執(zhí)行函數(shù)時，我首先考慮了遞歸調(diào)用的函數(shù)，原本的這個程序的所有的都定為elemtype類型的，雖然編譯沒出錯，但是在連接時發(fā)生了錯誤，在老師的指導(dǎo)下改成了具體的int型。int LinkList::Joseph(int m){

if(len>1){

LinkNode *q;if(m==1)

//在初始報數(shù)為1的情況下

{ q=elem;int a=q->code;

//將選中的結(jié)點的密碼記錄在a中 elem=elem->next;cout<

//用已經(jīng)刪除的結(jié)點的存的密碼作為下一次循環(huán)的報數(shù)值 } else

//一般情況下 { for(int i=1;i

elem=elem->next;//找到需要出列的結(jié)點

q=elem;elem=elem->next;

//此處的elem指針指向要刪除的結(jié)點的下一個結(jié)點，下

次遞歸調(diào)用時從這里開始向下循環(huán)報數(shù)

int a=q->code;

cout<

//在只有一個結(jié)點的情況下 cout<data;}

最后還有一個Delete函數(shù)，在刪除結(jié)點的時候要考慮幾個特殊情況，頭尾結(jié)點。刪除第一個結(jié)點時，需要將head指針下移，尾結(jié)點的next也要指向第二個結(jié)點；刪除尾結(jié)點時，要將尾結(jié)點前的結(jié)點與第一個結(jié)點相連。在設(shè)計這個函數(shù)時，我只考慮了當(dāng)len大于1的情況，在只剩下一個結(jié)點時，不必要刪除，直接輸出data的值即可（在約瑟夫函數(shù)中有寫）。具體函數(shù)如下： int LinkList::Delete(LinkNode *a)

{

if(len>1)//只考慮長度大于1的情況

{

if(head==a){

int out=head->data;LinkNode* q=head;

while(q->next!=head){

q=q->next;} q->next=head->next;head=head->next;delete a;len--;

//用len記錄刪除后的循環(huán)鏈表的長度 return out;}

else

{ LinkNode* q=head;int out=a->data;

while(q->next!=a){

q=q->next;} if(a->next=head).//刪除的是尾結(jié)點時（不知道為什么我寫程序里總是編譯出現(xiàn)錯誤）

{

q->next=head;

//重新鏈接

delete a;

len--;

return out;} else

{

q->next=a->next;

delete a;

len--;

return out;

} }

} }

5、測試結(jié)果： 程序清單：

#include struct LinkNode {

int data;

int code;

LinkNode *next;};

class LinkList { public:

LinkList();

void Creat(const int);

//~LinkList();

int Delete(LinkNode*);

int Joseph(int);

private:

LinkNode* head;

LinkNode* elem;

int len;

};

LinkList::LinkList()

{

head=elem=NULL;

len=0;}

void LinkList::Creat(const int number)

{

if(number==1){

head=elem=new LinkNode;

head->data=1;

cout<<“請輸入密碼:”<

cin>>head->code;

head->next=head;}

else {

head=elem=new LinkNode;

head->data=1;

cout<<“請依次輸入各個密碼:”<

cin>>head->code;

LinkNode*q=head;

q=head;

for(int i=1;i

{

LinkNode*p=new LinkNode;

p->data=i+1;

cin>>p->code;

q->next=p;

q=p;

}

q->next=head;}

len=number;}

int LinkList::Delete(LinkNode *a)

{

if(len>1)

{

if(head==a)

{

int out=head->data;

LinkNode* q=head;

while(q->next!=head)

{

q=q->next;

}

q->next=head->next;

head=head->next;

delete a;

len--;

return out;

}

else

{

LinkNode* q=head;

int out=a->data;

while(q->next!=a)

{

q=q->next;

}

q->next=a->next;

delete a;

len--;

return out;

}

} }

int LinkList::Joseph(int m){

if(len>1){

LinkNode *q;

if(m==1)

{

q=elem;

int a=q->code;

elem=elem->next;

cout<

Joseph(a);

}

else

{

for(int i=1;i

elem=elem->next;

q=elem;

elem=elem->next;

int a=q->code;

cout<

Joseph(a);

} } else

cout<data;}

int main(){

int num,code;

cout<<“請輸入人數(shù): ”;

cin>>num;

LinkList L;

L.Creat(num);

cout<<“請輸入第一個上限數(shù):

”;

cin>>code;

cout<<“出列順序:”<

L.Joseph(code);

return 0;}

4、小結(jié)

一、這次課程設(shè)計的心得體會通過實踐我的收獲如下：

一開始接觸數(shù)據(jù)結(jié)構(gòu)課程設(shè)計真的挺難的，好多都不會，不是邏輯方面的問題，而是不具備動手能力，腦子里總有一團(tuán)火，比如對于這個題目，一開始有很多的想法，想到了從邏輯上怎么實現(xiàn)他，要編寫哪些程序，但是一到需要編寫了就開始為難了，可以說是幾乎不知道從哪里入手，參考了書本里的程序，仿照他的結(jié)構(gòu)一步一步做下來，現(xiàn)在對于單鏈表的各種操作已經(jīng)算是比較熟練了，讓我知道光有理論知識還遠(yuǎn)遠(yuǎn)不夠，需要多動手，寫的多了自然就能手到擒來。

二、根據(jù)我在實習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點：

1、認(rèn)真上好專業(yè)實驗課，多在實踐中鍛煉自己。

2、寫程序的過程中要考慮周到，嚴(yán)密。

3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。

4、認(rèn)真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。

5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。

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

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

散列表的應(yīng)用:插隊買票

專業(yè) 計算機(jī)科學(xué)與技術(shù)（網(wǎng)絡(luò)技術(shù)）

金玲 計算機(jī)131 1310704114 張靜林 2015年1月23日 學(xué)生姓名 班學(xué)級 號

指導(dǎo)教師 完成日期

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

1.1 課程設(shè)計目的

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

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

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

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

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

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

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

3.1 系統(tǒng)流程圖 系統(tǒng)詳細(xì)設(shè)計

本題目主要解決兩個問題：一是怎么存放和查找大量數(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;

/*標(biāo)志位，該單元是否被占用*/ };圖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用平方探測法解決沖突

第二個問題是關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊列來模擬。由于有插隊現(xiàn)象的存在，不能單純的用一個數(shù)組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標(biāo)記來表示當(dāng)前元素的后繼元素，最后一個單元的后繼元素是第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ù)“先進(jìn)先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列重的第一個。程序結(jié)構(gòu)如圖4.5所示。

While(讀測試文件){

if(輸入”ENQUEUE”)

{

讀入名字；

插入散列表；

插入隊列；

}

else if(輸入”DEQUEUE”)

{

刪除隊列第一個名字；

將該名字輸出到文件；

}

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

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

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

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

參考文獻(xiàn)

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

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

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

/*散列值*/ long int Index;

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

int hashedx=0;

/*標(biāo)記元素是否已經(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;/*如果當(dāng)前單元被占用：單元內(nèi)的元素與當(dāng)前操作的名字不同，使用平方探測法解決沖突；與當(dāng)前操作的名字相同，則直接返回在散列中的位置*/ 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;

/*當(dāng)前測試用例序號*/ 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))/*輸入當(dāng)前測試用例的朋友組數(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;

/*初始化散列表，標(biāo)記位置0*/

for(i=0;i

/*對每一組朋友*/

{

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

/*當(dāng)前組里的人數(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]='