实验1顺序表和链表基本操作(给学生)

数据结构与算法分析实验报告一、实验目的本次实验旨在通过实际操作和分析，深入理解数据结构和算法的基本概念、原理和应用，提高解决实际问题的能力，培养逻辑思维和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

操作系统为 Windows 10。

三、实验内容（一）线性表的实现与操作1、顺序表的实现使用数组实现顺序表，包括插入、删除、查找等基本操作。

通过实验，理解了顺序表在内存中的存储方式以及其操作的时间复杂度。

2、链表的实现实现了单向链表和双向链表，对链表的节点插入、删除和遍历进行了实践。

体会到链表在动态内存管理和灵活操作方面的优势。

（二）栈和队列的应用1、栈的实现与应用用数组和链表分别实现栈，并通过表达式求值的例子，展示了栈在计算中的作用。

2、队列的实现与应用实现了顺序队列和循环队列，通过模拟银行排队的场景，理解了队列的先进先出特性。

（三）树和二叉树1、二叉树的遍历实现了先序、中序和后序遍历算法，并对不同遍历方式的结果进行了分析和比较。

2、二叉搜索树的操作构建了二叉搜索树，实现了插入、删除和查找操作，了解了其在数据快速查找和排序中的应用。

（四）图的表示与遍历1、邻接矩阵和邻接表表示图分别用邻接矩阵和邻接表来表示图，并比较了它们在存储空间和操作效率上的差异。

2、图的深度优先遍历和广度优先遍历实现了两种遍历算法，并通过对实际图结构的遍历，理解了它们的应用场景和特点。

（五）排序算法的性能比较1、常见排序算法的实现实现了冒泡排序、插入排序、选择排序、快速排序和归并排序等常见的排序算法。

2、算法性能分析通过对不同规模的数据进行排序实验，比较了各种排序算法的时间复杂度和空间复杂度。

四、实验过程及结果（一）线性表1、顺序表在顺序表的插入操作中，如果在表头插入元素，需要将后面的元素依次向后移动一位，时间复杂度为 O(n)。

删除操作同理，在表头删除元素时，时间复杂度也为 O(n)。

实验报告课程名称数据结构实验项目实验一线性表的生成与操作题目一顺序表和链表的创建与基本操作系别___ _计算机学院 _ ______专业__ __计算机大类_ __班级/学号__(1406/2014011288)_____学生姓名 _______(孙文学)_________实验日期_（2015年10月19日）成绩_______________________指导教师黄改娟实验题目：实验一线性表的生成与操作------顺序表和链表的创建与基本操作（自己所选择实验题目，必填）一、实验目的1)掌握线性表的顺序存储和链式存储结构；2)验证顺序表及链表的基本操作的实现；(验证)3)理解算法与程序的关系，能够将算法转换为对应程序；4)体会线性表在实际应用中能够解决的问题。

（设计、综合）二、实验内容1)根据实验一题目列表，选定题目，说明题目的主要需求；2)结合所选定的题目，定义存储结构，并完成对应应用的线性表创建、插入、删除、查找等基本操作的算法描述；3)程序编码实现，并获得运行结果。

三、报告内容1)实验题目及主要存储结构定义（提示：请根据所选定题目，描述存储结构）题目：顺序表和链表的创建及基本操作顺序表我是采用数组存储的，链表是采用结构体存储的2)结合题目，说明对相应线性表的基本操作算法描述（提示：可用自然语言、流程图、伪代码等均可，要求对每一个操作，都给出具体的算法描述）基本操作：#顺序表#（1）插入：在线性表中的x位置插入y----将x位置及之后的元素都往后挪一位，将y的值赋给a[x].（2）删除：删除位置为x的元素----另y=a[x],然后x之后的元素都往前挪一位。

（3）查找：寻找值为y的元素----从a[0]开始，若a[i]==y，则返回i，否则i++。

#链表#（1）插入：当i小于要插入的位置x时，i++，插入p->data------p->next=s->next;s->next=p;（2）删除：当p->data不等于要删除的值x时，p=p->next；q=p->next;p->next=q->next;free(q);（3）查找：当p->data!=x时，p=p->next，找到之后返回p->data3)程序源码（提示：列出所编写程序的代码。

实验1 顺序表基本操作【实验目的】<1>熟悉C语言的上机环境，掌握C语言的基本结构<2>会定义线性表的顺序存储结构<3>熟悉对顺序表的一些基本操作<4>熟悉与线性表相关的函数的定义和使用【实验内容】[实验任务一]顺序表的基本操作1.顺序表的插入操作【操作步骤】<1>启动辅助教学软件<2>选择“C语言”<3>选择“顺序表”<4>选择“顺序表插入”<5>输入建立表的数据<6>输入插入数据元素<7>输入插入位置<8>选择单步执行2.顺序表的删除操作【操作步骤】<1>启动辅助教学软件<2>选择“C语言”<3>选择“顺序表”<4>选择“顺序表插入”<5>输入建立表的数据<6>输入删除位置<7>选择单步执行[实验任务二]编写C语言程序1. 编程实现顺序表的插入操作。

