数据结构实验报告(模板类).doc

数据结构实验报告模板类实现链表目 录1.实验内容PAGE.22.实验目的PAGE.23预备知识PAGE.24.技术难点PAGE.25.设计思路PAGE.36.成员函数实现举例PAGE.47. 测试代码PAGE.78. 心得体会PAGE.101 实验内容 定义一个包含模板的结构。 定义一个链表类，能够增加元素、删除元素、查找元素、打印链表。 编写测试代码，验证链表类编写是否正确2 实验目的 理解指针的定义 理解类的结构 学习使用类模板3 预备知识 内存：计算机存储硬件。为了区别内存的不同位置，内存被分成字节，内存的全部字节顺序地赋予一个称为地址的编号。因此，内存地址是物理的，计算机设计好就给定了。 变量：在内存中占据一定的内存字节，在这些字节中存储的数据信息称为变量的内容。因此，通过变量就可以操作内存，也就是说要操作某块内存，就必须先将这块内存的首地址和一个变量名绑定起来。换句话说，当我们声明一个变量后，就意味着我们申请使用一块特定大小的内存，用于存储我们的数据。 指针变量：在变量中，有一类变量比较特殊，其形式为int *ptr。其特殊性是指该变量不是直接存储数据，而是存储内存地址。因此，通过该变量，我们可以得到另外一个内存空间所存储的信息。 数组：由于变量所申请的内存空间是非常有限的，很多情况下，我们需要更大的空间，例如存储字符串”C+ is difficult but interesting”。如果采用一系列char变量，则需要数10个变量。这种情况显然不是我们所希望看到的。这时候，我们就可以采用数组非常方便地完成字符组的存储：char str = ”C+ is difficult but interesting”。 动态分配：数组虽然可以申请更大的内存空间，但是其存在一个基本缺点是需要事先指定内存大小。但是，在很多情况下，我们无法知道需要分配内存的大小。例如，我们需要设计一个读取图像的程序。但是，不同图像的宽带和高度显然是不一样的，因此，需要的内存大小也不一样。因此，我们需要根据图像宽带和高度动态分配内存大小。在这种情况下，数组是无能为力的。而在C+中，采用new操作符来完成动态内存分配。4 技术难点 C+如何管理内存 内存和指针的关系 5. 设计思路对于链表的设计，基本可以参照学生信息管理的结构体与类的构建，这里就不一一叙述，直接上代码。template struct ListElementT ListElem;ListElement* NextDataAddress;template class Listprivate: ListElement* m_ElemList;ListElement* frist;public:List(); List(); public:List& operator=(List &rhs);/运算符重载 ListElement * FindElem(const T& target);void AddElem(T& NewElem);void DeleteElem (T value); ListElement* GetListPtr()return frist;/得到链表的首地址void display();void LinkList(List &list_1);/连接两个链表void SortList();/对链表进行排序void Change(ListElement Elem_1,ListElement Elem_2);/交换链表中的两个元素;6. 成员函数实现举例对于模板类的成员函数实现，void AddElem(T& NewElem)，void DeleteElem (T value)，void display()，ListElement * FindElem(const T& target)这四个函数与之前的学生信息管理系统的函数没有太大的区别，算法也基本一致，这里就不在过多叙述。接下来重点说一下List& operator=(List &rhs)的设计思路。在List& operator=(List &rhs)函数中，定义了指向结构的指针p与newnode。P指针用于对原链表的备份。而newnode则是不断申请新的内存空间，用于存放传递过来的原链表，并且将其数据不断再添加到this中去。其过程与新建链表有些类似，但是顺序却正好相反，是从链表的头部拿出数据，插入到另外一个链表的尾部，所以新的链表最后的数据排列顺序与原链表相反。代码：template List& List:operator= (List& rhs)ListElement *newNode, *p; p = rhs.GetListPtr();/ copy itemsthis- m_ElemList = NULL;while(p != NULL) newNode = new ListElement; newNode-ListElem = p-ListElem; newNode-NextDataAddress = m_ElemList; this-m_ElemList = newNode; frist = m_ElemList; p = p-NextDataAddress;return *this;图示如下： 对于void LinkList(List &list_1)函数来说，只需要将当前链表的指针指向末尾，然后将nextaddress存储list_1的首地址即可。具体定义如下：template void List:LinkList(List &list_1)while(this-m_ElemList-NextDataAddress != NULL)this-m_ElemList = this-m_ElemList-NextDataAddress;this-m_ElemList-NextDataAddress = list_1.GetListPtr();对于SortList函数，相对实现可以比较简单，对于链表的连接完全不用改变，只要交换链表中所存的数字就可以。具体的算法类似于冒泡排序。template void List:Change(ListElement &Elem_1,ListElement &Elem_2) ListElement temp; temp.ListElem = Elem_1.ListElem; Elem_1.ListElem = Elem_2.ListElem; Elem_2.ListElem = temp.ListElem; template void List:SortList() ListElement *temp=frist; while(temp-NextDataAddress != NULL) m_ElemList =frist; while(m_ElemList-NextDataAddress != NULL) if(m_ElemList-ListElem m_ElemList-NextDataAddress-ListElem) Change(*m_ElemList),(*(m_ElemList-NextDataAddress); m_ElemList = m_ElemList-NextDataAddress; temp = temp-NextDataAddress; 最后是Reverse函数，这个函数主要实现链表的倒序，因为要实现的时候需要改变指针，所以相对来说有些麻烦。但是倘若T为一个自定义结构的话，要实现链表的排序用Sort就不行了，只能通过Reverse来进行实现链表的倒序。具体的定义如图。这个地址需要保存 代码如下：template void List:Reverse()ListElement *ptr = frist-NextDataAddress;ListElement *pre = frist;ListElement *temp;while(ptr != NULL)temp = ptr-NextDataAddress;ptr-NextDataAddress = pre;frist-NextDataAddress = NULL;pre = ptr;ptr = temp;frist = pre;除此之外，另外加入了一个CrossLink功能，实现链表的交叉排列，相对比较简单，直接上代码：void List:CrossLink(List &list_1)ListElement *ptr =list_1.GetListPtr();ListElement *temp_1;ListElement *temp_2;m_ElemList = frist;while(m_ElemList)temp_1 = m_ElemList-NextDataAddress;temp_2 = ptr-NextDataAddress;m_ElemList-NextDataAddress = ptr;ptr-NextDataAddress = temp_1;m_ElemList = temp_1;ptr = temp_2;7. 测试代码和运行中间结果为了验证上述代码正确性，编写main函数进行验证。思路是首先增加10个元素；然后删除特定学号的元素。然后将一个链表赋值给另外一个空链表。最后将两个链表连接。每次改变链表后都对其进行一次输出。然后再对自定义结构进行测试。struct Studentint StudentID;int main()List List_1,List_2;for(int i=0;i10;i+)List_1.AddElem(i);List_1.DeleteElem(5);List_1.display();List_1.Reverse();List_2 = List_1;List_2.SortList();List_2.CrossLink(List_1);List_2.display();List Stu_1,Stu_2;for(int j=1;j=10;j+)Student student;student.StudentID = j;Stu_1.AddElem(student);Stu_1.Reverse();Stu_2 = Stu_1;Stu_2.LinkList(Stu_1);return 0;a) 增加元素与删除元素的运行过程（List_1变化过程） 跳出for循环之后的List_1运行到List_1.DeleteElem(5)时。b) 对List_2的处理过程赋值之后，可以看到List_2的链表元素与之前的链表顺序相反c) 连接链表的运行过程可以看到，连接两个链表之后的数据储存方式。 d）第二次运行，List_2做测试。可以看到，交叉连接两个链表之后的数据储存方式。 顺序也没有错误e）最后是对自定义结构体的测试Stu_1与Stu_2的结果。8. 实验体会在这次实验中，实现了链表的连接于相互的赋值，与链表的排列有了更深刻的理解。通过本次实验，使用自定义类型作为T时，对于有些函数需要重载才能够用在自定义类型上。这在以后的试验中需要多注意。