数据结构实验报告 实验一 线性表链式存储运算的算法实现

数据结构实验报告1线性表的顺序存储结构数据结构实验报告1线性表的顺序存储结构第一章引言线性表是计算机中最常见的数据结构之一，它是一种有序的数据元素集合，其中的数据元素之间具有一对一的关系。

线性表的存储结构有多种方式，其中顺序存储结构是最简单的一种，它使用一段连续的存储单元来存储线性表中的元素。

第二章顺序存储结构的定义顺序存储结构是将线性表中的元素按照其逻辑顺序依次存储在一块连续的存储空间中。

顺序存储结构的特点是可以快速地访问任意位置的元素，但插入和删除操作需要移动大量的元素。

第三章顺序存储结构的实现1.存储空间的分配顺序存储结构通常使用数组来实现，数组的长度应该大于等于线性表的长度，以防止溢出。

存储空间的分配可以使用静态分配或动态分配两种方式来实现。

2.线性表的初始化初始化线性表时，需要设置线性表的长度和当前元素的个数。

3.线性表的增删改查操作●插入操作：________在指定位置插入一个元素时，需要将插入位置之后的元素依次后移，给待插入的元素腾出位置。

●删除操作：________删除指定位置的元素时，需要将删除位置之后的元素依次前移，覆盖删除位置上的元素。

●修改操作：________修改指定位置的元素时，直接对该位置上的元素进行修改即可。

●查找操作：________根据指定的元素值，查找其在顺序存储结构中的位置。

4.线性表的遍历操作遍历操作可以按照顺序访问线性表中的每个元素，可以使用循环结构实现遍历操作。

第四章顺序存储结构的优缺点分析1.优点：________可以快速地访问任意位置的元素，节省存储空间。

2.缺点：________插入和删除操作需要移动大量的元素，不适用于频繁插入和删除的场景。

第五章实验过程和结果分析在本次实验中，我们以顺序存储结构为基础，实现了线性表的增删改查操作，并进行了遍历操作。

通过实验，我们发现顺序存储结构在查询操作上有较好的性能，但在插入和删除操作上的性能较差。

第六章附件本文档涉及的附件详见附件文件。

实验一线性表的链式存储【实验时间】【实验地点】【实验目的和要求】1．掌握线性表的结构特点和表示方法；2．掌握线性表链式存储结构特性和基本操作算法；3．掌握用指针实现单链表的建立、输出、插入和删除的算法。

【实验类型】验证性【实验时数】2学时【实验设备】计算机【参考资料】1．数据结构题解2．C程序设计【实验内容】熟练掌握线性表的链式表示和实现方法，利用其定义具体的链表结点；利用链表的结构特点，建立单链表；利用链表结点间的指针关系，实现链表的插入和删除。

[具体要求](1) 建立单链表时，要首先输入链表长度，根据输入值来确定所建链表的结点个数；(2) 在单链表中插入新结点时，要给出结点的插入位置和数据域的值；(3) 在单链表中删除某个结点时，要给出要删结点的位置；(4) 要编写单链表的输出函数，以便能验证程序的执行结果。

【实验分析】1、实验的第一步应该建立单链表结点类型和程序所需的宏或数据类型，例如：#define NULL 0 //宏定义NULL的值为0#define LEN sizeof(struct node) //宏定义LEN，为申请结点空间时做准备typedef struct{ int a;float b;} elemtype; //定义elemtype类型，这里同学们可以根据自己的情况来自行定义。

