第2章 线性表教学课件.pptx

第2章 线性表北京有冰糖葫芦，咱们成都有糖油果子。老远处看还真难以区分，在成都的北京人以为要吃到家乡的冰糖葫芦了；在北京的成都人以为要吃到家乡的糖油果子了。哈哈，原来它们尽管味道霄壤之别，却长得相像，皆是线性结构。 本章讲解线性表。要求理解线性表概念、基本操作；掌握线性表的存储结构；掌握顺序表的基本操作；掌握链表的基本操作；灵活应用线性表。提纲2.1 线性表基本概念2.2 顺序表2.3 单链表2.4 双链表2.5 循环链表2.6 线性表应用2.7 线性表学习总结2.1 线性表基本概念?线性表是由个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。当时为空表。线性表的特点是线性的，即一条线不分叉这样理解。故线性表有唯一的开始和结束，除了第1个元素，每个元素都有唯一的直接前驱；除了最后1个元素，每个元素都有唯一的直接后继。2.1 线性表基本概念如图2.1所示，太阳公公和小朋友们手拉手，他的直接前驱是2号小朋友，直接后继是4号小朋友；1号和5号小朋友分别是太阳公公的间接前驱和间接后继。2.1 线性表基本概念线性表的抽象数据接口描述如下：public interface IList { public void clear();//将线性表置成空表 public boolean isEmpty(); //判断线性表是否为空表 public int length();//返回线性表的长度 public Object get(int i) throws Exception;//获取第i个元素 public void insert(int i, Object x) throws Exception;//i位置插入x public void remove(int i) throws Exception;//删除位置i的元素 public int indexOf(Object x); //返回元素x首次出现的位序号 public void display(); //输出线性表所有元素} 根据存储结构不同，线性表分为顺序表和链表2大类。2.2 顺序表以顺序存储结构进行存储的线性表称为顺序表。2.2.1 顺序表存储结构顺序表存储结构采用顺序存储方式，逻辑上相邻的元素物理存储位置也相邻，元素存储都是连续的。由这种结构特点可知，顺序表可以随机访问快速定位某个元素，查找效率高，但删除和插入元素时，需要移动大量元素，效率低。举例：老师在教室里选择1列或1行无空位连续坐着n个学生的区域，假设有座位编号，老师可以迅速定位某个学生，如3号学生玩手机优先回答问题吧；若把3号学生请出教室后仍保持这个区域顺序存储，则4号坐到3号处，5号坐到4号处，依此类推n号坐到n-1号处；若3号学生在教室外呆了一会儿反省了，老师又让他坐回原来位置，则n-1号先坐回n号处。。。。。。此时的3号坐回4号处，原3号学生坐回3号处。在这个例子中，n个学生的区域是顺序表存储结构，对顺序表的查找较容易而对其删除和插入较麻烦。2.2.2 顺序表基本操作顺序表类的描述如下：public class SeqList implements IList { public Object[] listItem; //顺序表用一维数组作为存储空间 public int curLen; //顺序表当前长度 public int maxSize; //最大分配空间 public SeqList(int maxSize) { //构造存储空间为maxsize的顺序表 curLen = 0; maxSize = maxSize; listItem = new Object[maxSize]; } //顺序表基本操作（略）} 2.2.2 顺序表基本操作?实现顺序表往往用到一维数组：listItem[]，curLen记录实际元素个数即顺序表的长度，maxSize为最大分配空间，显然。若数组长度固定不变，这种分配称为静态分配，这样的顺序表称为静态顺序表；若程序运行时才确定maxSize，这种分配称为动态分配，这样的顺序表称为动态顺序表。动态分配可以解决因空间不够而产生的溢出问题，因它可以另外开辟空间，达到扩容目的。举例：100个座位号的教室，98个同学来上课没得问题。倘若来了3个听课的老师，那么就得在过道中加1个座位。在这个例子中，整个教室带编号的座位及学生看作顺序表，原，，扩容后，。2.2.2 顺序表基本操作初始化创建初始化创建是为顺序表分配一段预定义大小的连续空间，用listItem记录首地址。初始化元素个数不超过最大分配空间即可，如算法2.1和图2.2所示。2.2.2 顺序表基本操作?【算法2.1】顺序表的初始化创