第一篇：數(shù)據(jù)結(jié)構(gòu)作業(yè)

1.(1)問題的描述：設(shè)計(jì)一個程序exp1-1.cpp,輸出所有小于等于n(n為一個大于二的正整數(shù))的素?cái)?shù)。要求：（1）每行輸出10個素?cái)?shù);(2)盡可能采用較優(yōu)的算法。

(2)解決思想：判斷一個整數(shù)n是否為素?cái)?shù)，只需要用2~n-1之間的每一個整數(shù)去除，如果都不能被整除，那么m就是一個素?cái)?shù)。其實(shí)可以簡化，n不被被2~n-1之間的每一個整數(shù)去除，只需被2~根號n之間的每個數(shù)去除就可以了。因?yàn)槿绻鹡能被2~n-1之間任意整數(shù)整除，如果這個數(shù)大于根號m，那這個數(shù)必定對應(yīng)的還有一個比根號m小的因子(3)源代碼：

#include #include using namespace std;int main(){ int n,flag;int count=0;cout<<“請輸入一個大于二的正整數(shù)”<<“n=”;

cin>>n;if(n<=2)

cout<<“輸入錯誤”;

else

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

{

flag=0;

for(int j=2;j<=(int)sqrt(i);j++)

{

if(i%j==0)

{

flag=1;

break;

}

}

if(flag==0)

{

cout<

count++;

if(count%10==0)

cout<

}

}

cout<

} return 0;(4)運(yùn)行結(jié)果截圖

(5)心得體會:按照素?cái)?shù)定義來判斷素?cái)?shù)時(shí)，可以進(jìn)行一個較為明顯的優(yōu)化，即只需從2枚舉到根n即可。

2.(1)問題的描述：編寫一個程序exp1-2.cpp,計(jì)算任一輸入的正整數(shù)的各位數(shù)字之和，并分析算法的時(shí)間復(fù)雜度。

(2)解決思想:采用遞歸的算法，對輸入的正整數(shù)進(jìn)行不斷的取模運(yùn)算和取商運(yùn)算，即可得到該正整數(shù)的各位數(shù)字之和。時(shí)間復(fù)雜度為O(1)(3)源代碼

exp1-2.cpp

#include using namespace std;int fun(int n){ if(n <= 0){

return 0;} else

return n%10 + fun(n/10);} int main(){

int n;

cout<<”請輸入一個正整數(shù):“;

cin>>n;

cout<<”各位數(shù)字之和是:“<

(5)心得體會：當(dāng)遇到一個復(fù)雜問題時(shí)，可以從最簡單的地方著手，剛開始不知道n是幾位數(shù)，感覺這個問題有點(diǎn)棘手，心想如果是二位數(shù)就好辦了，因此腦海中浮現(xiàn)了“遞歸”的思想，把一個復(fù)雜問題轉(zhuǎn)變成簡單問題。即把一個正整數(shù)n邊分解邊累加，直到分解完畢。

3.(1)問題的描述：編寫一個程序exp1-3.cpp,判斷一個字符串是否為“回文”(順讀和倒讀都一樣的字符串稱為“回文”)，并分析算法的時(shí)間復(fù)雜度。

(2)解決思想：依次將字符串兩端的字符進(jìn)行比較，若都相同，則為回文字符串。時(shí)間復(fù)雜度為O(n)。(3)源代碼：

exp1-3.cpp #include #include using namespace std;#define MAX 1000

int fun(char s[]){ int flag=1;int i,j,n=strlen(s);

for(i=0,j=n-1;i

if(s[i]!=s[j])

{

flag=0;

break;

} return(flag);} int main(){ char s[MAX];cout<<”輸入一串字符串:“;cin>>s;if(fun(s)==1)

cout<<”字符串是回文“<

cout<<”字符串不是回文"<

(5)心得體會：如果將這題進(jìn)行擴(kuò)展，判斷一個正整數(shù)是否為回文數(shù)，也可以采用類似的算法。將正整數(shù)的各位存到數(shù)組里，用i從左到右掃描s，用j從右到左掃描s,若s[i]與s[j]不相等，則退出循環(huán)，否則繼續(xù)比較，直到i

第二篇：數(shù)據(jù)結(jié)構(gòu)作業(yè)——二叉樹

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二

題目：

用先序遞歸過程監(jiān)理二叉樹（存儲結(jié)構(gòu)：二叉鏈表）

輸入數(shù)據(jù)按先序遍歷輸入，當(dāng)某節(jié)點(diǎn)左子樹或者右子樹為空時(shí)，輸入‘*’號，如輸入abc**d**e**時(shí)，得到的二叉樹為：

并用如下實(shí)力測試：

算法思路：

顯然，建立一個二叉鏈表存儲的二叉樹，如果不考慮效率要求，考慮到程序的簡介性，遞歸建立和遞歸遍歷是一種很好的辦法。

利用C++的類模板的方法實(shí)現(xiàn)建立，遍歷，輸出等二叉樹操作。首先利用構(gòu)造函數(shù)實(shí)現(xiàn)先序遍歷建立二叉樹，然后調(diào)用類模板中已經(jīng)聲明好的四種遍歷函數(shù)，將遍歷結(jié)果輸出，檢驗(yàn)建立好的二叉樹是否為要求的二叉樹。

初始化：利用構(gòu)造函數(shù)建立二叉樹。采用先序遞歸的調(diào)用方法，構(gòu)造函數(shù)主體如下：

template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個”<>aa;if(aa==“*”)root = NULL;else{

root = new BiNode;

//生成一個結(jié)點(diǎn) root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

} return root;} 構(gòu)造這樣的函數(shù)，可以在輸入時(shí)，按先序遍歷順序每次輸入一個節(jié)點(diǎn)的數(shù)據(jù)，可以實(shí)現(xiàn)任意二叉樹的構(gòu)造。

為了檢驗(yàn)構(gòu)造的二叉樹是否為預(yù)先設(shè)想的二叉樹，需要遍歷二叉樹并進(jìn)行輸出?？紤]到單一的輸出并不能確定唯一的二叉樹，因此對遍歷二叉樹的四種常用發(fā)方法，即先序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷分別實(shí)現(xiàn)，通過遍歷結(jié)果檢驗(yàn)構(gòu)造的二叉樹是否為預(yù)先設(shè)計(jì)好的二叉樹。

先序遍歷：采用遞歸的方法建立。template voidBiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點(diǎn)為空，則返回空 else{ cout<data<<“ ”;//訪問根節(jié)點(diǎn)

xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹

} 中序遍歷：遞歸方法建立： template voidBiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點(diǎn)為空，則返回空 else{ zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹 cout<data<<“ ”;

//訪問根結(jié)點(diǎn)

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

}

} 后序遍歷：遞歸方法建立： template voidBiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點(diǎn)為空，返回空 else{ houxu(root->lchild);

//后序遞歸遍歷root的左子樹 houxu(root->rchild);

//后序遞歸遍歷root的右子樹 cout<data<<“ ”;

//訪問根節(jié)點(diǎn)

} } 層序遍歷：采用非遞歸方法。利用隊(duì)列的方法層序遍歷二叉樹。建立一個隊(duì)列，在訪問一個節(jié)點(diǎn)的時(shí)候，把它的左孩子和右孩子入隊(duì)，并且將這個節(jié)點(diǎn)出隊(duì)。當(dāng)隊(duì)列為空時(shí)，就完成了對二叉樹的層序遍歷。

