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

发布网友发布时间：2023-10-11 17:03

共5个回答

热心网友时间：2024-11-02 04:21

#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);
}
}
}
兄弟我可是花了好长的时间写的啊，通过调试了！
我应该跟你一样都是学计算机专业的！
现在真的是好需要积分啊！麻烦你还是把你那诱人的分数给我吧！
我不胜感激啊！

热心网友时间：2024-11-02 04:22

我将你所说的抽象结构全部面向对象(类模板)实现，并将全部实现写入头文件（当然正常只会写入类接口，不会写实现）：
基元类：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

热心网友时间：2024-11-02 04:22

热心网友时间：2024-11-02 04:23

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