线性表链式存储与操作实验报告

实验报告

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

实验日期：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. 重点是线性表的基本操作在两种存储结构上的实现；本次实验以顺序存储的操作为侧重点；并进一步学习结构化的程序设计方法。

二、实例

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

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

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

typedef struct

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

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

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

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

数据结构实验报告（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、建立一个空顺序存储结构队列； 对已建立的队列进行插入、删除、取队头元素等基本操作。

2、建立一个空链式存储结构队列； 对已建立的队列进行插入、删除、取队头元素等基本操作。

三、详细设计：

1、顺序队列的实现：

#include using namespace std;

const int Size=100; typedef char DataType;

class CirQueue { public:

CirQueue() { }

~CirQueue(){}

void EnQueue(DataType x) {

if((rear+1)%Size==front) { }

cout<<\队列已经满了\<

front=rear=0;//构造队列，初始化一个空的循环队列，front和rear指向

};

}

rear=(rear+1)%Size;//队尾指针在循环的意义下加 data[

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

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

一、实验目的：

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

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

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

顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： 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

实验一 VC++软件的熟悉与使用

一、 实验目的

1、 熟悉VC++控制台程序的建立、编辑、编译、运行步骤。

2、 熟悉VC++环境下调试的基本方法。

二、 实验原理

在VC++6.0 下建立、编译、调试并运行一个控制台程序，程序的功能描述是：有n个人（1≤n≤100）围成一圈，顺序排号（1~n）。从第一个人开始报数（从1到5报数），凡报到5的人退出圈子，余下的人继续报数，编写程序，实现按退出圈子的先后顺序输出这个序列。程序源代码如下：

#include<stdio.h>

#include<stdlib.h>

void main( )

{

int i,k,m,n,number[100],*p;

printf(“input count of person:n=”);

scanf(“%d”,&n);

if(n>100)

{

printf(“error\n”);

exit (0);

}

p=number;

for(i=0;i<n;i++)

*(p+i)=i+1;

i=0;

k=0;

m=0;

while(m<n-1)

{

if(*(p+i)!=0) k++;

if(k==5)

{

printf(“%d:%d->”,m+1,*(p+i));

*(p+

实验二 线性表的基本操作

一、实验目的

1. 掌握使用VC++6.0上机调试线性表的基本方法；

2. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。

3. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在链式存储结构上的运算。

二、实验要求

1. 认真阅读和掌握本实验的程序。 2. 补全程序上机调试。

3. 保存程序的运行结果和程序清单，并结合程序进行分析

三、实验内容

1. 顺序表基本操作的实现：包括顺序表的创建、插入、删除和查找，请补全程序并调试。 第1步：任务分析

完成顺序表的建立，插入，删除和查找等函数功能，有助于更好的理解顺序表的概念和使用规律。上述函数都是线性表的基本操作，根据这些基本操作，可以构成其他更复杂的操作。

第2步：程序构思

(1) 顺序表的创建：因为顺序表的结构中包括了存放数据元素的起始地址，表的容量，以及表的当前长度等部分，所以表的创建工作一方面要为这些成员赋值，而存放数据元素的空间也需要在此处进行分配，因此整个创建工作包括了空间的创建和各个成员的赋值操作。

(2) 顺序表的插入：因为顺序表中的元素是连续存放的，元素之间的关系是通过位置的相邻性来体现的。因此在顺序表