第一篇：數(shù)據(jù)結(jié)構(gòu)(c++版)實驗參考書
前 言
《數(shù)據(jù)結(jié)構(gòu)》是計算機及相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校考研專業(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計能力及良好的程序設(shè)計習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的存儲方案，設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實驗是兩個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機實驗是最佳的途徑之一。因此，實驗環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實驗，特編寫實驗指導(dǎo)書。
一、實驗?zāi)康?/p>
更好的理解算法的思想、培養(yǎng)編程能力。
二、實驗要求
1、每次實驗前學(xué)生必須根據(jù)試驗內(nèi)容認真準備實驗程序及調(diào)試時所需的輸入數(shù)據(jù)。
2、在指導(dǎo)教師的幫助下能夠完成實驗內(nèi)容，得出正確的實驗結(jié)果。
3、實驗結(jié)束后總結(jié)實驗內(nèi)容、書寫實驗報告。
4、遵守實驗室規(guī)章制度、不缺席、按時上、下機。
5、實驗學(xué)時內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機資格，平時成績扣10分。
6、實驗報告有一次不合格，扣5分，兩次以上不合格者，平時成績以零分記。
三、實驗環(huán)境 Qt或 VC++6.0
四、說明
1、本實驗的所有算法中元素類型可以根據(jù)實際需要選擇。
2、實驗題目中帶＊者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實驗不合格）。
3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準備。
五、實驗報告的書寫要求
1．明確實驗的目的及要求；
2．記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果；
3．說明實驗中出現(xiàn)的問題和解決過程；
4．寫出實驗的體會和實驗過程中沒能解決的問題；
六、參考書目
《數(shù)據(jù)結(jié)構(gòu)》（C++語言描述）王紅梅等 清華大學(xué)出版社
《DATA STRUCTURE WITH C++》 William Ford,William Topp 清華大學(xué)出版社（影印版）
實驗一 線性表的操作
實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時
一、實驗?zāi)康模?/p>
參照給定的線性表順序表類和鏈表類的程序樣例，驗證給出的線性表的常見算法。
二、實驗要求：
1、掌握線性表順序表類和鏈表類的特點。掌握線性表的常見算法。
2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。
三、實驗內(nèi)容：
1．設(shè)計一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類，要求編程實現(xiàn)如下任務(wù)：建立一個線性表，首先依次輸人數(shù)據(jù)元素1，2，3，?，10，然后刪除數(shù)據(jù)元素6，最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過50個。
2．設(shè)計一個帶頭結(jié)點的單鏈表類，要求：
(1)生成一個整數(shù)線性表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。
(2)設(shè)計一個測試主函數(shù)，實際運行驗證所設(shè)計單鏈表類的正確性。3．設(shè)計一個不帶頭結(jié)點的單鏈表類，要求：
(1)不帶頭結(jié)點單鏈表類的成員函數(shù)包括取數(shù)據(jù)元素個數(shù)、插入元素、刪除所有值為k的元素、取數(shù)據(jù)元素。
(提示：要考慮在第一個數(shù)據(jù)元素結(jié)點前插入和刪除第一個數(shù)據(jù)元素結(jié)點時與在其他位置插入和刪除其他位置結(jié)點時的不同情況。)(2)設(shè)計一個測試主函數(shù)，實際運行驗證所設(shè)計循環(huán)單鏈表類的正確性。4．設(shè)計一個帶頭結(jié)點的循環(huán)單鏈表類，實現(xiàn)約瑟夫環(huán)問題；
問題描述：設(shè)編號為1,2,?，n(n>0)個人按順時針方向圍坐-圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m從第一個人開始順時針方向自1起順序報數(shù)。報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù).如此下去，直到所有人全部出列為止。要求設(shè)計一個程序模擬此過程，并給出出列人的編號序列。
測試數(shù)據(jù)：
n=7,7個人的密碼依次為3,1,7,2,4,8,4 初始報數(shù)上限值m=20 *5．設(shè)計一個帶頭結(jié)點的循環(huán)雙向鏈表類，要求：
(1)帶頭結(jié)點循環(huán)雙向鏈表類的成員函數(shù)包括：取數(shù)據(jù)元素個數(shù)、插入、刪除、取數(shù)據(jù)元素。
(2)設(shè)計一個測試主函數(shù)，實際運行驗證所設(shè)計循環(huán)雙向鏈表類的正確性。*6．設(shè)計一個單鏈表實現(xiàn)一元多項式求和問題。要求：
（1）設(shè)計存儲結(jié)構(gòu)表示一元多項式；
（2）設(shè)計算法實現(xiàn)一元多項式相加。
四、程序樣例
順序表類定義：將該類保存在文件SeqList.h中。
const int MaxSize=100;//100只是示例性的數(shù)據(jù)，可根據(jù)實際問題具體定義 template
//定義模板類SeqList class SeqList { public:
SeqList(){length=0;}
//無參構(gòu)造函數(shù)
SeqList(T a[ ], int n);
//有參構(gòu)造函數(shù)
~SeqList(){ }
//析構(gòu)函數(shù)為空
int Length(){return length;} //求線性表的長度
T Get(int i);
//按位查找，取線性表的第i個元素
int Locate(T x);
//按值查找，求線性表中值為x的元素序號
void Insert(int i, T x);//在線性表中第i個位置插入值為x的元素
T Delete(int i);
//刪除線性表的第i個元素
void PrintList();
//遍歷線性表，按序號依次輸出各元素 private:
T data[MaxSize];
//存放數(shù)據(jù)元素的數(shù)組
int length;
//線性表的長度 };template
SeqList:: SeqList(T a[ ], int n){
if(n>MaxSize)throw “參數(shù)非法”;
for(i=0;i data[i]=a[i]; length=n;} template T SeqList::Get(int i){ if(i<1 && i>length)throw “查找位置非法”; else return data[i-1];} template int SeqList::Locate(T x){ for(i=0;i if(data[i]==x)return i+1;//下標為i的元素等于x，返回其序號i+return 0; //退出循環(huán)，說明查找失敗 } template void SeqList::Insert(int i, T x){ if(length>=MaxSize)throw “上溢”; if(i<1 | | i>length+1)throw “位置”;for(j=length;j>=i;j--) data[j]=data[j-1]; //注意第j個元素存在數(shù)組下標為j-1處 data[i-1]=x;length++;} template T SeqList::Delete(int i){ if(length==0)throw “下溢”; if(i<1 | | i>length)throw “位置”; x=data[i-1]; for(j=i;j data[j-1]=data[j]; //注意此處j已經(jīng)是元素所在的數(shù)組下標 length--; return x;} 鏈表類定義：將該類保存在文件LinkList.h中。template T data; Node } template LinkList(T a[ ], int n);//建立有n個元素的單鏈表 ~LinkList(); //析構(gòu)函數(shù) int Length(); //求單鏈表的長度 T Get(int i); //取單鏈表中第i個結(jié)點的元素值 int Locate(T x); //求單鏈表中值為x的元素序號 void Insert(int i, T x); //在單鏈表中第i個位置插入元素值為x的結(jié)點 T Delete(int i); //在單鏈表中刪除第i個結(jié)點 void PrintList(); //遍歷單鏈表，按序號依次輸出各元素 private: Node LinkList:: ~LinkList(){ p=first; //工作指針p初始化 while(p) //釋放單鏈表的每一個結(jié)點的存儲空間 { q=p; //暫存被釋放結(jié)點 p=p->next;//工作指針p指向被釋放結(jié)點的下一個結(jié)點，使單鏈表不斷開 delete q; } } template T LinkList::Get(int i) { p=first->next;j=1;//或p=first;j=0; while(p && j { p=p->next; //工作指針p后移 j++; } if(!p)throw “位置”;else return p->data; } template void LinkList::Insert(int i, T x) { p=first;j=0; //工作指針p初始化 while(p && j //工作指針p后移 j++;} if(!p)throw “位置”;else { s=new Node s->next=p->next; //將結(jié)點s插入到結(jié)點p之后 p->next=s;} } template T LinkList::Delete(int i){ p=first;j=0;//工作指針p初始化 while(p && j //查找第i-1個結(jié)點 { p=p->next; j++; } if(!p | |!p->next)throw “位置”;//結(jié)點p不存在或結(jié)點p的后繼結(jié)點不存在 else { q=p->next;x=q->data;//暫存被刪結(jié)點 p->next=q->next;//摘鏈 delete q; return x;} } template LinkList:: LinkList(T a[ ], int n) { first=new Node first->next=NULL;//初始化一個空鏈表 for(i=0;i s=new Node s->next=first->next; //插入到頭結(jié)點之后 first->next=s; } } template LinkList:: LinkList(T a[ ], int n) { first=new Node //生成頭結(jié)點 r=first; //尾指針初始化 for(i=0;i { s=new Node r->next=s;r=s; //插入到終端結(jié)點之后 } r->next=NULL; //單鏈表建立完畢，將終端結(jié)點的指針域置空 } 1．#include #include void main() { int r[ ]={1,2,3,4,5,6,7,8,9,10}; SeqList cout<<”執(zhí)行刪除操作前數(shù)據(jù)為：”< a.PrintList(); a.Delete(6); cout<<”執(zhí)行刪除操作后數(shù)據(jù)為：”< } 2． #include #include void divid(LinkList &L) { Node h=new Node p=L.first->next;q=L.first; while(p) { if(p->data%2!=0){ q=p;p=p->next;} else {q=p;p=p->next;q-next=h.first->next;h.first->next=q;} } p=L.first->next; while(p->next!=Null) {p=p->next;} p->next= h.first->next; delete h; } void main() { int r[ ]={1,-2,3,-4,-5,6,-7,8,9,10}; LinkList cout<<”執(zhí)行操作前數(shù)據(jù)為：”< List.PrintList(); divid(List); cout<<”執(zhí)行操作后數(shù)據(jù)為：”< 6．void Add(LinkList if(p->exp //第1種情況 pre=p; p=p->next; } else if(p->exp>q->exp){ //第2種情況，將結(jié)點q插入到結(jié)點p之前 v=q->next; pre->next=q; q->next=p; q=v; } else { //第3種情況 p->coef =p->coef+q->coef;//系數(shù)相加 if(p->coef ==0){ //系數(shù)為0，刪除結(jié)點p和結(jié)點q pre->next=p->next;//刪除結(jié)點p delete p; p=pre->next; } else { //系數(shù)不為0，只刪除結(jié)點q pre=p; p=p->next; } qre->next=q->next //刪除結(jié)點q delete q; q=qre->next;} if(q)pre->next=q;//將結(jié)點q鏈接在第一個單鏈表的后面 delete B.first; //釋放第二個單鏈表的頭結(jié)點所占的內(nèi)存 } 實驗二 棧、隊列、串的操作 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模?/p> 參照給定的棧類和隊列類的程序樣例，驗證給出的棧和隊列的常見算法，并結(jié)合線性表類實現(xiàn)有關(guān)串的操作。 二、實驗要求： 1、掌握棧、隊列、串的特點。掌握特殊線性表的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 1.堆棧類測試和應(yīng)用問題。要求： (1)設(shè)計一個主函數(shù)實現(xiàn)對順序堆棧類和鏈式堆棧類代碼進行測試。測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入棧，然后出棧堆棧中的數(shù)據(jù)元素并在屏幕上顯示。 (2)定義數(shù)據(jù)元素的數(shù)據(jù)類型為如下形式的結(jié)構(gòu)體： typedef struct { char taskname[10];//任務(wù)名 int taskno; //任務(wù)號 ｝DataType； 設(shè)計一個包含5個數(shù)據(jù)元素的測試數(shù)據(jù)，并設(shè)計一個主函數(shù)實現(xiàn)依次把5個數(shù)據(jù)元素入棧，然后出棧堆棧中的數(shù)據(jù)元素并在屏幕上顯示。2.隊列類測試和應(yīng)用問題。要求： 設(shè)計一個主函數(shù)對循環(huán)隊列類和鏈式隊列類代碼進行測試.測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入隊，然后出隊中的數(shù)據(jù)元素并在屏幕上顯示。3．設(shè)計串采用順序存儲結(jié)構(gòu)，編寫函數(shù)實現(xiàn)兩個串的比較Compare(S, T)。要求比較結(jié)果有大于、等于和小于三種情況。 *4.設(shè)計算法利用棧類實現(xiàn)把十進制整數(shù)轉(zhuǎn)換為二至九進制之間的任一進制輸出。*5.設(shè)計串采用靜態(tài)數(shù)組存儲結(jié)構(gòu)，編寫函數(shù)實現(xiàn)串的替換Replace(S, start, T, V)，即要求在主串S中，從位置start開始查找是否存在子串T，若主串S中存在子串T，則用子串V替換子串T，且函數(shù)返回1；若主串S中不存在子串T，則函數(shù)返回０。并要求設(shè)計主函數(shù)進行測試。 一個測試例子為：S＝”I am a student”，T=”student”，V=”teacher “。 四、程序樣例 1． 順序棧類的定義 const int StackSize=10; //10只是示例性的數(shù)據(jù)，可以根據(jù)實際問題具體定義 template //定義模板類SeqStack class SeqStack { public: SeqStack(){top=-1;} //構(gòu)造函數(shù)，棧的初始化 ~SeqStack(){ } //析構(gòu)函數(shù) void Push(T x); //將元素x入棧 T Pop(); //將棧頂元素彈出 T GetTop(){if(top!=-1)return data[top];} //取棧頂元素（并不刪除） bool Empty(){top==-1? return 1: return 0;} //判斷棧是否為空 private: T data[StackSize];//存放棧元素的數(shù)組 int top; //棧頂指針，指示棧頂元素在數(shù)組中的下標 };template if(top== StackSize-1)throw “上溢”; top++; data[top]=x; } template if(top==-1)throw “下溢”; x=data[top--]; return x; } 2． 鏈式棧類的定義 template LinkStack(){top=NULL;} //構(gòu)造函數(shù)，置空鏈棧 ~LinkStack(); //析構(gòu)函數(shù)，釋放鏈棧中各結(jié)點的存儲空間 void Push(T x); //將元素x入棧 T Pop(); //將棧頂元素出棧 T GetTop(){if(top!=NULL)return top->data;} //取棧頂元素（并不刪除） bool Empty(){top==NULL? return 1: return 0;} //判斷鏈棧是否為空棧 private: Node template void LinkStack::Push(T x) { s=new Node s->next=top;top=s; //將結(jié)點s插在棧頂 } template T LinkStack::Pop() { if(top==NULL)throw “下溢”; x=top->data; //暫存棧頂元素 p=top;top=top->next; //將棧頂結(jié)點摘鏈 delete p; return x; } template LinkStack::~LinkStack() { while(top){ p=top->next; delete top; top=p;} } 3．雙棧類的定義 const int StackSize=100;//100只是示例數(shù)據(jù)，需根據(jù)具體問題定義 template BothStack(){top1=-1;top2=StackSize;} //構(gòu)造函數(shù)，將兩個棧分別初始化 ~BothStack(){ } //析構(gòu)函數(shù) void Push(int i, T x); //將元素x壓入棧i T Pop(int i); //對棧i執(zhí)行出棧操作 T GetTop(int i); //取棧i的棧頂元素 bool Empty(int i); //判斷棧i是否為空棧 private: T data[StackSize]; //存放兩個棧的數(shù)組 int top1, top2; //兩個棧的棧頂指針，分別指向各自的棧頂元素在數(shù)組中的下標 };template //將棧1的棧頂元素出棧 if(top1==-1)throw “下溢”; return data[top1--]; } if(i==2){ //將棧2的棧頂元素出棧 if(top2==StackSize)throw ''下溢“; return data[top2++]; } } 4.循環(huán)隊列類定義 const int QueueSize=100;//定義存儲隊列元素的數(shù)組的最大長度 template //定義模板類CirQueue class CirQueue { public: CirQueue(){front=rear=0;} //構(gòu)造函數(shù)，置空隊 ~ CirQueue(){ } //析構(gòu)函數(shù) void EnQueue(T x); //將元素x入隊 T DeQueue(); //將隊頭元素出隊 T GetQueue(); //取隊頭元素（并不刪除） bool Empty(){front==rear? return 1: return 0;} //判斷隊列是否為空 private: T data[QueueSize]; //存放隊列元素的數(shù)組 int front, rear; //隊頭和隊尾指針，分別指向隊頭元素的前一個位置和隊尾元素的位置 }; template { if((rear+1)% QueueSize ==front)throw ”上溢“; rear=(rear+1)% QueueSize; //隊尾指針在循環(huán)意義下加 1data[rear]=x; //在隊尾處插入元素 } template T CirQueue::GetQueue() { if(rear==front)throw ”下溢“; i=(front+1)% QueueSize;//注意不要給隊頭指針賦值 return data[i]; } template if(rear==front)throw ”下溢“; front=(front+1)% QueueSize; //隊頭指針在循環(huán)意義下加1 return data[front]; //讀取并返回出隊前的隊頭元素，注意隊頭指針 } 5.鏈隊列類定義 template LinkQueue(); //構(gòu)造函數(shù)，初始化一個空的鏈隊列 ~LinkQueue(); //析構(gòu)函數(shù)，釋放鏈隊列中各結(jié)點的存儲空間 void EnQueue(T x); //將元素x入隊 T DeQueue(); //將隊頭元素出隊 T GetQueue(){if(front!=rear)return front->next->data;} //取鏈隊列的隊頭元素 bool Empty(){front==rear? return 1: return 0;} //判斷鏈隊列是否為空 private: Node T LinkQueue::DeQueue(){ if(rear==front)throw ”下溢“;p=front->next;x=p->data; //暫存隊頭元素 front->next=p->next; //將隊頭元素所在結(jié)點摘鏈 if(p->next==NULL)rear=front;//判斷出隊前隊列長度是否為1 delete p; return x;} template LinkQueue::LinkQueue(){ s=new Node front=rear=s; //將隊頭指針和隊尾指針都指向頭結(jié)點s } template void LinkQueue::EnQueue(T x) { s=new Node s->next=NULL; rear->next=s; //將結(jié)點s插入到隊尾 rear=s;} 注意問題 1．重點理解棧、隊列和串的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。2．棧、隊列的算法是后續(xù)實驗的基礎(chǔ)（樹、圖、查找、排序等）。實驗三 多維數(shù)組和廣義表的操作 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模簠⒄战o定的多維數(shù)組類和廣義表類的程序樣例，驗證給出的多維數(shù)組和廣義表的常見算法，并實現(xiàn)有關(guān)的操作。 二、實驗要求： 1、掌握多維數(shù)組和廣義表的特點。掌握它們的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 1.設(shè)計函數(shù)建立一個n*n階的對稱矩陣。要求： （1）實現(xiàn)將對稱矩陣用一維數(shù)組存儲輸出。（2）實現(xiàn)矩陣轉(zhuǎn)置算法。（3）實現(xiàn)魔方陣算法。 (4)設(shè)計一個測試例子，并編寫主程序進行測試。2．采用鏈式存儲結(jié)構(gòu)設(shè)計廣義表類，實現(xiàn)以下操作： （1）創(chuàng)建廣義表，取廣義表的表頭元素和表尾元素； （2）求廣義表的深度。 四、程序樣例 1．稀疏矩陣結(jié)構(gòu)類型聲明 const int MaxTerm=100; struct SparseMatrix { element data[MaxTerm]; int mu, nu, tu; //行數(shù)、列數(shù)、非零元個數(shù) };template ruct element { int row, col; T item };2．稀疏矩陣轉(zhuǎn)置算法Trans1 void Trans1(SparseMatrix A, SparseMatrix &B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;//設(shè)置行數(shù)、列數(shù)、非零元素個數(shù) if(B.tu>0){ //有非零元素則轉(zhuǎn)換 pb=0; for(col=0;col //依次考察每一列 for(pa=0;pa if(A.data[pa].col==col) //處理col列元素 { B.data[pb].row= A.data[pa].col; B.data[pb].col= A.data[pa].row; B.data[pb].item= A.data[pa].item; pb++; } } } 3．稀疏矩陣轉(zhuǎn)置算法Trans2 void Trans2(SparseMatrix A, SparseMatrix &B) { B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;//設(shè)置行數(shù)、列數(shù)、元素個數(shù) if(B.tu>0){ //有非零元素則轉(zhuǎn)換 for(i=0;i //A中每一列非零元素的個數(shù)初始化為0 num[i]=0; for(i=0;i { j= A.data[i].col; //取三元組的列號 num[j]++; } cpot[0]=0; //A中第0列第一個非零元素在B中的位置為0 for(i=1;i cpot[i]= cpot[i-1]+num[i-1]; for(i=0;i { j=A.data[i].col; //當前三元組的列號 k=cpot[j]; //當前三元組在B中的下標 B.data[k].row= A.data[i].col; B.data[k].col= A.data[i].row;B.data[k].item= A.data[i].item;cpot[j]++; //預(yù)置同一列的下一個三元組的下標 } } } 4．魔方陣 void Square(int a[ ][ ], int n){ p=0;q=(n-1)/2; a[0][q]=1; //在第0行的中間位置填for(i=2;i<=n*n, i++) { p=(p-1+n)% n; //求i所在行號 q=(q-1+n)% n; //求i所在列號 if(a[p][q]>0)p=(p+1)% n;//如果位置(p, q)已經(jīng)有數(shù)，填入同一列下一行 a[p][q]=i; } } 5.廣義表類定義 enum Elemtag {Atom, List}; //Atom=0為單元素；List=1為子表 template Elemtag tag; //標志域，用于區(qū)分元素結(jié)點和表結(jié)點 union { //元素結(jié)點和表結(jié)點的聯(lián)合部分 T data; //data是元素結(jié)點的數(shù)據(jù)域 struct { GLNode *hp, *tp; //hp和tp分別指向表頭和表尾 } ptr; };};template Lists(){ls=NULL;} //無參構(gòu)造函數(shù)，初始化為空的廣義表 Lists(Lists ls1, Lists ls2); //有參構(gòu)造函數(shù)，用表頭ls1和表尾ls2構(gòu)造廣義表 ~Lists(); //析構(gòu)函數(shù)，釋放廣義表中各結(jié)點的存儲空間 int Length(); //求廣義表的長度 int Depth(GLNode //求廣義表的深度 GLNode *Head();//求廣義表的表頭 GLNode *Tail(); //求廣義表的表尾 private: GLNode Lists::Lists(Lists ls1,Lists ls2) { ls = new GLNode ls->tag = 1;ls->ptr.hp = ls1;ls->ptr.tp = ls2; } 6．求廣義表深度算法Depth template int Lists::Depth(GLNode { if(ls==NULL)return 1; //空表深度為1 if(ls->tag==0)return 0; //單元素深度為0 max=0;p = ls;while(p){ dep = Depth(p->ptr.hp); //求以p->ptr.hp為頭指針的子表即表頭的深度 if(dep>max)max = dep; p = p->ptr.tp; //準備求表尾的深度 } return max+1; //非空表的深度是各元素的深度的最大值加1 } 7．取廣義表表頭算法Head template { return ls->ptr.hp;} 8．取廣義表表尾算法Tail template return ls-> ptr.tp;} 實驗四 樹和二叉樹 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模?/p> 參照給定的二叉樹類的程序樣例，驗證給出的有關(guān)二叉樹的常見算法，并實現(xiàn)有關(guān)的操作。 二、實驗要求： 1、掌握二叉樹、哈夫曼樹和樹的特點。掌握它們的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 1．設(shè)計實現(xiàn)二叉樹類，要求： （1）編寫一個程序，首先建立不帶頭結(jié)點的二叉鏈式存儲結(jié)構(gòu)的二叉樹，然后分別輸出按照前序遍歷二叉樹、中序遍歷二叉樹和后序遍歷二叉樹訪問各結(jié)點的序列信息，最后再測試查找函數(shù)和撤銷函數(shù)的正確性。（2）實現(xiàn)二叉樹層次遍歷的非遞歸算法。（3）編寫一主函數(shù)來驗證算法實現(xiàn)。 2.假設(shè)二叉樹采用鏈式存儲結(jié)構(gòu)進行存儲，編寫一個算法，輸出一個二叉樹的所有葉子結(jié)點，并統(tǒng)計葉子結(jié)點個數(shù)。*3.設(shè)計實現(xiàn)二叉線索鏈表類，要求： （1）編寫一個程序，首先建立中序線索鏈表的二叉樹，然后實現(xiàn)中序線索鏈表的遍歷算法。 （2）編寫一主函數(shù)來驗證算法實現(xiàn)。*4.編寫求二叉樹高度的函數(shù)。 *5.編寫創(chuàng)建哈夫曼樹和生成哈夫曼編碼的算法。 *6．假設(shè)二叉樹采用鏈式存儲結(jié)構(gòu)進行存儲，試設(shè)計一個算法，輸出從每個葉子結(jié)點到根結(jié)點的路徑。 *7．假設(shè)二叉樹采用鏈式存儲結(jié)構(gòu)進行存儲，試設(shè)計一個算法，求二叉樹的寬度（即具有結(jié)點數(shù)最多的層次上結(jié)點總數(shù)） 四、程序樣例 １．二叉樹 二叉鏈表結(jié)點聲明 template T data; BiNode template BiTree(){root=NULL;} //無參構(gòu)造函數(shù)，初始化一棵空的二叉樹 BiTree(BiNode ~BiTree(); //析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點的存儲空間 void PreOrder(BiNode //前序遍歷二叉樹 void InOrder(BiNode //中序遍歷二叉樹 void PostOrder(BiNode //后序遍歷二叉樹 void LeverOrder(BiNode //層序遍歷二叉樹 private: BiNode //指向根結(jié)點的頭指針 void Creat(BiNode //有參構(gòu)造函數(shù)調(diào)用 void Release(BiNode //析構(gòu)函數(shù)調(diào)用 };二叉樹的層序遍歷算法LeverOrder template if(q->lchild!=NULL) Q[++rear]=q->lchild;if(q->rchild!=NULL) Q[++rear]=q->rchild; } } 二叉樹的構(gòu)造函數(shù)算法BiTree template creat(root)； } template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空樹 else { root=new BiNode //生成一個結(jié)點 root->data=ch; Creat(root->lchild); //遞歸建立左子樹 Creat(root->rchild); //遞歸建立右子樹 } } 二叉樹的后序遍歷遞歸算法PostOrder template if(root==NULL)return; //遞歸調(diào)用的結(jié)束條件 else { PostOrder(root->lchild); //后序遞歸遍歷root的左子樹 PostOrder(root->rchild); //后序遞歸遍歷root的右子樹 cout< //訪問根結(jié)點的數(shù)據(jù)域 } } 二叉樹的后序遍歷非遞歸算法PostOrder template { top=-1; //采用順序棧，并假定棧不會發(fā)生上溢 while(root!=NULL | | top!=-1){ while(root!=NULL){ top++;s[top].ptr=root; s[top].flag=1;root=root->lchild; } while(top!=-1 && s[top].flag==2){ root=s[top--].ptr; cout< s[top].flag=2; root=s[top].ptr->rchild; } } } 二叉樹前序遍歷遞歸算法PreOrder template { if(root ==NULL) return; //遞歸調(diào)用的結(jié)束條件 else { cout< //訪問根結(jié)點的數(shù)據(jù)域 PreOrder(root->lchild); //前序遞歸遍歷root的左子樹 PreOrder(root->rchild); //前序遞歸遍歷root的右子樹 } } 二叉樹的前序遍歷非遞歸算法PreOrder template { top=-1; //采用順序棧，并假定不會發(fā)生上溢 while(root!=NULL | | top!=-1){ while(root!= NULL){ cout< } if(top!=-1){ root=s[top--]; root=root->rchild; } } } 二叉樹的析構(gòu)函數(shù)算法BiTree template Release(root);} void BiTree ::Release(BiNode if(root!=NULL){ Release(root->lchild); //釋放左子樹 Release(root->rchild); //釋放右子樹 delete root; } } 二叉樹的中序遍歷遞歸算法InOrder template if(root==NULL)return; //遞歸調(diào)用的結(jié)束條件 else { InOrder(root->lchild); //中序遞歸遍歷root的左子樹 cout< //訪問根結(jié)點的數(shù)據(jù)域 InOrder(root->rchild); //中序遞歸遍歷root的右子樹 } } ２．線索鏈表 線索鏈表結(jié)點聲明 enum flag {Child, Thread}; //枚舉類型，枚舉常量Child=0，Thread=1 template T data; ThrNode flag ltag, rtag;};線索鏈表類聲明 template InThrBiTree(ThrNode //構(gòu)造函數(shù)，建立中序線索鏈表 ~ InThrBiTree(); //析構(gòu)函數(shù)，釋放線索鏈表中各結(jié)點的存儲空間 ThrNode *Next(ThrNode void InOrder(ThrNode ThrNode void Creat(ThrNode //構(gòu)造函數(shù)調(diào)用 void ThrBiTree(ThrNode //構(gòu)造函數(shù)調(diào)用 };中序線索鏈表構(gòu)造函數(shù)算法InThrBiTree template { Creat(root); pre=NULL; ThrBiTree(root);} template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空樹 else { root=new ThrNode //生成一個結(jié)點，左右標志均置0 root->data=ch;root->ltag=0;root->rtag=0; Creat(root->lchild); //遞歸建立左子樹 Creat(root->rchild); //遞歸建立右子樹 } } template if(root==NULL)return;ThrBiTree(root->lchild);if(!root->lchild){ //對root的左指針進行處理 root->ltag=1; root->lchild=pre;//設(shè)置pre的前驅(qū)線索 } if(!root->rchild)root->rtag=1; //對root的右指針進行處理 if(pre->rtag==1)pre->rchild=root;//設(shè)置pre的后繼線索 pre=root;ThrBiTree(root->rchild);} 中序線索鏈表查找后繼的算法Next template if(p->rtag==1)q=p->rchild; //右標志為1，可直接得到后繼結(jié)點 else { q=p->rchild; //工作指針初始化，while(q->ltag==0) //查找最左下結(jié)點 q=q->lchild; } return q;} 中序線索鏈表查找后繼的算法Next template if(root==NULL)return;//如果線索鏈表為空，則空操作返回 p=root; while(p->ltag==0) //查找中序遍歷序列的第一個結(jié)點p并訪問 p=p->lchild;cout< data;while(p->rchild!=NULL) //當結(jié)點p存在后繼，依次訪問其后繼結(jié)點 { p=Next(p);cout< data;} } 中序線索鏈表構(gòu)造函數(shù)算法InThrBiTree template { Creat(root); pre=NULL; ThrBiTree(root);} template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空樹 else { root=new ThrNode //生成一個結(jié)點，左右標志均置0 root->data=ch;root->ltag=0;root->rtag=0; Creat(root->lchild); //遞歸建立左子樹 Creat(root->rchild); //遞歸建立右子樹 } } template if(root==NULL)return;ThrBiTree(root->lchild);if(!root->lchild){ //對root的左指針進行處理 root->ltag=1; root->lchild=pre;//設(shè)置pre的前驅(qū)線索 } if(!root->rchild)root->rtag=1; //對root的右指針進行處理 if(pre->rtag==1)pre->rchild=root;//設(shè)置pre的后繼線索 pre=root;ThrBiTree(root->rchild);} ３．哈夫曼樹 void HuffmanTree(element huffTree[ ], int w[ ], int n) { for(i=0;i<2*n-1;i++) //初始化 { huffTree [i].parent=-1;huffTree [i].lchild=-1;huffTree [i].rchild=-1; } for(i=0;i //構(gòu)造n棵只含有根結(jié)點的二叉樹 huffTree [i].weight=w[i];for(k=n;k<2*n-1;k++) //n-1次合并 { Select(huffTree, i1, i2); //在huffTree中找權(quán)值最小的兩個結(jié)點i1和i2 huffTree[i1].parent=k; //將i1和i2合并，則i1和i2的雙親是k huffTree[i2].parent=k; huffTree[k].weight= huffTree[i1].weight+huffTree[i2].weight;huffTree[k].lchild=i1; huffTree[k].rchild=i2;} } 注意問題 1．注意理解有關(guān)樹的各種遞歸算法的執(zhí)行步驟。 2．注意字符類型數(shù)據(jù)在輸入時的處理。3．重點理解如何利用棧結(jié)構(gòu)實現(xiàn)非遞歸算法。 實驗五 圖的有關(guān)操作 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模?/p> 參照給定的圖類的程序樣例，驗證給出的有關(guān)圖的常見算法，并實現(xiàn)有關(guān)的操作。 二、實驗要求： 1、掌握圖的特點，利用圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)實現(xiàn)圖的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 1.設(shè)計鄰接矩陣圖類，實現(xiàn)如下操作：（1）測試類中的成員函數(shù)；（2）實現(xiàn)拓撲排序算法；（3）實現(xiàn)最小生成樹算法；（4）實現(xiàn)最短路徑算法； （5）設(shè)計主函數(shù)，輸入數(shù)據(jù)，測試各算法。 2.設(shè)計鄰接表類，實現(xiàn)無向圖的深度優(yōu)先非遞歸遍歷、無向圖的廣度優(yōu)先遍歷，并設(shè)計主函數(shù)輸入數(shù)據(jù)進行測試。 *3.假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到頂點v的長度為l的所有簡單路徑。 四、程序樣例： 1.圖的鄰接表類的定義 struct ArcNode //定義邊表結(jié)點 { int adjvex;//鄰接點域 ArcNode *next;};template //定義頂點表結(jié)點 { T vertex; ArcNode *firstedge;};const int MaxSize=10; //圖的最大頂點數(shù) template ALGraph(T a[ ], int n, int e); //構(gòu)造函數(shù)，初始化一個有n個頂點e條邊的圖 ~ALGraph; //析構(gòu)函數(shù)，釋放鄰接表中各邊表結(jié)點的存儲空間 T GetVex(int i); //取圖中第i個頂點數(shù)據(jù)信息 void PutVex(int i, T value); //將圖中第i個頂點的數(shù)據(jù)域置為value void InsertVex(int i, T value);//在圖中插入一個頂點，其編號為i，值為value void DeleteVex(int i); //刪除圖中第i個頂點 void InsertArc(int i, int j); //在圖中插入一條邊，其依附的兩個頂點的編號為i和j void DeleteArc(int i, int j); //在圖中刪除一條邊，其依附的兩個頂點的編號為i和j void DFSTraverse(int v); //深度優(yōu)先遍歷圖 void BFSTraverse(int v); //廣度優(yōu)先遍歷圖 private: VertexNode adjlist[MaxSize]; //存放頂點表的數(shù)組 int vertexNum, arcNum; //圖的頂點數(shù)和邊數(shù) }; template //輸入頂點信息，初始化頂點表 { adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL; } for(k=0;k //依次輸入每一條邊，并在相應(yīng)邊表中插入結(jié)點 { cin>>i>>j; //輸入邊所依附的兩個頂點的序號 s=new ArcNode;s->adjvex=j;//生成一個邊表結(jié)點s s->next=adjlist[i].firstedge; //將結(jié)點s插入到結(jié)點i的邊表的表頭 adjlist[i].firstedge=s;} } template cout< p=adjlist[v].firstedge; while(p) //依次搜索頂點v的鄰接點j { j=p->adjvex;if(visited[j]==0)DFSTraverse(j); p=p->next; } } template { front=rear=-1; //初始化隊列, 假設(shè)隊列采用順序存儲且不會發(fā)生溢出 cout< //被訪問頂點入隊 while(front!=rear) { v=Q[++front]; p=adjlist[v].firstarc; //邊表中的工作指針p初始化 while(p) { j= p->adjvex; if(visited[j]==0){ cout< } p=p->next;} } } 2.圖的鄰接矩陣類的定義 const int MaxSize=10; //圖中最多頂點個數(shù) template MGraph(T a[ ], int n, int e); //構(gòu)造函數(shù)，初始化具有n個頂點e條邊的圖 ~MGraph(){ } //析構(gòu)函數(shù) T GetVex(int i); //取圖中第i個頂點數(shù)據(jù)信息 void PutVex(int i, T value); //將圖中第i個頂點的數(shù)據(jù)域置為value void InsertVex(int i, T value);//在圖中插入一個頂點，其編號為i，值為value void DeleteVex(int i); //刪除圖中第i個頂點 void InsertArc(int i, int j); //在圖中插入一條邊，其依附的兩個頂點的編號為i和j void DeleteArc(int i, int j); //在圖中刪除一條邊，其依附的兩個頂點的編號為i和j void DFSTraverse(int v); //深度優(yōu)先遍歷圖 void BFSTraverse(int v); //廣度優(yōu)先遍歷圖 private: T vertex[MaxSize]; //存放圖中頂點的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 int vertexNum, arcNum; //圖的頂點數(shù)和邊數(shù) };template { vertexNum=n;arcNum=e;for(i=0;i vertex[i]=a[i];for(i=0;i //初始化鄰接矩陣 for(j=0;j arc[i][j]=0; for(k=0;k //依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素 { cin>>i>>j; //邊依附的兩個頂點的序號 arc[i][j]=1; //置有邊標志 arc[j][i]=1; } } 3．圖的拓撲排序 void TopSort() { top=-1;count=0; //采用順序棧S并初始化，累加器初始化； for(i=0;i //掃描頂點表，將入度為0的頂點壓棧； if(adjlist[i].in==0)S[++top]=i； while(top!=-1) //當圖中還有入度為0的頂點時循環(huán) { j=S[top--]; //從棧中取出一個入度為0的頂點 cout< p=adjlist[j].firstedge;//掃描頂點表，找出頂點j的所有出邊 while(p!=NULL) { k=p->adjvex; adjlist[k].in--; //將入度減1，如果為0，則將該頂點入棧 if(adjlist[k].in==0) S[++top]=k; p=p->next; } } if(count cout<<”有回路“; } 4．圖的Prim算法，求圖的最小生成樹 void Prim(MGraph G){ for(i=1;i adjvex[i]=0;} lowcost[0]=0; //將頂點0加入集合U中 for(i=1;i cout<<”(“< //輸出加入TE中的邊 lowcost[k]=0; //將頂點v加入集合U中 for(j=1;j //調(diào)整數(shù)組lowcost和adjvex if G.arc[k][j] lowcost[j]=G.arc[k][j]; adjvex[j]=k; } } } 5．圖的最短路徑 void Dijkstra(MGraph G, int v) { for(i=0;i //初始化dist[n]、path[n] { dist[i]=G.arc[v][i]; if(dist[i]!=∞)path[i]=G.vertex[v]+G.vertex[i]; else path[i]=”“; } s[0]=G.vertex[v]; //初始化集合S dist[v]=0; //標記頂點v為源點 num=1;while(num //當數(shù)組s中的頂點數(shù)小于圖的頂點數(shù)時循環(huán) { k=0;for(i=0;i //在dist中查找最小值元素 if((dist[i] cout< //將新生成的終點加入集合S dist[k]=0; //置頂點vk為已生成終點標記 for(i=0;i //修改數(shù)組dist和path if(dist[i]>dist[k]+G.arc[k][i]){ dist[i]=dist[k]+G.arc[k][i]; path[i]=path[k]+G.vertex[i]; } } } void Floyd(MGraph G) { for(i=0;i //初始化矩陣dist和path for(j=0;j { dist[i][j]=G.arc[i][j]; if(dist[i][j]!=∞)path[i][j]=G.vertex[i]+G.vertex[j]; else path[i][j]=”“; } for(k=0;k //進行n次迭代 for(i=0;i //頂點i和j之間是否經(jīng)過頂點k for(j=0;j if(dist[i][k]+dist[k][j] dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=path[i][k]+path[k][j]; } } 注意問題 １．注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。 ２．注意區(qū)別正、逆鄰接矩陣。 實驗六 查找 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模?/p> 參照各種查找算法程序樣例，驗證給出的查找常見算法。 二、實驗要求： 1、掌握各種查找算法的特點，測試并驗證查找的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 1.建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找。 2．利用折半查找算法在一個有序表中插入一個元素，并保持表的有序性。3．建立順序表，統(tǒng)計表中重復(fù)元素個數(shù)。 5.根據(jù)給定的二叉排序樹類的定義,驗證二叉排序樹的各個成員函數(shù)。4.哈希表類設(shè)計。要求： (1)哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法；(2)設(shè)計一個側(cè)試程序進行側(cè)試。 四、程序樣例： １．順序表的順序查找算法SeqSearch1 int SeqSearch1(int r[ ], int n, int k) { r[0]=k;i=n;while(r[i]!=k)i--;return i;} ２．折半查找遞歸 int BinSearch2(int r[ ], int low, int high, int k) { if(low>high)return 0;//遞歸的邊界條件 else { mid=(low+high)/2; if(k else if(k>r[mid])return BinSearch2(r, mid+1, high, k); else return mid;} } ３．折半查找非遞歸 int BinSearch1(int r[ ], int n, int k){ low=1;high=n;while(low<=high) { mid=(low+high)/2; if(k else return mid; } return 0;} ４．單鏈表的順序查找算法SeqSearch2 int SeqSearch2(Node { p=first->next;j=1; while(p!=NULL && p->data!=k) { p=p->next; j++; } if(p->data==k)return j; else return 0;} ５．二叉排序樹類聲明 class BiSortTree //本章假定記錄中只有一個整型數(shù)據(jù)項 { public: BiSortTree(int a[ ], int n); //建立查找集合a[n]的二叉排序樹 ~ BiSortTree(); //析構(gòu)函數(shù)，釋放二叉排序樹中所有結(jié)點，同二叉鏈表的析構(gòu)函數(shù) void InsertBST(BiNode private: BiNode //二叉排序樹（即二叉鏈表）的根指針 }; 二叉排序樹構(gòu)造函數(shù)算法BiSortTree BiSortTree::BiSortTree(int r[ ], int n){ for(i=0;i s->lchild=s->rchild=NULL;InsertBST(root, s);} } 二叉排序樹插入算法InsertBST 1.若root是空樹，則將結(jié)點s作為根結(jié)點插入；否則 2.若s->data＜root->data，則把結(jié)點s插入到root的左子樹中；否則 3.把結(jié)點s插入到root的右子樹中。 void BiSortTree::InsertBST(BiNode if(root==NULL)root=s; else if(s->data else InsertBST(root->rchild, s);} 二叉排序樹查找算法SearchBST BiNode * BiSortTree::SearchBST(BiNode { if(root==NULL)return NULL； else if(root->data==k)return root; else if(k else return SearchBST(root->rchild, k); } 二叉排序樹的刪除算法DeleteBST void BiSortTree::DeleteBST(BiNode { if(!p->lchild &&!p->rchild){ //p為葉子 f->lchild= NULL;delete p;} else if(!p->rchild){ //p只有左子樹 f->lchild=p->lchild; delete p;} else if(!p->lchild){ //p只有右子樹 f->lchild=p->rchild; delete p; } else { //左右子樹均不空 par=p;s=p->rchild; while(s->lchild!=NULL) //查找最左下結(jié)點 { par=s; s=s->lchild; } p->data=s->data; if(par==p)par->rchild=s->rchild;//處理特殊情況 else par->lchild=s->rchild; //一般情況 delete s; } //左右子樹均不空的情況處理完畢 } ６．閉散列表的查找算法HashSearch1 int HashSearch1(int ht[ ], int m, int k) { j=H(k); if(ht[j]==k)return j; //沒有發(fā)生沖突，比較一次查找成功 i=(j+1)% m;while(ht[i]!=Empty && i!=j) { if(ht[i]==k)return i;//發(fā)生沖突，比較若干次查找成功 i=(i+1)% m; //向后探測一個位置 } if(i==j)throw ”溢出“;else ht[i]=k; //查找不成功時插入 } ７．開散列表的查找算法HashSearch２ Node j=H(k);p=ht[j];while(p && p->data!=k)p=p->next;if(p->data= =k)return p; else { q=new Node q->next= ht[j]; ht[j]=q; } } 注意問題 1．注意理解折半查找的適用條件（鏈表能否實現(xiàn)折半查找？）。2.注意理解靜態(tài)查找、動態(tài)查找概念。 3．比較各種查找算法的各自特點，能夠根據(jù)實際情況選擇合適的查找方法。 實驗七 排序的有關(guān)操作 實驗類型：驗證性 實驗要求：必修 實驗學(xué)時： 2學(xué)時 一、實驗?zāi)康模?/p> 參照各種排序算法程序樣例，驗證給出的排序常見算法。 二、實驗要求： 1、掌握各種排序算法的特點，測試并驗證排序的常見算法。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 輸入一組關(guān)鍵字序列分別實現(xiàn)下列排序: 1.實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。2.實現(xiàn)希爾排序算法。 3.實現(xiàn)快速排序算法（取第一個記錄或中間記錄作為基準記錄）。4.實現(xiàn)堆排序算法。*5.快速排序的非遞歸算法。*6.實現(xiàn)折半插入排序。 *7.采用鏈式存儲實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。 8.在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。 *9.雙向起泡排序。在起泡排序中，若待排序序列為正序，只需一趟掃描，而待排序序列為反序時，需進行n-1趟掃描。對于初始序列（94，10，12，18，42，44，67）只需掃描2趟，而對于初始序列（12，18，42，44，67，94，10）就需掃描6趟。造成這種不對稱的原因：每趟掃描僅能使最小數(shù)據(jù)下沉一個位置，如果改變掃描方向，情況正好相反，即每趟從后往前掃描，都能使當前無序區(qū)中最大數(shù)據(jù)上浮一個位置。為了改變上述兩種情況下的不對稱性，可以在排序過程中交替改變掃描方向，稱之為雙向起泡排序。 四、程序樣例: 1.選擇排序 void SelectSort(int r[ ], int n){ for(i=1;i //對n個記錄進行n-1趟簡單選擇排序 { index=i; for(j=i+1;j<=n;j++) //在無序區(qū)中選取最小記錄 if(r[j] if(index!=i)r[i]←→r[index]; } } 2．快速排序 int Partition(int r[ ], int first, int end) { i=first;j=end; //初始化 while(i { while(i //右側(cè)掃描 if(i r[i]←→r[j]; //將較小記錄交換到前面 i++; } while(i //左側(cè)掃描 if(i r[j]←→r[i]; //將較大記錄交換到后面 j--; } } retutn i; //i為軸值記錄的最終位置 } void QuickSort(int r[ ], int first, int end) { if(first //遞歸結(jié)束 pivot=Partition(r, first, end);//一次劃分 QuickSort(r, first, pivot-1);//遞歸地對左側(cè)子序列進行快速排序 QuickSort(r, pivot+1, end); //遞歸地對右側(cè)子序列進行快速排序 } } 3.起泡排序 void BubbleSort(int r[ ], int n) { exchange=n; //第一趟起泡排序的范圍是r[1]到r[n] while(exchange)//僅當上一趟排序有記錄交換才進行本趟排序 { bound=exchange;exchange=0； for(j=1;j //一趟起泡排序 if(r[j]>r[j+1]){ r[j]←→r[j+1]； exchange=j； //記錄每一次發(fā)生記錄交換的位置 } } } 4.希爾排序 void ShellSort(int r[ ], int n){ for(d=n/2;d>=1;d=d/2) //以增量為d進行直接插入排序 { for(i=d+1;i<=n;i++) { r[0]=r[i]; //暫存被插入記錄 for(j=i-d;j>0 && r[0] r[j+d]=r[j]; //記錄后移d個位置 r[j+d]=r[0]; } } } void InsertSort(int r[ ], int n){ for(i=2;i<=n;i++) { r[0]=r[i]; //設(shè)置哨兵 for(j=i-1;r[0] //尋找插入位置 r[j+1]=r[j]; //記錄后移 r[j+1]=r[0]; } } 5.堆排序 void Sift(int r[ ], int k, int m){ i=k;j=2*i; //置i為要篩的結(jié)點，j為i的左孩子 while(j<=m) //篩選還沒有進行到葉子 { if(j //根結(jié)點已經(jīng)大于左右孩子中的較大者 else { r[i]←→r[j]; //將根結(jié)點與結(jié)點j交換 i=j;j=2*i; //被篩結(jié)點位于原來結(jié)點j的位置 } } } void HeapSort(int r[ ], int n){ for(i=n/2;i>=1;i--) //初始建堆，從最后一個非終端結(jié)點至根結(jié)點 Sift(r, i, n); for(i=1;i //重復(fù)執(zhí)行移走堆頂及重建堆的操作 { r[1]←→r[n-i+1]; Sift(r, 1, n-i); } } 6.歸并排序 void MergeSort2(int r[ ], int r1[ ], int s, int t){ if(s==t)r1[s]=r[s]; else { m=(s+t)/2; Mergesort2(r, r1, s, m); //歸并排序前半個子序列 Mergesort2(r, r1, m+1, t); //歸并排序后半個子序列 Merge(r1, r, s, m, t); //將兩個已排序的子序列歸并 } } void MergeSort1(int r[ ], int r1[ ], int n){ h=1; while(h { MergePass(r, r1, n, h); h=2*h; MergePass(r1, r, n, h); h=2*h;} } void Merge(int r[ ], int r1[ ], int s, int m, int t){ i=s;j=m+1;k=s;while(i<=m && j<=t) { if(r[i]<=r[j])r1[k++]=r[i++]; //取r[i]和r[j]中較小者放入r1[k] else r1[k++]=r[j++];} if(i<=m)while(i<=m) //若第一個子序列沒處理完，則進行收尾處理 r1[k++]=r[i++]; else while(j<=t)//若第二個子序列沒處理完，則進行收尾處理 r1[k++]=r[j++]; } void MergePass(int r[ ], int r1[ ], int n, int h){ i=1;while(i≤n-2h+1) //待歸并記錄至少有兩個長度為h的子序列 { Merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h;} if(i＜n-h+1)Merge(r, r1, i, i+h-1, n);//待歸并序列中有一個長度小于h else for(k=i;k<=n;k++) //待歸并序列中只剩一個子序列 r1[k]=r[k]; } 注意問題： 注意理解各種算法的思想、了解算法的適用情況及時間復(fù)雜度，能夠根據(jù)實際情況選擇合適的排序方法。 實驗八 綜合實驗 實驗類型：綜合性 實驗要求：必修 實驗學(xué)時：2學(xué)時 一、實驗?zāi)康模?/p> 通過該實驗是學(xué)生能夠綜合數(shù)據(jù)結(jié)構(gòu)所學(xué)的知識，自行分析、設(shè)計，學(xué)會對一個實際問題分析、綜合、設(shè)計的能力。 二、實驗要求 1、掌握數(shù)據(jù)結(jié)構(gòu)所學(xué)的內(nèi)容，分析給定實驗內(nèi)容并設(shè)計出程序，然后運行，同時分析幾種不同方法的效率。 2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。 三、實驗內(nèi)容： 設(shè)計一個簡單個人電話號碼查詢系統(tǒng) 1.問題描述： 人們在日常中經(jīng)常要查找某個人或某個單位的電話號碼，本實驗將實現(xiàn)一個簡單的個人電話號碼查詢系統(tǒng)，根據(jù)用戶輸入信息（例如姓名等）進行快速查詢。 2、基本要求 （1）在外存上，用文件保存電話號碼信息；（2）在內(nèi)存中，設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲電話信息；（3）提供查詢功能；根據(jù)姓名實現(xiàn)快速查詢；（4）提供其他功能，例如插入、刪除、修改等； 3、設(shè)計思想 由于要管理的電話號碼信息很多，而且要在程序運行后仍然保存電話號碼信息，所以電話號碼信息采用文件的形式存放在外存上。在系統(tǒng)運行時，要將電話號碼信息從文件調(diào)入內(nèi)存來進行查詢等操作，為了接收文件中內(nèi)容，要有一個數(shù)據(jù)結(jié)構(gòu)與之對應(yīng)，可以設(shè)計如下結(jié)構(gòu)類型的數(shù)組來接收數(shù)據(jù)： const int max = 10 struct TeleNumber { String name;String phoneNumber;String mobileNumber;String email;為了實現(xiàn)對電話號碼的快速查詢，可以將上述結(jié)構(gòu)數(shù)組排序，以便應(yīng)用折半查找，但數(shù)組中實現(xiàn)插入和刪除操作的代價較高。如果記錄頻繁進行插入或刪除操作，可以考慮采用} Tele[max];二叉排序數(shù)組織電話號碼信息，則查詢和維護都能獲得較高的時間性能；另外也可以考慮直接使用哈希表表結(jié)構(gòu)存儲電話號碼信息，請同學(xué)根據(jù)實際情況自己選擇。 4、詳細分析采用幾種不同方法實現(xiàn)的效率。實驗九：停車場管理（開放實驗一） 實驗類型：設(shè)計性 【實驗內(nèi)容與要求】 設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。 試為停車場編制按上述要求進行管理的模擬程序。【知識要點】 綜合利用棧和隊列模擬停車場管理，學(xué)習(xí)利用棧和隊列解決實際問題。【實現(xiàn)提示】 以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。 需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。 設(shè)n=2,輸入數(shù)據(jù)為：（?A?，1，5），（?A?，2，10），（?D?，1，15），（?A?，3，20），（?A?，4，25），（?A?，5，30），（?D?，2，35），（?D?，4，40），（?E?，0，0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，?A?表示到達；?D?表示離去，?E?表示輸入結(jié)束。 根據(jù)以上問題寫出實驗報告。【參考程序】 #include （1）汽車可有不同種類，則它們的占地面積不同，收費標準也不同，如1輛客車和1.5輛小汽車的占地面積相同，1輛十輪卡車占地面積相當于3輛小汽車的占地面積。如何處理該問題？ （2）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。如何處理該問題？ 實驗十：窗口管理（開放實驗二） 實驗類型：設(shè)計性 【實驗內(nèi)容與要求】 圖形用戶界面（GUI）維護屏幕上的多個窗口。這些窗口按層次組織，最前面的窗口作為活動窗口。有些應(yīng)用程序維護一個當前打開窗口表。從菜單中可以訪問此表。用戶可以選擇一個窗口標題以使成為最前面的或活動的窗口。當一個底層窗口的視線被擋時，這就顯得特別有用。從菜單的表中選擇“Window_1”可以激活該窗口。 試為窗口編制按上述要求進行管理的模擬程序。【知識要點】 綜合利用鏈表、排序的方法，學(xué)習(xí)利用鏈表和排序解決實際問題。【實現(xiàn)提示】 本實驗中維護GUI應(yīng)用的一個窗口表。應(yīng)用程序支持以下的文件和表操作： New：插入名為“Untitled”的窗口。Close：刪除前排窗口。 Close All：清空表以關(guān)閉所有的窗口。 Save As：將窗口的內(nèi)容保存到不同的文件名中并更新窗口的標題。Quit：終止應(yīng)用程序。 Menu Display：窗口菜單按層次顯示每個窗口的號碼和名字。用戶可以輸入號碼并激活窗口，將它移到窗口表的最前面。 窗口表： 任一時刻所允許打開的窗口最大數(shù)目為10。每個打開的窗口都對應(yīng)有一個0到9范圍內(nèi)的號碼。關(guān)閉一個窗口時，其號碼可以用于創(chuàng)建新的打開窗口的New操作。處理各個窗口并修改當前活動窗口由Close，Close All，Save As和Activate方法負責(zé)，每個窗口都由一個窗口對象表示，它描述了窗口名及其在可用窗口表中的號碼。 根據(jù)以上問題寫出實驗報告。 C++/數(shù)據(jù)結(jié)構(gòu) 大作業(yè)/課程設(shè)計——【校園導(dǎo)游咨詢】【停車場管理】娃娃們可以收著以后用 絕對純手工打造 內(nèi)含類模塊/一維指針數(shù)組（謹以此程序供大家參考。運行結(jié)果后面有貼圖） 目錄 【1】校園導(dǎo)游咨詢 程序設(shè)計源代碼 及 截圖 【2】停車場管理——方案一 程序設(shè)計源代碼 及 截圖 【3】停車場管理——方案二 程序設(shè)計源代碼 及 截圖 【1】【【校園導(dǎo)游咨詢】】 ###### (ps:該校園導(dǎo)游咨詢系統(tǒng)沒有輸入值，所有信息是都在class MGraph的構(gòu)造函數(shù)中傳輸?shù)模倚@景點信息皆為【【上海電力學(xué)院】】景點信息。請大家注意，直接從文章copy到visual stutio中會出現(xiàn)中文字符，注意刪除，推薦大家在一行語句的分號后面，點出光標，按一下delete鍵，然后按一下enter鍵，完成visual stutio的自動對齊，這樣程序看起來一目了然，更易于操作和更改)【問題描述】 設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。【基本要求】 (1)設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。(2)為來訪客人提供圖中任意景點相關(guān)信息的查詢。 (3)為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑。【選作內(nèi)容】 (6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。**************************【以下為類的定義】******************************** #include class direction;template { friend class MGraph direction dir;//存放頂點方位信息的direction類的dir。}; class direction { public: int ln;//存放在方向圖中的橫坐標，表示東西 int col;//存放在方向圖中的縱坐標，表示南北 };template { public: MGraph(); //構(gòu)造函數(shù)，初始化具有n個頂點的圖 void printvexname();//顯示所有景點及景點代號 void printvexinf(int i);//顯示代號為i景點的名稱及信息 void printroad(int i,int j);//顯示景點i~j的最短路徑方案信息 void printdir(int i,int j);//顯示景點i到j(luò)的方向信息，如“向東100m，向南200m” VertexNode void Root(int p,int q);//遞歸尋找pq間的最短路徑 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//創(chuàng)建Path和Dist分別存放兩點間最短路徑的前驅(qū)節(jié)點，兩點間最短路徑長度 int Line[MaxSize];//Line存放路徑 int kkk;//Line[]數(shù)組的標記 private: T vertex[MaxSize];//存放圖中頂點的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 };*************************【以下為類的實現(xiàn) 即類函數(shù)的定義】*********************************** template //s[]為存放景點鄰接矩陣信息的一維數(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[]={“南門”,“實驗樓”,“南圖”,“大活”,“睿思樓”,“大禮堂”, “南4教”,“知行樓”,“國交樓”,“南3教”,“南2教”,“南1教”, “北圖”,“北3教”,“北4教”,“北2教”,“北1教”,“北門”};char* c[]={“南校區(qū)正門”,“物理實驗樓”,“南校區(qū)圖書館”,“大學(xué)生活動中心”, “教師辦公樓、醫(yī)務(wù)室及留學(xué)生公寓”,“大禮堂，用于舉辦各種文藝演出”,“南校區(qū)第4教學(xué)樓”,“實習(xí)基地，計算機房等”, “國際交流中心，教職工餐廳”,“南校區(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 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】【停車場管理系統(tǒng)【方案一 程序】】 ###### （ps：該程序有漏洞，若將要離開的車輛是停于便道上的，則對該車進行駛離操作時程序內(nèi)部有錯誤數(shù)據(jù)，雖然做了函數(shù)完成這一功能，但因時間有限，沒能及時查找更正，現(xiàn)在懶得改了。。大家將就看吧。不過運行是可以的）【問題描述】 設(shè)停車場是一個可停放n輛汽車的 長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車信放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場院，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。【基本要求】 以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。【測試數(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表示到達（Arrival）；D表示離去（Departure）；E表示輸入結(jié)束（End）。**************************【以下為類的定義】************************************* #include const double price=30;//每小時的費用 //思想：（報告第四頁） //我的系統(tǒng)界面，輸入信息為：（到達/離開/退出）；車牌號；時刻 //因此，我的停車場類分成車輛到達和車輛離開兩個主要的函數(shù)實現(xiàn)。//車輛到達，有入棧和入隊。車輛離開有出棧，出隊和入棧操作。 //因此我又編寫入棧的類，隊的類。與parkingmanagement進行友元。 //**************************************類定義*********************************************** class car//車的信息類 { public: double time;//計費時間 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//隊列（便道）的類 { friend class parkingmanagement;//parkingmanagement能訪問carstack類中所有成員 public: carqueue();//構(gòu)造函數(shù)，隊列的初始化 int full();//判斷隊列是否為滿 car *front,*rear;//存放car類型隊列元素的數(shù)組初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入棧,cs棧內(nèi)進行調(diào)整，返回棧內(nèi)位置 void popstack(carstack &cs,int cnum);//出棧，cs棧內(nèi)進行調(diào)整，//根據(jù)車牌號把車彈出棧,將出棧car的number賦值給int popstacknumber()//將出棧car的time賦值給double popstacktime()，無返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);//入隊,隊內(nèi)進行調(diào)整，返回隊內(nèi)位置 int popqueue(carqueue &cq);//出隊,隊內(nèi)進行調(diào)整，返回汽車車牌號 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛到達，//根據(jù)輸入的車牌號、到達時間，變更函數(shù)參數(shù)；并cout車位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//車輛離開，//根據(jù)輸入的車牌號找到汽車，并進行出棧操作、出隊操作和入棧操作； //并cout停留時間和收費情況 void deletequeue(carqueue &cq,int i);//刪除cq過道中第i輛車 int popstacknumber;//專門存放出棧的時候返回的車牌號 double popstacktime;//專門存放出棧的時候返回的時刻 };**********************************【以下為類的實現(xiàn)】************************************ carstack::carstack()//構(gòu)造函數(shù)，棧的初始化 { top=-1;s=new car[Max];//創(chuàng)建car類型棧元素的數(shù)組 if(s==NULL){ cout<<“棧空間分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//將cnum賦給棧頂位置的車的車牌號，s是car類型棧元素的數(shù)組(cs.s[cs.top]).time=ctime;//將ctime賦給棧頂位置的車的入棧時間，s是car類型棧元素的數(shù)組 return(cs.top+1);//返回棧內(nèi)位置加1，即停車場內(nèi)車位從1號開始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出棧，cs棧內(nèi)進行調(diào)整，//根據(jù)車牌號把車彈出棧,將出棧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;//當要出棧的車的車牌號=棧內(nèi)的車牌號元素時，跳出循環(huán) p=cs.s[i];//將要出棧的元素賦給car類型的p存放 while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出棧的元素數(shù)組逐個賦給臨時棧 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)//入隊,隊內(nèi)進行調(diào)整，返回隊內(nèi)位置 { car *p,*countp;int count(1);//count用于記錄車在過道上的位置信息，因隊列為鏈式的，所以進行循環(huán)累加 p=new car;//創(chuàng)建一個car類型的指針 p->number=cnum;p->time=ctime;p->next=NULL;//首先將指向存放car類型元素的數(shù)組初始地址置空 if(cq.front==NULL)//第一次入隊要判斷頭結(jié)點是否為空 { 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)//出隊,隊內(nèi)進行調(diào)整，返回汽車車牌號 { 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)//車輛到達，根據(jù)輸入的車牌號、到達時間，變更函數(shù)參數(shù)；并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)//如果到達的車的車牌號=棧內(nèi)已有車輛的車牌號 { fl=1;//fl記1 break;} } if(fl==1)//如果到達的車的車牌號!=棧內(nèi)已有車輛的車牌號 cout<<“輸入錯誤！請重新輸入！”< cout<<“該停車場還有空位，請到”< { pos=pushqueue(cq,cnum,ctime);//入隊，返回車位信息 cout<<“該停車場已滿，請將車停到便道”< { popstack(cs,cnum);//出棧操作 hour=ctime-popstacktime;//時間計算 outcarnum=popqueue(cq);//將便道上的第一輛車出隊，入棧。并將其車牌號賦給outcarnum pstack=pushstack(cs,outcarnum,ctime);//將便道上的第一輛車，入棧 cout<<“該車在本停車場內(nèi)停留時間為”< { 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】【停車場管理系統(tǒng)【方案二 程序】】 （ps：本方案與方案一有同樣的問題，就是在對 便道上的車 進行駛離操作時，數(shù)據(jù)錯誤，同樣的理由，沒有改正。如果有細心娃娃幫忙指點改正，在此感激啦~） *************************【以下為類定義】************************************ #include struct Node//過道停車的隊列所需鏈式結(jié)點 { T carnum;//定義車牌號類型 Node friend class carStack;public: T carnum;//車號 int cartime;//停車時間 }; template int EnQueue(T cnum);//將元素x入隊,并返回其在隊內(nèi)的位置（從1開始）T DeQueue();//將隊頭鏈式結(jié)點出隊,并返回汽車車牌號 void deletequeue(int i);//將隊內(nè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;//將結(jié)點s插入到隊尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即車在過道上的位置，【從1開始計！！】 return i;} template front=front->next;//將隊頭元素所在結(jié)點摘鏈 } return p->carnum;delete p;//將出隊進棧的車從隊列里刪除 } template template :top(-1){//建立一個最大尺寸為size的空棧 S=new carinfo { cerr<<“動態(tài)存儲失敗！”< template template void outputpark()//系統(tǒng)功能選擇頁面，輸入泊車信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“請駛?cè)胪＼噲龅摹? Node 上機實驗： 1、回文是指正讀，反讀均相同的字符序列，如“abba”和“abdba”均是回文，但是“good”不是回文，試用STACK類編寫該程序。 #include int top = 1;char *cMyStack =(char *)malloc((iLen/2+1)*sizeof(char));//定位對原始數(shù)組的檢測索引初始位置 cMyStack[0] = iLen/2;if(1 == iLen%2){ ++cMyStack[0];} //將原始數(shù)組的一半元素入棧 for(top=1;top<=iLen/2;top++){ cMyStack[top] = *(cScr+top-1);} //從棧頂開始依次匹配 while(*(cScr+cMyStack[0])== cMyStack[--top] && cMyStack[0]++ < iLen){} if(0 == top){//是回文數(shù) free(cMyStack);return 1;} else {//不是回文數(shù) free(cMyStack);return 0;} } 運行結(jié)果： 2.利用兩個棧類S1、S2模擬一個隊列時，編寫一程序利用棧的運算實現(xiàn)隊列的插入、刪除以及判斷隊列空的運算。 #include template assert(!mStack2.empty());mStack2.pop();} template sq.pushBack(1);printQueue(sq);sq.pushBack(2);printQueue(sq);sq.pushBack(3);printQueue(sq);sq.popFront();printQueue(sq);sq.popFront();printQueue(sq);sq.popFront();printQueue(sq);return 0;} 運行結(jié)果： 實驗2： 聲明復(fù)數(shù)的類Complex,使用友元函數(shù)add實現(xiàn)復(fù)數(shù)的加法。 #include < iostream > using namespace std; class Complex { private: double real, image;public : Complex(){} Complex(double a,double b) { real = a;image = b;} void setRI(double a, double b){ real = a;image = b;} double getReal(){ return real;} double getImage(){ return image;} void print(){ if(image>0) cout<<“復(fù)數(shù)：”<< real <<“ + ”<< image <<“i”<< endl;if(image<0) cout<<“復(fù)數(shù)：”<< real <<“-”<< image <<“i”<< endl;} friend Complex add(Complex ,Complex);//聲明友元函數(shù) }; Complex add(Complex c1, Complex c2)//定義友元函數(shù) { Complex c3; c3.real = c1.real + c2.real;//訪問Complex類中的私有成員 c3.image = c1.image + c2.image;return c3;} void main(){ Complex c1(29, 0.634), c2, c3;c2.setRI(85,106.012);c3 = add(c1, c2); cout<<“復(fù)數(shù)一：”;c1.print();cout<<“復(fù)數(shù)二：”;c2.print();cout<<“相加后：”;c3.print();} 結(jié)果： 實驗三： 7-5 定義一個基類Shape，在此基礎(chǔ)上派生出一個Rectangle和Circle,二者都有g(shù)etArea()函數(shù)計算對象的面積。使用Rectangle類創(chuàng)建一個派生類Square.#include public: Shape(){} double GetArea() { return 0.1;} };class Rectangle: public Shape { public: Rectangle(double w,double h) { width=w;height=h;} double GetArea(){ return width*height;} private: double width,height;};class Circle:public Shape { private: double r; public: Circle(double rr){ r=rr;} double GetArea(){ return PI*r*r;} }; int main(){ Rectangle * rec=new Rectangle(5,6); Circle * cir=new Circle(5); cout<<“RecArea:”< cout<<“CirArea:”< return 1; } 運行結(jié)果： 7-10.定義一個Object類，有數(shù)據(jù)成員weight及相應(yīng)的操作函數(shù)，由此派生出Box類，增加數(shù)據(jù)成員height和width及相應(yīng)的操作函數(shù)，聲明一個Box對象，觀察構(gòu)造函數(shù)和析構(gòu)函數(shù)的調(diào)用順序。#include object(){ cout<<“構(gòu)造object對象”< class box:public object { private: int Height,Width;public: box(){ cout<<“構(gòu)造box對象”< 面向?qū)ο蟪绦蛟O(shè)計實驗 Object Oriented Programming 課程編號： 學(xué) 分： 學(xué) 時：10 先修課程：計算機導(dǎo)論、C語言程序設(shè)計 適用專業(yè)：計算機科學(xué)與技術(shù)、軟件工程 教 材：《C++程序設(shè)計教程：實驗手冊》，清華大學(xué)出版社，Harvery M.，Paul J.，Tem R.，2004 開課院系：計算機科學(xué)與技術(shù)系 一、實驗的性質(zhì)和任務(wù) C++是一門高效實用的程序設(shè)計語言，它既可進行過程化程序設(shè)計，也可進行面向?qū)ο蟪绦蛟O(shè)計。隨著C++逐漸成為ANSI標準，這種新的面向?qū)ο蟪绦蛟O(shè)計語言已經(jīng)成為了程序員最廣泛使用的工具。本課程是一門計算機及相關(guān)專業(yè)的重要的專業(yè)基礎(chǔ)課，開設(shè)實驗課程主要目的是使學(xué)生掌握有關(guān)C++語言的基本概念、基本語法和編程方法，理解C++語言面向?qū)ο蟮闹匾卣鳎偈箤W(xué)生理論聯(lián)系實際，能夠靈活應(yīng)用自己所學(xué)的理論知識進行程序開發(fā)，增強學(xué)生的實踐動手技能，并能夠提高學(xué)生獨立分析問題和解決問題的能力。 二、實驗的基本內(nèi)容及要求 實驗 一、C++程序的運行環(huán)境、簡單C++數(shù)據(jù)類型及運算（1學(xué)時）1． 實驗?zāi)康?/p> (1)熟悉VC++6.0集成開發(fā)環(huán)境；掌握簡單C++程序的編輯、編譯和運行 (2)熟悉和理解C＋＋語言中的數(shù)據(jù)類型、表達式；掌握簡單C++程序的編寫及調(diào)試方法 2． 實驗內(nèi)容 (1)熟悉VC++6.0集成開發(fā)環(huán)境的基本操作方法，學(xué)會獨立使用該系統(tǒng)(2)了解在該系統(tǒng)上如何編輯、編譯、連接和運行一個C++程序(3)通過運行一個簡單的C++程序，初步了解C++源程序的特點 (4)熟悉和理解C＋＋語言中的數(shù)據(jù)類型、表達式，了解基本數(shù)據(jù)類型的字節(jié)寬度和范圍表示 (5)利用學(xué)習(xí)的數(shù)據(jù)類型，編制簡單的C＋＋程序?qū)嶒灉蕚?6)初步學(xué)習(xí)程序調(diào)試方法 3． 實驗準備 (1)安裝Visual C++編譯系統(tǒng) (2)熟悉Vc++6.0編譯系統(tǒng)的使用步驟，以及簡單C++程序的編輯、編譯和運行過程(3)復(fù)習(xí)C++的基本數(shù)據(jù)類型，表達式(4)復(fù)習(xí)程序的上機調(diào)試過程 (5)根據(jù)實驗內(nèi)容要求，編寫好實驗程序 4． 實驗步驟 (1)選擇菜單“開始/程序/Microsoft Visual Studio 6.0/Microsoft Visual C++ 6.0”,得到Visual C++ 6.0啟動后的用戶界面；(2)創(chuàng)建一個新工程； (3)編寫一個簡單的C++源程序，并保存；(4)編譯連接和運行程序 (5)輸入源程序，編譯、連接直到?jīng)]有錯誤(6)運行程序，觀察程序運行結(jié)果 5． 實驗報告 （1）提交源程序 （2）舉例說明在建立源程序、編譯、連接程序時，發(fā)現(xiàn)的錯誤屬于何種類型及解決辦法 （3）改變所用變量的數(shù)據(jù)類型，觀察程序運行結(jié)果的變化并分析原因（4）寫出上機實驗體會和實驗報告 實驗 二、數(shù)組（1學(xué)時）1．實驗?zāi)康?/p> 熟練掌握一維數(shù)組和二維數(shù)組的定義、引用和初始化；掌握字符數(shù)組與字符串的關(guān)系以及字符串變量的表示，熟練字符串處理函數(shù)的應(yīng)用。2.實驗內(nèi)容 (1)有一個數(shù)組，內(nèi)放10個整數(shù)，找出最小的數(shù)和它的下標，然后把它和數(shù)組中最前面的元素對換 輸入一個n×n的矩陣，求出兩條對角線元素值之和 編寫一程序，將兩個字符串連接起來，不要strcat函數(shù) 3．實驗準備 （1）復(fù)習(xí)一維數(shù)組和二維數(shù)組的定義、引用和初始化方法，進一步了解常用字符串處理函數(shù)的使用。 （2）根據(jù)實驗內(nèi)容要求，編寫好實驗程序 4．實驗步驟 （1）輸入源程序，編譯、連接直到?jīng)]有錯誤（2）根據(jù)實驗步驟，撰寫實驗報告 5．實驗報告 （1）結(jié)合上課內(nèi)容，寫出程序，并調(diào)試程序，要給出測試數(shù)據(jù)和實驗結(jié)果（2）整理上機步驟，總結(jié)經(jīng)驗和體會（3）完成實驗報告和提交源程序 實驗 三、函數(shù)與編譯預(yù)處理（1學(xué)時）1．實驗?zāi)康?/p> 掌握函數(shù)的定義、申明和使用方法；掌握函數(shù)調(diào)用的方法；掌握全局變量、局部變量、靜態(tài)變量的使用方法；掌握編譯預(yù)處理的使用。2.實驗內(nèi)容 （1）求兩正整數(shù)的最大公約數(shù)和最小公倍速數(shù)，用一個函數(shù)求最大公約數(shù)，另一個函數(shù)求最小公倍數(shù)。要求：不使用全局變量。將最大公約數(shù)和最小公倍數(shù)在主函數(shù)中輸出。 （2）十進位制數(shù)轉(zhuǎn)換二、八和十六進制數(shù)程序。要求： a.編寫一個函數(shù)實現(xiàn)十進制數(shù)轉(zhuǎn)換其它進制數(shù)； b.在主函數(shù)中給十進制數(shù)和轉(zhuǎn)換的進位制，輸出轉(zhuǎn)換結(jié)果。 3．實驗準備 (1)復(fù)習(xí)函數(shù)的定義、申明和使用方法，熟悉函數(shù)調(diào)用和編譯預(yù)處理(2)根據(jù)實驗內(nèi)容要求，編寫好實驗程序 4．實驗步驟 (1)輸入源程序，編譯、連接直到?jīng)]有錯誤(2)根據(jù)實驗步驟，撰寫實驗報告 5．實驗報告 (1)結(jié)合上課內(nèi)容，寫出程序，并調(diào)試程序，要給出測試數(shù)據(jù)和實驗結(jié)果(2)整理上機步驟，總結(jié)經(jīng)驗和體會(3)完成實驗報告和提交源程序 實驗 四、指針（2學(xué)時）1．實驗?zāi)康?/p> 熟練掌握各種類型指針的定義、申明、引用和運算；掌握數(shù)組指針和指向數(shù)組的指針變量，以及字符串的指針和指向字符串的指針變量；了解指針與鏈表關(guān)系。2.實驗內(nèi)容 (1)編寫程序，在堆內(nèi)存中申請一個float型數(shù)組，把10個float型數(shù)據(jù)0.1、0.2、0.3?、1.0賦予該數(shù)組，然后使用float型指針輸出該數(shù)組的各元素值并求出其累加和。(2)使用指針編寫函數(shù)strcat()函數(shù)，即實現(xiàn)兩個字符串的首尾連接（將字符串str2接到str1的后面，str1最后面的‘
主站蜘蛛池模板：
亚洲欧美成人一区二区三区在线|
狠狠色狠狠色综合网老熟女|
国产精品日本亚洲欧美|
精品人妻少妇一区二区三区不卡|
人妻丝袜无码国产一区|
亚洲午夜福利在线观看|
一个人看的www免费视频在线观看|
天堂网在线最新版www中文网|
成人国产一区二区三区|
无码免费无线观看在线视频|
午夜男女爽爽影院免费视频下载|
亚洲一区二区三区日本久久九|
亚洲午夜av久久久精品影院色戒|
久久国产热精品波多野结衣av|
欧美色欧美亚洲国产熟妇|
国产精品成熟老妇女|
不卡av中文字幕手机看|
国产欧美日本亚洲精品一5区|
又白又嫩毛又多15p|
а天堂8中文最新版在线官网|
人妻熟妇乱又伦精品视频app|
国产无遮挡又黄又爽免费网站|
国模大尺度啪啪|
国产亚洲欧美日韩亚洲中文色|
久久婷婷五月综合色d啪|
亚洲av中文无码乱人伦在线r▽|
欧美性色黄大片www喷水|
国产精品久久久久久久久免费|
色妞色综合久久夜夜|
人人澡人人人人天天夜夜|
少妇真实被内射视频三四区|
人妻暴雨中被强制侵犯在线|
色综合久久成人综合网|
欧美综合自拍亚洲综合图片区|
国产精品午夜在线观看体验区|
国产亚洲精品久久久久秋霞|
亚洲熟妇色自偷自拍另类|
巨胸不知火舞露双奶头无遮挡|
久久国产精品免费一区|
国产成人无码18禁午夜福利免费|
精品国产情侣高潮露脸在线|
第二篇：C++數(shù)據(jù)結(jié)構(gòu) 大作業(yè)課程設(shè)計
第三篇：C++實驗
第四篇：c++實驗(網(wǎng)絡(luò)工程 ))