数据结构实验报告实验0:顺序表与链表
专业:
班级:
姓名:
学号:
指导教师:
日期:
一、实验目的
(1)掌握顺序表的存储结构形式及其描述和基本运算的实。
(2)熟练掌握动态链表结构及有关算法的设计。
(3)掌握用链表表示特定形式的数据的方法,并能编写出有关运算的算法。
(4)理解单循环链表及双循环链表的特点。
二、实验内容
(1)顺序表的应用
(2)链表的应用
三、需求分析
1.输入的形式和输入值的范围
2.建立链表时输入的都是整数,输入0代表输入的结束,插入元素时需要输入插入的
位置和元素的值,删除元素时输入删除元素的值。
3.输出形式
4.所有操作在出现错误时都会有提示,并且在任意一个操作结束后都会输出操作后的
链表。
5.程序所能达到的功能
6.完成链表的生成,任意位置插入元素、删除,实现链表数据的排序,删除链表中相
同的元素,并且比较两个链表是否相等以及将两链表合成一个有序的链表。
7. 4.测试数据:见第八部分。
四、概要设计
实验一:
(1) 本程序包含的函数如下:
其中main函数负责操作其他的函数。
(2)各函数的功能设计为:
Creat(student & L):建立一个链表L(尾部插入建立的链表),并且返回这个链表的头指针。
find(student L,int e):在链表L中寻找一样元素e。
print(student L):依次输出链表 L 的内容。
insert(student & L):插入元素。
spilt(student & L):从后向前寻找奇数在偶数前的情况,如果一个奇数或偶数之后还是一个奇数和偶数,就让代表奇数和偶数的变量自增,在每次所有符合连续情况的奇偶数交换完成后,偶数要从新计数。
symmetry(student L):判断是否是对称的链表。
unite(student L1, student L2, Student & L3):将链表A和B合成一个非递减的链表,返回新链表的头指针.
五、详细设计
(1)结点类型和指针类型:
typedef struct
{
int *elem;//数组指针elem指示线性表的基地址。
int length;//线性表的当前实际长度。
int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位。
}student;
(2)单链表的基本操作
A.函数的算法:
A.Creat(student & L):建立一个链表L(尾部插入建立的链表),动态分配初始
大小的INT型空间。并且返回这个链表的头指针。
B.find(student L,int e):在链表L中寻找一样元素e,所有符合查找条件
的元素都设置其标志为flag=1。
C.print(student L):依次输出链表 L 的内容。
D.insert(student & L):插入元素。
E.spilt(student & L):从后向前寻找奇数在偶数前的情况,如果一个奇数或偶
数之后还是一个奇数和偶数,就让代表奇数和偶数的变量自增,在每次所有符合连
续情况的奇偶数交换完成后,偶数要从新计数。
F.symmetry(student L):判断是否是对称的链表。
G.unite(student L1, student L2, Student & L3):将链表A和B合成
一个非递减的链表,返回新链表的头指针.
六、调试分析
老师给出的代码加上网上借助了一些参考资料。主要就是将算法变成真正可用的函数。对称的那个功能用到了离散数学以前的知识点吧,额,也是一样根据算法写代码。奇数偶数自认觉得这个功能很新颖,但是分析后发现先计算出奇数偶数的个数,创建适当长度的链表进行。
七、使用说明
运行后会有以下的菜单:
八、测试结果
1 、建立单链表:
选择 1 ,11、12、13、14、15。得到单链表(11,12,13,14,15 )2 、遍历:
3、查找某一元素:
4、判断是否对称
5、将奇数排在偶数前
6、插入
7、合并有序表
8、退出
九、附录:部分代码
#include
#include
#define INIT_SIZE 5
#define ADD_SIZE 10
typedef struct
{
int *elem;//数组指针elem指示线性表的基地址。
int length;//线性表的当前实际长度。
int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位。
}student;
//创建单向无序链表
void Creat(student &L)
{
int go=1;//循环输入结点条件
L.elem=(int *)malloc(INIT_SIZE *sizeof(int));//动态分配初始大小的INT型空间。
L.listsize=INIT_SIZE;//把当前链表的存储袒赋值为链表动态分配的初始长度。
L.length=0;//链表的初始长度为0。
while(go==1)
{
if(L.length>=L.listsize)//如果所建链表长度超过当前分配的空间,则增加大小为初始增量的空间。
{
printf("\n所建链表长度超过当前分配的空间,将增加大小为初始增量的空间!\n");
L.elem=(int
*)realloc(L.elem,(L.listsize+ADD_SIZE)*sizeof(int));
L.listsize+=ADD_SIZE;
}
printf("请输入整数元素:");
scanf("%d",&L.elem[L.length]);//输入结点。
L.length++;
printf("\n继续创建操作请输入1,退出创建请输入0:");
scanf("%d",&go);
}
}
//遍历链表
void print(student L)
{
int i;
for(i=0;i printf("%d ",L.elem[i]); } //查找链表中某一元素 void find(student L,int e) { int i=0,flag=0,k=0; while(i { if(L.elem[i]==e) { if(k==0) { printf("\n在顺序表中找到该元素,位于第"); k=1; } flag=1;//所有符合查找条件的元素都设置其标志为flag=1; } if(flag==1)printf("%d,",i+1);//输出所有符合查找条件的元素的位置序号。 i++; } if(flag==1)printf("号位置!\n"); else printf("\n在该顺序表中找不到该元素!\n"); } //判断所建链表是否对称。 void symmetry(student L) { int i,ave; if(L.length==1)printf("\n该顺序表中仅有一个元素!\n"); else { ave=L.length/2;//使ave的值为链表的中间变量,作为循环结束条件。 for(i=0;i { if(L.elem[i]!=L.elem[L.length-i-1])//判断链表中前后交替结点是否相等, { printf("\n该顺序表为非对称表!\n");//如果在循环过程中出现不相等的情况, break;//即可判断此链表是一非对称表。 } else if(i=ave-1)printf("\n该顺序表为对称表!\n");//否则如果一直到最后都相等,则是对称链表。 } } } //奇数排在偶数之前 void split(student &L) { int temp,i,m=0,n,c,b,JShu=0,OShu=0;//i代表各元素所在位置的序号 for(i=L.length-1;i>=0;)//从后向前寻找奇数在偶数前的情况,如果一个奇数或偶数之后还是一个奇数和偶数, { OShu=0;//就让代表奇数和偶数的变量自增,在每次所有符合连续情况的奇偶数交换完成后,偶数要从新计数。 while((L.elem[i]%2)!=0&&(i>=0)) { JShu++; i--; }//此循环从后往前查找奇数,直到遇到一个偶数结束, while((L.elem[i]%2)==0&&(i>=0)) { m=i+1; OShu++; i--; }//此循环从后往前查找偶数,直到遇到一个奇数结束 if((L.elem[i]%2)!=0)//如果一器奇数在偶数之前,交换它们,使这一串奇数位于偶数之前。 { n=i+1;//此处的n值是根据实例推测出来就等于序号加1. if(JShu<=OShu)//如果这一串奇数的数量于位于其前面的一串偶数个数,就只交换奇数数量的数据。 for(b=0;b { temp=L.elem[n]; L.elem[n]=L.elem[n+OShu];//n+OShu也是根据实例推出来的。 L.elem[n+OShu]=temp; n++; } else//否则就交换偶数数量的元素,即以最少操作达到所有奇数排在所有偶数之前的目的。 { n=i+1; for(b=0;b { c=i+OShu+JShu; temp=L.elem[c]; L.elem[c]=L.elem[n]; L.elem[n]=temp; c--; n++; } } } } } //插入函数 void insert(student &L) int e,i,j,go=1; while(go==1) { if(L.length==0)//长度为0即是顺序表未创建任何元素,应首先创建。 { printf("\n顺序表中尚未有任何元素,请输入元素创建顺序表。\n"); Creat(L); } else { if(L.length>=L.listsize)//如果所建链表长度超过当前分配的空间,则增加大小为初始增量的空间。 { printf("\n所建链表长度超过当前分配的空间,将增加大小为初始增量的空间!\n"); L.elem=(int *)realloc(L.elem,(L.listsize+ADD_SIZE)*sizeof(int)); L.listsize+=ADD_SIZE; } printf("\n请输入要插入的元素:");scanf("%d",&e); i=0;//i值初始化为0使对比从顺序表第一个元素开始。 while(L.elem[i] i++; if(L.elem[i]>=e)//使最后一个元素参与此处的对比判断 { for(j=L.length;j>i;j--)//如果符合条件,则第i个元素及其以后的元素的值顺序后移,以腾出第i个位置 L.elem[j]=L.elem[j-1]; L.elem[i]=e;//以便能成功插入新的元素。 } else L.elem[i+1]=e;//假如顺序表中没有元素比新元素大,就把新元素插入到表尾。 L.length++; } printf("\n继续插入操作请输入1,中止请输入0。");scanf("%d",&go); } } //合并顺序表(非递减合并到非递减) void unite(student L1,student L2,student &L3) { int i=0,j=0,k=0; L3.length=0; L3.elem=(int *)malloc(L1.length+L2.length *sizeof(int)); L3.listsize=L1.length+L2.length; while(i { if(L1.elem[i]<=L2.elem[j]) { L3.elem[k]=L1.elem[i]; L3.length++; i++; k++; } else { L3.elem[k]=L2.elem[j]; L3.length++; j++; k++; } } while(i { L3.elem[k]=L1.elem[i]; i++; k++; L3.length++; } while(j { L3.elem[k]=L2.elem[j]; j++; k++; L3.length++; } } //主函数 void main() { student L,L1,L2,L3; L.length=0; L.listsize=0; L1.length=L1.listsize=0; L2.length=L2.listsize=0; int number,e; printf("\n *************欢迎进入链表操作系统,请选择操作 ************************"); printf("\n 1.创建顺序表"); printf("\n 2.遍历顺序表"); printf("\n 3.在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0"); printf("\n 4.判断该顺序表中元素是否对称,对称返回1,否则返回0"); printf("\n 5.把顺序表中所有奇数排在偶数之前"); printf("\n 6.输入整型元素序列利用有序表插入算法建立一个有序表"); printf("\n 7.利用算法6建立两个非递减表,并合并成非递减表"); printf("\n 8.退出"); printf("\n ***************************************************************** *\n"); printf("\n请输入选择序号:");scanf("%d",&number); while(number!=8) { switch(number) { case 1:Creat(L); break; case 2:print(L); break; case 3:printf("\n请输入要查找的元素:");scanf("%d",&e); find(L,e); break; case 4:symmetry(L); break; case 5:split(L); printf("\n调换奇偶数元素的位置后的顺序表如下:\n"); print(L); break; case 6:insert(L); break; case 7:printf("\n利用算法6创建表L1.\n"); insert(L1); printf("\n利用算法6创建的表L1如下:\n"); print(L1); printf("\n利用算法6创建表L2.\n"); insert(L2); printf("\n利用算法6创建的表L2如下:\n"); print(L2); printf("\n正在合并表L1和表L2……\n"); unite(L1,L2,L3); printf("\n表L1和表L2合并后的表L3如下:\n"); print(L3); break; case 8: break; } printf("\n继续操作请输入1~7之间的数字,退出请输入8:"); scanf("%d",&number); } } 2014-2015学年第一学期实验报告 课程名称:算法与数据结构 实验名称:城市链表 一、实验目的 本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉各种链表的操作为侧重点。同时,通过本次实验帮助学生复习高级语言的使用方法。 二、实验内容 (一)城市链表: 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 (二) 约瑟夫环 m 的初值为20;密码:3,1,7,2,6,8,4(正确的结果应为6,1,4,7,2,3,5)。三、实验环境 VS2010 、win8.1 四、实验结果 (一)城市链表: (1)创建城市链表; (2)给定一个城市名,返回其位置坐标; (3)给定一个位置坐标P 和一个距离D,返回所有与P 的距离小于等于 D 的城市。 (4)在已有的城市链表中插入一个新的城市; (5)更新城市信息; (6)删除某个城市信息。 (二) 约瑟夫环 m 的初值为20;密码:3,1,7,2,6,8,4 输出6,1,4,7,2,3,5。 五、附录 城市链表: 5.1 问题分析 该实验要求对链表实现创建,遍历,插入,删除,查询等操作,故使用单链表。 5.2 设计方案 该程序大致分为以下几个模块: 1.创建城市链表模块,即在空链表中插入新元素。故创建城市链表中包涵插入模块。 2.返回位置坐标模块。 3.计算距离模块 4.插入模块。 5.更新城市信息模块 6.删除信息模块。 5.3 算法 5.3.1 根据中心城市坐标,返回在距离内的所有城市: void FindCityDistance(citylist *L){ //根据距离输出城市 ……//输入信息与距离 L=L->next; w hile(L != NULL){ if(((L->x-x1)*(L->x-x1)+(L->y-y1)*(L->y-y1 )<=dis*dis)&&(((L->x-x1)+(L->y-y1))!=0 )){ printf("城市名称%s\n",L->Name); printf("城市坐标%.2lf,%.2lf\n",L->x,L->y); } L=L->next; } } 该算法主要用到了勾股定理,考虑到不需要实际数值,只需要大小比较,所以只用 横坐标差的平方+纵坐标差的平方<= 距离的平方判定。 C语言程序设计实验报告 实验一:链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境:当前所有电脑硬件环境均支持 2.软件环境:Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四.程序流程图 五.程序代码 #include r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(j 线性表实验报告 一、实验的目的要求 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请输入要插入元素的值:"); 数据结构实验报告 班级姓名同组者/ 成绩 日期2020.3.25指导教师 实验名称线性表及其应用 一、实验目的: 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作(建立、插入、删除、遍历等)在顺序、链式存储上的实现。 3、加深对C/C++、Java等编程语言的相关知识点的理解(如结构体/类、指针/引用、函数/方法、 引用参数等)。 二、实验内容: 1、 题目 根据给定的整型数组,以尾插法建立一个单链表,并实现以下操作: ①查找:输入一个欲查找的整数,找到则显示第一个相匹配的整数在单链表中所处的位置,若不存在,则显示提示信息。 ②删除:输入一个欲删除的整数e,若存在则在单链表中删除第一个值为e的元素。 ③插入:输入一个欲插入位置i和欲插入元素e,将e插入到第i个整数之前(注意i的合法性)。 源码 #include { linklist head,r,p;// 定义头指针r,p,指针 int x,i; head=(node *)malloc(sizeof(node));// 生成头结点 r=head;//r指向头结点 printf(" 输入数字:\n"); for(i=n;i>0;i--)//for循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;// 返回头指针 } void output (linklist head) //输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); 计算机与信息技术学院综合性、设计性实验报告 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法,模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备:CPU为Pentium 4 以上的计算机,内存2G以上 (2)配置软件:Microsoft Windows 7 与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理: 单链表属于线性表,线性表的存储结构的特点是:用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。因此,对于某个元素来说,不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。 设计方案: 采用模块化设计的方法,设计各个程序段,最终通过主函数实现各个程序段的功能。设计时,需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。 设计流程: 1. 引入所需的头文件; 2. 定义状态值; 3. 写入顺序表的各种操作的代码; 写入主函数,分别调用各个函数。在调用函数时,采用if结构进行判断输 入值是否非法,从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include 北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验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 实验报告 2012 ——2013 学年第 1 学期 实验课程数据结构与算法学生姓名 实验项目线性表的顺序存储学院计算机科学技术 实验性质班级学号 实验地点同组人数第组 实验日期第周星期第节 成绩 环境参数 一、实验目的及要求 二、实验原理、实验内容 三、实验仪器设备及材料 四、操作方法与实验步骤 五、实验数据记录及处理 六、实验结果分析及讨论 一、实验目的 1.掌握用Visual C++6.0上机调试单链表的基本方法 2.掌握单链表的插入、删除、查找、求表长以及有序单链表的逆序算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点并用指针p指示,然后申请一个由指针s 指示的结点空间,并置x为其数据域值,最后修改第i-1个结点,并使x结点的指针指向第i个结点,要在带头结点的单链表h中删除第i个结点,首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点,然后删除第i个结点并释放被删除结点空间。 [基本要求]用链式存储结构实现存储 [实现提示]链式存储结构不是随机存储结构,即不能直接取到单链表中某个结点,而要从单链表的头结点开始一个一个地计数寻找。 三、实验步骤 1、定义节点类型 2、进行单链表的初始化 3、查看初始化的单链表 4、使用switch-case结构进行选择操作 5、采用递归,使选择操作可以持续进行 四、实验代码 #include 链表实验报告 ————————————————————————————————作者: ————————————————————————————————日期: 《数据结构》实验报告二 系别:嵌入式系统工程系班级:嵌入式11003班 学号:11160400314姓名:孙立阔 日期:2012年4月9日指导教师:申华 一、上机实验的问题和要求: 单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个字符,产生不带表头的单链表,并输入结点值。 2.从键盘输入1个字符,在单链表中查找该结点的位置。若找到,则显示“找到了”;否则, 则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出单链表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出单链表所有结点值,观察输出结果。 5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结 点值,观察输出结果。 6.删除其中所有数据值为偶数的结点,输出单链表所有结点值,观察输出结果。 7.(★)将单链表分解成两个单链表A和B,使A链表中含有原链表中序号为奇数的元素, 而B链表中含有原链表中序号为偶数的元素,且保持原来的相对顺序,分别输出单链表A和单链表B的所有结点值,观察输出结果。 二、程序设计的基本思想,原理和算法描述: (包括程序的结构,数据结构,输入/输出设计,符号名说明等) 创建一个空的单链表,实现对单链表的查找,插入,删除的功能。 三、源程序及注释: #defineOK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 实验一:线性表逆置(顺序表)实验报告 (一)问题的描述: 实现顺序表的逆置算法 (二)数据结构的设计: 顺序表是线性表的顺序存储形式,因此设计如下数据类型表示线性表: typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; (三)函数功能、参数说明及概要设计: 1.函数Status InitList(SqList *L) 功能说明:实现顺序表L的初始化 算法设计:为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明:返回顺序表L长度 算法设计:返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明:将元素e插入到顺序表L中的第i个节点 算法设计:判断顺序表是否已满,已满则加空间,未满则继续,将元素e插入到第i个元素之前,并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明:依次对L的每个数据元素调用函数vi() 算法设计:依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明:实现顺序表L的逆置 算法设计:用for循环将顺序表L中的第i个元素依次与第(i+length)个元素交换6.函数void print(ElemType *c) 功能说明:打印元素c 算法设计:打印元素c 2. (四)具体程序的实现 实验报告 课程名称:数据结构 题目:链表实现多项式相加 班级: 学号: 姓名: 完成时间:2012年10月17日 1、实验目的和要求 1)掌握链表的运用方法; 2)学习链表的初始化并建立一个新的链表; 3)知道如何实现链表的插入结点与删除结点操作; 4)了解链表的基本操作并灵活运用 2、实验内容 1)建立两个链表存储一元多项式; 2)实现两个一元多项式的相加; 3)输出两个多项式相加后得到的一元多项式。 3、算法基本思想 数降序存入两个链表中,将大小较大的链表作为相加后的链表寄存处。定义两个临时链表节点指针p,q,分别指向两个链表头结点。然后将另一个链表中从头结点开始依次与第一个链表比较,如果其指数比第一个小,则p向后移动一个单位,如相等,则将两节点的系数相加作为第一个链表当前节点的系数,如果为0,则将此节点栓掉。若果较大,则在p前插入q,q向后移动一个,直到两个链表做完为止。 4、算法描述 用链表实现多项式相加的程序如下: #include void add_node(struct node*h1,struct node*h2); void print_node(struct node*h); struct node*init_node() { struct node*h=(struct node*)malloc(sizeof(struct node)),*p,*q; int exp; float coef=1.0; h->next=NULL; printf("请依次输入多项式的系数和指数(如:\"2 3\";输入\"0 0\"时结束):\n"); p=(struct node*)malloc(sizeof(struct node)); q=(struct node*)malloc(sizeof(struct node)); for(;fabs(coef-0.0)>1.0e-6;) { scanf("%f %d",&coef,&exp); if(fabs(coef-0.0)>1.0e-6) { q->next=p; p->coef=coef; p->exp=exp; p->next=NULL; add_node(h,q); } } free(p); free(q); return(h); } void add_node(struct node*h1,struct node*h2) { struct node*y1=h1,*y2=h2; struct node*p,*q; y1=y1->next; y2=y2->next; for(;y1||y2;) if(y1) { if(y2) { if(y1->exp 链表实验报告 一、实验名称 链表操作的实现--学生信息库的构建 二、实验目的 (1)理解单链表的存储结构及基本操作的定义 (2)掌握单链表存储基本操作 (3)学会设计实验数据验证程序 【实验仪器及环境】计算机 Window XP操作系统 三、实验内容 1、建立一个学生成绩信息(学号,姓名,成绩)的单链表,按学号排序 2、对链表进行插入、删除、遍历、修改操作。 3、对链表进行读取(读文件)、存储(写文件) 四、实验要求 (1)给出终结报告(包括设计过程,程序)-打印版 (2)对程序进行答辩 五、实验过程、详细内容 1、概念及过程中需要调用的函数 (1)链表的概念结点定义 结构的递归定义 struct stud_node{ int num; char name[20]; int score; struct stud_node *next; }; (2)链表的建立 1、手动输入 struct stud_node*Create_Stu_Doc() { struct stud_node *head,*p; int num,score; char name[20]; int size=sizeof(struct stud_node); 【链表建立流程图】 2、从文件中直接获取 先建立一个 (3)链表的遍历 (4 )插入结点 (5)删除结点 (6)动态储存分配函数malloc () void *malloc(unsigned size) ①在内存的动态存储区中分配一连续空间,其长度为size ②若申请成功,则返回一个指向所分配内存空间的起始地址的指针 ③若申请不成功,则返回NULL (值为0) ④返回值类型:(void *) ·通用指针的一个重要用途 ·将malloc 的返回值转换到特定指针类型,赋给一个指针 【链表建立流程图】 ptr ptr ptr->num ptr->score ptr=ptr->next head pt r s s->next = ptr->next ptr->next = s 先连后断 ptr2=ptr1->next ptr1->next=ptr2->next free (ptr2) 一.实验名称 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) . 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 二、要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 三、程序源代码 #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表 ListNode *LocateNode(); //函数,按值查找结点 void DeleteList(); //函数,删除指定值的结点void printlist(); //函数,打印链表中的所有值 void DeleteAll(); //函数,删除所有结点,释放内存 //==========主函数============== void main() { char ch[10],num[10]; LinkList head; head=CreatListR1(); //用尾插入法建立单链表,返回头指针printlist(head); //遍历链表输出其值 printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //输入要删除的字符串 DeleteList(head,ch); printlist(head); } DeleteAll(head); //删除所有结点,释放内存 } //==========用尾插入法建立带头结点的单链表 实验2 链表基本操作实验 一、实验目的 1. 定义单链表的结点类型。 2. 熟悉对单链表的一些基本操作和具体的函数定义。 3. 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如:单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表(带头结点)结点为结构类型,结点值为整型。 要求: 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作,其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 ...... 2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除: p->next=p->next->next; 四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验,自己的编程能力有了进一步的提高,认识到自己以前在思考一个问题上思路不够开阔,不能灵活的表达出自己的想法,虽然在打完源代码之后出现了一些错误,但是经过认真查找、修改,最终将错误一一修正,主要是在写算法分析的时候出现了障碍,经过从网上查找资料,自己也对程序做了仔细的分析,对单链表创建、插入、删除算法画了详细的N-S流程图。 实验2 链表基本操作实验 一、实验目的 1. 定义单链表的结点类型。 2. 熟悉对单链表的一些基本操作和具体的函数定义。 3. 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验容与要求 该程序的功能是实现单链表的定义和主要操作。如:单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表(带头结点)结点为结构类型,结点值为整型。 要求: 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作,其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除: p->next=p->next->next; 四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验,自己的编程能力有了进一步的提高,认识到自己以前在思考一个问题上思路不够开阔,不能灵活的表达出自己的想法,虽然在打完源代码之后出现了一些错误,但是经过认真查找、修改,最终将错误一一修正,主要是在写算法分析的时候出现了障碍,经过从网上查找资料,自己也对程序做了仔细的分析,对单链表创建、插入、删除算法画了详细的N-S流程图。 实验报告 实验一线性表 实验目的: 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); 大学数据结构实验报告 课程名称数据结构实验第(四)次实验实验名称链表的基本操作 学生姓名于歌专业班级学号 实验成绩指导老师(签名)日期2018年10月01日 一、实验目的 1. 学会定义单链表的结点类型,实现对单链表的一些基本操作和具体 的函数定义,了解并掌握单链表的类定义以及成员函数的定义与调用。 2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。 二、实验要求 1.预习C语言中结构体的定义与基本操作方法。 2.对单链表的每个基本操作用单独的函数实现。 3.编写完整程序完成下面的实验内容并上机运行。 4.整理并上交实验报告。 三、实验内容: 1.编写程序完成单链表的下列基本操作: (1)初始化单链表La (2)在La中插入一个新结点 (3)删除La中的某一个结点 (4)在La中查找某结点并返回其位置 (5)打印输出La中的结点元素值 (6)清空链表 (7)销毁链表 2 .构造两个带有表头结点的有序单链表La、Lb,编写程序实现将La、 Lb合并成一个有序单链表Lc。 四、思考与提高: 1.如果上面实验内容2中合并的表内不允许有重复的数据该如何操作? 2.如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点?五、实验设计 1.编写程序完成单链表的下列基本操作: (1)初始化单链表La LinkList InitList() { int i,value,n; LinkList H=(LinkList)malloc(sizeof(LNode)); LinkList P=H; P->next=NULL; do{ printf("请输入链表的长度:"); scanf("%d",&n); if(n<=0) printf("输入有误请重新输入!\n"); }while(n<=0); printf("请输入各个元素:\n"); for(i=0; i 单链表实验报告 ————————————————————————————————作者:————————————————————————————————日期: 计算机与信息技术学院综合性、设计性实验报告 专业:网络工程年级/班级:大二 2016—2017学年第一学期 课程名称数据结构指导教师李四 学号姓名16083240XX 张三 项目名称单链表的基本操作实验类型综合性/设计性实验时间2017.10.3 实验地点216机房 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法,模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备:CPU为Pentium 4以上的计算机,内存2G以上 (2)配置软件:Microsoft Windows 7与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理: 单链表属于线性表,线性表的存储结构的特点是:用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。因此,对于某个元素来说,不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。 设计方案: 采用模块化设计的方法,设计各个程序段,最终通过主函数实现各个程序段的功能。设计时,需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。 设计流程: 1.引入所需的头文件; 2.定义状态值; 3.写入顺序表的各种操作的代码; 写入主函数,分别调用各个函数。在调用函数时,采用if结构进行判断输入值是否非法,从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include<stdio.h>// EOF(=^Z或F6),NULL #include<stdlib.h> // srand(),rand(),exit(n) #include<malloc.h> // malloc( ),alloc( ),realloc()等 #include城市链表实验报告
链表实验报告
线性表实验报告
数据结构线性表单链表实验报告
单链表实验报告
数据结构实验一题目一线性表实验报告
线性链表实验报告
链表实验报告
线性表逆置(顺序表)实验报告
链表实现多项式相加实验报告
C语言链表实验报告
线性表实验报告
单链表的插入和删除实验报告
链表基本操作实验报告
链表基本操作实验报告
数据结构线性表实验报告
链表的基本操作-数据结构实验报告
单链表实验报告