數(shù)據(jù)結(jié)構(gòu)實驗報告冊

實驗一線性表的操作實驗類型：驗證性實驗要求：必修實驗學時：2學時一、實驗目的：參照給定的線性表順序表類和鏈表類的程序樣例，驗證給出的線性表的常見算法。二、實驗要求：1、掌握線性表順序表類和鏈表類的特點。掌握線性表的常見算法。2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明程序清單、調(diào)試情況、設計技巧、心得體會。三、實驗內(nèi)容：1．設計一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類，要求編程實現(xiàn)如下任務：建立一個線性表，首先依次輸人數(shù)據(jù)元素1,2,3,???，10,然后刪除數(shù)據(jù)元素6,最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過10個。第一題源代碼：#include<iostream>usingnamespacestd;template<classT>classSeqList{第一題源代碼：#include<iostream>usingnamespacestd;template<classT>classSeqList{private:intlength,x,j,data[10];public:public:SeqList(){length=0;}SeqList(Ta[],intn){for(inti=0;i<n;i++)data[i]=a[i];length=n;}~SeqList(){}intLength(){returnlength;//定義模板類SeqList//無參構(gòu)造函數(shù)//有參構(gòu)造函數(shù)//析構(gòu)函數(shù)為空//求線性表的長度}TGet(inti){}}TGet(inti){}intLocate(Tx){}voidInsert(inti,Tx){}TDelete(inti){if(length==0)throw"下溢"；if(i<1||i>length)throw"位置異常"；x=data[i-1]；for(j=i；j<length；j++)data[j-1]=data[j]；length--；returnx；}voidPrintList(){for(inti=0；i<length；i++)cout<<data[i]<<""；cout<<endl；}}；voidmain(){intn=10,a[10]={1,2,3,4,5,6,7,8,9,10}；SeqList<int>theseqlist(a,n)；coutvv"刪除前元素：";for(inti=0；i<n；i++)cout<<a[i]<<" "；〃按位查找，取線性表的第i個元素〃按值查找，求線性表中值為x的元素序號//在線性表中第i個位置插入值為x的元素//刪除線性表的第i個元素〃注意此處j已經(jīng)是元素所在的數(shù)組下標//遍歷線性表，按序號依次輸出各元素cout<<endl；theseqlist.Delete(6)；theseqlist.PrintList()；}運行結(jié)果：

2.設計一個帶頭結(jié)點的單鏈表類，要求：帶頭結(jié)點單鏈表類的成員函數(shù)包括取數(shù)據(jù)元素個數(shù)、插入元素、刪除所有值為k的元素、取數(shù)據(jù)元素。設計一個測試主函數(shù)，實際運行驗證所設計循環(huán)單鏈表類的正確性。第二題源代碼：#includeviostream>usingnamespacestd;templatevclassT>structNode{Tdata;NodevT>*next;}；template<classT>classLinkList{〃單鏈表頭指針private:〃單鏈表頭指針Node<T>*first;intlength;public:LinkList(){first=newNode<T>;first->next=NULL;}LinkList(Ta[],intn) 〃建立n個節(jié)點的指針{〃初始化一個空鏈表Node<T>*s;first=newNode<T>;first->next=NULL;for(inti=0;ivn;i++)〃初始化一個空鏈表{s=newNode<T>;

