贵州大学数据结构实验1-线性表及应用
实验一线性表及应用
一、实验目的
1．复习C语言的上机环境，掌握C语言的基本结构;
2．会定义线性表的顺序存储结构和链表的存储结构;
3．熟悉对顺序表的一些基本操作和具体的函数定义。
4．掌握顺序表和单链表的存储结构及相关运算
5．掌握顺序表和单链表的基本应用
二、实验硬软件环境
硬件环境：赛扬433以上CPU，10GB以上硬盘，64MB以上内存
软件环境：DOS+Turbo C 2.0 或Borland C++ 3.1以上
Windowx 9X+VC++ 5.0以上
三、实验要求
1．认真阅读和掌握本实验内容所给的全部程序。
2．保存和打印出程序运行结果，并结合程序进行分析。
3．按照你对顺序表操作的需要，屏幕考贝运行结果到实验报告中。
4．撰写实验报告并准时上交
四、注意事项
在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。
本实验设计完全由老师设计，版权限本班同学使用，勿外传。
实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构实验（张三）”文件夹中，形成如上图的文件夹结构。
上交实验报告时，请把“实验一”的所有内容（含实验报告）用winrar打包成.rar文件后一并交上来。上传名字为“实验一（张三）.rar”
五、基本理论
线性表：线性表（linear list）是这样的数据对象，其实例形式为： (e1 , e2 ,... en )，其中n 是有穷自然数。e
是表中的元素，n 是表的长度。元素
i
可以被视为原子，因为它们本身的结构与线性表的结构无关。当n = 0 时，表为空；当n > 0时，e1是第一个元素，e n是最后一个元素，可以认为e l优先于e2，e
优先于e3，如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。2
基本操作：
? 创建一个线性表。
? 确定线性表是否为空。
? 确定线性表的长度。
? 查找第k个元素。
? 查找指定的元素。
? 删除第k个元素。
? 在第k个元素之后/之前插入一个新元素。
线性表ADT（图1）：
图1 线性表抽象数据类型
顺序表：
采用数组来表示一个对象的实例，数组中的每个位置被称之为单元（cell）或节点（node），每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位置可以用一个数学公式来指明。
假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：
location(i)= i - 1 （式1-1）
式1-1表明第i个元素的存储位置在数组的第i-1个位置;
如果每个元素的长度为m，则可以通过公式计算第i个元素的存储地址：Address(i)=Address(1)+(i-1)*m (式1-2)
Address(1)为第1个元素的址，即数组的首地址。特别要记住的是第1个元素保存在数组的第0个位置。
图2 表性表实例
简而言之，顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。
优点：简单，数据元素的提取速度快；
缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n）
链表：
在存储线性表List中的每个元素e i时，同时存储元素的下一个元素的首地址（指针）Address(i+1),通过这种方法建立起元素之间的关系，从“逻辑”上看所有元素构成了图3所示的“链”，所以称为链表。
图3 一个单链表
从图3可以看出元素之间的链接关系，为了“访问”每个元素e i的，必须知道e i的首地址，而这个首地址存储在其“直接前驱”结点e i-1中，……，按此规律，可以回推到元素e1的首地址。即要访问List中任一元素e i,都必须从第一个元素e1开始，所以，必须保存首元素e1的地址在一个变量中(first),有的书使用Head作为变量名。图3的单链表的首元素的地址在first中，我们可以直接用“first”称呼此单链表。
List中所有元素可以占用连续的存储空间，也可以占用不连续的存储空间。但是从“逻辑”上来看所有元素仍然满足“一对一”的关系，即：（1）首元素没有“直接前驱”，尾元素没有“直接后继”。
（2）中间元素有且仅有一个“直接前驱”和“直接后继”
为了实现这种存储结构，可以使用C语言作如下定义：
的一个结点类型（用以存储一个数据元素，这样可以定义一个结点变量存储一个数据元素：
LinkNode a;
也可定义一个“结点”指针保存某个结点的首地址：
LinkNode *p;
对于其它可能不支持动态存储分配的高级语言来说，上述LinkNode类型定义时就内部就不能使用地址，但是我们可以利用数组“模拟”链表的功能，这种链
中的“位置”，这样定义的链表如图4所示：
图4 静态链表
链表还有“循环链表”（图5）和“双链表”（图6），无论多么复杂的链表，其基础都是单链表，因此，完全掌握单链表后，学习其它有关链接存储将会变得简单得多，这是本章我们的重点任务。
循环单链表，实际上是利用链表的“尾结点”的空指针来指向链表的首结点。有循环链表后，只要知道链表中任一结点的地址，就可以访问链表中所所有结点。注意图5b引入了一“头结点”，目的是让空链表与非空链表统一，方便操作实现。
图5 循环单链表
双链表是在单链表的基础上，在数据元素中再增加一个冗余项，用以保存结点的“直接前驱”结点的地址，这样结点既可以指向“直接后继”，也可以指向“直接前驱”，实现链表的双向查找。
图6 双向链表
链表最大的优点是在某个元素之后插入结点或删除结点非常方便，时间复杂度为常数O（1）。缺点是空间利用率低，存取指定元素效率低O（n）。
六、实验内容与过程
本实验用到的文件有（在文件夹“实验一\实验材料\”中）
Lineast.h、Lineast.cpp、LineastTest.cpp 、Link.h、Link.cpp、、LinkTest.cpp 前三个文件保存在子目录“SqList”中，后三个保存在子目录“Link”中后缀有“Test”的文件用以测试顺序表和链表的各项操作的正确性，里面包含了主函数“main”。*.h文件中包含了数据结构的定义，对应的同名cpp文件包含了对数据结构进行的各种操作的实现。
请按以下提示完成所有实验。
（一）文件Lineast.cpp是顺序表的实现，其中有三个函数没有完全实现，请同学认真阅读整个程序，然后根据所学的知识完善，完善后编译Lineast.cpp，然
for(int j=L->Length+1;j>i;j--)
{
L->data[j]=L->data[j-1];
}
L->Length++;
{
printf("error");
return 0;
}
else
for(j=i;j
L->data[j]=L->data[j+1];
}
L->Length--;
for(int m=1;m<=n;m++) {
if(L->data[m]==*e)
{
j=m;
break;
}
else
continue;
}
图7 运行菜单
对菜单中的每个功能项进行测试，以了解程序是否按照要求完成指定工作。
屏显：
）输入3，回车后，根据屏幕提示输入1，回车
屏显：
）输入3，回车后，根据屏幕提示输入3，回车
屏显：
）输入3，回车后，根据屏幕提示输入7，回车屏显：
屏显：
）输入3，回车后，根据屏幕提示输入：0，回车
屏显：
原因：此表是从1开始的，不存在0号元素
输入3，回车后，根据屏幕提示输入小于等于0的数，回车
屏显：
原因：此表是从1开始的，不存在-1号元素
）输入4，回车后，根据屏幕提示输入：35 3，回车
屏显：
）输入4，回车后，根据屏幕提示输入：10 1，回车
屏显：
）输入4，回车后，根据屏幕提示输入：5 0，回车
屏显：
原因：插入元素必须为在1到L->length+1之间）输入4，回车后，根据屏幕提示输入：5 -1，回车
屏显：
原因：插入元素必须为在1到L->length+1之间）输入4，回车后，根据屏幕提示输入：90 9，回车
屏显：
）输入4，回车后，根据屏幕提示输入：95 10，回车
屏显：
）输入4，回车后，根据屏幕提示输入：100 12，回车
屏显：
原因：插入元素必须为在1到L->length+1之间）输入5，回车
屏显：
）输入6，回车后，根据屏幕提入示输入：70 4，回车
屏显：
）输入6，回车后，根据屏幕提入示输入：5 0，回车
屏显：
原因：对表操作必须在1到L->length
）输入6，回车后，根据屏幕提入示输入：100 9，回车
屏显：
）输入6，回车后，根据屏幕提入示输入：110 11，回车
屏显：
修改元素后并为对L->length进行++
）输入7，回车后，根据屏幕提入示输入：6，回车
屏显：
）输入7，回车后，根据屏幕提入示输入：0，回车
屏显：
数组是从1开始的
）输入7，回车后，根据屏幕提入示输入：10，回车
屏显：
原因：第10号元素存在，并且为95
）输入8，回车
屏显：
）输入2，回车
屏显：
原因：L->length被清0
进一步思考并回答：
（1）步骤1、2分别用来干什么？
答：初始化一个顺序表
（2）步骤2-8用来干什么？其中步骤5-8有什么用？
答：2到8是用来删除一个元素，5到8是用来验证当删除条件不满足时是否能执行删除。
（3）步骤9-14用来干什么？其中11、12、13、14的目的是什么？
答：9到14是用来加入一个元素，11到14是用来验证当插入条件不满足时是否能进行插入。
（4）步骤16-19作用是什么？
答：是用来改变一个表内元素的值。
（5）步骤20-21作用是什么？
答：是用来验证当改变条件不满足时，是否能改变一个表内元素的值。
（二）单链表的操作实现放在Link.CPP中，其中有几个函数未完成（如下），请
int n=GetLength(L);
if(i<1||i>n)
return NULL;
if(i==1)return p;
for(j=0;j<=n;j++)
{
if(j!=i-1)p=p->next;
else break;
}
{
数据结构实验报告全集
数据结构实验报告全集 实验一线性表基本操作和简单程序 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、掌握线性表的顺序存储结构的定义及其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——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 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
数据结构实验报告 实验一 线性表链式存储运算的算法实现
昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名： 年月日 一.实验内容： 线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束
pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s 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 } 四.程序运行结果：
完整版信管实验报告(线性表基本操作)
管理学院信管专业12（1）班学号3112004734 姓名钟臻华协作者：无教师评定_________________ 实验题目线性表的基本操作 实验评分表
实验报告 一、实验目的与要求 1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概 念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对 算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、实验内容 1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分 析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。 1.顺序表的不删除出环元素算法实现 public class Josephus3{ public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数 //采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量 S eqList 实验1 线性表及其应用 题目1 顺序表的建立与基本操作 一、实验目的 1. 通过实验，掌握include命令及头文件的使用 2. 通过实验，掌握顺序表的建立与输出 3. 通过实验，掌握顺序表的基本操作 二、实验内容 1. 练习顺序表的建立与输出 2. 练习顺序表的基本操作 三、实验前的准备 1. 理解并掌握顺序表的存储结构、基本操作 2. 复习include命令的使用 3. 预习实习指导书，并准备相关的程序清单 四、实验步骤与方法 （1）建立自己的工作目录 （2）在当前文件夹下建立函数结果状态代码的定义文件Status.h（课本p10（1）预定义常量和类型）和数据结构数据文件SqList.h（内容包括顺序表的描述、顺序表建立、顺序表的查询、插入、删除与输出等功能。） （3）理解并运行下列程序： #include 实验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; 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 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、熟悉将算法转换成程序代码的过程。 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——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 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 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构与算法 课程类型：必修 实验项目名称：线性表实验 实验题目：算术表达式求值 班级：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) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 姓名学号 ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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) //实现加法功能。 数据结构 实验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.熟悉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、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 实验报告 实验一线性表 实验目的： 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);实验1 线性表及其应用
数据结构_实验1_线性表的基本操作
数据结构线性表实验报告
实验1__线性表的应用
数据结构实验一题目一线性表实验报告
哈工大 数据结构 实验一 线性表的实验
数据结构实验一 实验报告
实验一线性表与应用(I)
数据结构线性表的应用实验报告
201560140140--袁若飞--实验1：线性表的基本操作及其应用
《数据结构》实验一 线性表及其应用
数据结构实验一 实验报告
数据结构线性表实验报告
- 数据结构实验报告线性表及其应用
- 数据结构实验报告-实验：1线性表的顺序存储和操作实现
- 数据结构_实验1_线性表的基本操作
- 数据结构实验指导书(C ) 线性表的操作
- 数据结构线性表实验报告
- 数据结构实验报告——线性表顺序存储结构[1]
- [信息与通信]贵州大学数据结构实验1-线性表及应用
- 数据结构实验报告-线性表
- 《数据结构》实验一 线性表及其应用
- 数据结构实验报告 线性表
- 数据结构线性表实验报告
- 数据结构实验_线性表基本操作
- (完整版)数据结构线性表的应用实验报告
- 数据结构实验C语言实现线性表
- 数据结构实验1
- 数据结构实验线性表基本操作
- 数据结构实验-线性表
- 数据结构实验指导(一)
- 数据结构实验线性表及其应用
- 数据结构实验报告——线性表