2.编程实现顺序表的删除操作。

实验2 链表的基本操作【实验目的】<1>学会定义单链表的结点类型<2>熟悉单链表的一些基本操作，依据这些操作函数定义<3>掌握线性表的链式存储结构的特点<4>掌握循环链表和双向链表的定义、构造方法等。

【实验内容】[实验任务一]验证单链表的基本操作<1>单链表的插入操作<2>单链表的删除操作[实验任务二]编写C语言程序<1>用C语言实现构造单链表<2>用C语言实现输出单链表实验3 二叉树的基本操作【实验目的】<1>熟悉二叉树的结点结构<2>熟悉二叉树的基本操作<3>学会利用递归方法编写二叉树的遍历算法【实验内容】[实验任务一]二叉树的遍历<1>先序遍历<2>中序遍历<3>后续遍历[实验任务二]编写算法<1>根据二叉树的任一遍历算法，编写求二叉树中结点个数的算法。

软件技术基础实验一顺序表及单链表的使用班级：学号：姓名：日期：一、实验目的1.熟悉线性表的定义，理解顺序表基本操作。

2.会使用顺序表的基本操作求解一些简单问题。

3.掌握单链表的基本概念，理解单链表基本操作的实现。

4.会使用单链表的基本操作求解一些简单问题。

二、实验要求1.根据布置的作业编写源程序，上机验证实验结果；2.独立做实验，输入、调试所编程序；3.实验结束后，根据实验报告模板编写实验报告。

三、实验内容和步骤（1）创建一个（名为你的学号+a）工程，将所给的三个文件2.h 2.cpp 1加入到工程中，编写程序完成下列功能：1、理解1.h文件中sq_LList类的定义以及类成员函数的实现，删除main函数中的所有内容，在main函数中编写程序实现：（1）从键盘上输入5个整数，创建顺序表s1，并输出顺序表中的内容。

（2）从键盘上输入两个整数（元素的值和插入位置），插入到顺序表中，输出插入后的顺序表内容。

（3）从键盘上输入一个整数（删除元素的位置），判断在顺序表中是否存在，若存在，删除之，并输出删除后的顺序表内容。

源程序：void main(){}运行结果：2、编写程序实现顺序表逆置算法。

提示：（1）在1.h添加成员函数void Reverse()及此成员函数的定义。

