數據結構

實踐教程

目錄

第一部分基礎篇

第一章線性表

1.1學生成績管理

1.1.1項目簡介

1.1.2設計思路

1.1.3數據結構

1.1.4程序清單

1.1.5運行結果

1.2考試報名管理

1.2.1項目簡介

1.2.2設計思路

1.2.3數據結構

1.2.4程序清單

1.2.5運行結果

1.3約瑟夫生者死者游戲

1.3.1項目簡介

1.3.2設計思路

1.3.3數據結構

1.3.4程序清單

1.3.5運行結果

1.4約瑟夫雙向生死游戲

1.4.1項目簡介

1.4.2設計思路

1.4.3數據結構

1.4.4程序清單

1.4.5運行結果

第二章棧和隊列

2.1迷宮旅行游戲

2.1.1項目簡介

2.1.2知識要點

2.1.3設計思路

2.1.4程序清單

2.1.5運行結果

2.2八皇后問題

2.1.1項目簡介

2.1.2知識要點

2.1.3設計思路

2.1.4程序清單

2.1.5運行結果

2.3停車場的停車管理

2.1.1項目簡介

2.1.2知識要點

2.1.3設計思路

2.1.4程序清單

2.1.5運行結果

第三章串、數組和廣義表

3.1單詞檢索統(tǒng)計程序

3.1.1項目簡介

3.1.2設計思路

3.1.3數據結構

3.1.4程序清單

3.1.5運行結果

3.2Internet網絡通路管理

3.2.1項目簡介

3.2.2設計思路

3.2.3數據結構

3.2.4程序清單

3.2.5運行結果

第四章樹和二叉樹

4.1家譜管理

4.1.1項目簡介

4.1.2設計思路

4.1.3數據結構

4.1.4程序清單

4.1.5運行結果

4.2表達式求值問題

4.2.1項目簡介

4.2.2設計思路

4.2.3數據結構

4.2.4程序清單

4.2.5運行結果

4.4圖像壓縮編碼優(yōu)化

4.4.1項目簡介

4.4.2設計思路

4.4.3數據結構

4.4.4程序清單

4.4.5運行結果

第五章圖

5.1公交路線管理

5.1.1項目簡介

5.1.2設計思路

5.1.3數據結構

5.1.4程序清單

5.1.5運行結果

5.2導航最短路徑查詢

5.2.1項目簡介

5.2.2設計思路

5.2.3數據結構

5.2.4程序清單

5.2.5運行結果

5.4電網建設造價計算

5.4.1項目簡介

5.4.2設計思路

5.4.3數據結構

5.4.4程序清單

5.4.5運行結果

5.4軟件工程進度規(guī)劃

5.4.1項目簡介

5.4.2設計思路

5.4.3數據結構

5.4.4程序清單

5.4.5運行結果

第二部分綜合篇

1.1景區(qū)旅游信息管理系統(tǒng)

1.1.1項目需求

1.1.2知識要點

1.1.3設計流程

1.1.4程序清單

1.1.5運行測試

第一部分基礎篇

第一章線性表

線性表是數據結構中最簡單、最常用的一種線性結構，也是學習數據結構全部內容的基

礎，其掌握的好壞直接影響著后繼知識的學習。本章通過四個模擬項目來學習線性表的順序

和鏈式存儲結構，首先通過使用有關數組的操作實現(xiàn)學生成績管理，其次通過使用有關線性

鏈表的操作實現(xiàn)考試報名管理，然后通過使用循環(huán)鏈表的操作實現(xiàn)約瑟夫生者死者游戲。

1.1學生成績管理

1.1.1項目簡介

學生成績管理是學校教務部門日常工作的重要組成部分，其處理信息量很大。本項目是

對學生成績管理的簡單模擬，用菜單選擇方式完成下列功能：輸入學生數據：輸出學生數據；

學生數據查詢：添加學生數據；修改學生數據；刪除學生數據。

1.1.2設計思路

本項目的實質是完成對學生成績信息的建立、查找、插入、修改、刪除等功能，可以首

先定義項目的數據結構，然后將每個功能寫成一個函數來完成對數據的操作，最后完成主函

數以驗證各個函數功能并得出運行結果。

1.1.3數據結構

本項目的數據是一組學生的成績信息，每條學生的成績信息由學號、姓名和成績組成，

這組學生的成績信息具有相同特性，屬于同一數據對象，相鄰數據元素之間存在序偶關系。

由此可以看出，這些數據具有線性表中數據元素的性質，所以該系統(tǒng)的數據采用線性表來存

儲。

順序表是線性表的順序存儲結構，是指用一組連續(xù)的內存單元依次存放線性表的數據元

