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

1、数据结构算法实验内容与指导1、实验冃的：将卩中常用算法编写成程序，上机调试，验证算法的正确性，同时理解数 据结构对于软件开发的意义。同时又能复习c+语言的重点与难点，熟悉vc+6.0调 试环境，掌握一个完整程序的构成，为今后软件设计打下基础。2、实验要求：熟练掌握c+而象对象的编程思想及vc+6.0上机调试环境。3、实验內容：（1）线性表顺序存储（顺序表类）的插入、删除等操作的实现（2）线性表链式存储（单链表类）的建立、插入、删除等操作的实现（3）特殊线性表进栈、退栈操作的实现（4）顺序查找及二分查找算法的实现（5）常用的几种排序算法的实现（6）二叉树的建立、遍历算法的实现（7）图的邻接矩阵的

2、建立，及遍历算法实现实验一：线性表顺序存储（顺序表类）的插入、删除等操作的实现/seqlist.hclass seqlistprotected:datatypc *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

3、 i) const; ;seqlist:seqlist(int max)maxsize = max;size = 0;list = new datatypemaxsizel; seqlist: >seqlist( void)删除収数据元素构造函数析构函数delete jlist;取当前数据元素个数int seqlist:size(void) constreturn size;void seqlist:insert(const datatype& item, int i) 插入 在指定位置i前插入一个数据元素itemif (size = maxsize)cout « &q

4、uot;顺序表已满无法插入！ " vv cndl; cxit(o);if(i < 0 ii i > size)参数正确与否判断cout « “参数i越界出错!“ « endl; exit(o);从size-1至i逐个元素后移for(int j = size; j > i; j) listjj = listj-lj;listfil = item;在 i 位置插入 itemsizc+;当前元索个数加1datatype seqlist:delete(const int i)删除删除指定位置i的数据元素，删除的元索rh函数返回if (size = 0)c

5、out « "顺序表已空无元;素可删！ ” vv endl; exit(o);if(i < 0 ii i > size - 1)参数正确与否判断cout«*參数i越界出错!"«endl; exit(o);datatype x = listi;取到要删除的元素从i+1至size-1逐个元素前移for(int j = i;j < size-1; j+) listfj = listj+l;size-;当前元索个数减1return x;返回删除的元素datatype seqlist:getdata(int i) const 取数据元素

6、収位置i的数据元素，収到的数据元素山函数返回if(i < 0 ii i > size1)参数正确与否判断cout « “参数i越界出错!“ « endl;exit(o);返冋取到的元素/examtestl.cpp#include <iostream.h>定义具体问题元素的数据类型怎义顺序表类对象mylist在mylist屮顺序插入10个元索#include <stdlib.h> typedef int datatype;#include "seqlist.h"void main(void)scqlist mylist(

7、loo); int n = 10, x;for(int i = 0; i < n; i+)cout« "请输入插入元素x的值"<<endl ;cin>>x;mylist. insert (x, i);mylist.dclctc(4);删除 mylist 中数据元索 5for(i = 0; i < mylist.size(); i+) 依次取 mylist 屮的元素并显示 cout « mylist.getdata(i) « h m;分析讨论：问题1:请分析上述主函数的功能及运行结果；问题2:完成p41例2-2

8、建立学生情况表实验。/examtest2xpp#include <iostream-h>struct studenttypelong number;char name10j;char sex3j;int age;typedef studenttype datatype;#include "seqlist.h"#inelude <stdlib.h>学号数据项姓名数据项性别数据项年龄数据项结构体 studenttype定义datatype为studenttype数据类型包含顺序表文件void main(void)seqlist mylist(k)o);s

9、tudenttype 只=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.namc « s.scx « s.agc &#

10、171; cndl;实验二：线性表链式存储(单链表类)的建立、插入、删除等操作的实现/linlist.htemplate <class t> class linlist;template <class t> class listnode前视定义，否则友元无法定义模板类型为tfriend class linlist<t> private:listnode<t> *next;t data;定义类linlist<t>为友元指向下一结点的指针定义为公有成员方便使用头指针当前的数据元索个数定位构造函数析构函数取当前数据元索个数前插删徐/取元素p

11、ublic:构造函数1,用于构造头结点listnode(listnode<t> *ptrnext = null) next = ptrncxt;构造函数2,用于构造其他结点listnode(const t& item, listnode<t> *ptrnext = null)data = item; next = ptrnext; listnodc(void)析构函数；单链表类的定义template <class t>class linlist private:listnode<t> *head; int size;listnode<

12、;t> *index(int i); public:linlist(void);linlist(void);int listsize(void) const;void insert(const t& item, int i);t dclctc(int i);t getdata(int i);单链表类的实现 template <class t>linlist<t>:linlist(void)head = new listnode<t>(); size = 0;template <class t>linlist<t>:lin

13、list(void) listnode<t> *p, *q;p = head;while(p != null) q = p;p = p->next; delete q;size = 0;head = null;template <class t>构造函数头指针指向头结点/size的初值为0析构函数p指向第一个结点循环释放结点空间直至初始化状态结点个数置为初始化值0定位listnodc<t> *linlist<t>:indcx(int i)返回指向第i个数据元素结点的指针参数i的取值范围为：lwiwsizel； i=-l时返回头指针cout

14、« ”参数i越界出错! exit(0);if(i = -1) return head;listnodc<t> *p = hcad->ncxt; int j = 0;while(p != null && j < i)p = p->next;j+；return p;template <class t>"« endl;/i为-1吋返回头指针head p指向第一个数据元索结点从0开始计数寻找笫i个结点返回笫i个结点的指针if(i < -1 ii i > size-1)int linlist<t&g

