抽象数据类型定义的具体函数实现（C++实现）

几种数据结构的抽象数据类型定义
1、线性表的抽象数据类型定义
ADT List{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }
基本操作：
InitList( &L )
操作结果：构造一个空的线性表L。
DestroyList( &L )
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList( &L )
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListEmpty( L )
初始条件：线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE。
ListLength( L )
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
GetElem( L, i, &e )
初始条件：线性表L已存在，1≤i≤ListLength(L)。
操作结果：用e返回L中第i个数据元素的值。
LocateElem( L, e, compare() )
初始条件：线性表L已存在，compare()是数据元素判定函数。
操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
PriorElem( L, cur_e, &pre_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem( L, cur_e, &next_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
ListInsert( &L, i, e )
初始条件：线性表L已存在，1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete( &L, i, &e )
初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
ListTraverse( L, visit() )
初始条件：线性表L已存在。
操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT List

2、栈的抽象数据类型定义
ADT Stack{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }
约定an端为栈顶，a1端为栈底。
基本操作：
InitStack( &S )
操作结果：构造一个空栈S。
DestroyStack ( &S )
初始条件：栈S已存在。
操作结果：销毁栈S。
ClearStack( &S )
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty( S )
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。
StackLength( S )
初始条件：栈S已存在。
操作结果：返回S的数据元素个数，即栈的长度。
GetTop( S, &e )
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push( &S, e )
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop( &S, &e )
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse( S, visit() )
初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT Stack
就是以上所列函数的定义

我是一个菜鸟，这个问题对我来说很麻烦，还请大侠们帮帮忙，小弟在此谢过！！！

举报该问题

推荐答案 2010-03-30

#include<iostream>
#define ok 1
#define error 0
using namespace std;
typedef int status;
typedef struct Lnode
{
float coef;
int expn;
struct Lnode*next;
}*link;
typedef struct
{
link head,tail;
int len;
}polynomail;
extern status makenode(link&p,int e,float f)
{
p=(link)malloc(sizeof(Lnode));
if(!p)return error;
p->coef=f;
p->expn=e;
return ok;
}//生成一个节点
void freenode(link &p){free(p);}//释放一个节点
status initlist(polynomail &p)
{
p.head=p.tail=NULL;
p.len=0;
return ok;
}//初始化一个线性表
extern status insfirst(polynomail &p,link h,link s)
{
s=(link)malloc(sizeof(Lnode));if(!s)return error;
h=(link)malloc(sizeof(Lnode));if(!h)return error;
h=p.head;
s->next=h->next;
h->next=s;
return ok;
}//已知h指向线性表的头结点，将s所指节点插入在第一个节点之前
extern status delfirst(polynomail &p,link h,link &q)
{
q=(link)malloc(sizeof(Lnode));if(!q)return error;
h=(link)malloc(sizeof(Lnode));if(!h)return error;
h=p.head;
q=h->next;
h->next=q->next;
free(q);
return ok;
}//删除线性表第一个节点
extern status append(polynomail &p,link s)
{
p.tail->next=s;
while(s->next){s=s->next;}
p.tail=s;
return ok;
}//将指针s所指的一串节点链接在线性表的末尾，并改变表的尾指针
extern status remove(polynomail &p,link &q)
{
link s;
s=(link)malloc(sizeof(Lnode));
if(!s)return error;
s=p.head;
while(s->next!=p.tail){s=s->next;}
q=p.tail;
free(q);
p.tail=s;
return ok;
}//删除尾节点并以q返回，然后改变链表尾指针的指向
extern status insbefore(polynomail &p,link &q,link s)
{
link h;
s=(link)malloc(sizeof(Lnode));if(!s)return error;
h=(link)malloc(sizeof(Lnode));if(!h)return error;
h=p.head;
while(h->next!=q){h=h->next;}
s->next=q;
h->next=s;
q=s;
return ok;
}//在q所指节点之前插入一个节点
extern status insafter(polynomail &l,link &p,link s)
{
s->next=p->next;
p->next=s;
p=s;
return ok;
}//在P所指节点之后插入一个节点
extern status SetCurElem(link &p,int e,float f)
{
p->coef=f;
p->expn=e;
return ok;
}//设置节点的值
extern link GetCurElem(link p)
{
return p;
}//返回一个指向节点的指针
extern status listempty(polynomail p)
{
if(p.head==p.tail)
return ok;
else return error;
}//判断线性表是否为空
extern int listlength(polynomail p)
{
return(p.tail-p.head+1);
}//求线性表的长度
extern link GetHead(polynomail p)
{
return p.head;
}
extern link GetTail(polynomail p)
{
return p.tail;
}
extern link priorpos(polynomail l,link p)
{
link q;
q=(link)malloc(sizeof(Lnode));if(!q)return error;
q=l.head;
while(q->next!=p){q=q->next;}
if(q->next==p)return q;
else return NULL;
}//返回p节点前驱的位置
extern link nextpos(polynomail l,link p)
{
link q;
q=(link)malloc(sizeof(Lnode));if(!q)return error;
if(!p->next)return NULL;
return p->next;
}//返回p节点后继的位置
extern status locatepos(polynomail l,int i,link &p)
{
link q;
q=(link)malloc(sizeof(Lnode));if(!q)return error;
q=l.head->next;
int j=1;
while(q&&j<i)
{
q=q->next;
j++;
}
p=q;
if(!q||j>i)return error;
else return ok;
}//返回p所指的第i项的地址
extern int compare(link p,link q)
{
if(p->expn>q->expn)return 1;
if(p->expn<q->expn)return -1;
if(p->expn==q->expn)return 0;
}
extern link locateelem(polynomail p,link m,link &q,link &h,int(*cmp)(link a,link b))
{
q=(link)malloc(sizeof(Lnode));if(!q)return error;
h=(link)malloc(sizeof(Lnode));if(!h)return error;
cmp=compare;//函数指针的赋值
for(q=p.head->next;q->next!=NULL;q=q->next)
{
int n; n=(*cmp)(m,q);
if(n==0)
{
return q;
}
}
for(h=p.head->next;h->next!=NULL;h=h->next)
{
int n; n=(*cmp)(m,h);
if(n>0)
{
return priorpos(p,h);
}
}
}
兄弟我可是花了好长的时间写的啊，通过调试了！
我应该跟你一样都是学计算机专业的！
现在真的是好需要积分啊！麻烦你还是把你那诱人的分数给我吧！
我不胜感激啊！

温馨提示：答案为网友推荐，仅供参考

当前网址：http://99.wendadaohang.com/zd/WezjBOvvX.html

其他回答

第1个回答 2010-04-01

我将你所说的抽象结构全部面向对象(类模板)实现，并将全部实现写入头文件（当然正常只会写入类接口，不会写实现）：
基元类：ElemSet<T>
链表类：List<T>
栈类：Stack<T>
直接在你的工程中包括这些头文件就能用了

#ifndef ELEMSET
#define ELEMSET

#include <iostream>
using namespace std;

template <typename T>
class ElemSet //数据对象
{
T data;
public:
ElemSet<T>* next;

ElemSet():next(NULL){}
ElemSet(T d):data(d),next(NULL){}
ElemSet(const ElemSet<T>& e):data(e.data),next(NULL){}
void operator=(const ElemSet<T>& e){data=e.data;next=NULL;}

const T& read(){return data;}
bool compare(ElemSet<T> t)
{
return data==t.data;
}
void visit()
{
if(!(cout<<data)) throw "错误";
}
};

#endif

#ifndef LIST
#define LIST

#include <iostream>
#include "ElemSet.h"
using namespace std;

template <typename T>
class List
{
ElemSet<T>* first; //头指针
public:
List() //就是你说的InitList()
{
first=new ElemSet<T>;
first->next=NULL;
}
~List() //就是说的DestroyList()
{
while(first)
{
ElemSet<T>* p=first;
first=first->next;
delete p;
}
}
void Clearlist()
{
while(first->next)
{
ElemSet<T>* p=first;
first=first->next;
delete p;
}
}
bool ListEmpty()
{
return first->next==NULL;
}
int ListLength()
{
int count=0;
for(ElemSet<T>* p=first->next;p;p=p->next)
count++;
return count;
}
void GetElem(int num,ElemSet<T>& e)
{
ElemSet<T>* p=first;
for(;num;num--)
{
if(!(p=p->next)) throw "位置错误";
}
e=*p;
}
int LocateElem(const ElemSet<T>& t)
{
int loc=1;
for(ElemSet<T>* p=first->next;p;p=p->next)
{
if(p->compare(t)) return loc;
loc++;
}
return 0;
}
void PriorElem(const ElemSet<T>& cur_e,ElemSet<T>& pre_e)
{
if(first->next->compare(cur_e)) throw "第一个元素无前驱";
for(ElemSet<T>* p=first->next;p->next;p=p->next)
{
if(p->next->compare(cur_e))
{
pre_e=*p;
return;
}
}
throw "位置超限";
}
void NextElem(const ElemSet<T>& cur_e,ElemSet<T>& next_e)
{
for(ElemSet<T>* p=first->next;p->next;p=p->next)
{
if(p->compare(cur_e))
{
next_e=*(p->next);
return;
}
}
throw "链表没有该元素，或该元素没有后继";
}
void ListInsert(int i,const ElemSet<T>& e)
{
if(i<1) throw "位置错误";
ElemSet<T>* p=first; //找到待插入位置的前一个元素
for(;i>1;i--)
if(!(p=p->next)) throw "位置错误";
ElemSet<T>* t=new ElemSet<T>(e);
t->next=p->next;
p->next=t;
}
void ListDelete(int i,ElemSet<T>& e)
{
if(i<1) throw "位置错误";
ElemSet<T>* p=first; //找到待删除位置的前一个元素
for(;i>1;i--)
if(!(p=p->next)) throw "位置错误";
ElemSet<T>* t=p->next;
if(!t) throw "位置错误";
p->next=t->next;
e=*t;
delete t;
}
void ListTraverse()
{
for(ElemSet<T>* p=first->next;p;p=p->next)
{
p->visit();
cout<<' ';
}
cout<<endl;
}
};

#endif

#ifndef STACK
#define STACK

#include <iostream>
#include "ElemSet.h"
using namespace std;

template <typename T>
class Stack
{
ElemSet<T>* top;
public:
Stack<T>():top(NULL){} //就是你说的InitStack()
~Stack<T>() //就是你说的DestroyStack()
{
while(top)
{
ElemSet<T>* p=top;
top=top->next;
delete p;
}
}
void Clearlist()
{
while(top)
{
ElemSet<T>* p=top;
top=top->next;
delete p;
}
}
bool StackEmpty()
{
return !top;
}
int StackLength()
{
int n=0;
for(ElemSet<T>* p=top;p;p=p->next)
n++;
return n;
}
void GetTop(ElemSet<T>& e)
{
if(!top) throw "当前栈为空";
e=*top;
}
void Push(const ElemSet<T>& e)
{
ElemSet<T>* p=new ElemSet<T>(e);
p->next=top;
top=p;
}
void Pop(ElemSet<T>& e)
{
if(!top) throw "当前栈为空";
e=*top;
ElemSet<T>* p=top;
top=top->next;
delete p;
}
void StackTraverse() //从栈底到栈顶依次对S的每个数据元素调用函数visit()
{
if(!top) throw "当前栈为空";
Stack<ElemSet<T>*> t;
for(ElemSet<T>* p=top;p;p=p->next)
t.Push(p);
ElemSet<ElemSet<T>*> te;
for(t.Pop(te);!t.StackEmpty();t.Pop(te))
{
te.read()->visit();
cout<<' ';
}
te.read()->visit();
cout<<endl;
}
};

#endif

第2个回答 2016-01-02

第3个回答 2016-02-06

第4个回答 2015-12-07

抽象数据类型函数实现在子类中

相似回答

C语言设计实现抽象数据类型"有理数"基本操作包括有理数的加法,减法,乘 ...答：分数的数据类型是很简单的。另外，求有理数的分子，分母的问题，因为给的有理数只能是有限小数，所以根本没有疑问。但是如果改成：求分子分母之和最小的，在一定误差范围内的分数，这个问题才有价值比如：0.3333333，如果误差为1e-4 那么1/3明显要比333333/10000000 下面给出一个实现(C++)：struct...

c++程序设计题(复数类设计与实现)答：1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3...

什么是抽象数据类型?答：抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。比如说类就是一种抽象数据类型，类是由已有的数据类型来实现的。如复数类型：//在头文件complex.h中定义的复数类 ifndef _complex_h_define _complex_h_include <iostream.h> class complex { public:complex ( ){ Re ...

编写程序,实现双链表的抽象数据类型,并进行测试答：这是我写的C++代码，看行不行！include <iostream> using namespace std;/*双向链表类型定义*/ typedef struct duNode { char data;struct duNode *prior;struct duNode *next;}duNode;typedef duNode *duLinklist;//指针类型，故访问它的成员用“->”。/*初始化双向链表*/ void initLinklist_...

c++ split答：在c++中，其实是没有java与python中定义的split（）功能的函数，若是需要处理字符串的话可以试着采用其他方式，比如可以利用STL自己实现split函数。c++介绍：C++是属于C语言的继承，它既能够进行C语言的过程化程序设计，还能够进行以抽象数据类型为特点的基于对象的程序设计，当然也可以进行以继承与多态为...

c++开根号函数怎么用?答：c++开根号函数：起始文件：math.h，声明：double sqrt(double n)，完了是功能：n开平方后，得到算数平方根返回，形式：sqrt(100)，为计算100的平方根。C++不仅拥有计算机高效运行的实用性特征，同时还致力于提高大规模程序的编程质量与程序设计语言的问题描述能力。

c++类的定义与使用答：具体如下。C++是一款面向对象的编程语言，而使用类来进行数据隐藏，将函数当做接口，是一种面型对象很有效的实现方法。类的定义与结构体有些类似，用关键字c类对象的默认访问控制为privite型，因此在定义时，我们可以省略privite符号，上例为了表示清晰故加上了privite。在源文件中定义函数时，需要加上...

怎样写一个抽象数据类型!答：要写一个两个数相加的函数 int add(int a,int b)，可以看到，这个函数只支持int 类型，float,double等类型就不能用这个函数了，只能再写一个 float addf(float a,float b)。这样代码的重用性能不好。到了C++就有模版的出现了就是定义一个模版，传入参数类型是不定时，就可以定义为模版。你的...

如何用C++编写一个航空售票系统?答：include<iostream>#include<string>#include<fstream>#include<sstream>using namespace std;class Tair //通过定义一个类来定义数据录入的函数编写一个航空售票系统。一、C++是C语言的继承，它既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态...

大家正在搜

数据结构抽象数据类型定义抽象数据类型的定义什么意思抽象数据类型的定义有哪几部分组成抽象数据类型定义的格式为抽象数据类型的定义包括抽象数据类型三元组的定义抽象数据类型的定义包括哪些方面线性表的抽象数据类型定义图的抽象数据类型定义