素。在順序存儲結構下，邏輯關系相鄰的兩個元素在物理位置上也相鄰，這是順序表的特點。

本項目可以采用順序表的線性表順序存儲結構。

若?個數據元素僅占一個存儲單元，則其存儲方式參見圖1-1。

2

從圖1-1中可見，第i個數據元素的地址為

Loc(ai)=loc(al)+(i-l)

假設線性表中每個元素占用k個存儲單元，那么在順序表中，線性表的第i個元素的存

儲位置與第1個元素的存儲位置的關系是

Loc(ai)=loc(al)+(i-l)*k

這里Loc(ai)是第i個元素的存儲位置，loc(al)是第1個元素的存儲位置，也稱為線性表

的基址。顯然，順序表便于進行隨機訪問，故線性表的順序存儲結構是一種隨機存儲結構。

順序表適宜于做查找這樣的靜態(tài)操作；順序存儲的優(yōu)點是存儲密度大，存儲空間利用率

高。缺點是插入或刪除元素時不方便。

由于C語言的數組類型也有隨機存儲的特點，-維數組的機內表示就是順序結構。因此,

可用C語言的一維數組實現(xiàn)線性表的順序存儲。數組實現(xiàn)線性表的順序存儲的優(yōu)點是可以隨

機存取表中任一元素0(1),存儲空間使用緊湊；缺點是在插入，刪除某一元素時，需要移動

大量元素0(n),預先分配空間需按最大空間分配，利用不充分，表容量難以擴充。

用結構體類型定義每個學生數據，故該數組中的每個數據的結構可描述為：

typedefstructSTU

{charstuno[10];〃學號

charname[10];〃姓名

floatscore;//成績

}ElemType;

1.1.4程序清單

#include<iostream.h>

#include<iomanip.h>

#include<malloc.h>

#include<string.h>

#defineMaxListSize20

#defineEQUAL1

typedefstructSTU{

charstuno[10];

charname[10];

floatscore;

3

}ElemType;

classList

{private:

〃線性表的數組表示

ElemTypeelem[MaxListSize];

intlength;

intMaxSize;

public:

〃輸入學生數據

voidinit(List**L,intms);

//刪除所有學生數據

voidDestroyList(List&L){free(&L);}

〃將順序表置為空表

voidClearList(){length=0;}

〃判斷順序表是否為空表

boolListEmptyO

{returnlength==O;}

〃判斷順序表是否為滿

boolListFull()

{returnlength==MaxSize;}

〃刪除某個學生數據

boolListDelete(int,ElemType&e);

〃遍歷順序表

voidListTraverse();

//返回順序表的長度

intListLength();

〃學生數據查詢

voidGetElem(int,ElemType*);

//修改學生數據

boolUpdateList(ElemType&e,ElemType);

〃添加學生數據

boolListlnsert(int,ElemType&);

〃對學生數據按升序或降序輸出

voidprintlist(int);

4

voidList::init(List**L,intms)

{*L=(List*)malloc(sizeof(List));

(*L)->length=0;

(*L)->MaxSize=ms;

}

intList::ListLength()

{returnlength;}

boolList::ListDelete(intmark,ElemTypc&e)

{inti,j;

ififListEmptyO)returnfalse;

if(mark>0){//刪除表頭元素

e=elem[0];

for(i=l;i<length;i++)

elem[i-1]=elem[i];}

else〃刪除表尾元素

if(mark<0)e=elem[length-l];

else{〃刪除值為e的元素

fbr(i=O;i<length;i++)

if(strcmp(elem[i].name,)==O)break;

if(i>=lcngth)returnfalse;

elsee=elem[i];

for(j=i+l；j<length;j++)

elem[j-1]=elem[j];}

length—;

returntrue;

}

voidList::ListTraverse()

