数 据 结 构 实 验 报 告
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
#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值不合法