北邮数据结构实验报告 单链表..doc

北京邮电大学数据结构试验报告实验名称: 实验一线性表学生姓名: 班级: 班内序号: 学号: 日期: 2014年 1月 3日 1 实验目的?熟悉 C++ 语言的基本编程方法,掌握集成编译环境的调试方法?学习指针、模板类、异常处理的使用?掌握线性表的操作的实现方法?学习使用线性表解决实际问题的能力 2 实验内容 题目 1 根据线性表的抽象数据类型的定义, 选择下面任一种链式结构实现线性表, 并完成线性表的基本功能。线性表存储结构(五选一): 1、带头结点的单链表 2、不带头结点的单链表 3、循环链表 4、双链表 5、静态链表线性表的基本功能: 1、构造:使用头插法、尾插法两种方法 2、插入:要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他:可自行定义编写测试 main() 函数测试线性表的正确性。 3 程序分析 存储结构单链表的存储结构: 关键算法分析一、关键算法 1. 头插法自然语言描述: a. 在堆中建立新结点 a[i] 写入到新结点的数据域 c. 修改新结点的指针域 d. 修改头结点的指针域, 将新结点加入链表中代码描述: template<class T> LinkList<T>::LinkList(T a[], int n)// 头插法建立{ front = new Node<T>; front->next = NULL; for(int i=n-1;i>=0;i--) { Node<T>* s= new Node<T>; s->data = a[i]; s->next = front->next; front->next = s; }} 时间复杂度: O(n) 2. 尾插法自然语言描述: a. 在堆中建立新结点 a[i] 写入到新结点的数据域 c. 将新结点加入到链表中 d. 修改修改尾指针代码描述: template<class T> LinkList<T>::LinkList(T a[], int n)// 尾插法建立{ front = new Node<T>; front->next=NULL; Node<T> *r= front; for(int i=0;i<n;i++) { Node<T> *s= new Node<T>; s->data = a[i]; s->next = r->next; r->next= s; r=s; }} 时间复杂度: O(n) 3. 析构函数自然语言描述: a. 新建立一个指针,指向头结点 b. 移动 a 中建立的指针 c. 逐个释放指针代码描述: template<class T> LinkList<T>::~LinkList()// 析构函数,销毁链表{ Node<T> *p= front; while(p) { front = p;p= p->next; delete front; }} 4. 按位查找函数自然语言描述: a. 初始化工作指针 p 和计数器 j,p 指向第一个结点, j=1 b. 循环以下操作,直到 p 为空或者 j 等于 1 b1:p 指向下一个结点 b2:j加1 为空,说明第 i 个元素不存在,抛出异常 d. 否则,说明 p 指向的元素就是所查找的元素,返回元素地址代码描述: template<class T> Node<T>* LinkList<T>::Get(int i)// 按位查找{ Node<T> *p= front; int j=0; while(p) { if(j<i) {p= p->next; j++; } else break; } if(!p) throw" 查找位置非法"; else return p; } 时间复杂度: O(n) 5. 按值查找函数自然语言描述: a. 初始化工作指针 p 和计数器 j,p 指向第一个结点, j=1 b. 循环以下操作,找到这个元素或者 p 指向最后一个结点 b1. 判断 p 指向的结点是不是要查找的值,如果是,返回 j; b2. 否则 p 指向下一个结点, 并且 j 的值加一 c. 如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息代码描述: template<class T> int LinkList<T>::Locate(T x)// 按值查找{ Node<T> *p= front->next; intj= 1; while(p) { if(p->data == x) return j; else {p= p->next; j++; }} return -1; } 时间复杂度: O(n) 6. 插入函数自然语言描述: a. 在堆中建立新结点 b. 将要插入的结点的数据写入到新结点的数据域 c