华科数据结构实验报告.doc

课 程 实 验 报 告

课程名称： 数据结构

专业班级：计算机科学与技术13xx班
学 号：
姓 名：
指导教师：
报告日期： 2015

计算机科学与技术学院

目 录
1 课程实验概述 1
2 实验一 基于顺序结构的线性表实现
2.1 问题描述 2
2.2 系统设计 2
2.3 系统实现 3
2.4 效率分析 12
3 实验二 基于链式结构的线性表实现
3.1 问题描述 14
3.2 系统设计 14
3.3 系统实现 15
3.4 效率分析 25
4 实验总结与评价 27

1 课程实验概述
1.1 加深对数据结构和算法的理解，进一步提高编程能力；
1.2 培养和提高学生分析问题与解决问题的综合能力；
1.3 整理资料，撰写规范的实验报告。

2 实验一 基于顺序结构的线性表实现
2.1 问题描述
基于顺序存储结构，实现线性表的基本的常见的运算。
2.2 系统设计
2.2.1系统包括15个功能，分别为：
1.Creatlist 2.DestroyList
3.ClearList
4.ListEmpty
5.ListLength 6.GetElem
7.LocatElem
8.PriorElem 9.NextElem 10.ListInsert
11.ListDelete
12.ListTrabverse
13.Save the List
14.Load the List
15.Add elem to List
2.2.2系统数据物理结构类型为顺序结构，存储的数据类型为结构体：
typedef struct
{
int num;
}ElemType;//定义数据类型
2.2.3顺序表应声明一个头结点：
typedef struct
{
ElemType *elem ; //存储顺序表开始的头指针
int listsize; //存储当前顺序表总长度
int length; //存储当前元素的总个数，且当length为-1值时，表示还未被初始化

}Sqlist;//顺序表物理结构

2.3 系统实现
2.3.1 InitList(&L)
操作结果：构造一个空的线性表L。
操作步骤：函数接受传入的未初始化的顺序表地址，然后为其然后为顺序表分配空间，并把地址赋值给elem，分别初始化L中成员length与listsize，具体代码如下：
Status InitList(Sqlist *L) //初始化顺序表
{
L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;

}
2.3.2 DestroyList(&L)
初始条件：线性表已经存在。
操作结果：销毁线性表。
操作步骤：释放已分配给顺序表的空间，将length置为-1，表示该顺序表已被销毁，同时listsize也置为0，具体代码如下：
Status DestroyList(Sqlist *L)//销毁顺序表
{

free(L->elem);//释放已分配的空间
L->elem = NULL;
L->length = -1; //顺序表状态为被摧毁
L->listsize = 0; //长度置0
return OK;
}

2.3.3 ClearList(&L)
初始条件：线性表L已存在。
操作结果：将线性表L置空。
操作步骤：将表L中length置为0，表示该表为空，其他部分不予操作，具体代码如下：
Status ClearList(Sqlist *L)//顺序表清空
{
L->length =0; //长度置0
return OK;
}

2.3.4 ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回True，若L不为空，则返回False。
操作步骤：根据表内结构成员length判断，若length为0则返回true，否则，返回false，具体代码如下：
Status ListEmpty(Sqlist L)//判断顺序表是否为空
{
if(L.length==0)//链式表为空，返回真
return OK;
else
return ERROR;//链式表不为空返回FALSE

}

2.3.5 ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中的元素个数。
操作步骤：length存储表长，直接使用，具体代码如下:
Status ListLength(Sqlist L)//返回顺序表元素个数
{
printf("线性表长度为%d",L.length);
return OK;
}

2.3.6 GetElem(L,i,&e)
初始条件：线性表L已存在。
操作结果：用e返回L中第i个元素数值。
操作步骤：首先判断传入参数i是否合法，若i<1或大于表长，则返回ERROR，不进行操作，若合法，修改参数e，将第i号元素赋值给e，具体代码如下：
Status GetElem(Sqlist L,int i,ElemType *e)//获取i号元素
{

if(i>L.length || i<0) //判断i值是否合法
{

return ERROR;

}
else
{
*e = L.elem[i-1]; //返回i号值
return OK;

}

}

