链式存储结构实验报告
学号姓名实验日期2012-12-15
实验室计算机软件技术实验指导教师设备编号401 实验内容实习单元2 线性表
一．实验目的
（1）掌握使用VC++上机调试线性表的基本方法；
（2）掌握线性表的基本操作：插入、删除、查找等运算在链式存储结构上的实现。
二．实验内容
线性表在链式存储结构下的基本操作
三．实验要求
（1）认真阅读和理解实验1.1中给出的程序。并据此写出线性表的各种基本操作在链
式存储结构上的程序。
（2）上机运行写出的程序，并且独立调试通过。
四、给出线性表的抽象数据类型
ADT LinkList0120{
数据对象：D={ a i| a i∈ ElemSet,i=1,2,3,…，n,n≥ 0}
数据关系：R={ |a i-1,a i∈D,i∈2,3,4, …，n,n≥ 0}
基本操作：
InitList_Link0120(LinkList0120 &L);
操作结果：创建一个空的线性表L
ListInsert_Link0120 (LinkList0120 &L,int i,ElemType e);
初始条件：线性表L已存在。
操作结果：在线性表L中第i个位置插入元素e
DestroyList_Link0120(LinkList0120 &L);
初始条件：线性表L已存在。
操作结果：销毁一个线性表L
Status ClearList_Link0120(LinkList0120 &L);
初始条件：线性表L已存在。
操作结果：将线性表L重置
ListEmpty_Link0120 (LinkList0120 L);
初始条件：线性表L已存在。
操作结果：若L为空，则返回TURN，否则返回FALSE。
ListLength_Link0120(LinkList0120 L);
初始条件：线性表L已存在。
操作结果：求线性表L中元素的个数（返回表长）
GetElem_Link0120 (LinkList0120 L,int i,ElemType &e);
初始条件：线性表L已存在。
操作结果：用e返回线性表中第i个元素的值。
LocateElem_Link0120 (LinkList0120 L,
ElemType e,Status (*compare)(ElemType,ElemType)); 初始条件：线性表L已存在。
操作结果：在线性表L中查找元素e
Status PriorElem_Link0120 (LinkList0120 L,ElemType cur_e,ElemType &pre_e); 初始条件：线性表L已存在。
操作结果：用pre_e返回cur_e的前驱
NextElem_Link0120 (LinkList0120 L,ElemType cur_e,ElemType &next_e);
初始条件：线性表L已存在。
操作结果：用next_e返回cur_e的后继
ListDelete_Link0120 (LinkList0120 &L,int i,ElemType &e);
初始条件：线性表L已存在。
操作结果：求线性表L中元素的个数（返回表长）
ListTraverse_Link0120 (LinkList0120 L, Status (*visit)(ElemType));
初始条件：线性表L已存在。
操作结果：对线性表中每个元素调用函数visit()
js_Link0120(LinkList0120 L)
初始条件：线性表L已存在。
操作结果：求奇数个数
os_Link0120(LinkList0120 L)
初始条件：线性表L已存在。
操作结果：求偶数个数
Findd_L0120(LinkList0120 L, Status i, ElemType *e)
初始条件：线性表L已存在。
操作结果：查找倒数第i个元素
五、详细设计
1、给出本数据的存储结构定义及链式存储结构定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
实现线性表的抽象数据类型如下:
typedef int status;
typedef int ElemType; //定义线性表的数据元素类型为int
链式存储实现的抽象数据类型如下：
typedef struct LNode0120
{
ElemType data;
struct LNode0120 *next;
}LNode0120,*LinkList0120;
2.运算的函数声明：
Status InitList_Link0120(LinkList0120 &L);
操作结果：创建一个空的线性表L
Status ListInsert_Link0120 (LinkList0120 &L,int i,ElemType e);
初始条件：线性表L已存在。
操作结果：在线性表L中第i个位置插入元素e
Status DestroyList_Link0120(LinkList0120 &L);
初始条件：线性表L已存在。
操作结果：销毁一个线性表L
Status ClearList_Link0120(LinkList0120 &L);
初始条件：线性表L已存在。
操作结果：将线性表L重置
Status ListEmpty_Link0120 (LinkList0120 L);
初始条件：线性表L已存在。
操作结果：若L为空，则返回TURN，否则返回FALSE。
int ListLength_Link0120(LinkList0120 L);
初始条件：线性表L已存在。
操作结果：求线性表L中元素的个数（返回表长）
Status GetElem_Link0120 (LinkList0120 L,int i,ElemType &e);
初始条件：线性表L已存在。
操作结果：用e返回线性表中第i个元素的值。
Status LocateElem_Link0120 (LinkList0120 L,
ElemType e,Status (*compare)(ElemType,ElemType)); 初始条件：线性表L已存在。
操作结果：在线性表L中查找元素e
Status PriorElem_Link0120 (LinkList0120 L,ElemType cur_e,ElemType &pre_e); 初始条件：线性表L已存在。
操作结果：用pre_e返回cur_e的前驱
Status NextElem_Link0120 (LinkList0120 L,ElemType cur_e,ElemType &next_e); 初始条件：线性表L已存在。
操作结果：用next_e返回cur_e的后继
Status ListDelete_Link0120 (LinkList0120 &L,int i,ElemType &e);
初始条件：线性表L已存在。
操作结果：求线性表L中元素的个数（返回表长）
Status ListTraverse_Link0120 (LinkList0120 L, Status (*visit)(ElemType));
初始条件：线性表L已存在。
操作结果：对线性表中每个元素调用函数visit()
Status js_Link0120(LinkList0120 L)
初始条件：线性表L已存在。
操作结果：求奇数个数
Status os_Link0120(LinkList0120 L)
初始条件：线性表L已存在。
操作结果：求偶数个数
Status Findd_L0120(LinkList0120 L, Status i, ElemType *e)
初始条件：线性表L已存在。
操作结果：查找倒数第i个元素
3.给出操作实现的伪码
Status InitList_Link0120(LinkList0120 &L)
{//构造一个线性链表L
L=(LinkList0120)malloc(sizeof(LNode)); //创建一个结点
if(!L) exit(OVERFLOW); //内存分配失败
L->next=NULL; //p指针域为空
return OK;
}
Status ListInsert_Link0120(LinkList0120 &L, int i, ElemType e)
{//向链表中插入元素
LinkList0120 p = L; int j = 0;
while(p&&j { p = p->next; ++j;//找到第i-1个结点 } if(!p||j>i-1) return ERROR; LinkList0120 s = (LinkList0120)malloc(sizeof(LNode)); //创建一新结点s->data=e; s->next=p->next; p->next=s; return OK; } Status DestroyList_Link0120(LinkList0120 &L) {//销毁单链表L LinkList0120 p = L; LinkList0120 q = L; //p,q同时指向头结点 { q = p; p = p->next; free(q); } return OK; } Status ClearList_Link0120(LinkList0120 &L) {//清空单链表L LinkList0120 p=L->next; while(p) { p->data=NULL; p=p->next; } return OK; } Status ListEmpty_Link0120(LinkList0120 L) {//判断链表L是否为空 LinkList0120 p=L; if(p->next) return TRUE; else return FALSE; } int ListLength_Link0120(LinkList0120 L) {//返回链表L的表长 LinkList0120 p=L; int len=0; while(p->next) { ++len; p=p->next; } return len; } Status GetElem_Link0120(LinkList0120 L, int i, ElemType &e) {//用e返回链表L中第i个元素 LinkList0120 p=L->next; int j=1; { p = p->next; ++j; } if(!p||j>i) return ERROR; e = p->data; return OK; } Status LocateElem_Link0120(LinkList0120 L, ElemType e, Status (__cdecl *compare)(ElemType,ElemType)) { LinkList0120 p = L->next; int i = 1; while(p&&i<=ListLength_Link0120(L) && (*compare)(p->data,e)) { ++i; p = p->next; }//while if(i<=ListLength_Link0120(L)) return i; else return 0; } Status PriorElem_Link0120(LinkList0120 L, ElemType cur_e, ElemType &pre_e) {//求某元素的前驱 LinkList0120 p = L->next; LinkList0120 q = L->next; while(p) { if(p->data==cur_e&&p->data!=L->next->data) { pre_e = q->data; return pre_e; } q = p; p = p->next; }//while return ERROR; } Status NextElem_Link0120(LinkList0120 L, ElemType cur_e, ElemType &next_e) {//求某元素的后继 LinkList0120 p = L->next; while(p) { if(p->data==cur_e&&p->next!=NULL) { next_e = p->next->data; return next_e; } p = p->next; }//while return ERROR; } Status ListDelete_Link0120(LinkList0120 &L, int i, ElemType e) {//删除链表中的元素 LinkList0120 p = L; int j = 0; while(p->next&&j {//寻找第i个结点，p指向被删元素的前驱 p = p->next; ++j; } if(!p->next||j>i-1) return ERROR; LinkList0120 q = p->next; //删除并释放结点 p->next = q->next; e = q->data; free(q); return OK; } Status ListTraverse_Link0120(LinkList0120 L, Status (__cdecl *visit)(ElemType)) {//依次对L的每个数据元素调用函数visit()。一旦visit()失败，//则操作失败LinkList0120 p = L->next; while(p) { if(!(*visit)(p->data)) return ERROR; p = p->next; } return OK; } Status js_Link0120(LinkList0120 L) {//求奇数个数 LinkList0120 p=L->next; Status i=0; while(p) { if(!(p->data%2==0)) i++; p=p->next; } return i; } Status os_Link0120(LinkList0120 L) {//求偶数个数 LinkList0120 p=L->next; Status i=0; while(p) { if(p->data%2==0) i++; p=p->next; } return i; } Status Findd_L0120(LinkList0120 L, Status i, ElemType *e) {//查找倒数第i个元素 LinkList0120 p, q; int j; p = L->next; q = L->next; for(j = 1; j < i; j++) { if(!q) return ERROR; q = q->next; } while(q->next) { p = p->next; q = q->next; } *e = p->data; return OK; } 六、系统实现 1、给出主程序的代码 2、实验环境 1.环境：宿舍。 2.硬件：2048M内存，500G硬盘。 3.系统：Windows 7 64位操作系统 4.软件平台：Microsoft Visual C++ 6.0简体中文版 七、相关文件列表如下 demo.cpp:主程序文件 LinkList.cpp:操作实现的算法 https://www.wendangku.net/doc/4416833621.html,p:操作DisplayData0120和compare0120的算法LinkList.h：函数声明 Mydef.h：存储结构的定义 八、程序的运行测试及结果 测试用例1：线性表的初始化 测试用例2：插入 图2—1 图2—2 图2—3 图2—4 测试用例3：显示表长 测试用例4：求数据 测试用例5：求位置 测试用例6：求前驱 测试用例7：求后继 测试用例8：删除 测试用例9：输出线性表 测试用例10：求奇数个数 测试用例11：求偶数个数 测试用例12：查找倒数第i个元素 测试用例13：重置为空 测试用例14：判断是否为空 测试用例15：销毁 九、本次实习总结 1．总结本次实习的收获 （1）通过本次实习，加强了对抽象数据类型List的认识及其不同的存储表示与相关操作的算法、编程实现； （2）了解了顺序存储和链式存储的区别； （3）加深并掌握了函数指针的用法。 2．本系统的不足之处 （1）系统的健壮行不够强； （2）代码不够优化。 3.遇到的困难 遇到初始化线性表后不知如何输入数据，后来观看了一下别人的编程发现他们是把插入调到前面去了，然后就用插入功能向线性表中输入数据 十、参考材料 严蔚敏等．数据结构(C语言版)．北京：清华大学出版社，2006 老师给的“抽象数据类型定义”的资料 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 第二次作业 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a．在P结点后插入S结点的语句序列是-----------。 b．在P结点前插入S结点的语句序列是-----------。 c．删除P结点的直接后继结点的语句序列是----------。 d．删除P结点的直接前驱结点的语句序列是----------。 e．删除P结点的语句序列是------------。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 4. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 四种基本的存储结构 Prepared on 22 November 2020 数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。 （4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3 实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include 数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 ???该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 ???由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 ???该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（LinkedStorageStructure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 ???该方法通常在储存结点信息的同时，还建立附加的索引表。 ???索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(SpareIndex)。索引项的一般形式是： ????????????????????(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法 ???该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构顺序表 第一种方法： #include 第二种方法： #include 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 实验报告 课程名称：数据结构与算法分析 实验名称：链表的实现与应用 实验日期：班级：数媒1401 姓名：范业嘉学号 08 一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 二、实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。 三、数据结构设计 1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表 2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。 四、算法设计 1.定义一个链表 void creatlist(Linklist &L,int n) { int i; Linklist p,s; L=(Linklist)malloc(sizeof(Lnode)); p=L; L->next=NULL; for(i=0;i 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G); 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #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(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用 存储单元的地址必须是连续的。 优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值， 另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 顺序表与链表的比较 基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的 存储密度= 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度= 1 链表的存储密度< 1 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 顺序表和链表的比较顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：┌───┬───────────────┬───────────────┐││ 顺序表│链表│├─┬─┼───────────────┼───────────────┤│基│分│静态分配。程序执行之前必须明确│动态分配只要内存空间尚有空闲，││于│配│规定存储规模。若线性表长度n变│就不会产生溢出。因此，当线性表││空│方│化较大，则存储规模难于预先确定│的长度变化较大，难以估计其存储││间│式│估计过大将造成空间浪费，估计太│规模时，以采用动态链表作为存储││考││小又将使空间溢出机会增多。│结构为好。 ││虑├─┼───────────────┼───────────────┤││存│为1。当线性表的长数据结构实验报告格式
顺序存储结构和链式存储结构
(完整版)数据结构实验报告全集
数据结构实验报告
四种基本的存储结构
数据结构实验报告完整
四种基本的存储结构
数据结构复习要点(整理版).docx
数据结构实验报告模板
数据结构C语言版 串的定长顺序存储表示和实现
数据结构实验报告图实验
数据结构顺序存储结构
数据结构实验报告及心得体会
线性表的链式存储结构实验报告
数据结构试题及答案
数据结构实验报告--图实验
数据结构实验报告
数据结构实验报告 - 答案汇总
比较顺序存储结构和链式存储结构 (1)