数据结构专科电子教案二(高职高专)ppt课件.ppt

《数据结构专科电子教案二(高职高专)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表2.1线性表的定义和抽象数据类型aiElemType线性表的逻辑结构示意图2.2.1线性表的定义线性表(LinearList)是具有相同属性的数据元素的一个有限序列。(a1,a2,…,ai,ai+1,…,an)a1a2...aiai+1…an2.1.2线性表的抽象数据类型ADTLinearListisData:L=(a1,a2,…,ai,ai+1,…,an)Operation:voidInitList(&L);//初始化线性表voidClearList(&L);//删除线性表中所有元素

2、，使之成为一个空表intListSize(&L);//得到线性表的长度boolListEmpty(&L);//检查线性表是否为空ElemTypeGetElem(&L,intpos);//得到线性表中指定序号的元素voidTraverseList(&L);//遍历一个线性表boolFind(&L,ElemType&item);//从线性表中查找具有给定值的元素boolUpdate(&L,constElemType&item);//更新线性表中具有给定值的元素voidInsertRear(&L,con

3、stElemType&item);//向线性表的末尾添加一个元素voidInsertFront(&L,constElemType&item);//向线性表的表头插入一个元素voidInsert(&L,constElemType&item);//向线性表中满足条件的位置插入一个元素ElemTypeDeleteFront(&L);//从线性表中删除表头元素boolDelete(&L,constElemType&item);//从线性表中删除等于给定值的元素voidSort(&L);//对线性表进行排序

4、endLinearList2.2线性表的顺序存储和操作实现2.2.2---基本操作算法实现2.2.1---顺序存储结构2.2.1线性表的顺序存储：把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中从指定存储位置开始的一块连续的存储空间中。特点：逻辑关系相邻物理位置相邻a1a2…aiai+1…an…01i-1in-1MaxSize-1线性表的顺序存储结构示意图constintMaxSize=50;structList{ElemTypelist[MaxSize];intsize;//当前线性表

5、长度};线性表的顺序存储类型定义：在C++中，线性表的顺序存储结构是利用数组实现的。一、有关空表的操作1.初始化操作2.清空操作3.判空操作2.2.2顺序存储下的线性表操作的实现1、初始化线性表voidInitList(List&L){L.size=0;}2、删除线性表中的所有元素，使之成为一个空表voidClearList(List&L){L.size=0;}3、得到线性表的长度intListSize(List&L){returnL.size;}4、检查线性表是否为空boolListEmpty(

6、List&L){return(L.size==0);}二、有关查找的操作2、查找具有给定值的元素1、遍历线性表操作3、更新表中具有给定值的元素5、得到线性表中指定序号的元素374689……序号123456…L.size下标012345…L.size-1线性表中第5个元素是8ElemTypeGetElem(List&L,intpos){if(pos<1

7、

8、pos>L.size){cerr<<“posisnotrange!”<

9、遍历一个线性表从表头元素起依次访问每一个元素，并且每个元素只被访问一次a1a2…ai-1ai…an基地址L.list[0]最后一个L.list[L.size-1]374689……5下标012345…L.size-16.遍历一个线性表347689…5voidTraverseList(List&L){for(inti=0;i

10、素查找成功！boolFind(List&L,ElemType&item){for(inti=0;i