template voidBiTree::cengxu(BiNode *root){ constintMaxSize = 100;int front = 0;int rear = 0;//利用隊(duì)列的方法對樹進(jìn)行層序遍歷 BiNode* Q[MaxSize];BiNode* q;if(root==NULL)return;// 如果節(jié)點(diǎn)為空，返回空 else{

Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì) while(front!= rear)

{

q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì) cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

} } } 函數(shù)主體部分：聲明一個類中的對象，調(diào)用構(gòu)造函數(shù)，建立二叉樹，并輸出四種遍歷結(jié)果，檢驗(yàn)輸出結(jié)果。

int main(){

BiTreeshu;//聲明類中一個對象，在構(gòu)造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結(jié)點(diǎn)的指針

cout<<“前序遍歷序列為 ”<

程序結(jié)構(gòu)：

主函數(shù)建立一個類模板定義構(gòu)造函數(shù)，析構(gòu)函數(shù)，以及成員函數(shù)聲明類中的一個對象調(diào)用構(gòu)造函數(shù)，構(gòu)造一顆二叉樹層序遍歷二叉樹后序遍歷二叉樹中序遍歷二叉樹前序遍歷二叉樹獲取該二叉樹的根節(jié)點(diǎn)將結(jié)果輸出，人工檢驗(yàn) 源代碼：

#include using namespace std;

template struct BiNode

{

T data;

BiNode *lchild, *rchild;};

template class BiTree

{ public: BiTree();

//構(gòu)造函數(shù)，初始化一棵二叉樹 ~BiTree(void);

//析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲空間

BiNode* Getroot();

//獲得指向根結(jié)點(diǎn)的指針

void xianxu(BiNode *root);

//前序遍歷二叉樹

void zhongxu(BiNode *root);

//中序遍歷二叉樹

void houxu(BiNode *root);

//后序遍歷二叉樹

void cengxu(BiNode *root);

//層序遍歷二叉樹 private:

BiNode *root;

BiNode *Creat();

void Release(BiNode *root);

};template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個”<>aa;

if(aa==“*”)root = NULL;

else{

root = new BiNode;

//生成一個結(jié)點(diǎn)

root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

}

return root;}

template BiTree::~BiTree(void){ Release(root);//析構(gòu)函數(shù)，釋放存儲指針?biāo)枰目臻g }

template BiNode* BiTree::Getroot()//獲取根節(jié)點(diǎn)所在指針的位置 { return root;}

template void BiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點(diǎn)為空，則返回空

else{

cout<data<<“ ”;//訪問根節(jié)點(diǎn)

xianxu(root->lchild);//先序遍歷樹的左子樹

xianxu(root->rchild);//先序遍歷樹的右子樹

} }

template void BiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點(diǎn)為空，則返回空

else{

zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹

cout<data<<“ ”;

//訪問根結(jié)點(diǎn)

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

} }

template void BiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點(diǎn)為空，返回空

else{

houxu(root->lchild);

//后序遞歸遍歷root的左子樹

houxu(root->rchild);

//后序遞歸遍歷root的右子樹

cout<data<<“ ”;

//訪問根節(jié)點(diǎn)

} }

template void BiTree::cengxu(BiNode *root){

const int MaxSize = 100;int front = 0;int rear = 0;//利用隊(duì)列的方法對樹進(jìn)行層序遍歷

BiNode* Q[MaxSize];

BiNode* q;if(root==NULL)return;// 如果節(jié)點(diǎn)為空，返回空

else{

Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì)

while(front!= rear)

{

q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì)

cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

} } }

template void BiTree::Release(BiNode* root)//析構(gòu)函數(shù)，釋放存儲空間 {

if(root!= NULL){

Release(root->lchild);

//釋放左子樹

Release(root->rchild);

//釋放右子樹

delete root;

}

}

int main(){

BiTree shu;//聲明類中一個對象，在構(gòu)造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結(jié)點(diǎn)的指針

cout<<“前序遍歷序列為 ”<

cout<<“層序遍歷序列為”<

通過對結(jié)果的分析，發(fā)現(xiàn)輸出結(jié)果與建立二叉樹時(shí)的輸入完全符合，說明程序的運(yùn)行結(jié)果是正確的。

心得體會：

1)函數(shù)遞歸的方法可以在相當(dāng)程度上使程序簡潔，避免代碼的冗長復(fù)雜。2)構(gòu)造函數(shù)如果帶參數(shù)，在聲明對象的時(shí)候應(yīng)該將實(shí)參指出來。但是本題中構(gòu)造函數(shù)位遞歸調(diào)用，初始的根節(jié)點(diǎn)的數(shù)據(jù)值由鍵盤輸入，因此無法在聲明對象時(shí)引入實(shí)參。所以最后選擇了無參但是引用了this指針的構(gòu)造函數(shù)?？梢姡瑢τ跇?gòu)造函數(shù)的含參調(diào)用應(yīng)該小心謹(jǐn)慎。

3)編程時(shí)，要不停得檢驗(yàn)自己的輸入與輸出，必要的時(shí)候需要人工進(jìn)行計(jì)算，以保證程序的運(yùn)行按照預(yù)先的設(shè)想。

第三篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)

實(shí)驗(yàn)一 線性表

一、實(shí)驗(yàn)題

線性表的應(yīng)用———多項(xiàng)式計(jì)算

二、程序設(shè)計(jì)思路

包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實(shí)現(xiàn)思路一鏈?zhǔn)酱鎯Γ?/p>

1.void InitPoly(LNode *&p)初始化多項(xiàng)式 2.void TraversePoly(LNode *&p)遍歷多項(xiàng)式 3.void ClearPoly(LNode *&p)清除多項(xiàng)式

4.void InsertPoly(LNode *&p, double a, int e)插入一項(xiàng) 5.void DeletetPoly(LNode *&p,int pos)

刪除一項(xiàng)

6.double PolySum(LNode *&p, double x)

多項(xiàng)式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2)

多項(xiàng)式相加 順序存儲：

1.void InitPoly1(SeqList &L)初始化多項(xiàng)式 2.void ClearPoly1(SeqList &L)清除多項(xiàng)式 3.void TraversePoly1(SeqList L)

遍歷多項(xiàng)式

4.bool InsertPoly1(SeqList &L, ElemType item)插入一項(xiàng) 5.double PolySum1(SeqList L,double x)

多項(xiàng)式求值 6.bool DeleteList1(SeqList &L,int pos)

刪除一項(xiàng)

7.SeqList PolyAdd1(SeqList &L1,SeqList& L2)

多項(xiàng)式相加

三、源程序代碼

