资源描述：
《内蒙古工业大学谢秀兰计算机软件基础小抄》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1、数据是现实世界客观存在的实体或事情的属性值。是信息的载体。2、硬件系统的组成：运算器、控制器、存储器、输入设备输出设备。3、数据对象：具有相同性质的数据元素的集合。4、数据结构：数据结构是指同一数据对象中各数据元素间存在的关系。S=(D,R)D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。5、算法表示：算法名（参量表）6、线性表的基本运算有：(1)插入：在两个确定元素之间插入一个新元素。(2)删除：删除线性表中某个元素。(3)查找：按某种要求查找线性表中的一个元素，需要时可以进行更新。(4)排序：按给定要求对表中元素重新排序。7、插入设在长度为n
2、的线性表中第i个元素前插入一个元素x，其中存放线性表的向量为V[1:m](m>n)，算法如下：INSERTLIST(V,n,i,x)1.if(i<1)OR(i>n+1)then{参数错return}2.forj=ntoistep(-1)3.V[j+1]←V[j]4.end(j)5.V[i]←x6.n←n+17.return8、回收一个由p指针指向的结点，放回空白链表的算法为：RET(p)1、next(p)←av2、av←p3、return9、设有顺序s[1:m],top为栈顶指示器，其插入（进栈）和删除（退栈）运算如下：PUSH(s,m,top,x)//将元素x入栈//
3、1.if(top=m)then{“上溢”，return}2.top←top+13.s[top]←x4.returnPOP(s,top,y)//退栈，将栈顶元素送入y中//1.if(top=0)then{“下溢”，return}2.y←s[top]3.top←top-14.return10、设CQ[0:m-1]表示最大容量为m的循环队列，其中头、尾指示(front,rear)均按顺时针方向前进，rear=front=n-1为初态。循环队列的插入和删除算法如下：ADDCQ(CQ,m,front,rear,x)//将x插入队列CQ中//1.if(front=(rear+1)m
4、odm)then{“队满”return}2.rear←(rear+1)modm3.CQ[rear]←x4.returnDELCQ(CQ,m,front,rear,y)//删除队首元素送入y中//1.if(front=rear)then{“队空”return}2.front←(front+1)modm3.y←CQ[front]4.return11、设A，B分别为某稀疏矩阵转置前后的三元组表，i为行下标，j为列下标，v为元素值。变量m为稀疏矩阵行数，n为稀疏矩阵列数，tu为非零元素个数。本算法要求把A中的行下标、列下标交换后送到B中，并且使B中行下标仍按递增顺序存放。TRA
5、NSMAT(A，B)1．if(tu≠0)then2．{q←1//q为转置以后B的行号//3．forcol＝1ton4．forp＝1totu//p为转置前A的行号//5．ifA[p]．j＝colthen6．{B[q]．i←A[p]．j;B[q]．j←A[p]．i;7．B[q]．v←A[p]．v；q←q+1}8．end(p)9．end(col)}10．return12、树的定义：树是由n个(n≥0)结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm，其中每一个集合Ti本身又是一棵树，称为根结
6、点root的子树。用二元组关系来定义树为Tree＝(T，R)其中数据元素集合T及关系R组成。13、树结构中的术语:结点(node)：表示树中的元素。结点的度(degree)：结点拥有的子树数。叶子(leaf)：度为零的结点，又称端结点。孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。双亲(parents)：对应上述孩子结点的上层结点称为这些结点的双亲。兄弟(sibling)：同一双亲的孩子。结点的层次(level)：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余各层依此类推。深度(depth)：树中结点的最大层次数。森林(forest)：是m
7、(m≥0)棵互不相交的树的集合。有序树：树中结点在同层中按从左至右有序排列、不能互换的称为有序树，反之称为无序树。14、二叉树的基本性质(1)二叉树的第i层上至多有2i-1(i≥1)个结点。(2)深度为h的二叉树中至多含有2h-1个结点。(3)在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0＝n2+1。15、一般树转换为二叉树16、二叉树遍历DLR：先序遍历LDR：中序遍历LRD：后序遍历例：先序：ABCDEFG中序：CBDAEGF后序：CDBGFEA17、遍历算法PREORDER(p)//先序遍历//1.if(p≠n
