1、數據結構實驗實驗內容和目的：掌握幾種基本的數據結構：集合、線性結構、樹形結構等在求解實際問題中的應用，以及培養書寫規范文檔的技巧。學習基本的查找和排序技術。讓我們在實際上機中具有編制相當規模的程序的能力。養成一種良好的程序設計風格。實驗教材：數據結構題集（C語言版） 清華大學出版社 2007年實驗項目：實驗一、棧和循環隊列、實驗內容： 棧 掌握棧的特點(先進后出FILO)及基本操作,如入棧、出棧等，棧的順序存儲結構和鏈式存儲結構，以便在實際問題背景下靈活應用。本程序采用的是鏈棧結構，具有初始化一個棧、PUSH、POP、顯示所有棧里的元素四個功能。 循環隊列 掌握隊列的特點(先進先出FIFO)及

2、基本操作,如入隊、出隊等，學會循環隊列的實現，以便在實際問題背景下靈活運用。本程序具有初始化一個隊列、入隊、出隊、顯示隊列的所有元素、隊列長度五個功能。、實驗代碼 棧程序代碼：#include #include #define Stack_Size 6#define ERROR 0#define OK 1typedef int SElemType;typedef struct SNodeSElemType data;struct SNode *next;SNode,*LinkStack;int CreatTwo(LinkStack &head,int n)int i;SNode *p;head

