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

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

實(shí)踐教程

目錄

第一部分基礎(chǔ)篇

第一章線性表

1.1學(xué)生成績(jī)管理

1.1.1項(xiàng)目簡(jiǎn)介

1.1.2設(shè)計(jì)思路

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

1.1.4程序清單

1.1.5運(yùn)行結(jié)果

1.2考試報(bào)名管理

1.2.1項(xiàng)目簡(jiǎn)介

1.2.2設(shè)計(jì)思路

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

1.2.4程序清單

1.2.5運(yùn)行結(jié)果

1.3約瑟夫生者死者游戲

1.3.1項(xiàng)目簡(jiǎn)介

1.3.2設(shè)計(jì)思路

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

1.3.4程序清單

1.3.5運(yùn)行結(jié)果

1.4約瑟夫雙向生死游戲

1.4.1項(xiàng)目簡(jiǎn)介

1.4.2設(shè)計(jì)思路

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

1.4.4程序清單

1.4.5運(yùn)行結(jié)果

第二章棧和隊(duì)列

2.1迷宮旅行游戲

2.1.1項(xiàng)目簡(jiǎn)介

2.1.2知識(shí)要點(diǎn)

2.1.3設(shè)計(jì)思路

2.1.4程序清單

2.1.5運(yùn)行結(jié)果

2.2八皇后問題

2.1.1項(xiàng)目簡(jiǎn)介

2.1.2知識(shí)要點(diǎn)

2.1.3設(shè)計(jì)思路

2.1.4程序清單

2.1.5運(yùn)行結(jié)果

2.3停車場(chǎng)的停車管理

2.1.1項(xiàng)目簡(jiǎn)介

2.1.2知識(shí)要點(diǎn)

2.1.3設(shè)計(jì)思路

2.1.4程序清單

2.1.5運(yùn)行結(jié)果

第三章串、數(shù)組和廣義表

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

3.1.1項(xiàng)目簡(jiǎn)介

3.1.2設(shè)計(jì)思路

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

3.1.4程序清單

3.1.5運(yùn)行結(jié)果

3.2Internet網(wǎng)絡(luò)通路管理

3.2.1項(xiàng)目簡(jiǎn)介

3.2.2設(shè)計(jì)思路

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

3.2.4程序清單

3.2.5運(yùn)行結(jié)果

第四章樹和二叉樹

4.1家譜管理

4.1.1項(xiàng)目簡(jiǎn)介

4.1.2設(shè)計(jì)思路

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

4.1.4程序清單

4.1.5運(yùn)行結(jié)果

4.2表達(dá)式求值問題

4.2.1項(xiàng)目簡(jiǎn)介

4.2.2設(shè)計(jì)思路

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

4.2.4程序清單

4.2.5運(yùn)行結(jié)果

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

4.4.1項(xiàng)目簡(jiǎn)介

4.4.2設(shè)計(jì)思路

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

4.4.4程序清單

4.4.5運(yùn)行結(jié)果

第五章圖

5.1公交路線管理

5.1.1項(xiàng)目簡(jiǎn)介

5.1.2設(shè)計(jì)思路

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

5.1.4程序清單

5.1.5運(yùn)行結(jié)果

5.2導(dǎo)航最短路徑查詢

5.2.1項(xiàng)目簡(jiǎn)介

5.2.2設(shè)計(jì)思路

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

5.2.4程序清單

5.2.5運(yùn)行結(jié)果

5.4電網(wǎng)建設(shè)造價(jià)計(jì)算

5.4.1項(xiàng)目簡(jiǎn)介

5.4.2設(shè)計(jì)思路

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

5.4.4程序清單

5.4.5運(yùn)行結(jié)果

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

5.4.1項(xiàng)目簡(jiǎn)介

5.4.2設(shè)計(jì)思路

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

5.4.4程序清單

5.4.5運(yùn)行結(jié)果

第二部分綜合篇

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

1.1.1項(xiàng)目需求

1.1.2知識(shí)要點(diǎn)

1.1.3設(shè)計(jì)流程

1.1.4程序清單

