线性表的链式存储结构实验报告总结

实验报告

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

实验日期：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） 学院： 专业： 班级： 姓名 实验时间 实验项目名称 实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．掌握对链表进行创建、插入、删除和查找等操作的算法。 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. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

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时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式

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

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

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

#include \#include \#include \

#define MAX 4 #define LISTINCREMENT 3

// 学生结构体 typedef struct { char no[10]; char name[20]; char gender; float score; } STU;

// 动态数组的初始长度 // 动态数组长度不够时，每次增加的长度

// 动态顺序表结构体

typedef struct { STU *s; // 存放学生的动态数组的起始地址，数组大小可以扩充，因此称其为“动态” int listSize; // 当前顺序表中数组单元的个数 int length; // 当前表中元素的个数（肯定小于数组单元的个数） } SeqList;

// 功能菜单 void menu() { printf(\动态顺序表(顺序表空间可以扩充)***\\n\ printf(\ 1 插入一个学生 *\\n\ printf(\ 2 删除一个学生 *\\n\ printf(\ 3 修改学生信息

实验一 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+