2.3.7 LocateElem(L,e,compare())
初始条件：线性表L已存在，compare()是元素数据判定函数。
操作结果：返回L中与第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
操作步骤：从头开始循环遍历顺序表，利用i计数，若循环至表尾，或者查找到相同元素，则终止循环；若循环至表尾，表尾元素并不相等，表示不存在该元素，返回FALSE；若并为循环到表尾，终止循环，表示循环结束处元素即满足条件，返回位序i，具体代码如下：
Status LocateElem(Sqlist L,ElemType e, Status (*compare)(ElemType,ElemType))
{
ElemType *p;
p = L.elem;
int i=1;
while(i<=L.length&&!(*compare)(e, *p++)) //查找与e相等的元素
i++;
if(i<=L.length)
return i;//返回元素序号
else
return FALSE;

}

2.3.8 PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，负责操作失败，pre_e无定义。
操作步骤：根据传入参数cur_e，利用LocateElem()函数，确定该元素位序，若未查找到该元素或查找到该元素为首元素，均表示不存在该元素前驱，返回FALSE；否则，修改pre_e的值，将查找到值的前驱赋值给它，具体代码如下：
Status PriorElem(Sqlist L,ElemType cur_e,ElemType *pre_e)//查找指定元素前驱
{
int i;
i = LocateElem(L, cur_e, *compare);//使用定位函数，查找第i个值
if(i == -1)
{
return -1;
}
else if(!i || i ==1)//如果未找到元素或元素为第一个，则前驱不存在
return ERROR;
else
{
GetElem(L,i-1,pre_e);//前驱存在，获取该元素
return i-1;
}

}

2.3.9 NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e 无定义。
操作步骤：根据传入参数cur_e，利用LocateElem()函数，确定该元素位序，若未查找到该元素或查找到该元素为尾元素，均表示不存在该元素后继，返回FALSE；否则，修改next_e的值，将查找到值的后继赋值给它，具体代码如下：
Status NextElem(Sqlist L,ElemType cur_e,ElemType *next_e)
{
int i;
i = LocateElem(L, cur_e, *compare);//使用定位函数，查找第i个值
if(i == -1)
{
return -1;
}
else if(!i || i==L.length)//如果未找到元素或元素为最后一个，则后继不存在
return ERROR;
else
{
GetElem(L,i+1,next_e);//后继存在，获取该元素
return i+1;
}
}

2.3.10 ListInsert(&L,I,e)
初始条件：线性表已存在。
操作结果：在L中第i个位置前插入新的数据元素e，L的长度加1。
具体代码：首先判断传入i值是否合法，当i>L.length或者i<1时，不合法，返回ERROR，否则，执行下一步；第二步先判断数组是否已存储满，若满，增加分配空间，若未满，则执行插入操作；第三步，先将第i号元素之后每个元素向后挪一位，之后将要插入元素赋值给第i号元素，表长length增加1，具体代码如下：
Status ListInsert(Sqlist *L,int i,ElemType e)//在顺序表指定位置插入元素
{

if(i<1 || i>L->length+1) //判断插入点是否合法
return ERROR;
if(L->length > L->listsize) //若空间不足，为数组增加分配空间
{
ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
return OVERFLOW;
L->elem = newbase;
L->listsize = L->listsize + LISTINCREMENT;
}

int j;
for(j=L->length-1;j>=i-1;j--) //插入值后的元素全部向后移动一个
{
L->elem[j+1] = L->elem[j];
}
L->elem[i-1].num = e.num;
return OK;

}

2.3.11 ListDelete(&L,I,&e)
初始条件：线性表L已存在且非空，1<=i<=ListLength(L)。
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1.
操作步骤：首先判断传入i值是否合法，当i>L.length或者i<1时，不合法，返回ERROR，否则，执行下一步；第二步修改参数e，将要删除的第i号元素赋值给它；第三步，先将第i号元素之后每个元素向前挪一位,表长减1，具体代码如下：
Status ListDelete(Sqlist *L, int i, ElemType *e)//删除指定位置的元素
{
int j =0;
if(i<1 || i> L->length) //判断i值是否合法
return ERROR;
*e = L->elem[i-1]; //获取删除的值

for(j = i; j < L->length; j++) //将删除的元素后面的元素全部向前移动
{
L->elem[i-1] = L->elem[i];
}
L->length--; //顺序表长度减1完成删除
return OK;

}

