数据结构实验报告

数据结构实验报告

一、实验题目

1.实现线性表的各种基本运算 2.实现单链表的各种基本运算 3.合并两个单链表 二、实验目的

1.熟悉将算法转换为程序代码的过程。

2.了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。

3.熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存储特性。 4.了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。 5.熟练掌握线性链表的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。 三、实验要求

1.熟悉顺序表的插入、删除和查找 2.熟悉单链表的插入、删除和查找 四、实验内容

（1）实现顺序表的各种基本运算 抽象数据类型的定义：

我设计的顺序表包含的基本操作为：插入、删除、查找，基本功能为：构造一个空的顺序表。

存储结构定义及算法思想：

存储结构为：顺序表 数据元素类型为：整型 主要函数算法的实现思路：

A.插入： 一般情况下，在第i个元素之前插入一个元素时， 需将第n至第i(共n-i+1个元素)依次向后移动一个位置。在进行插入操作时 ，还需考虑两种情况，第一，插入位置的正确性，第二如果原表已满，需要为顺序表重新分配存储空间。

B.删除：一般情况下，删除第i个元素时，需将从第i+1至第n个元素（共n-i个元素）依次向前移动一个位置。进行删除操作前，只需考虑删除的位置是否合理，不需要考虑容量问题。

C.查找：基本操作是“进行两个元素之间的比较”，若L中存在和e相同的元素ai则比较次数为i,否则为L.length. 实验结果与分析：

运行截图：

插入操作：

删除操作：

查找操作：

心得体会：

在做顺序表的基本操作实验时，遇到很多问题，首先我做的第一步是看书，把书上的代码都看懂，在看顺序表存储结构的定义时，里面有两个变量，一个listsize,一个length,分别代表的是顺序表的存储容量(以sizeof(ElemType)为单位)和当前长度，当时没有注意到length是指的当前长度，所以脑子里面一直以为length=listsize*sizeof(ElemType),后来发现不对，才注意到length是指的当前长度，单位和listsize一致，大小小于等于listsize。还有一个地方就是书上在编写插入功能时有一条语句q=&(L.elem[i-1]);我看了以后不太懂，因为L.elem显然是一个指针，里面存放的地址，但是L.elem[i-1],这种写法，我还不是很熟悉，基本上没有见过，所以我就去网上查找了一下，后来明白了它的意思，并在程序中给出了注释，便于理解。注释如下://elem[i-1]等价于*（elem+i-1）,特别注意这点,表示的意思是顺序表中第i个元素，前面加取地址后赋给q,即q指向了顺序表的第i个元素，这里q表示一个指针变量。所以以后看书还是要细心，仔细的去琢磨，不要留模糊的东西。

第二步我做的是将书上的代码敲到VC里面去，敲过去后，我编译了一下，发现了很多问题，包括一系列的未定义，错误等语法问题，然后仔细的看了一下书，书上写的基本都是伪代码，里面用到的一些变量，很多都没用定义，还有一些字符，需要用#define去定义，所以我在看懂了代码的基础上进行了第三步。

第三步我做的就是将书上的伪代码编写成完整的程序，包括头文件的定义，如基本输入输出函数#include ,还有#include 等，还有一些宏定义，如#define OK 1,#define ERROR 0等，还有在函数功能编写时，为一些变量进行定义等等一系列，具体的见附上的部分重要代码。

（2）实现单链表的各种基本运算

抽象数据类型的定义：

我设计的顺序表包含的基本操作为：插入、删除、查找，基本功能为：构造一个空的单链表。

存储结构定义及算法思想：

存储结构为：单链表 数据元素类型为：整型 主要函数算法的实现思路：

A.插入： 为插入数据元素x,首先要生成一个数据域为x的结点，然后插入在单链表中。关键的算法语句如下:s->next=p->next;p->next=s;

B.删除：删除元素时，仅需修改结点a的指针，假设p为指向结点a的指针，则修改指针的语句为：p->next=p->next->next;

C.查找：在函数中，给出要查找的元素值，要求查找出元素的位置，采用指针后移位的方式，即p=p->next;来遍历单链表进行查找。 实验结果与分析：

插入元素:

删除元素：

查找元素：

心得体会：

有了之前顺序表的经验，这次单链表的代码敲的很快，首先是熟练度有所提升，另外， 哪里需要注意什么，哪里需要定义，在把书上的代码敲上去的时候，就已经会补充了， 所以整个代码基本上是一次完成，编译后的错误也很快的能够找到。 （3）实现作业题3

作业题3，我在前面编写的单链表的基础上稍加修改了一下，这里不再过多的描述，直接给出实验结果运行：

首先是利用之前的函数，创建了两个新的链表，并给两个新链表分别赋值，接着就编写了一个合并链表的函数，将两个链表合并起来，如图运行所示。

附录：

1.顺序表重要源代码

#include #include //包含头文件

typedef int ElemType ; typedef int Status ; #define OVERFLOW 0 #define OK 1 #define ERROR 0 //宏定义

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; //存储空间基地址，用于malloc函数分配存储空间接受地址 int length; //顺序表长度 int listsize; //分配的存储容量，以ElemType类型为单位 }SqList;

//顺序表的存储结构定义 //函数声明:

Status InitList_Sq(SqList &L); //构造一个空的线性表

Status ListInsert_Sq(SqList &L,int i,ElemType e);

//顺序表元素的插入运算

Status ListDelete_Sq(SqList &L,int i,ElemType &e); //顺序表元素的删除运算

Status compare(ElemType x, ElemType y); //比较函数

Status ListEmpty(SqList &L); Status ListLength(SqList &L); Status DestroyList(SqList &L); Status ClearList(SqList &L);

int LocateElem_Sq(SqList L,ElemType e,Status (* compare)(ElemType ,ElemType)); //顺序表元素的查找

以上这些是将伪代码补充成完整程序的重要部分，包括一些函数的定义，头文件的包含，宏定义等等，没有这些，伪代码是不可能变成执行程序的，而关于删除，插入，查找的具体函数体，因为是照书本敲出（自己也将书本函数体里没定义的变量一一定义了）这里不再给出。我的整个程序的结构就是三部分：

定义

Void main(); 函数体();

由于比较多，重要的函数体部分和书上的一样，所以不方便将整个程序全部附上。 2.单链表的重要源代码：

有了顺序表的经验，单链表的前面的一些定义也基本上和顺序表差不多，函数体也是书上的完善，这里不再给出。 3.作业题3:

作业题3我在单链表的基础上修改了一下，保留了插入元素功能，增加了合并功能，所以这里贴出合并函数体。

void MergeList(LinkList &ha,LinkList &hb,LinkList &hc) { LinkList pa, pb;pa=ha; pb=hb; while(pa->next && pb->next) { pa=pa->next; pb=pb->next; } if(!pa->next) { hc=hb; while(pb->next) pb=pb->next; pb->next=ha->next; } else { hc=ha; while(pa->next) pa=pa->next; pa->next=hb->next; } }

本文来源：https://www.bwwdw.com/article/yd4t.html