数据结构实验一题目一线性表实验报告

数据结构实验报告

实验名称： 实验1——线性表

学生姓名：

班 级：

班内序号：

学 号：

日 期：

1． 实验要求

1、实验目的： 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法

学习指针、模板类、异常处理的使用

掌握线性表的操作的实现方法

学习使用线性表解决实际问题的能力

2、实验内容：

题目1：

线性表的基本功能：

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

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

3、 删除

4、 查找

5、 获取链表长度

6、 销毁

7、 其他：可自行定义

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

2. 程序分析

2.1 存储结构

带头结点的单链表

2.2 关键算法分析

1.头插法

a、伪代码实现：在堆中建立新结点

将x写入到新结点的数据域

修改新结点的指针域

修改头结点的指针域,将新结点加入链表中

b、代码实现：

Linklist::Linklist(int 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;

}

}

2、尾插法

a、伪代码实现：a.在堆中建立新结点

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

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

d.修改修改尾指针

b、代码实现:

Linklist::Linklist(int a[],int n,int m)//尾插法

{front=new Node;

Node*r=front;

for(int i=0;i<n;i++)

{Node*s=new Node;

s->data=a[i];

r->next=s;

r=s;

}

r->next=NULL;

}

时间复杂度：O(n)

3、按位查找

a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1

循环以下操作，直到p为空或者j等于1

b1：p指向下一个结点

b2：j加1

若p为空，说明第i个元素不存在，抛出异常

否则，说明p指向的元素就是所查找的元素，返回元素地址

b、代码实现

Node* Linklist::Get(int i)//得到指向第i个数的指针

{Node*p=front->next;

int j=1;

while(p&&j!=i)//p非空且j不等于i，指针后移

{p=p->next;

j++;

}

return p;

}

4、插入操作

a、伪代码实现: 如果链表为空，直接插入

判断p的下一个结点的值大于x且p的值小于x

在堆中建立新结点

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

修改新结点的指针域

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

b、代码实现

void Linklist::Insert(int x)//将x按顺序插入

{Node*p=front->next;

if(!p)//如果链表为空，直接插入

{Node*s=new Node;

s->data=x;

s->next=front->next;

front->next=s;

}

else

while(!((p->next->data>x)&&(p->data<x)))//判断p的下一个结点的值大于x且p的值

小于x

{p=p->next;}

Node*s=new Node;//将x插入到p之后

s->data=x;

s->next=p->next;

p->next=s;

}

5、删除操作

a、伪代码实现:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点

设q指向第i个元素

将q元素从链表中删除

保存q元素的数据

释放q元素

b、代码实现

int Linklist::Delete(int i)//删除第i个位置的结点

{Node*p=front;

if(i!=1)

p=Get(i-1);//得到第i-1个位置的指针

Node*q=p->next;

p->next=q->next;

int x=q->data;

delete q;

return x;

}

6遍历打印函数

a、伪代码实现:判断该链表是否为空链表，如果是，报错

如果不是空链表，新建立一个temp指针

将temp指针指向头结点

打印temp指针的data域

逐个往后移动temp指针，直到temp指针的指向的指针的next域为空

b、代码实现

void Linklist::show()//打印数组元素

{Node*p=front->next;

while(p)

{

cout<<p->data<<" ";

p=p->next;

}

}

7.获取链表长度函数

a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0

如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点

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

则return n

使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next

域为0，返回n

b 、代码实现

void Linklist::Getlength()//得到数组长度

{Node*p=front->next;

int j=0;

while(p)

{p=p->next;

j++;}

cout<<j;

}

2.3 其他

源代码

#include<iostream>

using namespace std;

struct Node

{int data;

struct Node* next;

};

class Linklist

{public:

Linklist(int a[],int n);

Linklist(int a[],int n,int m);

Node* Get(int i);

void Insert(int x);

int Delete(int i);

int Locate(int x);

void Getlength();

void show();

~Linklist();

private:

Node*front;

};

Linklist::Linklist(int 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;

}

}

Linklist::Linklist(int a[],int n,int m)//尾插法

{front=new Node;

Node*r=front;

for(int i=0;i<n;i++)

{Node*s=new Node;

s->data=a[i];

r->next=s;

r=s;

}

r->next=NULL;

}

Node* Linklist::Get(int i)//得到指向第i个数的指针

{Node*p=front->next;

int j=1;

while(p&&j!=i)//p非空且j不等于i，指针后移

{p=p->next;

j++;

}

return p;

}

void Linklist::Insert(int x)//将x按顺序插入

{Node*p=front->next;

if(!p)//如果链表为空，直接插入

{Node*s=new Node;

s->data=x;

s->next=front->next;

front->next=s;

}

else

while(!((p->next->data>x)&&(p->data<x)))//判断p的下一个结点的值大于x且p的值

小于x

{p=p->next;}

Node*s=new Node;//将x插入到p之后

s->data=x;

s->next=p->ne …… 此处隐藏：2550字，全部文档内容请下载后查看。喜欢就下载吧 ……