2.3.12 ListTraverse(L,visit())
初始条件：线性表L已存在。
操作结果：依次对L的数据元素调用函数visit()。一旦visit失败，则操作失败。
操作步骤：循环遍历L，使用visit函数显示L内元素所存储的值，具体代码如下：
Status ListTrabverse(Sqlist L, void (* visit)(ElemType e))//遍历顺序表，并显示元素
{

int i;
if(!L.length) return(0);
printf("\n-------------元素如下----------------\n");
for(i=0;i<L.length;i++) visit(L.elem[i]);
printf("\n");
return(1);

}

2.3.13 SavaList(L)
初始条件：线性表L存在。
操作结果：将L内数据元素信息保存到文件。
操作步骤：自行输入要保存的文件名，初始化文件指针，打开文件，若打开失败，返回FALSE，打开成功，则写入文件，具体代码如下：
Status Save(Sqlist L)//将顺序表内容保存为文件
{
FILE *fp;
char filename[30] ;
printf("请输入想保存的文件名：");
scanf("%s",filename);
//写文件的方法
if ((fp=fopen(filename,"w"))==NULL)
{
printf("文件打开失败！\n ");
return FALSE;
}
fwrite(L.elem,sizeof(ElemType),L.length,fp);
fclose(fp);
return OK;
}

2.3.14 LoadList(Sqlist &L)
初始条件：线性表已存在。
操作结果：将保存的线性表数据从文件读取出来。
操作步骤：输入要加载的文件名，若打开失败则返回FALSE，若成功，则读取文件内容，写入表L中，具体代码如下：
Status Load(Sqlist *L)//加载文件至顺序表
{
FILE *fp;
L->length=0;
char filename[30] ;
printf("请输入想加载的文件名：");
scanf("%s",filename);
if ((fp=fopen(filename,"r"))==NULL)
{
printf("文件打开失败\n ");
return FALSE;
}
while(fread(&L->elem[L->length],sizeof(ElemType),1,fp))
L->length++;
fclose(fp);

return OK;
}

2.3.15 AddElem(Sqlist &L)
初始条件：线性表L已存在。
操作结果：在L初始化后为L添加数据元素。
操作步骤：选择要输入元素个数，循环输入元素，具体到吗如下：
void add(Sqlist *L)//比较函数
{
int n,i =0;
if(!L->elem)
printf("请先初始化！");
else
{
printf("请输入要输入的元素个数：\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("输入第%d个:\n",i+1);
scanf("%d",&L->elem[i].num);
L->length++;
}
}
}

2.4 效率分析
2.41 InitList(&L)
效率分析：该函数仅初始化顺序表，计算量为一常数，故其时间复杂度为O(1).
2.4.2 DestroyList(&L)
效率分析：该函数释放头结点空间与简单赋值操作，计算量为一常数，故其时间复杂度为O(1).
2.4.3 ClearList(&L)
效率分析：该函数将表长置0，计算量为一常数，故其时间复杂度为O(1).
2.4.4 ListEmpty(L)
效率分析：该函数做简单判断操作，计算量为常数，故其时间复杂度为O(1).
2.4.5ListLength(L)
效率分析：该函数简单输出操作，计算量为一常数，故其时间复杂度为O(1).
2.4.6 GetElem(L,i,&e)
效率分析：该函数做简单判断和赋值操作，计算量为一常数，故其时间复杂度为O(1).
2.4.7 LocateElem(L,e,compare())
效率分析：该函数做简单判断和赋值操作，计算量为一常数，故其时间复杂度为O(1).
2.4.8PriorElem(L,cur_e,&pre_e)
效率分析：该函数利用函数LocateElem和Getelem，计算量与n相关，故其时间复杂度为O(n).
2.4.9 NextElem(L,cur_e,&next_e)
效率分析：该函数利用函数LocateElem和Getelem，计算量与n相关，故其时间复杂度为O(n).
2.4.10 ListInsert(&L,I,e)
效率分析：该函数执行一层循环移动元素，计算量与n相关，故其时间复杂度为O(n).
2.4.11ListDelete(&L,I,&e)
效率分析：该函数执行一层循环移动元素，计算量与n相关，故其时间复杂度为O(n).
2.4.12 ListTraverse(L,visit())
效率分析：该函数做一层循环遍历顺序表，计算量与n相关，故其时间复杂度为O(n).
2.4.13 SavaList(L)
效率分析：该函数文件保存处理，计算量为一常数，故其时间复杂度为O(1).
2.4.14 LoadList(Sqlist &L)
效率分析：该函数加载文件，计算量为一常数，故其时间复杂度为O(1).
2.4.15 AddElem(Sqlist &L)
效率分析：该函数循环输入元素，计算量与n相关，故其时间复杂度为O(n).

