第一篇：數據結構實習報告

數據結構第六次作業p134

——11411203張玉

24.template

void SeqQueue::EnQueue(const T& x){//插入函數

if(IsFull()==true){

maxSize=2*maxSize;

elements[rear]=x;

rear=(rear+1)%maxSize;

}

elements[rear]=x;

rear=(rear+1)%maxSize;

};

template

bool SeqQueue::DeQueue(const T& x){//刪除函數if(IsEmpty()==true)return false;

if(rear<=maxSize/4){

maxSize=maxSize/2;

x=elements[front];

front=(front+1)%maxSize;

}

x=elements[front];

front=(front+1)%maxSize;

return true;

};

29.// 利用優先級隊列實現棧和隊列

#include

template class PQueue;//前視的類定義

template class Stack;

template class Queue;//優先級隊列結點類的定義 template

class PQueueNode

{

friend class PQueue;//PQueue類作為友元類定義friend class Stack;

friend class Queue;

public:

PQueueNode(T &value, int newpriority, PQueueNode priority(newpriority), link(next){}//構造函數 * next):data(value),virtual T GetData(){ return data;}//取得結點數據

virtual int GetPriority(){ return priority;}//取得結點優先級

virtual PQueueNode * GetLink(){ return link;}//取得下一結點地址

virtual void SetData(T& value){ data = value;}//修改結點數據

virtual void SetPriority(int newpriority){ priority = newpriority;} //修改結點優先級

virtual void SetLink(PQueueNode * next){ link = next;}//修改指向下一結點的指針 private:

T data;//數據

int priority;//優先級

PQueueNode *link;//鏈指針

};

//優先級隊列的類定義

template

class PQueue

{

friend class Stack;

friend class Queue;

public:

PQueue():front(NULL), rear(NULL){}//構造函數

virtual ~PQueue(){ MakeEmpty();}//析構函數

virtual void Insert(T &value, int newpriority);//插入新元素value到隊尾 virtual T Remove();//刪除隊頭元素并返回 virtual T Get();//讀取隊頭元素的值 virtual void MakeEmpty();//置空隊列

virtual int IsEmpty(){ return front == NULL;}//判隊列空否private:

PQueueNode *front, *rear;//隊頭指針, 隊尾指針

};template

void PQueue::MakeEmpty()

{

//將優先級隊列置空

PQueueNode *q;

while(front!= NULL)//鏈不空時, 刪去鏈中所有結點

{

//循鏈逐個刪除

q = front;

front = front->link;

delete q;

}

rear = NULL;//隊尾指針置空

}template

void PQueue::Insert(T &value, int newpriority)

{

//插入函數

PQueueNode *q = new PQueueNode(value, newpriority, NULL);if(IsEmpty())

front = rear = q;//隊列空時新結點為第一個結點

else

{

PQueueNode *p = front, *pr = NULL;//尋找q的插入位置

while(p!= NULL && p->priority >= newpriority)//隊列中按優先級從大到小鏈接{

pr = p;

p = p->link;

}

if(pr == NULL)

{

//插入在隊頭位置

q->link = front;

front = q;

}

else

{

q->link = p;

pr->link = q;//插入在隊列中部或尾部

if(pr == rear)

rear = q;

}

}

}

//刪除隊頭元素并返回

template

T PQueue::Remove()

{

if(IsEmpty())

return NULL;PQueueNode *q = front;

front = front->link;//將隊頭結點從鏈中摘下

T &retvalue = q->data;

delete q;

if(front == NULL)

rear = NULL;return retvalue;

}

//讀取隊頭元素的值

template

T PQueue::Get()

if(IsEmpty())

return NULL;

else

return front->data;

}

//(1)棧的定義與實現

template

class Stack:public PQueue

{

//棧類定義

public:

Stack():PQueue(){} //構造函數

void Insert(T & value);//插入新元素value到隊尾

};template

void Stack::Insert(T & value)

{

//插入函數

PQueueNode *q = new PQueueNode(value, 0, NULL);if(IsEmpty())front = rear = q;//棧空時新結點為第一個結點

else

{

//插入在前端

q->link = front;

front = q;

}

}//--------------------------Queue //(2)隊列的定義與實現

template

class Queue:public PQueue

{

//隊列類定義

public:

Queue():PQueue(){}//構造函數

void Insert(T & value);//插入新元素value到隊尾

};template

void Queue::Insert(T & value)

