数据结构算法实验内容与指导精品资料.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构算法实验内容与指导精品资料.doc》由会员分享,可在线阅读,更多相关《数据结构算法实验内容与指导精品资料.doc(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构算法实验内容与指导1、 实验目的:将书中常用算法编写成程序,上机调试,验证算法的正确性,同时理解数据结构对于软件开发的意义。同时又能复习C+语言的重点与难点,熟悉vc+6.0调试环境,掌握一个完整程序的构成,为今后软件设计打下基础。2、 实验要求:熟练掌握c+面象对象的编程思想及vc+6.0上机调试环境。3、 实验内容:(1)线性表顺序存储(顺序表类)的插入、删除等操作的实现(2)线性表链式存储(单链表类)的建立、插入、删除等操作的实现(3)特殊线性表进栈、退栈操作的实现(4)顺序查找及二分查找算法的实现(5)常用的几种排序算法的实现(6)二叉树的建立、遍历算法的实现(7)图的邻接矩阵
2、的建立,及遍历算法实现实验一:线性表顺序存储(顺序表类)的插入、删除等操作的实现/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 GetDat
3、a(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
4、;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逐
5、个元素前移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 SeqLis
6、t.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建立学生情况表实验
7、。/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, 李四,
8、男, 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;/前视定义,否则友元无法定义temp
9、late /模板类型为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)/析构函数;/单链表类
10、的定义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)/构造函数
11、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时返回头指
12、针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)/插入/
13、在第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-1i
14、f(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的取
15、值范围为: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;ImyL
16、ist.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)/用希
17、尔排序法对记录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+)
18、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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构算法实验内容与指导 精品资料 数据结构 算法 实验 内容 指导 精品 资料
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内