3 实验二 基于链式结构的线性表实现
3.1 问题描述
基于链式存储结构，实现线性表的基本的，常见的运算。
3.2 系统设计
3.2.1系统包括15个功能，分别为：
1.Creatlist 2.DestroyList
3.ClearList
4.ListEmpty
5.ListLength 6.GetElem
7.LocatElem
8.PriorElem 9.NextElem 10.ListInsert
11.ListDelete
12.ListTrabverse
13.Save the List
14.Load the List
15.Add elem to List
3.2.2系统数据物理结构类型为链式结构，存储的数据类型为结构体：
typedef struct
{
int num;
}ElemType;//定义数据类型
3.2.3定义节点结构：
typedef struct
{
ElemType data; //存储数据
struct LNode *next; //下一节点
}LNode, *LinkList; //节点结构
3.3 系统实现
3.3.1.InitList(&L)
操作结果：构造一个空的线性表L。
操作步骤：因为已分配过空间，仅改变当前链表状态，即将now置为0，具体代码如下：
Status CreatList(LinkList L) //初始化链表
{
now = 0;
return OK;

}

3.3.2.DestroyList(&L)
初始条件：链式表已经存在。
操作结果：销毁链式表。
操作步骤：循环释放节点，成功后将链表状态now置为-1，具体代码如下：
Status DestroyList(LinkList L) //销毁链表
{
LNode *p = L;
LNode *q = NULL;
while(p->next!= NULL) //释放节点空间
{
q = p->next;
free(p);
p = q;
}
now = -1; //链表状态
L->next = NULL;

return OK;
}

3.3.3.ClearList(&L)
初始条件：线性表L已存在。
操作结果：将线性表L置空。
操作步骤：循环释放节点空间，将状态now置为0，这是与销毁链式表不同的地方，具体代码如下：
Status ClearList(LinkList L) //链表清空
{
if(now == 0) //若为空，则返回1，不进行下面操作
return 1;
else
{
LNode *p= L->next;
LNode *q = NULL;
while(p!=NULL) //释放节点空间
{
q = p->next;
free(p);
p=q;
}
now =0; //修改当前链表状态为0（空）
L->next = NULL;
return OK;
}

}

3.3.4.ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回True，若L不为空，则返回False。
操作步骤：根据当前链表状态判断，若now为0，表示表为空，若不为0，则表不为空，具体代码如下：
Status ListEmpty(LinkList L) //判断链式表是否为空
{
if(now == 0) //链式表为空，返回真
return OK;
else
return FALSE; //链式表不为空返回FALSE
}

3.3.5.ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中的元素个数。
操作步骤：若表状态为0，则返回空，若不为0，循环遍历链表计数，并返回值，具体代码如下:
Status ListLength(LinkList L) //返回链式表元素个数
{
if(now == 0) //为空返回0
return 0;
else //不为空的操作
{
int i = 0; //计数变量
LNode *p = L;
while(p->next!=NULL) //循环计数
{
i++;
p = p->next;
}
return i; //返回链表长度

}
}

