数据结构复习.doc
《数据结构复习.doc》由会员分享,可在线阅读,更多相关《数据结构复习.doc(4页珍藏版)》请在三一文库上搜索。
1、1、线性结构:结构中的数据元素之间存在一对一的关系。2、数据结构的 形式定义为:数据结构是一个二元组:鶴Data-Structure=(D, S)聲 其中:D是数据元素的有限集,S是D上关系的有限集。 例1复数的数据结构定义如下:聲Complex=(C, R)R=P, P是定义在其中:C是含两个实数的集合C1, C2 ,分别表示复数的实部和虚部。集合上的一种关系C1, C2> 3、 元素之间的关系在计算机中有两种不同的表示方法:顺序表示和非顺序表示。由此得出两种不同的存储结构:顺序存储结构和链式存储结构。4、程序=算法+数据结构5、算法的五个特性(1)有穷性(2)确定性 (3)可行性 4
2、)输入 5)输出6、 算法效率的度量:时间复杂度空间复杂度7、线性表中元素的个数 n称为线性表的长度,n=0时称为空表;线性表:是n个数据元素的有限序列。同一线性表中的元素必须是同一类型的;问2:结构体中间的那个 struct LNode是什么意思?? 答2:在最后一行的"缩写”LNode还没出现之前,只能用原始的 struct LNode来进行变量说明。此处说明了指针分量*next的数据类型是struct LNode为他提供免费环球旅行服务。方法是, m时,这个人OUT,然后从下 直到最后剩下一个人就是幸运之星。问题就是谁问题:一个旅行社要从n名旅客中选出一名幸运旅客, 大家站成圈
3、,然后选定一个 m,从第1个人开始报数,报到 一个人开始重新从1报数,重复这个过程,是幸运者呢?或者说是怎样才能赢大奖。 main()int a50,n; int *p; int i, k, m; printf("please input people p=a;for(i=0;ivn;i+)*(p+i)=i+1; i=0;k=0;m=0; while(mvn-1)if(*(p+i)!=O)k+;if(k=3)*(p+i)=0;k=0;m+;number:");/报数为scanf("%d",&n); 总人数为 np指向数组a的首地址/数组初始化k=
4、3的人出列m为出列的人数i+;if(i=n)i=0;/i = n 时,循环while(*p= = 0)p+;printf("the last people number is:%dn",*p);8、栈必须按“后进先出 ”的规则进行操作 、栈只允许在表尾一端进行插入和删除9、通常称往栈顶插入元素的操作为“入栈”、称删除栈顶元素的操作为“出栈 ”。10、从数据结构的角度看,栈和队列也是线性表、栈(Stack) 是限定仅在表尾进行插入或删除操作的线性表。11、队列 (Queue): 也是运算受限的线性表。是一种先进先出(First In First Out ,简称 FIFO)的线
5、性表。只允许在表的一端进行插入,而在另一端进行删除。队首 (front) :允许进行删除的一端称为队首 。队尾 (rear) :允许进行插入的一端称为队尾。 即队列的修改是依先进先出的原则进行的12、接受用户从终端输入的程序或数据,并存入用户的数据区。? 退格符“ #”退行服“ ”13、树的存储结构 双亲表示法: 假设以一组连续空间存储树的结点,同时在每个结点中附设一个指示器 指示其双亲在链表中的位置。孩子表示法: 多重链表,每个指针指向一棵子树的根结点。 孩子兄弟表示法: 二叉树表示法,链表中两个链域分别指向该结点的第一个孩子和下 一个兄弟结点。 (左边为孩子节点,右边为兄弟节点)14、先序
6、遍历( T L R)若二叉树非空( 1)访问根结点; (2)先序遍历左子树; ( 3)先序遍历右子树15、中序遍历( L T R)若二叉树非空( 1)中序遍历左子树( 2)访问根结点( 3)中序遍历右子树16、后序遍历( L R T)若二叉树非空( 1)后序遍历左子树( 2)后序遍历右子树( 3)访问根结点17、 Huffman 树的构造在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且新的 二叉树根结点权值为其左、右子树根结点的权值之和;在F中删除这两棵树,同时将新得到的树加入F中;重复、,直到 F只含一颗树为止。18、构造Hufman树时,为了规范,规定 F=Ti,E
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习
链接地址:https://www.31doc.com/p-12355917.html