清华大学严蔚敏数据结构

(4)效率与存储量需求 效率指的是算法执行的时 间；存储量需求指算法执行过程中所需要的最 大存储空间。一般，这两者与问题的规模有关。
1.4.3 算法效率的度量 对一个算法要作出全面的分析可分成两用人才 个阶段进行，即事先分析和事后测试
事先分析 求出该算法的一个时间界限函数
事后测试 收集此算法的执行时间和实际占用空 间的统计资料。
时间复杂度为Ｏ(1) 如果将s=0也看成是基本操作，则语句频度为２，
其时间复杂度仍为Ｏ(1)，即常量阶。 例３、for(I=1;I<=n;++I)
{++x;s+=x;} 语句频度为：2n 其时间复杂度为：O(n)
例４、for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{++x;s+=x;} 语句频度为：2n2 其时间复杂度为：O(n2) 即时间复杂度为平方阶。 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一 个m次多项式，则A(n)=O(n m)
定义：如果存在两个正常数c和n0，对于所有的 n≧n0，有︱f(n) ︳≦c｜g(n) ︳
则记作 f(n)=O(g(n))
一般情况下，算法中基本操作重复执行的 次数是问题规模n的某个函数，算法的时 间量度记作
T(n)=O(f(n)) 称作算法的渐近时间复杂度。 例１、for(I=1，I<=n;++I)
2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加
2.1 线性表的逻辑结构
线性表(Linear List) ：由n(n≧)个数据元素(结 点)a1，a2， …an组成的有限序列。其中数据元 素的个数n定义为表的长度。当n=0时称为空表， 常常将非空的线性表(n>0)记作：

31
4、效率与低存储量需求 、
通常，效率指的是算法执行时间；存储量指的是 算法执行过程中所需要的最大存储空间。两者都 与问题的规模有关。
32
算法效率的衡量方法和准则
通常有两种衡量算法效率的方法： 事后统计法 缺点：1、必须执行程序 2、其它因素掩盖算法本质 事后分析估算法 和算法执行时间相关的因素： 1算法选用的策略 2、问题的规模 3、编写程序的语言 4、编译程序产生的机器代码的质量 5、计算机执行指令的速度
5
–例
书目自动检索系统
线性表
书目文件
书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号： 003 高等数学 华罗庚 004 书名： 线性代数 栾汝书 …… 作者名： …… ……
按书名
高等数学 理论力学 线性代数 ……
S01 L01 S01 S02 ……
索引表
按分类号
分类号： 001， 003… … 樊映川 出版单位： 002， … … .. 华罗庚 出版时间： 004， … … 栾汝书 价格： … … ..
29
2、可读性 、
算法主要是为了人的阅读与交流，其次才是为计 算机执行。因此算法应该易于人的理解；另一方 面，晦涩难读的程序易于隐藏较多错误而难以调 试；
30
3.健壮性 健壮性
当输入的数据非法时，算法应当恰当地作出反映 或进行相应处理，而不是产生莫名奇妙的输出结 果。并且，处理出错的方法不应是中断程序的执 行，而应是返回一个表示错误或错误性质的值， 以便在更高的抽象层次上进行处理。
23
1.3 算法和算法分析
算法的概念和描述： 算法的概念和描述： 什么是算法？ 什么是算法？ 算法（ 算法（Algorithm)是为了解决某类问题而规定的一 是为了解决某类问题而规定的一 个有限长的操作序列。 个有限长的操作序列。一个算法必须满足以下五 个重要特性： 个重要特性：

/* c1.h (程序名) */#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等*/#include<limits.h> /* INT_MAX等*/#include<stdio.h> /* EOF(=^Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() *//* 函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE *//* algo2-1.c 实现算法2.1的程序*/#include"c1.h"typedef int ElemType;#include"c2-1.h"/*c2-1.h 线性表的动态分配顺序存储结构*/#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/#define LISTINCREMENT 2/* 线性表存储空间的分配增量*/typedef struct{ElemType*elem; /* 存储空间基址*/int length; /* 当前长度*/int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */}SqList;#include"bo2-1.c"/* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */ Status InitList(SqList*L) /* 算法2.3 */{ /* 操作结果：构造一个空的顺序线性表*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*L).elem)exit(OVERFLOW); /* 存储分配失败*/(*L).length=0; /* 空表长度为0 */(*L).listsize=LIST_INIT_SIZE; /* 初始存储容量*/return OK;}Status DestroyList(SqList*L){ /* 初始条件：顺序线性表L已存在。

1、数据(Data) ：是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

一个数据元素可由若干个数据项(Data Item)组成。

数据项是数据的不可分割的最小单位。

数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C={‘A’,’B’,’C,…} 。

数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。

元素之间的相互联系(关系)称为逻辑结构。

数据元素之间的逻辑结构有四种基本类型，如图1-3所示。

①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

②线性结构：结构中的数据元素之间存在一对一的关系。

③树型结构：结构中的数据元素之间存在一对多的关系。

④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

2、顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

3、C语言中用带指针的结构体类型来描述typedef struct Lnode{ ElemType data; /*数据域，保存结点的值*/struct Lnode *next; /*指针域*/}LNode; /*结点的类型*/4、循环队列为空：front=rear 。

循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

5、性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。

性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。