数据结构与算法数据结构与算法 (2).ppt
《数据结构与算法数据结构与算法 (2).ppt》由会员分享,可在线阅读,更多相关《数据结构与算法数据结构与算法 (2).ppt(142页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、算法与数据结构算法与数据结构2 2第一部分第一部分线性表性表n具有线性关系的数据集合的处理具有线性关系的数据集合的处理n包括五部分内容包括五部分内容n线性表线性表n栈栈n队列队列n串串n*数组数组2023/3/30 23:082023/3/30 23:083 3第二章第二章线性表性表n2.1线性表的性表的类型型定定义n2.2线性表的性表的顺序表示序表示和和实现n2.3线性表的性表的链式表示式表示和和实现n2.4双双链表表n2.5循循环链表表n2.6线性表性表实现方法的方法的比比较n2.7算法算法设计举例例2023/3/30 23:082023/3/30 23:084 42.1.1线性表的概念性
2、表的概念n线性线性结构结构的的特点特点是数据元素之间的逻辑关系是线性是数据元素之间的逻辑关系是线性关系关系。n线性线性结构是数据元素间约束力最强的一种数据结构:结构是数据元素间约束力最强的一种数据结构:在非空线性结构的有限集合中,存在唯一一个被称在非空线性结构的有限集合中,存在唯一一个被称为为“第一个第一个”的数据元素;存在唯一一个被称为的数据元素;存在唯一一个被称为“最后一个最后一个”的数据元素;除的数据元素;除“第一个第一个”元素无前驱元素无前驱外,集合中的每个元素均有且只有一个外,集合中的每个元素均有且只有一个“直接直接”前前驱;除驱;除“最后一个最后一个”元素无后继外,集合中每个数元素
3、无后继外,集合中每个数据元素均有且只有一个据元素均有且只有一个“直接直接”后继后继。2023/3/30 23:082023/3/30 23:085 5算法与数据结构2.1.1线性表的概念性表的概念6 6算法与数据结构2.1.1线性表的概念性表的概念7 72.1.2线性表的抽象数据性表的抽象数据类型型templatetemplateclass Listclass Listpublic:public:virtual void virtual void clearclear()=0;()=0;/清空线性表清空线性表 virtual bool virtual bool emptyempty()cons
4、t=0;()const=0;/判判空空 virtual int virtual int sizesize()const=0;()const=0;/求线性表的长度求线性表的长度 virtual void virtual void insertinsert(int i,const T&value)=0(int i,const T&value)=0;/在位序为在位序为i0.ni0.n的位置插入元素的位置插入元素valuevalue virtual void virtual void removeremove(int i)=0;(int i)=0;/删除位序为删除位序为i0.n-1i0.n-1的元素的
5、元素 virtual int virtual int searchsearch(const T&value)const=0(const T&value)const=0;/查找值为查找值为valuevalue的元素第一次出现的位序的元素第一次出现的位序 virtual T virtual T visitvisit(int i)const=0;(int i)const=0;/查找位序为查找位序为i i的元素并返回其值的元素并返回其值 virtual void virtual void traversetraverse()const=0;()const=0;/遍历线性表遍历线性表 virtual v
6、oid virtual void inverseinverse()=0;()=0;/逆置线性表逆置线性表 virtual List();virtual List();2023/3/30 23:082023/3/30 23:088 8第二章第二章线性表性表n2.1线性表的性表的类型型定定义n2.2线性表的性表的顺序表示和序表示和实现n2.3线性表的性表的链式表示和式表示和实现n2.4双双链表表n2.5循循环链表表n2.6线性表性表实现方法的方法的比比较n2.7算法算法设计举例例2023/3/30 23:082023/3/30 23:089 9 9 9n分分类:n1、顺序表序表(用一用一维数数组实
7、现定定长的的线性存性存储结构构)n按索引按索引值从小到大存放在一片相从小到大存放在一片相邻的的连续区域区域n紧凑凑结构,存构,存储密度密度为1n2、链表表(用用指指针实现变长的的线性存性存储结构构)n单链表表n双双链表表n循循环链表表 线性表的存储结构 10102.2.1线性表的性表的顺序存序存储n在程序设计语言中,一块连续的存储空间可以用一在程序设计语言中,一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的,个数组实现。由于线性表中的元素个数是动态的,因此采用了动态数组。因此采用了动态数组。n保存一个动态数组,需要三个变量:指向线性表元保存一个动态数组,需要三个变量:指向线
8、性表元素类型的指针,数组规模(容量),数组中的元素素类型的指针,数组规模(容量),数组中的元素个数(表长)。个数(表长)。2023/3/30 23:082023/3/30 23:0811112.2.1线性表的性表的顺序存序存储1212顺序表的类型顺序表的类型定义定义template template/elemTypeelemType为顺序表存储的元素类型为顺序表存储的元素类型class seqList:public List class seqList:public List private:private:elemType*elemType*datadata;/利用动态数组存储数据元素利用动
9、态数组存储数据元素 int int curLengthcurLength;/当前顺序表中存储的元素个数当前顺序表中存储的元素个数 int int maxSizemaxSize;/顺序表的最大长度顺序表的最大长度 void resize();void resize();/表满时扩大表表满时扩大表空间空间public:public:seqList(int initSize=10);seqList(int initSize=10);/构造函数构造函数 seqList(seqList&sl);seqList(seqList&sl);/拷贝构造函数拷贝构造函数 seqList()delete data;
10、seqList()delete data;/析构函数析构函数 2023/3/30 23:082023/3/30 23:081313 void void clearclear()curLength=0;()curLength=0;/清空表,只需置清空表,只需置curLengthcurLength为为0 0 bool bool emptyempty()constreturn curLength=0;/()constreturn curLength=0;/判空判空 int int sizesize()const return curLength;()const return curLength;/返
11、回顺序表中当前存储元素的个数返回顺序表中当前存储元素的个数 void void traversetraverse()const;()const;/遍历顺序表遍历顺序表 void void inverseinverse();();/逆置顺序表逆置顺序表 void void insertinsert(int i,const elemType&value(int i,const elemType&value););/在位序在位序i i上插入值为上插入值为valuevalue的的元素元素 void void removeremove(int i);(int i);/删除位序删除位序i i上的上的元素元
12、素 int int searchsearch(const elemType&value)const(const elemType&value)const;/;/查找值为查找值为valuevalue的元素第一次出现的位序的元素第一次出现的位序 elemType elemType visitvisit(int i)const;(int i)const;/访问位序为访问位序为i i的元素的值,的元素的值,“位序位序0”0”表示第一个元素表示第一个元素;算法与数据结构1414说明:说明:在在插入插入insert(int i,const elemType&value)insert(int i,const
13、 elemType&value)、remove(int i)remove(int i)、查找、查找search(const elemType&value)search(const elemType&value)等运等运算中涉及到的参数算中涉及到的参数i i指的是元素在线性表中的位序(即下标)指的是元素在线性表中的位序(即下标)。假定线性表有。假定线性表有n n个元素,那么数组下标从个元素,那么数组下标从0 0到到n-1n-1。在在顺序表中顺序表中“求线性表长度求线性表长度”、“判空判空”、“清空清空”“”“取位取位序为序为i(0icurLen-1)i(0icurLen-1)的元素的元素”等操作
14、是非常简单的,算等操作是非常简单的,算法的时间复杂度都是法的时间复杂度都是O(1)O(1)。算法与数据结构15152.2.2顺序表上基本运算的序表上基本运算的实现n1构造函数构造函数n代代码2.1构建构建一个空一个空顺序序表表template seqList:seqList(int initSize=100)if(initSize=0)throw badSize();maxSize=initSize;data=new elemTypemaxSize;curLength=0;算法与数据结构时间复复杂度度为O(1)1616n2拷拷贝构造函数构造函数n代代码2.2在构造函数里在构造函数里动态分配了内
15、存分配了内存资源,源,这时需要用需要用户自定自定义拷拷贝构造函数构造函数进行深拷行深拷贝。template seqList:seqList(seqList&sl)maxSize=sl.maxSize;curLength=sl.curLength;data=new elemTypemaxSize;for(int i=0;i curLength;+i)datai=sl.datai;算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)1717n3遍遍历顺序序表表n代代码2.3templatevoid seqList:traverse()const if(empty(
16、)coutis emptyendl;/空表 else coutoutput element:n;for(int i=0;i curLength;i+)/依次访问顺序表中所有元素 coutdatai ;coutendl;算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)1818n4查找找值为value的的元素元素n算法思想:遍历线性表,将线性表中每一个元素依次与value进行比较。若value=datai(0=icurLength)则查找成功,返回datai的位序i,否则查找失败返回-1n代代码2.4templateint seqList:search(con
17、st elemType&value)const for(int i=0;i curLength;i+)if(value=datai)return i;return-1;/查找失败返回-1算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)1919n5求前求前驱和后和后继n算法思想:求顺序表中位序为i的元素的前驱和后继,若 i=0,则为第一个元素无前驱,否则其前驱是 datai-1;若 i=curLength-1,则为最后一个元素无后继,否则其后继是 datai+1。通过元素的下标可以直接定位其前驱和后继,算法的时间复杂度为O(1)。算法与数据结构2.2.2顺序
18、表上基本运算的序表上基本运算的实现2020算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现21212121顺序表的插入图示curcur a a0 0 a a1 1 a a2 2 a a0 0 a a1 1 a a2 2 curcura a4 4a a3 3a a5 5X Xa a5 5X Xa a4 4a a3 32023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构2222n代代码2.5插入运算插入运算templatevoidseqList:insert(inti,constelemType&value)if(icurLength)throwout
19、OfRange();/合法的插入位置合法的插入位置为0.curLengthif(curLength=maxSize)resize();/表表满,扩大大/下下标j-1在在curLength-1.i范范围的元素往后移的元素往后移动一一步步for(intj=curLength;ji;j-)dataj=dataj-1;datai=value;/将将value置入位序置入位序为i的位置的位置+curLength;/表的表的实际长度增度增1算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)2323n本算法中要注意以下本算法中要注意以下问题:(1)检验插入位置的有效性,这
20、里 i 的有效范围是:0icurLength,注意:在表尾元素 datacurLength-1 的后面插入元素成为新的表尾是合法的。(2)检查表空间是否满了,在表满的情况下不能再做插入,否则产生溢出错误。此时有两种解决方法:一种是不执行插入,报错后退出;另一种是扩大数组的容量。本书采用第二种方法。(3)注意数据的移动方向,最先移动的是表尾元素。算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现2424插入算法的时间复杂插入算法的时间复杂度分析度分析算法与数据结构2525算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现26262626顺序表的删除图示curcur a a
21、0 0 a a1 1 a a2 2 a a0 0 a a1 1 a a2 2 curcura a4 4a a3 3a a5 5a a6 6a a4 4a a3 3a a5 5a a6 62023/3/30 23:082023/3/30 23:08吉林大学珠海学院数据结构27272727算法与数据结构代代码2.6删除除运算运算template void seqList:remove(int i)/合法的删除位置为0.curLength-1 if(i curLength-1)throw outOfRange();/i+1.curLength-1范围的元素往前移动一步 for(int j=i;j c
22、urLength-1;j+)dataj=dataj+1;-curLength;/表的实际长度减12.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)28282828算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现2929删除算法的时间复杂度删除算法的时间复杂度分析分析算法与数据结构3030算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现3131n代代码2.7逆置逆置templatevoid seqList:inverse()elemType tmp;for(int i=0;i curLength/2;i+)/控制交换的次数 tmp=datai;d
23、atai=datacurLength-i-1;datacurLength-i-1=tmp;算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)3232n9扩大表空大表空间n由于由于数数组空空间在内存中必在内存中必须是是连续的,因此,的,因此,扩大数大数组空空间的操作的操作须重新申重新申请一个更大一个更大规模的新模的新数数组,将原有数,将原有数组的内容拷的内容拷贝到新数到新数组中,中,释放放原有数原有数组空空间,将新数,将新数组作作为线性表的存性表的存储区。区。算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现3333n代代码2.8扩大表大表空空间t
24、emplate void seqList:resize()elemType*p=data;/p指向原顺序表空间 maxSize*=2;/表空间扩大2倍 data=new elemTypemaxSize;/data指向新的表空间 for(int i=0;i curLength;+i)datai=pi;/复制元素 delete p;算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现时间复复杂度度为O(n)3434n*10合并合并顺序序表表n顺序序表表A与与B的的结点关点关键字字为整数,整数,A表与表与B表的元素均非表的元素均非递减有序,减有序,试给出一种高效的算法,将出一种高效的算法,
25、将B表中元素合并到表中元素合并到A表中,使新的表中,使新的A表的元素仍保持非表的元素仍保持非递减有序,高效指最减有序,高效指最大限度的避免移大限度的避免移动元素。元素。算法与数据结构2.2.2顺序表上基本运算的序表上基本运算的实现3535代码2.9合并合并顺序序表表,本例用类的成员函数实现templatebool seqList:Union(seqList&B)int m,n,k,i,j;m=this-curLength;/当前对象为线性表A n=B.curLength;/m,n分别为线性表A和B的长度 k=m+n-1;/k为结果线性表的工作指针(下标)i=m-1,j=n-1;/i,j分别为线
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法数据结构与算法 2 数据结构 算法
限制150内