数据结构 C语言版 线性表 顺序表示.doc

#includestdio.h #includestdlib.h #includestring.h #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OVERFLOW 0 #define OK 1 #define ERROR 0 typedef struct { int data; }ElemType; typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量以一数据元素存储长度为单位 }SqList; int InitList_Sq(SqList L) { // 构造一个空的线性表L。 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq int ListInsert_Sq(SqList L, int i, ElemType e) { // 在顺序线性表L的第i个元素之前插入新的元素e， // i的合法值为1≤i≤ListLength_Sq(L)+1 ElemType *p; if (i 1 || i L.length+1) return ERROR;// i值不合法 if (L.length = L.listsize)// 当前存储空间已满，增加容量 { ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) exit(OVERFLOW);// 存储分配失败 L.elem = newbase;// 新基址 L.listsize += LISTINCREMENT;// 增加存储容量 } ElemType *q =(L.elem[i-1]);// q为插入位置 // 插入位置及之后的元素右移 for (p =(L.elem[L.length-1]); p=q; --p) *(p+1) = *p; *q = e;// 插入e ++L.length;// 表长增1 return OK; } // ListInsert_Sq int ListDelete_Sq(SqList L, int i, ElemType e) { // 在顺序线性表L中删除第i个元素，并用e返回其值。 // i的合法值为1≤i≤ListLength_Sq(L)。 ElemType *p, *q; if (i1 || iL.length) // i值不合法 return ERROR; p = (L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p=q; ++p) // 被删除元素之后的元素左移 *(p-1) = *p; --L.length; // 表长减1 return OK; } // ListDelete_Sq int LocateElem_Sq(SqList L,ElemType e,int(*compare)(ElemType,ElemType)) { // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。 // 若找到，则返回其在L中的位序，否则返回0。 int i; ElemType *p; i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置 while (i = L.length !(*compare)(*p++, e)) ++i; if (i = L.length) return i; else return 0; } // LocateElem_Sq void output(SqList L) { int i; printf(操作后线性表输出结果为：); for(i=0;iL.length;i++) {