#include #include #include #include “Linkpoly.h” #include “Seqpoly.h” void main(){ cout<<“現(xiàn)在進(jìn)行第一次測試。（鏈表表示）”<>n;cout<<“請依次輸入要測試的各項(xiàng)的系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly(pa, a, e);//插入一項(xiàng) pa=pa->next;} pa=pa->next;cout<<“該多項(xiàng)式為:”;TraversePoly(pa);//輸出多項(xiàng)式 cout<>a;cin>>e;cin>>pos;if(DeletetPoly(pa, a, e, pos)){ cout<<“刪除成功！現(xiàn)在多項(xiàng)式為:”;TraversePoly(pa);cout<>x;sum=PolySum(pa, x);cout<<“該多項(xiàng)式的值為:”<>n;cout<<“請輸入該多項(xiàng)式的各項(xiàng)系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly(pb, a, e);//插入一項(xiàng) pb=pb->next;} pb=pb->next;pp=PolyAdd(pa, pb);cout<<“兩多項(xiàng)式相加后得到的多項(xiàng)式為:”;TraversePoly(pp);cout<>n;cout<<“請依次輸入要測試的各項(xiàng)的系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly1(s, a, e);} cout<<“該多項(xiàng)式為:”;TraversePoly1(s);cout<>a;cin>>e;cin>>pos;if(DeletetPoly1(s, a, e, pos)){ cout<<“刪除成功！現(xiàn)在多項(xiàng)式為:”;TraversePoly1(s);cout<>x;sum=PolySum1(s, x);cout<<“該多項(xiàng)式的值為:”<>n;cout<<“請輸入該多項(xiàng)式的各項(xiàng)系數(shù)和指數(shù):”;for(i=0;i>a;cin>>e;InsertPoly1(t, a, e);//插入一項(xiàng) } q=PolyAdd1(s, t);cout<<“兩多項(xiàng)式相加后得到的多項(xiàng)式為:”;TraversePoly1(q);cout<next=p;return true;} void TraversePoly(NodeType *p)//輸出多項(xiàng)式 { NodeType *h=p->next;if(h!=p){ cout<coef<<“*”<<“X”<<“^”<exp;h=h->next;} while(h!=p){ if(h->coef>0)cout<<“+”;cout<coef<<“*”<<“X”<<“^”<exp;h=h->next;} } void ClearPoly(NodeType *&p)//清除多項(xiàng)式 { NodeType *cp,*np;cp=p->next;while(cp!=p){ np=cp->next;delete cp;cp=np;} p->next=p;} bool InsertPoly(NodeType *&p, float a, int e)//插入一項(xiàng) { NodeType *h;if((h=new NodeType)==NULL)return false;h->coef=a;h->exp=e;h->next=p->next;p->next=h;return true;} bool DeletetPoly(NodeType *&p, float a, int e, int pos)//一項(xiàng)

{ if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){

刪除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多項(xiàng)式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多項(xiàng)式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->expexp){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} else{ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} } while(a!=p1){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} while(b!=p2){ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} return c;} Seqploy.h: #define MaxSize 10000 struct ListType{ float *list;int size;};void InitPoly1(ListType &p)//初始化多項(xiàng)式 { p.list=(float*)malloc(MaxSize*sizeof(float));if(p.list==NULL){ cout<<“動態(tài)可分配的儲存空間用完，退出運(yùn)行！”<0){ cout<<“+”;cout<

輸出多項(xiàng)式 } void ClearPoly1(ListType &p)//清除多項(xiàng)式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項(xiàng)

{ p.list[e]=a;if(p.size

{ int i,n;if(p.size==0){ cout<<“多項(xiàng)式為空,刪除無效!”<

插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值

{ double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//項(xiàng)式相加

{ ListType p;InitPoly1(p);float coef;

多項(xiàng)式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四實(shí)驗(yàn)結(jié)果分析

五.心得體會 對于結(jié)構(gòu)體的認(rèn)識增加了，對于動態(tài)存儲也有了更多的認(rèn)識，也是在不知不覺中提高了。

實(shí)驗(yàn)二 字符串的操作

一、實(shí)驗(yàn)題目——字符串的操作

二、程序設(shè)計(jì)思路

采用定長順序存儲表示，由用戶創(chuàng)建串s和串t，實(shí)現(xiàn)在串s中下標(biāo)為pos的字符之前插入串t。

三、源程序代碼

#define MAXLEN 10 typedef struct {

/*串結(jié)構(gòu)定義*/

char ch[MAXLEN];

int len;}SString;void createstring(SString *s)

/*創(chuàng)建串s*/ { int i,j;char c;printf(“input the length of the string:”);

scanf(“%d”,&j);

for(i=0;i

{

printf(“input the %d:”,i+1);

fflush(stdin);

scanf(“%c”,&c);

s->ch[i] = c;

} s->len = j;} void output(SString *s)

/*輸出串s*/ {

int i;for(i=0;ilen;i++)

printf(“%c

”,s->ch[i]);

printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標(biāo)為pos的字符之前插入串t */ {

int i;if(pos<0 || pos>s->len)

/*插入位置不合法*/

return(0);

if(s->len + t->len<=MAXLEN)

/*插入后串長≤MAXLEN*/ {

for(i=s->len + t->len-1;i>=t->len + pos;i--)

s->ch[i]=s->ch[i-t->len];/*將下標(biāo)為pos的字符后的元素往后移動t->len個長度*/

for(i=0;ilen;i++)

s->ch[i+pos]=t->ch[i];

/*將串t從下標(biāo)為pos位置開始插入到串s*/

s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/

{

for(i=MAXLEN-1;i>t->len+pos-1;i--)

s->ch[i]=s->ch[i-t->len];

for(i=0;ilen;i++)

s->ch[i+pos]=t->ch[i];

/*將串t從下標(biāo)為pos位置開始插入到串s*/

s->len=MAXLEN;

}

else

/*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/

{

for(i=0;i

s->ch[i+pos]=t->ch[i];

/*直接從下標(biāo)為pos的位置按順序插入串t*/

s->len=MAXLEN;

}

return(1);} } void main(){

SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0)

printf(“insert error!”);else {

printf(“after insert:n”);

output(str1);} }

四、實(shí)驗(yàn)結(jié)果

五、實(shí)驗(yàn)體會

通過本次實(shí)驗(yàn)，我加深了對串?dāng)?shù)據(jù)結(jié)構(gòu)的理解。在串的定長順序存儲結(jié)構(gòu)中，按照預(yù)定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。在存儲方式中，結(jié)點(diǎn)大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。

實(shí)驗(yàn)三

一、實(shí)驗(yàn)題目——非遞歸算法對二叉樹進(jìn)行中前序遍歷

二、程序設(shè)計(jì)思路

創(chuàng)建一棵10個節(jié)點(diǎn)構(gòu)造的完全二叉樹，并對其進(jìn)行前、中、后序遍歷。

三、源程序代碼

#define STUDENT EType #define SType SType

#define HeadEType int

#include #include

//定義數(shù)據(jù)結(jié)構(gòu)類型

struct STUDENT { char name[8];int age;char number[15];char address[20];};

struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree;

typedef struct { BinaryTreeNode *ptr;bool status;}SType;

typedef struct { SType *element;int top;int MaxSize;}Stack;

void CreatStack(Stack &S, int MaxStackSize){// 構(gòu)造一個最大容量為MaxStackSize 的堆棧

S.MaxSize = MaxStackSize;

S.element = new SType[S.MaxSize];

S.top =-1;}

bool IsEmpty(Stack &S){// 判斷堆棧S是否為空

if(S.top ==-1)

return true;

return false;}

bool IsFull(Stack &S){// 判斷堆棧S是否為空

if(S.top == MaxSize-1)

return true;

return false;}

bool Push(Stack &S , SType &x){// x進(jìn)s棧，返回進(jìn)棧后的狀態(tài)值

if(IsFull(S))

return false;

S.top++;

S.element[S.top] = x;

return true;}

bool Pop(Stack &S , SType &x){// 將s棧頂?shù)闹等≈義中，返回出棧后的狀態(tài)值

if(IsEmpty(S))

return false;

x = S.element[S.top];

S.top--;

return true;}

BinaryTreeNode

*MakeNode(EType &x)

{//構(gòu)造結(jié)點(diǎn)

BinaryTreeNode *ptr;

ptr = new BinaryTreeNode;

if(!ptr)return NULL;

ptr->data = x;

ptr-> LChild = NULL;

ptr-> RChild = NULL;

return

ptr;}

void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 聯(lián)接root，left, right所指的結(jié)點(diǎn)指針為二叉樹

root->LChild=left;

root->RChild=right;}

void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q||!IsEmpty(S)){

if(q)

{

cout<data.name<<“ ”;//訪問“根”節(jié)點(diǎn)

ele.ptr=q;

Push(S,ele);//節(jié)點(diǎn)指針進(jìn)棧，以后回溯時(shí)在退棧

q=q->LChild;//指針指向剛剛被訪問的“根”節(jié)點(diǎn)的左子樹

}

else

//當(dāng)左子樹為空時(shí)，利用堆?；厮?/p>

if(!IsEmpty(S))

{

Pop(S,ele);//退?；厮?/p>

q=ele.ptr;//指針重新指向剛剛被訪問的“根”節(jié)點(diǎn)

q=q->RChild;//指針指向該回溯節(jié)點(diǎn)的右子樹

} } }