{fbr(inti=O;i<length;i++)

{cout?setw(8)?elem[i].name;

cout?setw(10)?elem[i].stuno;

cout?setw(9)?elem[i].age;

cout?setw(8)?elem[i].score?endl;}

5

voidList::GetElem(inti,ElemType*e)

{*e=elem[i];}

boolList::EqualList(ElemType*el,ElemType*e2)

{if(strcmp(el->name,e2->name))

returnfalse;

if(strcmp(el->stuno,e2->stuno))

returnfalse;

if(el->age!=e2->age)

returnfalse;

if(e1->score!=e2->score)

returnfalse;

returntrue;

}

boolList::Less_EqualList(ElemType*el,ElemType*e2)

{if(strcmp(e1->namc,e2->name)<=0)returntrue;

elsereturnfalse;

}

boolList::LocateElcm(ElemTypee,inttype)

{inti;

switch(type)

{caseEQUAL:

fbr(i=O;i<length;i++)

if(EqualList(&elem[i],&e))

returntrue;

break;

default:break;}

returnfalse;

}

〃修改學生數據

boolList::UpdateList(ElemType&e,ElemTypeel)

{fbr(inti=O;i<length;i++)

if(strcmp(elem[i].name,)=O){

elem[i]=el;retumtrue;}

returnfalse;

6

boolList::ListInsert(inti,EIemType&e)

{ElemType*p,*q;

if(i<l||i>length+l)returnfalse;

q=&elem[i-l];

for(p=&elem[length-1];p>=q;—p)

*(p+l)=*p;

*q=e;

++length;

returntrue;

}

//對學生成績按升序或降序輸出

voidList::printlist(intmark)

{int*b=newint[length];

inti,k;

cout?"姓名學號成績\n”；

if(mark!=0){

fbr(i=O;i<length;i++)b[i]=i;

for(i=0;i<length;i++){k=i;

for(intj=i+1;j<length;j-H-){

if(mark==l&&elem[b[j]].score<elem[b[k]].score)kq；

if(mark==-l&&elem[b[k]].score<elem[b|j]].score)k=j;}

if(k!=i){intx=b[i];b[i]=b[k];b[k]=x;}}

fbr(inti=O;i<length;i++)

{cout?setw(8)?elem[b[i]].name;

cout?setw(10)?elem[b[i]].stuno;

cout?setw(9)?elem[b[i]].age;

cout?setw(8)?elem[b[i]].score?endl;}}

else{

fbr(i=O;i<length;i-H-)

{cout?setw(8)?elcm[i].name;

cout?setw(10)?elem[i].stuno;

cout?setw(9)?elem[i].age;

cout?setw(8)?elem[i].score?endl;}}

7

voidmain()

{cout?"linelist1m.cpp運行結果:\n”;

ElemTypee,el,e2,e3,e4,e5,e6;

List*La,*Lb,*Lc;

intk;

coutw”首先調用插入函數.\nn;

La->init(&La,4);

strcpy(e,nstu1")；

strcpy(e1.stuno/1100001");

el.age=22;

el.score=88;

La->ListInsert(1,e1);

strcpy(,"stu2H);

strcpy(e2.stuno,nl00002”)；

e2.age=21;

e2.score=79;

La->ListInsert(2,e2);

strcpy(e3.name,"stu3”)；

strcpy(e3.stuno,nl00003M);

e3.age=19;

e3.score=87;

La->ListInsert(3,e3);

La->printlist(O);

coutw”表La:M?La->ListLcngth()?endl;

cin.get();

Lb->init(&Lb,4);

strcpy(,"zmofunM);

strcpy(e4.stuno,nl00001”)；

e4.age=20;

e4.score=94;

Lb->ListInsert(1,e4);

strcpy(,"bobjinM);

strcpy(e5.stuno/,100002n);

8

e5.age=23;

e5.score=69;

Lb->ListInsert(2,e5);

strcpy(,"stu1”)；

strcpy(e6.stuno,n100001");

e6.age=22;

e6.score=88;

Lb->ListInsert(3,e6);

Lb->printlist(0);

cout?"表Lb[￡:n?Lb->ListLength()?endl;

cin.getQ;

k=Lc->ListDelete(-l,e6);

if(k=O)cout?”刪除失敗!\n”；

elsecoutw”刪除成功!\n”;

coutw”輸出表Lc:\n"；

Lc->printlist(O);

cin.get();

coutw”按成績升序輸出表Lc\n";

Lc->printlist(1);cin.get();

coutvv”按成績降序輸出表Lc\n";

Lc->printlist(-1);cin.get();

}

1.1.5運行結果

首先建立學生信息管理，輸出結果為：

姓名學號成績

Stul10000180

Stu210000291

Stu310000356

其次查詢學號為100002的學生的成績，輸出結果為:

91

再次調用插入函數，插入Stu4成功！輸入結果為：

姓名學號成績

9

Stul10000180

Stu210000291

Stu310000356

Stu410000475

最后刪除Stu2成果!輸出結果為

姓名學號成績

Stul10000180

Stu310000356

Stu410000475

查詢不及格的學生，輸出結果為:

Stu310000356

1.2考試報名管理

1.2.1項目簡介

考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)，給教務管理部門增加了很大的工作量,

報名數據手工錄入既費時又會不可避免地出現(xiàn)錯誤，同時也給不少學生以可乘之機。本項目

是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信

息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。

1.2.2設計思路

本項目的實質是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定

義項目的數據結構，然后將每個功能寫成一個函數來完成對數據的操作，最后完成主函數以

驗證各個函數功能并得出運行結果。

1.2.3數據結構

本項目的數據是一組考生信息，每條考生信息由準考證號、姓名、性別、年齡、報考類

別等信息組成，這組考生信息具有相同特性，屬于同一數據對象，相鄰數據元素之間存在序

偶關系。由此可以看出，這些數據也具有線性表中數據元素的性質，所以該系統(tǒng)的數據可以

采用線性表來存儲。

從上一節(jié)的例子中可見，線性表的順序存儲結構的特點是邏輯關系相鄰的兩個元素在物

理位置上也相鄰，因此可以隨機存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公

10

式來表示。然而，從另一個方面來看，這個特點也鑄成了這種存儲結構的弱點：在做插入或

刪除操作時，需要移動大量元素。為克服這一缺點，我們引入另一種存儲形式一一鏈式存儲。

鏈式存儲是線性表的另種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰,

因此它沒有順序存儲結構的弱點，但同時也失去了順序表可隨機存取的特點。

鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間

利用率低。事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。

順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性

表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其

主要操作是插入、刪除操作，則采用鏈表。

本項目對考生數據主要進行插入、刪除、修改等操作，所以采用鏈式存儲結構比較適合。

用結構體類型定義每個考生信息，故該單鏈表中的每個結點的結構可描述為：

typedefstructexaminee

{charexamiio[10];〃準考證號

charname[10];〃姓名

charsex;

floatage;

charexamtype[5];〃成績

}ElemType;

1.2.4程序清單

〃單鏈表的類定義linklist3.h

#ifndeflinklist3H

#definelinklist3H

#defineLEN30

〃定義ElemType為int

typedefintElemType;

〃單鏈表中結點的類型

typedefstructLNode{

ElemTypedata;〃值域

LNode*next;〃指針域

}LNode;

classLinkList{

LNode*head;

public:

11

〃構造函數

LinkList();

〃析構函數

?LinkList();

〃清空單鏈表

voidClearList();

〃求單鏈表長度

intListSize();

〃檢查單鏈表是否為空

boolListEmpty();

〃返回單鏈表中指定序號的結點值

ElemTypeGetElem(intpos);

〃遍歷單鏈表

voidTraverseList(void出ElemType&));

〃從單鏈表中查找元素

boolFindList(ElemType&item);

〃更新單鏈表中的給定元素

boolUpdateList(constElemType&item,ElemTypee);

〃向單鏈表插入元素,mark=0插在表首,否則插在表尾

voidInsertList(ElemTypeitem,intmark);

〃從單鏈表中刪除元素，mark為要刪除的第幾個元素

boolDeleteList(ElemType&item,intmark);

〃對單鏈表進行有序排列mark>0升序，否則降序

voidpailie(intmark=l);

//對單鏈表進行有序輸出,mark=0不排序,mark>0升序,mark〈0降序

voidOrderOutputList(intmark=0);

}；

#endif

//linklist3.cpp

#includeHlinklist3.hM

LinkList::LinkList()〃構造函數

{hcad=newLNode;

head->next=NULL;

12

LinkList::?LinkList()〃析構函數

{LNode*p=head->next,*q;

while(p)

{q=p->next;

free(p);

p=q;

)

}

voidLinkList::ClearList()〃清空單鏈表

{LNode*p=hcad->next,*q;

while(p)

{q=p->next;

free(p);

p=q;

}

head->next=NULL;

}

intLinkList::ListSize()〃求單鏈表長度

{LNode*p=head->next;

inti=0;

while(p)

{i++；

p=p->next;}

returni;

}

boolLinkList::ListEmpty()〃檢查單鏈表是否為空

{returnListSize()=O;}

〃返回單鏈表中指定序號的結點值

ElemTypeLinkList::GetElem(intpos)

{LNode*p=head->next;

inti=l;

while(p)

{if(i4-+==pos)retump->data;

p=p->next;

13

returnhead->data;

voidLinkList::TraverseList(voidf(ElemType&))〃遍歷單鏈表

{LNode*p=head->next;

while(p)

{f(p->data);

p=p->next;}

}

boolLinkList::FindList(ElemType&item)//從單鏈表中查找元素

{LNode*p=hcad->next;

while(p)

{if(p->data==item)retum1;

p=p->next;}

return0;

}

〃更新單鏈表中的給定元素

boolLinkList::UpdateList(constElemType&item,ElemTypee)

{LNode*p=head->next;

boolflag=0;

while(p)

{if{p->data==item)

{p->data=e;

flag=l;}

p=p->next;}

returnflag;

}

〃向單鏈表插入元素

voidLinkList::InsertList(ElcmTypeitem,intmark)

{LNode*q=newLNode;

q->data=item;

ifl(mark==0)

{q->next=head->next;

head->next=q;

return;}

LNode*p=head;

14

while(p>>next)

{p=p->next;}

q->next=NULL;

p->next=q;

}

〃從單鏈表中刪除元素

boolLinkList::DeleteList(ElemType&itein,intmark)

{if(ListEmpty()||mark<l||mark>ListSize())return0;

LNode*p=head,*q;

for(inti=0;i<mark-l;i++)

p=p->next;

item=p->next->data;

q=p->next->next;

free(p->next);

p->next=q;

return1;

}

〃對單鏈表進行有序排列mark>0升序，否則降序

voidLinkList::pailie(intmark)

{ElemTypea[LEN+l];

LNode*p=head->next;

intk;

fbr(k=l;p!=NULL;k++,p=p->next)

a[k]=p->data;

k-;

fbr(inti=l;i<k;i++)

for(intj=l;j<=k-i;j++)

{intt;

if(mark>0&&a[j]>a[j+l]||mark<0&&a[j]<a[j+l])

{t=a[j+l]；

a[j+l]=a[j]；

p=hcad->next;

for(intj=1;j<=k;j-H-,p=:p->next)

p->data=a|j];

15

〃對單鏈表進行有序輸出

voidLinkList::OrderOutputList(intmark)

{ElemTypca[LEN+l];

LNode*p=head->next;

intk;

for(k=l;p!=NULL;k-H-,p=p->next)

a[k]=p->data;

k-；

for(inti=l;i<k;i++)

for(intj=l;j<=k-i;j++)

{intt;

iffmark>O&&a[j]>a[j+1]||mark<O&&a[j]<a[j+1])

{t=a[j+l];

a[j+l]=a[j]；

fdr(intj=1;j<=k;j+4-)

cout?a[j]?"”；

)

#include<iostream.h>

#include<iomanip.h>

#include<stdlib.h>

//#include<stdio.h>

#includeHlinklist3.cppn

voidff(int&a)〃用于遍歷的函數

{cout?a?"”;}

voidmain()

{cout?n\nlinklist3m.cpp運行結果:\n”；

intinit_size,seed,xu;

coutw”首先請構造單鏈表list”；

cout?"\n初始化長度(1--30):";

cin?init_size;

seed=150;

coutw”是否排序:(=0不排序,=1升序,=-1降序):"；

16

cin?xu;

cout?"\n單鏈表list構造成功!”《”\n它是:“；

list.TraverseList(fl);

cout?”\n它為空嗎?(1:是;0:不是):“wlist.ListEmpty();

cout?"\n長度為:“vvlist.ListSize();

inti;

cout?"\n請輸入你想得到第幾個元素的值(l」vvinit_sizevv”):“；

cin?i;

coutw"單鏈表list中第“wivv”的值是“vvlist.GetElem⑴；

intit;

cout?"\n請輸入你想刪除第幾個元素的值(l」vvinit_sizevv”):“；

cin?i;

list.DcleteList(it,i)；

cout?"\n單鏈表list刪除第"vvivv”個元素”vv叫“vvitvv叫“vv”后變?yōu)?";

list.TraverseList(ff);//對單鏈表list每個數進行遍歷.

intnews,olds;

cout?"\n請輸入要被修改的元素:";cin?olds;

coutvv”請輸入修改后要變成的元素:";cin?news;

list.UpdatcList(olds,news);

cout?"\n修改后單鏈表list變?yōu)?“；

list.TraverseList(ff);

cout?"\n下面請構造單鏈表list2n;

cout?"\n請輸入單鏈表list2初始化長度(1-30):";

cin?init_size;

seed=120;

coutvv”請選擇是否排序：(=0不排序,=1升序,=-1降序):"；

cin?xu;

cout?"\n按回車鍵結束…”;

cin.get();cin.get();}

1.2.5運行結果

17

1.3約瑟夫生者死者游戲

1.3.1項目簡介

約瑟夫生者死者游戲的大意是：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，

危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無

奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數，數到第

9人，便把他投入大海中，然后從他的下一個人數起，數到第9人，再將他投入大海，如此

循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。

1.3.2設計思路

本游戲的數學建模如下：假設n個旅客排成一個環(huán)形，依次順序編號1,2,n。從

某個指定的第1號開始，沿環(huán)計數，每數到第m個人就讓其出列，且從下一個人開始重新計

數，繼續(xù)進行下去。這個過程一直進行到剩下k個旅客為止。

本游戲的要求用戶輸入的內容包括：

1.旅客的個數，也就是n的值；

2.離開旅客的間隔數，也就是m的值；

3.所有旅客的序號作為一組數據要求存放在某種數據結構中。

本游戲要求輸出的內容是包括

1.離開旅客的序號；

2.剩余旅客的序號；

所以，根據上面的模型分析及輸入輸出參數分析，可以定義一種數據結構后進行算法實

現(xiàn)。

1.3.3數據結構

為了解決這一問題，可以用長度為30的數組作為線性存儲結構，并把該數組看成是一個

首尾相接的環(huán)形結構，那么每投入大海?個乘客，就要在該數組的相應位置做一個刪除標記,

該單元以后就不再作為計數單元。這樣做不僅算法較為復雜，而且效率低，還要移動大量的

元素。用單循環(huán)鏈表解決這一問題，實現(xiàn)的方法相對要簡單得多。首先要定義鏈表結點，單

循環(huán)鏈表的結點結構與一般的結點結構完全相同，只是數據域用一個整數來表示位置：然后

將它們組成具有30個結點的單循環(huán)鏈表。接下來從位置為1的結點開始數，數到第8個結點,

就將下一個結點從循環(huán)鏈表中刪去，然后再從刪去結點的下一個結點開始數起，數到第8個

結點，再將其下一個結點刪去，如此進行下去，直到剩下15個結點為止。

18

為了不失一般性，將30改為一個任意輸入的正整數n,而報數上限(原為9)也為一個

任選的正整數k。這樣該算法描述如下：

(1)創(chuàng)建含有n個結點的單循環(huán)鏈表；

(2)生著與死者的選擇：

p指向鏈表的第一個結點，初始i置為1;

while(i<=n/2)〃刪除一半的結點

(從p指向的結點沿鏈前進k-1步；

刪除第k個結點(q所指向的結點)；

p指向q的下一個結點；

輸出其位置q->data;

i自增1;

}

(3)輸出所有生者的位置。

1.3.4程序清單

LinkListlnitRing(intn,LinkListR)〃尾插入法建立單循環(huán)鏈表函數

{

ListNode*p,*q;

inti;

R=q=(LinkNode*)malloc(sizeof(LinkNode));

for(i=l;i<n;i-H-){

p=(LinkNode*)malloc(sizeof(LinkNode));

q->data=i;

q->next=p;

q=p;

)

p->data=n;

p->next=R;

R=p;

returnR;

}

LinkListDeleteDeath(intn,intk,LinkListR)〃生者與死者的選擇

inti,j；

19

ListNode*p,*q;

P=R；

for(i=l;i<n/2;i++){//刪除一半結點

fbr(j=l;jvk?l;j++)〃沿鏈前進k-1步

p=p->next;

q=p->next;

p->next=q->next;

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

free(q);

}

R=p;returnR;

}

voidOutRing(intn,LinkListR){〃輸出所有生者

inti;

LinkNode*p;

p=R;

fbr(i=l;iv=n/2;i++,p=p->next){

printf('<%4d,\p->data)

)

}

有了上述算法分析和設計之后，實現(xiàn)就比較簡單了。首先要定義一個鏈表結構類型，然

后編寫一個主函數調用上面已定義好的函數即可。主函數的源程序如下：

#include<stdio.h>

#include<stdlib.h>

typedefstructnode{

intdata;

structnode*next;

}ListNode;

typedefListNode*LinkList;

voidmain(){

LinkListR;

intn,k;

LinkListInitRing(intn,LinkListR);

LinkListDeleteDcath(intn,intk,LinkListR);

voidOutRing(intn,LinkListR);

20

printf("總人數n.報數上限k=")；

scanf(64%d%d,,,&n,&k);

R=InitRing(n,R);

R=DeleteDeath(n,k,R);

OutRing(n,R);

}

1.3.5運行結果

編譯運行上述程序，提示：總人數n.報數上限k=

輸入30和9后并“回車”可得出如下結果：

9182761626719301224822523

21252829123410111314151720

1.4約瑟夫雙向生死游戲

1.4.1項目簡介

約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎上，正向計數后反向計數，然后再

正向計數。具體描述如下：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分;

因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只

得同意這種辦法，并議定30個人圍成一圈，山第一個人開始，順時針依次報數，數到第9

人，便把他投入大海中，然后從他的下一個人數起，逆時針數到第5人，將他投入大海，然

后從他逆時針的下一個人數起，順時針數到第9人，再將他投入大海，如此循環(huán)，直到剩下

15個乘客為止。問哪些位置是將被扔下大海的位置。

1.4.2設計思路

本游戲的數學建模如下：假設n個旅客排成一個環(huán)形，依次順序編號1,2,no從

某個指定的第1號開始，沿環(huán)計數，數到第m個人就讓其出列，然后從第m+1個人反向計

數到m-k+1個人，讓其出列，然后從m-k個人開始重新正向沿環(huán)計數，再數m個人后讓其

出列，然后再反向數k個人后讓其出列。這個過程一直進行到剩下q個旅客為止。

本游戲的要求用戶輸入的內容包括：

1.旅客的個數，也就是n的值；

2.正向離開旅客的間隔數，也就是m的值；

21

3.反向離開旅客的間隔數，也就是k的值；

4.所有旅客的序號作為?組數據要求存放在某種數據結構中。

本游戲要求輸出的內容是包括

1.離開旅客的序號；

2.剩余旅客的序號；

所以，根據上面的模型分析及輸入輸出參數分析，可以定義?種數據結構后進行算法實

現(xiàn)。

1.4.4數據結構

約瑟夫雙向生死游戲如果用單循環(huán)鏈表作為線性存儲結構，就只能正向計數結點，反向

計數比較困難，算法較為復雜，而且效率低。用雙向循環(huán)鏈表解決這一問題，實現(xiàn)的方法相

對要簡單得多。

為了不失一般性，將30改為一個任意輸入的正整數n,而正向報數上限(原為9)也為

一個任選的正整數m,正向報數上限(原為5)也為一個任選的正整數k,。這樣該算法描述

如下：

(1)創(chuàng)建含有n個結點的雙向循環(huán)鏈表；

(2)生著與死者的選擇：

p指向鏈表的第一個結點，初始i置為1:

while(i<=n/2)〃刪除一半的結點

｛從p指向的結點沿鏈前進m-l步；

刪除第m個結點(q所指向的結點)；

p指向q的下一個結點；

輸出其位置q->data;

i自增1;

從p指向的結點沿鏈后退k-1步；

刪除第k個結點(q所指向的結點)；

p指向q的上一個結點；

輸出其位置q->data;

i自增1;

)

(3)輸出所有生者的位置。

22

1.4.4程序清單

〃雙向循環(huán)鏈表的類定義dcirlinkl.h

typedefintElemType;

〃雙向鏈表結點的類型定義

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;〃左指針

structDuLNode*next;〃右指針

}DuLNode;

#defineLEN20

classDuLinkList

{private:

DuLNode*head;〃指向表頭的指針

DuLNode*curr;〃當前結點指針

intcount;//雙向循環(huán)鏈表的結點個數

public:

〃構造函數

DuLinkList();

〃析構函數

-DuLinkList(){deletehead;}

〃創(chuàng)建有序或無序的帶頭結點的雙向循環(huán)鏈表

DuLNode*CreateCLinkL(int,int,intmark=0);

〃清空單循環(huán)鏈表

voidClearCList();

〃求雙向循環(huán)鏈表長度

intCListSize();

//檢查雙向循環(huán)鏈表是否為空

boolCListEmpty();

〃返回指向第pos個結點的指針

DuLNode*Index(intpos);

〃返回雙向循環(huán)鏈表中指定序號的結點值

ElemTypeGetElem(intpos);

〃遍歷雙向循環(huán)鏈表

23

voidTraverseCList();

〃當前指針curr指向pos結點并返回curr

DuLNode*Reset(intpos=0);

〃當前指針curr指向下一結點并返回

DuLNode*Next();

〃當前指針curr指向上?結點并返回

DuLNode*Prior();

//判雙向循環(huán)鏈表當前指針curr=head否

boolEndOCList();

〃判雙向循環(huán)鏈表當前指針curr->ncxt是否到達表尾

boolEndCList();

〃判雙向循環(huán)鏈表當前指針curr->prior是否到達表尾

boolPEndCList();

〃刪除curr->next所指結點，并返回所刪結點的data

ElemTypeDeleteNt();

//從雙向循環(huán)鏈表中查找元素

boolFindCList(ElemType&item);

〃更新雙向循環(huán)鏈表中的給定元素

boolUpdateCList(constElemType&itcm,ElemType&e);

〃向鏈表中第pos個結點前插入域值為item的新結點

voidInsertCLfront(constElemType&item,intpos);

〃向鏈表中第pos個結點后插入域值為item的新結點

voidInsertCLafter(constElemType&item,intpos);

〃從鏈表中刪除第pos個結點并返回被刪結點的data

ElemTypeDclcteCList(intpos);

}.

〃雙向循環(huán)鏈表的實現(xiàn)dcirlinkl.cpp

#include<iostream.h>

#include<stdlib.h>

#include"dcirlinkl.hH

〃構造函數

DuLinkList::DuLinkList()

{hcad=newDuLNode;

head->prior=head;

24

head->next=head;

curr=NULL;

count=0;

)

〃創(chuàng)建有序或無序的帶頭結點的雙向循環(huán)鏈表

DuLNode*DuLinkList::CreateCLinkL(intn,intm,intmark)

{ElemTypex,a[LEN];

srand(m);

for(inti=0;i<n;i++)a[i]=rand()%100;

for(i=O;i<n-l;i++)

{intk=i;

fbr(intj=i+l;j<n;j++)

if(a[k]>aU])k=j;

if(k!=i)

{x=a[k];a[k]=a[i];a[i]=x;}}

DuLNode*p;

head=newDuLNode;

head->prior=NULL;

head->next=curr=p=newDuLNode;

curr->prior=head;

fbr(i=0;i<n;i++){

if(mark=l)p->data=a[i];〃升序

else

if(mark=-l)p->data=a[n-l-i];〃降序

elsep->data=rand()%100;〃無序

if(i<n-l){curr=curr->next=newDuLNode;

curr->prior=p;p=curr;}

count++;}

head->prior=curr;

curr->next=head;

returnhead;

}

〃清空雙向循環(huán)鏈表

voidDuLinkList::ClearCList()

{DuLNode*cp,*np;

25

cp=head->next;

while(cp!=head)

{np=cp->next;deletecp;cp=np;}

head=NULL;

}

〃求雙向循環(huán)鏈表長度

intDuLinkList::CListSize()

{DuLNode*p=head->next;

inti=0;

while(p!=head)

{i++;p=p->next;}

returni;

}

〃檢查雙向循環(huán)鏈表是否為空

boolDuLinkList::CListEmpty()

{returnhcad->next=head;}

〃返回指向第pos個結點的指針

DuLNode*DuLinkList::Index(intpos)

{if(pos<l)

{cerr?nposisoutrange!n?endl;exit(1);)

DuLNode*p=head->next;

inti=0;

while(p!=head)

{i++；

if(i==pos)break;

p=p->next;}

if(p!=head)returnp;

else{cerr?Mposisoutrange!n?endl;

returnNULL;}

}

//返回雙向循環(huán)鏈表中指定序號的結點值

ElemTypeDuLinkList::GetElem(intpos)

{ifl(pos<l)

{cerr?nposisoutrange!n?endl;exit(1);)

DuLNode*p=head->next;

26

inti=0;

while(p!=head)

{i"；

if(i=pos)break;

p=p->next;}

if(p!=head)returnp->data;

else{cerr?"posisoutrange!,,?endl;

returnpos;}

}

〃遍歷雙向循環(huán)鏈表

voidDuLinkList::TraverseCList()

{DuLNode*p=head->next;

while(p!=head)

{cout?setw(4)?p->data;

p=p->next;}

cout?endl;

}

〃當前指針curr指向pos結點并返回curr

DuLNode*DuLinkList::Reset(intpos)

{DuLNode*p=curr=head->next;

inti=-l;

while(p!=head)

{i++;

if(i=pos)break;

p=p->next;curr=curr->next;}

returncurr;

}

〃當前指針curr指向下一結點并返回

DuLNode*DuLinkList::Next()

{curr=curr->next;

returncurr;

}

〃當前指針curr指向上一結點并返回

DuLNode*DuLinkList::Prior()

{curr=curr->prior;

27

returncurr;

//判雙向循環(huán)鏈表當前指針curr=head否

boolDuLinkList::EndOCList()

{returncurr=head;}

〃判雙向循環(huán)鏈表當前指針curr->next是否到達表尾

boolDuLinkList::EndCList()

{returncurr->next=head;}

〃判雙向循環(huán)鏈表當前指針curr->prior是否到達表尾

boolDuLinkList::PEndCList()

{returncurr->prior==head;}

〃刪除curr->next所指結點，并返回所刪結點的data

ElemTypcDuLinkList::DeleteNt()

{DuLNode*p=curr->next;

curr->next=p->next;

curr->next->next->prior=p->prior;

ElemTypedata=p->data;

deletep;

count-;

returndata;

}

〃從雙向循環(huán)鏈表中查找元素

boolDuLinkList::FindCList(ElemType&item)

{DuLNode*p=head->next;

while(p!=head)

if(p->data=item)

{item=p->data;retumtrue;}

elsep=p->next;

returnfalse;

}

//更新雙向循環(huán)鏈表中的給定元素

boolDuLinkList::UpdateCList(constElemType&item,ElemType&e)

{DuLNode*p=head->next;

while(p!=head)〃查找元素

if(p->data=item)break;

28

elsep=p->next;

if{p=head)returnfalse;

else{〃更新元素

p->data=e;retumtrue;}

}

//向鏈表中第pos個結點前插入域值為item的新結點

voidDuLinkList::InsertCLfront(constElemType&item,intpos)

{DuLNode*newP=newDuLNode;

newP->data=item;

DuLNode*p=head->next;

inti=0;

while(p!=head)

{i++；

if(i=pos)break;

p=p->next;}

newP->prior=p->prior;

p->