数据结构IA数据结构初步幻灯片.ppt

希尔排序(缩小增量法) 排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止 第二部分 问题与习题 问题 Q1. 为了描述并解决先进先出特征的问题，我们一般会采用考虑以下哪种数据结构 A, 队列????? B, 栈????? C, 树????? D, 二叉树 Q2. 为了描述并解决先进后出特征的问题，我们一般会采用考虑以下哪种数据结构（?? ）。 ??A, 队列????? B, 栈????? C, 树????? D, 二叉树 Q3.对线性表进行二分法查找，其前提条件是 A,线性表以顺序方式存储，并且按关键码值排好序 B,线性表以顺序方式存储，并且按关键码值的检索频率排好序 C,线性表以链接方式存储，并且按关键码值排好序 D,线性表以链接方式存储，并且按关键码值的检索频率排好序 习题 题目10 详细参见习题集。 谢谢！ * 总结： 1）量化 2）构建组织，把研发人员和技术管理体系分清楚。技术管理体系的结构、工作内容、流程、输出。 3）培训：对象以岗位为目标 4）项目支持：分清RD体系和业务体系的职责，包括按时间段划分的职责 5）业务线整合：时间 6）DB：需细化，立项、完成时间，何时立项，转到项目控制体系 7）论文 8）专利：跟踪和关注 * 链栈 栈顶 ^ …... top data link 栈底 入栈算法 出栈算法 ^ …... 栈底 top top x p top ^ …... 栈底 top q 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (159)10=(237)8，其运算过程如下: n n div 8 n mod 8 159 19 7 19 2 3 2 0 2 实际情况: (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 队列的顺序存储结构 实现：用一维数组实现sq[M] front=0 rear=0 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J1,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素后一位置； front指示队头元素位置 初值front=rear=0 空队列条件：front==rear 入队列：sq[rear++]=x; 出队列：x=sq[front++]; rear rear front rear 1 2 3 4 5 0 J1,J2,J3出队 J1 J2 J3 front front front 存在问题 设数组长度为M，则： 当front=0,rear=M时，再有元素入队发生溢出——真溢出 当front?0,rear=M时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; 0 M-1 1 front rear …... …... 实现：利用“模”运算 入队： rear=(rear+1)%M; sq[rear]=x; 出队： front=(front+1)%M; x=sq[front]; 队满、队空判定条件 循环队列上的插入操作（进队列） Status EnQueue(SqQueue Q,QEle