第一篇：數據結構作業
1.(1)問題的描述：設計一個程序exp1-1.cpp,輸出所有小于等于n(n為一個大于二的正整數)的素數。要求：（1）每行輸出10個素數;(2)盡可能采用較優的算法。
(2)解決思想：判斷一個整數n是否為素數，只需要用2~n-1之間的每一個整數去除，如果都不能被整除，那么m就是一個素數。其實可以簡化，n不被被2~n-1之間的每一個整數去除，只需被2~根號n之間的每個數去除就可以了。因為如果n能被2~n-1之間任意整數整除，如果這個數大于根號m，那這個數必定對應的還有一個比根號m小的因子(3)源代碼：
#include
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)運行結果截圖 (5)心得體會:按照素數定義來判斷素數時，可以進行一個較為明顯的優化，即只需從2枚舉到根n即可。 2.(1)問題的描述：編寫一個程序exp1-2.cpp,計算任一輸入的正整數的各位數字之和，并分析算法的時間復雜度。 (2)解決思想:采用遞歸的算法，對輸入的正整數進行不斷的取模運算和取商運算，即可得到該正整數的各位數字之和。時間復雜度為O(1)(3)源代碼 exp1-2.cpp #include return 0;} else return n%10 + fun(n/10);} int main(){ int n; cout<<”請輸入一個正整數:“; cin>>n; cout<<”各位數字之和是:“< (5)心得體會：當遇到一個復雜問題時，可以從最簡單的地方著手，剛開始不知道n是幾位數，感覺這個問題有點棘手，心想如果是二位數就好辦了，因此腦海中浮現了“遞歸”的思想，把一個復雜問題轉變成簡單問題。即把一個正整數n邊分解邊累加，直到分解完畢。 3.(1)問題的描述：編寫一個程序exp1-3.cpp,判斷一個字符串是否為“回文”(順讀和倒讀都一樣的字符串稱為“回文”)，并分析算法的時間復雜度。 (2)解決思想：依次將字符串兩端的字符進行比較，若都相同，則為回文字符串。時間復雜度為O(n)。(3)源代碼： exp1-3.cpp #include 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)心得體會：如果將這題進行擴展，判斷一個正整數是否為回文數，也可以采用類似的算法。將正整數的各位存到數組里，用i從左到右掃描s，用j從右到左掃描s,若s[i]與s[j]不相等，則退出循環，否則繼續比較，直到i 數據結構實驗報告二 題目： 用先序遞歸過程監理二叉樹（存儲結構：二叉鏈表） 輸入數據按先序遍歷輸入，當某節點左子樹或者右子樹為空時，輸入‘*’號，如輸入abc**d**e**時，得到的二叉樹為： 并用如下實力測試： 算法思路： 顯然，建立一個二叉鏈表存儲的二叉樹，如果不考慮效率要求，考慮到程序的簡介性，遞歸建立和遞歸遍歷是一種很好的辦法。 利用C++的類模板的方法實現建立，遍歷，輸出等二叉樹操作。首先利用構造函數實現先序遍歷建立二叉樹，然后調用類模板中已經聲明好的四種遍歷函數，將遍歷結果輸出，檢驗建立好的二叉樹是否為要求的二叉樹。 初始化：利用構造函數建立二叉樹。采用先序遞歸的調用方法，構造函數主體如下： template template root = new BiNode //生成一個結點 root->data=aa; root->lchild = Creat(); //遞歸建立左子樹 root->rchild = Creat(); //遞歸建立右子樹 } return root;} 構造這樣的函數，可以在輸入時，按先序遍歷順序每次輸入一個節點的數據，可以實現任意二叉樹的構造。 為了檢驗構造的二叉樹是否為預先設想的二叉樹，需要遍歷二叉樹并進行輸出?？紤]到單一的輸出并不能確定唯一的二叉樹，因此對遍歷二叉樹的四種常用發方法，即先序遍歷，中序遍歷，后續遍歷，層次遍歷分別實現，通過遍歷結果檢驗構造的二叉樹是否為預先設計好的二叉樹。 先序遍歷：采用遞歸的方法建立。template xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹 } 中序遍歷：遞歸方法建立： template if(root==NULL)return; //如果節點為空，則返回空 else{ zhongxu(root->lchild); //中序遞歸遍歷root的左子樹 cout< //訪問根結點 zhongxu(root->rchild); //中序遞歸遍歷root的右子樹 } } 后序遍歷：遞歸方法建立： template if(root==NULL) return; //如果節點為空，返回空 else{ houxu(root->lchild); //后序遞歸遍歷root的左子樹 houxu(root->rchild); //后序遞歸遍歷root的右子樹 cout< //訪問根節點 } } 層序遍歷：采用非遞歸方法。利用隊列的方法層序遍歷二叉樹。建立一個隊列，在訪問一個節點的時候，把它的左孩子和右孩子入隊，并且將這個節點出隊。當隊列為空時，就完成了對二叉樹的層序遍歷。 template Q[rear++] = root;// 若節點不為空，則該節點入隊 while(front!= rear) { q = Q[front++];//只要隊列不為空，則節點依次出隊 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同時，該節點的雙子入隊 } } } 函數主體部分：聲明一個類中的對象，調用構造函數，建立二叉樹，并輸出四種遍歷結果，檢驗輸出結果。 int main(){ BiTree BiNode cout<<“前序遍歷序列為 ”< 程序結構： 主函數建立一個類模板定義構造函數，析構函數，以及成員函數聲明類中的一個對象調用構造函數，構造一顆二叉樹層序遍歷二叉樹后序遍歷二叉樹中序遍歷二叉樹前序遍歷二叉樹獲取該二叉樹的根節點將結果輸出，人工檢驗 源代碼： #include template { T data; BiNode template { public: BiTree(); //構造函數，初始化一棵二叉樹 ~BiTree(void); //析構函數，釋放二叉鏈表中各結點的存儲空間 BiNode //獲得指向根結點的指針 void xianxu(BiNode //前序遍歷二叉樹 void zhongxu(BiNode //中序遍歷二叉樹 void houxu(BiNode //后序遍歷二叉樹 void cengxu(BiNode //層序遍歷二叉樹 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一個結點 root->data=aa; root->lchild = Creat(); //遞歸建立左子樹 root->rchild = Creat(); //遞歸建立右子樹 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹 } } template if(root==NULL)return; //如果節點為空，則返回空 else{ zhongxu(root->lchild); //中序遞歸遍歷root的左子樹 cout< //訪問根結點 zhongxu(root->rchild); //中序遞歸遍歷root的右子樹 } } template if(root==NULL) return; //如果節點為空，返回空 else{ houxu(root->lchild); //后序遞歸遍歷root的左子樹 houxu(root->rchild); //后序遞歸遍歷root的右子樹 cout< //訪問根節點 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用隊列的方法對樹進行層序遍歷 BiNode BiNode else{ Q[rear++] = root;// 若節點不為空，則該節點入隊 while(front!= rear) { q = Q[front++];//只要隊列不為空，則節點依次出隊 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同時，該節點的雙子入隊 } } } template if(root!= NULL){ Release(root->lchild); //釋放左子樹 Release(root->rchild); //釋放右子樹 delete root; } } int main(){ BiTree BiNode cout<<“前序遍歷序列為 ”< cout<<“層序遍歷序列為”< 通過對結果的分析，發現輸出結果與建立二叉樹時的輸入完全符合，說明程序的運行結果是正確的。 心得體會： 1)函數遞歸的方法可以在相當程度上使程序簡潔，避免代碼的冗長復雜。2)構造函數如果帶參數，在聲明對象的時候應該將實參指出來。但是本題中構造函數位遞歸調用，初始的根節點的數據值由鍵盤輸入，因此無法在聲明對象時引入實參。所以最后選擇了無參但是引用了this指針的構造函數?？梢?，對于構造函數的含參調用應該小心謹慎。 3)編程時，要不停得檢驗自己的輸入與輸出，必要的時候需要人工進行計算，以保證程序的運行按照預先的設想。 實驗一 線性表 一、實驗題 線性表的應用———多項式計算 二、程序設計思路 包括每個函數的功能說明，及一些重要函數的算法實現思路一鏈式存儲： 1.void InitPoly(LNode *&p)初始化多項式 2.void TraversePoly(LNode *&p)遍歷多項式 3.void ClearPoly(LNode *&p)清除多項式 4.void InsertPoly(LNode *&p, double a, int e)插入一項 5.void DeletetPoly(LNode *&p,int pos) 刪除一項 6.double PolySum(LNode *&p, double x) 多項式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2) 多項式相加 順序存儲： 1.void InitPoly1(SeqList &L)初始化多項式 2.void ClearPoly1(SeqList &L)清除多項式 3.void TraversePoly1(SeqList L) 遍歷多項式 4.bool InsertPoly1(SeqList &L, ElemType item)插入一項 5.double PolySum1(SeqList L,double x) 多項式求值 6.bool DeleteList1(SeqList &L,int pos) 刪除一項 7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多項式相加 三、源程序代碼 #include { 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)//多項式求值 { 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)//多項式相加 { 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->exp 輸出多項式 } void ClearPoly1(ListType &p)//清除多項式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多項式為空,刪除無效!”< 插入一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)//項式相加 { ListType p;InitPoly1(p);float coef; 多項式求多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;四實驗結果分析 五.心得體會 對于結構體的認識增加了，對于動態存儲也有了更多的認識，也是在不知不覺中提高了。 實驗二 字符串的操作 一、實驗題目——字符串的操作 二、程序設計思路 采用定長順序存儲表示，由用戶創建串s和串t，實現在串s中下標為pos的字符之前插入串t。 三、源程序代碼 #define MAXLEN 10 typedef struct { /*串結構定義*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*創建串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;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標為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];/*將下標為pos的字符后的元素往后移動t->len個長度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為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;i s->ch[i+pos]=t->ch[i]; /*將串t從下標為pos位置開始插入到串s*/ s->len=MAXLEN; } else /*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接從下標為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);} } 四、實驗結果 五、實驗體會 通過本次實驗，我加深了對串數據結構的理解。在串的定長順序存儲結構中，按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區。在存儲方式中，結點大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。 實驗三 一、實驗題目——非遞歸算法對二叉樹進行中前序遍歷 二、程序設計思路 創建一棵10個節點構造的完全二叉樹，并對其進行前、中、后序遍歷。 三、源程序代碼 #define STUDENT EType #define SType SType #define HeadEType int #include //定義數據結構類型 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){// 構造一個最大容量為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進s棧，返回進棧后的狀態值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 將s棧頂的值取至x中，返回出棧后的狀態值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//構造結點 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){// 聯接root，left, right所指的結點指針為二叉樹 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//節點指針進棧，以后回溯時在退棧 q=q->LChild;//指針指向剛剛被訪問的“根”節點的左子樹 } else //當左子樹為空時，利用堆棧回溯 if(!IsEmpty(S)) { Pop(S,ele);//退棧回溯 q=ele.ptr;//指針重新指向剛剛被訪問的“根”節點 q=q->RChild;//指針指向該回溯節點的右子樹 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ while(q)//找到最左邊的子樹 { ele.ptr=q; Push(S,ele);//指針非空時，將當前的“根”節點指針進棧，用于以后回溯 q=q->LChild;//指針繼續指向該“根”節點的左子樹 } if(!IsEmpty(S))//當左子樹為空時，進行退?；厮?/p> { Pop(S,ele);//從堆棧中回溯節點指針（節點還未訪問） q=ele.ptr; cout< q=q->RChild;//指針向回溯的節點右子樹推進 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產生一個空棧 while(q ||!IsEmpty(S)){ if(q)//找最左邊的子樹 { ele.ptr=q; ele.status=false;//進棧前標記為第一次進棧 Push(S,ele); q=q->LChild;//指針繼續向左推進 } else if(!IsEmpty(S))//直到左子樹為空時，退棧回溯 { Pop(S,ele);//從堆棧中彈出回溯節點（還未訪問） q=ele.ptr;//q指向當前回溯節點 if(ele.status)//判斷節點進棧標志，是否對其進行訪問 { cout< q=NULL;//將q設為空，為了繼續退棧 } else { ele.status=true;//改變回溯節點的進棧標記，以便再次進棧 Push(S,ele); q=q->RChild;//指針向該回溯節點的右孩子推進 } } } } //主函數 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]);//構造10個二叉樹節點 } //將節點鏈接域填值，構造一個二叉樹 //這里構造的是一棵有10個節點的完全二叉樹 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構造完畢 //***********對已構造的完全二叉樹進行前序非遞歸遍歷************// cout<<“對該二叉樹進行前序遍歷結果：”< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< //***********對已構造的完全二叉樹進行中序非遞歸遍歷************// cout< 四、實驗結果分析 五、實驗總結 二叉樹是一種非常重要的數據結構，很多其它數據結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現，非遞歸后序遍歷實現起來相對來說要難一點。 實驗四 一、實驗題目——深度優先算法實現圖的遍歷 二、程序設計思路 以鄰接矩陣或鄰接表為存儲結構，以用戶指定的頂點為起始點，實現無向連通圖的深度優先，并輸出遍歷的結點序列。首先，根據用戶輸入的頂點總數和邊數，構造無向圖，然后以用戶輸入的頂點為起始點，進行深度優先，并輸出遍歷的結果。 三、源程序代碼 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊列的定義及相關函數的實現 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;} } //創建圖 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點數和邊數:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”< cout<<“請輸入邊 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; //因為是無向圖，所以有兩次建立邊表的過程 } } //------------------------------深度優先遍歷 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優先遍歷 { cout<<“該圖的深度優先遍歷結果為:”< visit[i]=0;//全部初始化為0，即未訪問狀態 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根據字符查找序號 { m=i; DFS(G,i,visit); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< 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<<“該圖的廣度優先遍歷結果為:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //繼續訪問未被訪問的結點 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、實驗結果及分析 五、實驗總結 本次試驗采用的是鄰接表的方式實現圖的深度優先遍歷和。對于深度優先遍歷，主要是采用遞歸的方式。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數據的輸入有問題，結果當然也就不可能正確了。只有正確的輸入數據，建立圖，才能得出正確的遍歷結果。 C++/數據結構 大作業/課程設計——【校園導游咨詢】【停車場管理】娃娃們可以收著以后用 絕對純手工打造 內含類模塊/一維指針數組（謹以此程序供大家參考。運行結果后面有貼圖） 目錄 【1】校園導游咨詢 程序設計源代碼 及 截圖 【2】停車場管理——方案一 程序設計源代碼 及 截圖 【3】停車場管理——方案二 程序設計源代碼 及 截圖 【1】【【校園導游咨詢】】 ###### (ps:該校園導游咨詢系統沒有輸入值，所有信息是都在class MGraph的構造函數中傳輸的，且校園景點信息皆為【【上海電力學院】】景點信息。請大家注意，直接從文章copy到visual stutio中會出現中文字符，注意刪除，推薦大家在一行語句的分號后面，點出光標，按一下delete鍵，然后按一下enter鍵，完成visual stutio的自動對齊，這樣程序看起來一目了然，更易于操作和更改)【問題描述】 設計一個校園導游程序，為來訪的客人提供各種信息查詢服務?！净疽蟆?/p> (1)設計你所在學校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。(2)為來訪客人提供圖中任意景點相關信息的查詢。 (3)為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一個最短的簡單路徑?！具x作內容】 (6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結果能提供詳盡的導向信息。**************************【以下為類的定義】******************************** #include class direction;template { friend class MGraph direction dir;//存放頂點方位信息的direction類的dir。}; class direction { public: int ln;//存放在方向圖中的橫坐標，表示東西 int col;//存放在方向圖中的縱坐標，表示南北 };template { public: MGraph(); //構造函數，初始化具有n個頂點的圖 void printvexname();//顯示所有景點及景點代號 void printvexinf(int i);//顯示代號為i景點的名稱及信息 void printroad(int i,int j);//顯示景點i~j的最短路徑方案信息 void printdir(int i,int j);//顯示景點i到j的方向信息，如“向東100m，向南200m” VertexNode void Root(int p,int q);//遞歸尋找pq間的最短路徑 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//創建Path和Dist分別存放兩點間最短路徑的前驅節點，兩點間最短路徑長度 int Line[MaxSize];//Line存放路徑 int kkk;//Line[]數組的標記 private: T vertex[MaxSize];//存放圖中頂點的數組 int arc[MaxSize][MaxSize];//存放圖中邊的數組 };*************************【以下為類的實現 即類函數的定義】*********************************** template //s[]為存放景點鄰接矩陣信息的一維數組，根據其對稱性可以用公式賦值給二維數組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[]={“南門”,“實驗樓”,“南圖”,“大活”,“睿思樓”,“大禮堂”, “南4教”,“知行樓”,“國交樓”,“南3教”,“南2教”,“南1教”, “北圖”,“北3教”,“北4教”,“北2教”,“北1教”,“北門”};char* c[]={“南校區正門”,“物理實驗樓”,“南校區圖書館”,“大學生活動中心”, “教師辦公樓、醫務室及留學生公寓”,“大禮堂，用于舉辦各種文藝演出”,“南校區第4教學樓”,“實習基地，計算機房等”, “國際交流中心，教職工餐廳”,“南校區第3教學樓”,“南校區第2教學樓”,“南校區第1教學樓”, “北校區圖書館”,“北校區第3教學樓”,“北校區第4教學樓”,“北校區第2教學樓”, “北校區第1教學樓”,“北校區正門”};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 template cout<<“向東”< cout<<“向南”< if(Path[p][q]>0){ Root(p,Path[p][q]);Root(Path[p][q],q);} else { Line[kkk]=q;kkk++;} } template for(q=0;q Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;} cout<<“n=======n”;cout<<“從”< { int choice;cout<<“================”< 【2】【停車場管理系統【方案一 程序】】 ###### （ps：該程序有漏洞，若將要離開的車輛是停于便道上的，則對該車進行駛離操作時程序內部有錯誤數據，雖然做了函數完成這一功能，但因時間有限，沒能及時查找更正，現在懶得改了。。大家將就看吧。不過運行是可以的）【問題描述】 設停車場是一個可停放n輛汽車的 長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車信放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場院，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序?！净疽蟆?/p> 以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數據進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現，隊列以鏈表結構實現?！緶y試數據】 設n=2，輸入數據為：(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表示到達（Arrival）；D表示離去（Departure）；E表示輸入結束（End）。**************************【以下為類的定義】************************************* #include const double price=30;//每小時的費用 //思想：（報告第四頁） //我的系統界面，輸入信息為：（到達/離開/退出）；車牌號；時刻 //因此，我的停車場類分成車輛到達和車輛離開兩個主要的函數實現。//車輛到達，有入棧和入隊。車輛離開有出棧，出隊和入棧操作。 //因此我又編寫入棧的類，隊的類。與parkingmanagement進行友元。 //**************************************類定義*********************************************** class car//車的信息類 { public: double time;//計費時間 int number;//車牌號 car *next;//存放car類型元素的數組初始地址 };class carstack//棧（停車場）的類 { friend class parkingmanagement;//parkingmanagement能訪問carstack類中所有成員 public: carstack();//構造函數，棧的初始化 int empty();//判斷棧是否為空 int full();//判斷棧是否為滿 car *s;//存放car類型棧元素的數組初始地址 int top;//棧頂指針 };class carqueue//隊列（便道）的類 { friend class parkingmanagement;//parkingmanagement能訪問carstack類中所有成員 public: carqueue();//構造函數，隊列的初始化 int full();//判斷隊列是否為滿 car *front,*rear;//存放car類型隊列元素的數組初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入棧,cs棧內進行調整，返回棧內位置 void popstack(carstack &cs,int cnum);//出棧，cs棧內進行調整，//根據車牌號把車彈出棧,將出棧car的number賦值給int popstacknumber()//將出棧car的time賦值給double popstacktime()，無返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);//入隊,隊內進行調整，返回隊內位置 int popqueue(carqueue &cq);//出隊,隊內進行調整，返回汽車車牌號 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛到達，//根據輸入的車牌號、到達時間，變更函數參數；并cout車位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛離開，//根據輸入的車牌號找到汽車，并進行出棧操作、出隊操作和入棧操作； //并cout停留時間和收費情況 void deletequeue(carqueue &cq,int i);//刪除cq過道中第i輛車 int popstacknumber;//專門存放出棧的時候返回的車牌號 double popstacktime;//專門存放出棧的時候返回的時刻 };**********************************【以下為類的實現】************************************ carstack::carstack()//構造函數，棧的初始化 { top=-1;s=new car[Max];//創建car類型棧元素的數組 if(s==NULL){ cout<<“?？臻g分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//將cnum賦給棧頂位置的車的車牌號，s是car類型棧元素的數組(cs.s[cs.top]).time=ctime;//將ctime賦給棧頂位置的車的入棧時間，s是car類型棧元素的數組 return(cs.top+1);//返回棧內位置加1，即停車場內車位從1號開始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出棧，cs棧內進行調整，//根據車牌號把車彈出棧,將出棧car的number賦值給int popstacknumber //將出棧car的time賦值給double popstacktime，無返回值！{ int i;car p;carstack stemp;//定義一個carstack類型的臨時存放出棧元素的棧 for(i=0;i<=cs.top;i++)if((cs.s[i]).number==cnum)break;//當要出棧的車的車牌號=棧內的車牌號元素時，跳出循環 p=cs.s[i];//將要出棧的元素賦給car類型的p存放 while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出棧的元素數組逐個賦給臨時棧 popstacknumber=p.number;//將這個車牌號信息傳給int popstacknumber()popstacktime=p.time;//將該車的時間信息傳給double popstacktime()cs.top--;//棧頂指針回到原來位置 while(stemp.top>=0)cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//臨時棧出棧的元素逐個賦給原棧，完成先退再進的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入隊,隊內進行調整，返回隊內位置 { car *p,*countp;int count(1);//count用于記錄車在過道上的位置信息，因隊列為鏈式的，所以進行循環累加 p=new car;//創建一個car類型的指針 p->number=cnum;p->time=ctime;p->next=NULL;//首先將指向存放car類型元素的數組初始地址置空 if(cq.front==NULL)//第一次入隊要判斷頭結點是否為空 { 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開始計?。 ?return count;} int parkingmanagement::popqueue(carqueue &cq)//出隊,隊內進行調整，返回汽車車牌號 { car p;p.number=((cq.front)->next)->number;//cq隊里，從cq.front開始指向下一個元素的車牌號賦給car類型的車信息 p.time=((cq.front)->next)->time;//cq隊里，從cq.front開始指向下一個元素的時刻 //賦給car類型的車信息 p.next=((cq.front)->next)->next;//cq隊里，從cq.front開始指向下一個元素的指針 //賦給car類型的車信息的下一個元素的指針 return p.number;cq.front=(cq.front)->next;} void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime)//車輛到達，根據輸入的車牌號、到達時間，變更函數參數；并cout車位信息 { int pos;if(!(cs.full()))//如果棧未滿，車輛停入停車場 { int fl(0),i;//定義一個從0開始的標記fl for(i=0;i<=cs.top;i++){ if(cs.s[i].number==cnum)//如果到達的車的車牌號=棧內已有車輛的車牌號 { fl=1;//fl記1 break;} } if(fl==1)//如果到達的車的車牌號!=棧內已有車輛的車牌號 cout<<“輸入錯誤！請重新輸入！”< cout<<“該停車場還有空位，請到”< { pos=pushqueue(cq,cnum,ctime);//入隊，返回車位信息 cout<<“該停車場已滿，請將車停到便道”< { popstack(cs,cnum);//出棧操作 hour=ctime-popstacktime;//時間計算 outcarnum=popqueue(cq);//將便道上的第一輛車出隊，入棧。并將其車牌號賦給outcarnum pstack=pushstack(cs,outcarnum,ctime);//將便道上的第一輛車，入棧 cout<<“該車在本停車場內停留時間為”< { p=cq.front;while(p!=NULL){ count++;//如果在過道中找到該車，則該車的位置為過道中的第count位置（count從1開始）p=p->next;if(p->number==cnum)//在過道中找到要出去的車，則在隊列中刪除該car。//后面的車輛依然順序排列，補足空位 { deletequeue(cq,count);if(count>Max){ cout<<“您的車在便道上的位置為”< car *p,*q;int j(0);p=cq.front;while(p && j ######【3】【停車場管理系統【方案二 程序】】 （ps：本方案與方案一有同樣的問題，就是在對 便道上的車 進行駛離操作時，數據錯誤，同樣的理由，沒有改正。如果有細心娃娃幫忙指點改正，在此感激啦~） *************************【以下為類定義】************************************ #include struct Node//過道停車的隊列所需鏈式結點 { T carnum;//定義車牌號類型 Node friend class carStack;public: T carnum;//車號 int cartime;//停車時間 }; template int EnQueue(T cnum);//將元素x入隊,并返回其在隊內的位置（從1開始）T DeQueue();//將隊頭鏈式結點出隊,并返回汽車車牌號 void deletequeue(int i);//將隊內低i個元素刪除，即便道上i位置的汽車駛離 bool Empty();//判斷鏈隊列是否為空 Node int Popcar(T outcnum,int outctime);//將第cnum輛車出棧，并返回其停車時間（hour）bool full();//判斷棧是否為滿？滿則返回1 carinfo s=new Node front=rear=s;} else { rear->next=s;//將結點s插入到隊尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即車在過道上的位置，【從1開始計！！】 return i;} template front=front->next;//將隊頭元素所在結點摘鏈 } return p->carnum;delete p;//將出隊進棧的車從隊列里刪除 } template template :top(-1){//建立一個最大尺寸為size的空棧 S=new carinfo { cerr<<“動態存儲失?。 ? template template void outputpark()//系統功能選擇頁面，輸入泊車信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“請駛入停車場的”< Node 哈夫曼編碼與解碼 一、設計思想 在設計本程序時，主要用到的算法有如下三個： 一、創建哈夫曼樹算法； 二、求哈夫曼編碼算法； 三、求哈夫曼解碼算法。? 創建哈夫曼樹算法如下： 1)存儲結構：構造由信息元素與對應的權值組成的信息元素結構體來存儲已給定的字母與其權重信息；構造由信息元素、權值、當前結點的父結點、左結點、右結點組成的哈夫曼樹結點結構體來存儲樹結點的信息，還會很方便地幫助創建哈夫曼樹；構造由信息元素與對應的哈夫曼編碼結構體來存儲哈夫曼編碼信息；方便進行對數據的編碼。2)結構體數組處理：哈夫曼樹沒有度為 1 的結點，若一個哈夫曼樹由 n 個葉子結點，則該哈夫曼樹共有2n-1個結點。應用以上的原理，根據用戶輸入的信息元素的個數n開辟大小為2n-1的哈夫曼樹數組來滿足創建哈夫曼樹的需要，并對此數組進行初始化，葉子結點的信息元素與權值即給定的的信息元素與權值；非葉子結點的信息元素與權值設置為空值；所有哈夫曼樹結點的父結點、左結點、右結點設置為 0。 3)選擇權值最小與次?。涸谶M行比較的過程中循環取出權值進行比較，設置兩個s1，s2分別記錄本次循環最小與次小的權值，進行下一次的比較選擇。返回權值最小與次小的哈夫曼樹結點信息。 4)生成小樹：應用3)中想法，在用戶輸入的信息元素中選擇權值中最小與次小的元素分別賦值給右葉子結點與左葉子結點，并把這兩個權值之和賦值給這兩個結點的父結點，記錄父結點位置。 5)生成哈夫曼樹：再應用3)4)把這些小樹的父結點的權值進行比較選擇，選擇權值比較大的設置為新的右結點的權值，權值比較小的設置為左結點，把這兩個權值的和賦值給新的父結點；以此重復進行，最終生成哈夫曼樹。? 求哈夫曼編碼算法如下 1)采用無棧非遞歸遍歷哈夫曼樹：每次站在根結點遍歷哈夫曼樹，直至到達某一個葉子結點為止，并臨時用一個數組記錄遍歷過程中每個結點的狀態。編碼完成后再復制給哈夫曼編碼結構體中的編碼數組。 2)遍歷與編碼：在邏輯上，遍歷時向左子時，編碼為0，向右子為1，將每次的結點狀態記錄連接即哈夫曼編碼；站在根結點上，若到左子上記錄此時的結點狀態為0，并把指針指向左子，進行下一次的遍歷，若到右結點上記錄此時的結點狀態1，并把指針指向右子，進行下一次的判斷遍歷；重復進行，到達某一個葉子結點為止，完畢后，將每次 哈夫曼編碼與解碼 下面是哈夫曼編碼過程的大致過程（如圖2）： 圖2 為huffman樹的各節點進行編碼 下面是對指定文件內信息編碼的大致過程（如圖3）： 圖3 信息的編碼 哈夫曼編碼與解碼 { int j,k;/*找出第一個單節點樹*/ for(k=1;k<=i;k++) { if(ht[k].parent!=0) { } continue; s1=k; break; } /*找出其中權重最小的樹*/ for(j=1;j<=i;j++) { if(ht[j].parent!=0) { } { } continue; if(ht[j].weight s1=j; } /*找出第二個單節點樹*/ for(k=1;k<=i;k++) { if(ht[k].parent!=0||k==s1){ } continue; s2=k; break; } /*找出其中權重次小的樹*/ 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]);/*將臨時儲存的code拷貝至hc中*/ } } free(cd);/*釋放cd*/ } void main(){ char text[300];/*聲明儲存源碼或Huffman碼的臨時數組*/ int i,j,count,choice;/*儲存字母數組*/ /*儲存字母對應權重的數組*/ 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);/*根據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”);} /*顯示由部分電碼譯碼得到的字符，并準備對后面的電碼進行譯碼*/ printf(“%c”,ht[count].letter);count=51; 四、運行結果 下圖是對SourceCode.txt文件信息進行編碼，所得到的效果圖（如圖5所示）： 圖5 對SourceCode.txt文件進行編碼 下圖是對CodeFile.txt文件中Huffman碼進行譯碼，所得到的效果圖（如圖6所示）： 圖6 對CodeFile.txt文件中Huffman碼進行譯碼第二篇：數據結構作業——二叉樹
第三篇：數據結構上機作業
第四篇：C++數據結構 大作業課程設計
第五篇：數據結構huffman編碼作業報告
點擊咨詢 