数据结构实验二

苏州科技学院数据结构（C语言版）实验报告 专业班级 测绘1011 学 号 10201151 姓 名 XX 实习地点 C1 机房 指导教师 史守正 目 录封面………………………………………………………………………1目录………………………………………………………………………2实验一 线性表…………………………………………………………3一、程序设计的基本思想，原理和算法描述…………………………………3二、源程序及注释（打包上传）……………………………………………3三、运行输出结果………………………………………………………… 4四、调试和运行程序过程中产生的问题及采取的措施………………………6五、对算法的程序的讨论、分析，改进设想，其它经验教训…………………6实验二 栈和队列……………………………7一、程序设计的基本思想，原理和算法描述……………………………8二、源程序及注释（打包上传）……………………………8三、运行输出结果…………………………………………………………8四、调试和运行程序过程中产生的问题及采取的措施………………………10五、对算法的程序的讨论、分析，改进设想，其它经验教训………………10实验三 树和二叉树………………………………………………11一、程序设计的基本思想，原理和算法描述………………………………11二、源程序及注释（打包上传）……………………………………………12三、运行输出结果…………………………………………………………12四、调试和运行程序过程中产生的问题及采取的措施………………………12五、对算法的程序的讨论、分析，改进设想，其它经验教训………………12实验四 图…………………………………………………………13一、程序设计的基本思想，原理和算法描述………………………………13二、源程序及注释（打包上传）……………………………………………14三、运行输出结果…………………………………………………………14四、调试和运行程序过程中产生的问题及采取的措施………………………15五、对算法的程序的讨论、分析，改进设想，其它经验教训………………16实验五 查找…………………………………………………………17一、程序设计的基本思想，原理和算法描述………………………………17二、源程序及注释（打包上传）……………………………………………18三、运行输出结果…………………………………………………………18四、调试和运行程序过程中产生的问题及采取的措施………………………19五、对算法的程序的讨论、分析，改进设想，其它经验教训………………19实验六 排序…………………………………………………………20一、程序设计的基本思想，原理和算法描述………………………………20二、源程序及注释（打包上传）……………………………………………21三、运行输出结果…………………………………………………………21四、调试和运行程序过程中产生的问题及采取的措施………………………24五、对算法的程序的讨论、分析，改进设想，其它经验教训………………24实验一 线性表一、程序设计的基本思想，原理和算法描述：程序的主要分为自定义函数、主函数。自定义函数有InitList_Sq、Out_List、ListInsert_Sq、ListDelete_Sq、LocateElem_Sq、compare。主函数在运行中调用上述的自定义函数，每个自定义函数实现程序的每部分的小功能。1.程序设计基本思想用c语言编译程序，利用顺序存储方式实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行数据的插入、删除、查找，并在插入或删除数据后，再输出线性表；最后在屏幕菜单中选择结束按钮，即可结束程序的运行。2．原理线性表通过顺序表现，链式表示，一元多项式表示，其中链式表示又分为静态链表，双向链表，循环链表等，在不同的情况下各不相同，他可以是一个数字，也可以是一个符号，通过符号或数字来实现程序的运行。3.算法描述（1）输入的形式和输入值的范围：执行插入操作时，需要输入插入的位置的元素的值；执行删除操作时，需要输入待删除元素的位置；执行查找操作时，需要输入待查找元素的值。在所有输入中，元素的值都是整数。（2）输出的形式：在所有操作中都要求显示相关操作是否正确以及操作后单链表的内容。其中删除操作完成后，要显示删除元素的值；查找操作完成后，若找到待查元素，则显示该元素在单链表中的位置。反之，给出不能找到的信息。（3）程序功能：完成单链表的生成、插入、删除、查找操作。（4）测试数据： ①依次输入元素12，34，56， 78， 90，生成一个单链表。 ②插入操作中在位置4上插入元素10。 ③删除操作中输入5 78，删除位于5的元素78。 ④查找操作中输入56，输出元素在单链表中的位置是3。二、源程序及注释（打包上传）：三、运行输出结果：- 5 -

1 第2章 线性表

线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。

重点提示：

 线性表的逻辑结构特征

 线性表的顺序存储和链式存储两种存储结构的特点

 在两种存储结构下基本操作的实现

2-1 重点难点指导

2-1-1 相关术语

1．线性表

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,an)，其中n为表长，n=0时称为空表。

要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。

2．顺序表

顺序存储的线性表。

要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。

3．链表

用链表存储的线性表。

要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。

4．单链表

每个结点除了数据域外还有一个指向其后继的指针域。

要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。

5．头指针

要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。

6．头结点

要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。

2 7．头结点的作用

要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2-1-2 线性表的顺序存储

1．顺序表

《数据结构》实验报告

实验序号：3 实验项目名称：链式表的操作

学 号 姓 名 专业、班

实验地点 指导教师 实验时间

一、实验目的及要求

1. 通过实验理解单链表的逻辑结构；

2. 通过实验掌握单链表的基本操作和具体的函数实现。

二、实验设备（环境）及要求

微型计算机；

windows 操作系统；

Microsoft Visual Studio 6.0集成开发环境。

三、实验内容与步骤

1.链式表表示和实现线性表的如下：

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"ctype.h"

typedef struct node //定义结点

{

char data[10]; //结点的数据域为字符串

struct node *next; //结点的指针域

}ListNode;

typedef ListNode * LinkList; // 自定义LinkList单链表类型

LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表

ListNode *LocateNode(LinkList head, char *key); //函数，按值查找结点

void DeleteList(LinkList head,char *key); //函数，删除指定值的结点

void printlist(LinkList head); //函数，打印链表中的所有值

void DeleteAll(LinkList head); //函数，删除所有结点，释放内存

江 西 科 技 师 范 大 学

实 验 报 告

课 程 数据结构B

系 别 大数据科学学院

班 级

22信息管理与信息系统

学 号 ********

姓 名 杨圣洲

报

告

规

格

一、实验目的

二、实验原理

三、实验仪器

四、实验方法及步骤

五、实验记录及数据处理

六、误差分析及问题讨论

目 录

实验一 线性表的顺序存储 ...................................... 1

实验二 线性表的链式存储 ...................................... 2

实验三 二叉树 ................................................ 3

实验四 图 ..................................................... 4

实验五 检索 .................................................. 5

实验六 内排序 ................................................ 6

每次实验课必须带上此本子，以便教师检查预习情况和记录实验原始数据。

实验时必须遵守实验规则。用正确的理论指导实践必须人人亲自动手实验，但反

对盲目乱动，更不能无故损坏仪器设备。

这是一份重要的不可多得的自我学习资料它将记录着你在大学生涯中的学习和学

习成果。请你保留下来，若干年后再翻阅仍将感到十分新鲜，记忆犹新。它将推动你在

人生奋斗的道路上永往直前！江 西 科 技 师 范 大 学 实 验 报 告

22年级

信息管理与信息系统

班

20224729号姓名

杨圣洲

同组姓名

实验日期

2024年6月18日成绩

指导老师：郑睿颖 第 1 页

实验一 线性表的顺序存储

实验名称：实验一 线性表的顺序存储

实验目的：

1、掌握线性表顺序存储结构的描述，学会对顺序存储线性表的基