抽象数据的定义
//矩形ADT的定义 //抽象类型的定义 ADT Rectangle{ length;//数据对象，非负实数，矩形的长 // 非负实数，矩形的宽 init(&R,length,width);//将矩形的 R的长和宽分别初始化为lengthh和width area(R);//返回矩形R的面积 circumference(R);//返回矩形R的周长 }ADT Rectangle; //此处主义最后有一个分号 //矩形ADT的表示 //定义矩形的存储结构 typedef struct { float length;//矩形的长 float width; //矩形的宽 } Rectangle; bool init(Rectangle &R,float l,float w); float area(Rectangle &R,float l,float w); float circumference(Rectangle R); //矩形ADT的实现 bool init(Rectangle &R,float l,float w) { if(l>0&&w>0){ R.length=1; R.width=w; return true; } else return false; } float area(Restangle R) { return R.length*R.widdth; } float circumference(Rectangle R ) { return=2*(R.length+R.width);
线性表的抽象数据和ADT描述
//伪代码，仅仅是描述 ADT list{ D={ai|ai|∈eleSet,i=1,2，...,n,n≥0}// 数据对象 R={<ai-1，ai>||ai-1,ai∈D,i=2,...,n,n≥0}//数据关系 void initList(*L);//初始化线性表，构造线性表，表长为0 void insertList(*L,i,e);//在线性表的第i个元素之前插入一个元素 unsigned listLength(L);//求线性表的长度 eleType getElem(L,i);//获取线性表的第i个元素 void getElem2(L,i,*e);//获取线性表的第i个长度，放入 unsigned locateElem(L,e);//返回e在线性表中的位置 void listDelete(*L,i,*e);//删除线性表的第i个元素，将其值存放于变量e中 void printList(l,visit())//遍历线性表 int emptyList(L);//线性表判断空 void destroyList(*L); //销毁线性表 }ADT list;
静态分配的代码如下
//初始化线性表，静态分配 void initList(SList *L) { L->Selem=(eleType*)malloc(maxSize*sizeof(eleType)); if(!L->Selem)//如果没有分配成功 { exit(OVERFLOW)//退出程序 ，提示溢出 } L->length=0; return 0; }
//静态分配，编译时以确定数组的大小和位置，程序运行期间不变 #define maxSize 1000//顺序表的最大长度 typedef struct{//定义结构体类型 eleType Selem[maxSize];//线性表存储与数组Selem,一次性申请maxSize个数据元素所需的存储空间maxSize*sizeof(eleType个存储单元 unsigned length: //顺序表的当前长度，增删元素时需同步进行加减操作，length取值范围为0~maxSize-1 }Slist;//静态分配空间的顺序表的类型名为Slist //若length已等于maxSize,则不可以进行插入操作 //若length等于0，则不可以进行插入操作
动态分配定义
//动态分配08/07/19 14:37 #define initSize 1000//顺序表的初始长度 #define incSize 500//增大顺序表的存储空间时，每次的增长值 typedef struct { //定义结构体类型 eleType *Delem;//线性表存储与指向数组的指针Delem,当前数组并不存在，程序运行期间需要申请initSize*sizeof(eleTtype)个存储单元 unsigned length; //顺序表的当前长度，增删元素时需同步进行加减操作，length取值为不超过当前申请存储单元个数的无符号数 } Dlist; //动态分配空间的顺序表的类型名为Dlist //初始化时，为顺序表申请initSize个数据元素所需的连续存储空间，首地址存放于指针变量Delem //若length已等于 maxSize，进行插入操作前需执行realloc函数，这样既保留元岑胡志，又能为数组 重新申请更大的连续存储空间，每次增长500个数据元素所占的存储空间量 //若length已等于0，则不可以进行删除操作 Name: Copyright: Author: Date: 08/07/19 14:36 Description: */
静态插入处理，将e插入到线性表L的第i个元素之前
void initList(SList*L,unsigned i,eleType e) { if(L->Length==maxSize)//存储空间已满 exit(OVERFLOW);//退出程序，提示溢出 if(i<1||i<L->Length)//非法逻辑位置 exit(ERROR);//退出程序，提示位置出错 for(unsigned j=L->length-1;j>=i-1;j--) L->Selem[j+1]=L->Selem[j];//从表尾开始到插入位置，数据元素一次后移一个位置 L->Selem[i-1]=e;//e插入到第i个位置 L->length++;//表长加一 return 0; } void initList(SList*L,unsigned i,eleTtype e) { if(L->length==maxSize) exit(OVERFLOW); if(i<1||i>L->length) exit(ERROR); for(unsigned j=L->length-1;j>=i-1;j--) L->Selem[j+1]=L->Selem[j]; L->Selem[i-1]=e; L->length++; return 0; } void initList(Slist*L,unsigned i,eleTtype e) { if(L->length==maxSize) exit(OVERFLOW); if(i>L->length||i<1) exit(Error) for(unsigned j=L->length-1;j>=i-1;j--) L->Selem[j+1]=L->Selem[j]; L->Selem[i-1]=e; L->length++; return 0; }
动态分配的插入处理
//动态分配代码如下 void insertList(DList *l,unsigned i,eleType e) { if(L->length==intSize) { eleType *p; p=(eleType*)realloc(L->Delem,(initSize+incSize)sizeof(eleType));//这里的incSize是什么意思 //重新申请（iniSize+incSize)*sizeof(eleType）大小的存储空间，L->Delem中的L->length个数据元素赋值过来，新空间收地址为p if(!p) exit(OVERFLOW); L->Delem=p;//L->Delem指向新申请到的存储空间 L->length+=incSize;//表长修改为新的的存储空间可存放的数据元素个数 } if(i>L->Length||i<1) exit(ERROR)； for(unsigned j=L->length-1;j>=i-1;j--)//从表长开始到插入位置，数据元素依次后移一个位置 L->Delem[j+1]=L->Delem[j]; L->Delem[i-1]=e;//一定要记住 ，e插入到线性表的的第i个位置 return 0;//为什么这里不需要线性表的长度加一 } /*realloc函数用于修改一个原先已经分配的内存块的大小， 可以使一块内存的扩大或缩小。当起始空间的地址为空，即*ptr = NULL, 则同malloc。当*ptr非空：若nuw_size < size,即缩小*ptr所指向的内存空间， 该内存块尾部的部分内存被拿掉，剩余部分内存的原先内容依然保留； 若nuw_size > size,即扩大*ptr所指向的内存空间， 如果原先的内存尾部有足够的扩大空间，则直接在原先的内存块尾部新增内存， 如果原先的内存尾部空间不足，或原先的内存块无法改变大小， realloc将重新分配另一块nuw_size大小的内存，并把原先那块内存的内容复制到新的内存块上。 因此，使用realloc后就应该改用realloc返回的新指针。*/