实验一线性表 数据结构（C++语言描述）实验报告 实验一线性表 一、实验目的和要求： 1、 掌握线性表顺序存储结构和链式存储结构的基本思想； 2、 掌握顺序表和单链表的基本操作。 二、实验原理： 1、 线性表的定义：数据之间存在一对一的线性关系的数据结构的称为线性结构，也可称为线性表。 2、 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储的存储位置来表示的，通常用一维数组来表示。 顺序表的优点：存储密度大、空间利用率高、，无需为表中元素之间的逻辑关系而增加额外的存储空间。 顺序表的缺点：插入和删除操作需要移动大量的元素；表的容量难以确定；造成空间的“碎片”。 在程序设计语言中，通常用一维数组来表示表的存储区域。假设用data[ListSize]来表示一段顺序表，其中ListSize 是一个根据实际问题规模定义的足够大的整数，另外用一个实际变量length 来表示当前实际元素的个数，表中的数据从 data[0]开始依次存放，表空时 length=0. 3、 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 链式存储结构的优点：插入和删除操作方便省时。 链式存储结构的缺点：存储空间的开销大。 链式存储的方法是使用结点构造链。每个结点分为数据域和指针域两部分组成。数据域用来存放数据元素，指针域用来存放后继存储单元的地址。 三、实验内容 1、 对于给定的单链表L，设计一个算法，删除L 中值为x 的结点的直接前驱结点。 2、 已知两个单链表LA 和LB 分别表示两个集合，其元素递增排列，设计算法求出 LA和LB 的交集 C，要求C 同样以递增的单链表形式存储。 四、实验设计： 1、（1）伪算法： 建立链表L； 循环搜索数据值为x 的前一结点，若已至表尾，且其值不为value，警告，退出程序；否则，重新拉链，将数值为x 的结点的前一结点标记，将被标记的结点断开，回收被删除的结点的内存空间，将链表长度减 1。 （2）实验代码： //对给定的链表L，设计一个算法，删除L 中值为x 的结点的直接前驱结点 #include #include using namespace std; class ListNode //建立结点类 {public: char data; ListNode *link; ListNode(){link=NULL;} ListNode(int&item,ListNode *next=NULL) {data=item; link=next; } }; class List //建立链表类 {public: List(){ListNo...
