顺序头文件
//c2-1.h线性表的动态分配顺序存储结构
#define LIST_INI_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LIST_INCREMENT 2 //线性表存储空间的分配增量
struct SqList{
ElemType *elem; //存储空间基址--未定义可以声明吗？
int length; //当前线性表的长度
int listsize; //当前分配的存储空间容量(以sizeof(ElemType)为单位)
};
顺序表基本方法
//bo2-1.cpp顺序表示的线性表的基本操作（12个）
//存储结构由c2-1.h定义
//构造一个空的顺序线性表
void InitList(SqList &L){
L.elem = (ElemType *) malloc(LIST_INI_INIT_SIZE*sizeof(ElemType));
if(!L.elem){
exit(OVERFLOW);
}
L.length=0;
L.listsize=LIST_INI_INIT_SIZE;
}
- //顺序线性表L已存在。
- //销毁顺序线性表L
void DestoryList(SqList &L){
free(L.elem); //free释放malloc申请的空间,并不改变指针的值，本质上就是做了一些标记而已，所以指针及空间内容都还是存在的，只不过有隐患罢了。
L.elem=NULL;
L.length=0;
L.listsize=0;
}
- //线性表L已存在，将L重置为空表
void ClearList(SqList &L){
L.length = 0;
}
- //顺序线性包L已存在，判断表是否是空表
- //为空表返回TRUE，否则返回FALSE
Status ListEmpty(SqList L){
if(L.length==0){
return TRUE;
} else{
return FALSE;
}
}
- //L存在，返回L中元素个数
int ListLength(SqList L){
return L.length;
}
- //如果顺序线性表L已存在，1<=i<=ListLength(L)
- //用e返回L中第i个元素的值
- //并用return 返回函数的值是否存在
Status GetElem(SqList L, int i, ElemType &e){
if(i<1 || i>L.length)
return ERROR;
e=*(L.elem+i-1);
return OK;
}
- //初始条件：顺序线性表L已存在，compare()是数据元素判断函数（满足为1，否则为0）
- //操作结果：返回L中第1个与e满足compare()的数据元素的位序
- //若这样的数据元素不存在，则返回值为0.
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType,ElemType)){
ElemType *p;
int i=1;
p=L.elem;
while(i<=L.length && !compare(*p++,e)){
i=i+1;
}
if(i<=L.length)
return i;
else
return 0;
}
- //顺序线性表L已存在，1<=i<=ListLength(L)+1
- //在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(SqList &L,int i,ElemType value){
ElemType *newbase,*q,*p;
if(i<1 || i>L.length+1) { //i值不合法
return ERROR;
}
//当前的存储空间已满，增加分配
if(L.length>=L.listsize){
newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)* sizeof(ElemType));
if(!newbase)
exit(OVERFLOW); //分配存储空间失败，退出程序
L.elem=newbase; //新基址
L.listsize+=LIST_INCREMENT; //每次增加两个空间
}
// p=L.elem;
// q=L.elem+L.length;
// while (q>(p+i)){
// *q=*(q-1);
// q=q-1;
// }
// *q=value;
q=L.elem+i-1; //当前插入位置
for(p=L.elem+L.length;p>q;p--){ //插入位置之后的元素右移
*p=*(p-1);
}
*q=value; //插入元素value
L.length++; //表长增加1
return OK;
}
- //顺序表L已存在
- //若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱值
- //否则操作失败，pre_e无定义
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){
int i=2;
ElemType *p=L.elem+1;
//找到cur_e元素
while (i<=L.length&&*p!=cur_e){
p++;
i++;
}
if(i>L.length)
return INFEASIBLE; //操作失败
else{
pre_e = *--p;
return OK;
}
}
- //顺序表L已存在
- //若cur_e是L的数据元素，且不是第一个，则用next_e返回它的前驱值
- //否则操作失败，next_e无定义
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e){
int i=1;
ElemType *p=L.elem;
//找到cur_e元素
while(i<L.length-1&&*p!=cur_e){
p++;
i++;
}
if(i>L.length-1){
return INFEASIBLE; //未找到该元素
}else{
next_e=*++p; //赋值给返回值
return OK;
}
}
- //顺序线性表L已存在，1<=i<=ListLength(L)
- //删除L的第i个元素，并用e返回其值，L的长度减1
Status ListDelete(SqList &L, int i, ElemType &e){
ElemType *q,*p;
if(i<1 || i>L.length){ //i值不合法
return ERROR;
}
p=L.elem+i-1; //p为被删除元素的位置
e=*p; //被删除元素值赋给e
q=L.elem+L.length-1; //表尾元素的位置
while(p<q){ //被删除元素之后的元素左移
*p=*(p+1);
p++;
}
L.length--; //表长减1
return TRUE;
}
- //依次对L的每个元素调用函数vi()
- //vi()的形参加'&'，表明可通过调用vi()改变元素的值
void ListTraverse(SqList L, void(*vi)(ElemType&)){
ElemType *p;
int i;
p=L.elem;
for(i=1;i<L.length;i++){
vi(*p++);
}
printf("\n");
}
- //将所有在线性表Lb中但不在La中的数据元素插入到La中
void Union(SqList &La, SqList Lb){
ElemType e;
int La_len,Lb_len;
int i;
La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(LocateElem(La,e,equal)==0){
ListInsert(La,La.length+1,e);
}
}
}
- //打印输出顺序表中的值
void PrintList(SqList &L){
using namespace std;
for(int i=0;i<L.length;i++){
cout<<*(L.elem+i)<<endl;
}
}
