数据结构与算法上机实验报告.doc

数据结构与算法B上机实验报告第1次2011-10-02顺序表的实现和基本操作第2次2011-10-29二叉树的实现和递归遍历第3次2011-11-23内部排序第4次2011-12-dd实现图从邻接矩阵到邻接表存储转化第一次 线性表数据结构一、上机实习题目线性链表操作插入、删除、合并、排序、查找二 数据结构设计（算法设计）源程序（#include #define MaxSize 100using namespace std;typedef int ElemType;class SeqList ElemType listMaxSize;int length;public: SeqList() length=0; void SeqListSort(int i,ElemType x); void SeqListCreat(int n); void SeqListInset(int i,ElemType x); void SeqListDelete(int i); void SeqListMerge(); int GetLength()return length; int SeqListFind(ElemType x); int SeqListIsEmpty(); void SeqListPrint(); Mylist1,Mylist2;/创建顺序表 void SeqList:SeqListCreat(int n) ElemType x;cout请输入数据元素:;for (int i=0;ix;listi=x;length+; /对顺序表进行排序void SeqList:SeqListSort(int i,ElemType x) for(int k=0;klength;k+) for(i=k+1;ilisti) x=listk; listk=listi; listi=x; /在顺序表L中的第i个位置插入新元素xvoid SeqList:SeqListInset(int i,ElemType x)int k;if(length=MaxSize)cout表已满，无法插入！endl;else if(ilength)cout参数i不合理！=i;k-)listk=listk-1;listi-1=x;length+; /删除第i个位置的数据元素void SeqList:SeqListDelete(int i)int k;if(!SeqListIsEmpty()cout表已空，无法删除！endl;else if(ilength)cout参数i不合理！endl;elsefor(k=i-1;klength;k+)listk=listk+1;length-; /查找元素x在表中的位置int SeqList:SeqListFind(ElemType x) int i=0;while(ilength)return -1;else return i+1;/判断顺序表是否为空int SeqList:SeqListIsEmpty()if(length=0)return 0;else return 1;/将顺序表显示在屏幕上void SeqList:SeqListPrint()if(!SeqListIsEmpty()cout空表！endl;elsefor(int i=0;ilength;i+)coutlisti ;coutendl; int main() SeqList Mylist1,Mylist2; int i,n,flag=1,select;ElemType x;cout1. 建立顺序表n;cout2. 对顺序表进行排序n; cout3. 求x数值的位置n;cout4. 在第i个位置插入新元素xn;cout5. 删除第i个位置上的数值n;cout6. 将两个顺序表合并n; cout7. 退出n;coutendl;while (flag)coutselect;switch(select)case 1: coutn; Mylist1.SeqListCreat(n); cout你所输入的顺序表1为：; Mylist1.SeqListPrint(); coutn; Mylist2.SeqListCreat(n); cout你所输入的顺序表2为：; Mylist2.SeqListPrint(); break; case 2: coutn; if(n=1) Mylist1.SeqListSort(i,x); cout排序后的顺序表1为:; Mylist1.SeqListPrint(); else Mylist2.SeqListSort(i,x); cout排序后的顺序表2为:; Mylist2.SeqListPrint(); break;case 3: coutx; i=Mylist1.SeqListFind(x); if(i!=-1) coutx的位置为：iendl; else cout没有找到！; break;case 4: coutix; Mylist1.SeqListInset(i,x); cout插入后的顺序表为:; Mylist1.SeqListPrint(); break;case 5: couti; Mylist1.SeqListDelete(i); cout删除后的顺序表为：; Mylist1.SeqListPrint(); break; case 6: cout合并后的顺序表为：n; Mylist1.SeqListPrint(); Mylist2.SeqListPrint(); break; case 7: flag=0; break; 三 运行结果为：四、上机环境和使用语言（计算机程序实现）Visual C+。 使用语言：C+五、上机总结（体会提高）总的来说，这次让我感触最深的就是C+挺麻烦的，应该说我还是太不熟悉了，以前没有怎么接触过，通过这次实验，我初步掌握了一点点的C+的基础，往后我要多花点时间学习。再者，通过这次实验，我也掌握了对于线性表的的表示，使用，特别是顺序表。但是对于链表还是有待提高。六、参考资料据结构与算法分析教材，据结构（C语言版），软件开发技术基础（第二版）。同时还有网上的一些资源。当然还有同学之间的探讨。第二次：非线性表数据结构一、上机实习题目编写的递归算法，交换二叉树的左右子树。二 数据结构设计（算法设计）源程序#include#include#define N 9typedef struct binode int data; struct binode *lchild,*rchild;/指向左右孩子的指针binode,*bitree;/结点与指针typedef struct bitree elem100; int top;stack;bitree creat_bt()/按先序建二叉树 bitree t; int i,x=0;/一颗N个结点的二叉树t scanf(%d,&x); if(x=100)/输入100作为结束该结点，而不是用循环 t=NULL; else t=(bitree)malloc(sizeof(binode); t-data=x; printf(请输入%d结点的左子结点,t-data); t-lchild=creat_bt(); printf(请输入%d结点的右子结点,t-data); t-rchild=creat_bt(); return t;bitree exchange(bitree t) /递归左、右子树交换bitree p; if(t!=NULL) p=t-lchild; t-lchild=t-rchild; t-rchild=p; exchange(t-lchild); exchange(t-rchild); return t;void preorder(bitree bt) /递归的先序遍历 if (bt) printf(% d,bt-data); preorder(bt-lchild); preorder(bt-rchild);main()bitree root;/一颗树rootprintf(n);printf(输入二叉树的元素：);root=creat_bt();printf(交换前的先序序列是：);preorder(root);exchange(root);printf(n交换后的先序序列是：);preorder(root);printf(n);三 运行结果为：四、上机环境和使用语言（计算机程序实现）Visual C+。 使用语言：C Win7操作系统五、上机总结（体会提高）通过这次实验，个人觉得对于二叉树的定义和主要特性有了更深的了解，当然对于二叉树的一些基本操作处理也有了一定的掌握。同时也更熟练的使用递归算法。六、参考资料据结构与算法分析教材，数据结构（C语言版），软件开发技术基础（第二版）。同时还有网上的一些资源。当然还有同学之间的探讨。第三次 算法一、上机实习题目编写一个程序，程序中包括各种排序算法，希尔排序，冒泡排序，快速排序等，用这些算法对数据进行排序处理。二 数据结构设计（算法设计）源程序#include using namespace std;void BiInsertsort(int r, int n) /插入排序（折半） for(int i=2;i=n;i+) if (riri-1) r0 = ri; /设置哨兵 int low=1,high=i-1; /折半查找 while (low=high) int mid=(low+high)/2; if (r0high;j-) rj+1 = rj; /后移 rj+1 = r0; for(int k=1;k=n;k+) coutrk ; cout=1;d=d/2) /以d为增量进行直接插入排序 for (int i=d+1;i0 & r0rj; j=j-d) rj+d = rj; /记录后移d个位置 rj+d = r0; for(int i=1;i=n;i+) coutri ; coutn;void BubbleSort(int r, int n) /起泡排序 int temp,exchange,bound; exchange=n; /第一趟起泡排序的范围是r0到rn-1 while (exchange) /仅当上一趟排序有记录交换才进行本趟排序 bound=exchange; exchange=0; for (int j=1; jrj+1) temp=rj; rj=rj+1; rj+1=temp; exchange=j; /记录每一次发生记录交换的位置 for(int i=1;i=n;i+) coutri ; coutn;int Partition(int r, int first, int end) /快速排序一次划分 int i=first; /初始化 int j=end; r0=rfirst; while (ij) while (ij & r0= rj) j-; /右侧扫描 ri=rj; while (ij & ri= r0) i+; /左侧扫描 rj=ri; ri=r0; return i; /i为轴值记录的最终位置void QuickSort(int r, int first, int end) /快速排序 if (firstend) /递归结束 int pivot=Partition(r, first, end); /一次划分 QuickSort(r, first, pivot-1);/递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); /递归地对右侧子序列进行快速排序 void SelectSort(int r , int n) /简单选择排序 int i,j,index,temp; for (i=1; in; i+) /对n个记录进行n-1趟简单选择排序 index=i; for (j=i+1; j=n; j+) /在无序区中选取最小记录 if (rjrindex) index=j; if (index!=i) temp=ri; ri=rindex; rindex=temp; for(i=1;i=n;i+) coutri ; coutn;void main() const int numv=12; int a3numv=0,6,13,19,23,37,39,41,45,48,58,86,0,86,58,48,45,41,39,37,23,19,13,6,0,23,13,48,86,19,6,41,58,37,45,39; int z1numv,z2numv; int m,n; cout请选择测试数据类型：正序 逆序 随机 若跳出,请按 m; while(m0&m4) cout请选择排序算法：直接插入排序 希尔排序 冒泡排序 快速排序 n 简单选择排序n; switch(n) case 1: cout 直接插入排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n直接插入排序结果为： n; BiInsertsort(am-1,numv-1); break; case 2: cout n希尔排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n希尔排序结果为： n; ShellSort(am-1, numv-1); break; case 3: cout n冒泡排序前： n; for(int k=1;knumv;k+) coutam-1k ; cout n冒泡排序结果为： n; BubbleSort(am-1, numv-1); break; case 4: cout n快速排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n快速排序结果为： n; QuickSort(am-1,0,numv-1); for(int i=1;inumv;i+) coutam-1i ; coutn; break; case 5: cout n简单选择排序前： n; for(int j=1;jnumv;j+) coutam-1j ; cout n简单选择排序结果为： n; SelectSort(am-1,numv-1); break; default: cout输入错误！endl; m=0; cout请选择测试数据类型：正序 逆序 随机 若跳出,请按 m; if(m=4) cout(*_*) 再见！endl; else cout输入错误！endl;三 运行结果为：对于各种排序方法的时间复杂度T(n)的分析：排序方法T（n）排序方法T(n)简单排序O（）堆排序O(nlog n)排序方法T（n）排序方法T（n）快速排序O(nlog n)归并排序O(nlog n)排序方法T（n）排序方法T（n）直接插入排序O（）冒泡排序O（）四、上机环境和使用语言（计算机程序实现）Visual C+。 使用语言：C+ Win7操作系统五、上机总结（体会提高）通过这次实验，感受最深的就是对于各种排序算法有了更深的了解和掌握。同时也对他们之间的差别有了更深的认识。原来对数据进行排序也可以有声有色！六、参考资料据结构与算法分析教材，数据结构（C语言版），软件开发技术基础（第二版）。同时还有网上的一些资源。当然还有同学之间的探讨。第四次 上机实验题目：编写算法，将图的邻接矩阵存储转化为图的邻接表存储。并对下图给出的实例执行算法，输出结果。数据结构知识：图的实现，图的邻接矩阵存储，图的邻接表存储以及他们之间的转化。程序源代码#include #include #define N 7#define E 15typedef char VexType;typedef int AdjType;typedef structVexType vertexN+1;AdjType edgeN+1N+1;AdjMatrix;typedef struct nodeint adjvex;struct node *next;EdgeNode;typedef structVexType vertxe;EdgeNode *link;VexNode;VexNode adjlistN+1;AdjMatrix *adj;void creatAdj(AdjMatrix *adj)int i,j,k; printf(请输入各顶点信息：);for(i=1;ivertexi);for(i=1;i=N;i+)for(j=1;jedgeij=0;printf(请输入各边的信息:);for(k=1;kedgeij=1;void Convert(AdjMatrix *adj)int i,j,k;EdgeNode *s;for(i=1;ivertexi; adjlisti.link=NULL;for(i=1;i=N;i+)for(j=1;jedgeij!=0) s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j; s-ne