1.1.5運(yùn)行測(cè)試

第一部分基礎(chǔ)篇

第一章線性表

線性表是數(shù)據(jù)結(jié)構(gòu)中最簡(jiǎn)單、最常用的一種線性結(jié)構(gòu)，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)全部?jī)?nèi)容的基

礎(chǔ)，其掌握的好壞直接影響著后繼知識(shí)的學(xué)習(xí)。本章通過四個(gè)模擬項(xiàng)目來學(xué)習(xí)線性表的順序

和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，首先通過使用有關(guān)數(shù)組的操作實(shí)現(xiàn)學(xué)生成績(jī)管理，其次通過使用有關(guān)線性

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

1.1學(xué)生成績(jī)管理

1.1.1項(xiàng)目簡(jiǎn)介

學(xué)生成績(jī)管理是學(xué)校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項(xiàng)目是

對(duì)學(xué)生成績(jī)管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)：輸出學(xué)生數(shù)據(jù)；

學(xué)生數(shù)據(jù)查詢：添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。

1.1.2設(shè)計(jì)思路

本項(xiàng)目的實(shí)質(zhì)是完成對(duì)學(xué)生成績(jī)信息的建立、查找、插入、修改、刪除等功能，可以首

先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對(duì)數(shù)據(jù)的操作，最后完成主函

數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。

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

本項(xiàng)目的數(shù)據(jù)是一組學(xué)生的成績(jī)信息，每條學(xué)生的成績(jī)信息由學(xué)號(hào)、姓名和成績(jī)組成，

這組學(xué)生的成績(jī)信息具有相同特性，屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。

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

儲(chǔ)。

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元

素。在順序存儲(chǔ)結(jié)構(gòu)下，邏輯關(guān)系相鄰的兩個(gè)元素在物理位置上也相鄰，這是順序表的特點(diǎn)。

本項(xiàng)目可以采用順序表的線性表順序存儲(chǔ)結(jié)構(gòu)。

若?個(gè)數(shù)據(jù)元素僅占一個(gè)存儲(chǔ)單元，則其存儲(chǔ)方式參見圖1-1。

2

從圖1-1中可見，第i個(gè)數(shù)據(jù)元素的地址為

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

假設(shè)線性表中每個(gè)元素占用k個(gè)存儲(chǔ)單元，那么在順序表中，線性表的第i個(gè)元素的存

儲(chǔ)位置與第1個(gè)元素的存儲(chǔ)位置的關(guān)系是

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

這里L(fēng)oc(ai)是第i個(gè)元素的存儲(chǔ)位置，loc(al)是第1個(gè)元素的存儲(chǔ)位置，也稱為線性表

的基址。顯然，順序表便于進(jìn)行隨機(jī)訪問，故線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。

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

高。缺點(diǎn)是插入或刪除元素時(shí)不方便。

由于C語言的數(shù)組類型也有隨機(jī)存儲(chǔ)的特點(diǎn)，-維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此,

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

機(jī)存取表中任一元素0(1),存儲(chǔ)空間使用緊湊；缺點(diǎn)是在插入，刪除某一元素時(shí)，需要移動(dòng)

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

用結(jié)構(gòu)體類型定義每個(gè)學(xué)生數(shù)據(jù)，故該數(shù)組中的每個(gè)數(shù)據(jù)的結(jié)構(gòu)可描述為：

typedefstructSTU

{charstuno[10];〃學(xué)號(hào)

charname[10];〃姓名

floatscore;//成績(jī)

}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:

〃線性表的數(shù)組表示

ElemTypeelem[MaxListSize];

intlength;

intMaxSize;

public:

〃輸入學(xué)生數(shù)據(jù)

voidinit(List**L,intms);

//刪除所有學(xué)生數(shù)據(jù)

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

〃將順序表置為空表

voidClearList(){length=0;}

〃判斷順序表是否為空表

boolListEmptyO

{returnlength==O;}

〃判斷順序表是否為滿

boolListFull()

{returnlength==MaxSize;}

〃刪除某個(gè)學(xué)生數(shù)據(jù)

