《数据结构软件.pptx》由会员分享，可在线阅读，更多相关《数据结构软件.pptx（354页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章绪论计算机科技计算机科技 是是 一门研究用计算机进行信息表一门研究用计算机进行信息表示和处理的科学。示和处理的科学。主要涉及两方面的问题：主要涉及两方面的问题：信息的表示信息的表示和和信息的信息的处理处理 信息的表示和组织直接关系到处理信息的程序信息的表示和组织直接关系到处理信息的程序 的效率，随着计算机的应用领域的扩大。信息的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个因此，为了编写出一个“好好”的程序，必须分的程
2、序，必须分析析 处理的对象的特征及个对象之间的存在的处理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题关系。这就是本课程所要研究的问题。第1页/共354页第一章绪论计算机程序计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？第2页/共354页数学数学软件软件硬件硬件DS1.地位第一章绪论第3页/共354页数学数学软件软件硬件硬件DS1.地位第一章绪论数据结构DataStructure第4页/共354页机外表示机外表示机外表示机外表示处理要求处理要求处理要求处理要求逻辑机构逻辑机构逻辑机构逻辑机构基
3、本运算基本运算基本运算基本运算存储机构存储机构存储机构存储机构算法算法算法算法数据模型问题 实现2.主要内容第一章绪论第5页/共354页机外表示机外表示机外表示机外表示处理要求处理要求处理要求处理要求逻辑机构逻辑机构逻辑机构逻辑机构基本运算基本运算基本运算基本运算存储机构存储机构存储机构存储机构算法算法算法算法数据模型问题 实现2.主要内容第一章绪论(1)(1)要对所加工的对象进行逻辑组织要对所加工的对象进行逻辑组织 (2)(2)如何把加工对象存储到计算机中去？如何把加工对象存储到计算机中去？(3)(3)数据运算数据运算 第6页/共354页3.学科定义什么是数据结构数据结构 是一门研究非数值
4、计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的科。第7页/共354页基本概念和术语(1)(1)数据元素数据元素(data element)(data element)数据基本单位，也称节或孩子，可由若干个数据项组成。数据基本单位，也称节或孩子，可由若干个数据项组成。数据项数据项是数据最是数据最小单位小单位(2)(2)数据数据(data)(data)是对客观事物的是对客观事物的 表示，指所有能输入到计算机并被计算机程序处理的符号的总称。表示，指所有能输入到计算机并被计算机程序处理的符号的总称。(3)(3)数据对象数据对象(data object)(data object
5、)性质相同的数据元素的集合性质相同的数据元素的集合(4)(4)数据结构数据结构 数据元素之间的相互关系数据元素之间的相互关系第8页/共354页 1)1)集合集合基本概念和术语数据间的四种典型结构：2）线形3）树形4）图或网络：第9页/共354页基本概念和术语四种典型结构：1)1)集合集合第10页/共354页四种典型结构基本概念和术语 2 2）线形）线形：第11页/共354页四种典型结构：基本概念和术语 3 3）树形）树形：第12页/共354页四种典型结构：基本概念和术语4 4）图或网络：）图或网络：第13页/共354页基本概念和术语（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。（6
6、 6）物理结构）物理结构(存储结构存储结构)：DEDE及关于在计算机中的表示。及关于在计算机中的表示。DE存储称为节点关系存储：a.顺序存储 b.链式存储第14页/共354页基本概念和术语（7 7）DSDS广义定义：广义定义：DE 的逻 辑 结 构 DE 的物 理 结 构DE 的 抽 象 运 算 （8 8）基本操作）基本操作加工型：查找 删除 更新 排序 引用型：查找第15页/共354页1数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A线性结构B非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面基本概念和术语第16页/共354页算法和算
7、法分析一、算法定义算法是对特定问题求解步骤的一种描述，是指令的有限序列。特性：有穷性 确定性 可行性 输入 输出第17页/共354页算法和算法分析二、算法的描述与分析描述：类描述：类C C语言语言要求要求 正确性：正确性：a.a.语法语法 b.nb.n个输入个输入 c.c.一组典型的苛刻的输入一组典型的苛刻的输入 d.d.所有输入所有输入 可读性可读性 健壮性健壮性 效率与存贮量效率与存贮量第18页/共354页算法和算法分析分析标准分析标准 a a、时间复杂度、时间复杂度 ：算法中基本操作重复执行的次数算法中基本操作重复执行的次数(频度频度)。T(o)=O(f(n)T(o)=O(f(n)时间复
8、杂度分为平均时间复杂度和最坏时间复杂度时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶复杂度的值取规模函数最高阶 第19页/共354页分析标准分析标准 a a、时间复杂度、时间复杂度 ：算法中基本操作重复执行的次数。算法中基本操作重复执行的次数。T(o)=O(f(n)T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶复杂度的值取规模函数最高阶 算法和算法分析b、空间复杂度：算法所需存贮空间S(n)=O(f(n)第20页/共354页算法和算法分析例：分析下列语句段的时间复杂度m=0;1fo
9、r(k=0;kn;k+)n+1for(j=0;jk;j+)n(n+1)/2m+=2;O(n2)第21页/共354页习题与练习一1.简要回答下列问题：a.数据与数据元素有何区别？b.逻辑结构与存储结构是什么？它们是什么关系？c.什么是算法？它有什么特点？第22页/共354页习题与练习一2.试写一个算法，统计输入的100个整数中奇数和偶数的个数。3.设计下面问题算法，并分析最坏情况时间复杂性:在数组A1.n中查找值为K的元素，若找到输出其位置i(0in+1),否则输出0。第23页/共354页习题与练习一4.设n为正整数，写出下列程序段的时间复杂度：（1）for(I=1;In;I+)m=m+I;fo
10、r(j=0;jn;j+)count+=m+j;第24页/共354页习题与练习一（2）for(I=0;In;I+)m=m+I;for(j=0;j10;)count+=m+j;j+;第25页/共354页习题与练习一（3）k=1;s=0;while(s=n-1)k=k+s*6;s+;printf(“%d,%d”,s,k);第26页/共354页第第 二二 章章 线线 性性 表表学习内容学习内容学习内容学习内容 v 线性表定义线性表定义v 线性表的抽象数据结构线性表的抽象数据结构v 线性表的顺序存储和操作实现线性表的顺序存储和操作实现v 线性表的链接存储线性表的链接存储v 线性表在链表上的操作实现线性表
11、在链表上的操作实现v 线性表在双向链表操作实现线性表在双向链表操作实现第27页/共354页第二章线性表线性结构特点：在数据元素的非空有限集合中在数据元素的非空有限集合中 1 1）“第一个第一个”唯一唯一 2 2）“最后一个最后一个”唯一唯一 3 3）除第一个外，每一个有且仅有一个直接前驱）除第一个外，每一个有且仅有一个直接前驱 4 4）除最后一个外，每一个均有且仅有一个直接后继）除最后一个外，每一个均有且仅有一个直接后继第28页/共354页 一一、线线性性表表的的定定义义一一、线线性性表表的的定定义义 第二章线性表线性表的逻辑结构示意图线性表的逻辑结构示意图aaia2ai+1an表头元素表尾元
12、素2.1 线性表的类型定义第29页/共354页2.1 线性表的类型定义一、线性表的定义一、线性表的定义一个线性表可以用一个标识符来一个线性表可以用一个标识符来命名：命名：A=(a1 1,a2 2,ai i,ai+1i+1,an n)ai i可以是基本数据类型也可以是struct 类型 第30页/共354页2.1 线性表的类型定义二、线性结构特点在数据元素的非空有限集中在数据元素的非空有限集中 元素个数元素个数n n表长度，表长度，n=0n=0空表空表 存在唯一的一个被称作存在唯一的一个被称作“第一个第一个”的数据元素的数据元素 存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据
13、元素的数据元素 除第一个外，集合中的每个数据元素均只有一个前趋除第一个外，集合中的每个数据元素均只有一个前趋 除最后一个外，集合中的每个数据元素均只有一个后继除最后一个外，集合中的每个数据元素均只有一个后继 元素同构，且不能出现缺项元素同构，且不能出现缺项第31页/共354页数据元素2.1 线性表的类型定义线性表几个具体例子L1=L1=（a a,b b,c c,4 4,7 7,+,-,*,/）L2=L2=（25,35,28,49,51,87,46,32,8825,35,28,49,51,87,46,32,88）L3=L3=（“BASICBASIC”,“PASCALPASCAL”,“JAVAJA
14、VA”,“OKOK”）L4=L4=（a,b,c,d,e,f,g,h,i,j,k,x,y,za,b,c,d,e,f,g,h,i,j,k,x,y,z）第32页/共354页2.1 线性表的类型定义基本运算基本运算基本运算基本运算(1)(1)初始化初始化 initList(sq)initList(sq)。其作用是建立一个空表。其作用是建立一个空表sqsq(即建立线性表的构架，但即建立线性表的构架，但不含任何数据元素不含任何数据元素)。(2)(2)求表长求表长 ListLen(sq)ListLen(sq)。其作用是返回线性表。其作用是返回线性表sqsq的长度。的长度。(3)(3)读表元素读表元素 Get
15、Elem(sqGetElem(sq，i)i)。若。若1iListLen(sq)1iListLen(sq)，则其作用是返回线性表则其作用是返回线性表sqsq的第的第i i个数据元素个数据元素;否则，返回否则，返回NULLNULL。第33页/共354页2.1 线性表的类型定义基本运算基本运算基本运算基本运算(4)(4)定定位位(按按值值查查找找)LocateElem(sqLocateElem(sq，x)x)。若若sqsq中中存存在在一一个个或或多多个个值值与与x x相相等等的的元元素，则其作用是返回这些元素的序号的最小值；否则，返回素，则其作用是返回这些元素的序号的最小值；否则，返回0 0。第34
16、页/共354页基本运算基本运算基本运算基本运算(5)(5)插插入入ListInsert(sqListInsert(sq，x x，i)i)。其其作作用用是是在在线线性性表表sqsq的的第第i i个个位位置置上上增增加加一一个个以以x x为为值值的的新新元元素素，使使sqsq由由(a1(a1，ai-1ai-1，aiai，an)an)变变为为(a1(a1，ai-1ai-1，x x，aiai，an)an)。参数。参数i i的合法取值范围是：的合法取值范围是：1 1in+1 in+1 in+1 in+1 2.1 线性表的类型定义第35页/共354页2.1 线性表的类型定义基本运算基本运算基本运算基本运算
17、(6)(6)删除删除ListDelete(sqListDelete(sq，i)i)。其作用是删除线性表。其作用是删除线性表sqsq的第的第i i个元素个元素ai,ai,使使sqsq由由(a1(a1，ai-1ai-1，aiai，ai+lai+l，an)an)变为变为(a1(a1，ai-1ai-1，ai+1ai+1，an)an)。参数。参数i i的合法取值范围是：的合法取值范围是：1in1in。第36页/共354页2.1 线性表的类型定义基本运算基本运算基本运算基本运算(7)(7)求前趋求前趋 PriorElem(sq,e)PriorElem(sq,e)若线性表中存在元素若线性表中存在元素e e且
18、不是第一个且不是第一个,其作用是返回其作用是返回e e的前趋元素的前趋元素;否则，返回否则，返回NULLNULL。(8)(8)求后继求后继 NextElem(sq,e)NextElem(sq,e)若线性表中存在元素若线性表中存在元素e e且不是最后一个且不是最后一个,其作用是返其作用是返回回e e的后继元素的后继元素;否则，返回否则，返回NULLNULL第37页/共354页2.1 线性表的类型定义基本运算基本运算基本运算基本运算应用基本运算可以实现线性表的其他运算，如求任一给定数据元素的直接后继或应用基本运算可以实现线性表的其他运算，如求任一给定数据元素的直接后继或直接前趋，将两个线性表合并成
19、一个线性表或将一个线性表拆分成两个线性表等直接前趋，将两个线性表合并成一个线性表或将一个线性表拆分成两个线性表等等。另一方面，在实际应用中，可以根据具体需要选择适当的基本运算等。另一方面，在实际应用中，可以根据具体需要选择适当的基本运算 第38页/共354页2.1 线性表的类型定义解本题的算法思路是：依次检查线性表B中的每个元素，看它是否在线性表A中。若在表A中，则将其从A中删除。基本运算基本运算基本运算基本运算 例例2.1 2.1 利用线性表的基本运算，编写在线性表利用线性表的基本运算，编写在线性表A A中删除线性表中删除线性表B B中出现的元素的中出现的元素的算法。算法。第39页/共354
20、页2.1 线性表的类型定义void void delete(sqlist delete(sqlist&A&A，sqlist sqlist B)B)/A/A为为引引用用型参数型参数 int i,k;ElemType x;int i,k;ElemType x;for(i=l;i=ListLen(B);i+)for(i=l;i0)(k0)ListDelete ListDelete(A(A，k);k);/若若在在线性表线性表A A /中找到则将其删除中找到则将其删除 第40页/共354页2.1 线性表的类型定义解先始化线性表C，然后依次检查线性表A中的每个元素，看它是否在线性表B中；若在线性表B中，则
21、将其插入到线性表C中.基本运算基本运算例2.2 利用线性表的基本运算，编写将线性表A和B中公共元素生成线性表C的算法 第41页/共354页2.1 线性表的类型定义void celem(sqlist Avoid celem(sqlist A，sqlist Bsqlist B，sqlist&C)sqlist&C)int i int i，k k，j=1j=1；ElemType xElemType x；InitList(C)InitList(C)；for (i=1for (i=1；i=Getlen(A)i0)Insert(C,x,j);j+;if (k0)Insert(C,x,j);j+;/若在线性表
22、若在线性表B B中中 /找到，将其插入找到，将其插入C C第42页/共354页2.2 线性表的顺序存储和实现一、一、线性表的顺序存储线性表的顺序存储（顺序表顺序表）定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。即用一组地址连续的存储单元存放一个线性表即用一组地址连续的存储单元存放一个线性表特点：特点：实现逻辑上相邻实现逻辑上相邻物理地址相邻物理地址相邻 实现随机存取实现随机存取实现：实现：（一维）数组（一维）数组 第43页/共354页下标位置下标位置下标位置下标位置0 01 1 i-1i-1i i
23、 n-1n-1MaxSizeMaxSize-1 1数组存贮空间数组存贮空间数组存贮空间数组存贮空间a a1 1a a2 2 a ai ia ai+1i+1 a an n2.2 线性表的顺序存储和实现ElemTypeElemType类型的数组类型的数组listMaxSizelistMaxSize存储线性表存储线性表A=A=(a1,a2,(a1,a2,ai,ai+1,ai,ai+1,an),an)元素地址计算方法元素地址计算方法第第i i个元素的存储位置为：个元素的存储位置为：list+(i-1)*sizeof(ElemType)list+(i-1)*sizeof(ElemType)线性表的顺序存
24、储结构示意图线性表的顺序存储结构示意图第44页/共354页2.2 线性表的顺序存储和实现元素地址计算方法元素地址计算方法 ：l l l lLOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)*L)+(i-1)*L l l l lLOC(aLOC(ai+1i+1)=LOC(a)=LOC(ai i)+L)+L其中：其中：uuuuL L一个元素占用的存储单元个数一个元素占用的存储单元个数 uuuuLOC(ai)LOC(ai)线性表第线性表第i i个元素的地址个元素的地址第45页/共354页a1an01n-112n内存V数组下标元素序号M-1a2备 用 空间2.2 线性表的顺序存
25、储和实现第46页/共354页2.2 线性表的顺序存储和实现线性表的顺序存储示例（图书资料）typedef struct card int num;char name20;char author10;char publisher30;float price;DATATYPE;第47页/共354页可以定义为静态数组或变量可以定义为静态数组或变量DATATYPE libraryM;DATATYPE libraryM;或动态申请和释放内存或动态申请和释放内存DATATYPE*pDataDATATYPE*pData；pDat=(DATATYPE*)malloc(sizeof(DATATYPE);pDat
26、=(DATATYPE*)malloc(sizeof(DATATYPE);free(pData)free(pData)；2.2 线性表的顺序存储和实现线性表的顺序存储示例（图书资料）第48页/共354页2.2 线性表的顺序存储和实现插入一个元素插入一个元素定义：线性表的插入是指在第i 个元素之前插入一个新的数据元素x，使长度为n n的线性表的线性表 (a(a1 1,a,a2 2,a,ai-1i-1,a,ai i,a,an n)变成长度为变成长度为n+1n+1的线性表的线性表 (a(a1 1,a,a2 2,a,ai-1i-1,x,a,x,ai i,a,an n)第49页/共354页2.2 线性表的
27、顺序存储和实现插入一个元素算法插入一个元素算法int sxbcr(int i,int x,int v,int*p)int sxbcr(int i,int x,int v,int*p)int j,n;n=*p;int j,n;n=*p;if(in+1)if(in+1)return(0);return(0);else for(j=n;j=i;j-)else for(j=n;j=i;j-)vj=vj-1;vj=vj-1;vj=x;*p=+n;vj=x;*p=+n;return(1);return(1);第50页/共354页2.2 线性表的顺序存储和实现插入一个元素图示插入一个元素图示1 1内存内存a
28、 a1 1a2a2a ai iai+1i+1a an n0 01i-1V V数组下标数组下标n-1in12i元素序号元素序号i+1nn+1第51页/共354页内存内存a1 1a2 2ai iai+1i+1an n0 01 1i-1i-1V V数组下标数组下标n-1n-1i in n1 12 2i i元素序号元素序号i+1i+1n nn+1n+1an-1n-12.2 线性表的顺序存储和实现插入一个元素图示插入一个元素图示2 2x x第52页/共354页2.2 线性表的顺序存储和实现插入算法时间复杂度插入算法时间复杂度插入算法时间复杂度插入算法时间复杂度T(n)T(n)PiPi是在第是在第是在第是
29、在第i i个元素之前插入一个元素的概率，则在长度为个元素之前插入一个元素的概率，则在长度为个元素之前插入一个元素的概率，则在长度为个元素之前插入一个元素的概率，则在长度为n n的线性表的线性表的线性表的线性表中插入一个元素时，所需移动的元素次数的平均次数为中插入一个元素时，所需移动的元素次数的平均次数为中插入一个元素时，所需移动的元素次数的平均次数为中插入一个元素时，所需移动的元素次数的平均次数为：第53页/共354页2.2 线性表的顺序存储和实现向线性表中表头插入一个元素向线性表中表头插入一个元素InsertFront(List&L,const ElemType&item)InsertFro
30、nt(List&L,const ElemType&item)InsertFront(List&L,const ElemType&item)InsertFront(List&L,const ElemType&item)if(L.size=MaxSize)if(L.size=MaxSize)if(L.size=MaxSize)if(L.size=MaxSize)printf(printf(printf(printf(“List overflow!List overflow!List overflow!List overflow!”););););return;return;return;retur
31、n;for(i=L.size for(i=L.size for(i=L.size for(i=L.size 1;i=0;i-)1;i=0;i-)1;i=0;i-)1;i=0;i-)L.listi+1=L.listi;L.listi+1=L.listi;L.listi+1=L.listi;L.listi+1=L.listi;L.list0=item;L.list0=item;L.list0=item;L.list0=item;L.size+;L.size+;L.size+;L.size+;第54页/共354页2.2 线性表的顺序存储和实现向线性表中满足条件的位置插入一个元素向线性表中满足条件的位
32、置插入一个元素void Insert(List&L,const ElemType&item)void Insert(List&L,const ElemType&item)void Insert(List&L,const ElemType&item)void Insert(List&L,const ElemType&item)if(L.size=MaxSize)if(L.size=MaxSize)if(L.size=MaxSize)if(L.size=MaxSize)printf(printf(printf(printf(“List overflow!List overflow!List ove
33、rflow!List overflow!”););););return;return;return;return;for(int i=0;iL.size;i+)for(int i=0;iL.size;i+)for(int i=0;iL.size;i+)for(int i=0;iL.size;i+)if(item L.listi)break;if(item L.listi)break;if(item L.listi)break;if(item=i;j-)1;j=i;j-)1;j=i;j-)1;j=i;j-)L.listj+1=L.listj;L.listj+1=L.listj;L.listj+1
34、=L.listj;L.listj+1=L.listj;L.listi=item;L.listi=item;L.listi=item;L.listi=item;L.size+;L.size+;L.size+;L.size+;第55页/共354页2.2 线性表的顺序存储和实现向线性表中的末尾添加一个元素void InsertRear(List&L,const ElemType&item)void InsertRear(List&L,const ElemType&item)if(L.size=MaxSize)if(L.size=MaxSize)printf(printf(“List overflow
35、!List overflow!”););return;return;L.listL.size=item;L.listL.size=item;L.size+;L.size+;第56页/共354页变成长度为n-1的线性表需将第i+1至第n共（n-i）个元素前移2.2 线性表的顺序存储和实现删 除 一 个 元 素 定义：线性表的删除是指将第定义：线性表的删除是指将第i i（1 1 i i n n）个元素删除，使长度为）个元素删除，使长度为n n的线性表的线性表第57页/共354页2.2 线性表的顺序存储和实现删 除 一 个 元 素算法int sxbsc(int i,int v,int*p)int s
36、xbsc(int i,int v,int*p)int j,n;n=*p;int j,n;n=*p;if(in)if(in)return(0);return(0);for(j=i;jn;j+)for(j=i;jn;j+)vj-1=vj;vj-1=vj;*p=-n;*p=-n;return(1);return(1);第58页/共354页内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+12.2 线性表的顺序存储和实现删 除 一 个 元 素图示1第59页/共354页内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+22.2
37、线性表的顺序存储和实现删 除 一 个 元 素图示2第60页/共354页 故在顺序表中插入或删除一个元平均移动表的一半元素，当故在顺序表中插入或删除一个元平均移动表的一半元素，当n n很大时，效率很大时，效率很低很低2.2 线性表的顺序存储和实现删除算法评价设设 QiQiQiQi是删除第是删除第i i i i个元素的概率，则在长度为个元素的概率，则在长度为n n n n的线性表中删除一个元素所需移动的元素次数的平均次数为的线性表中删除一个元素所需移动的元素次数的平均次数为：第61页/共354页2.2 线性表的顺序存储和实现从线性表中删除等于给定值的元素1 1int Delete(List&L,c
38、onst ElemType item)int Delete(List&L,const ElemType item)int Delete(List&L,const ElemType item)int Delete(List&L,const ElemType item)if(L.size=0)if(L.size=0)if(L.size=0)if(L.size=0)printf(printf(printf(printf(“L is an empty list!L is an empty list!L is an empty list!L is an empty list!”););););retur
39、n 0;return 0;return 0;return 0;for(i=0;i L.size;i+)for(i=0;i L.size;i+)for(i=0;i L.size;i+)for(i=0;i L.size;i+)if(L.listi=itme)breakif(L.listi=itme)breakif(L.listi=itme)breakif(L.listi=itme)break;第62页/共354页2.2 线性表的顺序存储和实现从线性表中删除等于给定值的元素2 2 if(i=L.size)if(i=L.size)if(i=L.size)if(i=L.size)printf(print
40、f(printf(printf(“Deleted element is not exist!Deleted element is not exist!Deleted element is not exist!Deleted element is not exist!”););););return 0;return 0;return 0;return 0;for(int j=i+1;jL.size;j+)for(int j=i+1;jL.size;j+)for(int j=i+1;jL.size;j+)for(int j=i+1;jL.size;j+)L.listj-1=L.list;L.lis
41、tj-1=L.list;L.listj-1=L.list;L.listj-1=L.list;L.size-;L.size-;L.size-;L.size-;return 1return 1return 1return 1;第63页/共354页 例例 已知线性表已知线性表(ao(ao，a1a1，an-1)an-1)按顺序存按顺序存储，且每个元素都是均不相等的储，且每个元素都是均不相等的 整数。设计整数。设计把所有奇数移到所有的偶数前边的算法把所有奇数移到所有的偶数前边的算法(要求要求时间最少，辅助空间最少时间最少，辅助空间最少)。2.2 线性表的顺序存储和实现解从左向右找到偶数A.datai，从
42、右向左找到奇数A.dataj，将两者交换；循环这个过程直到i大于j为止第64页/共354页2.2 线性表的顺序存储和实现void move(sqlist A)void move(sqlist A)int i=0,j=A.len-l,k;ElemType temp;int i=0,j=A.len-l,k;ElemType temp;while(i=j)while(i=j)while(A.datai%2=0)i+;while(A.datai%2=0)i+;while(A.dataj%2=l)j-;while(A.dataj%2=l)j-;if(ij)if(idata表示p指向结点的数据域(*p).
43、next/p-next表示p指向结点的指针域生成一个LNodeLNode型新结点：p=(LNode*)malloc(sizeof(LNode);系统回收p结点：free(p)2.3线性表的链式存储结构第72页/共354页ha1a2an.h空表2.3线性表的链式存储结构头结点头结点：在单链表第一个结点前附设的一个结点。：在单链表第一个结点前附设的一个结点。头结点指针域为空表示线性表为空头结点指针域为空表示线性表为空第73页/共354页2.3线性表的链式存储结构在带头节点的单链表中查找第在带头节点的单链表中查找第 i i 个结点个结点Status ListSearch_L(LinkList L,i
44、nt i,ElemType*e)Status ListSearch_L(LinkList L,int i,ElemType*e)Status ListSearch_L(LinkList L,int i,ElemType*e)Status ListSearch_L(LinkList L,int i,ElemType*e)P=L-next;j=1;P=L-next;j=1;P=L-next;j=1;P=L-next;j=1;While(!p&ji)While(!p&ji)While(!p&ji)While(!p&jnext;j+;p=p-next;j+;p=p-next;j+;p=p-next;j
45、+;if(p)return ERROR;if(p)return ERROR;if(p)return ERROR;if(p)return ERROR;*e=p;*e=p;*e=p;*e=p;return OKreturn OKreturn OKreturn OK；第74页/共354页2.3线性表的链式存储结构在带头节点的单链表中第在带头节点的单链表中第 i i i i 个结点处插入新元素个结点处插入新元素 x x x x第75页/共354页2.3线性表的链式存储结构Status ListInsert_L(LinkList L,Status ListInsert_L(LinkList L,Stat
46、us ListInsert_L(LinkList L,Status ListInsert_L(LinkList L,ElemType x,const int i)ElemType x,const int i)ElemType x,const int i)ElemType x,const int i)p=L;j=0;p=L;j=0;p=L;j=0;p=L;j=0;while while while while(p&j(p&j(p&j(p&jnext;j+;i-1)p=p-next;j+;i-1)p=p-next;j+;i-1)p=p-next;j+;/找第i-1i-1个结点 if(p=NULL)
47、|(j i-1)if(p=NULL)|(j i-1)if(p=NULL)|(j i-1)if(p=NULL)|(j i-1)printf(printf(printf(printf(“无无无无效效效效的的的的插插插插入入入入位位位位置置置置!n!n!n!n”);return);return);return);return ERROR;ERROR;ERROR;ERROR;/创建新结点,数据为x,x,指针为NULLNULLs=(LinkList s=(LinkList s=(LinkList s=(LinkList*)malloc(sizeof(LinkList);)malloc(sizeof(Li
48、nkList);)malloc(sizeof(LinkList);)malloc(sizeof(LinkList);s s s s-data-data-data-data=x;s-next x;s-next x;s-next x;s-next=p-next;p-next;p-next;p-next;p-next p-next p-next p-next=s;=s;=s;=s;return OK;return OK;return OK;return OK;第76页/共354页2.3线性表的链式存储结构删除元素删除元素 ：第77页/共354页2.3线性表的链式存储结构Status ListDele
49、te_L(LinkList L,int I,ElemType*e)P=L;j=0;While(p-next&jnext;+j;if(!(p-next)|j i-1)return ERROR;/删除位置不合理 q=p-next;p-next=q-next;/删除并释放结点*e=q-data;free(q);return OK;/ListDelete_L删除元素删除元素 ：第78页/共354页 2.3线性表的链式存储结构两个有序单链表合并为一个有序单链表(非递减)MergeList_L(Linklist La,LinkList Lb,LinkList Lc)pa=La-next;pb=Lb-nex
50、t;Lc=pc=La;While(pa&pb)If(pa-data data)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);第79页/共354页v它是一种动态结构，整个存储空间为多个链表共用v不需预先分配空间v指针占用额外存储空间v不能随机存取，查找速度慢2.3线性表的链式存储结构单链表具有单向性的缺点单链表特点单链表特点第80页/共354页2.3线性表的链式存储结构h空表h循环链表循环链表:表中最后一个结点的指针指向头表表中最后一个结点的指针指向头表p p或或p-ne