自学考试计算机系列课程
实践性环节实验报告本
课程名称数据结构
实验学期 2010 至 2011 学年第 2 学期
年级大三专业通信工程
学生姓名陈榕学号030409301749 指导教师涂风华
实验最终成绩
重庆大学计算机学院制
实验报告打印格式说明
1.标题:三号加粗黑体
2.开课实验室:5号加粗宋体
3.表中内容:
(1)标题:5号黑体
(2)正文:5号宋体
4.纸张:16开(20cm×2
5.5cm)
5.版芯
上距:2cm
下距:2cm
左距:2.8cm
右距:2.8cm
#include
单链表的创建、插入和删除 (数据结构) ——SVS #include
Status DeleteList_Link(LinkList L,int i,ElemType e) //删除链表{ LinkList q,p=L;int j=0; while(p->next&&j
数据结构实验报告全集 实验一线性表基本操作和简单程序 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.从键盘输入10个整数,产生顺序表,并输入结点值。 2.从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找 不到,则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 二、源程序及注释: #include
单链表的删除与插入源程序如下: #include
int i=0,j,m; linklist *s,*p; printf("请输入插入位置:"); scanf("%d",&j); printf("请输入需插入元素:"); scanf("%d",&m); s=L; while(i
单链表的初始化,建立,插入,查找,删除。 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; //单链表中的数据域
struct Node *next; //单链表的指针域 }Node,*LinkedList; //单链表的初始化 LinkedList LinkedListInit() { Node *L; L = (Node
*)malloc(sizeof(Node)); //申请结点空间 if(L == NULL) //判断是否有足够的内存空间 printf("申请内存空间失败\n"); L->next = NULL; //将next设置为NULL,初始长度为0的单链表return L; }
//单链表的建立1,头插法建立单链表 LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表
ElemType x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值
实验一顺序表的操作 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; }
数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间,决不构成对存储区的浪费。 链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表,下面将逐一介绍。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为N U L L。 图7 - 3还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。 看一下链表节点的数据结构定义: struct node { int num; struct node *p; } ; 在链表节点的定义中,除一个整型的成员外,成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中,非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步: 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表,将新节点连接到表头;若是非空表,将新 节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表,若有转到3 ),否则结束。 ?单链表的输出过程有以下几步 1) 找到表头。
实验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;
单链表的插入和删除实验日志 指导教师刘锐实验时间2010 年10 月11 日 学院数理专业数学与应用数学 班级学号姓名实验室S331-A 实验题目:单链表的插入和删除 实验目的:了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求:建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解程序(相关程序见附录) 。 2、调试程序,并设计输入字符串数据(如:aa, bb , cc , dd, ee,#),测试程序的如下功能: 不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 实验结果: 1、不允许重复字符串的插入功能结果如下:
3、删除和插入结点的功能如下:
心得体会: 通过这次实验我学会了单链表的建立和删除,基本了解了线性表的逻辑结构和链式存储结构,掌握了单链表的基本算法,使我受益匪浅。在调试程序的过程中,遇见了一系列的问题,后来在同学的帮助下,修改了几个语句后,终于把它给调试出来了。有时候一个标点符号的问题就可能导致程序无法运行。所以在分析调试程序的时候一定要仔细。 附加程序代码: 1、调试之后的程序如下(其中蓝色字体部分为修改过的): #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(); //函数,按值查找结点
typedef struct LNode//结点类型 { int data;//数值域 struct LNode *next;//指针域 }CrLNode,*CrLinklist; #include"Base.h" #include"construct.h" #include"circulate_operation.c" int main() { CrLinklist L; int i,choice,n,e; printf("请输入链表元素个数:"); scanf("%d",&n); L=Initlist_L(n); printf("请选择执行语句,选择输入1,执行插入操作或选择输入2,执行删除操作:"); scanf("%d",&choice); switch(choice) { case 1: { printf("请输入插入元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else printf("请输入插入元素的值:"); scanf("%d",&e); L=ListInsert_L(L,i,e); printf("插入后的链表为:"); printlist_L(L); };break; case 2: { printf("请输入删除元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else L=ListDelete_L(L,i); printf("删除后的链表为");
printlist_L(L); };break; } } CrLinklist Initlist_L(int n)//创建带头结点的单链表 { CrLinklist L; CrLinklist P; int i; L=(CrLinklist)malloc(sizeof(CrLNode)); L->next=L;/* 先建立一个带头结点的单链表*/ printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { P=(CrLinklist)malloc(sizeof(CrLNode)); /* 生成新结点*/ scanf("%d",&P->data); /* 输入元素值*/ P->next=L->next; /* 插入到表头*/ L->next=P; } return L; } CrLinklist ListInsert_L(CrLinklist L,int i,int e)//单链表的插入 { CrLinklist P,S; int j; P=L; j=0; while(P&&j
北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验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
. 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 二、要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 三、程序源代码 #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); //删除所有结点,释放内存 } //==========用尾插入法建立带头结点的单链表
实验报告:线性表的基本操作 实验1:实现顺序表各种基本运算的算法 一、实验目的 学会并运用顺序表存储结构及各种运算。 二、实验环境 VC++6.0 三、实验准备 (1) 复习课件中理论知识 (2)练习课堂所讲的例子 四、实验内容 编写一个程序实现SqList.cpp,实现顺序表基本运算,并在此基础上设计个主程序exp1.cpp,完成如下功能: (1)初始化顺序表L; (2)依次插入a、b、c、d、e元素; (3)输出顺序表L; (4)输出顺序表L长度; (5)判断顺序表L是否为空: (6)输出顺序表L的第3个元素; (7)输出元素a的位置; (8)在第4个位置上插入f元素; (9)输出顺序表L; (10)删除顺序表L的第3 个元素; (11)输出顺序表L; (12)顺序表L; 五、实验步骤 1、构造一个空的线形表并分配内存空间 Status InitList_Sql(SqList &L) {L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } 2、求线性表的长度 Status ListLength(SqList L) { return L.length; } 3、线性表清空 void ClearList(SqList &L){ L.length = 0; } 4、在顺序线形表 L 中第 i 个位置之前插入新的元素 e Status ListInsert_Sq(SqList &L,int i,ElemType e)
《数据结构》实验报告一 学院:班级: 学号:姓名: 日期:程序名 一、上机实验的问题和要求: 顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入10个整数,产生顺序表,并输入结点值。 2.从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找 不到,则显示“找不到”。 3.从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插 入在对应位置上,输出顺序表所有结点值,观察输出结果。 4.从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。 二、源程序及注释: #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
单链表的插入和删除实验报告
实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 二、要求: 建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 三、程序源代码 #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); //删除所有结点,释放内存 }
实验1 线性表的基本操作 一、实验目的 (1) 掌握线性表的逻辑特征; (2) 掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算; (3) 熟练掌握线性表的链式存储结构定义及基本操作; (4) 理解循环链表和双链表的特点和基本运算; (5 )加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力; 二、实验内容 1、创建有若干个元素(可以是整型数值)的顺序表,实现对顺序表的初始化,对已建立的顺序表插入操作、删除操作、遍历输出顺序表。 要求各个操作均以函数的形式实现,在主函数中调用各个函数实现以下操作: (1)从键盘上依次输入21、18、30、75、42、56,创建顺序表,并输出顺序表中的各元素值。 (2)分别在单链表的第3个位置插入67,给出插入成功或失败的信息,并输出此时顺序表中的各元素值。 (3)删除顺序表中的第6个数据元素,给出删除成功或失败的信息,并输出此时顺序表中的各元素值。 (4)查找顺序表中是否有75这个元素,如果有返回该元素在顺序表中的位序。 2、创建有若干个元素(可以是整型数值)的单链表,实现对单链表的初始化,对已建立的顺序表插入操作、删除操作、查找操作、遍历输出单链表表。 要求各个操作均以函数的形式实现,在主函数中调用各个函数实现以下操作: (1)从键盘上依次输入21、18、30、75、42、56,创建单链表,并输出单链表中的各元素值。 (2)分别在单链表的第4个位置,给出插入成功或失败的信息,并输出单链表中的各元素值。
(3)删除单链表中的第2个数据元素,给出删除成功或失败的信息,并输出单链表中的各元素值。 (4)查找顺序表中的第五个元素并输出该元素的值。 三、参考代码 (1) 顺序表的操作 #include
实验一顺序表的操作 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