{

//插入函數

PQueueNode *q = new PQueueNode(value, 0, NULL);

if(IsEmpty())

front = rear = q;//隊列空時新結點為第一個結點

else

rear = rear->link = q;//插入在隊尾位置

void main(){

Stack aStack;Queue aQueue;

int n = 1;

aStack.Insert(n);aQueue.Insert(n);}

第二篇：數據結構實習報告

數據結構實習報告

班級：13軟件二班

姓名：殷健 學號：1345536225

子集和數問題

1：問題描述

子集和數問題1：子集和問題的為〈W,c〉。其中，W={w1,w2,...,wn}是一個正整數的集合，子集和數問題判定是否存在W的一個子集W1，使得∑W1=c∑W(0

程序中設計了函數void computeSumofSub(int s,int k,int r)，其意義是從第k項開始，如果s（已經決策的和數）和w[k]（當前元素）之和為和數，就把結果輸出來，否則如果s與，w[k],w[k+1]之和小于和數，則調用computeSumofsub(s+w[k],k+1,r-w[k])，意為選擇此結點的左分支，再判斷s和后面所有元素之和是否不小于M（所有的加起來都小，必定無解），并且s+w[k+1]<=M（由于輸入的數據要求是從小到大且無重復元素，所以若s+w[k+1]）>M，也是無解），若條件符合即調用computeSumofSub(s,k+1,r-w[k])，即選擇當前結點的右分支。

算法展示：

#include using namespace std;#include #include #define M 50 class SumOfSub{ private: int w[M];

int m;int x[M];public: SumOfSub(int a[], int b, int n){

for(int i=0;i=m&&s+w[k+1]<= m){ x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);} }

};void main(){ int sum=0;int w[M];srand((unsigned)time(NULL));

for(int i=0;i

} cout<<“隨機數組為：”;cout<

cout<<“符合條件的子集為:”;for(int i=0;i<=k;i++){ } cout<

} cout<<“數組元素總和為：”<>m;sum=m*sum;cout<

復雜性分析: 對于不同的輸入結果，算法的執行次數有所不同，最好情況是n，最壞情況是n*2^n。盡管差異很大，但當n很大時，對某些輸入而言，回溯法仍可在短時間內求解。其它說明: 按書中所講的約束條件，程序中所有變量都是整型，輸入的各元素要從小到大輸入，而且不能有重復的元素。若是想要無序輸入，可以程序中加入程序1.c的歸并排序算法，對輸入的數組排序即可。

拓展一

問題描述: 子集和數問題拓展一：子集和問題的為〈W,c，p〉。其中，W={w1,w2,...,wn}是一個正整數的集合，子集和數問題判定是否存在W的一個子集W1，使得∑W1=c∑W(0

問題分析：

增加一個數組p,使得p的每個元素與w對應元素關系為pi=Wi+10;最后結果W子集中元素個數越多，則p和最大，但也可以將每個符合條件子集對應P集合的元素和計算出做個比較，然后輸出最大的再對應原W子集。

算法演示

#include using namespace std;#include #include #define M 50 class SumOfSub{ private: int w[M];int p[M];int m;int x[M];

int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){

max=0;j=0;

for(int i=0;i

w[i]=a[i];

p[i]=a[i]+10;

}

m = b;

x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout<<“ ”;

} else if(s+w[k]+w[k+1] <= m){ computeSumOfSub(s+w[k],k+1,r-w[k]);} if(s+r-w[k]>=m&&s+w[k+1]<= m){ x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);} } void printResult(int k){

int S=0;int i;

cout<<“符合條件的子集為:”;

for(i=0;i<=k;i++){ if(x[i] == 1){

S=S+p[i];

cout<

}

cout<<“p和為:”<

cout<

if(S>max){

max=S;

int J=0;

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

if(x[i]==1){

N[J]=w[i];

J++;

}

}

j=J;

} } void special(){

cout<

for(int i=0;i

cout<

}

cout<

for(int i=0;i

w[i]=rand();

if(w[i]==0){

w[i]=rand();

}

sum=sum+w[i];} cout<<“隨機數組為：”;for(i=0;i

cout<>m;sum=m*sum;cout<<“子集和為:”<

r += w[i];} sumOfSub.computeSumOfSub(0, 0, r);

sumOfSub.special();} 運行結果

復雜性分析

對于不同的輸入結果，算法的執行次數有所不同，最好情況是n，最壞情況是n*2^n。盡管差異很大，但當n很大時，對某些輸入而言，回溯法仍可在短時間內求解。

拓展二

問題描述

