实验一顺序结构线表基本操作的实现.doc

实验一 顺序结构线性表基本操作的实现专业：网络工程 班级：10级1班 学号： 姓名： 实验地点： B102 实验时间： 2011-9-14 指导教师：王润鸿【实验课程名称】数据结构【实验项目名称】线性表基本操作的实现一、 实验目的1掌握线性表顺序存储基本操作；2学会设计实验数据验证程序。二、 实验仪器及环境计算机，window xp操作系统，VC+6.0三、 实验内容及步骤线性表顺序存储基本操作存储结构定义：#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct ElemType *elem; /存储空间基址 int length； /当前长度 int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList；实现的基本操作：InitList( &L )操作结果：构造一个空的线性表 L 。DestroyList( &L )初始条件：线性表 L 已存在。操作结果：销毁线性表 L 。ListEmpty( L )初始条件：线性表L已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。ListLength( L )初始条件：线性表 L 已存在。操作结果：返回 L 中元素个数。PriorElem( L, cur_e, &pre_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。NextElem( L, cur_e, &next_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。GetElem( L, i, &e )初始条件：线性表 L 已存在，1iLengthList(L)。操作结果：用 e 返回 L 中第 i 个元素的值。LocateElem( L, e, compare( ) )初始条件：线性表 L 已存在，compare( ) 是元素判定函数。操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( )初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败。ClearList( &L )初始条件：线性表 L 已存在。操作结果：将 L 重置为空表。PutElem( &L, i, &e )初始条件：线性表L已存在，1iLengthList(L)。操作结果：L 中第 i 个元素赋值同 e 的值。ListInsert( &L, i, e )初始条件：线性表 L 已存在，1iLengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。ListDelete( &L, i, &e )初始条件：线性表 L 已存在且非空，1iLengthList(L)。操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。四、 实验记录#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;Status InitList_Sq(SqList &L);Status ListEmpty_Sq(SqList L);Status DestroyList_Sq(SqList L);Status ListLength_Sq(SqList L);Status ClearList_Sq(SqList &l);Status GetElem_Sq(SqList L,int i,ElemType &e);Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType &pre_e); Status NextElem_Sq(SqList L,ElemType cur_e,ElemType &next_e);Status ListInsert_Sq(SqList &L, int i, ElemType e);Status ListDelete_Sq(SqList &L, int i, ElemType &e);int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType);void MergeList_Sq(SqList La, SqList Lb, SqList &Lc);int deng(ElemType x,ElemType y) if(x=y)return 1; else return 0;Status InitList_Sq(SqList &L) / 构造一个空的线性表L。L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) return OK; / 存储分配失败L.length = 0; / 空表长度为L.listsize = LIST_INIT_SIZE; / 初始存储容量return OK; / InitList_SqStatus DestroyList_Sq(SqList L)free(L.elem);return OK;Status ListEmpty_Sq(SqList L)if(L.length!=0) return TRUE;else return FALSE;Status ListLength_Sq(SqList L)return L.length;Status GetElem_Sq(SqList L,int i,ElemType &e)ElemType *p;int n=1;p=L.elem;while(n=i)p+; n+;e=*-p;return 0;int PriorElem_Sq(SqList L,ElemType cur_e,ElemType &pre_e)int i=1;while(i=L.length)if(L.elemi!=cur_e)i+;else pre_e=L.elemi-1;break;return 0;int NextElem_Sq(SqList L,ElemType cur_e,ElemType &next_e)int i=1;while(i=L.length)if(L.elemi!=cur_e)i+;elsenext_e=L.elemi+1; break;return 0;Status ClearList_Sq(SqList &L)L.length=0;return L.length;Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序线性表L的第i个元素之前插入新的元素e，/ i的合法值为iListLength_Sq(L)+1ElemType *p;if (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) return ERROR; / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量ElemType *q = &(L.elemi-1); / q为插入位置for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增return OK; / ListInsert_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) ElemType *p;ElemType *q;if(iL.length-1) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p) *(p-1)=*p;-L.length;return OK;/ListDelete_Sqint LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType)ElemType i;ElemType *p;i=1;p=L.elem;while(i=L.length&!(*compare)(*p+,e) +i;if(i=L.length) return i;else return 0;/LocateElem_Sqvoid Traverse(SqList L)/逐个输出顺序线性表L的元素。for(int i=0;iL.length;i+)coutL.elemi ;void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知顺序线性表La和Lb的元素按值非递减排列。/ 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La.elem; pb = Lb.elem;Lc.listsize = Lc.length = La.length+Lb.length;pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType);if (!Lc.elem)exit(OVERFLOW); / 存储分配失败pa_last = La.elem+La.length-1;pb_last = Lb.elem+Lb.length-1;while (pa = pa_last & pb = pb_last) / 归并if (*pa = *pb) *pc+ = *pa+;else *pc+ = *pb+;while (pa = pa_last) *pc+ = *pa+; / 插入La的剩余元素while (pb = pb_last) *pc+ = *pb+; / 插入Lb的剩余元素 / MergeListvoid main() SqList La,Lb,Lc;int pre_e,next_e;int (*com)(ElemType ,ElemType );ElemType e,e1,e2; InitList_Sq(La); InitList_Sq(Lb);InitList_Sq(Lc);for(int i=1;i=10;i+)ListInsert_Sq(La, i, i*2); ListInsert_Sq(Lb, i, i*3); com=deng; printf(dex=%d,LocateElem_Sq( La, 4,com);coutnLa:;Traverse(La); coutnLb:; Traverse(Lb);MergeList_Sq(La, Lb, Lc);coutnLc:; Traverse(Lc); ListDelete_Sq(Lc, 5, e); coutn新Lc:;Traverse(Lc);coutn;PriorElem_Sq(Lc,6,pre_e);cout新Lc中6的前驱是:pre_eendl;NextElem_Sq(La,6,next_e);cout新Lc中6的后继是:next_eendl;if(ListEmpty_Sq(La)=0) coutLa表为空endl;if(ListEmpty_Sq(La)=1) coutLa表不为空endl; coutLa:;Traverse(La);coutendl; if(ListEmpty_Sq(Lb)=0) coutLb表为空endl