1、成 绩评阅人重庆邮电大学课程设计实验报告班级：1301416姓名：陈昊学号：2014214156指导老师：夏晨洋课程名称：数据结构实验时间：2015 年 10 月 26 日-2015 年 11 月 2 日实验地点：数字图书馆负一楼 B132实验二 单链表的存储与操作一、实验目的1理解线性表的逻辑结构；2理解单链表的存储结构特点，掌握单链表的存储分配要点；3掌握单链表的基本操作及实现，并能正确分析其时间复杂度。二、主要数据结构描述LinkList( ); /建立只有头结点的空链表LinkList(T a , int n); /建立有 n 个元素的单链表LinkList(); /析构函数int L
2、ength(); /求单链表的长度T Get(int i); /取单链表中第 i 个结点的元素值int Locate(T x); /求单链表中值为 x 的元素序号void Insert(int i, T x); /在单链表中第 i 个位置插入元素值为 x 的结点T Delete(int i); /在单链表中删除第 i 个结点void PrintList( ); /遍历单链表，按序号依次输出各元素Node *first; /单链表的头指针在单链表中，需要有构造函数用来构造整个单链表。需要析构函数来删除整个单链表。需要一个 Length 函数来求单链表的长度。需要一个取值函数Get，传入节点的编号
3、，返回节点的值。需要一个求序号的函数，传入数据的值，返回数据对应的编号，即在单链表中的位置。需要一个插入函数，用来在特定的位置插入一个节点用来存储新数据。需要一个删除函数，用来删除某个节点，并将该节点两端的节点连起来。需要一个遍历函数，用以遍历单链表。三、算法的基本思想描述1. 按位置/值查找：按位置和按值查找的思路大体相同，需要一个工作指针来对整个链表进行遍历，如果所遇到的编号或值与想要的一致，便会把工作指针的信息返回。此函数只需对链表遍历一次，所以平均时间复杂度为 O（n） ；2. 在位置 i 插入一个数据元素：此函数可以大体分成两个部分。第一个部分是遍历，寻找到要插入的位置，这个与上面的
4、方法相同。第二个部分是插入，要先申请一个新节点 s，在让 s 的指针域等于前一个节点 p 的指针域，最后让 p 的指针域等于 s。此函数只需对链表遍历一次，所以平均时间复杂度为 O（n） ；3. 删除位置 i 的数据元素：删除函数也有两个部分，第一个与插入相同，第二个先要暂存被删节点，用以返回，再让前一个节点的指针域等于后一个节点，最后删除被删节点。此函数只需对链表遍历一次，所以平均时间复杂度为O（n） ；4. 初始化单链表（有参）：有前插法和尾插法，实际上都是在链表的后面再添加一个新节点，所以时间复杂度为 O（n） ；5. 遍历单链表、求单链表长度、销毁单链表：这三个函数都是要遍历单链表，所以时间复杂度为 O（n） 。四、 运行的结果截图五、实验体会和收获通过这次试验，我熟悉了如何取单链表中第 i 个结点的元素值，如何按位查找位置为 i 的元素并输出值，如何构建一个单链表。总之这次试验然我熟悉了很多单链表的操作。六、程序清单。LinkList.hLinkList.cppLinkListMain.cpp
