第2章 线性表和链表.pptxVIP

第2章 线性表和链表第页4中常见的数据逻辑结构：集合、线性、树形、图形；4种数据存储结构：顺序、链式、索引、散列主要内容 线性表1 顺序表2 JAVA类库中的顺序表34 单链表5 双向链表6 循环链表第页 线性表的定义第页线性表(Linear List)是一种可以在任意位置进行插入和删除数据元素操作的、由n(n=0)个相同类型数据元素a0,a1,……,ai,……an-1组成的一个有限序列，可表示为：( a0,a1,……,ai,……an-1)。线性表的长度、空表、表头元素、表尾元素、前驱、后继；用二元组表示为linear_list=(A,R) A={ai|0=i=n-1,n0,ai?ElemType}; R={r},r={ai,ai+1|0=i=n-1}。线性表的抽象数据类型第页数据集合操作集合添加：在线性表的末尾添加一个数据元素；插入：在线性表的第i个元素前插入一个数据元素；删除：删除第i个数据元素；获取：获取第i个数据元素；遍历线性表：从第一个元素开始，访问表中每个数据元素；获取数据元素个数；判断线性表是否为空。顺序表地址 ……20002002200420062008 …… ……2 a03 a14a25a36a4 ……第页线性表的存储结构为顺序结构，该线性表叫做顺序表。顺序表的存储结构：数据元素占据内存中一片连续的存储单元。顺序表第页顺序表的操作插入:将数据元素插入顺序表指定的位置i处；删除:将指定位置i处的数据元素删除；查询：查询指定位置的数据元素，或者查询指定关键字的数据元素。实例第页例题2-1：对学生信息进行管理，要求对学生信息记录进行添加、查询和浏览操作，学生信息包括姓名、学号和成绩3个字段。顺序表的性能分析支持顺序存取，读取数据元素操作的时间复杂度为o(1);在顺序表中插入和删除一个数据元素的时间复杂度为o(n);缺点：需要预先给出表中数据元素的个数，插入和删除数据时，需要移动大量的数据元素。第页2.3 JAVA类库中的顺序表第页类ArrayList:使用类ArrayList对学生信息进行管理；链表学号姓名性别入学成绩学号姓名性别入学成绩201001吴承志男487201006何文颖女458201002李淑芳女450201007赵胜利男456201003刘丽女423201008崔文靖女478201004张会友男465201009刘丽女432201005石宝国男485201010魏永鸣男412吴承志……李淑芳……刘丽……张会友2100230020002080第页2.4 单链表dddd?head第页单链表的操作第页插入删除查询:从第一个结点开始,逐个访问每个结点,比对关键字;遍历:从链表的头结点开始,逐个访问每个结点,并输出结点信息.单链表的性能第页可以任意的增加节点，删除节点和添加节点时不需要大量的移动数据；不支持随机读取，查找(删除、插入)节点时需要遍历链表；一旦链表中的指针断开，链表就丢失。2.5 双向链表1.节点：指针域有两个：一个指向其前驱，一个指向其后继；2.链表：有一个指向表头的指针(head)，一个指向表尾的指针(tail)。第页双向链表的操作1.插入(头节点前、尾节点后、两个节点间)第页双向链表的操作第页插入(头节点前、尾节点后、两个节点间)插入(头节点前、尾节点后、两个节点间)第页双向链表的操作第页2. 删除(头节点、尾节点、中间节点)第页双向链表的操作第页3.查询:根据关键字查询一个节点。4.遍历：从双向链表的头节点或尾节点开始，逐个输出各个节点的信息。双向链表的实现第页在双向链表的尾结点添加一个结点，遍历链表，根据姓名查找结点。1.定义节点(StudNode)2.定义链表(StudOperation、StudLinkedList)3.链表的实现(StudLinkedListUser)2.6 循环链表第页循环单链表有一个头指针head、一个尾指针tail；尾结点的指针域指向头结点；循环链表第页循环双链表有一个头结点head，一个尾结点tail;头结点指向前驱的指针域指向尾结点，尾结点指向后继的指针域指向头结点。