计算机数据库(经济会计类)五讲计算机软件技术基础随堂讲义.ppt

5.3 数据结构 (3) 数据结构的运算 数据结构的运算是定义在数据逻辑结构上的操作，如插入、删除、查找、排序等。 比如一张表格，可能需要进行查找、增加、修改、删除记录等，进行这样的操作已不是加减乘除这样一些算术运算，在数据结构中，运算常常涉及算法的问题。  5.3 数据结构 5.3.3 常见数据结构介绍 (了解) (1) 数组 数组属于线性数据结构，是在计算机内存中使用一组连续的存储单元保存数据类型相同的一组数据，这些数据拥有相同的变量名，称为数组名。 5.3 数据结构 (2) 链表 链表(Linked List)是采用链式存储的线性表。线性链表的结点由数据域和指针域两个部分组成，数据域存储数据元素，指针域存储一个指向直接后继结点的指针。 5.3 数据结构 (3) 二叉树 二叉树是一种常用的非线性数据结构，其定义为：二叉树是一个结点的集合，该集合或者为空，或者满足下面两个条件： ① 有且仅有一个称为根的结点。 ② 其它结点分为两个互不相交的集合T1、T2。T1和T2均为二叉树，并且在T1和T2之间存在顺序关系(T1在T2之前)，分别称为根的左子树和右子树。 二叉树的5种基本形态 5.3 数据结构 二叉树的存储结构 5.3 数据结构 遍历二叉树 遍历二叉树是非常重要的一种运算。“遍历”的含义是对结构中的每个数据都访问一次且仅访问一次。可以有三种访问路径： ① 前序遍历:访问根结点;前序遍历左子树;前序遍历右子树 ② 中序遍历:中序遍历左子树;访问根结点;中序遍历右子树 ③ 后序遍历:后序遍历左子树;后序遍历右子树;访问根结点 ① 前序遍历：A B D E F G C ② 中序遍历：D B F E G A C ③ 后序遍历：D F G E B C A 5.4 算法 5.4.1 算法的基本概念 算法是指为解决给定问题而需实施的有穷操作步骤的描述。 5.4.2 算法的描述方法 (1) 用自然语言描述算法 (2) 用流程图描述算法 (3) 使用伪代码描述算法 (4) 用程序设计语言描述算法 算法的描述方法有以下四种： 5.4 算法 5.4.3 查找算法(了解) 查找(Searching)也称检索，设表F中有n个结点，Ki是记录Ri的关键字，现给定关键字K，在F中寻找关键字与K相同的结点R的过程，叫做查找。 (1) 顺序查找 顺序查找是线性表的最简单的查找算法。它是用给定的值与表中的每个结点的关键字逐个进行比较运算，若找到相等的关键字则查找成功，否则查找失败。 顺序查找算法的优点是适用范围广，对线性表中结点逻辑次序无关，即不要求按关键字排序。对线性表的物理存储结构也没有要求，顺序存储与链式存储均可。 5.4 算法 (2) 折半查找 折半查找的基本思想是： 先取表的中间位置的结点关键字与所给定的关键字进行比较，如果相等，则查找成功。如果给定值比该结点的关键字大，则所找结点在表的后半部分；否则所找结点在表的前半部分，然后再把选定的部分表的中间结点的关键字与给定关键字进行比较。如此反复进行，直到查找成功或者查找失败为止。 5.4 算法 例: 5.4 算法 5.4.4 排序算法(了解) 排序(Sort)是数据处理中的一种重要运算，它的功能是将一组数据元素(或记录)从任意序列排列成一个按关键字排序的序列。 按照排序过程中涉及的存储器的不同将排序分为内部排序和外部排序两类，其中内部排序是指整个排序过程都在内存中进行的排序。 5.4 算法 (1) 直接插入排序 算法的基本思想如下： ① 开始时，把第一个记录看成是已经排好序的子序列，这时子序列中只有一个记录； ② 从第二个记录起到最后一个记录，依次将每个记录与前面子序列的记录按关键字比较，确定记录插入的位置； ③ 将记录插入到子序列中，子序列记录个数加1，直至子序列长度与待排序列长度相等时结束。 5.4 算法 (1) 直接插入排序 5.4 算法 5.4.4 排序算法(了解) (2) 冒泡排序 冒泡排序的算法思想是： ① 将第n个记录的关键字与将第n-1个记录的关键字进行比较，若为逆序则将两个记录进行位置的交换，否则保持原来顺序； ② 将第n-1个记录的关键字与将第n-2个记录的关键字进行比较； ③ 重复上述排序过程，直到全部关键字均比较一遍； ④ 上面三步的比较交换过程称为第一趟排序，其结果是使关键字最小的记录被交换到了第1个记录的位置，完成一趟