3.3.6.GetElem(L,i,&e)
初始条件：线性表L已存在。
操作结果：用e返回L中第i个元素数值。
操作步骤：具体代码如下：
Status GetElem(Sqlist L,int i,ElemType *e)//获取i号元素
{
if(i>L.length || i<0) //判断i值是否合法
{
return ERROR;
}
else
{
*e = L.elem[i-1]; //返回i号值
return OK;
}
}

3.3.7.LocateElem(L,e,compare())
初始条件：线性表L已存在，compare()是元素数据判定函数。
操作结果：返回L中与第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
操作步骤：若表状态为0，则返回ERROR，否则，从表头开始循环遍历链式表，利用i计数，若循环至表尾，或者查找到相同元素，则终止循环；若循环至表尾，表尾元素并不相等，表示不存在该元素，返回FALSE；若并为循环到表尾，终止循环，表示循环结束处元素即满足条件，返回位序i，具体代码如下：
Status LocateElem(LinkList L,ElemType e, Status (*compare)(ElemType,ElemType)) //查找表内与特定元素相等的元素返回序号
{
if(now == 0) //链表为空
return 0;
else
{
LNode *p = L->next;
int i =1;
while(p->next && !compare(p->data,e)) //查找与e相等的元素
{
p = p->next;
i++;
}
if(!p || !compare(p->data,e)) //如果循环到最后，未发现元素
{
return ERROR;
}
else
return i; //返回元素序号
}
}

3.3.8.PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，负责操作失败，pre_e无定义。
操作步骤：根据传入参数cur_e，利用LocateElem()函数，确定该元素位序i，若未查找到该元素或查找到该元素为首元素，均表示不存在该元素前驱，返回FALSE；否则，利用GetElem函数，将pre_e与i-1作为参数传入，获取该元素前驱，具体代码如下：
Status PriorElem(LinkList L,ElemType cur_e,ElemType *now_e) //查找指定元素前驱
{

int i=0;
i = LocateElem(L, cur_e, *compare); //使用定位函数，查找第i个值

if(!i || i == 1) //如果未找到元素或元素为第一个，则前驱不存在
{
return ERROR;
}
else
{
GetElem(L, i-1,now_e); //前驱存在，获取该元素
return i-1;
}

}

3.3.9.NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e 无定义。
操作步骤：：根据传入参数cur_e，利用LocateElem()函数，确定该元素位序i，若未查找到该元素或查找到该元素为尾元素，均表示不存在该元素前驱，返回FALSE；否则，利用GetElem函数，将next_e与i+1作为参数传入，获取该元素后继，具体代码如下：
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) //查找指定元素后继
{

int i=0;
i = LocateElem(L, cur_e, *compare); //使用定位函数，查找第i个值
if(!i || i == ListLength(L)) //如果未找到元素或元素为最后一个，则后继不存在
{
return ERROR;
}
else
{
GetElem(L, i+1,next_e); //后继存在，获取该元素
return i+1;
}
}

3.3.10.ListInsert(&L,I,e)
初始条件：线性表已存在。
操作结果：在L中第i个位置前插入新的数据元素e，L的长度加1。
具体代码：首先判断传入i值是否合法，当i>ListLength(L)+1或者i<1时，不合法，返回ERROR，否则，执行下一步；第二步，从表头循环至第i-1个元素处；第三步，新建节点，将节点插入为第i个节点，表长length增加1，具体代码如下：
Status ListInsert(LinkList L, int i, ElemType e) //在链表指定位置插入元素
{

if(i<=0|| i> ListLength(L)+1) //判断插入点是否合法
return ERROR;
LNode *p = L;
LNode *q = NULL;
int j = 0;

while(p && j<i-1) //循环至第i-1个节点处
{
j++;
p=p->next;

}
if(!p) //无元素，插入到第一个
{
q = (LNode *)malloc(sizeof(LNode));
p = q;
q->next = NULL;
now =1;
return 0;
}
else //插入到第i个处
{
q = (LNode *)malloc(sizeof(LNode));
q->data = e;
q->next = p->next;
p->next =q;
now =1;

return OK;
}
}

3.3.11.ListDelete(&L,I,&