北京邮电大学
数据结构试验报告
实验名称：实验一 线性表
学生姓名：
班 级：
班内序号：
学 号：
日 期：20##年1月3日
1 实验目的
Ø 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法
Ø 学习指针、模板类、异常处理的使用
Ø 掌握线性表的操作的实现方法
Ø 学习使用线性表解决实际问题的能力
2 实验内容
2.1题目1
根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：
1、 带头结点的单链表
2、 不带头结点的单链表
3、 循环链表
4、 双链表
5、 静态链表
线性表的基本功能：
1、 构造：使用头插法、尾插法两种方法
2、 插入：要求建立的链表按照关键字从小到大有序
3、 删除
4、 查找
5、 获取链表长度
6、 销毁
7、 其他：可自行定义
编写测试main()函数测试线性表的正确性。
3 程序分析
3.1 存储结构
单链表的存储结构：
3.2 关键算法分析
一、关键算法
1.头插法
自然语言描述：a.在堆中建立新结点
b.将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.在堆中建立新结点
b.将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
c.若p为空，说明第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;
int j = 1;
while(p)
{
if(p->data == x) return j;
else
{
p = p->next;
j++;
}
}
return -1;
}
时间复杂度：O(n)
6.插入函数
自然语言描述： a.在堆中建立新结点
b.将要插入的结点的数据写入到新结点的数据域
c.修改新结点的指针域
d.修改前一个指针的指针域，使其指向新插入的结点的位置
代码描述:
template<class T>
void LinkList<T>::Insert(int i,T x)//插入函数
{
Node<T> * p = Get(i-1);
if(p)
{
Node<T> * s = new Node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
else throw"插入位置非法";
}
时间复杂度：O(n)
7.按位删除函数
自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点
b.设q指向第i个元素
c.将q元素从链表中删除
d.保存q元素的数据
e.释放q元素
代码描述:
template<class T>
T LinkList<T>::Delete(int i)//删除函数
{
Node<T> *p = Get(i-1);
Node<T> *q = p->next;
T x=q->data;
p->next = q->next;
delete q;
return x;
}
8.遍历打印函数
自然语言描述: a.判断该链表是否为空链表，如果是，报错
b.如果不是空链表，新建立一个temp指针
c.将temp指针指向头结点
d.打印temp指针的data域
e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空
代码描述:
template<class T>
void LinkList<T>::PrintList()//打印链表
{
Node<T> * p = front->next;
while(p)
{
cout<<p->data<<' ';
p = p->next;
}
cout<<endl;
}
9.获取链表长度函数
自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0
b.如果不是空链表，新建立一个temp指针，初始化整形数n为0
c.将temp指针指向头结点
d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n
e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n
代码描述:
template<class T>
int LinkList<T>::GetLength()//分析链表长度
{
Node<T> * p = front;
int i=0;
while(p)
{
p = p->next;
i++;
}
return i-1;
}
4 程序运行结果
4.1主函数流程图
4.2程序运行框图
5 实验心得
1.调试时出现的问题及解决的方法
在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。
2.心得体会
了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识
3.下一步的改进
可以增加完善报错机制，增强程序的健壮性
完整源代码
#include<iostream>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> * next;
};
template<class T>
class LinkList
{
public:
LinkList() { front = new Node<T>; front->next = NULL;}//无参构造函数
LinkList(T a[],int n);//构造函数
void Insert(int i,T x);//插入函数
T Delete(int i);//删除函数
Node<T>* Get(int i);//查找第几个的元素，返回的是该元素的地址
int Locate(T x);//定位某元素
int GetLength();//分析链表长度
~LinkList();//析构函数
void PrintList();//打印链表
private:
Node<T> * front;
};
//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;
// }
//}
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;
}
}
template<class T>
LinkList<T>::~LinkList()//析构函数，销毁链表
{
Node<T> * p = front;
while(p)
{
front = p;
p = p->next;
delete front;
}
}
template<class T>
void LinkList<T>::PrintList()//打印链表
{
Node<T> * p = front->next;
while(p)
{
cout<<p->data<<' ';
p = p->next;
}
cout<<endl;
}
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;
}
template<class T>
int LinkList<T>::Locate(T x)//按值查找
{
Node<T> * p = front->next;
int j = 1;
while(p)
{
if(p->data == x) return j;
else
{
p = p->next;
j++;
}
}
return -1;
}
template<class T>
void LinkList<T>::Insert(int i,T x)//插入函数
{
Node<T> * p = Get(i-1);
if(p)
{
Node<T> * s = new Node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
else throw"插入位置非法";
}
template<class T>
T LinkList<T>::Delete(int i)//删除函数
{
Node<T> *p = Get(i-1);
Node<T> *q = p->next;
T x=q->data;
p->next = q->next;
delete q;
return x;
}
template<class T>
int LinkList<T>::GetLength()//分析链表长度
{
Node<T> * p = front;
int i=0;
while(p)
{
p = p->next;
i++;
}
return i-1;
}
void main()
{
int n;
cout<<"将要输入的链表长度为：";
cin>>n;
int *b=new int[n];
cout<<"输入链表中的元素：";
for(int k=0;k<n;k++) cin>>b[k];
LinkList<int> a(b,n);
a.PrintList();
cout<<"链表的长度:"<<a.GetLength()<<endl;
int i;
cout<<"请输入要删除元素的位置：";
cin>>i;
cout<<"被删除掉的元素是："<<a.Delete(i)<<endl;
cout<<"删除后得到的链表是：";
a.PrintList();
int j;
cout<<"请输入要插入的元素：";
cin>>j;
cout<<"要将其插入在哪个位置：";
cin>>i;
a.Insert(i,j);
cout<<"插入后得到的链表是：";
a.PrintList();
cout<<"要查找第几个元素：";
cin>>i;
cout<<"要查找的元素为："<<a.Get(i)->data<<endl;
cout<<"要探寻位置的元素大小为：";
cin>>j;
cout<<"输入的元素位置在："<<a.Locate(j)<<endl;
}