typedef struct node{elemtype data; //data域为elemtype类型的，它应该包含两个子域：a和bstruct node *next;}NODE , *NODEPTR; //定义了单链表结点类型和单链表结点指针类型2、对单链表的四种操作进行实现。

(1) NODEPTR creatlink() 建立单链表的函数很明显这个函数的返回值时结点指针类型的，所以这个函数应该返回的时建立的单链表的头指针。

同学们可以根据自己的构思，从前往后或从后往前建立单链表。

此外，提醒同学们最好建立带有附加头结点的单链表。

一、实验背景数据结构是计算机科学中一个重要的基础学科，它研究如何有效地组织和存储数据，并实现对数据的检索、插入、删除等操作。

为了更好地理解数据结构的概念和原理，我们进行了一次数据结构实训实验，通过实际操作来加深对数据结构的认识。

二、实验目的1. 掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、特点及操作方法。

2. 熟练运用数据结构解决实际问题，提高算法设计能力。

3. 培养团队合作精神，提高实验报告撰写能力。

三、实验内容本次实验主要包括以下内容：1. 线性表（1）实现线性表的顺序存储和链式存储。

（2）实现线性表的插入、删除、查找等操作。

2. 栈与队列（1）实现栈的顺序存储和链式存储。

（2）实现栈的入栈、出栈、判断栈空等操作。

（3）实现队列的顺序存储和链式存储。

（4）实现队列的入队、出队、判断队空等操作。

3. 树与图（1）实现二叉树的顺序存储和链式存储。

（2）实现二叉树的遍历、查找、插入、删除等操作。

（3）实现图的邻接矩阵和邻接表存储。

（4）实现图的深度优先遍历和广度优先遍历。

4. 算法设计与应用（1）实现冒泡排序、选择排序、插入排序等基本排序算法。

（2）实现二分查找算法。

（3）设计并实现一个简单的学生成绩管理系统。

四、实验步骤1. 熟悉实验要求，明确实验目的和内容。

2. 编写代码实现实验内容，对每个数据结构进行测试。

3. 对实验结果进行分析，总结实验过程中的问题和经验。

4. 撰写实验报告，包括实验目的、内容、步骤、结果分析等。

五、实验结果与分析1. 线性表（1）顺序存储的线性表实现简单，但插入和删除操作效率较低。

（2）链式存储的线性表插入和删除操作效率较高，但存储空间占用较大。

2. 栈与队列（1）栈和队列的顺序存储和链式存储实现简单，但顺序存储空间利用率较低。

（2）栈和队列的入栈、出队、判断空等操作实现简单，但需要考虑数据结构的边界条件。

3. 树与图（1）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

数据结构线性表实验报告数据结构线性表实验报告实验目的：本次实验主要是为了学习和掌握线性表的基本操作和实现方式。

通过实验，我们可以加深对线性表的理解，并能够熟悉线性表的基本操作。

实验设备与环境：本次实验所需的设备包括计算机和编程环境。

我们选择使用C语言来实现线性表的操作，并在Visual Studio Code编程软件中进行编写和调试。

实验内容：1.线性表的定义和基本操作1.1 线性表的定义：线性表是一种有序的数据结构，其中的元素按照一定的顺序存储，可以插入、删除和访问元素。

1.2 线性表的基本操作：1.2.1 初始化线性表：创建一个空的线性表。

1.2.2 判断线性表是否为空：判断线性表是否不含有任何元素。

1.2.3 获取线性表的长度：返回线性表中元素的个数。

1.2.4 在线性表的指定位置插入元素：在线性表的第i个位置插入元素x，原第i个及其之后的元素依次后移。

1.2.5 删除线性表中指定位置的元素：删除线性表中第i个位置的元素，原第i+1个及其之后的元素依次前移。

1.2.6 获取线性表中指定位置的元素：返回线性表中第i个位置的元素的值。

1.2.7 清空线性表：将线性表中的元素全部删除，使其变为空表。

2.线性表的顺序存储结构实现2.1 线性表的顺序存储结构：使用数组来实现线性表的存储方式。

2.2 线性表的顺序存储结构的基本操作：2.2.1 初始化线性表：创建一个指定长度的数组，并将数组中的每个元素初始化为空值。

2.2.2 判断线性表是否为空：判断线性表的长度是否为0。

2.2.3 获取线性表的长度：返回线性表数组的长度。

2.2.4 在线性表的指定位置插入元素：将要插入的元素放入指定位置，并将原位置及其之后的元素依次后移。

2.2.5 删除线性表中指定位置的元素：将指定位置的元素删除，并将原位置之后的元素依次前移。

2.2.6 获取线性表中指定位置的元素：返回指定位置的元素的值。

2.2.7 清空线性表：将线性表数组中的每个元素赋空值。

数据结构实验报告课程数据结构 _ 院系专业班级实验地点姓名学号实验时间指导老师数据结构上机实验报告1一﹑实验名称：实验一——链表二﹑实验目的：1.了解线性表的逻辑结构特性；2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法；3.掌握链表的基本操作（建表、插入、删除等）4. 掌握循环链表的概念，加深对链表的本质的理解。

5.掌握运用上机调试链表的基本方法三﹑实验内容：（1）创建一个链表（2）在链表中插入元素（3）在链表中删除一个元素（4）销毁链表四﹑实验步骤与程序#include <iostream.h>#include <malloc.h>typedef struct LNode{int data;struct LNode *next;}Lnode, *LinkList;//假设下面的链表均为带头结点。

void CreatLinkList(LinkList &L,int j){//建立一个链表L,数据为整数，数据由键盘随机输入。

LinkList p,q;L=(LinkList )malloc(sizeof(Lnode));L->next=NULL;q=L;cout<<"请输入一个链表："<<endl;for(int i=0;i<j;i++){ p=(LinkList)malloc(sizeof(Lnode));cin>>p->data;p->next=q->next;q->next=p;q=p;}}int PrintLinkList(LinkList &L){//输出链表L的数据元素LinkList p;p=L->next;if(L->next==NULL){cout<<"链表没有元素!"<<endl;return 0;}cout<<"链表的数据元素为:";while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;return 1;}void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。

电子科技大学实验报告课程名称：数据结构与算法学生姓名：学号：点名序号：指导教师：实验地点：基础实验大楼实验时间：4月3日2014-2015-2学期信息与软件工程学院实验报告(一)学生姓名：学号：指导教师：实验地点：基础实验大楼实验时间：4月3日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—线性表的实现三、实验学时：4四、实验原理：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式即可以用于表示线性结构，也可用于表示非线性结构。

一般来说，在线性表的链式存储结构中，各数据结点的存储符号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。

对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。

线性表的链接存储中，为了方便在表头插入和删除结点的操作，经常在表头结点（存储第一个元素的结点）的前面增加一个结点，称之为头结点或表头附加结点。

这样原来的表头指针由指向第一个元素的结点改为指向头结点，头结点的数据域为空，头结点的指针域指向第一个元素的结点。

五、实验目的：本实验通过定义单向链表的数据结构，设计创建链表、插入结点、遍历结点等基本算法，使学生掌握线性链表的基本特征和算法，并能熟练编写C 程序，培养理论联系实际和自主学习的能力，提高程序设计水平。

六、实验内容：使用数据结构typedef struct node {Elemtype data；struct node *next；} ListNode, *ListPtr；typedef struct stuInfo {char stuName[10]; /*学生姓名*/int Age /*年龄*/} ElemType实现带头结点的单向链表的创建、删除链表、插入结点等操作，并能实现年龄递增的两个单向链表合并一个链表，合并后的链表按年龄递减，可认为同名同年龄是同一个学生，每个学生在合并后的链表中仅出现一次。

数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。

⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。

要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。

2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。

要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。

如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。

（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。

（3）当给定x的值时，能计算表达式相加或相减的结果。

（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。

（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。

实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。

2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。

（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。

因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。

综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。

3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。

二.实验目的：1.掌握线性表链式存储结构的C语言描述及运算算法的实现；2.分析算法的空间复杂度和插入和删除的时间复杂度；3.总结比较线性表顺序存储存储与链式存储的各自特点。

三.主要程序代码分析：LinkList creatListR1() //用尾插入法建立带头结点的单链表{char *ch=new char();LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*headListNode *s,*r,*pp;r=head; //尾指针初值指向头结点r->next=NULL;scanf("%s",ch); //读入第一个结点的值while(strcmp(ch,"#")!=0) { //输入#结束pp=LocateNode(head,ch);- strcpy(s->data,ch);r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL;}scanf("%s",ch); //读入下一个结点的值}return head; //返回表头指针}int Insert(ListNode *head) //链表的插入{ListNode *in,*p,*q;int wh;in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL;q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL;scanf("%s",in->data); //输入插入的数据scanf("%d",&wh); //输入插入数据的位置for(p=head;wh>0;p=p->next,wh--);q=p->next;p->next=in;in->next=q;}void DeleteList(LinkList head,char *key) //链表的删除{ListNode *p,*r,*q=head;p=LocateNode(head,key); //按key值查找结点的if(p==NULL)exit(0); //若没有找到结点，退出while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next;r=q->next;q->next=r->next;free(r); //释放结点*r}四.程序运行结果：-五.实验总结：通过线性表链式存储运算的算法实现的上机实验，我了解了链式的基本原理和方法，能编程对数据进行链式存储。