《各种排序的原函数》由会员分享，可在线阅读，更多相关《各种排序的原函数（118页珍藏版）》请在金锄头文库上搜索。
1、第2章 数据结构（Data Structure）,为什么研究数据结构对数据进行合理组织，使算法设计更容易、高效和可靠。数据结构的定义相互之间具有一种或多种特定关系的数据元素的集合。（关系可用操作描述，操作的描述称算法）数据结构的研究内容 数据逻辑结构：数据元素之间的相互关系，面向问题； 数据存储结构：逻辑结构在计算机中的实现，面向计算机； 运算：在逻辑结构上定义一组相应的运算，在存储结构上建立算法实现这些运算。,2.1 数据结构概述,2.1 数据结构概述,逻辑结构（4种）集合结构、线性结构(1对1)、树型结构(1对多)、图/网结构(多对多) 存储结构（4种）顺序(连续存储单元)、链接(用指针链
2、接元素)、索引(包含索引表和子表)、散列存储(由散列函数得存储地址) 运算运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等。,2.1 数据结构概述,算法 定义 精确地描述解决问题所用方法的一系列确切有穷的步骤 评价算法优劣的标准 时间复杂度：算法运行时间随问题规模(如矩阵阶数、字符串长度、数据元素个数等)n增长的数量f(n)，一般用算法在最坏情况下语句重复执行的最大次数估算。虽不能精确确定算法执行时间，但可以评估算法的时间增长趋势。 空间复杂度：指算法中所需的辅助空间单元。,算法的时间量级,2.2 线性
3、表和数组,一、线性表的定义 线性表的逻辑结构是n个数据元素的有限序列:(a1, a2 ,a3,an) n为线性表的长度(n0)，n=0的表称为空表 数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素； 除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。 所有数据元素ai在同一个线性表中必须是相同的数据类型,2.2 线性表和数组,线性表的基本运算主要有： 求表长度 检索 插入 删除 修改 归并 线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链
4、表数组是一种典型的顺序表,2.2 线性表和数组,二、数组 1、数组的特点 均匀性：每个元素占据相同大小的存储空间。 静态分配空间，必须预先定义大小。 随机存取：下标与值一一对应，每个元素由下标确定位置。 2、数组的顺序分配n维数组A=l1u1, l2u2, lnun元素个数：一维数组存储同构的线性表，要存储n维数组，需将n维下标映射为计 算机存储的一维地址,2.2 线性表和数组,n维数组的存储 行主排列法：按下标由外至里变化的顺序依次存放于内存(外先变) 列主排列法：按下标由里至外变化的顺序依次存放于内存 例：二维数组A=1m，1n 行主序：列主序：,2.2 线性表和数组,地址计算公式（P44
5、） 一维数组 二维数组 三维数组 n维数组 三、顺序表(数组)的运算 （1）插入，设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i(0=ii;k-) listk=listk-1;/第n-1结点至第i结点后移1个位置listi=x;/新结点插入+*npt;/线性表结点数加1return 0;/插入成功 ,2.2 线性表和数组,（2）删除：在有n个结点的线性表中，删除第i(0=i=n-1)个结点。步骤如下： 检查有关参数的合理性； 把原来第i+1个结点至第n-1个结点依次前移一个位置； 修正结点个数。,2.2 线性表和数组,int sq_delete(int *lis
6、t,int *npt,int i) /*list,线性表首结点指针 /*npt,记录线性表结点数的变量的指针 /i,删除位置 int k;if (i *npt) return 1;/不合理的删除位置if (*npt=0) return 2;/线性表已空for(k=i+1;km或top=maxn) return 1;/栈满，进栈失败返回1*toppt+；stack*toppt=x;/完成进栈return 0;/进栈成功返回0 int pop(NODE stack,int *toppt,NODE *cp)/弹栈函数 if (*toppt=0) return 1;/栈空，弹栈失败返回1*cp=sta
7、ck*toppt;/完成弹栈*toppt-；return 0;/弹栈成功返回0 ,2.3 栈和队列,3、栈的应用 子程序的调用及返回 调用时，下一语句地址压栈； 返回时，弹栈，获得返回后的执行语句的地址,2.3 栈和队列,表达式计算 参数传递 递归过程的实现,2.3 栈和队列,二、队列 1、定义是一种只许在队首删除元素，在队尾插入元素的先进先出(FIFO)的 线性表。2、顺序存储队列 （1）顺序队列 队尾指示器rear指示队尾元素，队头指示器front指示队头元素的前一位置，即队头指针所指的位置是空的。,2.3 栈和队列,入队时，rear+1，加入数据元素；出队时，取出数据元素，front+1
8、；当front=rear时，队列空。 存在问题：随着进队和出队操作，front和rear数组尾端，会出现前端空着，而队列空间已用完的情况,称为“假溢出”(P40,图2.21(c)。 为此，引入循环队列。 （2）循环队列（见下页图）将实现队列的数组的首元与末元连接起来。当rear=Maxsize时，如果q1有空，下一个元素将加入q1。 判断队空、队满的条件 rear赶上front：队满 front赶上rear：队空,2.3 栈和队列,判断条件同为rear=front，怎么办？ 区别方法：只剩一个空结点时就认为队满。（rear+1）MOD Maxsize=front，即少用一个单元区别两种情况。
9、循环队列的运算 判空（front=rear） 入队判断是否队满如未满调整队尾指示器rear把数据元素插入队尾 出队判断是否队空如未空调整队首指示器front取出数据元素。,2.3 栈和队列,int en_queue(NODE q,int maxn,int *tpt,int *hpt,NODE x)/入队函数 /设队列结点的数据类型为NODE，用能存储maxn个结点的数组实现 *tpt=(*tpt+1)%maxn;/*tpt队尾位置if (*tpt=*hpt) /队满，*hpt队首位置 *tpt=(*tpt-1+maxn)%maxn;/恢复队尾位置*tptreturn 1;/进队失败q*tpt=
10、x;return 0； int de_queue(NODE q,int maxn,int *tpt,int *hpt,NODE *cp)/出队函数 if (*hpt=*tpt) return 1；/队空*hpt=(*hpt+1)%maxn;*cp=q*hpt；return 0;,2.3 栈和队列,队列的应用 多道程序中的CPU管理 在只有一个CPU和内存的条件下，多用户同时使用计算机，需要在他们之间合理分配计算机资源。多用户队列在实现合理分配CPU中起重要作用。 缓冲区的设计 计算机向外设传送数据时，先把数据送到缓冲区，然后外设依次从缓冲区取数据进行具体操作。,2.4 链表,链接存储的特点：
11、动态分配存储空间； 增删操作不需移动大量元素，不要求连续存储。 链表的分类： 按链(指针)个数：单链表、双链表、多重链表 按指针方向：双向链表、循环链表 一、单链表1、定义链式存储的线性表。,2.4 链表,结点除信息域外还含有一个指针域，用来指出其后继结点的位置 最后一个结点没有后继结点，指针它的指针域为空(记为NIL 或)。另外还需要设置一个指针head，指向单链表的第一个结点,2.4 链表,2、单链表的操作,插 入,删 除,单链表的算法,插入算法 三种插入位置分析 插入表头： 空表，非空表统一修改头指针 中间结点或尾结点前：修改中间结点链域 尾结点后：修改尾结点链域 后两种操作统一,单链表
12、删除算法,删除第i个结点，i为0n1三种删除位置分析 删除表头结点： 修改头指针 删除中间结点或尾结点：修改中间结点链域 时间复杂度O（n），用于沿链找删除结点,2.4 链表,void insertList(nodetype *l, nodetype*np, char e)/在单链表的某给定字符节点e后插入新结点，如找不到则查在尾部；np是插入的新结点指针 nodetype*p;/if(*l=NULL)/如链表为空，则把插入结点作为头结点 np-lp=*l;/把np的指针域设为NULL*l=np;/把np设为头指针else p=*l;/取头指针while(p-lp!=NULL /把p的指针域指
13、向np ,2.4 链表,（2）删除算法,void deleteList(nodetype *l,char e)/l为链表头指针的指针 if(*l=NULL) return ;/空链表，返回nodetype *p,*q;p=*l;/ p用于判断比较q=NULL;/ q用于指向当前结点的前驱结点while(p!=NULL /回收被删除结点的空间 ,2.4 链表,删除算法需要2个检测指针，才能完成删除。一个用来判断 比较(p)，一个用来指向当前结点的前驱结点(q)。3、存储池是由若干可用结点组成的链表。需要的时候， 从表的首部取走一个即可，返归的时候也只要将 其链接在首部。,2.4 链表,它是OS存储管理的部分，OS采用某些方式将内存中空 闲的部分管理起来。当应用程序申请动态分配存储空间 时，存储管理从存储池中分配给用户，当用完后，应用程 序释放动态存储空间，由存储管理将其归还存储池中。,
