数据结构上机报告实验一
《数据结构》上机报告
_______年____月____日
姓名__________ 学号___________ 同组成员 ___________
1. 实验题目及要求
实验一、编写一个程序，实现顺序表的各种基本运算，并在此基础上完成以下功能:
1) 初始化顺序表；
2) 依次采用尾插入法插入a,b,c,d,e元素；
3) 输出顺序表L；
4) 输出顺序表L的长度；
5) 判断顺序表L是否为空；
6) 输出顺序表L的第三个元素；
7) 输出元素a的位置；
8) 在第4个元素位置上插入f元素；
9) 输出顺序表L；
10) 删除L的第3个元素；
11) 输出顺序表L；
12) 释放顺序表。
2. 需求分析
首先初始化顺序表
（1） 依次采用尾插入法插入a,b,c,d,e元素
输入参数的格式和合法取值范围：依次输入a,b,c,d,e，用逗号分隔。
输出格式：按顺序显示abcde元素。
测试数据：依次插入a,b,c,d,e元素后，显示顺序表长度abcde。
（2） 输出顺序表长度，判断其是否为空，并输出L的第三个元素和元素a的位置
输入参数的格式和合法取值范围：输入顺序表a,b,c,d,e，用逗号分隔。
输出格式：按顺序显示：顺序表的长度为多少
顺序表是否为空
顺序表第三个元素的值
元素a的位置为多少
测试数据：依次显示出顺序表的长度=5，顺序表为非空，
顺序表第三个元素是c，元素a的位置=1.
（3） 在第4个元素位置上插入f元素
输入参数的格式和合法取值范围：在原有顺序表L第4个元素位置插入f元素。
输出格式：按顺序显示第4个元素位置插入f元素的顺序表abcfde。
测试数据：依次显示出顺序表的元素abcfde。
（4） 删除第三个元素
输入参数的格式和合法取值范围：在顺序表abcfde中删除第三个元素。
输出格式：按顺序显示删除了第三个元素的顺序表abfde。
测试数据：一次显示顺序表abfde。
3. 概要设计
（1） 给出所用抽象数据类型的逻辑定义。
ADT LinearList {
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
结构关系：R={i,ai+1＞|ai,ai+1 ∈D}
基本操作：
InitList(&L)
操作前提：L是一个未初始化的线性表。
操作结果：将L初始化为一个空的线性表。
DestroyList(&L)
操作前提：线性表L已存在。
操作结果：销毁线性表L。
ListEmpty(L)
操作前提：线性表L已存在。
操作结果：若L为空表，则返回TURE，否则返回FALSE。
ListLength(L)
操作前提：线性表L已存在。
操作结果：返回L中数据元素个数。
DisplayList(L)
操作前提：线性表L已存在。
操作结果：打印表中元素。
ListInsert (&L,i , e)
操作前提：线性表L已存在，1≤i≤ListLength（L）+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度+1。
ListDelete (&L,i, e)
操作前提：线性表L已存在且非空，1≤i≤ListLength（L）。
操作结果：删除L的第i个元素数据，并用e返回其值，L的长度—1。
GetElem(L, i,&e)
操作前提：线性表L已存在，1≤i≤ListLength（L）。
操作结果：用e返回L中第i个元素的值。
LocateElem (L,e,compare( ))
操作前提：线性表L已存在，compare( )是数据元素判定函数。
操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。
若这样的数据元素不存在，则返回值为0。
（2） 画出各模块之间的调用关系图。
（3） 用伪码给出主程序的主要处理过程
#include＜stdio.h＞
#include＜malloc.h＞
#include＜process.h＞
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType * elem;
int length;
int Listsize;
}SqList;
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (! L.elem) exit(0);
L. length=0;
L.Listsize=LIST_INIT_SIZE;
return OK;}
Status DestroyList_Sq ( SqList &L)
{ if (!L.elem) return ERROR;
free (L.elem);
L.elem = NULL;
L.length = 0;
L.Listsize = 0;
return OK;}
Status EmptyList_Sq ( SqList L)
{ if(L.length==0) return TRUE;
else return FALSE;}
int LengthList_Sq ( SqList L)
{ if(!EmptyList_Sq(L)) return L.length;
else return 0;}
Status DisplayList_Sq ( SqList L)
{ int i=0;
for(int j=L.length-1;j＞=0;j--)
{ printf("%c",L.elem[i]);
i++;}
return OK; }
Status ListInsert_Sq(SqList &L, int i , ElemType e) {
if (i＜1|| i＞L.length+1) return ERROR;
if (L.length＞=L.Listsize) return ERROR;
for (int j=L.length-1 ; j＞= i-1; --j)
L.elem[j+1]= L.elem[ j];
L.elem[i-1] =e;
++L.length;
return OK;}
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
if ((i＜1)||(i＞L.length)) return ERROR;
e = L.elem[i-1];
for (int j= i; j＜= L.length-1; ++j)
L.elem[j-1] = L.elem[ j];
--L.length;
return OK;}
Status GetElemList_Sq ( SqList L,int i,ElemType &e)
{if(i＜1||i＞L.length) return ERROR;
e=L.elem[i-1];
return OK;}
int LocateElemList_Sq( SqList L,ElemType e)
{int i=0;
while(i
if(i＞=L.length) return 0;
return i+1;}
void main()
{SqList L;
ElemType e;
printf("(1)初始化顺序表\n");
InitList_Sq(L);
printf("(2)依次插入a,b,c,d,e元素\n");
ListInsert_Sq(L,1,'a');
ListInsert_Sq(L,2,'b');
ListInsert_Sq(L,3,'c');
ListInsert_Sq(L,4,'d');
ListInsert_Sq(L,5,'e');
printf("(3)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(4)顺序表的长度=%d\n",LengthList_Sq(L));
printf("(5)顺序表为%s\n",(EmptyList_Sq(L)?"空":"非空"));
GetElemList_Sq(L,3,e);
printf("(6)顺序表的第三个元素是%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElemList_Sq(L,'a'));
printf("(8)在第四个元素插入元素f\n");
ListInsert_Sq(L,4,'f');
printf("(9)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(10)删除第三个元素\n");
ListDelete_Sq(L,3,e);
printf("(11)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(12)释放顺序表\n");
DestroyList_Sq(L);}
4. 详细设计
（1） 类型定义
typedef struct{
ElemType * elem;
int length;
int Listsize;
}SqList;
（2） 给出所用抽象数据类型中每个操作的伪码算法
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (! L.elem) exit(0); L. length=0; L.Listsize=LIST_INIT_SIZE;
return OK;}
Status DestroyList_Sq ( SqList &L)
{ if (!L.elem) return ERROR;
free (L.elem); L.elem = NULL; L.length = 0; L.Listsize = 0; return OK;}
Status EmptyList_Sq ( SqList L)
{ if(L.length==0) return TRUE;
else return FALSE;}
int LengthList_Sq ( SqList L)
{ if(!EmptyList_Sq(L)) return L.length;
else return 0;}
Status DisplayList_Sq ( SqList L)
{ int i=0; for(int j=L.length-1;j＞=0;j--)
{ printf("%c",L.elem[i]);i++;} return OK; }
Status ListInsert_Sq(SqList &L, int i , ElemType e) {
if (i＜1|| i＞L.length+1) return ERROR;
if (L.length＞=L.Listsize) return ERROR;
for (int j=L.length-1 ; j＞= i-1; --j) L.elem[j+1]= L.elem[ j];
L.elem[i-1] =e; ++L.length; return OK;}
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
if ((i＜1)||(i＞L.length)) return ERROR; e = L.elem[i-1];
for (int j= i; j＜= L.length-1; ++j) L.elem[j-1] = L.elem[ j];
--L.length; return OK;}
Status GetElemList_Sq ( SqList L,int i,ElemType &e)
{if(i＜1||i＞L.length) return ERROR; e=L.elem[i-1]; return OK;}
int LocateElemList_Sq( SqList L,ElemType e)
{int i=0; while(i
if(i＞=L.length) return 0; return i+1;}
（3） 给出其他模块的伪码算法
void main()
{SqList L;
ElemType e;
printf("(1)初始化顺序表\n");
InitList_Sq(L);
printf("(2)依次插入a,b,c,d,e元素\n");
ListInsert_Sq(L,1,'a');
ListInsert_Sq(L,2,'b');
ListInsert_Sq(L,3,'c');
ListInsert_Sq(L,4,'d');
ListInsert_Sq(L,5,'e');
printf("(3)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(4)顺序表的长度=%d\n",LengthList_Sq(L));
printf("(5)顺序表为%s\n",(EmptyList_Sq(L)?"空":"非空"));
GetElemList_Sq(L,3,e);
printf("(6)顺序表的第三个元素是%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElemList_Sq(L,'a'));
printf("(8)在第四个元素插入元素f\n");
ListInsert_Sq(L,4,'f');
printf("(9)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(10)删除第三个元素\n");
ListDelete_Sq(L,3,e);
printf("(11)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(12)释放顺序表\n");
DestroyList_Sq(L);}
5. 调试分析
（1） 调试过程中主要遇到哪些问题？是如何解决的？
调式过程中发现总是粗心大意忘了加分号或者打错字，所以学习C语言一定要细心仔细，不能着急。
用DisplayList函数时出现了问题，后来经过询问同学和查阅书本对程序进行了改正，使其能够正确进行。
（2） 经验和体会
通过这次上机实验，对顺序表的各功能有了进一步的了解和学习，也对C语知识进行了巩固。
6. 测试结果
7. 附件
#include＜stdio.h＞
#include＜malloc.h＞
#include＜process.h＞
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType * elem;
int length;
int Listsize;
}SqList;
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (! L.elem) exit(0);
L. length=0;
L.Listsize=LIST_INIT_SIZE;
return OK;}
Status DestroyList_Sq ( SqList &L)
{ if (!L.elem) return ERROR;
free (L.elem);
L.elem = NULL;
L.length = 0;
L.Listsize = 0;
return OK;}
Status EmptyList_Sq ( SqList L)
{ if(L.length==0) return TRUE;
else return FALSE;}
int LengthList_Sq ( SqList L)
{ if(!EmptyList_Sq(L)) return L.length;
else return 0;}
Status DisplayList_Sq ( SqList L)
{ int i=0;
for(int j=L.length-1;j＞=0;j--)
{ printf("%c",L.elem[i]);
i++;}
return OK; }
Status ListInsert_Sq(SqList &L, int i , ElemType e) {
if (i＜1|| i＞L.length+1) return ERROR;
if (L.length＞=L.Listsize) return ERROR;
for (int j=L.length-1 ; j＞= i-1; --j)
L.elem[j+1]= L.elem[ j];
L.elem[i-1] =e;
++L.length;
return OK;}
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
if ((i＜1)||(i＞L.length)) return ERROR;
e = L.elem[i-1];
for (int j= i; j＜= L.length-1; ++j)
L.elem[j-1] = L.elem[ j];
--L.length;
return OK;}
Status GetElemList_Sq ( SqList L,int i,ElemType &e)
{if(i＜1||i＞L.length) return ERROR;
e=L.elem[i-1];
return OK;}
int LocateElemList_Sq( SqList L,ElemType e)
{int i=0;
while(i
if(i＞=L.length) return 0;
return i+1;}
void main()
{SqList L;
ElemType e;
printf("(1)初始化顺序表\n");
InitList_Sq(L);
printf("(2)依次插入a,b,c,d,e元素\n");
ListInsert_Sq(L,1,'a');
ListInsert_Sq(L,2,'b');
ListInsert_Sq(L,3,'c');
ListInsert_Sq(L,4,'d');
ListInsert_Sq(L,5,'e');
printf("(3)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(4)顺序表的长度=%d\n",LengthList_Sq(L));
printf("(5)顺序表为%s\n",(EmptyList_Sq(L)?"空":"非空"));
GetElemList_Sq(L,3,e);
printf("(6)顺序表的第三个元素是%c\n",e);
printf("(7)元素a的位置=%d\n",LocateElemList_Sq(L,'a'));
printf("(8)在第四个元素插入元素f\n");
ListInsert_Sq(L,4,'f');
printf("(9)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(10)删除第三个元素\n");
ListDelete_Sq(L,3,e);
printf("(11)输出顺序表:");
DisplayList_Sq(L);
printf("\n");
printf("(12)释放顺序表\n");
DestroyList_Sq(L);}
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构上机实验答案
数据结构实验指导书答案实验一1请编写函数intfunintaintb函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同若…
-
数据结构上机实验报告
空间数据结构基础上机实验报告20xx姓名班级地信121学号07122857环境与测绘学院级实验报告1C面向对象程序设计范例1二维坐…
-
数据结构第一次上机实验报告
数据结构第一次上机实验报告线性表实验要求1实现顺序表结构的创建插入删除查找等操作2利用上述顺序表操作实现如下程序建立两个顺序表表示…
-
数据结构上机实验报告
计算机科学与技术学院数据结构教程实验报告20xx20xx学年第2学期学生姓名学生专业学生班级学生学号20xx65实验报告一设计人员…
-
数据结构上机实验报告7
一．实验目的文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。二．实验内容被编译的文本文件…
- 《数据结构》上机实验报告—常用排序算法的实现
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构上机实验报告2
广东工业大学实验报告自动化学院网络工程专业班学号姓名何宇航成绩评定教师签名许亮一实验目的设计一个一元稀疏多项式简单计算器二实验内容…
-
数据结构实验报告34354
合肥师范学院实验报告册20xx20xx学年第2学期系别实验课程专业班级姓名学号指导教师计算机科学与技术系数据库原理计算机软件12级…