线性表的链式存储结构操作实现实验报告

实验报告

课程名称：数据结构与算法分析 实验名称：链表的实现与应用

实验日期：2015.01.30 班级： 数媒1401 姓名： 范业嘉 学号 1030514108 一、实验目的

掌握线性表的链式存储结构设计与基本操作的实现。

二、实验内容与要求

⑴定义线性表的链式存储表示；

⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试；

⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。

⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。

三、数据结构设计

1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表

2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数

实验一：线性表的链式存储结构

【问题描述】

某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：

（1） 显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。

（2） 在链表中删除一个最高分和一个最低分的结点。

（3） 计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】

（1） 建立一个评委打分的单向链表；

（2） 显示删除相关结点后的链表信息。

（3） 显示要求的结果。

【实验步骤;】

（1） 运行PC中的Microsoft Visual C++ 6.0程序，

（2） 点击“文件”→“新建” →对话窗口中“文件” →“c++ Source File” →在“文

件名”中输入“X1.cpp” →在“位置”中选择储存路径为“桌面” →“确定”，

（3） 输入程序代码，

程序代码如下:

head=create(PWRS);

printf("所有评委打分信息如下:\n");

print(head);//显示当前评委打分

calc(head);//计算成绩

printf("该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n");

print(head);//显示去掉极限分后的评委

实验二线性表的链式存储及其操作

实验项目：线性表的链表实现：遍历、插入、删除、翻转 实验类型: 基础性 一【指导思想】

用链表存储线性表，实现线性表的基本操作。 二【实验目的及要求】

1、复习C语言的指针的定义、链表的使用； 2、理解线性表的属性；

3、实践线性表的链式实现方法以及相关的操作。

4、要求：提交实验报告，附源程序中填空的内容（10处）、打印运行结果 涉及的知识点：

线性表的逻辑属性、运算

带表头的单链表的操作：定义、输入、输出、链表内容的翻转 元素/链表的操作：元素的插入、删除 三【实验内容】

实现链表的输入、输出、插入、删除、翻转等功能，教师提供主要源代码，问题描述：用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。 实验步骤：

读懂后面附带的源代码，在标注“填空”的位置填写适当的表达式或语句，使得程序完成指定功能。 测试要求：

1、连续插入5个实数；要求：插入的元素要分别位于表头、表中、表尾，以确保该

实验二：线性表的链式表示和实现

实验二：线性表的链式表示和实现

一、实验目的：

1．掌握线性表的链式存储结构的表示与实现.

2．掌握对链表进行创建、插入、删除和查找等操作的算法。 3．掌握算法的设计与分析过程。

4．进一步熟悉VC++开发环境，熟悉完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。

二、实验要求：

1．采用教材中c语言描述的单链表存储结构，模块化设计过程，设计高效的算法完成各种操作任务，针对实际数据实现各种操作。

2．完成程序编写，调试成功后，书写实验报告。

三、实验任务：

1．创建有n（n为正整数）数据元素的单链表，数据从键盘输入。 2．查找第i个结点，找到返回其值，否则返回0； 3．对已经创建的单链表分别进行插入结点操作，在第i个元素之前插入1个结点。

4．删除结点，将第i个结点的元素删除。 5．将单链表进行就地逆转。

6．将链表按值的奇偶数分解成两个链表。 要求：创建单链表后，其他操作可以是任意选择进行的。（考虑设计菜单调用各功能模块）

四、设计指导：

1．结点的定义 #include #include typedef int DataType; typedef struct node {DataTy

数据结构实验报告（1） 学院： 专业： 班级： 姓名 实验时间 实验项目名称 实1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现； 验2. 以线性表的各种操作（建立、插入、删除等）的实现为重点； 目3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 的 实验 条件 实1. 根据实验内容编程，上机调试、得出正确的运行程序。 验原理 实 验 2011-10-28 学号 指导教师 线性表的顺序存储结构 实验组 成绩 运行Visual c++的微机一台 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果 #include #include using namespace std; typedef int ElemType; struct List{ ElemType *list; int size; in

希望对你有所帮助!

实验二 线性表(顺序存储)

一、实验目的

1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

2. 重点是线性表的基本操作在两种存储结构上的实现；本次实验以顺序存储的操作为侧重点；并进一步学习结构化的程序设计方法。

二、实例

1. 线性表的顺序存储表示（结构）及实现。

阅读下列程序请注意几个问题：

（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体：

typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组 子域 */

int length; /* 表长度子域 */

}SqList; /* 顺序存储的结构体类型 */

（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料

北京邮电大学信息与通信工程学院

2010级数据结构实验报告

实验名称： 实验一——线性表（约瑟夫问题） 学生姓名： 在这我就不写了 班 级： ** 班内序号： ** 学 号：日 期：

**

2010年11月4日第1页

北京邮电大学信息与通信工程学院

1．实验要求

一、实验目的

通过实现约瑟夫问题，掌握如下内容：

1、 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法； 2、 学习指针、模板类、异常处理的使用； 3、 掌握线性表的操作实现方法；

4、 培养使用线性表解决实际问题的能力。 二、实验内容

利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：有n个人(n>=1)围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，顺时针数到m的那个人出列，他的下一个然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列。请问最后一个出列的人的编号。

2. 程序分析

对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式

实验一 线性表基本操作的编程实现

【实验目的】

线性表基本操作的编程实现 要求：

线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。

【注意事项】

1.开发语言：使用C。

2.可以自己增加其他功能。

【思考问题】

1. 线性表的顺序存储和链表存储的差异？优缺点分析？ 2. 那些操作引发了数据的移动？ 3. 算法的时间效率是如何体现的？

4. 链表的指针是如何后移的？如何加强程序的健壮性？

【参考代码】（以下内容，学生任意选择一个完成即可）

（一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include

#include

#define L

实验一：线性表逆置（顺序表）实验报告

（一） 问题的描述： 实现顺序表的逆置算法 （二） 数据结构的设计：

顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： typedef struct {

ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */

int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList;

（三） 函数功能、参数说明及概要设计： 1.函数Status InitList(SqList *L) 功能说明：实现顺序表L的初始化

算法设计：为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明：返回顺序表L长度 算法设计：返回顺序表中的length变量

3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明：将元素e插入到顺序表L中的第i个节点

算法设计：判断顺序表是否已满，已满则加空间，未满则继续，将元素e插入到第i个元素之前，并将后面的元素依次往后移

4.函数S

实验一 线性表的基本操作

一、实验目的

1、理解线形表的定义、特征和相关概念； 2、理解线形表的顺序存储结构； 3、掌握上机调试线性表的基本方法。 二、实验条件

1、PC机

2、软件Visual C++ 三、实验原理

线性表的顺序存储结构是用一组地址连续的存储单元依次存放线性表中的元素。其实现手段是数组类型。由于内存中的元素存放顺序与逻辑上的顺序相同，所以元素的地址就体现了逻辑关系，即物理相邻=逻辑相邻；在插入或者删除某一个元素时，其后的所有元素也要做相应的后移或者前移，即有可能要移动大量元素。 四、实验内容

1、利用两个线形表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B，用顺序表实现；

2、对给定的两个集合能够进行合并，并给出合并结果； 五、算法分析

void union(List &La, List Lb){ La_len = ListLength(La); Lb_len = ListLength(Lb); for (i=1; i<=Lb_len; i++){ GetElem(Lb,i, e);

If(!LocateElem(La,e,equal)) ListInsert(La, ++L