s->data=a[i];s->next=first->next;first->next=s;}length=n;}~LinkList(){Node<T>*p=first;while(p){Node<T>*q;q=p;p=p->next;deleteq;}//求單鏈表長度//求單鏈表長度〃取單鏈表第i個節(jié)點元素值//求單鏈表值為x的元素序號//在單鏈表中第i個位置插入元素值x的節(jié)點〃在單鏈表中刪除第i個節(jié)點//遍歷單鏈表，按序號依次輸出個元素intLength();TGet(inti);intLocate(Tx);voidInsert(inti,Tx);TDelete(inti);voidPrintList();};template<classT>intLinkList<T>::Length(){returnlength;}template<classT>TLinkList<T>::Get(inti){intj;Node<T>*p;p=first->next;j=1;while(p&&j<i){p=p->next;j++;if(!p)throw"位置";elsereturnp->data;}template<classT>intLinkList<T>::Locate(Tx){Node<T>*p;p=first;for(inti=0;i<length;i++){p=p->next;if(p->data==x)returni+1;}}template<classT>voidLinkList<T>::Insert(inti,Tx){Node<T>*p;intj;p=first;j=0;while(p&&j<i-1){p=p->next;j++;}if(!p)throw"位置"；else{Node<T>*s；s=newNode<T>；s->data=x；s->next=p->next；p->next=s；}length++；

template<classT>TLinkList<T>::Delete(inti){Node<T>*p;intj;p=first;j=0;while(p&&j<i-1){p=p->next;j++;}if(!p||!p->next)throw"位置"；else{Node<T>*q；q=newNode<T>；intx；q=p->next；x=q->data；p->next=q->next；deleteq；length--；returnx；}//遍歷單鏈表，按序號依次輸出個元素template<classT>voidLinkList<T>::PrintList()//遍歷單鏈表，按序號依次輸出個元素Node<T>*p；p=first；for(inti=0；i<length；i++){p=p->next；coutvv"第"vv(i+l)vv"個元素為："vv(p->data)vvendl;}}

voidmain(){intr[]={10,9,8,7,6,5,4,3,2,l};LinkList<int>a(r,10);coutvv"原表為:"vvendl;a.PrintList();coutvvendl;a.Insert(1,-2); 〃執(zhí)行插入操作；a.Insert(2,-1);a.Insert(3,0);coutvv"執(zhí)行插入后輸出為:"vvendl;a.PrintList();coutvvendl;a.Delete(1);a.Delete(1);a.Delete(1);coutvv"執(zhí)行刪除后輸出為:"vvendl;a.PrintList();coutvvendl;coutvv"按位查找元素:"vvendl;coutvv"第5個元素為:";coutvva.Get(5)vvendl; 〃查找鏈表中第5個元素coutvvendl;}運行結(jié)果:日柯日刼Q九^31N日91寧±----S3---JJ_=芻尋為^聶一.-

主T詵十主ryT'v

±.2345;EPaFF5

--,■wgg穽二■個II-.'-rl6.;ba”4,7,ii￥—丄X:F.'-—w'k-'l..Hu'T'i!*】Ef^gggF^kFkFfe-fe^kgFfe-Ef^gggr需kgFfe-fefe-F【uin二r:=mMl=■柯Jp甘亠SIJS""^7>>于>寧-￥>于.j￡u^^-=去>■壬畫■aQl-.—11YM」2:t

B9丄丄rlrl心得體會：實驗二棧、隊列、串的操作實驗類型：驗證性實驗要求：必修實驗學時：2學時一、實驗目的：參照給定的棧類和隊列類的程序樣例，驗證給出的棧和隊列的常見算法，并結(jié)合線性表類實現(xiàn)有關(guān)串的操作。二、實驗要求：1、掌握棧、隊列、串的特點。掌握特殊線性表的常見算法。2、提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明程序清單、調(diào)試情況、設計技巧、心得體會。三、實驗內(nèi)容：1.堆棧類測試和應用問題。要求：設計一個主函數(shù)實現(xiàn)對順序堆棧類和鏈式堆棧類代碼進行測試。測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入棧，然后出棧堆棧中的數(shù)據(jù)元素并在屏幕上顯示。第一題源代碼：#include<iostream>usingnamespacestd;、、、、、、、constintStackSize=10;template<classT>classSeqStack{private:Tdata[StackSize];inttop;public:SeqStack(){top=-1;}~SeqStack(){}voidpush(Tx);Tpop();TGetTop(){if(top!=-1)returndata[top];}boolEmpty(){top=-1?(return1):(return0);}};template<classT>voidSeqStack<T>::push(Tx){if(top==StackSize-1)throw"上溢";top++;data[top]=x;}template<classT>TSeqStack<T>::pop(){Tx;if(top==-1)throw"下溢";x=data[top--];returnx;}/template<classT>structNode{Tdata;Node<T>*next;};template<classT>classLinkStack{private:Node<T>*top;public:LinkStack(){top=NULL;}~LinkStack(){while(top){Node<T>*p;p=top->next;deletetop;top=p;}}voidpush(Tx);Tpop();Tgettop(){if(top!=NULL)returntop->data;}boolEmpty(){top==NULL?return1:return0;}};template<classT>voidLinkStack<T>::push(Tx){Node<T>*s;s=newNode<T>; //沒有申請空間時會出現(xiàn)錯誤s->data=x;s->next=top;top=s;}template<classT>TLinkStack<T>::pop(){Tx;Node<T>*p;if(top==NULL)throw"下溢";x=top->data;p=top；top=top->next;deletep;returnx;}voidmain(){SeqStackvint>aa;LinkStackvint>bb;for(inti=l;iv=5;i++)aa.push(i);coutvv"順序棧出棧："for(i=0;i<5;i++){intk=0;k=aa.pop();coutvvkvv"";}coutvvendl;for(i=1;i<=5;i++)bb.push(i);coutvv"鏈式棧出棧："for(i=1;iv=5;i++){intj=0;j=bb.pop();coutvvjvv"";}coutvvendl;}運彳丁結(jié)果:2.隊列類測試和應用問題。要求：設計一個主函數(shù)對循環(huán)隊列類和鏈式隊列類代碼進行測試.測試方法為：依次把1,2,3,4,5入隊，然后出隊中的數(shù)據(jù)元素并在屏幕上顯示。第二題源代碼：#include<iostream>#include<string>usingnamespacestd;constintQueueSize=100;template<classT>classCirQueue{public:Tdata[QueueSize];intfront,rear;CirQueue(){front=rear=0;}~CirQueue(){}voidEnQueue(Tx){if((rear+1)%QueueSize==front)throw上"溢";rear=(rear+1)%QueueSize;data[rear]=x;}TGetQueue(){if(rear==front)thTO溢"'；inti=(front+1)%QueueSize;returndata[i];}TDeQueue(){if(rear==front)throw下"溢";front=(front+1)%QueueSize;returndata[front];

};template<classT>structNodeTdata;Node<T>*next;};template<classT>classLinkQueue//隊頭隊尾指針//隊頭隊尾指針〃將x入隊//將隊頭元素出隊//取對頭元素//判斷鏈隊列是否為空Node<T>*front,*rear;public:LinkQueue();~LinkQueue()voidEnQueue(Tx);TDeQueue();TGetQueue()if(front!=rear)returnfront->next->data;boolEmpty()front==rear?return1:return0;};template<classT>LinkQueue<T>::LinkQueue()〃創(chuàng)建頭結(jié)點s〃創(chuàng)建頭結(jié)點stemplate<classT>voidLinkQueue<T>::EnQueue(Tx){Node<T>*s;s=newNode<T>;s->data=x;s->next=NULL;rear->next=s;rear=s;、、、、、、、、、、、、、template<classT>TLinkQueue<T>::DeQueue(){Node<T>*p;Tx;if(rear==front)throw"下溢"；p=front->next;x=p->data；front->next=p->next；if(p->next==NULL)rear=front；deletep；returnx；}voidmain(){CirQueue<int>a；LinkQueue<int>b；for(inti=1；i<=5；i++){a.EnQueue(i)；b.EnQueue(i)；}for(i=1；i<=5；i++){intk,j(0)；k=a.DeQueue()；j=b.DeQueue()；"vvjvvendl；coutvv"循環(huán)隊列輸出："vvkvv""<<"鏈隊列輸出:"vvjvvendl；}試驗結(jié)果：C:\DOCU1EKTS1KDSETTIMGS\ABIIMISTRATOK\MWX^據(jù)1歹歹歹歹歹

