線性表的順序表示：
#define LIST_INIT_SIZE 100 定義一個(gè)線性表類型
#define LISTINCREMENT 10
typedef struct
{
ElemType *elem; 基址
int length; 元素的長度
int listsize;當(dāng)前的存儲(chǔ)容量
}Sqlist;
void InitList_Sq(Sqlist &L) 初始化操作
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
return overflow;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return ok;
}
void DestroyList_Sq(Sqlist &L) 銷毀線性表
{
free(L.elem);
L.elem=NULL;
L.length=0;
L.listsize=0;
return ok;
}
void ClearList(Sqlist L) 清零操作
{
L.length=0;
return ok;
}
void ListEmpty(Sqlist L) 判空操作
{
if(L.length=0)
return True;
else
return False;
}
int ListLength(Sqlist L) 輸出表的長度，數(shù)據(jù)元素個(gè)數(shù)
{
return L.length;
}
void GetElem(Sqlist &L,int i,ElemType &e) 得到第I 個(gè)元素的數(shù)據(jù)元素的值
{
if(i<1 || i>L.length)
return error;
e=*(L.elem+i-1);
return ok;
}
int LocateElem(Sqlist &L,ElemType e,void (*compare)(ElemType,ElemType)) 查找與E相等的元素的位置
{
ElemType *p;
i=1;
while(i<=L.length && !compare(*p++,e))
++i;
if(i<=L.length)
return i;
else
return 0;
}
void PriorElem(Sqlist L,ElemType cur_e,ElemType pre_e) 得到給出的數(shù)的前一個(gè)元素值
{
int i=2;
ElemType *p;
p=L.elem+1;
while(i<=L.length && !(*p++==cur_e))
++i;
if(i>L.length)
return INFEASIBLE;
else
{
pre_e=*--p;
return OK;
}
}
void NextElem(Sqlist L,ElemType pre_e,ElemType cur_e) 得到后一個(gè)元素的值
{
int i=1;
ElemType *p
p=L.elem;
while(i<L.length && !(*p++==pre_e))
++i;
if(i>=L.length)
return INFEASIBLE;
else
{
cur_e=*++p;
return OK;
}
}
void InsertElem(Sqlist &L,int i,ElemType e) 在第I個(gè)元素中插入一個(gè)值為E的元素
{
if(i<1 || i>=length+1)
return ERROR;
if(L.length>=L.listsize)
{
if(!newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)
*sizeof(ElemType))))
return OVERFLOW;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
p=L.elem+L.length-1;
q=L.elem+i-1;
for(p;p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return ok;
}
void DeleteElem(Sqlist &L,int i,ElemType e) 刪除第I個(gè)元素
{
if(i<1 || i>=L.length)
return FALSE;
p=L.elem+i-1;
q=L.elem+L.length-1;
e=*p;
for(p;p<=q;++p)
*p=*(p+1);
--L.length;
return OK;
}
void ListTraverse(Sqlist &L,void (*vi)(ElemType)) 對(duì)線性表進(jìn)行VI的操作
{
int i;
ElemType *p;
p=L.elem;
for(i=1;i<=L.length;++i)
vi(*p++);
return OK;
}
以上是線性表的一些常用的原操作.
例：
1．求一個(gè)新的集合A=A U B。
void union(Sqlist &LA,Sqlist LB)
{
la_len=LA.length;
lb_len=LB.length;
for(i=1;i<=lb_len;++i)
{
GetElem(LB,i,e);
if(!Locate(LA,e,compare()))
InsertList(LA,++la_len,e);
}
return OK;
}
2.將二個(gè)非遞減的LA表和LB表歸并為一個(gè)新的非遞減的LC表
void MergeList(Sqlist LA,Sqlist LB,Sqlist &LC)
{
i=j=1;k=0;
InitList(LC);
while(i<=LA.length && j<=LB.length)
{
GetElem(LA,i,ai);
GetElem(LB,j,bj);
if(ai<=bj)
{
InsertList(LC,++k,ai);
++i;
}
else
{
InsertList(LC,++k,bj);
++j;
}
}
while(i<=LA.length)
{
GetElem(LA,i,ai);
InsertList(LC,++k,ai);
++i;
}
while(j<=LB.length)
{
GetElem(LB,i,bj);
InsertList(LC,++k,bj);
++j;
}
return OK;
}