void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q ||!IsEmpty(S)){

while(q)//找到最左邊的子樹

{

ele.ptr=q;

Push(S,ele);//指針非空時(shí)，將當(dāng)前的“根”節(jié)點(diǎn)指針進(jìn)棧，用于以后回溯

q=q->LChild;//指針繼續(xù)指向該“根”節(jié)點(diǎn)的左子樹

}

if(!IsEmpty(S))//當(dāng)左子樹為空時(shí)，進(jìn)行退棧回溯

{

Pop(S,ele);//從堆棧中回溯節(jié)點(diǎn)指針（節(jié)點(diǎn)還未訪問）

q=ele.ptr;

cout<data.name<<“ ”;//訪問回溯的“根”節(jié)點(diǎn)

q=q->RChild;//指針向回溯的節(jié)點(diǎn)右子樹推進(jìn)

} } }

void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法

Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大

CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧

while(q ||!IsEmpty(S)){

if(q)//找最左邊的子樹

{

ele.ptr=q;

ele.status=false;//進(jìn)棧前標(biāo)記為第一次進(jìn)棧

Push(S,ele);

q=q->LChild;//指針繼續(xù)向左推進(jìn)

}

else

if(!IsEmpty(S))//直到左子樹為空時(shí)，退?；厮?/p>

{

Pop(S,ele);//從堆棧中彈出回溯節(jié)點(diǎn)（還未訪問）

q=ele.ptr;//q指向當(dāng)前回溯節(jié)點(diǎn)

if(ele.status)//判斷節(jié)點(diǎn)進(jìn)棧標(biāo)志，是否對其進(jìn)行訪問

{

cout<data.name<<“ ”;//訪問回溯節(jié)點(diǎn)

q=NULL;//將q設(shè)為空，為了繼續(xù)退棧

}

else

{

ele.status=true;//改變回溯節(jié)點(diǎn)的進(jìn)棧標(biāo)記，以便再次進(jìn)棧

Push(S,ele);

q=q->RChild;//指針向該回溯節(jié)點(diǎn)的右孩子推進(jìn)

}

} } }

//主函數(shù) void main(){ BinaryTreeNode *ptr[11];

char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){

strcpy(x[11-i].name,Name[11-i]);

ptr[11-i]=MakeNode(x[11-i]);//構(gòu)造10個二叉樹節(jié)點(diǎn)

}

//將節(jié)點(diǎn)鏈接域填值，構(gòu)造一個二叉樹

//這里構(gòu)造的是一棵有10個節(jié)點(diǎn)的完全二叉樹

for(int j=1;j<5;j++){

MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構(gòu)造完畢

//***********對已構(gòu)造的完全二叉樹進(jìn)行前序非遞歸遍歷************// cout<<“對該二叉樹進(jìn)行前序遍歷結(jié)果：”<

//***********對已構(gòu)造的完全二叉樹進(jìn)行中序非遞歸遍歷************// cout<

//***********對已構(gòu)造的完全二叉樹進(jìn)行中序非遞歸遍歷************// cout<

四、實(shí)驗(yàn)結(jié)果分析

五、實(shí)驗(yàn)總結(jié)

二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因?yàn)闃涞亩x本身就是遞歸定義，因此采用遞歸的方法去實(shí)現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實(shí)現(xiàn)。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實(shí)現(xiàn)，非遞歸后序遍歷實(shí)現(xiàn)起來相對來說要難一點(diǎn)。

實(shí)驗(yàn)四

一、實(shí)驗(yàn)題目——深度優(yōu)先算法實(shí)現(xiàn)圖的遍歷

二、程序設(shè)計(jì)思路

以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，以用戶指定的頂點(diǎn)為起始點(diǎn)，實(shí)現(xiàn)無向連通圖的深度優(yōu)先，并輸出遍歷的結(jié)點(diǎn)序列。首先，根據(jù)用戶輸入的頂點(diǎn)總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先，并輸出遍歷的結(jié)果。

三、源程序代碼

#include #define MaxVerNum 50 struct edgenode { int endver;int inform;edgenode* edgenext;

};struct vexnode

{ char vertex;edgenode* edgelink;};struct Graph

{ vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊(duì)列的定義及相關(guān)函數(shù)的實(shí)現(xiàn) struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL)

return;if(Q->rear==NULL)

Q->front=Q->rear=q;else {

Q->rear->next=q;

Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL)

return;if(Q->front==Q->rear){

*e=Q->front->nData;

Q->front=Q->rear=NULL;} else {

*e=Q->front->nData;

Q->front=Q->front->next;} } //創(chuàng)建圖

void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點(diǎn)數(shù)和邊數(shù):”<>G->vexnum>>G->arcnum;cout<<“開始輸入頂點(diǎn)表:”<vexnum;i++){

cin>>G->adjlists[i].vertex;

G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”<arcnum;k++){

cout<<“請輸入邊對應(yīng)的頂點(diǎn):”;

cin>>i>>j;

p1=new edgenode;

p1->endver=j;

p1->edgenext=G->adjlists[i].edgelink;

G->adjlists[i].edgelink=p1;

p2=new edgenode;

p2->endver=i;

p2->edgenext=G->adjlists[j].edgelink;

G->adjlists[j].edgelink=p2;

//因?yàn)槭菬o向圖，所以有兩次建立邊表的過程

} }

//------------------------------深度優(yōu)先遍歷 void DFS(Graph *G,int i,int visit[]){ cout<adjlists[i].vertex<<“ ”;visit[i]=1;edgenode *p=new edgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){

DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優(yōu)先遍歷 { cout<<“該圖的深度優(yōu)先遍歷結(jié)果為:”<vexnum;i++){

visit[i]=0;//全部初始化為0，即未訪問狀態(tài)

} int m;for(i=0;ivexnum;i++){

if(G->adjlists[i].vertex==c)//根據(jù)字符查找序號

{

m=i;

DFS(G,i,visit);

break;

} } //繼續(xù)訪問未被訪問的結(jié)點(diǎn)

for(i=0;ivexnum;i++){

if(visit[i]==0)

DFS(G,i,visit);} cout<front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){

int e=0;

DeQueue(Q,&e);

cout<adjlists[e].vertex<<“ ”;

visit[e]=1;

edgenode* p=new edgenode;

p=G->adjlists[e].edgelink;

if(p)

{

int m=p->endver;

if(m==0)

{

EnQueue(Q,m);

while(visit[m]==0)

{

p=p->edgenext;

if(p==NULL)

break;

m=p->endver;

EnQueue(Q,m);

}

}

}

} } void BFStraversal(Graph *G,char c){ cout<<“該圖的廣度優(yōu)先遍歷結(jié)果為:”<vexnum;i++){

visited[i]=0;} int m;for(i=0;ivexnum;i++){

if(G->adjlists[i].vertex==c)

{

m=i;

BFS(G,i,visited);

break;

} } //繼續(xù)訪問未被訪問的結(jié)點(diǎn)

