单轴拉伸实验报告[5篇范文]

style=“margin-bottom: 0px” Text=“用®?户¡ì名?”>

style=“margin-left: 9px”>

style=“margin-left: 39px”>

三、实验步骤

第五篇：北邮数据结构实验报告 单链表

北京邮电大学 数据结构试验报告

实验名称： 实验一

线性表 学生姓名：

班

级：

班内序号：

学

号：

日

期： 2014年1月3日

实验目的

 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法  学习指针、模板类、异常处理的使用  掌握线性表的操作的实现方法  学习使用线性表解决实际问题的能力 实验内容

2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：

1、带头结点的单链表

2、不带头结点的单链表

3、循环链表

4、双链表

5、静态链表

线性表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序

3、删除

4、查找

5、获取链表长度

6、销毁

7、其他：可自行定义

编写测试main()函数测试线性表的正确性。程序分析

3.1 存储结构 单链表的存储结构：

3.2 关键算法分析

一、关键算法 1.头插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.修改新结点的指针域

d.修改头结点的指针域,将新结点加入链表中 代码描述： template LinkList::LinkList(T a[], int n)//头插法建立 {

front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){ Node* s = new Node;s->data = a[i];

}

} s->next = front->next;front->next = s;时间复杂度：O(n)

2.尾插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.将新结点加入到链表中

d.修改修改尾指针 代码描述: template LinkList::LinkList(T a[], int n)//尾插法建立 {

front = new Node;front->next=NULL;Node * r = front;for(int i=0;i * s = new Node;

}

} s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度：O(n)

3.析构函数

自然语言描述：a.新建立一个指针，指向头结点

b.移动a中建立的指针

c.逐个释放指针

代码描述: template LinkList::~LinkList()//析构函数，销毁链表 {

Node * 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 Node* LinkList::Get(int i)//按位查找 {

Node * p = front;int j=0;while(p){

if(j

} else break;p = p->next;j++;

} 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 int LinkList::Locate(T x)//按值查找 {

Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else { p = p->next;

j++;} } 时间复杂度：O(n)6.插入函数

自然语言描述： a.在堆中建立新结点

b.将要插入的结点的数据写入到新结点的数据域

c.修改新结点的指针域

d.修改前一个指针的指针域，使其指向新插入的结点的位置

代码描述: template void LinkList::Insert(int i,T x)//插入函数 {

Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 时间复杂度：O(n)7.按位删除函数

自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点

b.设q指向第i个元素

c.将q元素从链表中删除

d.保存q元素的数据

e.释放q元素 代码描述: template T LinkList::Delete(int i)//删除函数 { Node *p = Get(i-1);Node *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 void LinkList::PrintList()//打印链表 {

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;9.获取链表长度函数

自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0

b.如果不是空链表，新建立一个temp指针，初始化整形数n为0

c.将temp指针指向头结点

d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n

e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template int LinkList::GetLength()//分析链表长度 {

} Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;4 程序运行结果

4.1主函数流程图

4.2程序运行框图

实验心得

1.调试时出现的问题及解决的方法

在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。2.心得体会

了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进

可以增加完善报错机制，增强程序的健壮性

完整源代码

#include using namespace std;

template struct Node {

};

template class LinkList { public:

};

//template //LinkList::LinkList(T a[], int n)//头插法建立 LinkList(){ front = new Node;front->next = NULL;}//无参构造函数 LinkList(T a[],int n);//构造函数 void Insert(int i,T x);//插入函数 T Delete(int i);//删除函数

Node* Get(int i);//查找第几个的元素，返回的是该元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析链表长度 ~LinkList();//析构函数 void PrintList();//打印链表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

template LinkList::LinkList(T a[], int n)//尾插法建立 {

}

template LinkList::~LinkList()//析构函数，销毁链表 {

}

template void LinkList::PrintList()//打印链表 { Node * p = front;while(p){

} front = p;p = p->next;delete front;front = new Node;front->next=NULL;Node * r = front;for(int i=0;i

} Node * s = new Node;s->data = a[i];s->next = r->next;r->next= s;r=s;front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){

} Node* s = new Node;s->data = a[i];s->next = front->next;front->next = s;

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;

template Node* LinkList::Get(int i)//按位查找 {

}

template int LinkList::Locate(T x)//按值查找 {

} Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else

{ } p = p->next;

j++;Node * p = front;int j=0;while(p){

} if(!p)throw“查找位置非法”;else

return p;if(j

} else break;p = p->next;j++;

template void LinkList::Insert(int i,T x)//插入函数 {

}

template T LinkList::Delete(int i)//删除函数 {

}

template int LinkList::GetLength()//分析链表长度 {

}

void main(){ Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;Node *p = Get(i-1);Node *q = p->next;p->next = q->next;delete q;return x;Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;

T x=q->data;

} int n;cout<<“将要输入的链表长度为：”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“链表的长度:”<>i;cout<<“被删除掉的元素是：”<>j;cout<<“要将其插入在哪个位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的链表是：”;a.PrintList();cout<<“要查找第几个元素：”;cin>>i;cout<<“要查找的元素为：”<data<>j;cout<<“输入的元素位置在：”<