boolListDelete(int,ElemType&e);

〃遍歷順序表

voidListTraverse();

//返回順序表的長(zhǎng)度

intListLength();

〃學(xué)生數(shù)據(jù)查詢

voidGetElem(int,ElemType*);

//修改學(xué)生數(shù)據(jù)

boolUpdateList(ElemType&e,ElemType);

〃添加學(xué)生數(shù)據(jù)

boolListlnsert(int,ElemType&);

〃對(duì)學(xué)生數(shù)據(jù)按升序或降序輸出

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;

}

〃修改學(xué)生數(shù)據(jù)

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;

}

//對(duì)學(xué)生成績(jī)按升序或降序輸出

voidList::printlist(intmark)

{int*b=newint[length];

inti,k;

cout?"姓名學(xué)號(hào)成績(jī)\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運(yùn)行結(jié)果:\n”;

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

List*La,*Lb,*Lc;

intk;

coutw”首先調(diào)用插入函數(shù).\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”按成績(jī)升序輸出表Lc\n";

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

coutvv”按成績(jī)降序輸出表Lc\n";

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

}

1.1.5運(yùn)行結(jié)果

首先建立學(xué)生信息管理，輸出結(jié)果為：

姓名學(xué)號(hào)成績(jī)

Stul10000180

Stu210000291

Stu310000356

其次查詢學(xué)號(hào)為100002的學(xué)生的成績(jī)，輸出結(jié)果為:

91

再次調(diào)用插入函數(shù)，插入Stu4成功！輸入結(jié)果為：

姓名學(xué)號(hào)成績(jī)

9

Stul10000180

Stu210000291

Stu310000356

Stu410000475

最后刪除Stu2成果!輸出結(jié)果為

姓名學(xué)號(hào)成績(jī)

Stul10000180

Stu310000356

Stu410000475

查詢不及格的學(xué)生，輸出結(jié)果為:

Stu310000356

1.2考試報(bào)名管理

1.2.1項(xiàng)目簡(jiǎn)介

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

報(bào)名數(shù)據(jù)手工錄入既費(fèi)時(shí)又會(huì)不可避免地出現(xiàn)錯(cuò)誤，同時(shí)也給不少學(xué)生以可乘之機(jī)。本項(xiàng)目

是對(duì)考試報(bào)名管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信

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

1.2.2設(shè)計(jì)思路

本項(xiàng)目的實(shí)質(zhì)是完成對(duì)考生信息的建立、查找、插入、修改、刪除等功能，可以首先定

義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對(duì)數(shù)據(jù)的操作，最后完成主函數(shù)以

驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。

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

本項(xiàng)目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號(hào)、姓名、性別、年齡、報(bào)考類

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

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

采用線性表來存儲(chǔ)。

從上一節(jié)的例子中可見，線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的兩個(gè)元素在物

理位置上也相鄰，因此可以隨機(jī)存儲(chǔ)表中任一元素，它的存儲(chǔ)位置可用一個(gè)簡(jiǎn)單、直觀的公

10

式來表示。然而，從另一個(gè)方面來看，這個(gè)特點(diǎn)也鑄成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在做插入或

刪除操作時(shí)，需要移動(dòng)大量元素。為克服這一缺點(diǎn)，我們引入另一種存儲(chǔ)形式一一鏈?zhǔn)酱鎯?chǔ)。

鏈?zhǔn)酱鎯?chǔ)是線性表的另種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰,

因此它沒有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的特點(diǎn)。

鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間

利用率低。事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來?yè)Q取時(shí)間。

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

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

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

本項(xiàng)目對(duì)考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比較適合。

用結(jié)構(gòu)體類型定義每個(gè)考生信息，故該單鏈表中的每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)可描述為：

typedefstructexaminee

{charexamiio[10];〃準(zhǔn)考證號(hào)

charname[10];〃姓名

charsex;

floatage;

charexamtype[5];〃成績(jī)

}ElemType;

1.2.4程序清單

〃單鏈表的類定義linklist3.h

#ifndeflinklist3H

#definelinklist3H

