线性表链式结构实现实例

#include

#include

#include

using namespace std;

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

#define LISTINCREMENT 10 //线性表存储空间分配增量

/*状态码*/

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef struct Student

{

char num[10];

char name[10];

int score;

}STU;

typedef struct

{

STU *elem;

int length;

int listsize;

}SqList;

//初始化一个线性表

Status InitList_Sq(SqList &L)

{

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

if(!L.elem ) exit(OVERFLOW);

L.length =0;

L.listsize =LIST_INIT_SIZE;

return OK;

}

Status DestroyList_Sq(SqList &L)

{

free(L.elem );

L.elem =NULL;

L.length =0;

L.listsize =0;

return OK;

}

Status ClearList_Sq(SqList &L)

{

L.length =0;

return OK;

}

Status ListEmpty_Sq(SqList L)

{

if(L.length ==0)

return TRUE;

else

return FALSE;

}

int ListLength_Sq(SqList L)

{

return L.length ;

}

Status GetElem_Sq(SqList L,int i,STU &e)

{

if(iL.length )

return ERROR;

strcpy(e.name ,L.elem[i-1].name) ;

strcpy(e.num ,L.elem[i-1].num );

e.score =L.elem[i-1].score ;

return OK;

}

int compare(STU c1,STU c2)

{

if(strcmp(c1.name,c2.name)==0 &&strcmp(c1.num ,c2.num)==0 &&c1.score ==c2.score return 1;

else

return 0;

}

int LocateElem_Sq(SqList L,STU e)

{

STU *p;

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

p = L.elem; // p的初值为第1个元素的存储位置即地址

while(i

{

flag=compare(*p++,e);

if(flag==0)

++i;

else

break; )

}

return i;

}

Status PriorElem_Sq(SqList L,STU cur_e,STU &pre_e)

{

STU *p;

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

p = L.elem; // p的初值为第1个元素的存储位置即地址

while(i

if(i==1)

return ERROR;

else

{

pre_e=L.elem [i-2];

return OK;

}

}

Status NextElem_Sq(SqList L,STU cur_e,STU &next_e)

{

STU *p;

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

p = L.elem; // p的初值为第1个元素的存储位置即地址

while(i

if(i==L.length )

return ERROR;

else

{

next_e=L.elem [i];

return OK;

}

}

Status ListInsert(SqList &L,int i,STU e)

{

STU *newbase, *q, *p;

// 输入的i 不合法

if(i L.length + 1)

return ERROR;

// 当前存储空间已满, 增加分配

if( L.length >= L.listsize)

{// realloc改变L.elem 所指内存的大小，原始所指内存中的数据不变。

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

if( !newbase )

exit(ERROR);

L.elem = newbase; // 新基址

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

}

// 指定插入的位置

q = &(L.elem[i-1]);

// q之后的元素右移一步，以腾出位置

for(p =&(L.elem [ L.length - 1]); p >= q; --p)

*(p+1) = *p;

strcpy(q->name , e.name) ;

strcpy(q->num ,e.num );

q->score =e.score ;// 插入e

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

return OK;

}

Status ListDelete(SqList &L,int i,STU &e)

{

STU *p,*q;

// i值不合法

if( i L.length)

return ERROR;

p = L.elem + i - 1; // p为被删除元素的位置

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

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

for(++p; p

*(p-1) = *p;

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

return OK;

}

Status listTraverse(SqList L)

{

for(int i=0;i

cout

}

int main()

{

SqList L;

STU stu[5],e,pre_e,next_e,cur_e;

InitList_Sq(L);

cout

for(int i=0;i

{

cin>>stu[i].name >>stu[i].num >>stu[i].score ;

ListInsert(L,1,stu[i]);

}

cout

listTraverse(L);

/*GetElem_Sq(L,3,e);

cout

cin>>e.name >>e.num >>e.score ;

cout

cin>>cur_e.name >>cur_e.num >>cur_e.score ;

PriorElem_Sq(L,cur_e,pre_e);

cout>cur_e.name >>cur_e.num >>cur_e.score ;

NextElem_Sq(L,cur_e,next_e);

cout

cout

cin>>e.name >>e.num >>e.score ;

ListInsert(L,2,e);

listTraverse(L);

return 0;

}