数据结构实验报告.doc

《数据结构》
实验报告
姓名：
学号：
班级：
学院：
实验一单链表实验
(一) 实验目的
1. 理解线性表的链式存储结构。
2. 熟练掌握动态链表结构及有关算法的设计。
3. 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。
(二) 实验任务
编写算法实现下列问题的求解
1. 求链表中第 i 个结点的指针（函数），若不存在，则返回 NULL。
2. 在第 i 个结点前插入值为 x 的结点。
3. 删除链表中第 i 个元素结点。
4. 在一个递增有序的链表 L 中插入一个值为 x 的元素，并保持其递增有序特性。
5. 将单链表 L 中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将
这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。
6. 求两个递增有序链表 L1 和 L2 中的公共元素，并以同样方式连接成链表 L3。
(三) 主要仪器设备
PC 机，Windows 操作平台，Visual C++
(四) 实验分析
顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插
入、删除、遍历等操作的方法
(五) 源程序
头文件文件名：
#include<iostream>
using namespace std;
struct node
{
int data;
node *next;
};
class list
{
public:
list();
int length()const
{
return count; //求链表长度
}
~list();
void create(); / /链表构建，以 0 为结束标志
void output(); / /链表输出
intget_element(constinti)const; / /按序号取元素
node *locate(constint x) const; / /搜索对应元素
int insert(constinti,constint x); / /插入对应元素
intdelete_element(constinti); / /删除对应元素
node *get_head()
{
return head; //读取头指针
}
void insert2(constint x);
friend void SplitList(list L1, list&L2, list &L3);
friend void get_public(list L1, list L2, list &L3);
private:
int count;
node *head;
};
list::list()
{
head=new node;
head->next=NULL;
count=0;
}
void list::create() //链表构建，以 0 为结束标志
{
int x;
cout<<"请输入当前链表，以 0 为结束符。\n";
cin>>x;
node *rear=head;
while(x!=0)
{
count++;
node *s=new node;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
void list::output()
{
node *p=head->next;
cout<<"******Top of this list******"<<endl;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl<<"******End of this list******"<<endl;
}
int list::get_element(constinti)const //实验 1
{
intx,j;
node *p;
p=head->next;
j=1;
while(p!=NULL && j!=i)
{
p=p->next;
j++;
}
if(p==NULL) return 0;
else
{
return x=p->data;
return 1;
}
}
node *list::locate(constint x)const
{
node *p=head->next;
while(p!=NULL)
if(p->data==x)return p;
else p=p->next;
return N