#defineLEN30

〃定義ElemType為int

typedefintElemType;

〃單鏈表中結(jié)點(diǎn)的類型

typedefstructLNode{

ElemTypedata;〃值域

LNode*next;〃指針域

}LNode;

classLinkList{

LNode*head;

public:

11

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

LinkList();

〃析構(gòu)函數(shù)

?LinkList();

〃清空單鏈表

voidClearList();

〃求單鏈表長(zhǎng)度

intListSize();

〃檢查單鏈表是否為空

boolListEmpty();

〃返回單鏈表中指定序號(hào)的結(jié)點(diǎn)值

ElemTypeGetElem(intpos);

〃遍歷單鏈表

voidTraverseList(void出ElemType&));

〃從單鏈表中查找元素

boolFindList(ElemType&item);

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

boolUpdateList(constElemType&item,ElemTypee);

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

voidInsertList(ElemTypeitem,intmark);

〃從單鏈表中刪除元素，mark為要?jiǎng)h除的第幾個(gè)元素

boolDeleteList(ElemType&item,intmark);

〃對(duì)單鏈表進(jìn)行有序排列mark>0升序，否則降序

voidpailie(intmark=l);

//對(duì)單鏈表進(jìn)行有序輸出,mark=0不排序,mark>0升序,mark〈0降序

voidOrderOutputList(intmark=0);

}；

#endif

//linklist3.cpp

#includeHlinklist3.hM

LinkList::LinkList()〃構(gòu)造函數(shù)

{hcad=newLNode;

head->next=NULL;

12

LinkList::?LinkList()〃析構(gòu)函數(shù)

{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()〃求單鏈表長(zhǎng)度

{LNode*p=head->next;

inti=0;

while(p)

{i++；

p=p->next;}

returni;

}

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

{returnListSize()=O;}

〃返回單鏈表中指定序號(hào)的結(jié)點(diǎn)值

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;

}

〃對(duì)單鏈表進(jìn)行有序排列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

〃對(duì)單鏈表進(jìn)行有序輸出

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)〃用于遍歷的函數(shù)

{cout?a?"”;}

voidmain()

{cout?n\nlinklist3m.cpp運(yùn)行結(jié)果:\n”；

intinit_size,seed,xu;

coutw”首先請(qǐng)構(gòu)造單鏈表list”；

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

cin?init_size;

seed=150;

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

16

cin?xu;

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

list.TraverseList(fl);

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

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

inti;

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

cin?i;

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

intit;

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

cin?i;

list.DcleteList(it,i)；

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

list.TraverseList(ff);//對(duì)單鏈表list每個(gè)數(shù)進(jìn)行遍歷.

intnews,olds;

cout?"\n請(qǐng)輸入要被修改的元素:";cin?olds;

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

list.UpdatcList(olds,news);

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

list.TraverseList(ff);

cout?"\n下面請(qǐng)構(gòu)造單鏈表list2n;

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

cin?init_size;

seed=120;

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

cin?xu;

cout?"\n按回車鍵結(jié)束…”;

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

1.2.5運(yùn)行結(jié)果

17

1.3約瑟夫生者死者游戲

1.3.1項(xiàng)目簡(jiǎn)介

約瑟夫生者死者游戲的大意是：30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，

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

奈，大家只得同意這種辦法，并議定30個(gè)人圍成一圈，由第一個(gè)人開始，依次報(bào)數(shù)，數(shù)到第

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

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

1.3.2設(shè)計(jì)思路

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

某個(gè)指定的第1號(hào)開始，沿環(huán)計(jì)數(shù)，每數(shù)到第m個(gè)人就讓其出列，且從下一個(gè)人開始重新計(jì)

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

本游戲的要求用戶輸入的內(nèi)容包括：

1.旅客的個(gè)數(shù)，也就是n的值；

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

3.所有旅客的序號(hào)作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。

本游戲要求輸出的內(nèi)容是包括

1.離開旅客的序號(hào)；

2.剩余旅客的序號(hào)；

所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行算法實(shí)

現(xiàn)。

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

為了解決這一問題，可以用長(zhǎng)度為30的數(shù)組作為線性存儲(chǔ)結(jié)構(gòu)，并把該數(shù)組看成是一個(gè)

首尾相接的環(huán)形結(jié)構(gòu)，那么每投入大海?個(gè)乘客，就要在該數(shù)組的相應(yīng)位置做一個(gè)刪除標(biāo)記,

該單元以后就不再作為計(jì)數(shù)單元。這樣做不僅算法較為復(fù)雜，而且效率低，還要移動(dòng)大量的

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

循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與一般的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一個(gè)整數(shù)來表示位置：然后

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

就將下一個(gè)結(jié)點(diǎn)從循環(huán)鏈表中刪去，然后再?gòu)膭h去結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始數(shù)起，數(shù)到第8個(gè)

結(jié)點(diǎn)，再將其下一個(gè)結(jié)點(diǎn)刪去，如此進(jìn)行下去，直到剩下15個(gè)結(jié)點(diǎn)為止。

18

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

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

(1)創(chuàng)建含有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表；

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

p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始i置為1;

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

(從p指向的結(jié)點(diǎn)沿鏈前進(jìn)k-1步；

刪除第k個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))；

