实验一线性表的插入与删除
1. 实验目的
掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。
2. 实验内容
1．产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。
2．编制一个程序，依次实现以下功能：
(1)定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。
(2)从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后
保持线性表的有序性。最后将此有序线性表打印输出。
(3)在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。
3．以N=100及N=400分别运行2的程序，并比较它们的运行时间。
4．编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。
3. 实验步骤和要求
1．事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。
2．运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。
3．以N=100运行2的程序，并记下运行时间。
4．以N=400运行2的程序，并记下运行时间。
5．运行4的程序。
6．整理程序清单和运行结果，写出实验报告。
4. 方法说明
（1）随机整数的产生
产生随机整数的方法有很多，下面只介绍一种方法：
设m=216，初值y0=0，则递推公式y i=mod(2053 y i-1+13849，m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算x i=INT(1000y i/m)。
其中mod（*）是模运算，INT（*）是取整函数。
（2）线性表的插入与删除
在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。
为了要将新元素插入到一个有序的线性表中，可以从原有序表的最后一个元素开始，往前逐个与新元素比
较，并将大于新元素的所有元素都往后移动一个位置，直到找到新元素应插入的位置为止。显然，插入一个新元素后，表的长度也增加了1。现假设用一个数组L(1:m)来存储线性表，其中m 为最大容量（在本实验中为m=1000）；用一个变量n 表示线性表的长度（在本实验中，其初值为n=0）。则可以得到将新元素插入到有序线性表的算法如下。
输入：数组L(1:m)，有序线性表L(1:n)，需插入的新元素b 。其中n RETURN } 1n n } b 1)i L( 1}- i i L(i); 1)+{L(i DO b)>(L(i) and 0)>(i WHILE n i ELSE{ b 1)+L(n THEN 0=n IF ELSE{overflow"" OUTPUT THEN m =n IF +←←+←←←← 要在原线性表中删除一个元素b （在本实验中，保证b 在线性表中），且仍保持线性表的顺序存储结构，可以从线性表的第一个元素开始，往后逐个与新元素相比较，直到发现一个元素与新元素相等。然后从当前位置的下一个元素开始，将后面所有元素都往前移动一个位置，直到线性表的最后一个位置为止。显然，删除一个元素之后，线性表的长度减小了1。其算法如下。 输入：线性表L(1:n)，n 为线性表的长度，删除的元素b （一定在线性表中）。 输出：删除b 后的线性表L(1:n)。 RETURN } } 1n 1)L(j L(j) DO 1-n TO i j FOR THEN n i IF ELSE{ element" not this " OUTPUT THEN n i IF 1i DO b)(L(i) and n)(i E WHIL 1i ELSE{underflow"" OUTPUT THEN 0=n IF -←+←=<>+←≠≤←n i 在上述算法中，从线性表的第一个元素开始寻找要删除的元素b,实际上我们还可以从线性表的最后一个元素开始寻找b ，其算法留给读者自行考虑。 （3）线性链表的插入排序 定义一个二列数组A(1:1000，1:2)，其中，A(i,1)(i=1,2,…,1000)依随机数产生的顺序存放1000个数据，A(i,2)(i=1,2,…,1000)为链接指针，将1000个随机数链接成有序链表。其插入排序的方法如下。 依次从数据文件中读入一个数据，将它按行顺序存放到数组A 的第一列中，然后通过相应行的第二列将它链接到已经有序的链表中。其过程为：将读入的数据依次与链表中各元素进行比较，找到其应该插入的位置后，适当改变链指针，将其插入。其算法如下： 输入：1000个随机整数。 输出：头指针为H 的有序链表。 RETURN } }k A(i,2)A(i,2);) A(k,2 A(i,2)i DO x)1)(A(A(i,2), and 0)(A(i,2) WHILE H i ELSE{ k}H H;{A(k,2) THEN x A(H,1)IF x A(k,1) x;READ DO{ 1000 TO 2k FOR 0 A(1,2)x; A(1,1) x;READ 1;H ←←←<≠←←←>=←=←←← 实验二二叉树 1. 实验目的 掌握二叉树的存储结构 2. 实验内容 1．对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。 2．按层次输出所有结点。 3．输出所有叶子结点。 4．将所有左右子树值交换。 3. 实验步骤和要求 1．分别编制实验内容中题2、3、4的三个子程序。 2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。 （1）输入二叉树用链式结构存储； （2）调用题2的子程序，并输出结果； （3）调用题3的子程序，并输出结果； （4）调用题4的子程序，并输出结果； 3．自行设计一棵二叉树，重复步骤2。 4．整理程序清单与所有结果，并写出实验报告。 4. 方法说明 （1）二叉树的链式存储结构 二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i）。我们分别用三个一维数组表 示它们，并用头指针HBT指向二叉树的根结点。具体存储方案由读者自行考虑。 （2）按层次输出所有结点 为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。这个过程一直进行到队列空为止。设循环队列数组为cq（1：m），其头尾指针分别为front与rear，则按层次输出所有结点的算法如下： IF HBT = 0 THEN RETURN “ THIS TREE IS EMPTY” Front ←m, rear← m ADD ( cq, HBT, front, rear ) WHILE front ≠rear DO { DEL ( cq , i, front ,rear ) OUTPUT ( L( i ) , V( i ) ,R ( i )) IF L( i )≠0 THEN ADD (cq , L( i ), front, rear) IF R( i )≠0 THEN ADD (cq , R( i ), front, rear) } RETURN 在这个算法中的ADD和DEL分别为入队和退队运算的两个过程,其算法(不考虑溢出情况)如下： ADD （cq，i，front，rear） rear←rear + 1 IF rear = m + 1 THEN rear ←1 cq （rear）←i RETURN DEL (cq, i, front, rear ) front ←front + 1 IF front = m+ 1 THEN font←1 i←cq (front ) RETURN （3）输出所有叶子结点 叶子结点的左右指针域均为零。因此，为了输出所有叶子结点，需要设置一个容量足够大的栈S（可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。其算法如下： IF HBT = 0 THEN RETURN “THIS TREE IS EMTPY ” top←0 PUSH （S，HBT，top） WHILE top ≠0 DO { POP（S，i，top） IF （L（i）=0）and （R（i）=0）THEN OUTPUT V（i） ELSE { IF R（i）≠0 THEN PUSH （S，R（i），top） IF L（i）≠0 THEN PUSH （S，L（i），top） } } RETURN 其中PUSH 和POP分别为入栈和退栈的过程，其算法由读者自行考虑。 （4）将所有左右子树值交换 这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下： IF HBT = 0 THEN RETURN “THIS TREE IS EMPTY” top ←0 PUSH （S，HBT，top） WHILE top≠0 DO { POP（S，i，top） IF （L（i）≠0）or （R（i）≠0）THEN { L（i）?R（i） IF L（i）≠0 THEN PUSH （S，L（i），top） IF R（i）≠0 THEN PUSH （S，R（i），top） } } RETURN 实验三冒泡排序和快速排序 1. 实验目的 通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。 2. 实验内容 1）随机产生20位整数 2）输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。 1.冒泡排序 2.快速排序 3）纪录每种方法比较次数和移动次数 3. 实验环境 1．硬件：PC机。 2．软件：DOS 、Windows9.x 、Window2000或以上版本，TurboC 2.0 或以上版本。 实验四-1 多媒体关系型数据库的建立 1. 实验目的 通过实验综合应用有关多媒体、关系型数据库的基本技术，使学生了解关系型数据库的概念，包括数据项定义域、约束等；掌握SQL语言的基本语法和使用；掌握数据库、表、视图的建立，以及多媒体数据的录入。 2. 实验内容 为一个音像店建一个多媒体数据库，存储本店职工、相关音像商品、顾客、订单等信息。具体内容如下： 1、使用MS ACCESS数据库管理系统，通过示例数据库熟悉其操作，理解关系型数据库的基本概念； 2、使用VisData建立多媒体数据库MM－shop.mdb中的基表，掌握基本SQL语言的使用； 3、在ACCESS平台上维护MM－shop.mdb，建立多个查询表（视图）。 3. 实验步骤与要求 （一）、熟悉使用MS ACCESS数据库管理系统 1、在ACCESS数据库管理系统中创建一个新的空数据库db1.mdb； 2、使用“设计视图”新建多个表，增加多个字段，要包含所有的数据类型，并设计各个字段的属性，如：字段大小、格式、默认值、是否允许为空等等； 3、对自建表建立查询表，理解视图（View）的概念； 4、利用向导制作窗体，显示表内容； 5、利用向导制作报表，显示表内容； （二）、建立多媒体数据库MM－shop.mdb 1、在ACCESS数据库管理系统中建立空白数据库MM－shop.mdb； 2、使用VisData联接MM数据源，联接到MM－shop.mdb； 4、在VisData中使用SQL语言建立以下表：雇员、商品、客户、订单。具体字段名称如下，字段属性自己定义。 雇员数据项： 商品数据项： 客户数据项： 订单数据项： 5、在ACCESS数据库管理系统平台上进一步设计各个字段的唯一性、值域、格式、默认值、是否允许为空等约束条件； 6、在ACCESS数据库管理系统平台上输入示例数据，包括多媒体数据（JPG图片、MP3音频）； 7、在VisData平台上采用SQL语言执行数据查询、删除、插入、更新操作。 附：在VisData中使用SQL语言的步骤 （1）启动VisData ； （2）从菜单“文件－>打开数据库－>Microsoft Access”进入标准文件对话框，选择MM－shop.mdb数据库； （3）“SQL语句”窗口中输入SQL语句，然后“执行”即可。 （三）、在ACCESS数据库管理系统平台上建立查询表（视图） 1、查找出三种最贵的商品； 2、统计某一雇员的销售额。 4. 实验注意事项及说明 1、本实验第一部分主要为熟悉ACCESS数据库管理系统平台，理解关系型数据库的基本概念。对于ACCESS 本身所特有的窗体、报表、模块等功能有所了解即可； 2、本实验的第二部分为主要内容，应事先编制好相应的SQL语句，在上机实验时加以验证，并作为作业上交； 3、本实验的第三部分为主要内容，应予以重视，特别是“统计某一雇员的销售额”。可以考虑在ACCESS 的查询设计视图中使用SQL语言予以实现； 4、在输入示例数据时应注意，要输入足够的数据，特别是相关的数据，以利于查询表（视图）的建立。例如：在“订单”中出现的“雇员ID”一定要在“雇员”表中存在，等等。 实验四-2 数据库应用系统的开发 1. 实验目的 使用MS Visual Basic等快速开发工具，建立一个对上述多媒体数据库可以进行数据显示、增加、更新、删除等操作的小型数据库应用系统。结合实验六，使学生初步了解开发一个数据库应用系统的基本思路和方法。 2. 实验内容 在上述实验的基础上，为音像店多媒体数据库建立一个包括数据展示、数据输入、增减等基本操作的数据库应用系统。具体内容如下： 1、使用VB建立一个单文档窗口的数据库应用系统框架； 2、为每一个数据库表建立一个数据窗口； 3、在系统框架中引入各个数据窗口。 3. 实验步骤与要求 1、启动MS Visual Basic 6，选择“VB应用程序向导”，遵循向导建立一个“单文档界面”，即主窗体； 2、遵循向导，添加数据窗体； 3、对于不含有多媒体数据的数据库表，可以继续遵循向导建立多个数据窗体（要选择多种不同风格的窗体布局、绑定类型等）； 4、对于含有多媒体数据的数据库表，一般不直接使用向导。 （1）当遵循向导自动生成数据窗体结束后，从菜单“工程－添加窗体”加入新窗体； （2）手动建立数据窗体：在窗体中加入TEXT、LABEL、DATA和OLE控件，将DATA控件关联到数据库的含有多媒体数据的表，将TEXT关联到相应表的非多媒体字段，将OLE控件关联到含有多媒体数据的字段； （3）加COMMAND BUTTON控件，并加入相应的程序代码，实现数据的增加、更新、删除等操作； 5、在主窗体中加入菜单，将多个数据窗体联接到主窗体； 6、调试程序，直至顺利运行 4. 实验注意事项及说明 1、在遵循向导增加的数据窗体后，要从菜单“工程－>引用”中添加ADO2.0 Library； 2、手动生成的数据窗体的程序代码可以参考自动生成的数据窗体的程序段。 #include 《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include //* * * * * * * * * * * * * * * * * * * * * * * //PROGRAM NAME :顺序结构的线性表 * //CONTENT :插入,删除,查找 * //* * * * * * * * * * * * * * * * * * * * * * * #include 线性表实验报告 一、实验的目的要求 1、了解线性表的逻辑结构特性，以及这种结构特性在计算机内的两种存储结构。 2、掌握线性表的顺序存储结构的定义及其C语言实现。 3、掌握线性表的链式存储结构——单链表的定义及其C语言实现。 4、掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5、掌握线性表在链式存储结构——单链表中的各种基本操作。 6、认真阅读和掌握实验的程序。 7、上机运行本程序。 8、保存和打印出程序的运行结果，并结合程序进行分析。 二、实验的主要内容 题目：请编制C语言，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。 具体地说，就是要根据键盘输入的数据建立一个单链表，并输出该单链表；然后根据屏幕 菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后 在屏幕菜单中选择0，即可结束程序的运行。 三、解题思路分析 在链表中插入数据，不需要进行大量的数据移动，只需要找到插入点即可，可以采用后插入的算法，在插入点的后面添加结点。在链表中删除数据，先找到删除点，然后进行指针赋值操作。 四、程序清单 #include LNode *L; LNode *creat_L(); void out_L(LNode *L); void insert_L(LNode *L,int i,ElemType e); ElemType delete_L(LNode *L,ElemType e); int locat_L(LNode *L,ElemType e); void main() {int i,k,loc; ElemType e,x; char ch; do{printf("\n"); printf("\n 1.建立单链表"); printf("\n 2.插入元素"); printf("\n 3.删除元素"); printf("\n 4.查找元素"); printf("\n 0.结束程序运行"); printf("\n================================"); printf("\n 请输入您的选择(1,2,3,4,0)"); scanf("%d",&k); switch(k) {case 1:{L=creat_L(); out_L(L); }break; case 2:{printf("\n请输入插入位置:"); scanf("%d",&i); printf("\n请输入要插入元素的值："); 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 实验容：线性表的创建、插入删除等 #include"stdio.h" #include"stdlib.h" int*inistl(int m,int *n) /*建立线性表函数*/ {int*v=NULL; v=malloc(m*sizeof(int*)); /*创建链表，并把首地址赋给指针V*/ n=0; return v; } void insl(int*v,int m,int*n,int i,int b)/*在链表指定位置插入元素b*/ { int j; if(*n>=m) /*检查是否链表溢出*/ {printf("the stack is overflow\n"); return; } if(i>*n-1) i=*n+1; /*若插入点大于元素位置则在表的结束插入*/ if(i<1) i=1; /*空表在首部插入元素*/ for(j=*n;j>=i;j--) /*首位之间任意位置的插入*/ v[j]=v[j-1]; v[i-1]=b; *n=*n+1; /*插入后元素统计指针加1*/ } void desl(int*v,int m,int*n,int i) /*线性表删除函数*/ {int j; if(*n==0) /*判断线性表是否为空*/ {printf("the stack is underflow\n "); return; } if((i<1)||(i>*n)) /*删除点在首部以前和尾部以后特殊情况排除*/ {printf("not this element in the list!"); return; } for (j=i;j<=*n-1;j++) /*在允许位置做删除操作*/ v[j-1]=v[j]; *n=*n-1; /*元素统计指针减1*/ return; }) void input(int*v,int n) /*空表起始输入元素函数*/ {int i; for(i=0;i 管理学院信管专业12（1）班学号3112004734 姓名钟臻华协作者：无教师评定_________________ 实验题目线性表的基本操作 实验评分表 实验报告 一、实验目的与要求 1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概 念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对 算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、实验内容 1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分 析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。 1.顺序表的不删除出环元素算法实现 public class Josephus3{ public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数 //采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量 S eqList 实验一顺序表的操作 1.实验题目：顺序表的操作 2.实验目的和要求： 1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。 2)通过在Turbo C（WinTc，或visual stdio6）实现以上操作的C语言代码。 3）提前了解实验相关的知识（尤其是C语言）。 3.实验内容：(二选一) 1)顺序表的插入算法,删除算法,顺序表的合并算法 2)与线性表应用相关的实例(自己选择详尽实例) 4.部分参考实验代码： ⑴顺序表结构的定义： #include { int j; if(i<0||i>la-> length +1) {printf(“\n the value of i is wrong!”); return 0; } if(la-> length +1>=MAXLEN) { printf(“\n overflow!”); return 0; } . for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length++; return 1; } ⑶顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length) { printf(“\n the position is wrong!\n”); return 0; } 数据结构-线性表输入-输出-插入-删除-查找 创建一个线性表实现输入，输出，插入，删除，定位。 （注意：不论在调用哪个函数前，都要先使L.elem=a，就是使指针elem回到数组a的首地址。） #include 线性表的插入与删除的实现 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求 三.数据结构的定义 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。 2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。 在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 五.线性结构和非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。 线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。 常见的线性结构：线性表、栈、队列 七.线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征： 1.线性表中的所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ① 其中，LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。 因为在顺序存储结构中，每个数据元素地址可以通过公式①计算得到，所以线性表的顺序存储结构是随机存取的存储结构。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; #include"stdio.h" #include"stdlib.h" int*inistl(int m,int *n) /*建立线性表函数*/ {int*v=NULL; v=malloc(m*sizeof(int*)); /*创建链表，并把首地址赋给指针V*/ n=0; return v; } void insl(int*v,int m,int*n,int i,int b)/*在链表指定位置插入元素b*/ { int j; if(*n>=m) /*检查是否链表溢出*/ {printf("the stack is overflow\n"); return; } if(i>*n-1) i=*n+1; /*若插入点大于元素位置则在表的结束插入*/ if(i<1) i=1; /*空表在首部插入元素*/ for(j=*n;j>=i;j--) /*首位之间任意位置的插入*/ v[j]=v[j-1]; v[i-1]=b; *n=*n+1; /*插入后元素统计指针加1*/ } void desl(int*v,int m,int*n,int i) /*线性表删除函数*/ {int j; if(*n==0) /*判断线性表是否为空*/ {printf("the stack is underflow\n "); return; } if((i<1)||(i>*n)) /*删除点在首部以前和尾部以后特殊情况排除*/ {printf("not this element in the list!\n"); return; } for (j=i;j<=*n-1;j++) /*在允许位置做删除操作*/ v[j-1]=v[j]; *n=*n-1; /*元素统计指针减1*/ return; } void input(int*v,int n) /*空表起始输入元素函数*/ {int i; for(i=0;i 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 姓名学号 ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i #include 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构与算法 课程类型：必修 实验项目名称：线性表实验 实验题目：算术表达式求值 班级：0903201 学号：1090320110 姓名：王岳 一、实验目的 二、实验要求及实验环境 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 1．逻辑设计 2．物理设计 四、测试结果 五、系统不足与经验体会 六、附录：源代码（带注释） #include else { this -> top--; return this -> ss[this -> top + 1]; } } void push(elementtype x) { if (this -> top == 511) printf("error:full!!!\n"); else { this -> top++; this -> ss[this -> top] = x; } } }; void change(int &i,int &j,double *a,char *input,stack 实验一顺序表的操作 1. 实验题目：顺序表的操作 2.实验目的和要求： 1)了解顺 序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、 删除、查找以及线性表合并 )。 2)通过在 Turbo C ( WinTc ，或 visual stdio6 )实现以上操作的 C 语言 代码。 3)提前了解实验相关的知识(尤其是 C 语 言)。 3.实验内容：(二选一) 1) 顺序表的插入算法, 删除算法, 顺序表的合并算法 2) 与线性表应用相关的实例( 自己选择具体实例) 4.部分参考实验代码： ⑴ 顺序表结构的定义： #include . for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length ++; return 1; } ⑶ 顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length ) { printf( “ return 0; n”); } for(i;i 实验一线性表的基本操作 一、实验目的 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构上的运算。 二、实验要求 1、认真阅读和掌握本实验的程序。 2、上机运行本程序。 3、保存和打印出程序的运行结果，并结合程序进行分析。 4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单 和运行结果 三、实验内容 线性表基本操作的实现。 算法描述:对每一个算法,要写出算法的中文描述。本实验中要求写出在第i 个结点前插入数据为x的结点、删除指定结点、创建一个线性表、打印线性表的算法描述。 四、程序清单 1、sqlist.h文件清单： #include "stdio.h" #include "malloc.h" #define null 0 #define maxsize 1024 typedef char datatype; typedef struct { datatype data[maxsize]; int last; }sequenlist; /*在第i个结点前插入元素x（note：元素从0始计数）*/ int insert(sequenlist *L, datatype x,int i) { int j; if (L->last==maxsize-1)/*如果原线性表已经满了*/ { printf("overflow"); return 0; } else if ((i<0)||(i>L->last)) /*如果输入的i值超出范围*/ { printf("error,please input the right 'i'"); return 0; } else { for(j=L->last; j>=i; j--) /*从第i个元素起,每个元素后移一位*/ L->data[j+1]=L->data[j];顺序表的创建插入与删除
顺序表的查找、插入与删除实验报告
01顺序结构的线性表插入删除查找
线性表实验报告
数据结构-顺序表的查找插入与删除
线性表的创建插入和删除的操作
完整版信管实验报告(线性表基本操作)
实验一 数据结构顺序表的插入和删
数据结构-线性表输入-输出-插入-删除-查找
线性表的插入与删除的实现
数据结构_实验1_线性表的基本操作
线性表的插入,删除,修改
数据结构实验一题目一线性表实验报告
实验一线性表与应用(I)
线性表顺序存储实现、插入、删除操作
哈工大 数据结构 实验一 线性表的实验
实验一数据结构顺序表的插入和删除
线性表的插入和删除
相关主题
文本预览