实验一-线性表操作-实验报告.doc

中国矿业大学计算机学院实验报告 "课程名称 数据结构 实验名称__线性表操作 " "实验报告要求：1.实验目的 2.实验内容 3.实验步骤 " "4.运行结果 5.流程图 6.实验体会 " " 一、实验目的 " "1 熟悉并掌握线性表的逻辑结构、物理结构。 " "2 熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。 " "3 " "熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件" "之间的相互关系及各自的作用。 " "4 " "熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程" "。 " "二、实验要求 " "1 实验之前认真准备，编写好源程序。 " "2 " "实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性" "的验证。 " "3 不断积累程序的调试方法。 " "三、实验内容 " "基本题: " "1 对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。 " "源程序： " " #include<iostream.h> " "#include<conio.h> " "#include<stdlib.h> " " " "const LIST_INIT_SIZE=10; " "const LISTINCREMENT=1; " " " "typedef struct " "{ " "int *elem; " "int length; " "int listsize; " "}SqList; " " " "void InitList_Sq(SqList&L) //构造一个空的线性表L " "{ " "L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); " "if(!L.elem) " "exit(0); //存储分配失败 " "L.length=0; //空表长度为0 " "L.listsize=LIST_INIT_SIZE; //初始存储容量 " "cout<<"OK!"<<endl; " "} " " " "void ListInsert_Sq(SqList&L,int i,int j) " "//在顺序线性表L中第i个位置之前插入新的元素j， " "//i的合法值为1<=i<=ListInsert_Sq(L)+1 " "{ " "if(i<1""i>L.length+1) " "cout<<"ERROR!"<<endl; //i值不合法 " "if(L.length>=L.listsize) " "//当前存储空间已满，增加分配 " "{ " "int " "*newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(" "int)); " "if(!newbase) " "exit(0); //存储分配失败 " "L.elem=newbase; //新基址 " "L.listsize+=LISTINCREMENT; //增加存储容量 " "} " "int *q=&(L.elem[i-1]); " "for(int*p=&(L.elem[L.length-1]);p>=q;--p) " "*(p+1)=*p; " "*q=j; " "++L.length; " "cout<<"OK!"<<endl; " "}//ListInsert_Sq " " " "void ListDelete_Sq(SqList&L,int i,int&j) //在顺序线性表L中删除 " "第i个元素，并用j返回其值 " "//i的合法值为1<=i<=ListInsert_Sq(L) " "{ " "if((i<1)""(i>L.length)) " "cout<<"ERROR!"<<endl; //i值不合法 " "int *p=&(L.elem[i-1]); //p为被删除元素的位置 " "j=*p; //被删除元素的值赋给j " "int *q=L.elem+L.length-1; //表尾元素的位置 " "for(++p;p<=q;++p) " "*(p-1)=*p; " "--L.listsize; //被删除元素之后的元素左移" "cout<<"OK!"<<endl; //表长减1 " "}//ListDelete_Sq " " " "bool compare(int m,int n) " "{ " "if(m==n) " "return true; " "else " "return false; " "} " " " "int LocateElem_Sq(SqList L,int j) " "//在顺序线性表L中查找第1个值与j满足compare() 实验报告涉及的知识点主要集中在数据结构中的线性表操作，特别是顺序存储的线性表，以及C++编程实践。以下是对这些知识点的详细说明： 1. **线性表的逻辑结构与物理结构**： - **逻辑结构**：线性表是一种抽象的数据结构，它包含一个有限序列的元素，每个元素都有一个前驱和/或后继，除了第一个元素没有前驱，最后一个元素没有后继。 - **物理结构**：在顺序存储的线性表中，元素在内存中是按顺序连续存放的，可以是数组形式。这种存储方式便于直接访问元素，但插入和删除操作可能涉及到大量元素的移动。 2. **顺序表的存储结构**： - 顺序表采用数组来存储线性表中的元素，数组的大小通常设定为一个初始值（如LIST_INIT_SIZE），并在需要时通过动态扩展（如使用realloc）来增加容量。 3. **基本操作**： - **初始化**：InitList_Sq函数用于初始化一个空的顺序表，分配初始容量的内存，并设置长度为0。 - **插入操作**：ListInsert_Sq函数在指定位置插入元素。如果当前表满，需要扩展存储空间。插入操作涉及到后继元素的逐个右移。 - **删除操作**：ListDelete_Sq函数删除指定位置的元素，删除后的元素左移，同时更新表的长度。删除操作要求提供合法的索引，否则返回错误提示。 - **查找操作**：LocateElem_Sq函数在顺序表中查找满足特定条件的元素，这里使用了compare函数来比较元素值。 4. **C++编程实践**： - **头文件**：实验代码中包含了<iostream.h>、<conio.h>和<stdlib.h>三个头文件，分别用于输入输出、控制台输入输出和内存管理。 - **结构体**：定义了一个名为SqList的结构体，包含元素指针、长度和存储容量三个成员，表示顺序表的状态。 - **内存管理**：使用malloc和realloc进行动态内存分配和释放，确保了存储空间的灵活性。 - **函数设计**：每个操作都封装为一个函数，符合面向过程的编程思想，便于代码复用和模块化。 5. **程序的正确性和健壮性**： - 实验要求在编写源程序后，进行认真调试，确保程序的正确性。同时，要考虑程序的健壮性，即处理非法输入的能力，例如在插入和删除操作中检查索引的有效性。 6. **VC++环境**： - 实验还涉及到使用VC++环境进行多文件的输入、编辑、调试和运行，这是实际编程中不可或缺的一部分。 7. **实验体会**： - 通过实验，学生可以加深对线性表概念的理解，掌握顺序表的实现细节，提升C++编程技能，同时学会如何使用开发工具进行程序的调试和测试。 该实验旨在通过实际操作加深对线性表这一重要数据结构的理解，以及锻炼使用C++进行程序设计和调试的能力。