子集和數問題拓展一：子集和問題的為〈W,c，P〉。其中，W={w1,w2,...,wn}是一個正整數的集合，子集和數問題判定是否存在W的一個子集W1，使得∑W1=c∑W(0

問題分析

增加一個數組隨機數組P，每個符合條件子集對應P集合的元素和計算出做個比較，然后輸出最大的再對應原W子集。

算法演示

#include using namespace std;#include #include #define M 50 class SumOfSub{ private: int w[M];int p[M];int m;

int x[M];int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){

max=0;

j=0;

cout<<“隨機數組p為:”;

for(int i=0;i

w[i]=a[i];

p[i]=rand();

cout<

}

cout<

m = b;

x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout<<“ ”;

} else if(s+w[k]+w[k+1] <= m){ computeSumOfSub(s+w[k],k+1,r-w[k]);} if(s+r-w[k]>=m&&s+w[k+1]<= m){ x[k] = 0;computeSumOfSub(s, k+1, r-w[k]);} } void printResult(int k){

int S=0;int i;

cout<<“符合條件的子集為:”;

for(i=0;i<=k;i++){ if(x[i] == 1){

S=S+p[i];

cout<

}

cout<<“p和為:”<

cout<

if(S>max){

max=S;

int J=0;

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

if(x[i]==1){

N[J]=w[i];

J++;

}

}

j=J;

} } void special(){

cout<

for(int i=0;i

cout<

}

cout<

for(int i=0;i

w[i]=rand();

if(w[i]==0){

w[i]=rand();

}

sum=sum+w[i];} cout<<“隨機數組w為：”;for(i=0;i

cout<>m;sum=m*sum;cout<<“子集和為:”<

r += w[i];} sumOfSub.computeSumOfSub(0, 0, r);

sumOfSub.special();}

運行結果

復雜性分析

對于不同的輸入結果，算法的執行次數有所不同，最好情況是n，最壞情況是n*2^n。盡管差異很大，但當n很大時，對某些輸入而言，回溯法仍可在短時間內求解。

第三篇：數據結構實習報告

附件：

實習報告格式，如下：

數據結構實習報告

班級： 姓名：

xxx（20121514101）

xxx（20121514101）

xxx（20121514101）

指導教師：

日期：

題目

一、問題描述（把你所選的題目及要求說一下）

二、概要設計（抽象數據類型定義）

三、詳細設計（主要算法和函數間的調用關系）

四、調試分析（調式過程中出現的問題及如何改正）

五、心得體會（組內成員的分工及實習期間的體會）

六、用戶手冊（系統的使用方法介紹）

可參照習題集上的實習報告格式。

第四篇：數據結構實習報告

一、概述軟件開發的流程

二、回顧C語言的基本語法：

1、常量（類型）

2、變量（類型、定義）

3、表達式（例子：三位數的拆分）

4、控制語句（if條件語句，例子：餓了嗎？for循環語句，例子：做好事問題求解）

5、數組（例子：猜數字游戲）

三、學生成績計算系統

做好事問題求解：

某學校為表揚好人好事需核實一件事，老師找了A、B、C、D三個學生，A說：“不是我。”。B說：“是C。”。C說：“是D。”。D說：“C胡說”。這四個人中三個人說了實話。請問：這件好事是誰做的？

#include “Stdio.h” #include “Conio.h”

void main(void){ char thisman;/*定義變量用來保存做好事的人*/ int sum=0;/*求和變量*/ /*循環枚舉做好事的人*/ for(thisman='A';thisman<='D';thisman++){ /*對四個人所說的話進行求和，真話為1，假話為0*/ sum=(thisman!='A')+(thisman=='C')+(thisman=='D')+(thisman!='D');/*判斷和是否為3，真話3，假話1*/ if(sum==3){ /*找到做好事的人，輸出*/ printf(“thisman is %cn”,thisman);}

} getch();} 猜數字：

在計算機上設置一個沒有重復數字的4位數，不能讓猜得人知道。猜的人就可以開始猜。每猜一個數字，出數者就要根據這個數字給出幾A幾B，其中A前面的數字表示位置正確的數的個數，而B前的數字表示數字正確而位置不對的數的個數。

如正確答案為5234，而猜的人猜5346，則是1A2B，其中有一個5的位置對了，記為1A，而3和4這兩個數字對了，而位置沒對，因此記為2B，合起來就是1A2B。

接著猜的人再根據出題者的幾A幾B繼續猜，直到猜中為止。

次數限制：

有的時候，這個游戲有猜測次數上的限制。根據計算機測算，這個游戲，如果以最嚴謹的計算，任何數字可以在7次之內猜出。而有些地方把次數限制為6次或更少，則會導致有些數可能猜不出來。而有些地方考慮到人的邏輯思維難以達到計算機的那么嚴謹，故設置為8次甚至10次。也有的沒有次數上的限制。我們今天要做的這個游戲就是設定次數為8次。

#include “Stdio.h” #include “Conio.h” void guess(int b[])/*猜數字游戲進行猜數的函數，采用數組作為參數*/ { int i=0,j=0,s=0,x=0,k1=0,k2=0;/*i、j、s用于進行循環，x用記錄猜

