数据结构电子课件教案第2章线性表

《数据结构电子课件教案第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表1线性结构是数据结构中使用最广泛也是最简单的一种结构线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2基本内容1线性表的概念；2线性表两类存储结构和它们的类型定义；3在这些存储结构下，线性表的基本操作的算法；学习要点：1了解线性表逻辑结构的特征;2重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用C语言描述它们的类型定义；3

2、掌握在顺序存储结构下，线性表的基本操作的算法；4掌握在链式存储结构下，线性表的基本操作的算法；5能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及适用场合；32.1线性表的逻辑结构及类型定义定义：一个线性表是n(n>=0)个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：元素个数n—表长度，n=0空表1

3、”应用例子例2-1：线性表La和Lb表示两个集合A和B，求集合A和B的并集AUB（P20）例2-2：已知线性表LA和LB中的数据元素按值非递减有序排列。将LA和LB归并为一个新的线性LC，且LC中的数据仍然按值非递减有序排列（P20）52.2线性表的顺序存储结构2.2.1顺序表－线性表的顺序存储表示定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：逻辑上相邻—物理地址

4、相邻随机存取实现：可用C++语言的一维数组实现6a1a2…ai…anconstLIST_INIT_SIZE=100;constLISTINCREMENT=10;typedefstruct{ElemType*elem;//存储元素一维数组intlength;//线性表当前长度intlistsize;//当前分配的数组容量}SqList;2.2线性表的顺序存储结构L.LengthL.listsize72.2线性表的顺序存储结构2.2.2顺序表中基本操作中的实现基本操作及时间复杂性初始化操作（相当于C＋＋构造函数）查找元素T(n)=O(n)插入元素T

5、(n)=O(n)删除元素T(n)=O(n)销毁操作（相当于C＋＋析构函数）2.2.2顺序表中的其它算法例：顺序表的合并操作（P26算法2.7）82.3线性表的链式表示和实现特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点9ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表逻辑关系2.3.1单链表和指针(Zhao,Qian,Sun,Li,Zhou,Wu

6、,Zhen,Wang)ZhengZhouZhaoLiQianWuSunWang8652714^12345678^3指针数据元素数据域指针域结点节点如何在计算机中表示这样一个线性链表???10计算机表示typedefstructLNode{ElemTypedata;structLNode*next;}LNnode,*LinkList;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).nextp->next表示p指向结点的指针域生成一个LNode型新结点：p=newLNnod

7、e;系统回收p结点：deletep定义：结点中只含一个指针域的链表叫~，也叫单链表2.3.1单链表和指针112.3.1单链表和指针指针操作基本示例指针指向节点指针指向后继指针移动p=qp=q->nextp=p->nextqpqppp122.3.1单链表和指针链指针改接链指针改接后继p->next=qp->next=q->nextqpqp131intLength_L(LinkListL){//L为链表的头指针，本函数返回L所指链表的长度p=L;k=0;while(p!=NULL){k++;//k计非空结点数p=p->next;}//whilere

8、turnk;}2.3.2单链表的基本操作求链表长度求链表长度查找指定元素插入节点删除节点L1830754256∧PPk21算法评价：T（n）＝O（n）