数据结构讲义第1章.ppt

wsx wsx ADT 抽象数据类型名{ 数据对象：参数表 数据关系：数据关系的定义 基本操作：基本操作的定义 }ADT 抽象数据类型名 抽象数据类型一般定义： 其中，数据对象和数据关系的定义用伪码表示，基本操作的定义格式为: 基本操作名（参数表） 初始条件：初始条件描述 操作结果： 操作结果描述 基本操作的参数两种形式：赋值参数只为操作提供输入值；引用参数以打头，除可提供输入值外，还将返回操作结果。 例 抽象数据类型三元组的定义 ADT Triplet{ 数据对象：D={e1,e2,e3|e1,e2,e3?ElemSet} 数据关系：R={e1,e2,e2,e3} 基本操作： InitTriplet(T,v1,v2,v3) 操作结果：构造三元组T，元素e1,e2和e3分别 被赋值参数v1,v2和v3的值。 DestroyTriplet(T) 操作结果：三元组T被销毁。 Get(T,i,e) 初始条件：三元组T已存在， 操作结果：用e返回T的第i个元素值。 Put(T,i,e) 初始条件：三元组T已存在， 操作结果：改变T的第i个元素值e。 … }ADT Triplet 1.3 抽象数据类型的表示与实现 例：线性表的实现： ADT List{ 数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n=0} 数据关系: R1={ai-1,ai| ai-1,ai(- D,i=2,...,n} 基本操作： InitList(L) DestroyList(L) ListInsert(L,i,e) ListDelete(L,i,e) }ADT List ListInsert(List L,int i,ElemType e) { if(i1||iL.length) return ERROR; q=(L.elem[i-1]); for(p=(L.elem[L.length-1]);p=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } 下面我们以抽象数据类型Triplet（三元组）的表示与实现为例说明此问题。 float *InitTriplet(float v1,float v2,float v3) { float *T; T=(float *)malloc(sizeof(float)*3); T[0]=v1;T[1]=v2;T[2]=v3; return T; } Status InitTriplet(Triplet T,Elemtype v1, Elemtype v2, Elemtype v3) { //构造三元组T，依次置T的三个元素的初值为V1,V2,V3。 T=（ElemType *)malloc(3*sizeof(ElemType));//分配3个元素的存储空间 if(!T) exit(OVERFLOW);//分配存储空间失败 T[0]=v1; T[1]=v2; T[2]=v3; return OK; }//InitTriplet DestroyTriTlet(float *T) { free(T); T=NULL; return 1; } Put(float *T,int i,float *e) { if(i1||i3) return 0; T[i-1]=*e; return 1; } Get(float *T,int i,float *e) { if(i1||i3) return 0; *e=T[i-1]; return 1; } IsAscending(float *T) { return(T[0]T[1] T[1]T[2]); } Status DestroyTriplet(Triplet T) { //销毁三元组 free(T); T=NULL; return OK; }//DestroyTriplet Status Get(Triplet T,int i,ElemType e) {//1=i=3,用e返回T的第i元的值 if(i1||i3) return ERROR; e=T[i-1]; return OK; }//Get Status Put(Triplet T,int i,ElemType e) {//1=