线性表的抽象数据类型的实现实验报告
数据结构实验报告
实验名称：线性表的抽象数据类型的实现
计算机与信息学院
实验1线性表的抽象数据类型的实现
实验目的
1.掌握线性表的顺序存储结构和链式存储结构；
2.熟练掌握顺序表和链表基本算法的实现；
3.掌握利用线性表数据结构解决实际问题的方法和
基本技巧；
4.按照实验题目要求独立正确地完成实验内容（编
写、调试算法程序，提交程序清单及及相关实验
数据与运行结果）；
5.按时提交实验报告。
实验环境
计算机、C语言程序设计环境
实验学时
2学时，选做实验。
实验内容
一、顺序表的基本操作实现实验
要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：
①创建任意整数线性表（即线性表的元素值随机在
键盘上输入），长度限定在20之内；
②打印（遍历）该线性表（依次打印出表中元素值）；
③在线性表中查找第i个元素，并返回其值；
④在线性表中第i个元素之前插入一已知元素；
⑤在线性表中删除第i个元素；
⑥求线性表中所有元素值（整数）之和；
实验步骤
C源程序代码
/*file:seqlist.cpp*/
#include
#include
#include
#define size 20
#define elemtype int
struct seqlist
{ elemtype elem[size];
int last;
};
void menu()
{ printf("\n..........................................");
printf("\n0.退出操作................................");
printf("\n1.建立数据类型为整形的顺序表（长度小于20).");
printf("\n2.打印线性表..............................");
printf("\n3.在线性表中查找第i个元素，并返回其值.....");
printf("\n4.在线性表中第i个元素之前插入一已知元素...");
printf("\n5.在线性表中删除第i个元素.................");
printf("\n6.求线性表中所有元素值（整数）之和........");
printf("\n7.初始化..................................\n");
void ins(seqlist *L)
{L->last=-1;}
void creat(seqlist *L)
{ int i=0; elemtype j;
printf("请输入线性表元素(-1结束):");
scanf("%d",&j);
while(j!=-1)
{ L->elem[i++]=j; L->last++;
if(i>size-1) break;
scanf("%d",&j);
}
}
void print(seqlist *L)
{ int i;
printf("顺序表中元素为:");
for(i=0;i<=L->last;i++)
printf("%d\t",L->elem[i]);
}
int find(seqlist *L,int i)
{ if(i<1||i>L->last+1) return 0;
else return(L->elem[i-1]);
int insert(seqlist *L,int i,int x)
{ int j;
if(L->last+1==size||i<1||i>L->last+2) return 0;
L->last++;
for(j=L->last;j>=i-1;j--)
L->elem[j+1]=L->elem[j];
L->elem[i-1]=x;
return 1;
}
int del(seqlist *L,int i)
{ int e,j;
if(L->last==-1||i<1||i>L->last+1)
return 0;
else
e=L->elem[i-1];
for(j=i;j<=L->last+1;j++)
L->elem[j-1]=L->elem[j];
L->last--; return 1;
}
int sum(seqlist *L)
{ int i=0,s=0;
if(L->last==-1) return 0;
for(i=0;i<=L->last;i++) s+=L->elem[i];
return s;
}
int isempty(seqlist *L)
{ if(L->last==-1)
return 1;
else return 0;
}
void main()
{ int i,cz,e; elemtype date; seqlist L;
menu();
printf("请输入你要执行的操作的序号:");
i=scanf("%d",&cz);
while(1)
{ if(!i) printf("只能输入数值");
else break;
printf("\n再输入一次："); rewind(stdin);
i=scanf("%d",&cz);
}
while(cz)
{ switch(cz)
{ case 1:
if(isempty(&L))
{ ins(&L); c reat(&L); }
else printf("表已经存在，先清空再进行此操作！\n");
break;
case 2:
if(isempty(&L))
printf("表为空\n");
else print(&L);
break;
case 3:
printf("输入待查找元素的位置:\n");
scanf("%d",&i);
if(find(&L,i))
printf("查找的第%d个元素为%d\n",i,find(&L,i));
else
printf("查找位置错误\n");
break;
case 4:
printf("请输入要插入的元素及位置:\n");
scanf("%d",&date);
scanf("%d",&i);
if(insert(&L,i,date))
printf("插入元素成功!\n");
else printf("插入位置不合法或栈已满!\n");
break;
case 5:
printf("请输入要删除元素的位置\n");
scanf("%d",&i);
e=L.elem[i-1];
if(del(&L,i))
{ printf("删除第%d个值为%d的元素\n",i,e);
printf("删除成功\n");
}
Else printf("删除位置不合法或表已空\n");
break;
case 6:
if(isempty(&L))
printf("表已空!\n");
else printf("线性表中所有元素值（整数）和:%d\n",sum(&L));
break;
case 7: ins(&L);break;
default: printf("无此操作!\n");break;
}
menu();
printf("请输入你要执行的操作的序号:");
i=scanf("%d",&cz);
while(1)
{ if(!i) printf("\n只能输入数值");
else break;
printf("\n再输入一次："); rewind(stdin);
i=scanf("%d",&cz);
}
}
}
测试数据与实验结果
7.初始化
1.建表
2.打印
3.查找
4.插入不合法长度超过20
5.删除然后打印
4~.插入合法
6.求和
二、链表（带头结点）基本操作实验
要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：
①创建任意字符型有序（递增排序）单循环链表（即
链表的字符元素随机在键盘上输入），长度限定在
15之内；
②打印（遍历）该链表（依次打印出表中元素值）；
③在链表中查找第i个元素，i合法返回元素值，否
则，返回FALSE；
④在链表中查找与一已知字符相同的第一个结点，
有则返回TRUE，否则，返回FALSE；
⑤在链表中按照有序方式插入一已知字符元素；
⑥在线性表中删除第i个结点；
⑦计算链表的长度。
实验步骤
C源程序代码
#include
#include
#include
#define elemtype char
#define size 15
static int n=0;
typedef struct Node
{
elemtype data;
struct Node * next;
}Node,*linklist;
void init(linklist *L)
{
*L=(linklist)malloc(sizeof(Node));
(*L)->next=*L;
n=0;
}
void creat(linklist L)
{
int i=0,j;
Node *s,*r;
elemtype c[size],t;
r=L->next;
printf("请输入字符型元素(最多15个,输入字符'@'结束):");
scanf("%s",c);
while(c[i]!='@')
{
n++;
i++;
}
i=0;
for(i=0;i { for(j=i;j { if(c[j] {t=c[j];c[j]=c[j+1];c[j+1]=t;} } } for(i=0;i { t=c[i]; s=(Node *)malloc(sizeof(Node)); s->data=t; r->next=s; r=s; } } void length(linklist L) { printf("链表长度为:%d",n); } void show(linklist L) { int j; Node *p; p=L; if(!p) {printf("表为空!");return;} for(j=0;j { printf("%c",p->next->data); p=p->next; } } int isempty(linklist L) { Node *pre; pre=L; if(pre->next==L) return 1; return 0; } void find4(linklist L,int i) { int j=0; Node *p; if(i<1||i>size) printf("查找位置错误!"); p=L; while(j { p=p->next; ADT Rational { //起名要易懂 数据对象：D={e1,e2|e1,e2∈Z,e2≠0} //分母不为零 数据关系：R={ Status InitRational(Rational &Q,ElemType v1, ElemType v2){ //构造有理数Q，分子分母分别为v1,v2，若v2=0则Q赋空，返回Error if(v2==0){Q=NULL;return ERROR;} /*return后括号可有可无*/ Q=(ElemType *)malloc(2*sizeof(ElemType)); //莫忘malloc.h if(!Q)exit(OVERFLOW);//分配存储空间失败, stdlib.h,注意!及适用场合用法Q[0]=v1;Q[1]=v2; /*之前的else可省略，若不省略最好加花括号*/ return(OK); } Status DestroyRational(Rational &Q) //销毁有理数Q { if(Q) { free(Q); Q=NULL; return OK; } } void OutputRational(Rational Q){ //以分数形式输出有理数Q if(!Q)printf(“the rational does not exist! \n‘); printf(“ %d/%d ”,Q[0],Q[1]); } 第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间： 线性表实验报告 一、实验的目的要求 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 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include 数据结构与算法 实验报告 实验一：线性表操作实验 —用循环链表实现约瑟夫环问题 姓名：沈靖雯 学号：2014326601094 班级：14信科二班 二〇一六年十月 实验一 线性表操作实验 【实验内容】 实现线性表的初始化和插入删除操作 提高部分实验：用循环链表实现约瑟夫环问题 【实验目的】 掌握线性表的顺序映象和链式映象方式，能熟练掌握链表结构的使用。 【问题描述】 一个旅行社要从n 个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m( 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验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 抽象数据类型线性表的定义如下： ADT List { 数据对象：D={ a i | a i∈ElemSet, i =1, 2, ……, n, n≥0} 数据关系：R1 = { < a i-1 , a i > | a i-1 , a i ∈D, i =2, ……, n } 基本操作： InitList (&L ) 操作结果：构造一个空的线性表L 。 DestoryList (&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ClearList (&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty (L) 初始条件：线性表L已存在。 操作结果：若L 为空表，则返回TRUE，否则返回FALSE。 ListLength (L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem ( L, i, &e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。 操作结果：用e返回L中第i个数据元素的值。 LocateElem ( L,e, compare() ) 初始条件：线性表L已存在，compare()是判定函数。 操作结果：返回L中第1个与e满足关系compare() 的数据元素的位序。若这样的数据元素不存在，则返 回值0。 PriorElem ( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素且不是第1个， 则用pre_e返回它的前驱，否则操作失败。 NextElem ( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素且不是最后一个， 则用next_e返回它的后继，否则操作失败。 ListInsert ( &L, i, e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e， L的长度加1。 ListDelete( &L, i, &e ) 初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值， 实验一：线性表逆置（顺序表）实验报告 （一）问题的描述： 实现顺序表的逆置算法 （二）数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： 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. （四）具体程序的实现 一．实验名称 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) 实验报告 实验一线性表 实验目的： 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) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立 的基本操作。 2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现 顺序表插入的基本操作。 3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9， 实现顺序表的删除的基本操作。 2.单链表的实践 3.1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链 表建立的基本操作。 2) 将该单链表的所有元素显示出来。 3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插 入的基本操作。 4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置 （如i=2）删除一个结点，实现单链表删除的基本操作。 5) 实现单链表的求表长操作。 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了刚创 建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 1、#include "stdio.h" #include "malloc.h" #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; } SqList; Status InitList( SqList &L ) { int i,n; L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType)); if (!L.elem) return(OVERFLOW); printf("输入元素的个数:"); scanf("%d",&n); printf("输入各元素的值:"); for(i=0;i 实验一抽象数据类型的表示与实现 一．实验目的及要求 （1）熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现； （2）理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）； （3）认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。 二．实验内容 （1）编程实现对一组从键盘输入的数据，计算它们的最大值、最小值等，并输出。 要求：将计算过程写成一个函数，并采用引用参数实现值的求解。 （2）编程实现抽象数据类型三元组的定义、存储和基本操作，并设计一个主菜单完成各个功能的调用。 三．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现对一组从键盘输入的数据，计算它们的最大值、最小值等，并输出。 要求：将计算过程写成一个函数，并采用引用参数实现值的求解。 程序代码部分： 头文件： #define N 10000 void comparason(double a[],int n,double &max,double &min); 主函数： #include"" #include"" int main() { int n; printf("请输入数据个数\n"); scanf("%d",&n); double a[N],max,min; int i; printf("请输入数据（空格隔开）\n"); for(i=0;i 实验报告 实验二线性表及其基本操作实验(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 数据结构实验报告 实验名称：线性表的抽象数据类型的实现 学号：2011129127 姓名：刘瑞奇 指导老师：解德祥 计算机与信息学院 实验1线性表的抽象数据类型的实现 实验目的 1.掌握线性表的顺序存储结构和链式存储结构； 2.熟练掌握顺序表和链表基本算法的实现； 3.掌握利用线性表数据结构解决实际问题的方法和基本技巧； 4.按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程 序清单及及相关实验数据与运行结果）； 5.按时提交实验报告。 实验环境 计算机、C语言程序设计环境 实验学时 2学时，选做实验。 实验内容 一、顺序表的基本操作实现实验 要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）： ①创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在 20之内； ②打印（遍历）该线性表（依次打印出表中元素值）； ③在线性表中查找第i个元素，并返回其值； ④在线性表中第i个元素之前插入一已知元素； ⑤在线性表中删除第i个元素； ⑥求线性表中所有元素值（整数）之和； 实验步骤 C源程序代码 /*file:seqlist.cpp*/ #include 专题1 数据结构分类与抽象数据类型 1.1 数据结构分类 数据结构讨论现实世界和计算机世界中的数据及其相互之间的联系，这体现在逻辑和存储两个层面上，相应称之为逻辑结构和存储结构。也就是说，在现实世界中讨论的数据结构是指逻辑结构，在计算机世界中讨论的数据结构是指存储结构，又称为物理结构。 数据的逻辑结构总体上分为4种类型：集合结构、线性结构、树结构和图结构。数据的存储结构总体上也分为4种类型：顺序结构、链接结构、索引结构和散列结构。原则上，一种逻辑结构可以采用任一种存储结构来存储（表示）。 对于现实世界中的同一种数据，根据研究问题的角度不同，将会选用不同的逻辑结构；对于一种逻辑结构，根据处理问题的要求不同，将会选用不同的存储结构。 对于复杂的数据结构，不论从逻辑层面上还是从存储层面上看，都可能包含有多个嵌套层次。如假定一种数据结构包含有两个层次，第一层（顶层）的逻辑结构可能是树结构，存储结构可能是链接结构；第二层（底层）的逻辑结构可能是线性结构，存储结构可能是顺序结构。第一层结构就是数据的总体结构，第二层结构就是第一层中数据元素的结构。 数据的逻辑结构通常采用二元组来描述，其中一元为数据元素的集合，另一元为元素之间逻辑关系的集合，每一个逻辑关系是元素序偶的集合，如 #include 第3章抽象数据类型的实现 3.1 实验概要 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 实验计划学时: 6 3.2 实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 3.3 预习与参考 1．确定要实现的抽象数据类型，并对基本操作做适当的选取和增加； 2．选择存储结构，并写出相应的类型定义； 3．设计各基本操作的实现算法，并表达为函数形式； 4．设计测试方案，编写主函数； 5．将上述4步的结果写成预习报告。 3.4 实验要求和设计指标 以教材中线性表，串，稀疏矩阵，广义表，二叉树，树，图以及查找表等抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个抽象数据类型。 可选的抽象数据类型如下表所列： 注：如果基本操作数量较多，可选择实现其中一个基本操作子集。 实验要求如下： 1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。 4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。 3.5 实验仪器设备和材料 软件实验室。 编程环境：Anyview C可视化编程环境、TC++、C++Builder或者VC++。 3.6 调试及结果测试 调试内容应包括：调试过程中遇到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。 3.7 考核形式 考核形式以实验过程和实验报告相结合的方式进行。在实验完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算实验部分的结束。实验报告作为整个设计性实验评分的书面依据。设计性实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行正确；程序的结构合理；设计报告符合规范。 3.8 实验报告要求 实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报告要包括以下几项内容：（1）设计任务、要求及所用软件环境或工具； （2）抽象数据类型定义以及各基本操作的简要描述； （3）所选择的存储结构描述及在此存储结构上各基本操作的实现； （4）程序清单（计算机打印），输入的数据及各基本操作的测试结果； （5）实验总结和体会。 实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。 3.9 思考题 对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。 3.10 示例 管理学院信管专业12（1）班学号3112004734 姓名钟臻华协作者：无教师评定_________________ 实验题目线性表的基本操作 实验评分表 实验报告 一、实验目的与要求 1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概 念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对 算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、实验内容 1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分 析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。 1.顺序表的不删除出环元素算法实现 public class Josephus3{ public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数 //采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量 S eqList有理数抽象数据类型定义
数据结构第2章作业 线性表(答案)
线性表实验报告
严蔚敏版数据结构课后习题答案-完整版
C语言数据结构线性表的基本操作实验报告
数据结构实验一线性表
数据结构实验一题目一线性表实验报告
抽象数据类型线性表的定义
线性表逆置(顺序表)实验报告
线性表实验报告
数据结构线性表实验报告
线性表的基本操作实验报告
抽象数据类型的表示与实现(实验一)
实验报告二：线性表及其基本操作实验(2学时)
线性表的抽象数据类型的实现实验报告
抽象数据类型
数据结构 有理数抽象数据类型
抽象数据类型的实现
完整版12信管实验报告(线性表基本操作)