【昊昊带你学】基本数据结构(上).doc

流程控制语句及伪代码首先，我们要知道伪代码是为了来描述算法的。所以伪代码必须结构清晰，可读性要好，尽量贴近自然语言。据昊昊所知，伪代码没有什么硬性规定的样子，大家不用拘泥于某种语言只要能表达清楚就好。下面我们来介绍一下常用的语句及其伪代码（这里我参照的是算法导论里的伪代码，以后用的伪代码应该也是参照导论来写的）。If条件语句：顾名思义是由某个条件使流程分化成若干条支线，伪代码如下：If 表达式 then else Switch分支语句：其实switch的功能可以用if条件语句很类似，只是if只能分为两条支线，而switch可以分出很多条，伪代码如下：Switch 表达式Case 值1 ：Case 值2 ：Case 值n ： While循环语句：这个循环语句是先判断再循环，知道条件不满足时退出循环。伪代码如下：While 表达式Do 1、2、3、N、（先判断表达式是否为真，当表达式为真时执行语句1-n，在重复上述过程，直到表达式为假）For 循环语句：这也是一种循环，不过这种循环有明确的次数。伪代码如下：For i a to/downto b （step x）Do （i以x步长 从a 递增/递减 至b执行循环体，这里i是变量）Break：中断语句执行Continue：终止当前循环，继续下一次循环。赋值符号：A 5（将A赋值为5）栈LIFO（last-in-first-out）类型的数据结构，在算法概述那篇文章里已经有所介绍，下面来具来介绍一下栈的实现（来自算法导论）：/galles/visualization/StackArray.html上面那个网址是一个可视的栈。这表示栈为空，top指向0STACK-EMPTY(S) /没有编程经验的孩纸看这里，这叫一个函数If tops = 0Then return trueElse return truePS: S是一个栈，tops返回的是栈顶位置。如果是0则栈中没有元素。否则栈不为空。PUSH(S,x)TopS topS + 1StopS xPS:push的意思是将一个元素压到栈里，那么就需要将栈顶那个指针上移，此时 topS指向的位置没有元素，然后将X赋给StopS。POP(S)If STACK-EMPTY()Then error “underflow”Else topS topS 1Return StopS+1PS: 与PUSH相反，POP要弹出栈顶元素。所以先将栈顶指针下移然后弹出栈顶元素。PEEK(S)Return StopSPS: PEEK是显示栈顶元素而不删除（如果在OOP编程的时候可能不能直接操作栈内元素，用PEEK来封装一下O_o）队 先进先出的数据结构：/galles/visualization/QueueArray.html先进去玩玩吧要注意，这表示头指针在3这个位置这表示尾指针在2这个位置大家可以把队中加满元素，然后DEQUEUE出两个元素，再ENQUEUE一个元素，你会发现它被加到0的位置了。Tail从14跳到了0.ENQUEUE(Q,x)QtailQ xIf tailQ = lengthQThen tailQ 1Else tailQ tailQ + 1PS: 进队操作，x赋给队尾元素，tailQ+1，如果队列已满，队尾指针挪到开头，来防止溢出DEQUEUE(Q)X QheadQIf headQ = lengthQThen