实验二：线性表的链式表示和实现

1、学校代码： 10128学 号： 201220905048 数据结构实验报告（题 目：线性表的链式表示和实现学生姓名：孙跃学 院：理学院系 别：数学系专 业：信息与计算科学班 级：信计12-2任课教师：杜雅娟二一四年九月111、 实验目的 理解线性结构的定义、组织形式、结构特征和类型说明以及在链式存储方式下实现的插入、删除和按值查找的算法。2、 实验内容线性表的链式表示和实现3、 实验程序 根据给出的程序清单分别另建立4个文件：c1.h、c2-2.h、bo2-2.cpp和main2-2.cpp，并把它们保存在同一个文件夹中。 1.预定义常量和类型 教材定义OK、ERROR等为函数结果状态代码，文

2、件Status为其类型。我们把这些信息放到头文件c1.h中。c1.h还包含一些常用的，如string.h、stdio.h等。为了操作的方便，几乎每一个程序都把C1.h包含进去，也就把这些结果状态代码和头文件包含了进去。头文件的内容如下： / c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #inc

3、lude<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,cin / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math

4、.h中已定义OVERFLOW的值为3,故去掉此行/ #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE2、 线性链表的单链表存储结构/ c2-2.h 线性表的单链表存储结构 struct LNode ElemType data; LNode *next; ; typedef LNode *LinkList; / 另一种定义LinkList的方

5、法3、 单链表线性表的基本操作/ bo2-2.cpp 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个) Status InitList(LinkList &L) / 操作结果：构造一个空的线性表L L=(LinkList)malloc(sizeof(LNode); / 产生头结点,并使L指向此头结点 if(!L) / 存储分配失败 exit(OVERFLOW); L->next=NULL; / 指针域为空 return OK; Status DestroyList(LinkList &L) / 初始条件：线性表L已存在。操作结果：销毁线性表L LinkLis

6、t q; while(L) q=L->next; free(L); L=q; return OK; Status ClearList(LinkList L) / 不改变L / 初始条件：线性表L已存在。操作结果：将L重置为空表 LinkList p,q; p=L->next; / p指向第一个结点 while(p) / 没到表尾 q=p->next; free(p); p=q; L->next=NULL; / 头结点指针域为空 return OK; Status ListEmpty(LinkList L) / 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRU

7、E，否则返回FALSE if(L->next) / 非空 return FALSE; else return TRUE; int ListLength(LinkList L) / 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 int i=0; LinkList p=L->next; / p指向第一个结点 while(p) / 没到表尾 i+; p=p->next; return i; Status GetElem(LinkList L,int i,ElemType &e) / 算法2.8 / L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返

8、回OK,否则返回ERROR int j=1; / j为计数器 LinkList p=L->next; / p指向第一个结点 while(p&&j<i) / 顺指针向后查找,直到p指向第i个元素或p为空 p=p->next; j+; if(!p|j>i) / 第i个元素不存在 return ERROR; e=p->data; / 取第i个元素 return OK; int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType) / 初始条件: 线性表L已存在,compa

9、re()是数据元素判定函数(满足为1,否则为0) / 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 /若这样的数据元素不存在,则返回值为0 int i=0; LinkList p=L->next; while(p) i+; if(compare(p->data,e) / 找到这样的数据元素 return i; p=p->next; return 0; Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) / 初始条件: 线性表L已存在 / 操作结果: 若cur_e是L的数据

10、元素,且不是第一个,则用pre_e返回它的前驱, / 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE LinkList q,p=L->next; / p指向第一个结点 while(p->next) / p所指结点有后继 q=p->next; / q为p的后继 if(q->data=cur_e) pre_e=p->data; return OK; p=q; / p向后移 return INFEASIBLE; Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) / 初始条件

11、：线性表L已存在 / 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， / 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE LinkList p=L->next; / p指向第一个结点 while(p->next) / p所指结点有后继 if(p->data=cur_e) next_e=p->next->data; return OK; p=p->next; return INFEASIBLE; Status ListInsert(LinkList L,int i,ElemType e) / 算法2.

12、9。不改变L / 在带头结点的单链线性表L中第i个位置之前插入元素e int j=0; LinkList p=L,s; while(p&&j<i-1) / 寻找第i-1个结点 p=p->next; j+; if(!p|j>i-1) / i小于1或者大于表长 return ERROR; s=(LinkList)malloc(sizeof(LNode); / 生成新结点 s->data=e; / 插入L中 s->next=p->next; p->next=s; return OK; Status ListDelete(LinkList L,

13、int i,ElemType &e) / 算法2.10。不改变L / 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 int j=0; LinkList p=L,q; while(p->next&&j<i-1) / 寻找第i个结点,并令p指向其前趋 p=p->next; j+; if(!p->next|j>i-1) / 删除位置不合理 return ERROR; q=p->next; / 删除并释放结点 p->next=q->next; e=q->data; free(q); return OK; Sta

14、tus ListTraverse(LinkList L,void(*vi)(ElemType) / vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同 / 初始条件：线性表L已存在 / 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 LinkList p=L->next; while(p) vi(p->data); p=p->next; printf("n"); return OK; 4、检验b02-2.cpp的主程序/ main2-2.cpp 检验bo2-2.cpp的主

15、程序(与main2-1.cpp很像) #include"c1.h" typedef int ElemType; #include"c2-2.h" / 与main2-1.cpp不同 #include"bo2-2.cpp" / 与main2-1.cpp不同 Status comp(ElemType c1,ElemType c2) / 数据元素判定函数(相等为TRUE,否则为FALSE) if(c1=c2) return TRUE; else return FALSE; void visit(ElemType c) / 与main2-1.c

16、pp不同 printf("%d ",c); void main() / 除了几个输出语句外，主程和main2-1.cpp很像 LinkList L; / 与main2-1.cpp不同 ElemType e,e0; Status i; int j,k; i=InitList(L); for(j=1;j<=5;j+) i=ListInsert(L,1,j); printf("在L的表头依次插入15后：L="); ListTraverse(L,visit); / 依次对元素调用visit()，输出元素的值 i=ListEmpty(L); printf(&

17、quot;L是否空：i=%d(1:是 0:否)n",i); i=ClearList(L); printf("清空L后：L="); ListTraverse(L,visit); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)n",i); for(j=1;j<=10;j+) ListInsert(L,j,j); printf("在L的表尾依次插入110后：L="); ListTraverse(L,visit); GetElem(L,5,e); printf("第5个元素的值为

18、：%dn",e); for(j=0;j<=1;j+) k=LocateElem(L,j,comp); if(k) printf("第%d个元素的值为%dn",k,j); else printf("没有值为%d的元素n",j); for(j=1;j<=2;j+) / 测试头两个数据 GetElem(L,j,e0); / 把第j个数据赋给e0 i=PriorElem(L,e0,e); / 求e0的前驱 if(i=INFEASIBLE) printf("元素%d无前驱n",e0); else printf("元素%d的前驱为：%dn",e0,e); for(j=ListLength(L)-1;j<=ListLength(L);j+)/最后两个数据 GetElem(L,j,e0); / 把第j个数据赋给e0 i=NextElem(L,e0,e