数据结构日记2

第二天时间:9/18/

　　转眼又过了一周了,前面一周里面我编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一定耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会.栈和队列 　　1、知识点: 　　●栈的定义:操作受限的线性表 　　●特点:后进先出 　　●栈的存储结构:顺序,链接 　　　/push(s,d) 　　●栈的基本操作: 　　　\pop(s) 　　栈定义： 　　struct{ 　　　datatypedata[max_num]; 　　　inttop; 　　}; 　　●队列定义 　　特点:先进先出 　　/入队列in_queue(Q,x) 　　●队列的操作: 　　\出队列del_queue(Q) 　　●队列存储结构: 　　链队列: 　　Typedefstructnode{ 　　　Datatypedata; 　　　Structnode*next; 　　}NODE; 　　Typedefstruct{ 　　　NODE*front; 　　　NODE*rear; 　　}Queue; 　　顺序队列: 　　struct{ 　　　datatypedata[max_num]; 　　　intfront,rear; 　　}; 　　问题: 　　队列ó线性表 　　假溢出=循環队列 　　队列满，队列空条件一样=浪费一个存储空间 　　递归 　　定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。 　　包括二个步骤： 　　1）递推6!=5!=4!=3!=2!=1!=0! 　　2）回归==24=6=2=1=0 　　递归工作栈实现递归的机制。 　　2、有关算法： 　　1）顺序，链表结构下的出栈，入栈 　　2）循環，队列的入队列，出队列。 　　3）链队列的入队列，出队列。 　　4）表达式计算：后缀表达式35+6//+*- 　　 　　 　　 　　 　　中缀表达式（3+5）/6-4*（3+6/8）

　　由于中缀比较难处理，计算机内一般先将中缀转换为后缀。 　　运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。 　　　中缀=后缀 　　5)迷宫问题 　　6)线性链表的递归算法一个链表=一个结点+一个链表 　　intfuction(NODE*p){ 　　　if(p==NULL)return0; 　　　elsereturn(function(p-next)); 　　} 　　树与二叉树 　　一、知识点: 　　1.树的定义:data_struct(D,R); 　　其中:D中有一个根,把D和出度去掉,可以分成M个部分. 　　D1,D2,D3,D4,D5…DM 　　R1,R2,R3,R4,R5…RM 　　而子树Ri形成树. 　　1)递归定义高度

--0

--1

--1

--2

--2

此树的高度为2

　　2.二叉树定义: 　　结点个数=0. 　　3.术语:左右孩子,双亲,子树,度,高度等概念. 　　4.二叉树的性质 　　●层次为I的二叉树I层结点2I个 　　●高度为H的二叉树结点2H+1-1个 　　●H(点)=E(边)+1 　　●个数为N的完全二叉树高度为

_LOG2n_

　　●完全二叉树结点编号:从上到下,从左到右.

_i/2_

_i-1/2_

1i结点的左孩子:2i2i+i结点的右孩子:2i+12i+(根)1为起点0为起点

　　二叉树的存储结构: 　　 　　1)扩展成为完全二叉树,以一维数组存储。

　　 　　2)双亲表示法

　　 　　3)双亲孩子表示法

　　结构: 　　 　　typedefstruct{ 　　 　　　datatypedata; 　　 　　　intparent; 　　 　　　intlchild; 　　 　　　intrchild; 　　 　　}NODE; 　　 　　NODEtree[N];//生成N个结点的树 　　 　　4)二叉链表 　　 　　5)三叉链表 　　 　　6)哈夫曼树 　　5.二叉树的遍历 　　　先根　　　中根栈中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树. 　　　后根/ 　　　先,中序已知求树:先序找根,中序找确定左右子树. 　　　层次遍历(队列实现) 　　6.线索二叉树(穿线树) 　　　中序线索二树树目的:利用空指针直接得到中序遍历的结果. 　　　手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 　　结点结构:

　　Ltag=0,lch指向左孩子,ltag=1,指向前趋结点 　　Rtag=0,rch指向右孩子;rtag=1,指向后继结点 　　中序遍历:1)找最左结点(其左指针为空) 　　 　　2)当该结点的rtag=1,该结点的rch指向的就为后继 　　 　　3)当rtag=0,后继元素为右子树中最左边那个 　　N个结点的二树有空指针N+1个 　　周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题(递归)，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#includestdio.h这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然，并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重。

转载请注明：http://www.92nongye.com/hxjs/204613530.html