（2）在main函数调用并实现将顺序表s1逆置头文件中成员函数定义：void sq_LList<T>::Reverse(){}void main(){//添加内容}运行结果：（2）创建一个（名为你的学号+b）工程，将所给的三个文件1.h 1.cpp 1加入到工程中，编写程序完成下列功能：1、理解1.h文件中linked_List类的定义及类成员函数的实现，删除main函数中的所有内容，在main函数中编写程序实现：（1）从键盘上输入5个整数，创建单链表s1，并输出单链表中的内容。

（2）从键盘上输入一个整数（删除位置），删除指定位置的元素，输出删除后的单链表内容。

数据结构实验报告一、实验目的数据结构是计算机科学中重要的基础课程，通过本次实验，旨在深入理解和掌握常见数据结构的基本概念、操作方法以及在实际问题中的应用。

具体目的包括：1、熟练掌握线性表（如顺序表、链表）的基本操作，如插入、删除、查找等。

2、理解栈和队列的特性，并能够实现其基本操作。

3、掌握树（二叉树、二叉搜索树）的遍历算法和基本操作。

4、学会使用图的数据结构，并实现图的遍历和相关算法。

二、实验环境本次实验使用的编程环境为具体编程环境名称，编程语言为具体编程语言名称。

三、实验内容及步骤（一）线性表的实现与操作1、顺序表的实现定义顺序表的数据结构，包括数组和表的长度等。

实现顺序表的初始化、插入、删除和查找操作。

2、链表的实现定义链表的节点结构，包含数据域和指针域。

实现链表的创建、插入、删除和查找操作。

（二）栈和队列的实现1、栈的实现使用数组或链表实现栈的数据结构。

实现栈的入栈、出栈和栈顶元素获取操作。

2、队列的实现采用循环队列的方式实现队列的数据结构。

完成队列的入队、出队和队头队尾元素获取操作。

（三）树的实现与遍历1、二叉树的创建以递归或迭代的方式创建二叉树。

2、二叉树的遍历实现前序遍历、中序遍历和后序遍历算法。

3、二叉搜索树的操作实现二叉搜索树的插入、删除和查找操作。

（四）图的实现与遍历1、图的表示使用邻接矩阵或邻接表来表示图的数据结构。

2、图的遍历实现深度优先遍历和广度优先遍历算法。

四、实验结果与分析（一）线性表1、顺序表插入操作在表尾进行时效率较高，在表头或中间位置插入时需要移动大量元素，时间复杂度较高。

删除操作同理，在表尾删除效率高，在表头或中间删除需要移动元素。

2、链表插入和删除操作只需修改指针，时间复杂度较低，但查找操作需要遍历链表，效率相对较低。

（二）栈和队列1、栈栈的特点是先进后出，适用于函数调用、表达式求值等场景。

入栈和出栈操作的时间复杂度均为 O(1)。

2、队列队列的特点是先进先出，常用于排队、任务调度等场景。

实验一顺序表与链表
姓名：学号：实验日期：
教师评语：
一、实验目的
1、掌握线性表中元素的前驱、后继的概念。

2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。

3、对线性表相应算法的时间复杂度进行分析。

4、理解顺序表、链表数据结构的特点（优缺点）。

二、实验内容和要求
1、试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,a n）逆置为(a n,a n-1,…,a1)。

2、假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各个不相同），现要求另开辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。

试用单链表编写求C的算法。

3、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

已知s 为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

三、实验小结
1。

顺序表,链表实验报告.总结实验报告实验目的：学生管理系统（顺序表）实验要求：1.建表2.求表长3.插入4.查找5.删除6.列表7.退出源程序：#include#include#include#define MaxSize 1000typedef struct{char xh[40];char xm[40];int cj;}DataType; //学生的结构typedef struct {DataType data[MaxSize]; //定义表的数据类型int length; //数据元素分别放置在data[0]到data[length-1]当中} SqList; //表的结构void liebiao(SqList *L) //建立表格{int k,n;char q;printf("请输入,输入学生的个数：\n");fflush(stdin);scanf("%d",&n);for(k=0;k<=n-1;k++){printf("请输入学生学号\n");scanf("%s",L->data[k].xh);printf("请输入学生名字\n");scanf("%s",L->data[k].xm);printf("请输入学生成绩\n");scanf("%d",&L->data[k].cj);}L->length=n;}void qb(SqList *L) //全部输出{int k,w;for(k=0;klength;k++){w=k+1;printf("第%d位学生：",w);printf("%s %s %d\n",L->data[k].xh,L->data[k].xm,L->da ta[k].cj);}}int cr(SqList *L,DataType *xs,int i) //插入信息{int j;if(L->length==MaxSize){printf("没有!");return 0;}else if((i<0)||(i>L->length)){printf("程序溢出，不符合");return 0;}else{for(j=L->length-1;j>=i;j--){strcpy(L->data[j+1].xh,L->data[j].xh); strcpy(L->data[j+1].xm,L->data[j].xm); L->data[j+1].cj=L->data[j].cj;}strcpy(L->data[i].xh,xs->xh);strcpy(L->data[i].xm,xs->xm);L->data[i].cj=xs->cj;L->length=L->length+1;}return 0;}int cz(SqList *L) //查找信息{char xh[40];char xm[40];int cj;int i=0,u;printf(" 1、按学号查询 \n");printf(" 1、按姓名查询 \n");printf(" 1、按成绩查询 \n");printf("请选择：");fflush(stdin);scanf("%d",&u);if (u==1){printf("请输入要查找学生的学号："); scanf("%s",xh);for(i=0;ilength;i++){if(strcmp(L->data[i].xh,xh)==0) return i;}}if (u==2){printf("请输入要查找学生的姓名："); scanf("%s",xm);for(i=0;ilength;i++){if(strcmp(L->data[i].xm,xm)==0) return i;}}if (u==3){printf("请输入要查找学生的成绩："); scanf("%s",cj);for(i=0;ilength;i++){if(L->data[i].cj,&cj)return i;}}return -1;//*如果没找到，返回-1}int cz2(SqList *L) //删除查找的函数{char xh[40];char xm[40];int i=0,h;printf(" 1、按学号删除 \n");printf(" 2、按姓名删除 \n");printf("请选择：");fflush(stdin);scanf("%d",&h);if (h==1){printf("请输入要删除学生的学号：");scanf("%s",xh);for(i=0;ilength;i++){if(strcmp(L->data[i].xh,xh)==0) //判断输入和已知学号一样不return i;}}else if (h==2){printf("请输入要删除学生的姓名：");scanf("%s",xm);for(i=0;ilength;i++){if(strcmp(L->data[i].xm,xm)==0) //判断输入姓名和已知姓名一样不return i;}}return -1;}void sc(SqList *L) //删除函数{int i,j;printf("请先选择您要删除的学生信息的方式：\n");scanf("%d",&j);i=cz2(L);if(i==-1){printf("没有查到要删除的学生信息");return;}for(j=i;jlength;j++) // 要删除学生以后的学生整体上调一位{L->data[j].cj=L->data[j+1].cj; //就是后一个覆盖了前一个strcpy(L->data[j].xh,L->data[j+1].xh);strcpy(L->data[j].xm,L->data[j+1].xm);}L->length--;printf("该学生信息已被删除！\n");}int bc(SqList *L){return (L->length);}int main() //主体大函数{int i,k;SqList *L; //定义顺序表的指针DataType *xs;L=(SqList *)malloc(sizeof(SqList)*MaxSize); char q;ee:rewind(stdin);{printf(" 学生管理系统 \n"); //函数的各个结构printf(" \n");printf(" \n");printf(" \n");printf(" 建立表格请输入1 \n");printf(" 求表长请输入2 \n");printf(" 插入请输入3 \n");printf(" 查找请输入4 \n");printf(" 删除请输入5 \n");printf(" 列表请输入6 \n");printf(" 退出请按0 \n");printf(" 请输入");scanf("%c",&q);}if(q=='1'){rewind(stdin);liebiao(L);goto ee;}if(q=='2'){rewind(stdin);bc(L);printf("共%d个学生\n",L->length);goto ee;}if(q=='3'){rewind(stdin);printf(" 插入 \n");printf("\t\t 请输入要添加的学生信息: \n"); xs=(DataType *)malloc(sizeof(DataType)); printf("请输入学生学号\n");scanf("%s",xs->xh);printf("请输入学生名字\n");scanf("%s",xs->xm);printf("请输入学生成绩\n");scanf("%d",&xs->cj);printf("请输入要插入的位置：\n"); rewind(stdin);scanf("%d",&i);cr(L,xs,i);goto ee;}if(q=='4'){rewind(stdin);printf(" 查找 \n");printf(" 查询学生信息 \n");i=cz(L);if(i!=-1){printf("%s %s %d\n",L->data[i].xh,L->data[i].x m,L->data[i].cj);}else{printf("信息不存");}goto ee;}if(q=='5'){rewind(stdin);printf(" 删除 \n"); printf(" 删除学生信息 \n");sc(L);goto ee;}if(q=='6'){rewind(stdin);printf(" 列表 \n");qb(L);goto ee;}if(q=='0') {printf("谢谢使用\n");}if(!(q=='1'||q=='2'||q=='3'||q=='4'||q=='5'||q=='5'||q=='0 ')) {goto ee;}system ("pause"); return 0;}主程序：输入1--6n=1 n=2n=3n=4n=5n=6退出建表求表长插入查找删除列表建表：是否输入学生个数n ，变量k k=0; k<=n-1;输入学号，姓名，成绩k=k+1 结束输入查找学号n，变量k k=0n=k是否k=k+1输出是否是否输入插入位置n 表长L 变量kn<=Lk=0n=kk=k+1strcpy(L->data[j+1].xh,L->data[j].xh);strcpy(L->data[j+1].xm,L->data[j].xm);L->data[j+1].cj=L->data[j].cj输入错误结束是否否是输入删除的位置n 变量k 表长Ln<=Lk=0n=k k=k+1strcpy(L->data[j].xh,L->data[j-1].xh);strcpy(L->data[j].xm,L->data[j-1].xm); L->data[j].cj=L->data[j-1].cj输入错误结束。

实验一、二：线性表的应用班级学号姓名一、实验预备知识1 复习C++中编写函数的相关内容。

2 复习如何用主函数将多个函数连在一起构成一个C++完整程序。

二、实验目的1 掌握线性表的顺序和链式存储结构2 熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算3 熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算三、实验要求1 编写初始化并创建线性表和输出线性表的算法。

2 编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。

3 编写一个主函数，将上面函数连在一起，构成一个完整的程序。

4将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。

四、实验步骤顺序表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．初始化并建立顺序表。

3．编写顺序表输出算法。

（内存中开辟的单元数为8）4．依次插入3，21，15三个数，分别插入在第4，6和2位置，每插入一次都要输出一次顺序表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次顺序表。

单链表实验内容：1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．建立一个带表头结点的单链表（前插入法和尾插入法都可以）。

3．编写单链表输出算法。

4．依次插入3，21，15三个数，分别插入在第4，6和12位置，每插入一次都要输出一次单链表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次单链表。

五、实验结果1．给出程序清单及输入/输出结果。

2．实验过程中遇到的问题、解决方法及心得体会。

顺序表的基本操作和实现实验报告顺序表的基本操作和实现实验报告引言顺序表是一种常用的数据结构，它能够在连续的存储空间中存储元素，并通过索引来访问和修改这些元素。

本实验旨在通过实现基本操作，包括插入、删除、获取等，来深入理解顺序表的原理和实现方式。

实验目的1.掌握顺序表的基本操作2.理解顺序表的实现原理3.学习使用编程语言实现顺序表实验过程1.创建顺序表–使用数组作为底层存储结构，设置一个指针指向数组的起始位置，并初始化顺序表的长度为0。

2.插入元素–通过移动元素的方式，在指定位置插入一个新元素。

–更新顺序表的长度。

3.删除元素–通过覆盖元素的方式，删除指定位置的元素。

–更新顺序表的长度。

4.获取元素–根据指定位置，返回对应的元素。

5.更新元素–根据指定位置，修改对应的元素的值。

–不改变顺序表的长度。

6.打印顺序表–遍历顺序表中的元素，并输出到控制台。

实验结果根据以上操作，我们成功实现了一个顺序表，并在各基本操作上进行了测试和验证。

实验结果表明，顺序表能够高效地支持元素的插入、删除、获取和更新等操作，并能够正确地保存和展示数据。

实验总结通过本次实验，我们深入学习了顺序表的基本操作和实现方式。

顺序表作为一种简单而有用的数据结构，在实际应用中有着广泛的应用。

同时，我们也体会到了数据结构与算法的设计和实现的重要性，它们对于程序性能和可读性都有着关键的影响。

参考文献1.《数据结构与算法分析》2.《算法导论》3.《C++ Primer》实验环境•编程语言: C++•开发环境: Visual Studio Code•操作系统: Windows 10实验步骤1.创建顺序表的类SeqList，并定义私有属性int* data和intlength。

2.定义构造函数SeqList(int size)，用于初始化顺序表的大小。

3.实现插入元素的方法void insert(int pos, int value)，根据指定位置和值，在顺序表中插入新元素。

元素之后的所有数据都前移一个位置，最将线性表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素则可以采用顺序查找的方法，从表中第 1 个数据元素开始依次将值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0 值。

线性表的动态分配顺序存储结构—C语言实现#define MaxSize 50//存储空间的分配量Typedef char ElemType；Typedef struct{ElemType data[MaxSize];int length; //表长度（表中有多少个元素）}SqList;动态创建一个空顺序表的算法：void InitList(SqList *&L) //初始化线性表{L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L->length=0; //置空线性表长度为0}线性表的插入：status Sqlist_insert(Sqlist &L,int i,Elemtype x)/*在顺序表L中第i个元素前插入新元素x*/{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/if (L.length>=MAXLEN)return OVERFLOW;/*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j]; /*将第i个元素及后续元素位置向后移一位*/L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/L.length++; /*顺序表L的长度加1*/return OK;}线性表的删除：status Sqlist_delete(Sqlist &L,int i,Elemtype &e)/*在顺序表L中删除第i个元素*{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/L.length--;/*顺序表L的长度减1*/return OK；}线性表元素的查找：int LocateElem(SqList *L, ElemType e) //按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++; //查找元素eif (i>=L->length) //未找到时返回0return 0;elsereturn i+1; //找到后返回其逻辑序号}输出线性表：void DispList(SqList *L) //输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}输出线性表第i个元素的值：bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false; //参数错误时返回falsee=L->data[i-1]; //取元素值return true; //成功找到元素时返回true}代码：#include <stdio.h>#include <malloc.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int length;} SqList;void InitList(SqList *&L);void DestroyList(SqList *L);bool ListEmpty(SqList *L);int ListLength(SqList *L);void DispList(SqList *L);bool GetElem(SqList *L,int i,ElemType &e);int LocateElem(SqList *L, ElemType e);bool ListInsert(SqList *&L,int i,ElemType e);bool ListDelete(SqList *&L,int i,ElemType &e);void InitList(SqList *&L)//初始化线性表{L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间L->length=0;//置空线性表长度为0 }void DestroyList(SqList *L)//销毁线性表{free(L);}bool ListEmpty(SqList *L)//判线性表是否为空表{return(L->length==0);}int ListLength(SqList *L)//求线性表的长度{return(L->length);}void DispList(SqList *L)//输出线性表{int i;if (ListEmpty(L)) return;for (i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}bool GetElem(SqList *L,int i,ElemType &e)//求线性表中某个数据元素值{if (i<1 || i>L->length)return false;//参数错误时返回falsee=L->data[i-1];//取元素值return true;//成功找到元素时返回true}int LocateElem(SqList *L, ElemType e)//按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++;//查找元素eif (i>=L->length)//未找到时返回0return 0;elsereturn i+1;//找到后返回其逻辑序号}bool ListInsert(SqList *&L,int i,ElemType e)//插入数据元素{int j;if (i<1 || i>L->length+1)return false;//参数错误时返回falsei--;//将顺序表逻辑序号转化为物理序号for (j=L->length;j>i;j--)//将data[i]及后面元素后移一个位置L->data[j]=L->data[j-1];L->data[i]=e;//插入元素eL->length++;//顺序表长度增1return true;//成功插入返回true}bool ListDelete(SqList *&L,int i,ElemType &e)//删除数据元素{int j;if (i<1 || i>L->length)//参数错误时返回falsereturn false;i--;//将顺序表逻辑序号转化为物理序号e=L->data[i];for (j=i;j<L->length-1;j++)//将data[i]之后的元素前移一个位置L->data[j]=L->data[j+1];L->length--;//顺序表长度减1return true;//成功删除返回true}void main(){SqList *L;ElemType e;printf("顺序表的基本运算如下:\n");printf(" (1)初始化顺序表L\n");InitList(L);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf(" (3)输出顺序表L:");DispList(L);printf(" (4)顺序表L长度=%d\n",ListLength(L));printf(" (5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));GetElem(L,3,e);printf(" (6)顺序表L的第3个元素=%c\n",e);实验结果：心得体会：通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。

链表的基本操作实验报告链表的基本操作实验报告引言：链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表相较于数组拥有更灵活的操作，能够动态地增删节点。

本实验旨在通过实际操作链表，加深对链表基本操作的理解和掌握。

实验目的：1. 理解链表的基本概念和结构；2. 学会链表的插入、删除和遍历操作；3. 掌握链表的相关算法。

实验过程：1. 创建链表首先，我们需要创建一个链表。

链表可以是单链表、双链表或循环链表，本次实验我们选择创建一个单链表。

创建链表的过程如下：（1）定义一个链表的节点结构，包含数据和指向下一个节点的指针；（2）创建头节点，并将头节点的指针指向NULL，表示链表为空。

2. 插入节点链表的插入操作可以在链表的任意位置插入节点。

我们可以选择在链表的头部、尾部或指定位置插入节点。

下面以在链表头部插入节点为例，介绍插入节点的过程：（1）创建一个新节点，设置新节点的数据；（2）将新节点的指针指向原头节点；（3）将头节点的指针指向新节点，完成插入操作。

3. 删除节点链表的删除操作可以删除链表中的任意节点。

同样，我们可以选择删除链表的头部、尾部或指定位置的节点。

以下是删除链表头部节点的步骤：（1）将头节点的指针指向下一个节点，跳过原头节点；（2）释放原头节点的内存空间。

4. 遍历链表链表的遍历操作用于访问链表中的每个节点。

通过遍历链表，我们可以获取链表中的所有数据或执行特定的操作。

链表的遍历操作如下：（1）从链表的头节点开始，依次访问每个节点；（2）对每个节点执行相应的操作，如打印节点的数据。

实验结果：通过以上实验过程，我们成功地创建了一个链表，并实现了链表的插入、删除和遍历操作。

链表的基本操作能够灵活地处理数据，适用于各种场景。

链表的插入和删除操作可以在O(1)时间内完成，相较于数组的插入和删除操作具有更高的效率。

实验总结：链表作为一种常见的数据结构，具有灵活性和高效性的特点。

顺序表的基本操作实验报告顺序表的基本操作实验报告引言：顺序表是一种常见的数据结构，它以连续的存储空间来存储数据元素，具有随机访问的特点。

在本次实验中，我们将通过实践来学习顺序表的基本操作，包括插入、删除、查找等，以加深对顺序表的理解和运用。

实验目的：1. 掌握顺序表的插入操作；2. 掌握顺序表的删除操作；3. 掌握顺序表的查找操作；4. 熟悉顺序表的基本操作的时间复杂度。

实验材料和方法：1. 实验材料：计算机、编程环境；2. 实验方法：使用编程语言实现顺序表的基本操作，并进行测试。

实验过程：1. 插入操作：在顺序表中插入一个元素，需要将插入位置之后的元素依次后移，并将新元素插入到指定位置。

实现代码如下：```pythondef insert_element(seq_list, index, value):seq_list.append(None) # 在顺序表末尾添加一个空位for i in range(len(seq_list)-1, index, -1):seq_list[i] = seq_list[i-1]seq_list[index] = value```通过测试，我们可以验证插入操作的正确性和时间复杂度。

2. 删除操作：顺序表的删除操作需要将删除位置之后的元素依次前移，并将最后一个元素删除。

实现代码如下：```pythondef delete_element(seq_list, index):for i in range(index, len(seq_list)-1):seq_list[i] = seq_list[i+1]seq_list.pop()```通过测试，我们可以验证删除操作的正确性和时间复杂度。

3. 查找操作：顺序表的查找操作可以通过遍历整个顺序表来实现，也可以利用有序性进行优化。

实现代码如下：```pythondef search_element(seq_list, value):for i in range(len(seq_list)):if seq_list[i] == value:return ireturn -1```通过测试，我们可以验证查找操作的正确性和时间复杂度。

数据结构实验报告-实验⼀顺序表、单链表基本操作的实现实验⼀顺序表、单链表基本操作的实现l 实验⽬的1、顺序表（1）掌握线性表的基本运算。

（2）掌握顺序存储的概念，学会对顺序存储数据结构进⾏操作。

（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容1、顺序表1、编写线性表基本操作函数：（1）InitList(LIST *L,int ms)初始化线性表；（2）InsertList(LIST *L,int item,int rc)向线性表的指定位置插⼊元素；（3）DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；（4）DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；（5）FindList(LIST *L,int item)查找线性表的元素；（6）OutputList(LIST *L)输出线性表元素；2、调⽤上述函数实现下列操作：（1）初始化线性表；（2）调⽤插⼊函数建⽴⼀个线性表；（3）在线性表中寻找指定的元素；（4）在线性表中删除指定值的元素；（5）在线性表中删除指定位置的元素；（6）遍历并输出线性表；l 实验结果1、顺序表（1）流程图（2）程序运⾏主要结果截图（3）程序源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct LinearList/*定义线性表结构*/{int *list; /*存线性表元素*/int size; /*存线性表长度*/int Maxsize; /*存list数组元素的个数*/};typedef struct LinearList LIST;void InitList(LIST *L,int ms)/*初始化线性表*/{if((L->list=(int*)malloc(ms*sizeof(int)))==NULL){printf("内存申请错误");exit(1);}L->size=0;L->Maxsize=ms;}int InsertList(LIST *L,int item,int rc)/*item记录值；rc插⼊位置*/ {int i;if(L->size==L->Maxsize)/*线性表已满*/return -1;if(rc<0)rc=0;if(rc>L->size)rc=L->size;for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/L->list[i+=1]=L->list[i];L->list[rc]=item;L->size++;return0;}void OutputList(LIST *L)/*输出线性表元素*/{int i;printf("%d",L->list[i]);printf("\n");}int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/ {int i;for(i=0;i<L->size;i++)if(item==L->list[i])return i;return -1;}int DeleteList1(LIST *L,int item)/*删除指定元素值得线性表记录，返回值为>=0为删除成功*/ {int i,n;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(n=i;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return i;}return -1;}int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{int i,n;if(rc<0||rc>=L->size)return -1;for(n=rc;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return0;}int main(){LIST LL;int i,r;printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.size,LL.Maxsize);printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.list,LL.Maxsize);while(1){printf("请输⼊元素值，输⼊0结束插⼊操作:");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d",&i);if(i==0)break;printf("请输⼊插⼊位置：");scanf("%d",&r);InsertList(&LL,i,r-1);printf("线性表为：");OutputList(&LL);}while(1){printf("请输⼊查找元素值，输⼊0结束查找操作：");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d ",&i);if(i==0)break;r=FindList(&LL,i);if(r<0)printf("没有找到\n");elseprintf("有符合条件的元素，位置为：%d\n",r+1);}while(1){printf("请输⼊删除元素值，输⼊0结束查找操作：");fflush(stdin);/*清楚标准缓存区*/scanf("%d",&i);if(i==0)break;r=DeleteList1(&LL,i);if(i<0)printf("没有找到\n");else{printf("有符合条件的元素，位置为：%d\n线性表为：",r+1);OutputList(&LL);}while(1){printf("请输⼊删除元素位置，输⼊0结束查找操作：");fflush(stdin);/*清楚标准输⼊缓冲区*/scanf("%d",&r);if(r==0)break;i=DeleteList2(&LL,r-1);if(i<0)printf("位置越界\n");else{printf("线性表为：");OutputList(&LL);}}}链表基本操作l 实验⽬的2、链表（1）掌握链表的概念，学会对链表进⾏操作。

