实验二顺序表基本操作的实现.doc

实验二顺序表基本操作的实现专业：10网络工程 班级：10计本1班 学号： 姓名： 实验地点： B102 实验时间： 2011-10-19 指导教师： 王润鸿 【实验课程名称】数据结构【实验项目名称】链表基本操作的实现一、 实验目的1掌握线性表链式存储基本操作；2学会设计实验数据验证程序。二、 实验仪器及环境计算机，window xp操作系统，VC+6.0三、 实验内容及步骤四、 线性表链式存储基本操作存储结构定义：typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;实现的基本操作：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 iostream.h#include stdlib.h/* 定义ElemType为int类型 */typedef int ElemType;#define TRUE 1#define ERROR 0#define FALSE 0#define OK 1#define NULL 0#define flag -1/* 单链表的结点类型 */typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;/* 初始化单链表 */LinkList InitList(LinkList &L) L=(LinkList)malloc(sizeof(LNode);L-next=NULL;return L;/* 清空单链表 */void ClearList(LinkList L) L-next=NULL;/* 检查单链表是否为空 */int ListEmpty(LinkList L)if(L-next=NULL) return TRUE;else return FALSE;/* 遍历单链表 */void ListTraverse(LinkList L)LinkList p=(LinkList)malloc(sizeof(LNode);p=L-next;while(p!=NULL) coutdatanext;coutnext;j=0;while(p!=NULL) j+;p=p-next; return j;/得到链表的指定值int GetElem (LinkList L, int i)LinkList p; int j;p=L-next;j=1;while (p!=NULL & jnext; j+; if (j=i) return p-data;else return NULL;int LocateElem(LinkList L,ElemType e)LinkList p; int i=0;p=L-next;while(p)i+;if(p-data=e) return i;p=p-next;return 0;int ListInsert(LinkList &L, int i, ElemType e) / 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p & j next; +j; if (!p | j i-1) return ERROR; / i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_L/删除一个结点/int ListDelete(LinkList &L, int i) /在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 LinkList p,q; p = L; int j = 0; while (p-next & j next; +j; if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 free(q); return OK; / ListDelete_L/直接创建一个链表void CreateList(LinkList &L, int n) / 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L LinkList p; int i; L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i=1; ip-data; / 改为一个随机生成的数字(200以内) p-next=L-next; L-next=p; / 插入到表头 / CreateList_Lvoid main()int i;ElemType e;LinkList La; InitList(La);cout请逆序输入单链表元素endl; CreateList(La,6);coutThe list is:; ListTraverse(La); coutthe length is:ListLength(La)endl; if(ListEmpty(La) coutThe list is empty!endl; else coutThe list is not empty!endl; coute; coutthe location.is:LocateElem(La,e)endl;coutie;ListInsert(La,i,e); coutThe new list is:;ListTraverse(La);couti;ListDelete(La,i); coutThe new list is:;ListTraverse(La);coutClear the list!endl; ClearList(La);coutThe len