数据结构线性链表源程序.doc

/数据结构示例程序（顺序表的各种操作） /-文件包含-#include #include #include /-预定义常量和类型（教材第10页）-#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;/-第2-顺序表结构定义（教材2页）-#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType; /在本示例程序中，顺序表元素为整型 typedef struct ElemType *elem; int length; int listsize;SqList;/-顺序表基本操作-/构造一个空的顺序表L（教材第23页算法2.3） Status InitList_Sq(SqList &L) L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;/销毁顺序表L Status DestroyList_Sq(SqList &L) if (L.elem) free(L.elem); L.length=0; L.listsize=0; return OK;/将L重置为空顺序表 Status ClearList_Sq(SqList &L) L.length=0; return OK;/判断L是否为空顺序表。若为空顺序表，返回TRUE，否则返回FALSE。 Status ListEmpty_Sq(SqList L) if (L.length=0) return TRUE; else return FALSE;/求顺序表L的长度 int ListLength_Sq(SqList L) return L.length;/用e返回顺序表L中第i个数据元素的值 Status GetElem_Sq(SqList L,int i,ElemType &e) if (iL.length) return ERROR; e=L.elemi-1; return OK; /返回顺序表L中第1个和e相等的数据元素的位序。若这样的数据元素不存在，则返回值为0。 int LocateElem_Sq(SqList L,ElemType e) int i; i=0; while (iL.length & L.elemi!=e) i+; if (iL.length) return i+1; else cout1) pre_e=L.elemi-2; return OK; else cout0 & iL.length) next_e=L.elemi; return OK; else cout顺序表为空或数据元素cur_e不在顺序表中或数据元素cur_e在顺序表中是最后一个数据元素！; return ERROR; /在顺序表L中第i个位置之前插入新的元素e（教材第24页算法2.4） Status ListInsert_Sq(SqList &L,int i,ElemType e) ElemType *newbase,*p,*q; if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for (p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/在顺序表L中删除第i个元素，并用e返回其值（教材第24-25页算法2.5） Status ListDelete_Sq(SqList &L,int i,ElemType &e) ElemType *p,*q; if (iL.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for (+p;p0) for (i=1;i=L.length;i+) coutL.elemi-1,; return OK; else cout顺序表为空！; return ERROR; /-主函数-int main() SqList L; /定义顺序表L ElemType e,e1,e2; int i; InitList_Sq(L); /构造一个空的顺序表L for (i=1;i=5;i+) ListInsert_Sq(L,i,i); ListTraverse(L); coutendl; ListDelete_Sq(L,2,e); ListTraverse(L); coutendl; coutLength=ListLength_Sq(L)endl; GetElem_Sq(L,3,e); coute=eendl; coutThe position of 5 is LocateElem_Sq(L,5)endl; PriorElem_Sq(L,4,e1); coutThe prior elem of 4 is e1endl