數的次數，k1用于記錄位置相同且數相同的數字個數、k2記錄數相同的數字個數*/ int a[4];while(1){ x++;printf(“di %d ci shu ru:”,x);scanf(“%d”,&j);/*輸入要猜的數放在變量j中*/ for(i=3;i>=0;i--)/*將輸入的4位數進行拆分放到數組a中*/ { a[i]=j%10;j=j/10;} for(i=0;i<4;i++)/*比較位置和數字都一致的*/ { if(a[i]==b[i])k1++;} for(i=0;i<4;i++)/*只比較數字相同不管位置*/ { for(s=0;s<4;s++)if(a[i]==b[s])k2++;} printf(“%dA%dBn”,k1,k2);if(x==8)/*如果已經猜了8次還沒有猜對那么就要提示并推出這一輪游戲*/ { printf(“your time over back menun”);break;} if(k1==4&&k2==4)/*猜對了數字，提示勝利*/ { printf(“win!”);break;} k1=0;/*將計數變量清零*/ k2=0;} } void set_num()/*設置被猜的數子*/ { printf(“input number:”);scanf(“%d”,&num);/*輸入被猜的數字，存放在變量num中*/ for(i=3;i>=0;i--)/*將四位數拆分并按高低位存放在數組b中*/ { b[i]=num%10;num=num/10;} printf(“ok press any key”);getch();/*等待*/ clrscr();/*清屏*/ } int main(void){ int b[4],num,i,ch=0;while(1)/*條件為1的無限循環作為軟件運行的主體，等待退出命令*/ { printf(“****menu****n”);printf(“set number input 1n”);printf(“guess number input 2n”);printf(“exit input 3n”);printf(“input your select items:”);scanf(“%d”,&ch);if(ch==1)/*選擇變量為1調用設置被猜數字函數*/ { set_num();} if(ch==2)/*選擇變量為2調用猜數游戲過程函數*/ { guess(b);} if(ch==3)/*選擇變量為3退出循環結束游戲*/ { break;} }

getch();return 0;}

第五篇：數據結構實習報告

數據結構課程設計的實習報告怎么寫呀，請求做過課設的同學發一篇范文過來謝謝-_-規范實習報告的開頭應給出題目、班級、姓名、學號和完成日期，并包括以下七個內容：

1、需求分析以無歧義的陳述說明程序設計的任務，強調的是程序要做什么?明確規定：(1)輸入的形式和輸入值的范圍；(2)輸出的形式；(3)程序所能達到的功能；(4)測試數據：包括正確地輸入及其輸出結果和含有錯誤的輸入及其輸出結果，數據結構實習報告。

2、概要設計說明本程序中用到的所有抽象數據類型的定義、主程序的流程以及各程序模塊之間的層次(調用)關系。

3、詳細設計實現概要設計中定義的所有數據類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達到的詳細程度建議為：按照偽碼算法可以在計算機鍵盤直接輸入高級程序設計語言程序)；畫出函數的調用關系圖。

4、調試分析內容包括：(1)調試過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析；(2)算法的時空分析(包括基本操作和其他算法的時間復雜度和空間復雜度的分析)和改進思想；(3)經驗和體會等，實習報告《數據結構實習報告》。

5、用戶使用說明說明如何使用你編寫的程序，詳細列出每一步操作步驟。

6、測試結果列出你的測試結果，包括輸入和輸出。這里的測試數據應該完整和嚴格，最好多于需求分析中所列。

7、附錄題目：約瑟夫-實習報告尺寸：約瑟夫-實習報告.doc目錄：

一、需求分析

二、概要設計

三、程序具體設計及函數調用關系

四、調試分析

五、測試結果原文：實習報告題目：約瑟夫(Joseph)問題的一種描述是：編號為1，2，.，n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數)。一開始任選一個整數作為報數上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個開始重新從1報數，如此下去，直至年有人全部出列為止。試設計一個程序求出出列順序。班級：姓名：學號：完成日期：

一、需求分析1.本演示程序中，利用單向循環鏈表存儲結構存儲約瑟夫環數據(即n個人的編號和密碼)。2.演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數據，運算結果顯示在其后。3.程序執行的命令包括：1)構造單向循環鏈表；2)4.測試數據m的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6(正確的出列順序為6，1，4，7，2，1，3，5)。

二、概要設計1.單向循環鏈表的抽象數據類型定義為：ADT List{數據對象：D={ai|ai∈正整數，I=1，2，.，n,n≥0}數據關系：R1={ai-1，ai|，ai-1，ai∈D,I=1，2，.，n}基本操作：Init List(&L)操作結果：構造一個空的線性表L。List Insert(&L,i,e)初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結果：在L中第i個位置之前插入新的數據無素e，L長度加1。List Delete(&L,i,&e)初始條件：線性表L存在非空，1≤i≤List Length(L).操作結果：刪除L的第i個元素，并用e返回其值，L長度減1。2.程序包含四個模塊：1)主程序模塊：void main(){.