for(i=0;ivexnum;i++){

if(visited[i]==0)

BFS(G,i,visited);} cout<>ch;DFStraversal(G,ch);BFStraversal(G,ch);}

四、實(shí)驗(yàn)結(jié)果及分析

五、實(shí)驗(yàn)總結(jié)

本次試驗(yàn)采用的是鄰接表的方式實(shí)現(xiàn)圖的深度優(yōu)先遍歷和。對于深度優(yōu)先遍歷，主要是采用遞歸的方式。試驗(yàn)本身問題不是太大，但要注意輸入的問題，什么時(shí)候用空格，什么時(shí)候用回車，這一點(diǎn)是需要注意的，因?yàn)橐坏?shù)據(jù)的輸入有問題，結(jié)果當(dāng)然也就不可能正確了。只有正確的輸入數(shù)據(jù)，建立圖，才能得出正確的遍歷結(jié)果。

第四篇：C++數(shù)據(jù)結(jié)構(gòu) 大作業(yè)課程設(shè)計(jì)

C++/數(shù)據(jù)結(jié)構(gòu) 大作業(yè)/課程設(shè)計(jì)——【校園導(dǎo)游咨詢】【停車場管理】娃娃們可以收著以后用 絕對純手工打造 內(nèi)含類模塊/一維指針數(shù)組（謹(jǐn)以此程序供大家參考。運(yùn)行結(jié)果后面有貼圖）

目錄

【1】校園導(dǎo)游咨詢 程序設(shè)計(jì)源代碼 及 截圖 【2】停車場管理——方案一 程序設(shè)計(jì)源代碼 及 截圖 【3】停車場管理——方案二 程序設(shè)計(jì)源代碼 及 截圖

【1】【【校園導(dǎo)游咨詢】】

######

(ps:該校園導(dǎo)游咨詢系統(tǒng)沒有輸入值，所有信息是都在class MGraph的構(gòu)造函數(shù)中傳輸?shù)?，且校園景點(diǎn)信息皆為【【上海電力學(xué)院】】景點(diǎn)信息。請大家注意，直接從文章copy到visual stutio中會出現(xiàn)中文字符，注意刪除，推薦大家在一行語句的分號后面，點(diǎn)出光標(biāo)，按一下delete鍵，然后按一下enter鍵，完成visual stutio的自動對齊，這樣程序看起來一目了然，更易于操作和更改)【問題描述】

設(shè)計(jì)一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)?！净疽蟆?/p>

(1)設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于10個。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。(2)為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。

(3)為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一個最短的簡單路徑?！具x作內(nèi)容】

(6)擴(kuò)充每個景點(diǎn)的鄰接景點(diǎn)的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。**************************【以下為類的定義】******************************** #include #include using namespace std;const int MaxSize=18;const int INFINITY=65535;//最大值無窮

class direction;template class MGraph;template class VertexNode//定義頭結(jié)點(diǎn)