数据结构实验报告实验1一、实验目的本次实验的主要目的是通过实际操作和编程实现，深入理解和掌握常见的数据结构，如线性表、栈、队列等，并能够运用所学知识解决实际问题。

二、实验环境本次实验使用的编程环境为Visual Studio 2019，编程语言为C+＋。

三、实验内容与步骤（一）线性表的实现与操作1、顺序表的实现定义一个固定大小的数组来存储线性表的元素。

实现插入、删除、查找等基本操作。

2、链表的实现定义链表节点结构体，包含数据域和指针域。

实现链表的创建、插入、删除、遍历等操作。

（二）栈的实现与应用1、栈的实现使用数组或链表实现栈的数据结构。

实现入栈、出栈、栈顶元素获取等操作。

2、栈的应用利用栈实现表达式求值。

（三）队列的实现与应用1、队列的实现使用循环数组或链表实现队列。

实现入队、出队、队头元素获取等操作。

2、队列的应用模拟银行排队系统。

四、实验结果与分析（一）线性表1、顺序表插入操作：在指定位置插入元素时，需要移动后续元素，时间复杂度为 O(n)。

删除操作：删除指定位置的元素时，同样需要移动后续元素，时间复杂度为 O(n)。

查找操作：可以直接通过索引访问元素，时间复杂度为 O(1)。