鏈鏈鏈鏈鏈o1234Et歹歹歹歹歹

鏈鏈鏈鏈鏈o1234Et V出他嵋吧歹歹歹歹歹ahl-j..Jhl-)...?hl-j..JFi-;ly3r、r、3桿桿刁?Erm-m-m-m-m-心得體會：實驗三多維數(shù)組和廣義表的操作實驗類型：驗證性實驗要求：必修實驗學時：2學時一、 實驗目的：參照給定的多維數(shù)組類和廣義表類的程序樣例，驗證給出的多維數(shù)組和廣義表的常見算法，并實現(xiàn)有關(guān)的操作。二、 實驗要求：1、 掌握多維數(shù)組和廣義表的特點。掌握它們的常見算法。2、 提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設計技巧、心得體會。三、 實驗內(nèi)容：設計函數(shù)建立一個n*n階的對稱矩陣。要求：（1） 實現(xiàn)將對稱矩陣用一維數(shù)組存儲輸出。（2） 實現(xiàn)矩陣轉(zhuǎn)置算法。（3） 實現(xiàn)魔方陣算法。（4） 設計一個測試例子，并編寫主程序進行測試。第一題源代碼：1.1#includeviostream>usingnamespacestd;inta[10][10];intsave[100];intmain（）{intn,i,j;puts（"輸入矩陣的維數(shù)N”）；cin>>n;for（i=0;i<n;i++）for（j=0;j<n;j++）{a[i][j]=rand（）%10+1;a[j][i]=a[i][j];

}for(i=0;i<n;i++){for(j=0;j<n;j++)coutvva[i][j]vv"\t";coutvvendl;}puts(”轉(zhuǎn)化后：");intk=0;for(i=0;i<n;i++)for(j=0;j<=i;j++){k=i*(i+1)/2+j;save[k]=a[i][j];k++; }for(i=0;i<n*(n+1)/2;i++)coutvvsave[i]vv""coutvvendl;return0;}運彳丁結(jié)果：'=!：l■-^C:kDocu?entsandSel+irkgs\.Ad?iTListratoirY桌63842tocontinue輸入矩陣的維數(shù)63842tocontinue需侷0 5 9Pi'-essAnykey1.2#includeviostream>usingnamespacestd;constintMaxTerm=100;template<classT>structelement{introw,col;Titem;};structSparseMatrix{element<int>data[MaxTerm];intmu,nu,tu;};voidTrans1(SparseMatrixA,SparseMatrix&B){B.mu=A.nu；B.nu=A.mu；B.tu=A.tu；if(B.tu>0){intpb=0；for(intcol=0；col<A.nu；col++)for(intpa=0；pa<A.tu；pa++)if(A.data[pa].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++；}}}intmain(){inti;SparseMatrixAA,BB;puts(”輸入行數(shù)列數(shù)非零元素個數(shù)”)；cin>>AA.mu>>AA.nu>>AA.tu;puts("輸入三元表:")； 〃puts()與cout一樣for(i=0；i<7；i++){cin>>AA.data[i].row；cin>>AA.data[i].col；cin>>AA.data[i].item；}Trans1(AA,BB)；puts("輸出三元表心”)；for(i=0；i<7；i++){cout<<BB.data[i].row<<"\t"；cout<<BB.data[i].col<<"\t"；cout<<BB.data[i].item<<"\t"<<endl；}return0；}運行結(jié)果："C:\Bocu>ent:sandSettings\Ad|輸入行數(shù)列數(shù)非零元素不礦567輸入三元表：0e15032205-151111123*3￡4Q91輸出=元表門0Q15491k111*13Q22□260-15Pressany血勺tocontinuc心得體會:實驗四樹和二叉樹實驗類型：驗證性實驗要求：必修實驗學時：2學時一、 實驗目的：參照給定的二叉樹類的程序樣例，驗證給出的有關(guān)二叉樹的常見算法，并實現(xiàn)有關(guān)的操作。二、 實驗要求：1、 掌握二叉樹、哈夫曼樹和樹的特點。掌握它們的常見算法。2、 提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設計技巧、心得體會。三、 實驗內(nèi)容：1.設計實現(xiàn)二叉樹類，要求：編寫一個程序，首先建立不帶頭結(jié)點的二叉鏈式存儲結(jié)構(gòu)的二叉樹，然后分別輸出按照前序遍歷二叉樹、中序遍歷二叉樹和后序遍歷二叉樹訪問各結(jié)點的序列信息，最后再測試查找函數(shù)和撤銷函數(shù)的正確性。實現(xiàn)二叉樹層次遍歷的非遞歸算法。假設二叉樹采用鏈式存儲結(jié)構(gòu)進行存儲，編寫一個算法，輸出一個二叉樹的所有葉子結(jié)點，并統(tǒng)計葉子結(jié)點個數(shù)。編寫求二叉樹高度的函數(shù)編寫一主函數(shù)來驗證算法實現(xiàn)

