基于顺序表实现集合的并交差运算实验报告
基于顺序表实现集合的并交差运算实验报告 一 实验题目: 基于顺序表实现集合的并交差运算
二 实验要求:
2.1:编写一个程序，实现顺序表的各种基本运算
(1)初始化顺序表h ；
(2)依次采用尾插法插入a,b,c,d,e 元素;
(3)输出顺序表h
(4)输出顺序表h 的长度
(5)判断顺序表h 是否为空
(6)输出顺序表h 的第三个元素
(7)输出元素在a 的位置
(8)在第4个元素位置上插入f 元素
(9)输出顺序表h
(10)删除L 的第3个元素
(11)输出顺序表
(12)释放顺序表
2.2:编写一个程序，采用顺序表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序，构成有序顺序表，并求这样的两个集合的并,交和差。
三 实验内容:
3.1 线性表的抽象数据类型:
ADT List{
数据对象;D=}0,,...,2,1,ElemS et |{≥=∈n n i a a i i
数据关系:R1=},...,2,,|,{11n i D a a a a i i i i =∈><--
基本操作：
InitList(&L)
操作结果;构造一个空的线性表L
DestroyList(&L)
初始条件：线性表L 已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将L置为空表
ListEmpty(L)
初始条件：线性表已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE
ListLength(L)
初始条件：线性表已存在
操作结果：返回L中数据元素的个数
GetElem(L,i)
初始条件:线性表已存在，1<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值
LocateElem(L,i,e)
初始条件：线性表已存在，用循环遍历整个线性表，如果e与线性表中的元素相同；
操作结果：用此时的i+1返回该元素在线性表的位序
ListInsert(&L,i,e)
初始条件：线性表存在，1<=i<=ListLength(L)+1;
操作结果：在L中第i个位置之前插入新的数据元素,e,L的长度加1。
ListDelete(&L,i,&e)
初始条件:线性表L已存在且非空，1<=i<=ListLength(L)；
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
}ADT List
3.2存储结构的定义;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
3.3基本操作实现:
void InitList(SqList *&L)//初始化顺序表
{
L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个
顺序表的内存空间
L->length = 0;
}
void DestroyList(SqList *L)
{
free(L);//释放指针L
}
bool ListEmpty(SqList *L)
{
return (L->length == 0);//length为0表示表空}
int ListLength(SqList *L)
{
return (L->length);
}
void DispList(SqList *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length;i++)
{
printf("%c ",L->data[i]);
printf("\n");
}
}
bool GetElem(SqList *L,int i,ElemType &e)
{
if(i < 1||i > L->length) return false;
e = L->data[i-1];
return true;
}
int LocateElem(SqList *L,ElemType e)
{
int i = 0;
while(i < L->length&&L->data[i]!=e)
{
i++;
}
if(i >= L->length) return 0;
else return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if(i < 1||i>L->length+1) return false;
i--;
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if(i<1||i>L->length) return false;
i--;
e = L->data[i];
for(j = i;j
L->data[j]=L->data[j+1];
L->length--;
return true;
}
3.4解题思路：
1.先通过CreateListR 函数将集合 a 和 b 中的元素添加到顺序表 ha 和 hb 中，添加过程使用的是顺序表原有的Initlist 函数（初始化表）和 ListInsert 函数（向表中插入元素）。
2.因为原集合是无序的，所以我通过 sort 函数（冒泡排序），使得集合变得有序。
3.得到有序集合 ha 和 hb 后，便可以使用 Union 函数
（类似归并的思想写出来的求并集的函数），求出 ha 和 hb 的并集。
4.而求交集的方法则是，通过将集合 a 中的元素一个一个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果存在则将元素放入 hc ，如果不存在，则舍去。以此求得两集合的交集。
5.求两集合的差则可以反过来，同样通过将集合 a 中的元素一个一个取出，并通过函数LocateElem ，查看集合 hb 中是否存在该元素，如果不存在则将元素放入 hc ，如果存在，则舍去。以此求得两集合的差集。
3.5解题过程：
实验源代码如下：
3.5.1顺序表的各种运算
#include
#include
#include
using namespace std;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
void Initlist(Sqlist *&L)
{
L =(Sqlist *)malloc(sizeof(Sqlist));
L->length = 0;
}
bool ListInsert(Sqlist *&L, int x, char c)
{
int j;
if(x<1 || x>L->length+1)
return false;
x--;
for(j = L->length; j>x ; --j)
{
L->data[j] = L->data[j-1];
}
L->data[x] = c;
L->length++;
return true;
}
bool ListEmpty(Sqlist *L)
{
return (L->length==0);
}
void DispList(Sqlist *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length; ++i)
{
printf(" %c",L->data[i]);
}
printf("\n");
}
int ListLength(Sqlist *L)
{
return L->length;
}
bool GetElem(Sqlist *L,int x,Elemtype &c) {
if(x<1 || x>L->length)
return false;
c = L->data[x-1];
return true;
}
int LocateElem(Sqlist *L,Elemtype e)
{
int i = 0;
while(i
i++;
if(i==L->length)
return 0;
else
return i+1;
}
bool ListDelete(Sqlist *&L,int x,Elemtype &e) {
int j;
if(x<1 ||x >L->length + 1)
return false;
x--;
e = L->data[x];
for(j = x;j < L->length-1; ++j)
L->data[j] = L->data[j + 1];
L->length--;
return true;
}
void DestroyList(Sqlist *L)
{
free(L);
}
int main( )
{
Sqlist *p;
Elemtype e;
printf("(1)初始化顺序表 p\n");
Initlist(p);
printf("(2)依次采用尾插法插入 a , b , c , d , e 元素\n"); ListInsert(p,1,'a');
ListInsert(p,2,'b');
ListInsert(p,3,'c');
ListInsert(p,4,'d');
ListInsert(p,5,'e');
printf("(3)输出顺序表 p:");
DispList(p);
printf("(4)顺序表 p 长度=%d\n",ListLength(p));
printf("(5)顺序表 p 为%s\n",(ListEmpty(p)?"空":"非空"));
GetElem(p,3,e);
printf("(6)顺序表 p 的第3个元素=%c\n",e);
printf("(7)元素 a 的位置=%d\n",LocateElem(p,'a'));
printf("(8)在第 4 个元素位置上插入 f 元素\n");
ListInsert(p,4,'f');
printf("(9)输出顺序表 p:");
DispList(p);
printf("(10)删除 p 的第3个元素\n");
ListDelete(p,3,e);
printf("(11)输出顺序表 p: ");
DispList(p);
printf("(12)释放顺序表 p\n");
DestroyList(p);
return 0;
}
3.5.2求集合的并交差
#include
#include
#include
using namespace std;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
void Initlist(Sqlist *&L)
{
L =(Sqlist *)malloc(sizeof(Sqlist)); L->length = 0;
}
bool ListInsert(Sqlist *&L, int x, char c) {
int j;
if(x<1 || x>L->length+1)
return false;
x--;
for(j = L->length; j>x ; --j)
{
L->data[j] = L->data[j-1];
}
L->data[x] = c;
L->length++;
return true;
}
bool ListEmpty(Sqlist *L)
{
return (L->length==0);
}
void DispList(Sqlist *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length; ++i)
{
printf("%c",L->data[i]);
}
printf("\n");
}
int ListLength(Sqlist *L)
{
return L->length;
}
bool GetElem(Sqlist *L,int x,Elemtype &c) {
if(x<1 || x>L->length)
return false;
c = L->data[x-1];
return true;
}
int LocateElem(Sqlist *L,Elemtype e)
{
int i = 0;
while(i
if(i==L->length)
return 0;
else
return i+1;
}
bool ListDelete(Sqlist *&L,int x,Elemtype &e) {
int j;
if(x<1 ||x >L->length + 1)
return false;
x--;
e = L->data[x];
for(j = x;j < L->length-1; ++j)
L->data[j] = L->data[j + 1];
L->length--;
return true;
}
void DestroyList(Sqlist *L)
{
free(L);
}
void CreateListR(Sqlist *&L,Elemtype e[],int n) {
Initlist(L);
int i;
ListInsert(L,1,e[0]);
for(i = 1;i < n; ++i)
{
if(!LocateElem(L,e[i]))
ListInsert(L,i+1,e[i]);
}
}
void sort(Sqlist *&L)
{
int i, j;
for(i = 0;i < L->length; ++i)
{
for(j = 0;j < L->length; ++j)
{
if(L->data[i] < L->data[j])
{
char t = L->data[i];
L->data[i] = L->data[j];
L->data[j] = t;
}
}
}
}
void Union(Sqlist *a,Sqlist *b,Sqlist *&c)//利用归并的思想求并集{
Initlist(c);
int i, j, k;
i = 0;
j = 0;
k = 0;
while(i
{
if(a->data[i] < b->data[j])
{
ListInsert(c,k+1,a->data[i]);
k++;
i++;
}
else if(a->data[i] == b->data[j])
{
ListInsert(c,k+1,a->data[i]);
k++;
i++;
j++;
}
else
{
ListInsert(c,k+1,b->data[j]);
k++;
j++;
}
}
while(i
{
ListInsert(c,k+1,a->data[i]);
i++;
k++;
}
while(j
{
ListInsert(c,k+1,b->data[j]);
j++;
k++;
}
}
void InsterSect(Sqlist *a,Sqlist *b,Sqlist *&c) {
DestroyList(c);
Initlist(c);
int i ,k;
for(i = 0,k = 0;i < a->length; ++i)
{
if(LocateElem(b,a->data[i]))
{
ListInsert(c,k+1,a->data[i]);
k++;
}
}
}
void Subs(Sqlist *a,Sqlist *b,Sqlist *&c)
{
DestroyList(c);
Initlist(c);
int i ,k;
for(i = 0,k = 0;i < a->length; ++i)
{
if(!LocateElem(b,a->data[i]))
{
ListInsert(c,k+1,a->data[i]); k++;
}
}
}
int main( )
{
Sqlist *ha, *hb, *hc;
Elemtype a[]={'c','a','e','h'};
Elemtype b[]={'f','h','b','g','d','a'}; printf("集合的运算如下\n");
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf("原集合 A:"); DispList(ha);
printf("原集合 B:"); DispList(hb);
sort(ha);
sort(hb);
printf("有序集合A："); DispList(ha);
printf("有序集合B："); DispList(hb);
Union(ha,hb,hc);
printf("集合的并C："); DispList(hc);
InsterSect(ha,hb,hc);
printf("集合的交C："); DispList(hc);
Subs(ha,hb,hc);
printf("集合的差C："); DispList(hc);
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;
}
四实验结果:
数据结构实验集合的并交差运算实验报告记录
数据结构实验集合的并交差运算实验报告记录
————————————————————————————————作者：————————————————————————————————日期：
实验报告 实验课程：数据结构 实验项目：实验一集合的并交差运算专业：计算机科学与技术 班级： 姓名： 学号： 指导教师：
目录一、问题定义及需求分析 （1）实验目的 （2）实验任务 （3）需求分析 二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码
一、问题定义及需求分析 （1）实验目的 设计一个能演示集合的并、交、差运算程序。 （2）实验任务 1)采用顺序表或链表等数据结构。 2)集合的元素限定为数字和小写英文字母。 （3）需求分析： 输入形式为:外部输入字符串； 输入值限定范围为:数字和小写英文字母； 输出形式为：字符集； 程序功能:计算两个集合的交、并、差以及重新输入集合功能； 二、概要设计： (1)抽象数据类型定义： 线性表 (2)主程序流程： 调用主菜单函数初始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息另初始化两个线性表创建选择功能菜单界面通过不同选项调用不同功能函数在每个功能函数里面加结束选择功能，实现循环调用功能菜单 计算完毕退出程序； （3）模块关系： 主菜单 差运算并运算交运算新建集合结束/返回 结束 三、详细设计 抽象数据类型定义： typedef struct{ ElemType *elem; int length; int listsize;
C语言数据结构线性表的基本操作实验报告
实验一线性表的基本操作 一、实验目的与基本要求 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
数据结构课程设计_集合的并、交和差运算
数据结构课程设计 学院：信息科学与工程学院 专业：计算机科学与技术 班级： 学号： 学生姓名： 指导教师： 2009 年12 月25 日
一、实验内容 实验题目：编制一个演示集合的并、交和差运算的程序。 需求分析： 1、本演示程序中，集合的元素限定为小写字母字符[“a”…”z”]。集合输入的形 式为一个以“回车符“为结束标志的字符串，串中字符顺序不限。 2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信 息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。 3、程序执行的命令包括： 1）构造集合1；2）构造在集合2；3）求并集；4）求交集；5)求差集；6）返回；7）结束。“构造集合1”和“构造集合2”时，需以字符的形式键入集合元素。 二、数据结构设计 为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。 1、有序表的抽象数据类型定义为： readdata(pointer head) 初始条件：head是以head为头节点的空链表。 操作结果：生成以head为头节点的非空链表。 pop(pointer head) 初始条件：head是以head为头节点的非空链表。 操作结果：将以head为头节点的链表中数据逐个输出。 2、集合的抽象数据类型定义为： and(pointer head1,pointer head2,pointer head3) 初始条件：链表head1、head2、head3已存在 操作结果：生成一个由head1和head2的并集构成的集合head3。 or(pointer head1,pointer head2,pointer head3) 初始条件：链表head1、head2、head3已存在 操作结果：生成一个由head1和head2的交集构成的集合head3。
1.C语言顺序表实验报告
实验报告要求 一、实验目的 二、实验内容 三、程序流程图 四、实验结果（要求检测所有情况的正确性，写出测试条件及相应的测试结果） 五、完成思考题 实验一顺序表的基本操作(2学时) 一、实验目的 了解顺序表的逻辑特征，掌握顺序表的描述方法、特点及有关的概念，掌握顺序表上的插入和删除等基本操作算法。 二、实验内容 在顺序表List []中，实现顺序表的基本操作，包括：初始化顺序表，在表中插入元素、删除元素。 基本要求： （1）顺序表的元素个数可随意设定； （2）可连续测试任意多个元素的插入、删除，（插 入、删除位置及要插入元素数值均从键盘输入）； （3）任一操作结束后将顺序表中的内容输出； （4）可由用户选择退出程序。 三、实验要点及说明 顺序表又称为线性表的顺序存储结构，它是用一组地址连续的存储单元依次存放线性表的各个元素。 可按如下格式定义顺序表： #define MAXLEN 50 /* 定义顺序表最大元素个数50 */ typedef struct{ datatype List[MAXLEN];/* 定义顺序表List */ int Num; /* 定义顺序表表长*/ }Seqlist; 模块划分：（1）initiq( )函数：初始化顺序表 （2）insertq( )函数：实现插入功能 （3）deleteq( )函数：实现删除功能 （4）print( )函数：实现输出功能 四、参考源程序 #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
集合 的交并和差的运算与实现
#include 《数据结构》实验报告一 系别：班级： 学号：姓名： 日期：指导教师： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入10个整数，产生顺序表，并输入结点值。 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释： #include <> /*顺序表的定义：*/ #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; /*子函数的声明*/ void CreateList(SeqList * L,int n); /*创建顺序表函数*/ int LocateList(SeqList L,DataType x); /*查找顺序表*/ void InsertList(SeqList * L,DataType x,int i); /*在顺序表中插入结点x*/ void DeleteList(SeqList * L,int i);/*在顺序表中删除第i个结点*/ void PrintList(SeqList L,int n); /*打印顺序表中前n个结点*/ void main() { SeqList L; int n=10,x,i; /*欲建立的顺序表长度*/ =0; 一．实验名称 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) 数据结构C++课程设计题目: 集合的并、交和差运算 一、设计题目 集合的并、交和差运算 二、小组成员分工说明 一个人 三、需求分析 1）运行环境（软、硬件环境） 软件环境：Microsoft Vista操作系统，Visual C++ 6.0 硬件环境：2.0GB内存 2）输入的形式和输入值的范围 运行所给的测试数据，集合的元素限定为小写字符〔a. .z〕：第一组： Set1＝magazine ，Set2＝paper 第二组： Set1＝0120per4a6tion89，Set2＝error data 输出的形式描述 程序运行并、交和差运算后得到数据，输出字符。 3）功能描述 能演示执行集合的并、交和差运算。 4）测试数据 (1) Set1＝magazine ，Set2＝paper， Set1∪Set2＝aeginmprz，Set1∩Set2＝ae，Set1－Set2＝gimnz。 (2) Set1＝0120per4a6tion89，Set2＝error data， Set1∪Set2=adeinoprt，Set1∩Set2=aeort，Set1－Set2＝inp。 四、概要设计 1）抽象数据类型定义描述 （顺序表的抽象数据类型描述） ADT Seqlist is Data 线性表的长度 Operation Seqlist 初始化值：无 动作：置顺序表的长度为0 Length 输入：无 前置条件：表已存在 功能：求表的长度 输出：返回表的长度，即表中数据元素的个数 后置条件：表不变 Get 输入：元素的序号i 前置条件：表已存在，i合法 功能：在表中取序号为i的数据元素 输出：若i合法，返回序号为i的元素值，否则抛出异常后置条件：表不变 Locate 输入：数据元素item 前置条件：表已存在 功能：在线性表中查找值等于item的元素 输出：若查找成功，返回x在表中的序号，否则返回0 后置条件：表不变 Insert 输入：插入位置i；待插元素item 前置条件：表已存在,i合法 功能：在表的第i个位置处插入一个新元素x 输出：若插入不成功，抛出异常 后置条件：若插入成功，表中增加一个新元素 Delete 输入：删除位置i 前置条件：表已存在 功能：删除表中的第i个元素 输出：若删除成功，返回被删元素，否则抛出异常 后置条件：若删除成功，表中减少一个元素 Empty 输入：无 前置条件：表已存在 功能：判断表是否为空 输出：若是空表，返回1，否则返回0 后置条件：表不变 Clear 输入：无 前置条件：无 功能：清空顺序表 输出：无 后置条件：表的长度是0 end ADT seqList 2）功能模块设计（如主程序模块设计） 顺序表的基本操作的实现 一、实验目的 1、掌握使用VC++上机调试顺序表的基本方法； 2、掌握顺序表的基本操作：建立、插入、删除等运算。 二、实验仪器 安装VC++软件的计算机。 三、实验原理 利用线性表的特性以及顺序存储结构特点对线性表进行相关的基本操作四、实验内容 程序中演示了顺序表的创建、插入和删除。 程序如下： #include i nt i,x; i nt n=10; L.length=0; c lrscr(); C reateList(&L,n); /*建立顺序表*/ P rintList(&L,n); /*打印建立后的顺序表*/ p rintf("INPUT THE RESEARCH ELEMENT"); s canf("%d",&x); i=LocateList(&L,x); p rintf("the research position is %d\n",i); /*顺序表查找*/ p rintf("input the position of insert:\n"); s canf("%d",&i); p rintf("input the value of insert\n"); s canf("%d",&x); I nsertList(&L,x,i); /*顺序表插入*/ P rintList(&L,n); /*打印插入后的顺序表*/ p rintf("input the position of delete\n"); s canf("%d",&i); D eleteList(&L,i); /*顺序表删除*/ P rintList(&L,n); /*打印删除后的顺序表*/ g etchar(); } /*顺序表的建立：*/ void CreateList(SeqList *L,int n) {int i; printf("please input n numbers\n"); for(i=1;i<=n;i++) scanf("%d",&L->data[i]); L->length=n; 实验报告 实验一线性表 实验目的： 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); 实验二集合的并、交和差运算 // 在写代码的过程中，没有注意头结点~~~ 导致出现了很多野指针~~~ ，几乎重写. 。o 0 ~~~ // 经同学检查，发现有错误~~~ 红色部分代码已经修正 //集合的并、交和差运算 /* 选作内容 (1)集合元素的判定和子集判定运算 (2)求集合的补集 (3)集合的混合式运算表达求值 (4)集合的元素类型推广到其他类型，甚至任意类型 */ /* 测试数据： (1)Set1 ="magazine"，Set2 ="paper"， Set1∪Set2 ="aegimnpra"，Set1∩Set2 ="ae"，Set1 - Set2 ="gimnz" (2)Set1 =012oper4a6tion89"，Set2 ="error date"， Set1∪Set2 ="adeinoprt"，Set1∩Set2 ="aeort"，Set1 - Set2 ="inp" */ #include 嘉应学院计算机学院 实验报告 课程名称数据结构实验名称线性表实验地点锡科405 指导老师巫喜红实验时间第2-3周提交时间第3周 班级1303班姓名魏振辉学号131110108 一、实验目的和要求 编写一个程序algo2-1.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。 实验环境：Windows xp Visual C++6.0 三、实验过程描述 （详见本文件夹） 四、结果分析 运行结果如下图所示： 初始化线性表，先定义一个变量num，用while循环配合switch语句的使用来达到在未选择退出即num不等 时一直提示操作的效果，每执行一次操都会先运行fflush(stdin)函数来清除缓存区，避免下次操作受到干扰； 1、往线性表里插入元素，位置和元素用空格隔开； 2、查询线性表是否为空 3、输出顺序表 4、查询线性表长度 5、查询某位置的元素。执行查询操作时先用if语句判断查询元素的函数LocateElem(L,e)返回的值来执行不的操作，当返回的值为0时则所查元素不在线性表中； 6、查询木元素的位置。用if语句判断是否正确输入； 7、删除某元素。 8、释放顺序表 9、退出。用if语句每次执行操作时都判断一次指令是否正确。 五、实验总结 实验一：线性表的基本操作 【实验目的】 学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。 【实验内容】 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.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include 实验报告 实验二线性表及其基本操作实验(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 《数据结构》 课程设计说明书 题目集合的并交差运算 学号 姓名 指导教师 日期 内蒙古科技大学课程设计任务书 附录：程序代码 #include jihe a[3];jihe b; /*************************长度****************************************/ int jihe::ListLength(int i) { LinkList *p; p = a[i].L; while (p->next != NULL) { p = p->next; a[i].length ++; } return a[i].length; } /****************************输入*************************************/ void jihe::ListCreat(int i) /*尾插法插入元素*/ { cout<<"请为集合输入数值（以回车键结束）："; char c; LinkList *p,*r; a[i].L=(LinkList*)malloc(sizeof(LinkList)); a[i].L->next=NULL; r=a[i].L; cin>>c; while(c!='\n') { p=(LinkList*)malloc(sizeof(LinkList)); if(c==' ') {} else { p->data=c; r->next=p; r=p; } c=cin.get(); } r->next=NULL; cout<<"输入完毕，请按回车键返回主菜单！"< 顺序表的应用数据结构实验报告记录 ————————————————————————————————作者：————————————————————————————————日期： 大学数据结构实验报告 课程名称数据结构实验第（三）次实验实验名称顺序表的应用 学生姓名于歌专业班级学号 实验成绩指导老师（签名）日期2018年9月30日一、实验目的 1．学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。 2．掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。 3．掌握对多函数程序的输入、编辑、调试和运行过程。 二、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对顺序表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。 三、实验内容： 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能： （1）根据指定学生个数，逐个输入学生信息 （2）逐个显示学生表中所有学生的相关信息 （3）根据姓名进行查找，返回此学生的学号和成绩 （4）根据指定的位置可返回相应的学生信息（学号，姓名，成绩） （5）给定一个学生信息，插入到表中指定的位置 （6）删除指定位置的学生记录 （7）统计表中学生个数 四、实验设计 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能： （1）根据指定学生个数，逐个输入学生信息 for(count=0; count 实验一：线性表逆置（顺序表）实验报告 （一）问题的描述： 实现顺序表的逆置算法 （二）数据结构的设计： 顺序表是线性表的顺序存储形式，因此设计如下数据类型表示线性表： 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. （四）具体程序的实现 石河子大学 《集合的并，交和差运算》程序设计基础课程设计报告 二OO八年六月二十一日 目录 一．编程目的： (2) 二．设计要求 (2) 三．各函数功能说明： (2) 四．函数框架图： (6) 五．总结： (7) 参考书目……………………………………………………………….8. 一．编程目的： 编写数学程序，能够演示执行集合的集合的并，交和差运算的程序，可以任意对两个集合进行集合之间的运算。 通过该程序的编写，我学会了如何更加熟练的掌握类和动态链表，我觉得程序设计很有难度，同时我学会了不会的一定要自己去找资料和问自己的同学或者询问自己的师兄师姐，那样有助于自己的自主学习。 经过自己的查找和询问，让自己对书上的知识理解的更加透彻一点了，该程序让我们把书上的知识灵活运用，让我们把书上的知识变活了，不至于掌握死的知识。 二．设计要求： 用类、数组建立数据库（最少包含3条记录以及具有下列功能） 1.集合的限定：集合元素必须为小写字母（元素为小写字母‘a~z’）2．能够进行集合之间的并集，交集以及差集运算。 3.可以进行最简单的提示（例如输入数据有误时候会进行提示） 三．各函数功能说明： 函数源代码以及函数的功能： #include typedef struct pointer { //定义一个结构体变量pointer char dat; struct pointer *link; } pointer; void readdata(pointer *head){ //读集合 pointer *p; char tmp; printf("input data ('0' for end):"); //输出结果以‘0’结尾 scanf("%c",&tmp); while(tmp!='0') { if((tmp<'a')||(tmp>'z')) { printf("输入错误！必须为小写字母！\n"); return; } p=(pointer *)malloc(sizeof(struct pointer)); p->dat=tmp; p->link=head->link; head->link=p; scanf("%c",&tmp); } } void disp(pointer *head){ //显示集合数据 pointer *p; p=head->link; while(p!=NULL) { printf("%c ",p->dat); p=p->link; } printf("\n"); } void bing(pointer *head1,pointer *head2, pointer *head3){ //计算集合1与集合2的并实验报告一顺序表的操作
线性表实验报告
集合的并,交和差运算数据结构C 课程设计
数据结构- 顺序表的基本操作的实现-课程设计-实验报告
数据结构线性表实验报告
实验 二 集合的并、交和差运算C++
顺序表实验报告
线性表的基本操作实验报告
顺序表的查找、插入与删除实验报告
实验报告二：线性表及其基本操作实验(2学时)
集合的交并差运算
顺序表的应用数据结构实验报告记录
线性表逆置(顺序表)实验报告
集合的并,交和差运算