第一篇：數據結構實驗報告冊
實驗一 線性表的操作
實驗類型：驗證性 實驗要求：必修 實驗學時： 2學時
一、實驗目的：
參照給定的線性表順序表類和鏈表類的程序樣例，驗證給出的線性表的常見算法。
二、實驗要求：
1、掌握線性表順序表類和鏈表類的特點。掌握線性表的常見算法。
2、提交實驗報告，報告內容包括：目的、要求、算法描述、程序結構、主要變量說明、程序清單、調試情況、設計技巧、心得體會。
三、實驗內容：
1．設計一個靜態數組存儲結構的順序表類，要求編程實現如下任務：建立一個線性表，首先依次輸人數據元素1，2，3，…，10，然后刪除數據元素6，最后依次顯示當前線性表中的數據元素。要求采用順序表實現，假設該順序表的數據元素個數在最壞情況下不會超過10個。
第一題源代碼： #include
//定義模板類SeqList class SeqList { private: int length,x,j,data[10];public: public: SeqList()
//無參構造函數
{
length=0;
}
SeqList(T a[ ], int n)
//有參構造函數
{
for(int i=0;i data[i]=a[i]; length=n;} ~SeqList() //析構函數為空 { } 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) { if(length==0) throw“下溢”; if(i<1||i>length) throw“位置異常”; x=data[i-1]; for(j=i;j data[j-1]=data[j]; length--; return x;} void PrintList() { for(int i=0;i cout< ”; cout< void main(){ int n=10,a[10]={1,2,3,4,5,6,7,8,9,10};SeqList cout< //刪除線性表的第i個元素 //注意此處j已經是元素所在的數組下標 //遍歷線性表，按序號依次輸出各元素 -------------------------2．設計一個帶頭結點的單鏈表類，要求： (1)帶頭結點單鏈表類的成員函數包括取數據元素個數、插入元素、刪除所有值為k的元素、取數據元素。 (2)設計一個測試主函數，實際運行驗證所設計循環單鏈表類的正確性。第二題源代碼： #include struct Node { T data;Node Node //單鏈表頭指針 int length;public: LinkList() { first=new Node first->next=NULL; } LinkList(T a[],int n) //建立n個節點的指針 { Node first=new Node first->next=NULL; //初始化一個空鏈表 for(int i=0;i { s=new Node s->data=a[i]; s->next=first->next; first->next=s; } length=n; } ~LinkList() { Node while(p) { Node q=p; p=p->next; delete q; } } int 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(); // 遍歷單鏈表，按序號依次輸出個元素 };/********************************/ template p=p->next; j++;} if(!p) throw “位置”;else return p->data;} /***********************************/ template p=p->next; if(p->data==x) return i+1;} } /***********************************/ template p=p->next; j++;} if(!p) throw“位置”;else { Node s=new Node s->data=x; s->next=p->next; p->next=s;} length++;} /**************************************/ template p=p->next; j++;} if(!p||!p->next) throw“位置”;else { Node q=new Node int x; q=p->next; x=q->data; p->next=q->next; delete q; length--; return x;} } /*******************************************/ template // 遍歷單鏈表，按序號依次輸出個元素 { Node p=p->next; cout<<“第”<<(i+1)<<“個元素為：”<<(p->data)< int r[ ]={10,9,8,7,6,5,4,3,2,1}; LinkList cout<<“原表為:”< a.PrintList(); cout< a.Insert(1,-2); //執行插入操作; a.Insert(2,-1); a.Insert(3,0); cout<<“執行插入后輸出為:”< a.PrintList(); cout< a.Delete(1); a.Delete(1); a.Delete(1); cout<<“執行刪除后輸出為:”< a.PrintList(); cout< cout<<“按位查找元素:”< cout<<“第 5 個元素為: ”; cout< //查找鏈表中第 5 個元素 cout< 心得體會： 實驗二 棧、隊列、串的操作 實驗類型：驗證性 實驗要求：必修 實驗學時： 2學時 一、實驗目的： 參照給定的棧類和隊列類的程序樣例，驗證給出的棧和隊列的常見算法，并結合線性表類實現有關串的操作。 二、實驗要求： 1、掌握棧、隊列、串的特點。掌握特殊線性表的常見算法。 2、提交實驗報告，報告內容包括：目的、要求、算法描述、程序結構、主要變量說明、程序清單、調試情況、設計技巧、心得體會。 三、實驗內容： 1.堆棧類測試和應用問題。要求： 設計一個主函數實現對順序堆棧類和鏈式堆棧類代碼進行測試。測試方法為：依次把數據元素1,2,3,4,5入棧，然后出棧堆棧中的數據元素并在屏幕上顯示。第一題源代碼： #include T data[StackSize]; int top;public: SeqStack() { top=-1; } ~SeqStack() { } void push(T x); T pop(); T GetTop() { if(top!=-1) return data[top]; } bool Empty() { top=-1?(return 1):(return 0); } }; template throw “上溢”;top++;data[top]=x;} template throw “下溢”;x=data[top--];return x;} /****************************************************/ template template top=NULL;} ~LinkStack(){ while(top) { Node p=top->next; delete top; top=p; } } void push(T x);T pop();T gettop(){ if(top!=NULL) return top->data;} bool Empty(){ top==NULL?return 1:return 0;} }; template //沒有申請空間時 會出現錯誤！ s->data=x;s->next=top;top=s;} template throw “下溢”;x=top->data;p=top;top=top->next;delete p;return x;} /******************************************************/ void main(){ SeqStack for(int i=1;i<=5;i++) aa.push(i); cout<<“順序棧出棧：”;for(i=0;i<5;i++){ int k=0; k=aa.pop(); cout< ”;} cout< for(i=1;i<=5;i++) bb.push(i); cout<<“鏈式棧出棧：”;for(i=1;i<=5;i++){ int j=0; j=bb.pop(); cout< ”;} cout< 2.隊列類測試和應用問題。要求： 設計一個主函數對循環隊列類和鏈式隊列類代碼進行測試.測試方法為：依次把 1,2,3,4,5入隊，然后出隊中的數據元素并在屏幕上顯示。 第二題源代碼： #include const int QueueSize=100; /**************************************/ template int front, rear; CirQueue(){ front=rear=0;} ~ CirQueue(){ } void EnQueue(T x) { if((rear+1)% QueueSize ==front) throw “上溢”; rear=(rear+1)% QueueSize; data[rear]=x; } T GetQueue() { if(rear==front)throw “下溢”; int i=(front+1)% QueueSize; return data[i];} T DeQueue(){ if(rear==front) throw “下溢”; front=(front+1)% QueueSize; return data[front]; } };/*********************************************/ template /*********************************************/ template //隊頭隊尾指針 public: LinkQueue(); ~LinkQueue(){ } void EnQueue(T x); //將x入隊 T DeQueue(); //將隊頭元素出隊 T GetQueue() { if(front!=rear) return front->next->data; //取對頭元素 } bool Empty() //判斷鏈隊列是否為空 { front==rear?return 1:return 0;} };/***************************************/ template //創建頭結點s front=rear=s;} /***************************************/ template throw“下溢”;p=front->next;x=p->data;front->next=p->next;if(p->next==NULL) rear=front;delete p;return x;} /***********************************************/ void main(){ CirQueue a.EnQueue(i); b.EnQueue(i);} for(i = 1;i <= 5;i++){ int k,j(0); k = a.DeQueue(); j=b.DeQueue(); cout<<“循環隊列輸出：”<< k<<“ ”<<“鏈隊列輸出：”< 心得體會： 實驗三 多維數組和廣義表的操作 實驗類型：驗證性 實驗要求：必修 實驗學時： 2學時 一、實驗目的：參照給定的多維數組類和廣義表類的程序樣例，驗證給出的多維數組和廣義表的常見算法，并實現有關的操作。 二、實驗要求： 1、掌握多維數組和廣義表的特點。掌握它們的常見算法。 2、提交實驗報告，報告內容包括：目的、要求、算法描述、程序結構、主要變量說明、程序清單、調試情況、設計技巧、心得體會。 三、實驗內容： 1.設計函數建立一個n*n階的對稱矩陣。要求： （1）實現將對稱矩陣用一維數組存儲輸出。（2）實現矩陣轉置算法。（3）實現魔方陣算法。 （4）設計一個測試例子，并編寫主程序進行測試。 第一題源代碼： 1.1 #include 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++) cout< cout< } puts(“轉化后: ”); int k = 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++)cout< cout< 運行結果： 1.2 #include template struct element { int row, col;T item;}; struct SparseMatrix { element void Trans1(SparseMatrix A, SparseMatrix &B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(B.tu>0) { int pb = 0; for(int col = 0;col for(int pa = 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++; } } } int main(){ int i;SparseMatrix AA,BB;puts(“輸入行數 列數 非零元素個數”);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< cout< cout< return 0;} 運行結果： 心得體會： 實驗四 樹和二叉樹 實驗類型：驗證性 實驗要求：必修 實驗學時： 2學時 一、實驗目的： 參照給定的二叉樹類的程序樣例，驗證給出的有關二叉樹的常見算法，并實現有關的操作。 二、實驗要求： 1、掌握二叉樹、哈夫曼樹和樹的特點。掌握它們的常見算法。 2、提交實驗報告，報告內容包括：目的、要求、算法描述、程序結構、主要變量說明、程序清單、調試情況、設計技巧、心得體會。 三、實驗內容： 1．設計實現二叉樹類，要求： （1）編寫一個程序，首先建立不帶頭結點的二叉鏈式存儲結構的二叉樹，然后分別輸出按照前序遍歷二叉樹、中序遍歷二叉樹和后序遍歷二叉樹訪問各結點的序列信息，最后再測試查找函數和撤銷函數的正確性。 （2）實現二叉樹層次遍歷的非遞歸算法。 （3）假設二叉樹采用鏈式存儲結構進行存儲，編寫一個算法，輸出一個二叉樹的所有葉子結點，并統計葉子結點個數。（4）編寫求二叉樹高度的函數（5）編寫一主函數來驗證算法實現 第一題源代碼： #include struct BiNode { T data;BiNode template static int i; BiNode void Creat(BiNode { char ch; cin>>ch; if(ch=='#')root=NULL; else { root=new BiNode root->data=ch; Creat(root->lchild); Creat(root->rchild); } } void Release(BiNode { if(root!=NULL) { Release(root->lchild); Release(root->rchild); delete root; } } //前序建立擴展二叉樹 //建立一棵空樹 //生成一個結點 //遞歸建立左子樹 //遞歸建立右子樹 void PreOrder(BiNode //前序遍歷 { if(root==NULL) return;else { cout< PreOrder(root->lchild); PreOrder(root->rchild);} } void InOrder(BiNode { if(root==NULL) return;else { InOrder(root->lchild); cout<<(root->data); InOrder(root->rchild);} } void PostOrder(BiNode { if(root==NULL) return;else { InOrder(root->lchild); InOrder(root->rchild); cout<<(root->data);} } void LevelOrder(BiNode BiNode int front = 0, rear = 0; //中序遍歷二叉樹 //后序遍歷二叉樹 //采用順序隊列，并假定不會發生上溢 if(root==NULL) return; Q[++rear]=root; while(front!=rear) { BiNode cout< if(q->lchild!=NULL) Q[++rear]=q->lchild; if(q->rchild!=NULL) Q[++rear]=q->rchild; } } void showleaf(BiNode //顯示葉子節點，并統計個數 { if(root==NULL) { return; } else { if((root->lchild==NULL)&&(root->rchild==NULL)) { cout< i++; } else { showleaf(root->lchild); showleaf(root->rchild); } } } int Depth(BiNode //算法求二叉樹的深度 { if(root==NULL) return 0; else { int hl= Depth(root->lchild); int hr= Depth(root->rchild); if(hl>hr) return hl+1; else return hr+1; } } public: BiTree(){ Creat(root); } BiTree(BiNode Release(root);} void display(){ cout<<“前序遍歷二叉樹： PreOrder(root); cout< cout<<”中序遍歷二叉樹： InOrder(root); cout< cout<<“后序遍歷二叉樹： PostOrder(root); cout< cout<<”層序遍歷二叉樹： LevelOrder(root); cout< cout<<“輸出葉子節點： showleaf(root); ”;“;”;“;”; cout< cout<<“葉子節點數為：”< cout<<“樹的深度為： ”< } };template void main(){ cout<<“前序建立擴展二叉樹：”< 運行結果： 注意：實驗結束后提交一份實驗報告電子文檔 電子文檔命名為“學號+姓名”，如：E01214058宋思怡 《數據結構》實驗報告 （一）學號：姓名：專業年級： 實驗名稱：線性表 實驗日期：2014年4月14日 實驗目的： 1、熟悉線性表的定義及其順序和鏈式存儲結構； 2、熟練掌握線性表在順序存儲結構上實現基本操作的方法； 3、熟練掌握在各種鏈表結構中實現線性表基本操作的方法； 4、掌握用 C/C++語言調試程序的基本方法。 實驗內容： 一、編寫程序實現順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： （1）初始化順序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）輸出順序表L； （4）輸出順序表L長度； （5）判斷順序表L是否為空； （6）輸出順序表L的第3個元素； （7）輸出元素24的位置； （8）在L的第4個元素前插入元素0； （9）輸出順序表L； （10）刪除L的第5個元素； （11）輸出順序表L。 源代碼 調試分析（給出運行結果界面） 二、編寫程序實現單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： ???? ???? 小結或討論: （1）實驗中遇到的問題和解決方法 （2）實驗中沒有解決的問題 （3）體會和提高 南京信息工程大學實驗（實習）報告 實驗（實習）名稱數據結構實驗（實習）日期 2011-11-2得分指導教師周素萍 系公共管理系專業信息管理與信息系統年級10級班次1姓名常玲學號2010230700 3實驗一順序表的基本操作及C語言實現 【實驗目的】 1、順序表的基本操作及 C 語言實現 【實驗要求】 1、用 C 語言建立自己的線性表結構的程序庫，實現順序表的基本操作。 2、對線性表表示的集合，集合數據由用戶從鍵盤輸入（數據類型為整型），建立相應的順序表，且使得數據按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。 【實驗內容】 1、根據教材定義的順序表機構，用 C 語言實現順序表結構的創建、插入、刪除、查找等操作； 2、利用上述順序表操作實現如下程序：建立兩個順序表表示的集合（集合中無重 復的元素），并求這樣的兩個集合的并。 【實驗結果】 [實驗數據、結果、遇到的問題及解決] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅指針 // 保存pb的前驅指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結點插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲在數組中，元素之間的關系直接通過相鄰元素的位置來表達。 優點：簡單，數據元素的提取速度快； 缺點：（1）靜態存儲，無法預知問題規模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數集合中得到并集。 數據結構實驗報告 一． 題目要求 1）編程實現二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷； 3）每次對樹的修改操作和遍歷操作的顯示結果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對于前三個題目要求，我們用一個程序實現代碼如下 #include typedefintElemType; //數據類型 typedefint Status; //返回值類型 //定義二叉樹結構 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創建二叉樹函數 BiTreebst=NULL;inti=0;while(i //數據域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子樹為空重接它的左子樹 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子樹空則重新接它的右子樹 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被刪除結點的前驅 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函數 printf(“ ---------------------二叉排序樹的實現-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節點個數:”);scanf(“%d”,&num);printf(“依次輸入這些整數（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示輸入操作符************************:”);printf(“n”);printf(“ 1:插入節點 2:刪除節點 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節點:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要刪除的節點”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst); printf(“后序遍歷:n”); PostOrderNoRec(bst); printf(“樹狀圖為:n”); printtree(bst,layer); break;case 5: printf(“程序執行完畢!”); return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結構變為 typedefintElemType; //數據類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結構 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數據域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數不是key,而是另外三個 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數也類似 即可完成50個信息存儲 用數組存儲50個信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學生管理系統”< cout<<“該學號信息已經存在，添加失敗”< break;} cout<<“重新輸入添加的學號”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲存數據界面（儲存學生信息略） 創建二叉樹： 插入節點： 刪除節點： 非遞歸遍歷： 退出： 數組儲存學生信息界面 分析查找效率： 因為二叉樹查找要創建二叉樹，而數組查找只創建一個數組，二叉樹的創建時間比較長，所以對于數據量較少的情況下數組的查找效率比較高。但當數據量增加時，二叉樹的查找優勢就顯現出來。所以數據量越大的時候，二叉樹的查找效率越高。 四． 總結與改進 這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。 一開始打算用棧實現非遞歸，但是根據書里面的偽代碼發現部分是在C++編譯器里運行不了的（即使補充了頭文件和數據的定義），所以之后參考了網上的數組非遞歸，發現其功能和棧相似。 遞歸遍歷的實現比非遞歸的遍歷真的簡單很多。 開始時只看到前三問，所以沒有寫到儲存學生數據的代碼，里面還可以用clock（）函數加一個計算查找所要數據時間的代碼，讓二叉樹查找與數組查找到效率比較更加直觀。 實驗報告4 排序 一、實驗目的 1、掌握常用的排序方法，并掌握用高級語言實現排序算法的方法。 2、深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用。 3、了解各種方法的排序過程及其依據的原則，并掌握各種排序方法的時間復雜度的分析方法。 二、實驗要求及內容 要求編寫的程序所能實現的功能包括： 1、從鍵盤輸入要排序的一組元素的總個數 2、從鍵盤依次輸入要排序的元素值 3、對輸入的元素進行快速排序 4、對輸入的元素進行折半插入排序 三、實驗代碼及相關注釋 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的結構體 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的結構體 int Partition(SqList &L, int low, int high) //1 尋找基準 { L.r[0]=L.r[low];//子表的第一個記錄作基準對象 int pivotkey = L.r[low].key;//基準對象關鍵字 while(low while(low L.r[low] = L.r[high];//小于基準對象的移到區間的左側 while(low L.r[high] = L.r[low];//大于基準對象的移到區間的右側 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中遞歸地進行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //尋找基準 QuickSort(L, low, pivotloc-1);//對左序列同樣遞歸處理 QuickSort(L, pivotloc+1, high);//對右序列同樣遞歸處理 } } Sequenlist *Sqlset() //2 輸入要折半插入排序的一組元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“請輸入要排序的所有元素的總個數：”; cin>>i; cout< cout<<“請依次輸入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入點在前半區 else low=mid+1;//插入點在后半區 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“請選擇功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“請輸入要排序的所有元素的總個數：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后為：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函數功能說明 1、Sequenlist *Sqlset() 輸入要折半插入排序的一組元素 2、int Partition(SqList &L, int low, int high) 尋找快速排序的基準 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序運行結果 下圖僅為分別排序一次，可多次排序，后面有相關截圖： 六、實驗中遇到的問題、解決及體會 1、起初編寫快速排序的程序時，我是完全按照老師PPT上的算法敲上去的，然后建立了一個SqList的結構體，調試運行時出現錯誤，仔細查看才意識到Partition函數中L中應該包含元素key，而我建立結構體時沒有注意，然后我將key這個元素補充進去，繼續調試，又出現錯誤，提示我Partition沒有定義，我就覺得很奇怪，我明明已經寫了函數定義，為什么會這樣，當我又回過頭來閱讀程序時，我發現QuickSort函數中調用了Partition函數，但是我的Partition函數的定義在QuickSort函數的后面，于是我將Partition函數放到了QuickSort函數的前面，再次調試運行，就可以正常運行，得出結果了。這讓我懂得，編程一定要認真仔細，不可大意馬虎，否則又會花很多時間回過頭來檢查修改程序，得不償失。 運行程序錯誤截圖： 2、本來我是編寫了兩個程序，分別實現快速排序和折半插入排序的功能，但我后來想我是否可以將其合二為一，于是我想到用if選擇語句用來實現不同的功能，從鍵盤輸入功能選項m，if（m==1），可以進行快速排序，if（m==2），可以進行折半插入排序，于是我繼續思考，我是否可以在一次運行程序中，多次對含有不同元素的序列進行排序，于是我用了goto語句，每次排序一次后，自動循環到選擇語句，當不需要在排序的時候，可以從鍵盤輸入3，退出程序，這樣一來，程序變得更加實用和清晰明朗。這讓我懂得，想要編出好的程序，要善于思考，在實現所需功能的前提下，多想問題，看是否能使程序更加實用簡便。 修改程序前兩個運行結果截圖 （兩個程序，調試運行兩次，每次只能進行一次排序） 1、快速排序程序運行結果截圖： 2、折半插入排序程序結果截圖： 程序重要模塊修改截圖： 修改程序后運行截圖： （一個程序，調試運行一次，可多次進行不同序列的不同排序）第二篇：數據結構實驗報告
第三篇：數據結構實驗報告
第四篇：數據結構實驗報告
第五篇：數據結構實驗報告
點擊咨詢 