实验二 抽象数据类型的表 示和实现

⼴义表实验报告抽象数据类型的实现1．实验概要实验项⽬名称: 抽象数据类型的实现实验项⽬性质: 设计性实验所属课程名称: 数据结构实验计划学时: 62．实验⽬的对某个具体的抽象数据类型，运⽤课程所学的知识和⽅法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。

通过本设计性实验，检验所学知识和能⼒，发现学习中存在的问题。

进⽽达到熟练地运⽤本课程中的基础知识及技术的⽬的。

3．编译软件Microsoft Visual C++6.04．抽象数据类型定义以及各基本操作的简要描述ADT GList{数据对象:D={i=1,2,...,n>=0;ei (-AtomSet或ei (-GList,AtomSet为某个数据对象} 数据关系:R1={|ei-1,ei (-D,2=基本操作:InitGlist(&L);操作结果:创建空的⼴义表LCreateGList(&L,S);初始条件:S是⼴义表的书写形式串操作结果:由S创建⼴义表LDestroyGlist(&L);初始条件:⼴义表L存在操作结果:销毁⼴义表LCopyGlist(&T,L);初始条件:⼴义表L存在操作结果:由⼴义表L复制得到⼴义表TGListLength(L);初始条件:⼴义表L存在操作结果:求⼴义表L的长度,即元素个数GListDepth(L);初始条件:⼴义表L存在初始条件:⼴义表L存在操作结果:判断⼴义表L是否为空GetHead(L);初始条件:⼴义表L存在操作结果:取⼴义表L的头GList GetTail(L)初始条件:⼴义表L存在操作结果: 取⼴义表L的尾InsertFirst_GL(&L,e)初始条件:⼴义表L存在操作结果:插⼊元素e作为⼴义表L的第⼀元素DeleteFirst_GL(GList &L,&e)初始条件:⼴义表L存在操作结果:删除⼴义表L的第⼀元素，并⽤e返回其值Traverse_GL(GList L,void(*v)(AtomType))初始条件:⼴义表L存在操作结果:遍历⼴义表L，⽤函数Visit处理每个元素} ADT GList5．⼴义表的存储结构-------⼴义表的扩展线性链表存储表⽰------typedef enum{ATOM,LIST}ElemTag; // ATOM==0:原⼦,LIST==1:⼦表typedef struct GLNode{ElemTag tag; // 公共部分,⽤于区分原⼦结点和表结点union // 原⼦结点和表结点的联合部分{AtomType atom; // 原⼦结点的值域struct GLNode *hp; // 表结点的表头指针}a;struct GLNode *tp; // 相当于线性链表的next,指向下⼀个元素结点 }*GList,GLNode;6．主函数及部分函数流程图主函数流程图:由S创建⼴义表L流程图：销毁⼴义表L流程图:求⼴义表L深度流程图：⼴义表L长度流程图:遍历⼴义表L流程图:7.程序清单#include /头⽂件a.h/#include#include#include#include#define TRUE 1 / 函数结果状态代码/ #define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef char AtomType;typedef int Status;typedef struct / 串的堆分配存储/{char *ch;int length;}HString;typedef enum{ATOM,LIST}ElemTag; /⼴义表的扩展线性链表存储表⽰/ typedef struct GLNode {ElemTag tag;union{AtomType atom;struct GLNode *tp;}*GList,GLNode;void InitString(HString *T); /函数声明/int StrCompare(HString S,HString T);int StrLength(HString S);Status StrAssign(HString *T,char *chars);Status StrCopy(HString *T,HString S);Status StrEmpty(HString S);Status ClearString(HString *S);Status SubString(HString *Sub, HString S,int pos,int len); Status sever(HString *str,HString *hstr);GList GetHead(GList L);GList GetTail(GList L);void visit(AtomType e);void Traverse_GL(GList L,void(*v)(AtomType));int GListLength(GList L);int GListDepth(GList L);Status InitGList(GList *L);Status CreateGList(GList *L,HString S);Status DestroyGList(GList *L);Status CopyGList(GList *T,GList L);Status GListEmpty(GList L);Status InsertFirst_GL(GList *L,GList e);Status DeleteFirst_GL(GList *L,GList *e);Status StrAssign(HString *T,char *chars) /串的操作/ { /⽣成⼀个其值等于串常量chars的串T / int i,j;if((*T).ch)free((*T).ch); /释放T原有空间/i=strlen(chars);if(!i){(*T).ch=NULL;(*T).length=0;{(*T).ch=(char*)malloc(i*sizeof(char)); /分配串空间/ if(!(*T).ch)exit(OVERFLOW);for(j=0;j(*T).ch[j]=chars[j];(*T).length=i;}return OK;}Status StrCopy(HString *T,HString S){ /由串S复制得串T /int i;if((*T).ch)free((*T).ch); /释放T原有空间/(*T).ch=(char*)malloc(S.length*sizeof(char));if(!(*T).ch) /分配串空间失败/exit(OVERFLOW);for(i=0;i(*T).ch[i]=S.ch[i];(*T).length=S.length;return OK;}Status StrEmpty(HString S){ /若S为空串,则返回TRUE,否则返回FALSE /if(S.length==0&&S.ch==NULL)return TRUE;elsereturn FALSE;}int StrCompare(HString S,HString T){ /若S>T,则返回值>0;若S=T,则返回值=0;若Sfor(i=0;ireturn S.length-T.length;}int StrLength(HString S){ /返回S的元素个数,称为串的长度/return S.length;}Status ClearString(HString *S){ /清空串/if((*S).ch){free((*S).ch);(*S).ch=NULL;}(*S).length=0;return OK;}Status SubString(HString *Sub, HString S,int pos,int len) { /⽤Sub返回串S的第pos个字符起长度为len的⼦串/ int i; if(pos<1||pos>S.length||len<0||len>S.length-pos+1) return ERROR;if((*Sub).ch)free((*Sub).ch);if(!len) /空⼦串/{(*Sub).ch=NULL;(*Sub).length=0;}else / 完整⼦串/{(*Sub).ch=(char*)malloc(len*sizeof(char));if(!(*Sub).ch)exit(OVERFLOW);for(i=0;i<=len-1;i++)return OK;}void InitString(HString *T){ /产⽣空串/(*T).length=0;(*T).ch=NULL;}Status sever(HString *str,HString *hstr){ /将⾮空串str分割成两部分:hstr为第⼀个','之前的⼦串,str为之后的⼦串/ int n,i=1,k=0; HString ch,c1,c2,c3;InitString(&ch);InitString(&c1);InitString(&c2);InitString(&c3);StrAssign(&c1,",");StrAssign(&c2,"(");StrAssign(&c3,")");n=StrLength(*str);do{SubString(&ch,*str,i,1);if(!StrCompare(ch,c2))++k;else if(!StrCompare(ch,c3))--k;++i;}while(i<=n&&StrCompare(ch,c1)||k!=0);if(i<=n){StrCopy(&ch,*str);SubString(hstr,ch,1,i-2);SubString(str,ch,i,n-i+1);StrCopy(hstr,*str);ClearString(str);}return OK;}Status InitGList(GList *L) /⼴义表的操作/ { /创建空的⼴义表/*L=NULL;return OK;}Status CreateGList(GList *L,HString S) { /由S创建⼴义表/HString emp,sub,hsub;GList p;InitString(&emp);InitString(&sub);InitString(&hsub);StrAssign(&emp,"()");*L=(GList)malloc(sizeof(GLNode));if(!*L)exit(OVERFLOW);if(!StrCompare(S,emp)) /创建空表/{(*L)->tag=LIST;(*L)->a.hp=NULL;(*L)->tp=NULL;}else if(StrLength(S)==1) /创建单原⼦⼴义表/ {(*L)->tag=ATOM;(*L)->a.atom=S.ch[0];(*L)->tp=NULL;(*L)->tag=LIST;(*L)->tp=NULL;SubString(&sub,S,2,StrLength(S)-2); /脱外层括号/sever(&sub,&hsub); / 从sub中分离出表头串hsub / CreateGList(&(*L)->a.hp,hsub); p=(*L)->a.hp;while(!StrEmpty(sub)) /表尾不空,则重复建n个⼦表/{sever(&sub,&hsub);CreateGList(&p->tp,hsub);p=p->tp;};}return OK;}Status DestroyGList(GList *L){ /销毁⼴义表/GList ph,pt;if(*L) /L不为空表/{if((*L)->tag) /当L是⼦表/ph=(*L)->a.hp;else /当L是原⼦/ph=NULL;pt=(*L)->tp;free(*L); /释放L所指结点/*L=NULL;DestroyGList(&ph); /递归销毁表ph /DestroyGList(&pt); /递归销毁表pt /}return OK;}Status CopyGList(GList *T,GList L)*T=NULL;return OK;}*T=(GList)malloc(sizeof(GLNode));if(!*T)exit(OVERFLOW);(*T)->tag=L->tag;if(L->tag==ATOM) /复制共⽤体部分/(*T)->a.atom=L->a.atom; /复制单原⼦/ elseCopyGList(&(*T)->a.hp,L->a.hp); /复制⼦表/ if(L->tp==NULL)(*T)->tp=L->tp;elseCopyGList(&(*T)->tp,L->tp); /复制⼦表/ return OK;}int GListLength(GList L){ /求⼴义表L的长度/int len=0;GList p;if(L->tag==LIST&&!L->a.hp) /空表/return 0;else if(L->tag==ATOM) /单原⼦表/return 1;else /⼀般表/{p=L->a.hp;do{len++;p=p->tp;}while(p);}int GListDepth(GList L){ /求⼴义表L的深度/int max,dep;GList pp;if(L==NULL||L->tag==LIST&&!L->a.hp)return 1; /空表深度为1/else if(L->tag==ATOM)return 0; /单原⼦表深度为0 /else /求⼀般表的深度/for(max=0,pp=L->a.hp;pp;pp=pp->tp){dep=GListDepth(pp);if(dep>max)max=dep;}return max+1; /⾮空表的深度是各元素的深度的最⼤值加1 / } Status GListEmpty(GList L){ /判定⼴义表L是否为空/if(!L||L->tag==LIST&&!L->a.hp)return OK;elsereturn ERROR;}GList GetHead(GList L){ /取⼴义表表头/GList h;InitGList(&h);if(!L||L->tag==LIST&&!L->a.hp){printf("\n空表⽆表头!");exit(0);}exit(OVERFLOW);h->tag=L->a.hp->tag;h->tp=NULL;if(h->tag==ATOM)h->a.atom=L->a.hp->a.atom;elseCopyGList(&h->a.hp,L->a.hp->a.hp);return h;}GList GetTail(GList L){ /取⼴义表表尾/GList T;if(!L){printf("\n空表⽆表尾!");exit(0);}T=(GList)malloc(sizeof(GLNode));if(!T)exit(OVERFLOW);T->tag=LIST;T->tp=NULL;CopyGList(&T->a.hp,L->a.hp->tp);return T;}Status InsertFirst_GL(GList *L,GList e){ /插⼊元素e作为⼴义表L的第⼀元素/ GList p=(*L)->a.hp; (*L)->a.hp=e;e->tp=p;return OK;}Status DeleteFirst_GL(GList *L,GList *e){ /删除⼴义表L的第⼀元素,并⽤e返回其值/ if(*L)(*L)->a.hp=(*e)->tp;(*e)->tp=NULL;}else*e=*L;return OK;}void Traverse_GL(GList L,void(*v)(AtomType)) { /遍历⼴义表/GList hp;if(L){if(L->tag==ATOM) /L是原⼦/{v(L->a.atom);hp=NULL;}else /L是⼦表/hp=L->a.hp;Traverse_GL(hp,v);Traverse_GL(L->tp,v);}}void visit(AtomType e){printf("%c ", e);}void main() /主函数/{char p[80];GList l,m;HString t;InitString(&t);Status Eflag;int x;int d;do{E flag=TRUE;d o{system("cls");printf("\n***************************************************"); printf("\n1:建⽴空⼴义表");printf("\n2:由字符串建⽴⼴义表");printf("\n3:退出");printf("\n***************************************************"); printf("\n请选择功能：");scanf("%d",&x);switch(x){case 1: if(InitGList(&l)){printf("\n建表成功！");getch();}else{printf("\n建表失败！");getch();Eflag=FALSE;}break;case 2: printf("\n请输⼊合法的⼴义表书写形式"); printf("\n格式如：(),(a,b),(a,(),b),(a,(c,d),f)");printf("\n输⼊字符串：");if(CreateGList(&l,t)){printf("\n建表成功！");getch();}else{printf("\n建表失败！");getch();Eflag=FALSE;}break;case 3: printf("\n感谢使⽤本软件！");getch();exit(0);default: printf("\n输⼊错误！请重新输⼊！");getch();}}w hile(x!=1&&x!=2||!Eflag);d o{Status Eflag=TRUE;system("cls");printf("\n***************************************************"); printf("\n1:复制⼴义表");printf("\n2:求⼴义表长度");printf("\n3:求⼴义表深度");printf("\n4:判断⼴义表是不是空表");printf("\n5:取⼴义表表头");printf("\n6:取⼴义表表尾");printf("\n7:头结点插⼊元素");printf("\n8:删除第⼀个元素");printf("\n11:退出");printf("\n***************************************************"); printf("\n请选择功能：");printf("\n请输⼊你要选择的功能：");scanf("%d",&x);switch(x){case 1: if(CopyGList(&m,l)){printf("\n复制成功！");getch();}break;。

【实验题目】实验1. 抽象数据类型. 【问题描述】用C 或C++语言设计并实现一个可进行复数运算的演示程序。

【基本要求】1.由输入的实部和虚部生成一个复数2.两个复数求和3.两个复数求差4.从已知复数中分离出实部和虚部5.复数及相应运算结果以相应的表现形式显示。

【实现提示】定义复数为由两个相互之间存在次序关系的实数构成的抽象数据类型，则可以利用实数的操作来实现复数的操作。

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四） 一、【实验构思（Conceive ）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）1. 首先构造结构体数组接受储存数据2. 构造函数进行模块运算3. 应用到了算法中的抽象数据类型ADT （即数据+操作），数据部分包括实部和虚部；操作部分包括加分Plus 、减法Minus 、乘法Multiply 、除法Divide 4. 运用到了复数的基本知识及四则运算法则：设 z 1=a + bi ，z 2=c + di ，（a ，b ，c ，d ∈R ，）加减法：（a + bi ）±（c + di ）=（a ± c ）+（b ± d ）i 乘法：（a + bi ）*（c + di ）=（ac - bd ）+（ad + bc ）i除法： 2222()()()()a bi a bi c di ac bd bc ad ic di cd c d++-+-==+++ 二、【实验设计(Design)】(15%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 解答：抽象数据类型 数据部分：用结构体（数组）实现复数的储存结构 操作部分：实现复数的输入、存储、运算及输出 程序模块伪码说明： #define N 2int n=0; //控制选择语句，及检验输入是否正确 typedef struct{double real;//复数的实部double imag;//复数的虚部}paramater; //paramater是结构体变量的类型表示“复数”，声明复数的存储结构paramater cpxNum[N];//构造结构体数组储存数据paramater result;//构造result结构体储存结果int main(){//实现第一个复数的输入储存cout<<"\t请输入第一个复数的实部和虚部:";cin>>real>>imag;outs(c[0].real,c[0].imag)//初始化复数c[0]并实现输出//实现第二个复数的输入储存cout<<"\t请输入第二个复数的实部和虚部:";cin>>real>>imag;puts( c[0].real,c[0].imag);//初始化复数c[1]并实现输出//复数运算cout << "c1 + c2的结果是: "; puts(plus(c[0],c[1])); cout << endl; //调用plus函数运算加法，再用puts函数输出结果复数cout << "c1 - c2的结果是: "; puts(milus(c[0],c[1])); cout << endl; //调用mlius函数运算减法，再用puts函数输出结果复数cout << "c1 * c2的结果是: "; puts(multiply(c[0],c[1])); cout << endl; //调用multiply函数运算乘法，再用puts函数输出结果复数cout << "c1 / c2的结果是: "; puts(divide(c[0],c[1])); cout << endl; //调用divide函数运算除法，再用puts函数输出结果复数return 0;}三、【实现描述（Implement）】(25%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验二抽象数据类型的表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。

2、掌握抽象数据类型的定义方式和用C语言实现的方法。

3、熟悉如何运用主函数检验各基本操作函数的正确性的具体操作。

二.实验内容1、认真阅读以下有关抽象数据类型的知识：（1）抽象数据类型的概念抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。

一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。

抽象数据类型通常采用以下格式定义：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>} ADT抽象数据类型名（2）三元组的抽象数据类型定义及表示我们以抽象数据类型三元组为例，说明抽象数据类型是如何定义的。

三元组实际上就是一个数据对象中有3个数据元素。

三元组中元素的数据类型，可以是整型数，也可以是字符、浮点数或者更复杂的数据类型。

以下是三元组的抽象数据类型定义：ADT Triplet{数据对象：D={e1, e2, e3 | e1, e2, e3∈ElemSet (ElemSet为某个数据对象的集合)}数据关系：R1={<e1, e2>, <e2, e3>}基本操作：InitTriplet(&T, v1, v2, v3)操作结果：构造三元组T，元素e1, e2和e3分别被赋以v1, v2, v3值DestroyTriplet(&T)操作结果：三元组T被销毁Get(T, i, &e)初始条件：三元组T已存在，1≤i≤3操作结果：用e返回T的第i元的值IsAscending(T)初始条件：三元组T已存在操作结果：如果T的三个元素按升序排列，则返回1，否则返回0 IsDecending(Triplet T);初始条件: 三元组T已存在操作结果: 如果T的三个元素按降序排列，则返回1，否则返回0 Put(&T, i, e)初始条件：三元组T已存在，1≤i≤3操作结果：改变T的第i元的值为eMax(T, &e)初始条件：三元组T已存在操作结果：用e返回T的三个元素中的最大值Min(T, &e)初始条件：三元组T已存在操作结果：用e返回T的三个元素中的最小值} ADT Triplet三元组在计算机中的具体存储方式可以采用动态分配的顺序存储结构，如图所示：Triplet ElemType动态分配的顺序存储的三元组2、在计算机中实现上述三元组抽象数据类型。

（二〇一四年九月《数据结构》实验报告学校代码： 10128 学 号： 201220905048题 目：抽象数据类型的表示和实现 学生姓名：孙跃 学 院：理学院 系 别：数学系专 业：信息与计算科学 班 级：信计12-2 任课教师：杜雅娟一、实验目的1.熟悉Visual C++语言的上机环境，掌握C语言的基本结构。

2.理解抽象数据类型的表示和实现。

二、实验内容抽象数据类型Triplet的表示和实现。

三、实验程序根据给出的程序清单分别另建立4个文件：c1.h、c1-1.h、bo1-1.cpp和main1-1.cpp，并把它们保存在同一个文件夹中。

1.预定义常量和类型教材定义OK、ERROR等为函数结果状态代码，文件Status为其类型。

我们把这些信息放到头文件c1.h中。

c1.h还包含一些常用的，如string.h、stdio.h等。

为了操作的方便，几乎每一个程序都把c1.h包含进去，也就把这些结果状态代码和头文件包含了进去。

头文件的内容如下：// c1.h (程序名)#include<string.h>#include<ctype.h>#include<malloc.h> // malloc()等#include<limits.h> // INT_MAX等#include<stdio.h> // EOF(=^Z或F6),NULL#include<stdlib.h> // atoi()#include<io.h> // eof()#include<math.h> // floor(),ceil(),abs()#include<process.h> // exit()#include<iostream.h> // cout,cin// 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE2.采用动态分配的顺序存储结构采用动态分配的顺序存储结构的头文件名取名为c1-1.h// c1-1.h 采用动态分配的顺序存储结构typedef ElemType *Triplet; // 由InitTriplet分配三个元素存储空间// Triplet类型是ElemType类型的指针类型，用它定义的变量存放ElemType类型数据的地址3.抽象数据类型Triplet和Elem Type的基本操作// bo1-1.cpp 抽象数据类型Triplet和ElemType(由c1-1.h定义)的基本操作(8个)Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3){ // 操作结果:构造三元组T,依次置T的三个元素的初值为v1,v2和v3if(!(T=(ElemType *)malloc(3*sizeof(ElemType))))exit(OVERFLOW);T[0]=v1,T[1]=v2,T[2]=v3;return OK;}Status DestroyTriplet(Triplet &T){ // 操作结果：三元组T被销毁free(T);T=NULL;return OK;}Status Get(Triplet T,int i, ElemType &e){ // 初始条件：三元组T已存在，1≤i≤3。

抽象数据类型的表⽰与实现
抽象数据类型的表⽰与实现
抽象数据类型(Abstract Data Type 简称ADT)是指⼀个数学模型以及定义在此数学模型上的⼀组操作。

抽象数据类型需要通过固有数据类型(⾼级编程语⾔中已实现的数据类型)来实现。

抽象数据类型是与表⽰⽆关的数据类型，是⼀个数据模型及定义在该模型上的⼀组运算。

对⼀个抽象数据类型进⾏定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。

⼀旦定义了⼀个抽象数据类型及具体实现，程序设计中就可以像使⽤基本数据类型那样，⼗分⽅便地使⽤抽象数据类型。

抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等⽅⾯的描述。

【通俗的说：就是名字、数据集合、关系和操作的集合】
抽象数据类型描述的⼀般形式如下：
ADT抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名1：
……
……
操作名n：
}ADT抽象数据类型名称
总结：
抽象数据类型定义（ADT）
作⽤：抽象数据类型可以使我们更容易描述现实世界。

例：⽤线性表描述学⽣成绩表，⽤树或图描述遗传关系。

定义：⼀个数学模型以及定义在该模型上的⼀组操作。

关键：使⽤它的⼈可以只关⼼它的逻辑特征，不需要了解它的存储⽅式。

定义它的⼈同样不必要关⼼它如何存储。

例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第⼀个和最后⼀个外，每个元素有唯⼀的前趋和唯⼀的后继。

可以有这样⼀些操作：插⼊⼀个元素、删除⼀个元素等。

实验报告学院: 信息工程学院专业: 计算机信息工程学院计算机实验中心制一实验内容实验1 抽象数据类型复数的实现二实验目的1. 了解抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉C语言语法及程序设计。

为以后章节的学习打下基础。

三需求分析复数抽象数据类型ADT的描述及实现。

[复数ADT的描述]ADT complex{数据对象：D={ c1,c2 c1,c2∈FloatSet }数据关系：R={ <c1,c2> c1, c2 ∈D }基本操作：创建一个复数 InitComplex();输出一个复数 OutComplex();求两个复数相加之和 AddComplex();求两个复数相减之差 SubComplex();求两个复数相乘之积 MulComplex();求两个复数的商 SComplex();等等;} ADT complex;本实验实现使用TC2.0实现复数的描述及操作。

具体实现要求：1．从键盘分别输入2个复数，并可修改已输入的复数。

2．能输出指定的复数。

3．两个复数相加之和，观察输出结果。

4．两个复数相加之差，观察输出结果。

5．求两个复数相乘之积，观察输出结果。

6.求两个复数的商，观察输出结果。

7．用户可看到如下界面：****************************** 1.输入复数C1 ** 2.输入复数C2 ** 3.输出复数C1 ** 4.输出复数C2 ** 5.求C1和C2的和 ** 6.求C1和C2的差 ** 7.求C1和C2的积 ** 8.求C1和C2的商 ** 0.结束 ******************************四详细设计步骤1：复数的抽象数据类型的定义。

步骤4：上机编程与调试#include "stdafx.h"#include "Complex0515.h"#include "user.h"int main(int argc, char* argv[]){int flag,flag1;float cr,ci,vr,vi;Complex c1,c2,C;CComplex0506 c;printf(" ***************************** \n");printf(" * 1.输入复数C1 * \n");printf(" * 2.输入复数C2 * \n");printf(" * 3.输出复数C1 * \n");printf(" * 4.输出复数C2 * \n");printf(" * 5.求C1和C2的和* \n");printf(" * 6.求C1和C2的差* \n");printf(" * 7.求C1和C2的积* \n");printf(" * 8.求C1和C2的商* \n");printf(" * 0.结束* \n");printf(" ***************************** \n");while(1){printf("请输入您的选择（0~8）:");scanf("%d",&flag);switch(flag){case 1:printf("请分别输入复数C1的实部和虚部（空格隔开）:");scanf("%f %f",&vr,&vi);break;case 2:printf("请分别输入复数C2的实部和虚部（空格隔开）:");scanf("%f %f",&cr,&ci);break;case 3:c.InitComplex(c1,vr,vi);printf("C1="); c.OutComplex(c1); //复数的初始化break;case 4:c.InitComplex(c2,cr,ci);printf("C2="); c.OutComplex(c2);break;case 5:c.AddComplex(C,c1,c2); //求两个复数的和printf("C1+C2="); c.OutComplex(C);break;case 6:c.SubComplex(C,c1,c2); //求两个复数的差printf("C1-C2="); c.OutComplex(C);break;case 7:c.MulComplex(C,c1,c2); //求两个复数的积printf("C1*C2="); c.OutComplex(C);break;case 8:c.SComplex(C,c1,c2); //求两个复数的商printf("C1/C2="); c.OutComplex(C);break;case 0:printf("结束\n");flag1=1;break;default:printf("输入不合法！\n");break;}//switchif(flag1==1) break;}//whilereturn 0;}运行结果：图1.1步骤五:实验总结1.通过本次实验，基本掌握抽象数据类型的定义方法及要求；2.基本掌握C语言程序设计的规范操作流程；3.编程过程中有些地方考虑不全面，程序不够健壮，；。

实验2 抽象数据类型的实现一、实验目的1.了解抽象数据类型（ADT）的基本概念及描述方法；2. 掌握抽象数据类型（ADT）的实现方法；3. 学会使用VC6.0建立工程（project）来组织程序。

二、预备知识1. C语言中数组、函数、结构体、指针的使用方法。

2. C语言中动态内存分配和释放方法（malloc和free库函数的使用）。

3. VC6.0集成开发环境使用方法，尤其是工程使用和程序调试方法。

4. 复数的基本知识及四则运算法则：设z1=a + bi，z2=c + di，（a，b，c，d∈R）加减法：z1±z2 =（a ±c）+（b ±d）i乘法：z1 * z2 =（ac - bd）+（ad + bc）i三、实例——三元组抽象数据类型实现1．三元组抽象数据类型的定义ADT Triplet{数据对象：D＝{e1, e2, e3| e1, e2, e3∈ElemSet (定义了关系运算的某个集合)} 数据关系：R1 = {<e1, e2>, <e2, e3>}基本操作：InitTriplet(&T, v1, v2, v3);操作结果：构造了三元组T，元素e1, e2和e3分别被赋以参数v1, v2和v3。

DestroyTriplet(&T);操作结果：三元组T被销毁。

Get(T, i, &e);初始条件：三元组T已存在，1≤i≤3；操作结果：用e返回T的第i元的值。

Put(&T, i, e);初始条件：三元组T已存在，1≤i≤3；操作结果：修改T的第i元的值为e。

IsAscending(T);初始条件：三元组T已存在；操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。

IsDescending(T);初始条件：三元组T已存在；操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。

Max(T, &e);初始条件：三元组T已存在；操作结果：用e返回T的三个元素中的最大值。

二叉树抽象数据类型数据结构实验报告数据结构实验报告题目：二叉树抽象数据类型的实现学院***学院专业*********年级班别***********学号***********学生姓名 *************指导教师成绩____________________2012年6月一．实验概要二叉树抽象数据类型的实现二.实验目的1.了解二叉树的定义以及各项基本操作。

2.实现二叉树存储、遍历及其他基本功能三. 实验仪器设备和材料Visual studio 2010四．实验的内容1.二叉树类型定义以及各基本操作的简要描述；ADT BinaryTree {数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D=∅，则R=,称BinaryTree为空二叉树；若D≠，则R={H}，H是如下二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠∅，则存在D-{root}={D1,Dr}，且D1∩Dr=∅；(3)若D1≠∅，则D1中存在惟一的元素x1，<root，x1>∈H，且存在Dr上的关系Hr∈H；H={<root，x1>，<root，xr>，H1,Hr}；(4)（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。

基本操作P:InitBiTree(&T);操作结果：构造空二叉树T。

DestroyBiTree(&T);初始条件：二叉树T存在。

操作结果：销毁二叉树T。

CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。

操作结果：按definition构造二叉树T。

ClearBiTree(&T);初始条件：二叉树T存在。

操作结果：将二叉树T清为空树。

BiTreeEmpty(T);初始条件：二叉树T存在。

淮海工学院计算机工程学院实验报告书课程名：数据结构题目：线性表的抽象数据类型的实现班级：D软件101学号：511021112姓名：丁冬梅评语：成绩：指导教师：批阅时间：2011年月日1实验题目或内容实验题目：一、顺序表的基本操作实现实验二、链表（带头结点）基本操作实验实验内容：一、按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中按照有序方式插入一已知字符元素；6）在线性表中删除第i个结点；7）计算链表的长度。

2目的与要求实验目的：1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。

实验要求：一、要求：数据元素类型ElemType取整型int。

按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3）在线性表中查找第i个元素，并返回其值；4）在线性表中第i个元素之前插入一已知元素；5）在线性表中删除第i个元素；6）求线性表中所有元素值（整数）之和；二、要求：数据元素类型ElemType取字符型char。

实验 报 告（华文中宋小初字居中，字间加一个空格）学 号： 20101453 指导教师： 刘 伟黑龙江工程学院教务处制SY-023一、实验目的1．熟悉抽象数据类型的表示和实现方法。

二、实验仪器设备、材料1．WindowsXP2．Visual C++ 6.0三、预习内容1．抽象数据类型的概念2．准备好相关的程序清单四、实验内容和步骤（1）由输入的实部和虚部生成一个复数；代码如下:#include "stdio.h"#include <iostream>using namespace std;typedef struct{double real;double imag;}Complex;Complex shengChengFuShu(){Complex c;cout<<"请输入实部："<<endl;cin>>c.real;cout<<"请输入虚部："<<endl;cin>>c.imag;return c;}void shuChuFuShu(Complex c){cout<<c.real<<"+"<<c.imag<<"i"<<endl;}void main(){Complex a;a = shengChengFuShu();shuChuFuShu(a);}(2)从已知复数中分离出实部和虚部代码如下：#include "stdio.h"#include <iostream>using namespace std;typedef struct{double real;double imag;}Complex;void initComplex(Complex &c, double re, double im) {c.real = re;c.imag = im;}Complex shengChengFuShu(){Complex c;cout<<"请输入实部："<<endl;cin>>c.real;cout<<"请输入虚部："<<endl;cin>>c.imag;return c;}double getReal(Complex c){return c.real;}double getimag(Complex c){return c.imag;}void shuChuFuShu(Complex c){cout<<c.real<<"+"<<c.imag<<"i"<<endl; }void main(){Complex a;a = shengChengFuShu();shuChuFuShu(a);cout<<getReal(a)<<endl;cout<<getimag(a)<<endl;}（3）两个复数求和，减法，乘法，除法，共轭代码如下：#include "stdio.h"#include <iostream>using namespace std;typedef struct{double real;double imag;}Complex;void initComplex(Complex &c, double re, double im) {c.real = re;c.imag = im;}Complex shengChengFuShu(){Complex c;cout<<"请输入实部："<<endl;cin>>c.real;cout<<"请输入虚部："<<endl;cin>>c.imag;return c;}Complex add(Complex c1, Complex c2){Complex c;c.real = c1.real + c2.real;c.imag = c1.imag + c2.imag;return c;}Complex jianfa(Complex c1, Complex c2){Complex c;c.real = c1.real -c2.real;c.imag = c1.imag- c2.imag;return c;}Complex chengfa(Complex c1, Complex c2){Complex c;c.real = c1.real * c2.real - c1.imag * c2.imag;c.imag = c1.real * c2.imag + c1.imag * c2.real;return c;}Complex chufa(Complex c1, Complex c2){ Complex c;c.real=((c1.real * c2.real)+(c1.imag * c2.imag))/(c2.real*c2.real+c2.imag*c2.imag);c.imag=(c1.imag*c2.real-c1.real*c2.imag)/(c2.real*c2.real+c2.imag*c2.imag);return c;}Complex gongE(Complex c1){Complex c;c.real=c1.real;c.imag=-1*c1.imag;return c;}void shuChuFuShu(Complex c){cout<<c.real<<"+"<<c.imag<<"i"<<endl;}void main(){ Complex c,b,a,d,f,h,j;a = shengChengFuShu();b=shengChengFuShu();c=add(a,b);shuChuFuShu(c);d=chengfa(a,b);shuChuFuShu(d);f= chufa(a,b);shuChuFuShu(f);h=jianfa(a,b);shuChuFuShu(h);j=gongE(a);shuChuFuShu(j);}2．测试数据注：1、此报告为参考格式，各栏项目可根据实际情况进行调整；2、“实验仪器设备”一栏：设计性实验根据实验条件对实验仪器设备提出具体要求；3、“实验内容或步骤”一栏：设计性实验需填写设计方案。

1.1 数据结构与算法的计算环境(实验估计时间：90分钟)1.1.1 背景知识除了进行科学计算之外，计算机已经被广泛地应用在控制、管理和数据处理等非数值计算的领域中。

与此相应，处理对象也由早先纯粹的数值发展到字符、表格和图形图像等各种具有一定结构的数据，这给计算机程序设计带来了新的问题。

为了编写一个“好”的程序，必须明确处理对象的特征及各对象之间的关系。

这就是“数据结构”这门学科形成和发展的背景。

任何实际问题只有建立了数学模型才可以被计算机计算，而数据结构就是实际问题中操作对象 (元素) 的数学抽象，算法则是建立和解决数学模型的方法。

数据结构用来反映计算机加工处理的对象，即数据的内部构成，即数据由哪几部分构成，以什么方式构成，呈什么样的结构等。

数据结构包括逻辑结构和物理结构。

这里的逻辑结构和物理结构是指一个事物的两个方面，而不是指两个不同的对象。

逻辑结构反映数据元素之间的逻辑关系，而物理结构反映了数据元素在计算机内部的存储安排，也称为存储结构。

数据结构是数据存在的形式，也是信息的一种组织方式，其目的是为了提高算法的效率。

数据结构通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

由于相同算法中的抽象数据类型用不同的数据结构来表示，会造成不同的执行效率，这就有必要来研究不同数据结构表示的效率差异及其适用场实验1 数据结构和算法分析基础2 数据结构与算法实验教程合。

1. 数据结构的研究对象数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

因此，主要有3个方面的内容，即数据的逻辑结构、数据的存储(物理) 结构和对数据的操作(或算法) 等。

通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的存储结构。

2. 数据结构的形式化定义数据是指由有限的符号(比如“0”和“1”，具有其自己的结构、操作和相应的语义) 组成的元素的集合。

结构是元素之间关系的集合。

通常来说，一个数据结构DS 可以表示为一个二元组：DS=(D, S)这里，D是数据元素的集合(或者是“结点”，可能还含有“数据项”或“数据域”) ，S是定义在D (或其他集合) 上的关系的集合，S = { R | R : D×D×...} ，称之为元素的逻辑结构。