《数据结构算法实验内容与指导精品资料.doc》由会员分享，可在线阅读，更多相关《数据结构算法实验内容与指导精品资料.doc（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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
19、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,
20、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;/计算第二个有序子数组上界/两个有序子数组合并fo
21、r(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(
22、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 DataType
23、KeyType 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);
24、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;附录资料:不需要的可以自行删除 libxml2应用实例Libxm
25、l2 是一个xml的c语言版的解析器，本来是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或ftp(ftp.xmlsoft.org)站点下载libxml压缩包(libxml2-
26、xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvzf libxml2-xxxx.tar.gz3) 进入解压缩后的文件夹中运行 ./configure -prefix /home/user/myxml/xmlinst(此处为待安装的路径)或者直接使用 ./configure make make install 4) 添加路径 export PATH=/home/user/myxml/xmlinst/bin:$PATH 说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单的代码解析XML文件，包括本地和远程的文件，但是在编码上有一些问题。Libxml默
27、认只支持UTF8的编码，无论输入输出都是UTF-8，所以如果你解析完一个XML得到的结果都是UTF8的，如果需要输出GB2312或者其它编码，需要ICONV来做转码(生成UTF8编码的文件也可以用它做),如果系统中没有安装iconv的话，需要安装libiconv。 1) 下载libiconv压缩包(例如libiconv-1.11.tar.gz) 2) 对压缩包进行解压缩tar xvzf libiconv-1.11.tar.gz 3) 进入解压缩后的文件夹中运行 ./configure make make install三、关于XML：在开始研究 Libxml2 库之前，先了解一下XML的相关基
28、础。XML 是一种基于文本的格式，它可用来创建能够通过各种语言和平台访问的结构化数据。它包括一系列类似 HTML 的标记，并以树型结构来对这些标记进行排列。例如，可参见清单 1 中介绍的简单文档。为了更清楚地显示 XML 的一般概念，下面是一个简化的XML文件。清单 1. 一个简单的 XML 文件 root delete 10清单 1 中的第一行是 XML 声明，它告诉负责处理 XML 的应用程序，即解析器，将要处理的 XML 的版本。大部分的文件使用版本 1.0 编写，但也有少量的版本 1.1 的文件。它还定义了所使用的编码。大部分文件使用 UTF-8，但是，XML 设计用来集成各种语言中的
29、数据，包括那些不使用英语字母的语言。接下来出现的是元素。一个元素以开始标记 开始(如 )，并以结束标记 结束(如 )，其中使用斜线 (/) 来区别于开始标记。元素是 Node 的一种类型。XML 文档对象模型 (DOM) 定义了几种不同的 Nodes 类型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子节点。例如，age 元素有一个子元素，即文本节点 10。XML 解析器可以利用这种父子结构来遍历文档，甚至修改文档的结构或内容。LibXML2 是这样的解析器中的其中一种，并且文中的示例应用程序正是使
30、用这种结构来实现该目的。对于各种不同的环境，有许多不同的解析器和库。LibXML2 是用于 UNIX 环境的解析器和库中最好的一种，并且经过扩展，它提供了对几种脚本语言的支持，如 Perl 和 Python。四、Libxml2中的数据类型和函数一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师的话，90%的功能都是由30%的内容提供的。对于libxml2，我认为搞懂以下的数据类型和函数就足够了。1）内部字符类型xmlCharxmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据类型。事实上它的定义是：xmlstring.htypedef unsigned c
31、har xmlChar;使用unsigned char作为内部字符格式是考虑到它能很好适应UTF-8编码，而UTF-8编码正是libxml2的内部编码，其它格式的编码要转换为这个编码才能在libxml2中使用。还经常可以看到使用xmlChar*作为字符串类型，很多函数会返回一个动态分配内存的xmlChar*变量，使用这样的函数时记得要手动删除内存。2） xmlChar相关函数如同标准c中的char类型一样，xmlChar也有动态内存分配、字符串操作等相关函数。例如xmlMalloc是动态分配内存的函数；xmlFree是配套的释放内存函数；xmlStrcmp是字符串比较函数等等。基本上xmlCh
32、ar字符串相关函数都在xmlstring.h中定义；而动态内存分配函数在xmlmemory.h中定义。3）xmlChar*与其它类型之间的转换另外要注意，因为总是要在xmlChar*和char*之间进行类型转换，所以定义了一个宏BAD_CAST，其定义如下：xmlstring.h#define BAD_CAST (xmlChar *)原则上来说，unsigned char和char之间进行强制类型转换是没有问题的。4）文档类型xmlDoc、指针xmlDocPtrxmlDoc是一个struct，保存了一个xml的相关信息，例如文件名、文档类型、子节点等等；xmlDocPtr等于xmlDoc*，它
33、搞成这个样子总让人以为是智能指针，其实不是，要手动删除的。xmlNewDoc函数创建一个新的文档指针。xmlParseFile函数以默认方式读入一个UTF-8格式的文档，并返回文档指针。xmlReadFile函数读入一个带有某种编码的xml文档，并返回文档指针；细节见libxml2参考手册。xmlFreeDoc释放文档指针。特别注意，当你调用xmlFreeDoc时，该文档所有包含的节点内存都被释放，所以一般来说不需要手动调用xmlFreeNode或者xmlFreeNodeList来释放动态分配的节点内存，除非你把该节点从文档中移除了。一般来说，一个文档中所有节点都应该动态分配，然后加入文档，最
34、后调用xmlFreeDoc一次释放所有节点申请的动态内存，这也是为什么我们很少看见xmlNodeFree的原因。xmlSaveFile将文档以默认方式存入一个文件。xmlSaveFormatFileEnc可将文档以某种编码/格式存入一个文件中。5）节点类型xmlNode、指针xmlNodePtr节点应该是xml中最重要的元素了，xmlNode代表了xml文档中的一个节点，实现为一个struct，内容很丰富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode *xmlNodePtr;struct _xmlNode void *_privat
35、e;/* application data */ xmlElementType type; /* type number, must be second ! */ const xmlChar *name; /* the name of the node, or the entity */ struct _xmlNode *children;/* parent-childs link */ struct _xmlNode *last; /* last child link */ struct _xmlNode *parent;/* child-parent link */ struct _xml
36、Node *next; /* next sibling link*/ struct _xmlNode *prev; /* previous sibling link*/ struct _xmlDoc*doc;/* the containing document */ /* End of common part */ xmlNs *ns; /* pointer to the associated namespace */ xmlChar *content; /* the content */ struct _xmlAttr *properties;/* properties list */ xmlNs *nsDef; /* namespace definitions on this node */ void *psvi;/* for type/PSVI informations */ unsigned short line; /* line number */ unsigned short extra;/* extra data for XPath/XSLT */;可以看到，节点之间是以链表和树两种方式同时组织起来的，next和prev指针可以组成链表，而