//malloc()

#include //srand((unsigned)time(NULL));

//用宏定义确定ElemType类型

#define ElemType int

//-----线性表的动态分配顺序存储结构-----

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量

#define LISTINCREMENT5 //线性表存储空间的分配增量

typedef struct {

ElemType *elem;//存储空间基址

int length;//当前长度

int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)

} SqList;

// 操作结果：构造一个空的线性表L。

Status InitList_Sq(SqList &L) {//构造一个空的顺序表，动态申请存储空间

L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if (!L.elem) {//存储分配失败

printf("初始化失败");

exit(OVERFLOW);//exit(-1)程序异常退出

}

L.length = 0;//空表的长度初始化为0

L.listsize = LIST_INIT_SIZE;//空表的初始存储空间为 LIST_INIT_SIZE

return OK;

}// InitList_Sq算法2.3

// 初始条件：线性表L已存在。

// 操作结果：销毁线性表L。

Status DestroyList_Sq(SqList &L) {

//free(L.elem);//释放存储空间基址

L.elem = NULL;//存储空间基址置空

L.length = 0;//当前长度初始化为 0

L.listsize = 0;//分配的存储容量为 0

return OK;

}// DestroyList_Sq

// 初始条件：线性表L已存在。

// 操作结果：将L重置为空表。

Status ClearList_Sq(SqList &L) {

L.length = 0;

return OK;

}// ClearList_Sq

// 初始条件：线性表L已存在。

// 操作结果：若L为空表，返回TRUE，否则返回FALSE。

Status ListEmpty_Sq(SqList L) {

return L.length ? TRUE : FALSE;

}// ListEmpty_Sq

// 初始条件：线性表L已存在。

// 操作结果：返回L中数据元素个数。

int ListLength_Sq(SqList L) {

return L.length;

}// ListLength_Sq

// 初始条件：线性表L已存在，1≤pos≤ListLength(L) 。

// 操作结果：用e返回L中第pos个数据元素的值。

Status GetElem_Sq(SqList L, int pos, ElemType &e) {

if(L.length==0 || pos<1 || pos>L.length)

return ERROR;

e = L.elem[pos-1];

return OK;

}// GetElem_Sq

// 初始条件：线性表L已存在，compare()是数据元素判定函数。

// 操作结果：返回L中第1个与e满足compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0。

Status compare(ElemType listElem, ElemType e) {

if(listElem==e)//找到元素e

return TRUE;

else {

//printf("在列表中没有值为%d的元素\n", e);

return FALSE;

}

}// Compare

int LocateElem_Sq(SqList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) {

int i = 1;//i的初值为第1元素的位序

ElemType *p = L.elem;//p的初值为第1元素的存储位置

//*p++代表*(p+1)， 在循环中意味调用函数Status (*compare)(ElemType, ElemType),

//用线性表中的每个元素与e比较，当*p++与e相等时，返回1，取反为0，循环中止。

//compare是指向函数的指针

while(i<=L.length && !(*pfn_compare)(*p++, e))

++i;//compare是一个指向函数的指针，返回值为Status(int)

if (i<=L.length) {

return i;//i的值在线性表中，返回元素的位序

} else

return 0;

}// LocateElem_Sq 算法2.6

// 初始条件：线性表L已存在。

// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。

Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e) {

int i = LocateElem_Sq(L, cur_e, compare);

if(i==0 || i==1) return ERROR;

GetElem_Sq(L, i-1, pre_e);

return OK;

}

// 初始条件：线性表L已存在。

// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，pre_e无定义。

Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e) {

int i = LocateElem_Sq(L, cur_e, compare);

if(i==0 || i==L.length) return ERROR;

GetElem_Sq(L, i+1, next_e);

return OK;

}

// 初始条件：线性表L已存在，1≤pos≤ListLength(L)+1。

// 操作结果：在L中第pos个位置之前插入新的元素e，L的长度加1。

Status ListInsert_Sq(SqList &L, int pos, ElemType e) {

if (pos<1 || pos>L.length+1) { //pos的合法值为1≤pos≤ListLength(L)+1。即插入元素的位置pos应大于 0，小于 线性表的长度+1

printf("插入位置有问题");

return ERROR;

}

if (L.length >= L.listsize) {//当前存储空间已满，增加分配

ElemType *newbase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));

if (!newbase) {//realloc更改已分配的内存单元大小

printf("存储分配失败");

exit(OVERFLOW);//存储分配失败

}

L.elem = newbase;//新基址

L.listsize += LISTINCREMENT;//增加存储容量

}

ElemType *q = &(L.elem[pos-1]);//q为插入位置，即将插入位置的地址赋给q

ElemType *p = &(L.elem[L.length-1]);//p为最后一个元素的地址

for ( ; p>=q; --p) {

*(p+1) = *p;//插入位置及之后的元素右移

}

*q = e;//插入e

++L.length;//表长增1

return OK;

}//ListInsert_Sq 算法2.4

// 初始条件：线性表L已存在且非空，1≤pos≤ListLength(L)。

// 操作结果：删除L的第pos个数据元素，并用e返回其值,L的长度减1。

Status ListDelete_Sq(SqList &L, int pos, ElemType &e) {

if (pos>L.length || pos<1) {//pos的合法值为1<=pos<=ListLength_Sq(L)，即删除元素的位置pos应大于 0，小于 线性表的长度+1

printf("被删除元素的位置有误");

return ERROR;

}

ElemType *p = &(L.elem[pos-1]);//p为被删除元素的位置 ，即将被删除元素的地址赋给p

e = *p;//被删除元素的值赋给e

ElemType *q = L.elem + L.length - 1;//表尾元素的位置

for (++p; p<=q; ++p) {//被删除元素之后的元素左移

*(p-1) = *p; //假定在线性表{11 12 13 14 15}中删除13，变为{11 12 14 15}，

}//则有 pos=3，e=13，p=&e，则循环初始条件++p=&(L.elem[3])即*p=14，*(p-1)=*p即将14往前移一位

--L.length;//表长减1

return OK;

}// ListDelete_Sq 算法2.5

// 初始条件：线性表L已存在。

// 操作结果：依次对L的每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。

Status visit(ElemType e) {

printf("%d ", e);

return OK;

}

Status ListTraverse_Sq(SqList L, Status (*pfn_visit)(ElemType)) {

if(!L.elem){

printf("\n线性表未初始化或被销毁了!!!");

return ERROR;

}

if(L.length == 0)

printf("线性表中无元素!!!");

for (int i=0; i