《数据结构》实验报告
一、实验要求 二、实验目的
通过该实验，深入理解顺序表的逻辑结构、物理结构等概念，掌握顺序表基本操作的编程实现，注意顺序表插入、删除等操作过程中数据元素的移动现象，培养学生编写程序时，要考虑程序的强壮性，熟练掌握通过函数参数返回函数结果的办法。
三、设计思想
程序分为两大部分，一部分是自定义的头文件，另一部分是主要程序代码。自定义头文件又分成两部分，common.h中是预定义常量和类型，sqlist.h是线性表的动态分配顺序存储结构以及各函数的声明。.cpp部分分为sqlist.cpp和main.cpp。Sqlist.cpp 是线性表的基本操作，main.cpp是主函数，调用Sqlist.cpp中的函数。
四、主要源代码
Common.h
#define TRUE 1
#define ERROR 0
#define OK 1
#define FALSE 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
SqList.h
#include <stdlib.h>
#include "Common.h"
#define ElemType int
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct{
ElemType* elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） } SqList;
//基本操作
Status InitList(SqList &L);
//操作结果：构造一个空的线性表L。
Status DestroyList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：销毁线性表L。
Status ClearList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：将L重置为空表。
bool ListEmpty(SqList L);
//初始条件：线性表L已存在。
//操作结果：若L为空表，则返回TRUE，否则返回FALSE。
int ListLength(SqList L);
//初始条件：线性表L已存在。
//操作结果：返回L中数据元素的个数。
Status GetElem(SqList L, int i, ElemType &e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)。
//操作结果：用e返回L中第i个数据元素的值。
int LocateElem(SqList L, int e, bool (*equal)(ElemType, ElemType)); //初始条件：线性表L已存在，compare()是数据元素判定函数。 //返回L中第一个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
Status ListInsert(SqList &L, int i, ElemType e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1.
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.
Status ListDelete(SqList &L, int i, ElemType &e);
//初始条件：线性表L已存在且非空，1<=i<=ListLength(L).
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1.
Status ListTraverse(SqList L, bool (*visit)(ElemType));
//初始条件：线性表L已存在
//操作结果：依次对L的每个元素调用函数visit().一旦visit()失败,则操作失败。
.cpp
#include <malloc.h>
#include "SqList.h"
Status InitList(SqList &L){
//操作结果：构造一个空的线性表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;
}//InitList
Status DestroyList(SqList &L){
//操作结果：销毁线性表L。
free(&L);
return OK;
}
Status ClearList(SqList &L) {
//操作结果：将L重置为空表。
L.length = 0;
return OK;
}
bool ListEmpty(SqList L){
//操作结果：若L为空表，则返回TRUE，否则返回FALSE。
if(0 == L.length)
return true;
else return false;
}
int ListLength(SqList L){
//操作结果：返回L中数据元素的个数。
return L.length;
}
Status GetElem(SqList L, int i, ElemType &e){
//1<=i<=ListLength(L)。
//操作结果：用e返回L中第i个数据元素的值。
if(i < 1 || i>=L.length) return ERROR;
e = L.elem[i-1];
return OK;
}
int LocateElem(SqList L, ElemType e, bool (*equal)(ElemType, ElemType)){ //compare()是数据元素判定函数。
//返回L中第一个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.
int i = 1;
ElemType* p = L.elem;
while(i <= L.length && !(*equal)(*p++, e)) ++i;
if(i <= L.length) return i;
else return 0;
}
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){
//操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
int i=1;
while(i <= L.length && !(cur_e==L.elem[i-1])) ++i;
if(i<2 || i>L.length)
return ERROR;
pre_e = L.elem[i-2];
return OK;
}
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e){
//操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
int i=1;
while(i <= L.length && !(cur_e==L.elem[i-1])) ++i;
if(i<2 || i>L.length)
return ERROR;
next_e = L.elem[i];
return OK;
}
Status ListInsert(SqList &L, int i, ElemType e){
//1<=i<=ListLength(L)+1.
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.
if(i < 1 || 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) exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType * q = &(L.elem[i-1]); //q为插入位置
ElemType * p;
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1) = *p; //右移
*q = e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList &L, int i, ElemType &e){
//1<=i<=ListLength(L).
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1.
if(i<1 || i>L.length) return ERROR;
ElemType* p = &(L.elem[i-1]);
e = *p;
ElemType* q = L.elem + L.length - 1;
for(++p;p<=q;++p) *(p-1) = *p;
--L.length;
return OK;
}
Status ListTraverse(SqList L, bool (*visit)(ElemType)){
//操作结果：依次对L的每个元素调用函数visit().一旦visit()失败,则操作失败。
int i=1;
ElemType* p = L.elem;
while(i <= L.length && (*visit)(*p++)) ++i;
return OK;
}
Main.cpp
#include<stdio.h>
#include "SqList.h"
bool equal(int a,int b)
{
if(a==b)
return true;
return false;
}
bool visit(ElemType e)
{
printf("%d",e);
return true;
}
int main()
{
printf("1---初始化一个列表\n");
printf("2---显示线性表\n");
printf("3---获取线性列表指定位置的元素\n");
printf("4---求线性表长度\n"); printf("5---求前驱\n"); printf("6---求后继\n"); printf("7---在线型表指定位置插入元素\n"); printf("8---删除指定位置元素\n"); printf("9---清空线性列表\n"); printf("10---判断线性列表是否为空\n"); printf("11---销毁线性列表\n"); printf(" 退出---输入负数：\n"); SqList L; ElemType k; ElemType pre_k; ElemType next_k; int i,j,m; printf("\n"); printf("输入想要的操作:"); scanf("%d",&j); if(j== 1){ InitList(L); for( i=0;i<20;i++) { k=i+1; ListInsert(L,i+1,k); } printf("已初始化线性表L\n"); printf("输入想要的操作:"); scanf("%d",&j); } if(j==2) { ListTraverse(L, visit); printf("\n"); printf("输入想要的操作:"); scanf("%d",&j); } if(j==3) { printf("输入想要的元素:"); scanf("%d",&m);
if(m<0 || m>20) { printf("输入错误!"); } else{ GetElem(L,m,k); printf("该元素是:%d\n",k); } printf("输入想要的操作:"); scanf("%d",&j); } if(j== 4) { printf("线性表长度是：%d\n",ListLength(L)); printf("输入想要的操作:"); scanf("%d",&j); } if(j==5) { printf("输入求第几个数的前驱:"); scanf("%d",&k); PriorElem(L,k,pre_k); printf("前驱是:%d\n",pre_k); printf("输入想要的操作:"); scanf("%d",&j); } if(j==6) { printf("输入求第几个数的后继:"); scanf("%d",&k); NextElem(L,k,next_k); printf("后继是:%d\n",next_k); printf("输入想要的操作:"); scanf("%d",&j); } if(j==7) { printf("在第几个位置插入元素?"); scanf("%d",&k); printf("插入的数字是:"); int x; scanf("%d",&x); ListInsert(L,k,x); printf("插入后线性表为:\n");
ListTraverse(L, visit); printf("\n"); printf("输入想要的操作:"); scanf("%d",&j); } if(j==8) { printf("输入要删除的元素的位置"); scanf("%d",&k); ListDelete(L,k,m); printf("所删除的元素是:%d",m); printf("删除元素后线性表为:\n"); ListTraverse(L,visit); printf("\n"); printf("输入想要的操作:"); scanf("%d",&j); } if(j==9) { ClearList(L); printf("线性表已清空!\n"); printf("线性表长度:%d\n",ListLength(L)); printf("输入想要的操作:"); scanf("%d",&j); } if(j==10) { if(ListEmpty(L)) { printf("kong\n"); } printf("输入想要的操作:"); scanf("%d",&j); } if( j==11) { DestroyList(L); printf("线性表已销毁\n"); } if(j<=0) { printf("任意键退出\n"); } return 0;
}
五、调试与测试数据
主函数中忘记添加自定义头文件
主函数一开始是用的switch语句，但是执行其中一个之后，就无法接着执行下一项操作，所以改用if语句。
六、实验总结
第一次写这种比较大的数据结构程序，感到很难，无从下手。后来看了一些网上的关于线性表的程序，也终于受了点启发，又请教了其他同学，听了听老师的讲解，才渐渐的写出程序。但是调试又遇到了点问题，通过在网上查询也都解决。通过写这次的程序，对我以后有很大帮助。