数据结构算法实验内容与指导.doc

数据结构算法实验内容与指导1、 实验目的：将书中常用算法编写成程序，上机调试，验证算法的正确性，同时理解数据结构对于软件开发的意义。同时又能复习C+语言的重点与难点，熟悉vc+6.0调试环境，掌握一个完整程序的构成，为今后软件设计打下基础。2、 实验要求：熟练掌握c+面象对象的编程思想及vc+6.0上机调试环境。3、 实验内容：（1）线性表顺序存储（顺序表类）的插入、删除等操作的实现（2）线性表链式存储（单链表类）的建立、插入、删除等操作的实现（3）特殊线性表进栈、退栈操作的实现（4）顺序查找及二分查找算法的实现（5）常用的几种排序算法的实现（6）二叉树的建立、遍历算法的实现（7）图的邻接矩阵的建立，及遍历算法实现实验一：线性表顺序存储（顺序表类）的插入、删除等操作的实现/SeqList.hclass SeqListprotected:DataType *list;/数组int maxSize;/最大元素个数int size;/当前元素个数public:SeqList(int max=0); /构造函数SeqList(void); /析构函数int Size(void) const;/取当前数据元素个数void Insert(const DataType& item, int i);/插入DataType Delete(const int i);/删除DataType GetData(int i) const;/取数据元素;SeqList:SeqList(int max)/构造函数maxSize = max;size = 0;list = new DataTypemaxSize;SeqList:SeqList(void)/析构函数delete list;int SeqList:Size(void) const/取当前数据元素个数return size;void SeqList:Insert(const DataType& item, int i)/插入/在指定位置i前插入一个数据元素itemif (size = maxSize) cout 顺序表已满无法插入！ endl;exit(0);if(i size)/参数正确与否判断cout 参数i越界出错! i; j-) listj = listj-1; listi = item;/在i位置插入itemsize+;/当前元素个数加1DataType SeqList:Delete(const int i)/删除/删除指定位置i的数据元素，删除的元素由函数返回if (size = 0)cout 顺序表已空无元素可删！ endl;exit(0);if(i size - 1)/参数正确与否判断cout参数i越界出错!endl;exit(0);DataType x = listi;/取到要删除的元素/从i+1至size-1逐个元素前移for(int j = i;j size-1; j+) listj = listj+1;size-;/当前元素个数减1return x;/返回删除的元素DataType SeqList:GetData(int i) const/取数据元素/取位置i的数据元素，取到的数据元素由函数返回if(i size - 1)/参数正确与否判断cout 参数i越界出错! endl;exit(0);return listi;/返回取到的元素/ExamTest1.cpp#include #include typedef int DataType;/定义具体问题元素的数据类型#include SeqList.hvoid main(void)SeqList myList(100);/定义顺序表类对象myListint n = 10, x; for(int i = 0; i n; i+) /在myList中顺序插入10个元素cout “请输入插入元素x的值”x;mylist.Insert(x,i);myList.Delete(4);/删除myList中数据元素5for(i = 0; i myList.Size(); i+)/依次取myList中的元素并显示cout myList.GetData(i) ;分析讨论：问题1：请分析上述主函数的功能及运行结果；问题2:完成P41例2-2建立学生情况表实验。/ExamTest2.cpp#include #include struct StudentTypelong number;/学号数据项char name10;/姓名数据项char sex3;/性别数据项int age;/年龄数据项;/结构体StudentTypetypedef StudentType DataType;/定义DataType为StudentType数据类型#include SeqList.h/包含顺序表文件void main(void)SeqList myList(100);StudentType x3 = 2000001, 张三, 男, 20, 2000002, 李四, 男, 21,2000003, 王五, 女, 22;int n = 3;DataType s; for(int i = 0; i n; i+) /在myList中顺序插入n个元素myList.Insert(xi, i);for(i = 0; i myList.Size(); i+)/依次取myList中的元素并显示s = myList.GetData(i);cout s.number s.name s.sex s.age endl;实验二：线性表链式存储（单链表类）的建立、插入、删除等操作的实现/LinList.htemplate class LinList;/前视定义,否则友元无法定义template /模板类型为Tclass ListNodefriend class LinList;/定义类LinList为友元private:ListNode *next; /指向下一结点的指针T data;/定义为公有成员方便使用public:/构造函数1,用于构造头结点ListNode(ListNode *ptrNext = NULL)next = ptrNext;/构造函数2,用于构造其他结点ListNode(const T& item, ListNode *ptrNext = NULL)data = item;next = ptrNext;ListNode(void)/析构函数;/单链表类的定义template class LinListprivate:ListNode *head;/头指针int size;/当前的数据元素个数ListNode *Index(int i);/定位public:LinList(void);/构造函数LinList(void);/析构函数int ListSize(void) const;/取当前数据元素个数void Insert(const T& item, int i);/前插T Delete(int i);/删除T GetData(int i);/取元素; /单链表类的实现 template LinList:LinList(void)/构造函数head = new ListNode();/头指针指向头结点size = 0;/size的初值为0template LinList:LinList(void)/析构函数 ListNode *p, *q;p = head;/p指向第一个结点while(p != NULL)/循环释放结点空间直至初始化状态q = p;p = p-next;delete q;size = 0;/结点个数置为初始化值0head = NULL;template ListNode *LinList:Index(int i)/定位/返回指向第i个数据元素结点的指针/参数i的取值范围为：-1isize-1；i=-1时返回头指针if(i size-1)cout 参数i越界出错！ endl;exit(0);if(i = -1) return head;/i为-1时返回头指针headListNode *p = head-next;/p指向第一个数据元素结点int j = 0;/从0开始计数while(p != NULL & j next;j+;return p;/返回第i个结点的指针template int LinList:ListSize(void) const/取当前数据元素个数并返回return size;template void LinList:Insert(const T& item, int i)/插入/在第i个结点后插入一个元素值为item的新结点/参数i的取值范围为：0isizeif(i size)cout 参数i越界出错！ endl;exit(0);ListNode *p = Index(i - 1);/p为指向第i-1个结点的指针/构造新结点p，p的data域值为item，next域值为 p-nextListNode *q = new ListNode(item, p-next);p-next = q;/新结点插入第i个结点前size+;/元素个数加1template T LinList:Delete(int i)/删除/删除第i个数据元素并返回。参数i的取值范围为：0isize-1if(size = 0) cout 链表已空无元素可删！ endl;exit(0);if(i size-1)cout 参数i越界出错！ endl;exit(0);ListNode *s, *p = Index(i - 1);/p为指向第i-1个结点指针s = p-next;/s指向第i个结点p-next = p-next-next;/第i个结点脱链T x = s-data;delete s;/释放第i个结点空间size-;/结点个数减1return x;/返回第i个结点的data域值template T LinList:GetData(int i)/取数据元素/取第i个数据元素并返回。参数i的取值范围为：0isize-1if(i size-1)cout 参数i越界出错！ endl;exit(0);ListNode *p = Index(i);/p指向第i个结点return p-data;/ExamTest3.cpp#include #include #include LinList.hvoid main(void) LinList myList; Int s=10,20,30,40,50,60,70,80,90,100,n=10;Int temp;For(int I=0;In;I+) MyList.Insert(sI,I); MyList.Delete(4);For(I=0;ImyList.Size();I+) temp=myList.GetData(i); couttemp” “;问题1：请分析上述主函数的功能及运行结果；实验三：各种排序算法的实验/sort.h#include #include void InsertSort (DataType a, int n)/用直接插入法对a0-an-1排序int i, j;DataType temp;for(i=0; i -1 & temp.key = aj.key)aj+1 = aj;j-;aj+1 = temp;void ShellSort (datatype a, int n, int d, int numOfD)/用希尔排序法对记录a0-an-1排序/各组内采用直接插入法排序int i, j, k, m, span;datatype temp;for(m = 0; m numOfD; m+)span = dm;for(k = 0; k span; k+)for(i = k; i -1 & temp.key = aj.key)aj+span = aj;j = j-span;aj+span = temp;void SelectSort(datatype a, int n)/*用直接选择排序法对a0-an-1排序*/int i, j, small;datatype temp;for(i=0; i n-1; i+)small = i;for(j = i+1; j n; j+)if(aj.key asmall.key) small=j;if(small != i)temp = ai;ai = asmall;asmall = temp;void BubbleSort(datatype a, int n)/用冒泡排序法对a0-an-1排序int i, j, flag=1;datatype temp;for(i = 1; i n & flag = 1; i+)flag = 0;for(j = 0; j aj+1.key)flag = 1;temp = aj;aj = aj+1;aj+1 = temp;void QuickSort(datatype a, int low, int high)/用递归方法对对象alow-ahigh进行快速排序int i, j;datatype temp;i = low;j = high;temp = alow;while(i j)/在数组的右端扫描while(i j & temp.key = aj.key) j-;if(i j)ai = aj;i+;/在数组的左端扫描while(i j & ai.key temp.key) i+;if(i j)aj = ai;j-;ai = temp;/对子对象数组进行递归快速排序if(low i) QuickSort(a, low, i-1);if(i high) QuickSort(a, j+1, high);void Merge(DataType a, int n, DataType swap, int k)/k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中int m = 0, u1,l2,i,j,u2;int l1 = 0;/第一个有序子数组下界为0while(l1+k = n-1)l2 = l1 + k;/计算第二个有序子数组下界u1 = l2 - 1;/计算第一个有序子数组上界u2 = (l2+k-1 = n-1)? l2+k-1: n-1;/计算第二个有序子数组上界/两个有序子数组合并for(i = l1, j = l2; i = u1 & j = u2; m+)if(ai.key = aj.key)swapm = ai;i+;elseswapm=aj;j+;/子数组2已归并完，将子数组1中剩余的元素存放到数组swap中while(i = u1)swapm = ai;m+;i+;/子数组1已归并完，将子数组2中剩余的元素存放到数组swap中while(j = u2)swapm = aj;m+;j+;l1 = u2 + 1;/将原始数组中只够一组的数据元素顺序存放到数组swap中for(i = l1; i n; i+, m+) swapm = ai;void MergeSort(DataType a, int n)int i, k = 1;/归并长度从1开始DataType *swap = new DataTypen;/申请动态数组空间while(k n)Merge(a, n, swap, k);/调用归并函数Merge(a, n, swap, k)for(i = 0; i n; i+)ai = swapi; /将元素从临时数组swap放回数组a中k = 2 * k; /归并长度加倍delete swap;/释放动态数组空间/exam.cpp#include #include #define N 8typedef int KeyType;struct DataTypeKeyType key;#include Sort.hvoid main(void)DataType test8;int dN,I=0,p,cnt=0,low,high; char c;cout”请输入”N”个”endl;for(I=0;ItestI;cout”请选择排序方式”endl;cout”1-直接插入排序”endl;cout”2-希尔排序”endl;cout”3-直接选择排序”endl;cout”4-冒泡排序”endl;cout”5-快速排序”endl;cout”6-归并排序”endl;cout”0-退出”c;switch( c) case 1: InsertSort(test,N);break; case 2:p=N; while(p/2)!=1) dI=p/2; cnt+;p=p/2;I+;dI=1;cnt+;ShellSort(text,N,d,cnt);break;case 3:SelectSort(test,N);break;case 4:BubbleSort(text,N);break;case 5: low=0;high=N-1;QuickSort(text,low,high); break;case 6:MergeSort(text,N);break;case 0: exit(0);break;16