数据结构与算法实验报告线性表

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

2010级数据结构实验报告

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

**

2010年11月4日第1页

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

1．实验要求

一、实验目的

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

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

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

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

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

2. 程序分析

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

数据结构实验报告（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

第 2 章 线性表

课后习题讲解 1. 填空

⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。

【解答】表长的一半，表长，该元素在表中的位置

⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。 【解答】108

【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108

⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。

【解答】p->next=(p->next)->next

⑷ 单链表中设置头结点的作用是（ ）。 【解答】为了运算方便

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。 【解答】p->next=head 【分析】如图2-8所示。

⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。

【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->

三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。

四、已知一个单向链表，试给出复制该链表的算法。

要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作

3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。

五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数： int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。

2、定义线性表的基本操作

3、在1，2的基础上，完成本题。

4、在main函数中进行

线性表实验报告+二叉树实验报告

实验报告

班级： 学号： 姓名： 日期：

1. 实验题目

编辑一个程序，用来演示线性表的建立、插入、删除等操作。

2. 需求分析

本演示程序在Microsoft Visual C++ 6.0环境下编写调试，完成线性表的生成、任意位置的插入、删除等。

（1）输入的形式和输入的范围：执行插入操作时，需要输入插入位置和元素的值；执行删除操作时，需要输入待删除元素的位置。在所有输入中，元素的值都是由整数、字符数组和字符数组组成的。

（2）输出的形式：在所有操作中都要求显示相关操作是否正确以及操作后线性表的内容。其中删除操作完成后，要显示删除后所剩的元素的值。

（3）程序所能达到的功能：完成线性表的生成、插入、删除操作。

3. 概要设计

（1）为了实现上述程序功能，需要定义线性表的数据结构。线性表单个元素的结构如图1.1所示。

图1.1 线性表元素的数据结构

（2）本程序包含6个函数： ①主函数main()。

②初始化线性表函数creat()。 ③插入元素函数insert()。 ④删除元素函数del()。

线性表实验报告+二叉树实验报告

各函数间的关系如图1.2所示

数据结构与算法

实 验 报 告

编制教师 袁宇丽 审定 何文孝

（适用于计算机科学学院2012级本科学生）

专业: 班级: 级 班 学号:________________________ 姓名:________________________ 2013至2014学年第二学期

计算机科学学院

实验名称：线性表的应用 指导教师： 余文春 实验日期：2014年 月 日 实验地点：北503 成绩： 实验目的：

1、 掌握线性表及其顺序存储与链式存储结构的概念。 2、 掌握两种存储方式的基本运算、实现方法和技术。 3、 灵活应用线性表进行程序设计，解决实际问题。 实验内容：

约瑟夫(Joseph)问题的一种描述是：编号为1，2，?，n的n个人按顺时针方向围坐一圈，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，同样报到m的人出列，如此下去，直至所有人全部出列为止。利用循环链表为存储结构模拟此过程

金陵科技学院实验报告

学 生 实 验 报 告 册

课程名称：算法与数据结构

金陵科技学院实验报告

实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 工科楼A205 实验日期： 2013年10月16日 实验成绩： 批改教师： 批改时间：

金陵科技学院实验报告

实验1 顺序表

一、实验目的和要求

掌握顺序表的定位、插入、删除等操作。

二、实验仪器和设备

Turbo C 2.0

三、实验内容与过程（含程序清单及流程图）

1、必做题

（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。

编写主函数测试结果。

（2） 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。

如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。

解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素

数据结构实验报告

题目： 线性表 班级：网络工程1401班 学号： 1408020106 指导教师： 高峰 日期： 2016/7/6

实验一：线性表

一：实验要求

掌握数据结构中线性表的基本概念。

熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构撒谎能够的实验。 熟练掌握链表的各种操作和应用。

二．实验内容

1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。

2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。

三：实验过程及步骤

源代码：

#include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int * elem; int length; int listsize; }SqList; //SqList sq;

void InitList_Sq(SqList *sq) //初始化列表 {

sq->elem=(int *)malloc(LIST_IN

实验一 线性表及其应用

一、实验目的

1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容

1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤

1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示

1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。

在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024

typedef int elemtype; /* 线性表中存放整型元素 */ typedef

实验一 线性表的基本操作

一、实验目的

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