数据结构学习笔记.pdf

编程原则

2014年3月27日

22:37

•数据格式不合适，任务与任务之间需要相互转换

•如果不能很好地组织数据结构，将很容易出错或者需要大量的修补

•计算机编程应减少全局变量，不利于模块化和调试，不过C51中却很

合适

•对一个函数，可以列出它的precondition和postcondition

•传参时如果参数很大，复制它将使用大量的时间，比如结构体

•自顶向下细分原则，主程序所有工作都要分给函数来执行，编写主程

序时就要想清所有的原理，但是具体的考虑可以延后

•每个函数都应当只完成一项任务，但一定要很好的完成

•函数输出应该尽量简洁，尽量避免使用全局变量

•为了单独调试某些函数，可以使用占位程序（一些简短的虚拟函数）

分区数据结构的第1页

生命游戏

2014年7月27日

14:32

•多数程序90%的计算时间花费在10%的代码上，在生命游戏中，是判断周围细胞的循环

•switch中，case结果一样：

case1:

case2:

printf(NO!);

•生命游戏中，存活细胞的数量一般远远小于网格的总数（比如1200个中的40个），这样

可以把计算限制在一个有限区域中

•列表：数组无法使用变量声明（起码大部分环境不行），可变大小的列表可以使用固定

长度的数组来实现，生命游戏中就存在要处理的细胞数是变化的的情况

typedefCellListEntry;

在头文件中写typedefcharListEntry;这样在不同环境下修改头文件即可

分区数据结构的第2页

堆栈

2014727

年月日

15:54

•堆栈是一种数据结构

•把数据压入满堆栈或从空堆栈读出数据都应报错

一般的堆栈和可遍历的堆栈严格来说是两种数据类型

如果有必要，可以编写结合链表的堆栈，需要两个*head用于入栈、出

栈，一个是栈顶的指针，一个是临时替换的

为了提高程序的效率，一般大的数据结构无论是否修改都传指针

分区数据结构的第3页

不可遍历堆栈代码

2014年8月4日

15:38

#includestdlib.h

#includestdio.h

#defineMAXSTACK5

typedefenumBoolean{FALSE,TRUE}Boolean;

typedefcharStackEntry;

typedefstructstack

{

inttop;//记录这是堆栈的第几个

StackEntryentry[MAXSTACK];

}Stack;

voidError(char*);

voidCreateStack(Stack*s);

BooleanStackEmpty(Stack*s);

BooleanStackFull(Stack*s);

voidPush(StackEntryitem,Stack*s);

voidPop(StackEntry*item,Stack*s);

voidClearStack(Stack*s);

intStackSize(Stack*s);

voidStackTop(StackEntry*item,Stack*s);

intMenu();

voidmain()

{

intchoice=-1;

Stacka;

Stack*aloc=a;

StackEntrydata;

StackEntry*dataloc=data;

CreateStack(aloc);

while(1)

{

choice=-1;

printf(堆栈现有%d个成员,StackSize(aloc));

MENU:

分区数据结构的第4页

MENU:

choice=Menu();