15、t;:listsize(void) const取当前数据元素个数并返回return size;template <class t>void linlist<t>:insert(const t& item, int i)插入在第i个结点后插入一个元素值为item的新结点参数i的取值范围为：owiwsizeif(i < 0 ii i > size)cout « u参数i越界出错！” « endl;exit(o);listnode<t> *p = index(i - 1);/p为指向第il个结点的指针构造新结点p，p的dat

16、a域值为item, next域值为p->next listnode<t> *q = new listnode<t>(item, p->next);p->next = q;新结点插入第i个结点前size+;元索个数加1template <class t>t linlist<t>:delete(int i)删除删除第i个数据元素并返回。参数i的取值范i韦i为：()wiwsizelif(sizc = 0)cout « "链表己空无元索可删！ ” « endl;exit(o);if(i<olli>

17、;sizc-l)cout « u参数i越界出错！” « endl;exit(o);listnode<t> *s, *p = index(i - 1);/p 为指向第 il 个结点指针s = p->next;/s指向笫i个结点p->next = p->next->next;第 i 个结点脱链t x = s->data;delete s;size;return x;template <class t>t linlist<t>:getdata(int i)/释放笫i个结点空间结点个数减1返冋第i个结点的data域值

18、取数据元素取第i个数据元素并返回。参数i的取值范由为：owiwsizejif(i < 0 lli>size-l)cout « n参数i越界岀错! m«endl; exit(o);p指向第i个结点listnodc<t> *p = indcx(i); return p->data;/examtest3.cpp#include <iostream.h>#include <stdlib.h>include ,linlist.h,'void main(void)linlist<int> mylist;int s

19、= 10,20,30,40,50,60,70,80,90,100 ,n= 10;int temp;for(int i=0;i<n;i+)mylist.insert(si j);mylist.delete(4);for(i=0;i<mylist.size();l+)temp=mylist.getdata(i);cout«temp« “；问题1:请分析上述主函数的功能及运行结果;实验三：各种排序算法的实验/sort.h#include <iostream.h>#include <stdlib.h>void inscilsort (dataty

20、pc a, int n)用直接插入法对a0卜anl排序int i,j;datatype temp;for(i=0; i<n-l; i+)temp = ai+l;j = i；while(j > -1 && temp.key <= afjl.key)aj+l = a|j;j-；aj+l = temp;void shellsort (datatype alj, int n, int dj, int numofd)/用希尔排序法对记录a0anl排序各组内采用直接插入法排序int i, j, k、m, span;datatype temp;for(m = 0; m &l

21、t; numofd; m+)span = dm;for(k = 0; k < span; k+)for(i = k; i < n-span; i = i+span)temp = ai+span;j = i；while(j > -1 && temp.key <= ajkey) alj+spanj = aj; j =j-span;aj+span = temp;void sclcctsort(datatypc a, int n)/*用直接选择排序法对a0j-an-lw*/int i, j, small;datatype temp;for(i=0; i <

22、 n-1; i+)small = i;for(j = i+1; j < n; j+)if(aj.kcy < asmall.kcy) small=j;if(small != i)temp = ai; ai = asmall;asmall = temp;void bubblcsort(datatypc a, int n) 用冒泡排序法对 a0卜an訂排序 int i,j,flag=l;datatype temp;for(i = 1; i < n && flag = 1; i+)flag = 0;for(j = 0; j < n-i; j+)if(aj.key

23、 > aj+l.key)flag = 1;temp = aj;a|j =aj+l；aj+l = temp;void quicksort(datatype aj, 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;ai = aj;i+；在数组的左端扫描while(i < j && a

24、fi.key < temp.key) i+; ig)a|j = ai；j-；ai = temp;对子对象数组进行递归快速排序if(low < i) quicksort(a, low, i-1);if(i v high) quicksort(a, j+1, high);void merge(datatype a, int n, datatype swapfl, int k)/k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中 int m = 0, ul,12,i,j,u2;int 11 = 0; whilc(ll+k <= n-1) 12 = 11 +k;u

25、l =12 1;第一个冇序子数组下界为0计算第二个有序子数组卜-界 计算第一个有序了数组上界u2 = (12+k-l <= n-1)? 12+k-l: nl;计算第二个有序子数组上界两个有序子数组合并for(i = 11, j = 12; i <= ul && j <= u2; m+) if(ai.key <= aj.key)swapm = ai;i+；elseswapm=aj;j+；/子数组2已归并完，将子数组1中剩余的元素存放到数组swap中while(i <= u 1)swapm = ai;m+;i+;/子数组1已归并完，将子数组2中剩余的元

26、素存放到数组swap中 while(j <= u2)swapfml = aj;m+;j+;11 =u2+ 1;将原始数组中只够一组的数据冗素顺序存放到数组swap中 for(i = 11; i < n; i+, m+) swapm = aij;void mergesort(datatype a, int n)归并长度从1开始申请动态数组空间int i, k = 1;datatype * swap = new datatypen;while(k < n)调用归并函数merge(a, n, swap, k)将元素从临时数组swap放回数组a中归并长度加倍释放动态数组空间merge(a, n, swap, k); for(i = 0; i < n; i+) ai = swapi;k = 2 * k; delete swap;/exam.cpp#include <iostream-h>#inelude <st