3、=(LinkStack)malloc(sizeof(SNode);head-next=NULL;printf(請輸入數據(數字):n);for(i=n;i0;-i)p=(SNode *)malloc(sizeof(SNode);scanf(%d,&p-data);p-next=head-next;head-next=p;return 1;int menu_select()int sn;for(;)scanf(%d,&sn);if(sn6)printf(nt輸入錯誤，請重新輸入n);elsebreak;return sn;int Push(LinkStack &top,SElemType e)S

4、Node *q;q=(LinkStack)malloc(sizeof(SNode);if(!q)printf(溢出!n);return(ERROR);q-data=e;q-next=top-next;top-next=q;return(OK);int Pop(LinkStack &top,SElemType &e)SNode *q;if(!top-next)printf(error!n);return(ERROR);e=top-next-data;q=top-next;top-next=q-next;free(q);return(OK);void main() int e;LinkStack

5、top;printf(1.初始化一個棧;n2.PUSH;n3.POP;n4.顯示所有棧里的元素;n5.結束;n);while(1)switch(menu_select()case 1:if(CreatTwo(top,Stack_Size)printf(Success!n);break; case 2:printf(Push:n);scanf(%d,&e);if(Push(top,e)printf(Success!n);break;case 3:if(Pop(top,e)printf(Success!n);printf(%dn,e);break;case 4:LinkStack p;printf

6、(所有棧里的元素:n);p=top;while(p-next)p=p-next;printf(%7d,p-data);printf(n);break;case 5:return;運行結果： 循環隊列程序代碼：#include#include#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef structint *elem;/隊列存儲空間int front;int rear;SqQueue;/判斷選擇是否正確int menu_select()int sn;for(;)scanf(%d,&sn);if(s

7、n6)printf(nt輸入錯誤，請重新輸入n);elsebreak;return sn;/參數(傳出)SqQueue &Q,循環隊列(空)int InitQueue(SqQueue &Q)Q.elem=(int *)malloc(MAXSIZE*sizeof(int);if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;iMAXSIZE;i+)Q.elemi=-1;return OK;/返回Q的元素個數int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

8、/顯示隊列的元素void Display(SqQueue Q)for(int i=0;i=QueueLength(Q);i+)if(Q.elemi!=-1)printf(%d ,Q.elemi);printf(n);/入隊int EnQueue(SqQueue &Q,int e)Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear=Q.front)return ERROR;Q.elemQ.rear=e;return OK;/出隊int DeQueue(SqQueue &Q,int &e)if(Q.front=Q.rear)return ERROR;e=Q.elemQ.fron

9、t+1;Q.elemQ.front+1=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;void main()SqQueue Q;InitQueue(Q);int elem,e;printf(請輸入隊列元素(以0結束):n);scanf(%d,&elem);while(elem!=0)EnQueue(Q,elem);scanf(%d,&elem);printf(隊列為：n);Display(Q);printf(1.初始化一個隊列;n2.入隊;n3.出隊;n4.顯示隊列的所有元素;n5.隊列長度:n6.結束;n);while(1)switch(menu_sele

10、ct()case 1:printf(請輸入隊列元素(以0結束):n);scanf(%d,&elem); while(elem!=0)EnQueue(Q,elem); scanf(%d,&elem);printf(隊列為：n);Display(Q);fflush(stdin);break; case 2:scanf(%d,&elem);EnQueue(Q,elem);printf(隊列為：n);Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf(隊列為：n);Display(Q);break;case 4:printf(n隊列

11、的所有元素:n);Display(Q);break;case 5:printf(%dn,QueueLength(Q);break;case 6:return;運行結果：實驗二、數組、實驗內容： 數組一般不做插入或刪除操作，也就是說，一旦建立了數組，則結構中的數據元素個數和元素之間的關系就不再發生變動。本程序數組的大小定義為3*3，可以通過修改“#define M”來變動。本程序具有矩陣相加、矩陣A轉置、矩陣B轉置、矩陣相乘四個功能。、實驗代碼：#include #define M 3void MatrixAdd(int m1MM,int m2MM,int resultMM)/兩個矩陣m1和m2

12、相加,結果放到resultint i,j;for (i=0;iM;i+)for(j=0;jM;j+)resultij=m1ij+m2ij;void MatrixTrams(int m1MM,int resultMM)/矩陣轉置int i,j;for (i=0;iM;i+)for (j=0;jM;j+)resultij=m1ji;void MatrixMultiply(int m1MM,int m2MM,int resultMM)int i,j;for (i=0;iM;i+)for (j=0;jM;j+)resultij=0;for (int k=0;kM;k+)resultij+=m1ik*m

13、2kj;void Display(int resultMM)/顯示矩陣int i,j;for (i=0;iM;i+)for(j=0;jM;j+)printf(%-5d,resultij);printf(n);void main()int AMM,BMM;int i,j;printf(請輸入第一個矩陣：n);for(i=0;iM;i+)for(j=0;jM;j+)scanf(%d,&Aij);printf(請輸入第二個矩陣：n);for(i=0;iM;i+)for(j=0;jM;j+)scanf(%d,&Bij);int resultMM;/*printf(n 矩陣A:n);Display(A)

14、;printf(n 矩陣B:n);Display(B);*/printf(請選擇：n1.矩陣相加：n2.矩陣A轉置：n3.矩陣B轉置：n4.矩陣相乘：n5.退出。nn);while (1)int l;scanf(%d,&l);switch(l)case 1:printf(矩陣相加的運算結果：n);MatrixAdd(A,B,result);Display(result);printf(n);break;case 2:printf(矩陣A轉置的運算結果：n);MatrixTrams(A,result);Display(result);printf(n);break;case 3:printf(矩

15、陣B轉置的運算結果：n);MatrixTrams(B,result);Display(result);printf(n);break;case 4:printf(矩陣相乘的運算結果：n);MatrixMultiply(A,B,result);Display(result);printf(n);break;case 5:printf(退出。n);return;default:printf(輸入錯誤！);printf(n);實驗結果：實驗三、查找1 、實驗內容掌握各種查找（順序、二分法、查找樹、哈希）方法及適用場合，并能在解決實際問題時靈活應用。本實驗采用二分查找。二分查找又稱折半查找，它是一種效

16、率較高的查找方法。折半查找法的優點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。本程序具有找出數據位置和顯示查找次數兩個功能。、實驗代碼：#include #define MAX 100void main()int rMAX,i,k,low,high,mid,m,n;printf(nn 建立遞增有序的查找順序表（以-1結束）：n);for(i=0;iMAX;i+)scanf(%d,&ri);if(ri=-1)n=i;break;printf(n 請輸入要查找的數據：n);scanf(%d,&k);low

17、=0;high=n-1;m=0;while(lowk)high=mid-1;elseif(rmidhigh)printf(沒有找到n);printf(共進行%d次比較。n,m);if(rmidk)mid+;printf(可將這個數插入到第%d個數的后面。n,mid);else printf(n 要找的數據=%d在第%d個數的位置上。n,k,mid+1); printf(nn 共進行了%d次比較。n,m);實驗結果：實驗四、樹1 、實驗內容：進一步掌握樹的結構及非線性特點，遞歸特點和動態性；進一步鞏固對指針的使用和二叉樹的三種遍歷方法、建立方法及用廣義表進行輸入輸出。本程序將第一個元素作為樹根，

18、其余元素若小于樹根則為左子樹，若大于樹根則為右子樹。本程序具有求左子樹、求右子樹、求深度、先序遍歷、中序遍歷（遞歸算法）、中序遍歷（非遞歸算法）、后序遍歷六個功能。、實驗代碼/描述：兩個指針指向左右孩子，算法見教材#include #include #define MAX 50typedef struct btnodeint Data;struct btnode *Llink;struct btnode *Rlink;btnode,*btreetype;btreetype CreatTree(int n)/傳入數據數量，返回根結點指針int i;btreetype root=NULL;for

19、(i=0;iData);newNode-Llink=NULL;newNode-Rlink=NULL;currentNode=root;if(currentNode=NULL)root=newNode;elsewhile (currentNode!=NULL)parentNode=currentNode;if(newNode-DataData)currentNode=currentNode-Llink;elsecurrentNode=currentNode-Rlink;if(newNode-DataData)parentNode-Llink=newNode;elseparentNode-Rlin

20、k=newNode;return root;void OutputTree(btreetype &root)btreetype p;p=root-Llink;printf(建立的二叉樹的左子樹為：n);while (p!=NULL)printf(%-8d,p-Data);p=p-Llink;p=root-Rlink;printf(n建立的二叉樹的右子樹為：n);while (p!=NULL)printf(%-8d,p-Data);p=p-Rlink;int depth(btreetype root)btreetype p;p=root;int dep1;int dep2;if(root=NUL

21、L)return 0;elsedep1=depth(p-Llink);dep2=depth(p-Rlink);if(dep1dep2)return(dep1+1);else return(dep2+1);void PreOrder(btreetype &root)/先序遍歷（遞歸）btreetype p;p=root;if (p!=NULL)printf(%-5d,p-Data);PreOrder(p-Llink);PreOrder(p-Rlink);void InOrder(btreetype &root)/中序遍歷（遞歸）btreetype p;p=root;if (p!=NULL)InOrder(p-Llink);