数据结构线性表基本操作(C语言).doc

#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefint ElemType;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedef structElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList *L); /构造空的线性表void DestroyList_Sq(SqList *L); /销毁一个线性表void ClearList_Sq (SqList *L); /将L置为空表Status ListEmpty_Sq (SqList L); /空表返回TRUEStatus ListLength_Sq (SqList L); / 返回元素个数Status GetElem_Sq (SqList L, int i, ElemType *e);/用e返回第i个元素 算法2.2中使用Status LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType);/ 在L中找到一个值与e满足compare()的元素的位序Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e);/用pre_e返回cur_e的前驱Status NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e);/用next_e返回cur_e的后继Status ListInsert_Sq(SqList *L, int i, ElemType e);/在第i位插入新的元素eStatus ListDelete_Sq(SqList *L, int i, ElemType *e);/删除第i个元素 用e返回/算法2.3Status InitList_Sq(SqList *L) / 构造空的线性表L-elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if (! L-elem)printf(构造失败!n);exit(OVERFLOW);L-length = 0;L-listsize = LIST_INIT_SIZE;printf(构造成功！n);return OK;void DestroyList_Sq(SqList *L)/ 销毁一个线性表if (L-elem != NULL)free (L-elem);L-elem = NULL;L-length = 0;L-listsize = 0;printf(已销毁线性表!n);void ClearList_Sq (SqList *L)/将L置为空表if(L-elem != NULL)L-length = 0;printf(已将L置为空表!n);Status ListEmpty_Sq (SqList L)/ 空表返回TRUEif (L.elem != NULL)if (L.length = 0)printf(是空表n);return TRUE;elseprintf(不是空表n);return FALSE;elseexit(ERROR);Status ListLength_Sq (SqList L)/ 返回元素个数if (L.elem != NULL)return L.length;elsereturn ERROR;Status GetElem_Sq (SqList L, int i, ElemType *e)/用e返回第i个元素 算法2.2中使用if (ListEmpty_Sq(L)printf(为空表!n);return ERROR;if (i L.length)printf(不存在地%d个位置!n, i);return ERROR;*e = L.elemi - 1;return OK;/算法2.6Status LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType)/ 在L中找到一个值与e满足compare()的元素的位序int i = 1;int *p = L.elem;while (i = L.length & !(* compare)(*p +, e)+i;if (i = L.length)return i;elsereturn 0;/*指向函数的指针*/Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e)/用pre_e返回cur_e的前驱int i = 2;while (i = L.length)if (cur_e = L.elemi - 1)*pre_e = L.elemi - 2;return OK;i +;return ERROR;Status NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e)/用next_e返回cur_e的后继int i = 1;while (i L.length)if (cur_e = L.elemi - 1)*next_e = L.elemi;return OK;i +;return ERROR;/算法2.4Status ListInsert_Sq(SqList *L, int i, ElemType e)/在第i位插入新的元素eElemType *newbase, *p, *q;if (i L-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;/算法2.5Status ListDelete_Sq(SqList *L, int i, ElemType *e)/删除第i个元素 用e返回ElemType *p, *q;if (i L-length)return ERROR;p = &(L-elemi -1);*e = *p;q = L-elem + L-length - 1;for (+ p; p length;return OK ;Status main(void)SqList L;ElemType i, n = 0, e = 0, cur_e = 0, pre_e = 0, next_e = 0;char ch;printf(初始化线性表);InitList_Sq(&L);printf(是否销毁线性表L? YORN );ch = getchar();if (ch = Y)DestroyList_Sq(&L);return 0;elseClearList_Sq(&L);for (i = 1; i = LISTINCREMENT; i +)L.elemi - 1 = i;L.length +;printf(线性表内初始数值为:n);for (i = 1; i = LISTINCREMENT; i +)printf(%4d, L.elemi - 1);printf(n);n = ListLength_Sq (L);printf(线性表内元素个数为 %3dn, n);printf(欲知道第i位数字 i = );scanf(%d, &i);GetElem_Sq(L, i, &e);printf(第%d位数字为%dn, i, e);cur_e = e;PriorElem_Sq(L, cur_e, &pre_e);printf(%d的前驱是%dn, cur_e, pre_e);NextElem_Sq(L, cur_e, &next_e);printf(%d的后继是%dn, cur_e, next_e);printf(请输入要插入的位数和要插入的数字:);scanf(%d %d, &n, &e);ListInsert_Sq(&L, n, e);printf(插入后线性表内%d个数据为:n, L.length);for (i = 1; i = L.length; i +)printf(%4d, L.elemi - 1);printf(n);ListDelete_Sq(&L, n, &e);printf(删除线性表中第%d个数据%d后，线性内%d个数据为:n, n, e, L.length);for (i = 1; i = L.length; i +)printf(%4d, L.elemi - 1);printf(n);return 0;