{ friend class MGraph;public: int vex;//頂點(diǎn)名稱 T vexname;//頂點(diǎn)名稱 T vexinf;//頂點(diǎn)信息

direction dir;//存放頂點(diǎn)方位信息的direction類的dir。};

class direction { public: int ln;//存放在方向圖中的橫坐標(biāo)，表示東西 int col;//存放在方向圖中的縱坐標(biāo)，表示南北 };template class MGraph//定義無向圖的鄰接矩陣

{ public: MGraph();

//構(gòu)造函數(shù)，初始化具有n個頂點(diǎn)的圖

void printvexname();//顯示所有景點(diǎn)及景點(diǎn)代號

void printvexinf(int i);//顯示代號為i景點(diǎn)的名稱及信息

void printroad(int i,int j);//顯示景點(diǎn)i~j的最短路徑方案信息

void printdir(int i,int j);//顯示景點(diǎn)i到j(luò)的方向信息，如“向東100m，向南200m” VertexNode adjlist[MaxSize];//存放景點(diǎn)全部信息的 景點(diǎn)類數(shù)組 int vertexNum,arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù)

void Root(int p,int q);//遞歸尋找pq間的最短路徑

int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//創(chuàng)建Path和Dist分別存放兩點(diǎn)間最短路徑的前驅(qū)節(jié)點(diǎn)，兩點(diǎn)間最短路徑長度

int Line[MaxSize];//Line存放路徑 int kkk;//Line[]數(shù)組的標(biāo)記

private: T vertex[MaxSize];//存放圖中頂點(diǎn)的數(shù)組

int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 };*************************【以下為類的實(shí)現(xiàn) 即類函數(shù)的定義】*********************************** template MGraph::MGraph()//a[]為景點(diǎn)代號，b[]為景點(diǎn)名稱，c[]為景點(diǎn)信息，d[]為景點(diǎn)方位信息的橫坐標(biāo)，e[]為景點(diǎn)方位信息的縱坐標(biāo)

//s[]為存放景點(diǎn)鄰接矩陣信息的一維數(shù)組，根據(jù)其對稱性可以用公式賦值給二維數(shù)組arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char* b[]={“南門”,“實(shí)驗(yàn)樓”,“南圖”,“大活”,“睿思樓”,“大禮堂”, “南4教”,“知行樓”,“國交樓”,“南3教”,“南2教”,“南1教”, “北圖”,“北3教”,“北4教”,“北2教”,“北1教”,“北門”};char* c[]={“南校區(qū)正門”,“物理實(shí)驗(yàn)樓”,“南校區(qū)圖書館”,“大學(xué)生活動中心”, “教師辦公樓、醫(yī)務(wù)室及留學(xué)生公寓”,“大禮堂，用于舉辦各種文藝演出”,“南校區(qū)第4教學(xué)樓”,“實(shí)習(xí)基地，計(jì)算機(jī)房等”, “國際交流中心，教職工餐廳”,“南校區(qū)第3教學(xué)樓”,“南校區(qū)第2教學(xué)樓”,“南校區(qū)第1教學(xué)樓”, “北校區(qū)圖書館”,“北校區(qū)第3教學(xué)樓”,“北校區(qū)第4教學(xué)樓”,“北校區(qū)第2教學(xué)樓”, “北校區(qū)第1教學(xué)樓”,“北校區(qū)正門”};int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};int i,j;vertexNum=18;arcNum=30;

for(i=0;i

for(j=0;j void MGraph::printvexname(){ int i;for(i=0;i

template void MGraph::printvexinf(int i){ cout< void MGraph::printdir(int i,int j){ int dx,nb;//臨時(shí)存放i與j之間的南北東西關(guān)系 j在i的哪邊？？ dx=adjlist[j].dir.col-adjlist[i].dir.col;nb=adjlist[j].dir.ln-adjlist[i].dir.ln;if(dx>0)//即j在i的東邊

cout<<“向東”<0)//即j在i的南邊

cout<<“向南”< void MGraph::Root(int p,int q){

if(Path[p][q]>0){

Root(p,Path[p][q]);Root(Path[p][q],q);} else {

Line[kkk]=q;kkk++;} }

template void MGraph::printroad(int i,int j){ int p,q,m,k,item1,item2;for(p=0;p0)

for(q=0;q0)if(((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){

Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}

cout<<“n=======n”;cout<<“從”<”;printdir(i,item2);cout<<“-->”<”;printdir(item1-1,item1);cout<<“-->”<

{ int choice;cout<<“================”<>choice;return choice;} void main(){ MGraph mg;int funcchoice();int fc;while(1){ fc=funcchoice();if(fc==1){ int i;for(i=0;i>i;mg.printvexinf(i);} else if(fc==3){ int i,j;mg.printvexname();cout<<“請輸入兩景點(diǎn)代號（我們將把最短路線反饋予您）：”;cin>>i>>j;mg.printroad(i,j);} else if(fc==4)break;else cout<<“輸入有誤，請重新輸入！”<

【2】【停車場管理系統(tǒng)【方案一 程序】】

######

（ps：該程序有漏洞，若將要離開的車輛是停于便道上的，則對該車進(jìn)行駛離操作時(shí)程序內(nèi)部有錯誤數(shù)據(jù)，雖然做了函數(shù)完成這一功能，但因時(shí)間有限，沒能及時(shí)查找更正，現(xiàn)在懶得改了。。大家將就看吧。不過運(yùn)行是可以的）【問題描述】

設(shè)停車場是一個可停放n輛汽車的 長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車信放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場院，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序?！净疽蟆?/p>

以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時(shí)刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)?！緶y試數(shù)據(jù)】

設(shè)n=2，輸入數(shù)據(jù)為：(A，1，5)，（A，2，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到達(dá)（Arrival）；D表示離去（Departure）；E表示輸入結(jié)束（End）。**************************【以下為類的定義】************************************* #include using namespace std;const int Max=2;//車庫最大容量

const double price=30;//每小時(shí)的費(fèi)用 //思想：（報(bào)告第四頁）

//我的系統(tǒng)界面，輸入信息為：（到達(dá)/離開/退出）；車牌號；時(shí)刻 //因此，我的停車場類分成車輛到達(dá)和車輛離開兩個主要的函數(shù)實(shí)現(xiàn)。//車輛到達(dá)，有入棧和入隊(duì)。車輛離開有出棧，出隊(duì)和入棧操作。

//因此我又編寫入棧的類，隊(duì)的類。與parkingmanagement進(jìn)行友元。

//**************************************類定義*********************************************** class car//車的信息類

{ public: double time;//計(jì)費(fèi)時(shí)間 int number;//車牌號

car *next;//存放car類型元素的數(shù)組初始地址 };class carstack//棧（停車場）的類

{ friend class parkingmanagement;//parkingmanagement能訪問carstack類中所有成員 public: carstack();//構(gòu)造函數(shù)，棧的初始化 int empty();//判斷棧是否為空 int full();//判斷棧是否為滿

car *s;//存放car類型棧元素的數(shù)組初始地址 int top;//棧頂指針 };class carqueue//隊(duì)列（便道）的類

{ friend class parkingmanagement;//parkingmanagement能訪問carstack類中所有成員 public: carqueue();//構(gòu)造函數(shù)，隊(duì)列的初始化 int full();//判斷隊(duì)列是否為滿 car *front,*rear;//存放car類型隊(duì)列元素的數(shù)組初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入棧,cs棧內(nèi)進(jìn)行調(diào)整，返回棧內(nèi)位置 void popstack(carstack &cs,int cnum);//出棧，cs棧內(nèi)進(jìn)行調(diào)整，//根據(jù)車牌號把車彈出棧,將出棧car的number賦值給int popstacknumber()//將出棧car的time賦值給double popstacktime()，無返回值！

int pushqueue(carqueue &cq,int cnum,double ctime);//入隊(duì),隊(duì)內(nèi)進(jìn)行調(diào)整，返回隊(duì)內(nèi)位置 int popqueue(carqueue &cq);//出隊(duì),隊(duì)內(nèi)進(jìn)行調(diào)整，返回汽車車牌號

void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛到達(dá)，//根據(jù)輸入的車牌號、到達(dá)時(shí)間，變更函數(shù)參數(shù)；并cout車位信息

void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛離開，//根據(jù)輸入的車牌號找到汽車，并進(jìn)行出棧操作、出隊(duì)操作和入棧操作； //并cout停留時(shí)間和收費(fèi)情況

void deletequeue(carqueue &cq,int i);//刪除cq過道中第i輛車 int popstacknumber;//專門存放出棧的時(shí)候返回的車牌號 double popstacktime;//專門存放出棧的時(shí)候返回的時(shí)刻

};**********************************【以下為類的實(shí)現(xiàn)】************************************ carstack::carstack()//構(gòu)造函數(shù)，棧的初始化 { top=-1;s=new car[Max];//創(chuàng)建car類型棧元素的數(shù)組 if(s==NULL){ cout<<“?？臻g分配不成功！”<

cs.top++;(cs.s[cs.top]).number=cnum;//將cnum賦給棧頂位置的車的車牌號，s是car類型棧元素的數(shù)組(cs.s[cs.top]).time=ctime;//將ctime賦給棧頂位置的車的入棧時(shí)間，s是car類型棧元素的數(shù)組 return(cs.top+1);//返回棧內(nèi)位置加1，即停車場內(nèi)車位從1號開始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出棧，cs棧內(nèi)進(jìn)行調(diào)整，//根據(jù)車牌號把車彈出棧,將出棧car的number賦值給int popstacknumber //將出棧car的time賦值給double popstacktime，無返回值！{ int i;car p;carstack stemp;//定義一個carstack類型的臨時(shí)存放出棧元素的棧

for(i=0;i<=cs.top;i++)if((cs.s[i]).number==cnum)break;//當(dāng)要出棧的車的車牌號=棧內(nèi)的車牌號元素時(shí)，跳出循環(huán) p=cs.s[i];//將要出棧的元素賦給car類型的p存放

while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出棧的元素?cái)?shù)組逐個賦給臨時(shí)棧 popstacknumber=p.number;//將這個車牌號信息傳給int popstacknumber()popstacktime=p.time;//將該車的時(shí)間信息傳給double popstacktime()cs.top--;//棧頂指針回到原來位置

while(stemp.top>=0)cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//臨時(shí)棧出棧的元素逐個賦給原棧，完成先退再進(jìn)的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入隊(duì),隊(duì)內(nèi)進(jìn)行調(diào)整，返回隊(duì)內(nèi)位置 { car *p,*countp;int count(1);//count用于記錄車在過道上的位置信息，因隊(duì)列為鏈?zhǔn)降模赃M(jìn)行循環(huán)累加 p=new car;//創(chuàng)建一個car類型的指針

p->number=cnum;p->time=ctime;p->next=NULL;//首先將指向存放car類型元素的數(shù)組初始地址置空 if(cq.front==NULL)//第一次入隊(duì)要判斷頭結(jié)點(diǎn)是否為空 { cq.front=cq.rear=p;} else

{//尾插法插入元素 p->next=(cq.rear)->next;(cq.rear)->next=p;cq.rear=(cq.rear)->next;} countp=(cq.front)->next;while(countp!=NULL){ count++;countp=countp->next;}//count即車在過道上的位置，【從1開始計(jì)?。　?return count;} int parkingmanagement::popqueue(carqueue &cq)//出隊(duì),隊(duì)內(nèi)進(jìn)行調(diào)整，返回汽車車牌號

{ car p;p.number=((cq.front)->next)->number;//cq隊(duì)里，從cq.front開始指向下一個元素的車牌號賦給car類型的車信息 p.time=((cq.front)->next)->time;//cq隊(duì)里，從cq.front開始指向下一個元素的時(shí)刻 //賦給car類型的車信息

p.next=((cq.front)->next)->next;//cq隊(duì)里，從cq.front開始指向下一個元素的指針 //賦給car類型的車信息的下一個元素的指針 return p.number;cq.front=(cq.front)->next;} void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime)//車輛到達(dá)，根據(jù)輸入的車牌號、到達(dá)時(shí)間，變更函數(shù)參數(shù)；并cout車位信息 { int pos;if(!(cs.full()))//如果棧未滿，車輛停入停車場 { int fl(0),i;//定義一個從0開始的標(biāo)記fl for(i=0;i<=cs.top;i++){ if(cs.s[i].number==cnum)//如果到達(dá)的車的車牌號=棧內(nèi)已有車輛的車牌號 { fl=1;//fl記1 break;} } if(fl==1)//如果到達(dá)的車的車牌號!=棧內(nèi)已有車輛的車牌號 cout<<“輸入錯誤！請重新輸入！”<

cout<<“該停車場還有空位，請到”<

{ pos=pushqueue(cq,cnum,ctime);//入隊(duì)，返回車位信息

cout<<“該停車場已滿，請將車停到便道”<

{ popstack(cs,cnum);//出棧操作

hour=ctime-popstacktime;//時(shí)間計(jì)算

outcarnum=popqueue(cq);//將便道上的第一輛車出隊(duì)，入棧。并將其車牌號賦給outcarnum pstack=pushstack(cs,outcarnum,ctime);//將便道上的第一輛車，入棧

cout<<“該車在本停車場內(nèi)停留時(shí)間為”<

{ p=cq.front;while(p!=NULL){ count++;//如果在過道中找到該車，則該車的位置為過道中的第count位置（count從1開始）p=p->next;if(p->number==cnum)//在過道中找到要出去的車，則在隊(duì)列中刪除該car。//后面的車輛依然順序排列，補(bǔ)足空位

{ deletequeue(cq,count);if(count>Max){ cout<<“您的車在便道上的位置為”<

car *p,*q;int j(0);p=cq.front;while(p && jnext;j++;}//找到第i個節(jié)點(diǎn)(i從1開始)if(!p ||!p->next)cout<<“i不合法”;else { q=p->next;p->next=q->next;delete q;} } *******************************【以下是主程序】************************************ void print(){ cout<<“= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =”<>acc>>carnum>>cartime;if(acc=='A')park.arrival(cars,carq,carnum,cartime);else if(acc=='D')park.leave(cars,carq,carnum,cartime);else if(acc=='E')break;else cout<<“您的輸入有誤，請重新輸入！”<

######【3】【停車場管理系統(tǒng)【方案二 程序】】

（ps：本方案與方案一有同樣的問題，就是在對 便道上的車 進(jìn)行駛離操作時(shí)，數(shù)據(jù)錯誤，同樣的理由，沒有改正。如果有細(xì)心娃娃幫忙指點(diǎn)改正，在此感激啦~）

*************************【以下為類定義】************************************ #include using namespace std;const int MaxSize=2;//停車場內(nèi)最多能停2輛車 template class carStack;// template //定義模板類

struct Node//過道停車的隊(duì)列所需鏈?zhǔn)浇Y(jié)點(diǎn) { T carnum;//定義車牌號類型

Node *next;//此處也可以省略 };template class carinfo {

friend class carStack;public: T carnum;//車號

int cartime;//停車時(shí)間 };

template class carQueue { friend class carStack;public: carQueue();//構(gòu)造函數(shù)，初始化一個空的鏈隊(duì)列

int EnQueue(T cnum);//將元素x入隊(duì),并返回其在隊(duì)內(nèi)的位置（從1開始）T DeQueue();//將隊(duì)頭鏈?zhǔn)浇Y(jié)點(diǎn)出隊(duì),并返回汽車車牌號

void deletequeue(int i);//將隊(duì)內(nèi)低i個元素刪除，即便道上i位置的汽車駛離 bool Empty();//判斷鏈隊(duì)列是否為空 Node *front, *rear;};template class carStack { friend class carinfo;public: carStack();//構(gòu)造函數(shù)，棧的初始化,停車場容量為【size】 void Pushcar(T cnum,int ctime);//有車停入停車場

int Popcar(T outcnum,int outctime);//將第cnum輛車出棧，并返回其停車時(shí)間（hour）bool full();//判斷棧是否為滿？滿則返回1 carinfo *S;//?? int top;};******************************【以下為類的實(shí)現(xiàn)】**************************************** template //初始化隊(duì)列 carQueue::carQueue(){ front=rear=NULL;} template int carQueue::EnQueue(T cnum)//車子進(jìn)入便道 { int i(0);Node *s,*p;//？？

s=new Node;s->carnum=cnum;s->next=NULL;if(front==NULL)//空隊(duì)列，【【【新結(jié)點(diǎn)既是隊(duì)頭，又是隊(duì)尾】】】關(guān)鍵是！front指向第一個結(jié)點(diǎn) {

front=rear=s;} else {

rear->next=s;//將結(jié)點(diǎn)s插入到隊(duì)尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即車在過道上的位置，【從1開始計(jì)??！】 return i;}

template T carQueue::DeQueue(){ Node *p;if(front==NULL)cout<<“便道上沒車”;else { p=front;

front=front->next;//將隊(duì)頭元素所在結(jié)點(diǎn)摘鏈 } return p->carnum;delete p;//將出隊(duì)進(jìn)棧的車從隊(duì)列里刪除 }

template bool carQueue::Empty()//判斷是否為空，為空則返回1，不為空則返回0 { return front==NULL;}

template carStack::carStack()//構(gòu)造棧算法

:top(-1){//建立一個最大尺寸為size的空棧

S=new carinfo[MaxSize];//創(chuàng)建存儲棧的數(shù)組 if(S==NULL)//分配不成功

{ cerr<<“動態(tài)存儲失?。　?

template void carStack::Pushcar(T cnum,int ctime){ if(top==MaxSize-1)cout<<“車場內(nèi)已停滿汽車”;else { S[++top].carnum=cnum;S[top].cartime=ctime;} }

template int carStack::Popcar(T outcnum,int outctime){ int i,hour;carStack Stemp;//建一個臨時(shí)模擬停車場 int Stop=-1;for(i=0;i<=top;i++)if(outcnum==S[i].carnum)break;while(top>i)Stemp.S[++Stop]=S[top--];hour=outctime-S[top].cartime;return hour;top--;while(Stop>=0)S[++top]=Stemp.S[Stop--];} template bool carStack::full(){ return top==MaxSize-1;} template void carQueue::deletequeue(int i){ Node *p,*q;int j(1);p=front;while(p && jnext;j++;}//找到第i-1個結(jié)點(diǎn)(結(jié)點(diǎn)位置從1開始)if(!p||!p->next)cout<<“i不合法！”<next;p->next=q->next;delete q;} } ******************************【以下為主函數(shù)】***************************************

void outputpark()//系統(tǒng)功能選擇頁面，輸入泊車信息

{ cout<<“========================”< cs;carQueue cq;while(1){ outputpark();cin>>arrive>>carnum>>cartime;if(arrive=='A'){ if(cs.top!=MaxSize-1)//停車場內(nèi)有空位可以駛?cè)?/p>

{ cs.Pushcar(carnum,cartime);cout<<“請駛?cè)胪＼噲龅摹?

Node *p;p=cq.front;while(p!=NULL){ if(p->carnum==carnum){ flagde=1;break;} pos++;p=p->next;} if(flagde){ cout<<“您的車停在便道上”<

第五篇：數(shù)據(jù)結(jié)構(gòu)huffman編碼作業(yè)報(bào)告

哈夫曼編碼與解碼

一、設(shè)計(jì)思想

在設(shè)計(jì)本程序時(shí)，主要用到的算法有如下三個：

一、創(chuàng)建哈夫曼樹算法；

二、求哈夫曼編碼算法；

三、求哈夫曼解碼算法。? 創(chuàng)建哈夫曼樹算法如下：

1)存儲結(jié)構(gòu)：構(gòu)造由信息元素與對應(yīng)的權(quán)值組成的信息元素結(jié)構(gòu)體來存儲已給定的字母與其權(quán)重信息；構(gòu)造由信息元素、權(quán)值、當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成的哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)體來存儲樹結(jié)點(diǎn)的信息，還會很方便地幫助創(chuàng)建哈夫曼樹；構(gòu)造由信息元素與對應(yīng)的哈夫曼編碼結(jié)構(gòu)體來存儲哈夫曼編碼信息；方便進(jìn)行對數(shù)據(jù)的編碼。2)結(jié)構(gòu)體數(shù)組處理：哈夫曼樹沒有度為 1 的結(jié)點(diǎn)，若一個哈夫曼樹由 n 個葉子結(jié)點(diǎn)，則該哈夫曼樹共有2n-1個結(jié)點(diǎn)。應(yīng)用以上的原理，根據(jù)用戶輸入的信息元素的個數(shù)n開辟大小為2n-1的哈夫曼樹數(shù)組來滿足創(chuàng)建哈夫曼樹的需要，并對此數(shù)組進(jìn)行初始化，葉子結(jié)點(diǎn)的信息元素與權(quán)值即給定的的信息元素與權(quán)值；非葉子結(jié)點(diǎn)的信息元素與權(quán)值設(shè)置為空值；所有哈夫曼樹結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)設(shè)置為 0。

3)選擇權(quán)值最小與次?。涸谶M(jìn)行比較的過程中循環(huán)取出權(quán)值進(jìn)行比較，設(shè)置兩個s1，s2分別記錄本次循環(huán)最小與次小的權(quán)值，進(jìn)行下一次的比較選擇。返回權(quán)值最小與次小的哈夫曼樹結(jié)點(diǎn)信息。

4)生成小樹：應(yīng)用3)中想法，在用戶輸入的信息元素中選擇權(quán)值中最小與次小的元素分別賦值給右葉子結(jié)點(diǎn)與左葉子結(jié)點(diǎn)，并把這兩個權(quán)值之和賦值給這兩個結(jié)點(diǎn)的父結(jié)點(diǎn)，記錄父結(jié)點(diǎn)位置。

5)生成哈夫曼樹：再應(yīng)用3)4)把這些小樹的父結(jié)點(diǎn)的權(quán)值進(jìn)行比較選擇，選擇權(quán)值比較大的設(shè)置為新的右結(jié)點(diǎn)的權(quán)值，權(quán)值比較小的設(shè)置為左結(jié)點(diǎn)，把這兩個權(quán)值的和賦值給新的父結(jié)點(diǎn)；以此重復(fù)進(jìn)行，最終生成哈夫曼樹。? 求哈夫曼編碼算法如下

1)采用無棧非遞歸遍歷哈夫曼樹：每次站在根結(jié)點(diǎn)遍歷哈夫曼樹，直至到達(dá)某一個葉子結(jié)點(diǎn)為止，并臨時(shí)用一個數(shù)組記錄遍歷過程中每個結(jié)點(diǎn)的狀態(tài)。編碼完成后再復(fù)制給哈夫曼編碼結(jié)構(gòu)體中的編碼數(shù)組。

2)遍歷與編碼：在邏輯上，遍歷時(shí)向左子時(shí)，編碼為0，向右子為1，將每次的結(jié)點(diǎn)狀態(tài)記錄連接即哈夫曼編碼；站在根結(jié)點(diǎn)上，若到左子上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)為0，并把指針指向左子，進(jìn)行下一次的遍歷，若到右結(jié)點(diǎn)上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)1，并把指針指向右子，進(jìn)行下一次的判斷遍歷；重復(fù)進(jìn)行，到達(dá)某一個葉子結(jié)點(diǎn)為止，完畢后，將每次

哈夫曼編碼與解碼

下面是哈夫曼編碼過程的大致過程（如圖2）：

圖2 為huffman樹的各節(jié)點(diǎn)進(jìn)行編碼

下面是對指定文件內(nèi)信息編碼的大致過程（如圖3）：

圖3 信息的編碼

哈夫曼編碼與解碼

{

int j,k;/*找出第一個單節(jié)點(diǎn)樹*/

for(k=1;k<=i;k++)

{

if(ht[k].parent!=0)

{ } continue;

s1=k;

break;

} /*找出其中權(quán)重最小的樹*/

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

{

if(ht[j].parent!=0)

{ } { }

continue;

if(ht[j].weight

s1=j;

} /*找出第二個單節(jié)點(diǎn)樹*/

for(k=1;k<=i;k++)

{

if(ht[k].parent!=0||k==s1){ }

continue;

s2=k;

break;

} /*找出其中權(quán)重次小的樹*/

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

{

if(ht[j].parent!=0)

{ } {

continue;

if(ht[j].weight

s2=j;

哈夫曼編碼與解碼

cd[--Istart]='0';

} { }

else/*右1*/

cd[--Istart]='1';

hc[i]=(char *)malloc((n-Istart)*sizeof(char));

strcpy(hc[i], &cd[Istart]);/*將臨時(shí)儲存的code拷貝至hc中*/ }

}

free(cd);/*釋放cd*/ }

void main(){

char text[300];/*聲明儲存源碼或Huffman碼的臨時(shí)數(shù)組*/

int i,j,count,choice;/*儲存字母數(shù)組*/ /*儲存字母對應(yīng)權(quán)重的數(shù)組*/

char zi[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

int w[26]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};

huffmantree ht;

huffmancode hc;

HuffmanTree(ht,w,zi,26);/*生成huffman樹*/

huffmancoding(ht,hc,26);/*根據(jù)huffman樹生成huffman碼*/

FILE *fp;

printf(“[1]Encoding...n”);printf(“[2]Decoding...n”);scanf(“%d”,&choice);if(choice==1)/*1為編碼*/ {

char file[20];printf(“Please choice the file:”);/*輸入需要編碼的文件名*/ scanf(“%s”,file);printf(“******************從%s文件讀取字符串******************n”,file);if((fp=fopen(file,“r”))==NULL){ } fgets(text,300,fp);/*從文件中讀取字符串*/ fclose(fp);printf(“Source code is:”);/*輸出讀取的字符串*/ puts(text);printf(“cannot open this filen”);

printf(“Please choice function:”);/*選擇編碼還是譯碼*/

哈夫曼編碼與解碼

}

}

} printf(“n”);} /*顯示由部分電碼譯碼得到的字符，并準(zhǔn)備對后面的電碼進(jìn)行譯碼*/ printf(“%c”,ht[count].letter);count=51;

四、運(yùn)行結(jié)果

下圖是對SourceCode.txt文件信息進(jìn)行編碼，所得到的效果圖（如圖5所示）：

圖5 對SourceCode.txt文件進(jìn)行編碼

下圖是對CodeFile.txt文件中Huffman碼進(jìn)行譯碼，所得到的效果圖（如圖6所示）：

圖6 對CodeFile.txt文件中Huffman碼進(jìn)行譯碼