数据结构 绪论

杂谈

1.关于 typedef 和#define

1）typedef

有的书上在定义变量的时候会出现一些你在程序设计教材中从来没见过的诡异的数据
类型，比如严奶奶书上就有类似于 Elemtype A;的变量定义语句，这里的 Elemtype 是
什么类型，新来的同学常常会一头雾水。要说明这个问题，我们先来说明一下 typedef 的
用法。一句话，typedef 就是用来给现有的数据类型起一个新名字的，我们在结构类型定
义时用到过，如 typedef struct{……} TypeA;即为给 “struct{……}”起了一个
名字 TypeA，就好比你制作了计算机中的整型，给他起了个名字为 int。并且如果我想给
int 型起个新名字 A,就可以这样写 typedef int A;这样的话定义一个整形变量 x 的时
候 A x;就等价于 int x;在考研中 typedef 用的最多的地方就在结构型的定义过程中，
其他的地方几乎不用。你可以这样理解 typedef 是用来起名字的，新定义的结构型没有名
字，因此用 typedef 给它起个名字是有必要的，但是对于已有的数据类型，如 int，float
等已经有了简洁的名字，还有必要给它起个新名字吗？有必要，但不是在考研数据结构中。
为什么有必要，有兴趣的同学可以去查下资料，查完你会发现，typedef 对程序设计的贡
献很大，但是对于考研答卷，用处不大，所以大家对其用法不必深究。说到这里大家就明白
了，严奶奶的书上之所以有那么多大家不认识的数据类型，只不过是严奶奶悄悄的给我们认
识的数据类型起了新名字而已。

2）#define

在严奶奶的书上除了我们没见过的数据类型以外，还有一些东西我们也没见过，比如在
一个函数中她会写到 return ERROR； return OK；之类的语句，对于经常在编译器上
写代码的同学，乍一看到这种语句会十分的不爽，立马就会想，ERROR 和 OK 这样的东西能
编译通过？或者就是怀疑自己语言水平太差，严奶奶写的程序里边有太多自己看不懂的地方
了，信心大减。其实不然，和 typedef 一样，严奶奶悄悄的用#define 语句处理过 ERROR
或者 OK 之类的词了。其实 ERROR 和 OK 就是两个常量，作为函数的返回值，来提示用户函
数操作结果的。严奶奶初衷是想把 0,1 这种常作为函数返回标记的数字定义成 ERROR 和
OK（一般出错返回 0，成功返回 1），这样比起数字来更人性化，更容易理解，但结果却适
得其反，让新手们更困惑了。#define 对于考研数据结构可以说没有什么贡献，我们只要
认得它就行，写程序时一般用不到。比如#define MAX 50 这句，即定义了常量 MAX（此
时x=50;等价于x=MAX;）。在写程序大题的时候如果你要定义一个数组，如int A[MAX];
加上一句注释：“/MAX 为已经定义的常量，其值为 50/”即可。

说到这就想起某天在qq空间看到的一张图，你见过什么样的代码让你虎躯一震
#define ；;
发现了什么，没发现？仔细看！将中文分号定义为英文分号，妈妈再也不用担心我的程序因为输入法的问题编译错误了！

2.函数

STATUS f(ELEMTYPE a)
{
if(a>=0) return ERROR;
else return OK;
}

对于一些基础稍差的同学来说，这个函数麻烦了，STATUS,ELEMTYPE,ERROR,OK 这都什么东西，其实严奶奶在离这个函数很远的地方写过这些语句：
#define ERROR 1
#define OK 0
typedef STATUS bool //这句中的 bool 是布尔型，只取两个值0 和 1，其实用 bool 用 int 型代替就可以。
typedef ELEMTYPE int
在那个函数前边加上这四句是否看懂了呢？看懂后可以把它翻译一下就能写出以下代码：

bool f(int a) //本行可换成 int f(int a)
{
    if(a>=0) return 1;
    else return 0;
}

上边这种写法是不是清楚明白了。严奶奶之所以要将程序写的如此个性，原因有两个，
一是上边那个自己另起的类型名或者常量名，都有着实际的意义，STATUS 代表状态，OK
代表程序执行成功，ERROR 代表出错，这样代码写的就更人性化。二是，如果我们在写一
个大工程，对于其中的一个变量，在整个工程中都已经用 int 型定义过了，但是工程现在
要求修改，将所有 int 型换成 char 型，这下麻烦就大了。如果你写成上边那种形式，将
int 型起个新名字 ELEMTYPE，在整个程序中凡是类似于 int x;的语句都写成 ELEMTYPE
x;此时如果要统一更换数据类型，只需将 typedef ELEMTYPE int 这一句中的 int 换成
char 即可，这无疑是十分方便的事情，这就是 typedef 对于程序设计的意义所在
（#define 也能达到类似的目的）。

算法的时间复杂度与空间复杂度分析基础

时间复杂度

Alt text

1.计算一个算法时间复杂度的步骤如下：

• 确定算法中的基本操作，以及问题的规模。
• 根据基本操作执行情况计算出规模 n 的函数 f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。

注意：有的算法中基本操作执行次数跟初始输入的数据有关。如果题目不做特殊要求，
一般我们依照使得基本操作执行次数最多的输入来计算时间复杂度，即将最坏的情况作为算法时间复杂度的度量。

2.分析以下算法的时间复杂度。

void fun(int n)
{
    int i=0;s=0;
    while(s<n)
    {
        i++;
        s=s+i;
    }
}

分析：
显然 n 为规模，基本操作为 i++;s=s+i;i 与 s 都从 0 开始，假设循环执行 m 次结束，
则有 s 1 =1,s 2 =1+2=3,s 3 =1+2+3=6, ……,s m =m(m+1)/2（其中 s m 为执行到第 m 次的时
候 s 的值），则有 m(m+1)/2+K=n，（K 为起修正作用的常数）由求根公式得：

Alt text

由此可知时间复杂度为：
T(n)=O(√n)

基本概念和术语

数据：含义极为广泛
数据元素：数据的基本单位
数据项：数据的不可分割的最小单位
数据对象：数据对象是性质相同 的集合，是数据的一个子集。
数据的逻辑结构
数据的逻辑数结构是对数据之间关系的描述

据结构是指 互之间存在一种或多种特定关系的 数 相 数据元素的集合。数据结构包括 3
方面的内容：逻辑结构，存储结构和对数据的运算。
数据的逻辑结构：对数据之间关系的描述，它与数据的存储结构无关，同一种逻
辑结构可以有多种存储结构。归纳起来数据的逻辑结构主要有两大类。

• 线性结构
• 非线性结构

数据的物理结构（存储结构：有以下四种常用的存储方法

• 顺序存储
• 链式存储
• 索引存储
• 散列（哈希）存储

数据类型和变量：数据类型是一个值的集合以及定义在这个值集上的一组操作

参考文献：数据结构高分笔记、数据结构（严蔚敏、吴伟民著）