2、链表插入操作：只需修改指针，时间复杂度为 O(1)。

删除操作：同样只需修改指针，时间复杂度为 O(1)。

查找操作：需要遍历链表，时间复杂度为 O(n)。

（二）栈1、表达式求值能够正确计算简单的四则运算表达式，如 2 ＋ 3 4。

对于复杂表达式，如（2 ＋ 3) 4，也能得到正确结果。

（三）队列1、银行排队系统模拟了客户的到达、排队和服务过程，能够反映出队列的先进先出特性。

五、实验中遇到的问题及解决方法（一）线性表1、顺序表的空间浪费问题问题描述：当预先分配的空间过大而实际使用较少时，会造成空间浪费。

解决方法：可以采用动态分配空间的方式，根据实际插入的元素数量来调整存储空间。

2、链表的指针操作错误问题描述：在链表的插入和删除操作中，容易出现指针指向错误，导致程序崩溃。

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：线性表数据结构试验班级：软件112学号：姓名：线性表实验报告要求1目的与要求:1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现；4）熟练掌握线性表的链式存储结构的基本操作算法实现;5）掌握线性表在实际问题中的应用和基本编程技巧;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电子（全班同学提交到学委，再统一打包提交给老师）和纸质（每班每次5份，学委安排，保证每个同学至少提交一次）；8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理；9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操作时调试和运行。