第一題源代碼：#include<iostream>usingnamespacestd;template<classT>structBiNode{Tdata;BiNode<T>*lchild,*rchild;};template<classT>classBiTree{private:staticinti;//前序建立擴展二叉樹//建立一棵空樹//前序建立擴展二叉樹//建立一棵空樹//生成一個結(jié)點//遞歸建立左子樹//遞歸建立右子樹voidCreat(BiNode<T>*&root){charch;cin>>ch;if(ch=='#')root=NULL;else{root=newBiNode<T>;root->data=ch;Creat(root->lchild);Creat(root->rchild);}}voidRelease(BiNode<T>*root){if(root!=NULL){Release(root->lchild);Release(root->rchild);deleteroot;}}voidPreOrder(BiNode<T>*root){if(root==NULL)return;else//前序遍歷{cout<<root->data;PreOrder(root->lchild);PreOrder(root->rchild);}}voidInOrder(BiNode<T>*root){if(root==NULL)return;else{InOrder(root->lchild);cout<<(root->data);InOrder(root->rchild);}}//中序遍歷二叉樹voidPostOrder(BiNode<T>*root){if(root==NULL)return;else{InOrder(root->lchild);InOrder(root->rchild);cout<<(root->data);}}voidLevelOrder(BiNode<T>*root){//后序遍歷二叉樹BiNode<T>*Q[100];intfront=0,rear=0;//采用順序隊列，并假定不會發(fā)生上溢if(root==NULL)return;Q[++rear]=root;while(front!=rear){BiNode<T>*q=Q[++front];