线性表的基本操作

数 据 结 构 实 验 报 告

2011 年 4 月 13 日

一.项目组成

二.程序结构图

题目一: main InitList_Sq CreateList_SDestroyList_SClearList_SqGetElem_SqListEmpty_S ListLength_SListInsert_Sq

ListDelete_Sq ListTraverse_SLocateElem_SPriorElem_Sq NextElem_Sq

题目二:

三.算法及其功能函数

题目一:

ListDelete_L InitList_L CreateList_L DestroyList_ClearList_L main InitList_Sq(SqList *L) /*创建线性表*/

CreateList_Sq(SqList *L) /*输入线性表中元素 */ DestroyList_Sq(SqList *L) /*销毁线性表*/ ClearList_Sq(SqList *L) /*清空线性表*/ ListEmpty_Sq(SqList L) /*判断是否为空*/ ListLength_Sq(SqList L) /*求线性表长度 */

GetElem_Sq(SqList L, int i, ElemType *e) /*取第i个元素并用e返回*/ LocateElem_Sq (SqList L, int e) /*判断e在表中位置*/ PriorElem_Sq(SqList L,int i, ElemType cur_e, ElemType *pre_e) /*取前驱*/ NextElem_Sq(SqList L,int i, ElemType cur_e, ElemType *next_e ) /*取后继*/ ListInsert_Sq(SqList *L, int i, ElemType e) /*在第i个元素前插入e*/ ListDelete_Sq(SqList *L, int i, ElemType *e) /*删除第i个元素 */ ListTraverse_Sq(SqList L,int i) /*遍历线性表*/

ListEmpty_L ListLength_L ListTraverse_GetElem_L LocateElem_PriorElem_L NextElem_L ListInsert_L

题目二:

InitList_L(LinkList *L) /*创建线性表*/

CreateList_L(LinkList *L) /*输入线性表中元素 */ DestroyList_L(LinkList *L) /*销毁线性表*/ ClearList_L(LinkList *L) /*清空线性表*/ ListEmpty_L(LinkList L) /*判断是否为空*/ ListLength_L(LinkList L) /*求线性表长度 */

GetElem_L(LinkList L, int i, ElemType *e) /*取第i个元素并用e返回*/ LocateElem_L (LinkList L, int e) /*判断e在表中位置*/ PriorElem_L(LinkList L,int i, ElemType cur_e, ElemType *pre_e) /*取前驱*/ NextElem_L(LinkList L,int i, ElemType cur_e, ElemType *next_e ) /*取后继*/ ListInsert_L(LinkList *L, int i, ElemType e) /*在第i个元素前插入e*/ ListDelete_L(LinkList *L, int i, ElemType *e) /*删除第i个元素 */ ListTraverse_L(LinkList L,int i) /*遍历线性表*/

四.源代码

题目一:

#include #include typedef int ElemType; typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0

#define OVERFLOW -2

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表空间的分配增量 typedef struct{

ElemType *elem; //存储空间基址 int length; //当前长度

int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList;

Status 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

Status CreateList_Sq(SqList *L){ int i,n; printf(\请输入线性表长度\\nn=\ scanf(\ (*L).length=n;

printf(\输入线性表L:\\n\ for(i=0;i

Status DestroyList_Sq(SqList *L) { //销毁线性表L。 if((*L).elem)

free((*L).elem); //释放线性表占据的所有存储空间 return OK;

} //DestroyList_Sq

Status ClearList_Sq(SqList *L) { //将L重置为空表。

(*L).length=0; //将线性表的长度置为0 return OK; } //ClearList_Sq

Status ListEmpty_Sq(SqList L) { //线性表判空。 if(L.length==0)

return TRUE; //若L为空，则返回TURE else return FALSE; //若L不为空，则返回FALSE } //ListEmpty_Sq

Status ListLength_Sq(SqList L) { //返回线性表的长度。 return(L.length); } //ListLength_Sq

Status GetElem_Sq(SqList L, int i, ElemType *e) { //用e返回L中的第i个数据元素的值。

if(i<1||i>L.length) return ERROR; // i值不合法