凡不做准备，没有提前编写程序者，拒绝上机试验。

2实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。

按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值）；3）在顺序表中查找第i个元素，并返回其值；4）在顺序表第i个元素之前插入一已知元素；5）在顺序表中删除第i个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。

按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中第i个结点之前插入一个新结点；6）在线性表中删除第i个结点；7）计算链表的长度。

实验1: 顺序表的操作实验一、实验名称和性质二、实验目的1．掌握线性表的顺序存储结构的表示和实现方法。

2．掌握顺序表基本操作的算法实现。

3．了解顺序表的应用。

三、实验内容1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。

3．删除有序顺序表中的重复元素（设计性内容）。

四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC++6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。

六、验证性实验1．实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。

（4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。

2. 实验相关原理线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#define MAXLEN 30 /*线性表的最大长度*/typedef struct{Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/int length; /*顺序表的长度，即元素个数*/}Sqlist; /*顺序表的类型*/【核心算法提示】（1）顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i ≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

实验2链表基本操作实验一、实验目的1. 定义单链表的结点类型。

2. 熟悉对单链表的一些基本操作和具体的函数定义。

3. 通过单链表的定义掌握线性表的链式存储结构的特点。

二、实验内容与要求该程序的功能是实现单链表的定义和主要操作。

女口：单链表建立、输出、插入、删除、查找等操作。

