实验2 线性表的基本操作及应用
一、实验目的
1、掌握单链表的创建，插入、删除、查找和打印算法；
2、运用线性表解决线性结构问题。
二、实验内容
基本要求：
1、实现单链表的创建
2、实现单链表的插入
3、实现单链表的删除
4、实现单链表的查找
5、实现单链表的显示；
选作内容：
两个线性表合并算法的实现。已知顺序表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB归并为一个新的顺序表LC，且LC中的数据元素仍按值非递减有序排序。例如：LA＝（3,5,8,11） LB＝（2,6,9,15,20）。
三、实验步骤
1、程序设计规划（实现的功能、分几个模块、子函数）
2、编写单链表创建子函数
3、编写单链表插入子函数
4、编写单链表删除子函数
5、编写单链表查询子函数
6、编写单链表显示子函数
7、编写主函数Main()，通过功能菜单调用子函数
8、编译调试程序
四、参考源码：
见LinkList.cpp
实验一线性表的应用 一、实验教学目的 1、熟悉将算法转换成程序代码的过程。 2、了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 3、熟悉链表数据结构的定义和插入、删除等基本操作，会使用链表的基本操作解决一些实际问题 二、实验教学内容 1、实验题目 (1)用C语言数组实现顺序表,并在顺序表上实现：①在第3个位置插入666; ②将第8个元素删除；③在顺序表中查找值为65的元素。 (2)已知有两个多项式Pn(x)和Qm(x)，基于链表设计算法实现Pn(x)+Qm(x)运算，而且不重新开辟存储空间。 ⑶基于链表编程实现多项式乘法运算 2、实验要求： (1)要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。 (2)熟悉链表及其运算的实现。 ①自己编写实现函数； ②对所编写的算法进行时间复杂度分析。 ⑶实验⑴、⑵必做，实验⑶选做。 3、实验预备知识 （1）复习C语言相关知识（如：结构体、用typedef自定义类型、函数）。 （2）阅读顺序表与链表的类型定义和相应的插入、删除、查找等基本操作。 4、实验环境
（1）一台运行 Windows 2000/XP 操作系统的计算机。 （2）选用turbo c、visual c++、delphi、c++ builder 或visual basic等任何一种语言。 5、实验说明 （1）顺序存储定义 #define MAXSIZE 100/*表中元素的最大个数*/ typedef int datatype; /*元素类型*/ typedef struct {datatype data[MAXSIZE]; /*静态线性表*/ int last; /*表的实际长度*/ }seqlist; /*顺序表的类型名*/ （2）建立顺序表时可利用随机函数自动产生数据。 （3）注意问题 ①插入、删除时元素的移动原因、方向及先后顺序。 ②不同的函数形参与实参的传递关系。 （4）链表类型定义 typedef int datatype;/*元素类型*/ typedef struct node {datatype data; struct node *next; }lnode,*linklist;/*单链表的类型定义*/ （5）为了算法实现简单，最好采用带头结点的单向链表。 （6）注意问题 ①重点理解链式存储的特点及指针的含义。 ②注意比较顺序存储与链式存储的各自特点。 ③注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 ④单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。 三、实验内容和实验步骤：（由学生填写） 四、实验用测试数据和相关结果分析：（由学生填写） 五、实验总结：（由学生填写） 六、程序参考模板
《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求：
数据结构 实验1：线性表的基本操作及其应用 班级：RB软工移151 学号：201560140140 姓名：袁若飞
实验一线性表 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，题目一、二是必做题。题目三、题目四选作。 三、实验准备知识 1、请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个： （1）初始化线性表initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。 （2）求表长度List_length(L)——即求表中的元素个数。 （3）按序号取元素get_element(L,i)——取出表中序号为i的元素。（4）按值查询List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。 （5）插入元素List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6）删除元素List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。 2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。
实验二线性表(顺序存储) 一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2. 重点是线性表的基本操作在两种存储结构上的实现；本次实验以顺序存储的操作为侧重点；并进一步学习结构化的程序设计方法。 二、实例 1. 线性表的顺序存储表示（结构）及实现。 阅读下列程序请注意几个问题： （1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体： typedef struct { ElemType a[MAXSIZE]; /* 一维数组子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */ （2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 [源程序] （略） 三、实验题 1. 一个线性表有n个元素（n 姓名学号 ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i 实验一线性表的基本操作 一、实验目的 1. 熟悉C/C++语言上机环境； 2. 掌握线性表的基本操作：查找、插入、删除等运算在顺序存储、链式存储结构上的运算。 二、实验环境 1. 装有Visual C＋＋6.0的计算机。 2. 本次实验共计2学时。 三、实验内容 1. 建立顺序表，基本操作包括：初始化、建立顺序表、输出顺序表、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 2. 设有两个非递增有序的线性表A和B，均已顺序表作为存储结构。编写算法实现将A表和B表合并成一个非递增有序排列的线性表（可将线性表B插入线性表A中，或重新创建线性表C）。 3. 建立单链表，基本操作包括：初始化、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 四、源程序 #include 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 实验一线性表操作 实验目的： (1)掌握在顺序、链式存储结构上实现线性表的各种基本运算。 (2)重点掌握单链表的基本操作及应用。 (3)学会综合运用C语言中函数、指针、结构体等知识进行编程。 本次实验中，下列实验项目选做一。 1、顺序表的综合操作 [问题描述] 设计算法，实现线性结构上的顺序表的建立以及元素的查找、插入、删除等操作。 [基本要求及提示] （1）从键盘输入10个整数，建立顺序表。 （2）从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 （3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。 （4）从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 （5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、线性表的逆置 [问题描述] （1）以顺序存储结构实现线性表的就地逆置。 （2）以链式存储结构实现线性表的就地逆置。 注：线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,…,an）逆置为（an，an-1，…，a2，a1）。 [基本要求及提示] （1）从键盘输入10个整数，建立顺序表。 （2）实现顺序表逆置，并将结果输出。 （3）从键盘输入10个整数，建立链表。 （4）实现链表逆置，并将结果输出。 （5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。也可以将顺序表和链表上的操作分开，做成两个程序。 3、线性表的元素分类 [问题描述] 已知线性表中元素均为正整数，设计算法将其调整为前后两部分，前边均为奇数，后边均为偶数。即实现线性表的元素的分类。 [基本要求及提示] （6）从键盘输入10个整数，建立顺序表。 实验报告——线性表应用一、实验目的 用单链表储存一元多项式，并实现两个多项式的相加运算。 二、实验内容 1.先创建链表，存储多项式； 2.输出多项式； 3.两个多项式相加； 4.输出多项式。 三、程序代码 #include void print(Polynode*L) { Polynode*p; p=L->next; printf("a="); if(p&&p->coef!=0) printf("%.2f*x^%d",p->coef,p->exp); while(p->next!=NULL) { if((p->next->coef)>0&&p) printf("+"); else printf("-"); p=p->next; printf("%.2f*x^%d",fabs(p->coef),p->exp); } } //多项式相加 void polyadd(Polylist polya,Polylist polyb) { Polynode*p,*q,*tail,*temp; int sum; p=polya->next; q=polyb->next; tail=polya; while (p!=NULL&&q!=NULL) { if(p->exp 一．实验名称 1.线性表基本操作； 2.处理约瑟夫环问题 二．试验目的： 1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．定义单链表的结点类型。 3．熟悉对单链表的一些基本操作和具体的函数定义。 4．通过单链表的定义掌握线性表的链式存储结构的特点。 5．熟悉对单链表的一些其它操作。 三．实验内容 1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。 2.编制一个能求解除约瑟夫环问题答案的程序。 实验一线性表表的基本操作问题描述： 1. 实现单链表的定义和基本操作。该程序包括单链表结构类型以及对单链表操作 的具体的函数定义 程序中的单链表（带头结点）结点为结构类型，结点值为整型。 /* 定义DataType为int类型*/ typedef int DataType; /* 单链表的结点类型*/ typedef struct LNode {DataType data; struct LNode *next; }LNode,*LinkedList; LinkedList LinkedListInit() //初始化单链表 void LinkedListClear(LinkedList L) //清空单链表 int LinkedListEmpty(LinkedList L)//检查单链表是否为空 void LinkedListTraverse(LinkedList L)//遍历单链表 int LinkedListLength(LinkedList L)//求单链表的长度 /* 从单链表表中查找元素*/ LinkedList LinkedListGet(LinkedList L,int i) /* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListInsert(LinkedList L,int i,DataType x) //向单链表中插入元素 /* 从单链表中删除元素*/ void LinkedListDel(LinkedList L,DataType x) 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 实验编号：2四川师大《数据结构》实验报告2016年9月30日 实验二线性表及其实现_ 一．实验目的及要求 （1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点。 （2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用。 （3）掌握循环链表和双链表的定义和构造方法。 二．实验内容 （1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找）、排序等），并设计一 个菜单调用线性表的基本操作。 （2）建立一个按元素递增有序的单链表L，并编写程序实现： a）将x插入其中后仍保持L的有序性； b）将数据值介于min和max之间的结点删除，并保持L的有序性； c）将单链表L逆置并输出； （3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。 注：（1）为必做题，（2）~（3）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找）、排序等），并设计一 个菜单调用线性表的基本操作。 A.顺序储存： 代码部分： Main.cpp: #include"Sqlist.h" int main() { Sqlist L; int e = 0, number=0,locat =0,elect=0; int ret;//存放返回值 printf("请先创建一个含有10个整型元素的顺序表！\n"); Initlist_Sq(L); do { elect=Print_Sq(L); switch (elect) { case 0: break; case 1://插入 printf("请输入你想添加的位置和数字（用空格隔开）："); scanf_s("%d%d",&number,&locat); ListInsert_Sq(L, number, locat); break; case 2://删除 printf("请输入你想删除数字的位置："); scanf_s("%d", &locat); listDelete_Sq(L, locat, e); printf("the delete number is %d\n", e); break; case 3://顺序查找 printf("请输入你想查找的数字："); scanf_s("%d", &number); ret=listFine1_Sq(L, locat, number); if(ret) { printf("%d在表中的位置是%d\n", number, locat); 数据结构实验报告一 题目：线性表的应用举例班级：信息一班 姓名：冯琴琴 学号： 120108010001 得分： 实验一线性表的应用举例 1. 求两个线性表La和Lb的并集 La = La U Lb 2. 已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 #include 学 《数据结构》课程 实验报告 实验名称：线性表基本操作的实现实验室(中心)： 学生信息： 专业班级： 指导教师： 实验完成时间： 2016 实验一线性表基本操作的实现 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件 计算机、Microsoft Visual C++ 6.0软件 四、设计方案（算法设计） ㈠采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 ㈡设计的主要思路 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 4.对前面建立的链表进行插入、删除及连个链表的连接操作； ㈢算法描述 1、顺序表 void Init(sqlist &);//初始化顺序表 BOOL Inse(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int Loc(sqlist,char); //在线性表中定位元素 void print(sqlist); //输出顺序表 void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并 2、链表 void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 五、程序代码 1、顺序表 #include 实验报告二线性表 一、实验目的： （1）理解线性表的逻辑结构、两种存储结构和数据操作； （2）应用顺序表的基本算法实现集合A=AUB算法，应用顺序表的基本算法实现两有序顺序表的归并算法；（单链表的归并算法） （3）掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。 二、实验容： 1、设有线性表LA＝（3,5,8,11）和LB=（2,6,8,9,11,15,20）； ①若LA和LB分别表示两个集合A和B，求新集合 A＝A U B（‘并’操作，相同元素不保留）； 预测输出：LA=（3,5,8,11,2,6,9,15,20） 实现代码： package Q1_1; public class Node 实验报告 实验二线性表及其基本操作实验(2学时) 实验目的： (1) 熟练掌握线性表ADT和相关算法描述、基本程序实现结构； (2) 以线性表的基本操作为基础实现相应的程序； (3) 掌握线性表的顺序存储结构和动态存储结构之区分。 实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲) (1)一元多项式运算的C语言程序实现(加法必做，其它选做)； (2) 有序表的合并； (3)集合的并、交、补运算； (4)约瑟夫问题的求解。 注：存储结构可以选用静态数组、动态数组、静态链表或动态链表之一。对链表也可以采用循环链表（含单向或双向）。 实验准备： 1) 计算机设备；2) 程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。 实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。 实验过程：（一元多项式的加法） 【算法描述】 定义两个指针qa和qb，分别指向多项式A和多项式B当前进行比较的某个结点，然后比较2个结点中的指数项，则有以下三种结果： 1、指针qa所指结点的指数值小于指针qb所指结点的指数值，则应摘取指针qa 所指的结点插入到“和多项式”链表当中去； 2、指针qa所指结点的指数值大于指针qb所指结点的指数值，则应摘取指针qb 所指的结点插入到“和多项式”链表当中去； 3、指针qa所指结点的指数值等于指针qb所指结点的指数值，则将两个结点的系数相加，若和数不等于零，则修改qa所指结点的系数值，同时释放qb所指结点。反之，从多项式A的链表删除相应结点，并释放指针qa和qb所指结点。【源程序】 #include 计算机系数据结构实验报告（1） 实验目的： 帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。 问题描述： 1、构造一个空的线性表L。 2、在线性表L的第i个元素之前插入新的元素e； 3、在线性表L中删除第i个元素，并用e返回其值。 实验要求： 1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线 性表的基本操作算法。 2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。 算法分析： 由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下： 实验内容和过程： 顺序存储结构线性表程序清单： //顺序存储结构线性表的插入删除 #include int len; //当前元素个数 int listsize; //当前存储最大容量 }SqList; //构造一个空的线性表L int InitList(SqList &L) { =(ElemType *)malloc(LISTSIZE*sizeof(ElemType)); if (! exit(-2); //分配空间失败 =0; =LISTSIZE; } //在顺序线性表L中第i个位置之前插入新的元素e int ListInsert(SqList &L,int i,ElemType e) { if (i<1||i>+1) return -1; //i值不合法 if >= { ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType)); //存储空间已满，增加分配 if(!newelem) exit (-2); //分配失败 =newelem; +=CREMENTSIZE; } ElemType *q=&[i-1]) ; for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++; return 1; } //在顺序线性表L中删除第i个元素，并用e返回其值 int ListDelete(SqList &L,int i,ElemType&e) { if (i<1||i> return -1; //i值不合法 实验报告 实验一线性表 实验目的： 1. 理解线性表的逻辑结构特性； 2. 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4?掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。 实验原理： 线性表顺序存储结构下的基本算法； 线性表链式存储结构下的基本算法； 实验内容： 2 - 21设计单循环链表，要求： (1 ) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删 除操作、取消数据元素操作和判非空操作。 (2 ) 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2 — 22 .设计一个有序顺序表，要求： (1 ) 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取 数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 (2 ) 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 (3) 设计合并函数ListMerge ( L1,L2,L3 ),功能是把有序顺序表 L1和L2中的数据元 素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。程序代码： 2－21 (1)头文件 LinList.h 如下： typedef struct node { DataType data; struct node *next; }SLNode; /* ( 1 )初始化 ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /* 如果有内存空间，申请头结点空间并使头指针 head 指向头结点 */ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1); (*head)->next=NULL; /* 置结束标记 NULL*/ } 南昌航空大学实验报告 课程名称：数据结构实验名称：实验二线性表的链式存储结构 班级：学生姓名：冯华华学号：11046213 指导教师评定： XXX 签名: XXX 一、问题描述 1单链表的实现与操作。 2设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，…， n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整 数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。例如，n=7,7个人的密码依次为： 3,1,7,2,4,8,4,m的初值取6，则正确的出列顺序应为6,1,4,7,2,3,5。要求使用单向循环 链表模拟此出列过程。 二、程序分析 约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的 生成其中的结点，出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。 用结构指针描述每个人： struct Joseph {int num;/*环中某个人的序号*/ int secret;/环中某个人的密码*/ struct Joseph *next;/指向其下一个的指针*/}; 1）初始化约瑟夫环： 调用函数struct Joseph *creat()生成初始约瑟夫环。在该函数中使用head 指向 表头。输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到 链表中，p2 指向最后一个序号为非0 的结点（最后一个结点）。 2）报数出列： 调用函数voil sort(struct Joseph * head,int m)，使用条件p1->next!=p1判断 单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1->next;移动指针， 计算结点数（报数）；结点p1出列时直接使用语句：p2->next=p1->next，取出该 结点中的密码作为新的循环终值。 三、调试过程及实验结果 最后程序运行结果如下所示： 输入数据：数据格式为序号，密码 输入0，0为结束 1，3↙<回车> 2，1↙<回车>实验一线性表与应用(I)
实验一 线性表的基本操作
《数据结构》实验一 线性表及其应用
实验一 线性表操作实验题目
数据结构《线性表的应用》实验报告
线性表实验报告
数据结构线性表的应用实验报告
数据结构_实验二_线性表及其实现
线性表的应用举例实验报告(燕山大学)
数据结构实验线性表基本操作
实验二线性表
实验报告二：线性表及其基本操作实验(2学时)
数据结构实验线性表及其应用
数据结构线性表实验报告
实验二 线性表的链式存储结构
相关主题
文本预览