#include
using namespace std; //常量值定义 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 #define UNDERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 //函数返回值类型定义 typedef int Status; //数据元素类型定义 typedef int ElemType; //顺序表结构定义 typedef struct{ ElemType *elem; int length; int listsize; }SqList; //辅助函数的声明bool compare( ElemType, ElemType );//比较两个元素,看是否满足指定的条件 typedef bool (*pCompare)( ElemType, ElemType ); //函数指针 Status output( ElemType );//输出数据元素 typedef Status (*pOutput)( ElemType ); //顺序表基本操作的声明 Status InitList( SqList& );//初始化顺序表 Status DestroyList( SqList& );//销毁顺序表 Status ClearList( SqList& );//清空顺序表 bool ListEmpty( SqList& );//判断顺序表是否为空 int ListLength( SqList& );//获取顺序表的长度 Status GetElem( SqList&, int, ElemType& );//随机访问顺序表中的元素 Status LocateElem( SqList&, ElemType, int&, pCompare );//按指定的规则在顺序表中查找元素 Status PriorElem( SqList&, ElemType, ElemType& );//返回指定元素的前驱Status NextElem( SqList&, ElemType, ElemType& );//返回指定元素的后继Status ListInsert( SqList&, int, ElemType );//在顺序表中的指定位序的元素之前插入一个元素Status ListDelete( SqList&, int, ElemType& );//删除顺序表中指定位序的元素,并返回该元素Status ListTraverse( SqList&, pOutput );//遍历顺序表,并将每个数据元素输出bool compare(ElemType e1, ElemType e2) //操作结果:比较e1和e2是否相等,若相等,返回TRUE;否则,返回FALSE
{ if(e1==e2) return TRUE; else return FALSE; } Status output( ElemType e ) //操作结果:将e在屏幕上输出 { cout<<e<<" "; return OK; } Status InitList( SqList &L ) //操作结果:构造一个空的线性表L,按照指定的大小分配存储空间 { L.elem =( ElemType* )malloc( LIST_INIT_SIZE * sizeof( ElemType ) ); if( L.elem == NULL ) { cout<<"顺序表初始化失败"<<endl; exit( OVERFLOW ); } L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; } Status DestroyList( SqList &L ) //初始条件:线性表L已存在 //操作结果:销毁线性表 { free( L.elem ); L.elem = NULL; L.length=0; L.listsize=0; return OK; } Status ClearList( SqList &L ) //初始条件:线性表L已存在 //操作结果:将L置为空表 { free( L.elem ); L.elem=( ElemType* )malloc( LIST_INIT_SIZE * sizeof( ElemType ) );//重新分配预设的LIST_INIT_SIZE大小的存储空间 if( L.elem==NULL ) { cout<<"存储空间分配失败"<<endl; return ERROR; } L.length=0; L.listsize = LIST_INIT_SIZE; return OK; } bool ListEmpty( SqList &L ) //初始条件:线性表L已存在 //操作结果:若L为空表,则返回TRUE;否则,返回FALSE { if( L.length != 0 ) return FALSE; else return TRUE; } int ListLength( SqList &L ) //初始条件:线性表L已存在 //操作结果:返回L中数据元素的个数 { return L.length; } Status GetElem( SqList &L, int index, ElemType &e ) //初始条件:线性表L已存在,1<=index<=ListLength(L) //操作结果:用e返回L中第index个数据元素的值 { if( (index < 1 ) || ( index>L.length ) ) { cout<<"查找位置不合理!"<<endl; return ERROR; } e=L.elem[index-1]; return OK; } Status LocateElem( SqList &L, ElemType e, int &pos, pCompare comFun) //初始条件:线性表L已存在,comFun是指向compare()函数的指针 //操作结果:返回L中第1个与e满足关系compare()的数据元素的位置。若这样的数据元素 //不存在,返回ERROR { int i=0; for(;(i < L.length) && (comFun(e,L.elem[i])==FALSE);i++) ; //循环体为空 if( i>L.length-1 ) { cout<<"未找到元素"<<endl; return ERROR; } else { pos=i; return OK; } } Status PriorElem( SqList &L, ElemType e, ElemType &priElem) //初始条件:线性表L已存在 //操作结果:若e是L的数据元素,且不是第一个,则用priElem返回它的前驱,否则,操作失败。 { int i; if( LocateElem( L, e, i, compare )==ERROR) return ERROR; if(i==0) { cout<<"该元素不存在前驱"<<endl; return ERROR; } priElem = L.elem[i-1]; return OK; } Status NextElem( SqList &L, ElemType e, ElemType &nextElem) //初始条件:线性表L已存在 //操作结果:若e是L的数据元素,且不是最后一个,则用nextElem返回它的后继,否则,操作失败 { int i; if(LocateElem( L, e, i, compare )==ERROR) return ERROR; if( i== L.length-1 ){ cout<<"该元素不存在后继"<<endl; return ERROR; } nextElem=L.elem[i+1]; return OK; } Status ListInsert( SqList &L, int index,ElemType e) //初始条件:线性表L已存在,1<=i<=ListLength(L)+1 //操作结果:在L中的第index个元素之前插入新的数据元素e,L的长度加1 { if((index<1) || (index>L.length+1)){ cout<<"插入的位置不合理"<<endl; return ERROR; } if(L.length>=L.listsize){ ElemType *newbase=(ElemType*)realloc( L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(newbase==NULL){ cout<<"增量存储空间分配失败"<<endl; exit(OVERFLOW); } else{ L.elem = newbase; L.listsize += LISTINCREMENT; } } //移动元素 int i = L.length; for(; i>index-1 ;i--) L.elem[i]=L.elem[i-1]; //插入元素 L.elem[index-1]=e; //修改表长 L.length++; return OK; } Status ListDelete( SqList &L, int index, ElemType &e) //初始条件:线性表L已存在且非空,1<=i<=ListLength(L) //操作结果:删除L的第index个元素,并用e返回其值,L的长度减1 { if((index<1) || (index>L.length)){ cout<<"删除的位序不合理"<<endl; return ERROR; } if( L.length == 0 ){ cout<<"顺序表为空,删除错误"<<endl; exit(UNDERFLOW); } e=L.elem[index-1]; int i=index-1; for(;i L.elem[i]=L.elem[i+1]; //修改表长 L.length--; return OK; }Status ListTraverse( SqList &L, pOutput outFun)
//初始条件:线性表L已存在 //操作结果:依次对L的每个数据元素调用函数output()。 { if(L.length == 0){ cout<<"顺序表为空,遍历失败"<<endl; return ERROR; } for(int i=0;i outFun( L.elem[i] ); cout<<endl; return OK; }