p指向q的下一個(gè)結(jié)點(diǎn)；

輸出其位置q->data;

i自增1;

}

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

1.3.4程序清單

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

{

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++){//刪除一半結(jié)點(diǎn)

fbr(j=l;jvk?l;j++)〃沿鏈前進(jìn)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)

)

}

有了上述算法分析和設(shè)計(jì)之后，實(shí)現(xiàn)就比較簡(jiǎn)單了。首先要定義一個(gè)鏈表結(jié)構(gòu)類型，然

后編寫一個(gè)主函數(shù)調(diào)用上面已定義好的函數(shù)即可。主函數(shù)的源程序如下：

#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("總?cè)藬?shù)n.報(bào)數(shù)上限k=")；

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

R=InitRing(n,R);

R=DeleteDeath(n,k,R);

OutRing(n,R);

}

1.3.5運(yùn)行結(jié)果

編譯運(yùn)行上述程序，提示：總?cè)藬?shù)n.報(bào)數(shù)上限k=

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

9182761626719301224822523

21252829123410111314151720

1.4約瑟夫雙向生死游戲

1.4.1項(xiàng)目簡(jiǎn)介

約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎(chǔ)上，正向計(jì)數(shù)后反向計(jì)數(shù)，然后再

正向計(jì)數(shù)。具體描述如下：30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險(xiǎn)萬分;

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

得同意這種辦法，并議定30個(gè)人圍成一圈，山第一個(gè)人開始，順時(shí)針依次報(bào)數(shù)，數(shù)到第9

人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，逆時(shí)針數(shù)到第5人，將他投入大海，然

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

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

1.4.2設(shè)計(jì)思路

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

某個(gè)指定的第1號(hào)開始，沿環(huán)計(jì)數(shù)，數(shù)到第m個(gè)人就讓其出列，然后從第m+1個(gè)人反向計(jì)

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

出列，然后再反向數(shù)k個(gè)人后讓其出列。這個(gè)過程一直進(jìn)行到剩下q個(gè)旅客為止。

本游戲的要求用戶輸入的內(nèi)容包括：

1.旅客的個(gè)數(shù)，也就是n的值；

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

21

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

4.所有旅客的序號(hào)作為?組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。

本游戲要求輸出的內(nèi)容是包括

1.離開旅客的序號(hào)；

2.剩余旅客的序號(hào)；

所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義?種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行算法實(shí)

現(xiàn)。

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

約瑟夫雙向生死游戲如果用單循環(huán)鏈表作為線性存儲(chǔ)結(jié)構(gòu)，就只能正向計(jì)數(shù)結(jié)點(diǎn)，反向

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

對(duì)要簡(jiǎn)單得多。

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

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

如下：

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

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

p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始i置為1:

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

｛從p指向的結(jié)點(diǎn)沿鏈前進(jìn)m-l步；

刪除第m個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))；