该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。

程序中的单链表(带头结点)结点为结构类型，结点值为整型。

要求：同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。

必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。

三、算法分析与设计。

1•创建单链表：头结点LA1 A2An A2.单链表插入void LinkedListlnsert(LinkedList L,int i,ElemType x) 链表插入函数(L头指针，i插入位置，x插入兀素)LinkedList p,s;疋义结构体类型指针p,sj=1;p=L;疋义整型j计数，寻找插入位置，p指针指向头结点p=p->next;j++; 满足条件时p指针后移,j自加1while(p&&j<i) 当p为真且j<i时循环j 〜____ p=NULL||j<i一一printf("插入位置不正确\n");s=(LNode *)malloc(sizeof(LNode));使用malloc函数动态分配存储空间，指针s指向新开辟的结点，并将插入元素x存放到新开辟结点s的数据域，将结点s指向i+1 结点位置，第i个结点指向s,实现了链表元素插入。

by1s->data=x; s->n ext=p->n ext; p->n ext=s;3.单链表的删除:p->n ext=p->n ext- >n ext;15 x=表 -俞弹i tl 度 書翁的琴素汕6.从链表中查找元素四、运行结果1.单链表初始化骨选择夷进行的操作、遍历链表 J 从链表中査找元素1.如程輕巴章兰与竽疋匹菇值里同門元素在顺序aw 位置 迥链五Fs 已元壽上也库吏卬删除更10^5^性表 毒他键退出。