计算机软件技术基础3-1 数据结构及算法(概述+线性表).ppt

1,常用数据结构及其运算,第三章,2,§3.1 概述 §3.2 线性表 §3.3 栈与队 §3.4 树与二叉树 §3.5 图 §3.6 查找与排序,目录,3,3.1 概 述,3.1.1 数据结构的概念 3.1.2 数据的逻辑结构和物理结构 3.1.3 算法与算法分析 3.1.4 算法分析技术初步 3.1.5 小结,,4,3.1.1 数据结构的概念,数值型与非数值型数据数值型：整型、实型、布尔型等非数值型：文献检索、金融管理、商业系统 等数据处理,数据结构研究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。如线性关系、层次关系、网状关系等。,,5,数据(data)——是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。,数据元素(data element)——是数据的基本单位。如数据集合N={ 1，2，3，4，5 }中整数1至5均为数据元素。 数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。,,3. 基本概念和术语,3.1.1 数据结构的概念,6,数据类型——程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等 结构类型：变量值可分，如数组、结构体等,,数据对象(data object)——性质相同的数据元素的集合。如大写字母字符的数据对象是集合：C={ ‘A’，’B’，.，’Z’ }。,3.1.1 数据结构的概念,7,数据结构(data structure)——是指同一数据对象中各数据元素间存在的关系。,,数据结构与算法—— 程序＝算法＋数据结构算法指解决特定问题的有限运算序列,3.1.1 数据结构的概念,8,1.逻辑结构：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。二元组 S =（D，R）D－－数据元素的非空有限集合R－－D上关系的非空有限集合。,,3.1.2 数据的逻辑结构和物理结构,9,四类基本结构：,,举 例,3.1.2 数据的逻辑结构和物理结构,10,例1：linearity = (D, R)，其中D ＝ {1,2,3,4,5,6,7,8,9,10}R = {r}r = {, , , , , , , , },例2：Tree= (D, R)，其中D ＝ {1,2,3,4,5,6,7,8,9,10}R = {r}r = {, , , , , , , , },,3.1.2 数据的逻辑结构和物理结构,11,例4：S = (D, R)，其中D ＝ {1,2,3,4,5,6}R = {r1, r2}r 1= {, , , , }r2={,,,,},例3：Graph= (D, R)，其中D ＝ {1,2,3,4,5}; R = {r}r = {, , , , },,3.1.2 数据的逻辑结构和物理结构,12,2.物理结构(存储结构)：是逻辑结构在计算 机中的映象，即具体实现。四种基本存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构3.逻辑结构与存储结构的关系－算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。－同一种逻辑结构可采用不同的存储结构。,,3.1.2 数据的逻辑结构和物理结构,13,一、什么是算法, 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。  算法的五个特征：有穷性、确定性、可行性、 输入、输出  算法描述：采用类C语言的形式，有时也用自然语言。注释部分用//或/*.*/表示。,,3.1.3 算法与算法分析,14,二、算法设计的要求：正确性、健壮性、效率与低存储 三、算法评价标准：时间复杂度、空间复杂度一般时间复杂度考虑的较多。  一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。  度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算 着重介绍第二种方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）,,3.1.3 算法与算法分析,15,一、时间复杂度 1. 频度：指一条语句重复执行的次数。记作： F(n) 2. 算法的时间度量：T(n)=O(F(n))是问题规模 n 的某个函数F(n),称为算法的渐进时间复杂度或时间复杂度。 例：T(n)=3n2 + 2n, 则 T(n)=O(n2)T(n)=3n + 2n, 则 T(n)=O(3n),,3.1.4 算法与分析技术初步,16,“++x”的语句频度及三段程序的时间复杂度：(a) (b) (c)F(n): 1 n n2T(n): O(1) O(n) O(n2),例: (a) {++x;s=0}(b) for (i=1;i=n;++i) {++x;s+=x;}(c) for (j=1;j=n;++j)for (k=1;k=n;++k) {++x;s+=x;},,3.1.4 算法与分析技术初步,17,问题 ？有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。,,3.1.4 算法与分析技术初步,18, 常见的时间复杂度1）O(1)：常量型2）O(n)、O(n2)、.、O(nk)：多项式型3）O(log2n)、O(2log2n)：对数型4）O(2n)、O(en)：指数型 按增长率排序，一般有：1) 3) 2) 4),,3.1.4 算法与分析技术初步,19, 当难以精确计算基本操作执行次数（或语句频度）情况下，只需求出关于 n 的增长率或阶即可。 当难以确定各种输入数据集出现的概率时，平均时间复杂度也难以确定时，可用最坏的情况作为分析依据,,3.1.4 算法与分析技术初步,20,例：求下列程序段的时间复杂度1. for (i=0; in; i++) 2. for (j=0; jn; j++){ 3. b[i][j]=0; 4. for (k=0; kn; k++) 5. b[i][j]=b[i][j]+a[i][k]*a[k][j]; 6. },以执行次数最多的语句（第5句）进行计算：语句频度为：F(n)=n3时间复杂度：T(n)=O(F(n))=O(n3),,3.1.4 算法与分析技术初步,21,3. 程序运行时间计算方法(1) 两条法则 加法法则若 T1(n)=O(F(n))， T2(n)=O(G(n))则： T1(n)+ T2(n) = max(O(F(n)),O(G(n))) 乘法法则：若 T1(n)=O(F(n))， T2(n)=O(G(n))则： T1(n) • T2(n) = O( F(n) • (G(n) ),,3.1.4 算法与分析技术初步,22,例：三个程序段执行时间分别为O(n)、O(n3)、O(nlogn)则 T(n)= max(O(n),O(n3),O(nlogn))= O(n3),加法法则特例：某两步的运行时间分别为 O(F(n))、O(G(n))其中 F(n)= n4, n为偶数； G(n)= n2, n为偶数= n2, n为奇数； G(n)= n3, n为奇数,则总运行时间：T(n)= O(n4), 当n为偶数时；= O(n3), 当n为奇数时；,,3.1.4 算法与分析技术初步,23,,(2) 常用的六条分析规则：1)每个赋值语句或读/写语句的运行时间通常是O(1)。例外情况：赋值语句的右部表达式出现函数调用， 此时要考虑计算函数值所耗费的时间2)一个序列语句的运行时间由加法法则确定，即为该 序列中耗时最多的语句的运行时间。,,,3.1.4 算法与分析技术初步,24,3) if(…),S语句：执行时间为条件测试时间(O(1))＋ 分支语句S的执行时间。if(…),S1 条件测试(O(1))+ S1和S2中运行时else S2 间较大者。,,,,4) 循环语句的运行时间：是n次重复执行循环体所耗 时间的总和。（应用乘法法则）即：执行一次循环体时间的最大值×循环次数每次执行循环体的时间 = 循环体本身运行时间＋计 算循环参数及测试时间（通常为O(1)）。多层循环：由内层－外层逐层分析,,3.1.4 算法与分析技术初步,25,,5) 过程调用语句：a.非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。b.递归调用：可先对递归过程设一特定的运行时间 函数T(n)，根据过程递归调用的情况，得到T(n) 的一个递推关系。6) go to 语句：可以最坏情况进行计算，即在遇到向 下转移的go to 语句时，可认为go to 语句所引起 的控制转移根本没有发生；当遇到向上转移的go to 语句时，则必须考虑它对程序运行时间的影响。,,,3.1.4 算法与分析技术初步,26,4. 时间复杂度计算举例,例1： (1) for ( i=1; i=i+1; --j ) {(3) if ( A[j-1]A[j] ) { (4) temp = A[j-1];(5) A[j-1]=A[j];(6) A[j]=temp;}}},分析： (4)~(6): O(1) (3)~(6): O(1) (2)~(6): O(1×(n-i))= O(n-i) (1)~(6): T(n)=O(n2),,,3.1.4 算法与分析技术初步,27,例2：for ( i=2 ; i= i ; --j){ S ;},求“S”语句的频度及整个程序段的算法复杂度,分析：i=2：执行 n-1 次i=3：执行 n-2 次…i=n-2；执行 3 次 则：F(n) = 3+4+5+…+n-1 = (n-3)(n+2)/2T(n) = O(n2),,3.1.4 算法与分析技术初步,28,例3： i=1;While ( i=n)@ i=i*3 ;,求@语句的频度及整个程序段的算法复杂度,分析：设@句的频度为F(n) 则：,,T(n) = O(log3n),,3.1.4 算法与分析技术初步,29,例4： prime( int n ) // n为一正整数{ int i=2 ;while (( n%i)!=0 },求算法的复杂度,,分析：设嵌套最深层语句“ i++”的频度为F(n), 有：F(n)×1.0sqrt(n) 则,,3.1.4 算法与分析技术初步,30,例5： x = n ; y = 0 ;while ( x = (y+1)(y+1)) do@ y = y+1 ;,求@语句的频度和整个程序段的算法复杂度,,分析： F(n)×F(n) = n,,,3.1.4 算法与分析技术初步,31,例6： w = 11 ; k= 21 ;while ( k 10 ) do@ if w 20 then {w=w-10 ; k--}else w=w+10;,求@语句的频度,,分析：对每一合法k值，@句执行2次则，@句频度F(n)= (21-10)×2＝22,,,3.1.4 算法与分析技术初步,32,例7： x = 87 ; y = 10 ;while ( y 0 ) {@ if ( x 100 ){ x - = 10 ; y - - ; }else x + + ;},求@语句的频度和整个算法的复杂度。,,分析：@句频度F(n)= 15＋11×9＝114T(n)=O(1),,,3.1.4 算法与分析技术初步,33,例8： int fact ( int n) // 计算n!{(1) if ( n=1)(2) fact=1;else(3) fact=n*fact(n-1) ; },计算程序段的时间复杂度,,,,,3.1.4 算法与分析技术初步,34,例9： float p (n)int n;{(1) if (n=1) return(n) ;(2) else return(p(n-1)+p(n-2)); },计算程序段的时间复杂度,,,,,,3.1.4 算法与分析技术初步,35,二、空间复杂度 空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：S(n) 时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，因此在分析中着重考虑时间的因素。,,3.1.4 算法与分析技术初步,36, 理解数据、数据元素、数据对象、逻辑结构和物理结构、数据类型、数据结构、算法等基本概念。 掌握频度、时间复杂度的计算。 了解空间复杂度。,,3.1.5 小结,37,3.2 线 性 表,,3.2.1 线性表的定义和运算 3.2.2 顺序存储线性表 3.2.3 线性链表 3.2.4 向量和链表的比较 3.2.5 小结 3.2.6 作业,38,3.2.1 线性表的定义和运算,线性表的概念线性表的逻辑结构是n个数据元素的有限序列:L=(a1, a2 ,.，an) L为线性表，ai(i=1,.，n)是属于某数据对 象的元素，n为线性表的长度(n≥0)，n=0的表称为空表。 2. 线性表的定义L=（D，R）,,39,3. 线性表的结构特点 表中的数据元素为同一数据类型 数据元素之间是线性关系 每个元素有且只有一个前趋元素(第一个元素除外)，每个元素有且只有一个后继元素(最后一个元素除外),3.2.1 线性表的定义和运算,,40,有序表与无序表的概念若线性表中的数据元素相互之间可以比较，且ai≥ai+1 ，i=2，3，.，n（或ai≤ai+1 ，i=1，2，.，n-1），则称该线性表为有序表，否则称为无序表。 线性表的基本运算插入、删除、查找、排序等。(按位置、按值),3.2.1 线性表的定义和运算,,41,3.2.2 顺序存储线性表（顺序表）,一、顺序存储结构 用一组地址连续的存储单元存放线性表的数据元素（也称为向量式存储结构） 该结构用高级语言中的一维数组类型表示。 例如：可用一维数组A[n]来存储线性表： （a1, a2 ,.，an）。 地址计算： addr(ai)=addr(a1)+(i-1)*L 特点：随机存储结构(查找方便)。,,42,例：,addr(a4) = addr(a1) + (i-1)×L = 2000H+(4-1)×1=2003H,3.2.2 顺序存储线性表,,43,二、顺序存储结构的插入与删除 1.插入 1)概念：有线性表(a1,a2 ,.，an)，长度为n，要在第i-1与第i个元素之间插入一个新元素。使得线性表变为：(a1,a2 ,. ai-1,x, ai,.,an), 长度为n+1。2)插入过程：将ai至an依次后移一个位置(共移动n-i+1个元素)，然后将新元素插入在第i个位置上(合法位置：1=i=n+1)。请参见教材27页图2-3所示。,3.2.2 顺序存储线性表,,44,3)算法描述int InsertList(L[m],n,i,x) //形式参数 { if (in+1) return(0); //位置非法 for (j=n;j=i;j--) L[j+1]=L[j]; //移动元素 L[i]=x; //插入元素 n++; //长度加1 return(1); //执行成功，返回 },3.2.2 顺序存储线性表,,45,2. 删除1）概念：删除第i个位置上的元素，使线性表的长度由n变为n-1。2）删除过程：ai+1～an依次前移一个位置(共移动n-i个元素) 。(合法位置：1=i=n)参见教材27页图2-4所示。,3.2.2 顺序存储线性表,,46,3）算法描述int DeleteList(L[m],n,i) { if (in) return(0); //参数不合法 for (j=i;j=n-1;j++) L[j]=L[j+1]; //前移 n--; //表长减1 return(1); },3.2.2 顺序存储线性表,,47,运算的时间分析 在插入和删除运算中，时间主要消耗在移动元素上。 设pi－在第i个元素前插入一个元素的概率，则在长度为n的线性表中插入一个元素所需的平均移动次数为：,3.2.2 顺序存储线性表,,48,在等概率情况下，pi=1/(n+1)，则有：, 同理，删除时有：,在等概率情况下，qi=1/n，则有：,问题：顺序表插入、删除的时间复杂度？,O(n),3.2.2 顺序存储线性表,,49,4.顺序表特点： 优点：存储效率高、查找方便。 缺点：1)插入删除代价高(插入或删除一个元素，平均需要移动表中一半的元素),仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。2)要求连续存储区，管理不灵活，元素删除后不能释放空间。,3.2.2 顺序存储线性表,,50,三、顺序存储结构的应用举例2.顺序表合并,将两个有序顺序表A（有m个元素）和B（有n个元素），合并为一个有序线性表C。,3.2.2 顺序存储线性表,,51,解：LINK (A, m, B, n, C){ i=0; j=0; t=0; k=0;while (i B[j]) C[k++]=B[j++];else { C[k++]=B[j++]; //相等者只保存一个i++; }}if ( i= =m) //B未完，将B余下的元素赋给Cfor (t=j; tn; t++)C[k++]=B[t];if ( j= =n) //A未完，将A余下的元素赋给Cfor (t=i; tm; t++)C[k++]=A[t];return k;},3.2.2 顺序存储线性表,,52,3.2.3 线性链表,一、问题的提出  顺序存储结构的缺点 1）插入和删除时需移动大量的元素； 2）要求存放元素的存储单元连续； 3）有时会造成空间浪费或溢出； 4）表的容量不易扩充（个数固定）。,,53,二、线性链表的逻辑结构 1. 逻辑结构, 每个结点有两个字段：data－数据域，存放结点值next－指针域，存放后继结点的地址, 头指针：head （指向链表的第一个结点）  链表可以为空： head NULL 字段值的获取：data(a1) ; next(a1) ;（C语言：a1-data;a1-next;）,3.2.3 线性链表,,54,二、线性链表的逻辑结构2. 线性链表的特点, 存储单元不要求连续，插入和删除方便；  要求较多的存储空间（存放指针域）。,3.2.3 线性链表,,55,三、单链表 1. 基本概念：每个结点只有一个指针域的链表。, 结点定义：typedef struct node {char data;struct node *next;} NODE;,3.2.3 线性链表,,56,三、单链表 2. 线性链表的基本运算 （1）基本操作,3.2.3 线性链表,,1）指针赋值：s=p;q=p-next; 2）指针移动：p=p-next;) 3）后插： s-next=p-next；p-next=s； 4）前插： q=head； while(q-next!=p) q=q-next; q-next=s；s-next=p；,57,1）指针赋值：s=p;q=p-next; 2）指针移动：p=p-next;) 3）后插： s-next=p-next；p-next=s； 4）前插： q=head； while(q-next!=p) q=q-next; q-next=s；s-next=p；,58,（2）结点的动态生成及回收 动态生成：GETNODE（P）;data（P）data=b;）C语言中的实现：(包含头文件“alloc.h”)int Get(NODE *P){P=(NODE *)malloc(sizeof(NODE));if (!P) return(0);else return(1);} 回收：RET（P）;C语言中的实现：free（P）;,3.2.3 线性链表,,59,NODE *CreateList(int n) //建立有n个结点的单链表 { NODE *h=NULL,*pre=NULL,*s; //定义变量 for (i=0;idata); s-next=NULL; //生成结点并赋值 if (h==NULL) h=s; else pre-next=s; pre=s; //结点指针链接 } return(h); //返回链表头指针 },三、单链表 3.线性链表的建立（补充）,3.2.3 线性链表,,60,1）问题描述：在值为a的结点前插入一个值为x的结点。若链表为空，则x成为其头结点；若表中无a元素，则将x插入表尾。,三、单链表 4.插入运算,3.2.3 线性链表,,61,2）算法描述InsertList(head,a,x) { GETNODE(p); p-data = x; //取得一个新结点p if (head==NULL) then { //空表 head=p; p-next = NULL; return; } if (head-data==a)then{ //a为头结点 p-next = head; head = p; return; } q=head; while (q-next!=NULL //完成插入 },3.2.3 线性链表,,62,1）问题描述：将值为a的结点删除。,三、单链表 5.删除运算,3.2.3 线性链表,,63,2）算法描述DeleteList(head,a) { if (head==NULL) return; //空表 if (head-data==a)then{ //a为头结点 p=head; head=head-next; free(p); return; } LOOKFOR(head,a,q); if (q-next= =NULL) then {return;} p=q-next; q-next=p-next; free(p); //完成删除 return;},3.2.3 线性链表,,64,,三、单链表 5.算法运算时间分析在单链表中插入或删除一个结点时，仅需改变 一个或两个指针，而无需移动元素。,3.2.3 线性链表,,65,1）在链表的第一个结点之前附加一个头结点,四、线性链表的其他形式 1.带头结点的线性链表,头结点：数据域－不 用，或用于存放其它信息，如表长。指针域－指向链表的第一个结点。,3.2.3 线性链表,,66,2）头结点的用处：可简化算法的形式，例如在插入运算中，当表空时尚有头结点存在，因此头指针非空，当a为表中第一个元素时，因有头结点存在，则在a结点之前插入一元素时不必修改头指针。,3.2.3 线性链表,,67,表中最后一个结点指向表的第一个结点，整个链表形成一个环。（只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始）,四、线性链表的其他形式 2.循环链表,3.2.3 线性链表,,68, 优点：提高查找效率 思考：如何判断循环链表的表尾？（单链表：判断指针域为空）,四、线性链表的其他形式 2.循环链表,3.2.3 线性链表,,69, 逻辑结构:,四、线性链表的其他形式 3.双向链表,3.2.3 线性链表,,70,四、线性链表的其他形式 3.双向链表, 特点：一个结点有两个指针域，容易找到前驱。  双向链表的插入：在P结点之后插入值为y的结点,GETNODE(q); q-data=y; q-next=p-next; p-next=q; q-next-prior = q; q-prior = p;,3.2.3 线性链表,,71,四、线性链表的其他形式 3.双向链表, 双向链表的删除：删除结点P。,p-prior-next=p-next; p-next-prior =p-prior; free(p);,3.2.3 线性链表,,72,五、链表应用举例 1.一元多项式相加, 结点结构：每一个非零项构成链表中的一个结点， 结点由两个数据域和一个指针域构成：,3.2.3 线性链表,,73,A(x)=3x14+2x8+1 B(x)=8x14-3x10+10x6C(x)=A(x)+B(x) 设 pa, pb 指针 （1）若指数相等，则系数相加，c(x)中建项（系数为0，不建） （2）若pa-exppb-exp 复抄pa所指项，反之，复抄pb所指项。,74,struct node1 *addpoly(struct node1 *ah, struct node1 *bh) { struct node1 *pa,*pb,*pc,*ch,*pp;int x,e;ch=(struct node1 *)malloc(LEN);ch-exp=-1; ch-next=ch; pc=ch; /*建立新表头结点*/pa=ah-next; pb=bh-next; while((pa-exp!=-1)||(pb-exp!=-1)){ if( pa-exp==pb-exp){ x=pa-cof+pb-cof; e=pa-exp; /*系数相加*/pa=pa-next; pb=pb-next； /*修改指针*/},3.2.3 线性链表,,75,else if (pa-exppb-exp) { x=pa-cof; e=pa-exp; /*复抄A(x)*/pa=pa-next; }else { x=pb-cof; e=pb-exp; /*复抄B(x)*/pb=pb-next; }if (x!=0) /*形成新结点链入C(x)*/{ pp=(struct node1 *)malloc(LEN);pp-cof=x; pp-exp=e;pp-next=ch; pc-next=pp; pc=pp;} }return(ch); },3.2.3 线性链表,,76,五、链表应用举例 2.在带表头结点的单链表结构上查找值为x的结点,LOOKFOR(head, x, p) { p=head-next;for( ; p!=NULL },3.2.3 线性链表,,77,五、链表应用举例 3.将两个有序单链表合并为一带表头的有序单链表,Merge (P1, P2) { GETNODE(ch);p=ch;p-next=NULL;while((P1!=NULL)},If(P1!=NULL) p-next=P1;If(P2!=NULL) p-next=P2;P1=NULL;P2=P1;return(ch); },,3.2.3 线性链表,,78,3.2.4 向量和链表的比较, 线性表的长度是否固定向量的存储空间是静态分配的，适用于表长固定的场合；链表的存储空间是动态分配的，适用于表长不固定的场合。  线性表的主要操作是什么向量是连续存放的，适用于频繁查找操作的表。链表适用于经常进行插入和删除的表。  采用的算法语言：链表要求指针类型变量。,,79, 理解线性表的概念 熟悉线性表的顺序和链式两种存储结构 掌握顺序表的插入和删除算法 掌握链表的建立、遍历、插入和删除算法 掌握双向链表 的插入和删除操作 掌握应用实例，加深理解链表的各种操作 了解向量和链表各自的优缺点,2.2.5 小结,,80,2.2.6 作业, 在双向链表的值为a、b的两个结点之间插 入值为x的结点。,,