第2章 线性表2.1线性表2.2顺序表2.3单链表2.4循环单链表2.5双向链表2.6仿真链表
第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表
线性表线性表的定义线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n（n≥0）个相同类型数据元素ao，ai，a2，…，an-1组成的线性结构
线性表 线性表的定义 线性表是一种可以在任意位置进行插入和删除数据元素操 作的、由n（n ≥ 0）个相同类型数据元素a0 , a1 , a2 , ., an-1 组成的线性结构
线性表抽象数据类型的接口定义如下：interface List3void insert(int i, Object obi);//插入//删除Object delete(int i);//取数据元素Object getData(int i);//求元素个数int getSize();bool isEmpty();
线性表抽象数据类型的接口定义如下： interface List { void insert(int i, Object obj);//插入 Object delete(int i); //删除 Object getData(int i); //取数据元素 int getSize(); //求元素个数 bool isEmpty(); }
顺序表特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素需要预先确定数据元素的最大个数。解决问题的思路：改用另一种存储方式：链式存储结构
顺序表特点：逻辑关系上相邻的两个元素在物理存储位置上也 相邻； 优点:可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路：改用另一种存储方式： 链式存储结构
链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，指针表示一个数据元素逻一个数据元素和一个指辑意义上的存储位置针称为一个结点链式存储结构是基于指针实现的链式存储结构的线性表称为链表。根据结点构造链的方法不同，链表主要有单链表循环单链表和双向链表三种
根据结点构造链的方法不同，链表主要有单链表、 循环单链表和双向链表三种。 链式存储结构是用指针把相互直接关联的结点（即 直接前驱结点或直接后继结点）链接起来。 指针表示一个数据元素逻 辑意义上的存储位置 一个数据元素和一个指 针称为一个结点 链式存储结构是基于指针实现的 链式存储结构的线性表称为链表