数据结构实验指导书(2)

2019-03-10 18:02

在实验后要总结和整理课程设计报告。

1.3实习报告内容

⒈ 问题描述

包括实验题目(问题描述)、实验目的(实验基本要求)、实验内容(任务)、条件和约束的描述。 ⒉ 设计

⑴ 数据结构设计和核心算法设计描述; ⑵ 主控及功能模块层次结构;

⑶ 主要功能模块的输入、处理(算法框架描述)和输出; ⑷ 功能模块之间的调用与被调用关系等。 ⒊ 测试

测试范例,测试结果,测试结果的分析与讨论,测试过程中遇到的主要问题及所采用的解决措施。 ⒋ 使用说明和作业小结

⑴ 使用说明主要描述如何使用你的程序以及使用时的主要事项;

⑵ 在小结中说明程序的改进思想、经验和体会,并回答教师布置的讨论题。 ⒌打印一份程序清单及运行示例的结果。

将以上各项文字材料及程序清单等装订成册,形成一个完整的报告。

2 实验指导书

实验题目根据实验学时进行选择,综合性和设计性实验每个类别至少做两个题目。

2.1验证性实验

实 验 一 单链表操作验证

题目:单链表操作验证

1.实验目的

(1)掌握线性表的链接存储结构;

6

(2)验证单链表及其基本操作的实现;

(3)进一步掌握数据结构及算法的程序实现的基本方法。 2.实验内容

(1)用头插法(或尾插法)建立带头结点的单链表; (2)对已建立的单链表实现插人、删除、查找等基本操作。 3.实现提示(此为C++版,具体实验用C语言实现,下同) 首先,将单链表中的结点定义为如下结构类型: template struct Node { T data; Node *next; };

其次,定义单链表的数据类型——单链表类LinkList,包括题目要求的插人、删除、查找等基本操作,为便于查看操作结果,设计一个输出函数依次输出单链表的元素。

template<class T> class LinkList { public:

LinkList(T a[ ],int n); //建立有n个元素的单链表 ~LinkList( ); //析构函数

void Insert(int i,T x); //在单链表中第i个位置插入元素值为x的结点 T Delete(int i); //在单链表中删除第i个结点 int Locate(T x); //求单链表中值为x的元素序号 void PrintList(); //遍历单链表,按序号依次输出各元素 private:

Node

再次,设计单链表类LinkList的构造函数和析构函数。

用头插法或尾插法建立单链表。头插法建立单链表的算法如下: 头插法建立单链表 temlate

LinkList::LinkList(T a[],int n) {

first=new Node;

7

first->next=NULL; //初始化一个空链表 for(i=0;i

s=new Node; s->data=a[i]; //为每个数组元素建立一个结点 s->next=first->next;//插入到头结点之后 first->next=s; } }

析构函数用于释放单链表中所有结点,算法如下: 单链表的析构函数算法~LinkList template :: ~LinkList() {

p=first; //工作指针P初始化

while(p) //释放单链表的每一个结点的存储空间 {

q=p; //暂存被释放结点

p=p->next; //工作指针P指向被释放结点,使单链表不断开 delete q; } }

最后,对所建立的单链表设计插人、删除、查找等基本操作的算法。 (l)插人算法 单链表插人算法Insert template

void LinkList::Insert(int i,T x) {

p=first;j=0; //工作指针P初始化 while (p && j

p=p->next; //工作指针P后移 j++; }

if (! p) throw“位置”; else{

s=new Node; s->data=x; //向内存申请一个结点s,其数据域为x s->next=p->next;//将节点s插入到结点p之后

8

p->next=s; } }

(2)删除算法

单链表的删除算法Delete Template T LinkList::Delete(int i) {

P=first ;j=0;//工作指针p初始化 While (p && j

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

if ( ! p | | ! p->next) throw“位置”; //结点p不存在或结点p的后继结点不存在 else{

q=p->next; x=q->data; //暂存被删结点 p->next=q->next; //摘链 delete q; return x; } }

(3)查找算法

单链表查找算法Locate template int LinkList::Locate(T x) {

p=first->next; j=1; while(p && p->data!=x) {

p=p->next; //工作指针p后移 j++; }

if (p) return j; else return 0;

9

}

4.实验程序

//以下为头函数,文件名为LinkList.h #ifndef LinkList_H #define LinkList_H template<class T> struct Node { T data;

Node< T> *next; //此处也可以省略 };

template class LinkList { Public:

LinkList(T a[],int n); //建立有n个元素的单链表 ~LinkList(); //析构函数

void Insert(int i, T x); //在单链表中第i个位置播入元素为x的结点 T Delete(int i); //在单链表中删除第i个结点 int Locate(T x); //求单链表中值为x的元素序号 void PrintList(); // 遍历单链表,按序号依次输出各元素 private:

Node *first; //单链表的头指针 }; #endif

//以下为头函数LinkList.h中LinkList类的成员函数按规定定义,文件名为LinkList.cpp #include\.h\template

LinkList::LinkList(T a[],int n) {

Node * first; first=new Node;

first->next=NULL; //初始化一个空链表

10


数据结构实验指导书(2).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:五年级下册劳动全册教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: