已解决问题 - 浏览534次
下一个已解决问题
yangfengzhou
抽象数据类型怎么写啊!!!?
最近做的一个作业,报告上要求写出抽象数据类型,不会写啊,各位帮帮忙啊!!!
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define RD 10 //待排序数为十进制
#define D 3 //记录数为三位数
#define NUM 21
typedef struct //记录类型定义
{
int key[D]; //子关键字数组
int data; //数据项
int next; //静态链域
}node;
node r[NUM];
typedef struct //静态链表
{
node r[NUM];
int length;
}Slinklist;
typedef struct
{
node data[20];
int head,tail;
}sequeue;
sequeue *sq[RD];
sequeue Queue[RD]; //定义十个队列
void print() //打印测试数据
{
int i;
for(i=1;i<NUM;i++)
{
cout<<r[i].data<<" ";
if(i%10==0) cout<<endl;
}
cout<<endl;
}
void shouji(int i) //将RD个队列中的非空队列首尾相接,链接成一个新的链表
{
int j,t=1;
for(j=0;j<RD;++j) //找到非空队并串接
{
while(sq[j]->tail!=sq[j]->head)
{
r[t].key[0]=sq[j]->data[sq[j]->head].key[0];
r[t].key[1]=sq[j]->data[sq[j]->head].key[1];
r[t].key[2]=sq[j]->data[sq[j]->head++].key[2];
r[t].data=r[t].key[2]+(10*r[t].key[1])+(100*r[t].key[0]);
r[t].next=t+1;
t++;
}
}
r[t].next=0;
cout<<"第"<<-(i-2)<<"趟分配收集后的数据:"<<endl;
print();
}
void feipei(int i) //第I趟分配,按关键字key[i]相同的分配在一组
{
int j,p;
for(j=0;j<=RD-1;++j) //将RD队列初始化为空队
{
sq[j]=&Queue[j];
sq[j]->head=0;
sq[j]->tail=0;
}
p=1; //p指向链表的第一个记录
while(p<NUM) //将相应数据按关键字放入队列中
{
j=r[p].key[i];
sq[j]->data[sq[j]->tail].data=r[p].data;
sq[j]->data[sq[j]->tail].key[0]=r[p].key[0];
sq[j]->data[sq[j]->tail].key[1]=r[p].key[1];
sq[j]->data[sq[j]->tail++].key[2]=r[p].key[2];
p++;
}
shouji(i);
}
void jspx() //基数排序
{
int i;
for(i=D-1;i>=0;--i) //从最低位子关键字开始,进行D趟分配和收集
{
feipei(i);
}
}
void main()
{
int i,length=NUM-1;
for(i=1;i<NUM;i++) //初始化数据r[]
{
cout<<"请输入第"<<i<<"个数据:"<<endl;
cin>>r[i].data;
r[i].key[0]=(r[i].data/100);
r[i].key[1]=((r[i].data%100)/10);
r[i].key[2]=((r[i].data%100)%10);
r[i].next=i+1;
}
print();
r[0].next=1;
r[NUM].next=0;
jspx();
print();
cou
panda最佳答案 - 由投票者2008-01-30 15:32:14选出
数据结构、数据类型和抽象数据类型，这三个术语在字面上既不同又相近，反映出它们在含义上既有区别又有联系。
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。
v数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。Pascal语言所定义的数据类型的种类如图1-8所示。
其中，简单数据类型对应于简单的数据结构;构造数据类型对应于复杂的数据结构;在复杂的数据结构里，允许成分数据本身具有复杂的数据结构，因而，构造数据类型允许复合嵌套;指针类型对应于数据结构中成分数据之间的关系，表面上属简单数据类型，实际上都指向复杂的成分数据即构造数据类型中的数据，因此这里没有把它划入简单数据类型，也没有划入构造数据类型，而单独划出一类。
数据结构反映数据内部的构成方式，它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。
由于指针数据的引入，使构造各种复杂的数据结构成为可能。按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。 由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。
最常用的数据结构是数组结构和记录结构。数组结构的特点是：
成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。
每一个成分数据具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。
所有的成分数据被依序安排在一片连续的存储单元中。
概括起来，数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这种结构有这些良好的特性，所以最常被人们所采用。在高级语言中，与数组结构相对应的数据类型是数组类型，即数组结构的数据变量必须说明为array [i] of T0 ，其中i是数组结构的下标类型，而T0是数组结构的基类型。
记录结构是另一种常用的数据结构。它的特点是:
与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。
不同的域允许有不同的结构，因而允许属于不同的数据类型。
与数组结构一样，它们可以随机访问，但访问的途径靠的是域名。
在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。
抽象数据类型的含义在上一段已作了专门叙述。它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算(过程或函数)。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。
其他回答(1)
-
抽象数据类型
(Abstract Data Type 简称ADT)
是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
抽象数据类型描述的一般形式如下：
ADT 抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名1：
……
……
操作名n：
}ADT抽象数据类型名称
抽象数据类型定义（ADT）
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。
