考研课件数据结 构线 性表.ppt

《考研课件数据结 构线 性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构线性表张宪超教授本节重点复习要点考点精讲例题精解同步练习复习要点（1）1.线性表的概念线性表的定义和特点线性表的基本操作2.线性表的存储表示顺序表的定义及基本运算的实现单链表的定义及基本运算的实现3.线性表的特殊链接表示循环链表的特殊遍历方式双向链表的方向性复习要点（2）4.线性表的应用（1）在一维数组上的算法，如原地逆置、非零元素压缩、成块元素移动等。在一维数组上的递归算法，如求和平均值等。在顺序表上的查找、插入、删除、合并、求交等算法及性能分析。在单链表上的迭代求解算法及性能，包括统

2、计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、链表逆转等。复习要点（3）4.线性表的应用（2）带表头结点的单链表上的迭代算法，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、两个有序链表的合并等。单链表的递归算法，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、求链表各结点值的和、平均值等。循环链表的迭代算法、双向链表的迭代算法。5.多项式的建立，两个多项式的相加，两个多项式的相乘算法考点精讲1.线性表的

3、定义和基本操作线性表的定义线性表的操作2.线性表的实现线性表的顺序存储线性表的链式存储顺序存储与链式存储的比较其他线性表的形式3.线性表的插入和删除操作基于顺序存储结构的运算基于链式存储结构的运算线性表的定义和基本操作线性表的定义线性表的操作线性表的定义和基本操作（1）线性表的定义（1）通常，定义线性表为n个数据元素（或称为表元）的有限序列。记为。其中L是表名，ai是表中的结点，是不可再分割的数据。n是表中数据元素的个数，也称为表的长度，若n=0叫做空表。线性表的特点存在唯一的一个头元素（第一个

4、元素）存在唯一的一个尾元素（最后一个元素）除了第一个元素外，集合中的每个元素均只有一个直接前驱除了最后一个元素外，集合中的每一个元素均只有一个直接后继线性表的定义和基本操作（2）线性表的定义（2）理解线性表的要点表中的元素具有逻辑上的顺序性，在表中各元素的排列有其先后次序表中元素个数有限表中元素都有数据元素，即每一个表元素都是不可再分的原子数据表中元素的数据类型都相同表中元素具有抽象性，即仅讨论表元素之间的逻辑关系线性表的定义和基本操作（3）线性表的操作表的初始化运算：将线性表置为空表求表长度运

5、算：统计线性表中表元素的个数查找运算：查找线性表中第i个元素或查找表中具有给定关键值的表元素插入运算：将新表元素插入到线性表第i个位置上，或插入到具有给定关键值的表元素的前面或后面删除运算：删除表中第i个元素，或删除给定关键值的表元素读取运算：读取线性表第i个表元素的值复制运算：复制线性表所有表元素到另一个线性表线性表的实现线性表的顺序存储线性表的链式存储顺序存储与链式存储的比较其他线性表的形式线性表的顺序存储线性表的顺序存储又称为顺序表一组地址连续的存储单元存储表中元素逻辑关系相邻的表元素在物

6、理位置上也相邻线性表的顺序存储结构线性表的链式存储线性表的链式存储又称为线性链表结点之间在空间上可以连续也可以不连续结点内附的链接指针表示元素之间的逻辑关系逻辑上相邻的表元素在物理位置上不一定相邻顺序存储与链式存储的比较比较顺序存储链式存储访问方式顺序存取/直接存取从链表头顺序存取逻辑关系与物理位置完全对应不一定对应存储空间利用率无附加空间附加一个指针的空间查找速度快慢插入和删除速度慢快空间限制静态分配：不能扩充不需事先分配动态分配：扩充需移动元素其他线性表的形式双向链表每个结点包含两个指针，指

7、明直接前驱和直接后继元素，可在两个方向上遍历该结点相邻的元素循环链表表尾结点的后继指针指向表中的第一个结点，可以在任意位置上遍历链表静态链表借助数组来描述线性表的链式存储结构线性表的插入和删除运算基于顺序存储结构的运算基于链式存储结构的运算基于顺序存储结构的运算基于链式存储结构的运算单链表的查找运算单链表的插入运算单链表的删除运算单链表的查找运算templateLink*LinkList::SetPos(inti){if(i==-1)//i为-1则定位到头结点retu

8、rnhead;intcount=0;Link*p=newLink(head->link);while(p!=NULL&&countlink;count++;}returnp;//指向第i个结点，当链表长度小于i时返回NULL}单链表的插入运算templateboolLinkList::Insert(constinti,constTvalue){if((p=SetPos(i-1))==NULL)//p是第i个结点的前驱{cout<<"插入操作不允