p指向q的下一個(gè)結(jié)點(diǎn)；

輸出其位置q->data;

i自增1;

從p指向的結(jié)點(diǎn)沿鏈后退k-1步；

刪除第k個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))；

p指向q的上一個(gè)結(jié)點(diǎn)；

輸出其位置q->data;

i自增1;

)

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

22

1.4.4程序清單

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

typedefintElemType;

〃雙向鏈表結(jié)點(diǎn)的類型定義

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;〃左指針

structDuLNode*next;〃右指針

}DuLNode;

#defineLEN20

classDuLinkList

{private:

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

DuLNode*curr;〃當(dāng)前結(jié)點(diǎn)指針

intcount;//雙向循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)

public:

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

DuLinkList();

〃析構(gòu)函數(shù)

-DuLinkList(){deletehead;}

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

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

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

voidClearCList();

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

intCListSize();

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

boolCListEmpty();

〃返回指向第pos個(gè)結(jié)點(diǎn)的指針

DuLNode*Index(intpos);

〃返回雙向循環(huán)鏈表中指定序號(hào)的結(jié)點(diǎn)值

ElemTypeGetElem(intpos);

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

23

voidTraverseCList();

〃當(dāng)前指針curr指向pos結(jié)點(diǎn)并返回curr

DuLNode*Reset(intpos=0);

〃當(dāng)前指針curr指向下一結(jié)點(diǎn)并返回

DuLNode*Next();

〃當(dāng)前指針curr指向上?結(jié)點(diǎn)并返回

DuLNode*Prior();

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

boolEndOCList();

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

boolEndCList();

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

boolPEndCList();

〃刪除curr->next所指結(jié)點(diǎn)，并返回所刪結(jié)點(diǎn)的data

ElemTypeDeleteNt();

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

boolFindCList(ElemType&item);

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

boolUpdateCList(constElemType&itcm,ElemType&e);

〃向鏈表中第pos個(gè)結(jié)點(diǎn)前插入域值為item的新結(jié)點(diǎn)

voidInsertCLfront(constElemType&item,intpos);

〃向鏈表中第pos個(gè)結(jié)點(diǎn)后插入域值為item的新結(jié)點(diǎn)

voidInsertCLafter(constElemType&item,intpos);

〃從鏈表中刪除第pos個(gè)結(jié)點(diǎn)并返回被刪結(jié)點(diǎn)的data

ElemTypeDclcteCList(intpos);

}.

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

#include<iostream.h>

#include<stdlib.h>

#include"dcirlinkl.hH

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

DuLinkList::DuLinkList()

{hcad=newDuLNode;

head->prior=head;

24

head->next=head;

curr=NULL;

count=0;

)

〃創(chuàng)建有序或無序的帶頭結(jié)點(diǎn)的雙向循環(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)鏈表長(zhǎng)度

intDuLinkList::CListSize()

{DuLNode*p=head->next;

inti=0;

while(p!=head)

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

returni;

}

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

boolDuLinkList::CListEmpty()

{returnhcad->next=head;}

〃返回指向第pos個(gè)結(jié)點(diǎn)的指針

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)鏈表中指定序號(hào)的結(jié)點(diǎ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;

}

〃當(dāng)前指針curr指向pos結(jié)點(diǎn)并返回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;

}

〃當(dāng)前指針curr指向下一結(jié)點(diǎn)并返回

DuLNode*DuLinkList::Next()

{curr=curr->next;

returncurr;

}

〃當(dāng)前指針curr指向上一結(jié)點(diǎn)并返回

DuLNode*DuLinkList::Prior()

{curr=curr->prior;

27

returncurr;

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

boolDuLinkList::EndOCList()

{returncurr=head;}

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

boolDuLinkList::EndCList()

{returncurr->next=head;}

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

boolDuLinkList::PEndCList()

{returncurr->prior==head;}

〃刪除curr->next所指結(jié)點(diǎn)，并返回所刪結(jié)點(diǎn)的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個(gè)結(jié)點(diǎn)前插入域值為item的新結(jié)點(diǎn)

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->