若1<=i,j<=n,已知k,求i,j(用公式1)
已知k=49求i,j
将j=i代入(公式1)得k+1<=i(i+1)/2求使之成立的最小i.然后再将i值代入(公式1)求出j
若0<=i,j<=n-1已知k求i,j(同上用公式2)
以上方法希望大家掌握!
3.下三角矩阵(类似于对称矩阵)
4.上三角矩阵
若0<=i,j<=n-1已知i,j求k(要求自己会推导)
第p行上恰好有n-p个元素,在i行上ai,j前有j-i个元素,i前有i个完整行
所以第I行前共有元素个数为:
∑(n-p)(求和下限为p=0,上限为i-1)=
(i*(2n-i+1))/2
所以k=(i*(2n-i+1))/2+j-ii<=j(上三角)
若1<=i,j<=n已知i,j求k的情况大家可以自己去推导
k=((i-1)(2n-i+2))/2+(j-i+1)-1
注意:
以上的k值均从0开始。
其实我认为做这种题目,首先看两点,一是矩阵的起始下标,二是数组的开始下标!
检验你的公式是否正确你可以取一个比较容易计算的元素比如a0,2代入到公式检验下,因为a0,2是矩阵的第三个元素!
三角矩阵的存储单元要比对称矩阵多一个元素,用于存储相对三角矩阵的常数值c,存放在第n(n+1)/2+1个单元里
例如:
已知一个9阶上三角矩阵A按行存储在一维数组B中,B[0]存放矩阵中第一个元素a11则B[31]存放元素(a5,6),按列序存放,存放元素(a4,8)
上面题目在录音中均有详细讲解过程。
以上计算每年至少会有一个填空题!
5.三对角矩阵
按行序1<=i,j<=n。
Loc(aij)=Loc(a11)+3*(i-1)-1+j-i+2
若一个s(素数)对角矩阵满足下述条件:
若0<=i,j<=n-1,已知i,j求k。
k=(3*i-1)+(j-i+2)-1=2i+j
若0<=i,j<=n-1已知k求i,ji=(k+1)/3,j=k-2*i.
若1<=i,j<=n 已知i,j求k。
k=3*(i-1)-1+(j-i+2)-1=2*i+j-3
若0<=i,j<=n-1已知k求i,j.i=(k+1)/3+1,j=k-2*i+3
以上公式我认为没有必要去记,可以参考一下人邮出版社的〈数据结构课程辅导与习题解析〉这本书,里面有具体的推导过程。
象上面的所有的计算都有具体例题
6.随机稀疏矩阵存储(只掌握三元组,行逻辑,十字链表不要求掌握)
熟悉带行表的稀疏矩阵的存储结构,会根据行表推导原矩阵(参看04年的简答题)
6.广义表:
判断广义表的深度,广度,和表长。
会画广义表用书上的第一种存储结构。
有很多朋友画广义表的时候经常会出错,我觉得可以用一个方法去检验你画的图是否正确!
你可以根据广义表的表达式用gethead()和gettail()函数取得某一个元素(这是一系列的操作组合,参看04年的填空第六题的形式),然后看在你画的广义表中从表头开始取得该元素是否也经历了这些操作就行了
第六章:
树与二叉树
1.掌握二叉树的5个性质,并能灵活运用!
第三个性质的证明必须掌握(参看04年的简答题1)
2.已知一棵度为m的树,有n1个度为1的结点,有n2个度为2的结点,有nm个度为m的结点,问有多少叶子结点?
免费考研网
n0+n1+….+Nm=∑i*ni+1(求和的下限是i=1,上限是m)
n0=∑(i-1)*ni+1
3.两类特殊的二叉树:
满二叉树(结点数为2**k-1个),完全二叉树(结点号与满二叉树必须对应)
4.性质4的证明 (书上有证明)
5.二叉树的存储结构(书上的定义一定要记住)
顺序存储结构 链式存储
二叉:
空域 n+1
三叉:
空域n+2
一般有:
在一棵有n个结点,度为k的树中必有n*(k-1)+1个空链域
6.各种遍历的递归和非递归算法均应熟练掌握
中序非递归见P130
先序非递归参看相关的资料
后序非递归:
Voidpostorder_fei(BinNode*t)
{ BinNode*p;
printf(“post_order_fei:
“');
top=0;stack[top]=t;
while(top!
=-1)
{while(stack[top])
{top=top+1;
stack[top]=stack[top-1]->lch;
top=top-1;
if(top!
=-1)
{p=stack[top];
if((!
p->rch)||(p->rch->visited==1))
{stack[top]=null;
printf(“%c”,p->data);p->visited=1;
}
else
{top=top+1;stack[top]=p->rch;}
}
}
}
}
7.遍历算法的应用举例
(1)求二叉树中叶子结点的个数。
(先序(中序,后序)遍历二叉树,设一个全局变量作为计数器,左右指针为空的结点为叶结点)
intcountleaf(BinTreeT)
{intn1,n2;
if(!
T)return0;
else{if((!
T->lchild)&&(!
T->rchild))
return1;
else{n1=countleaf(T->lchild);//n1存放左子树的叶结点数
n2=countleaf(T->rchild);//n2存放右子树的叶结点数
return(n1+n2);
}
}
}
(2)求二叉树深度(后序遍历 )
基本思想:
二叉树的深度为左右子树的最大深度加1
intDepth(BinTreeT)
{intdep,dep1,dep2;
if(!
T)dep=0;
else{dep1=Depth(T->lch);
dep2=Depth(T->rch);
dep=1+(dep1>dep2?
dep1:
dep2);
}
returndep;
}
(3)复制二叉树(先序遍历)
Voidcopytree(BinTreeroot,BinTree*newroot)//newroot为指向指针的指针
{if(!
root)*newroot=Null;
else
{*newroot=(BinNode*)malloc(sizeof(BinNOde));
(*newroot)->data=root->data;
copytreer(root->lchild,&((*newroot)->lchild));//复制到左子树
copytree(root->rchild,&((*newroot)->rchild));//复制到右子树
}
}
(4)交换二叉树的左右子树(类似先序遍历,用后序也可以,但中序不行)
Voidexchange(BinNode*T)
{BinNode*q;
if(T)
{q=T->lchild;
T->lchild=T->rchild;
T->rchild=q;
exchange(T->lchild);
exchange(T->rchild);
}
}
(5)建立二叉树的存储结构(不同的定义方法相应有不同的存储结构,现以字符串的形式 根 左子树 右子树定义一棵二叉树(即二叉树的扩展序列)
如:
以字符串AB*C**D**(*号表示空字符)
statusCreatBitree(BiTree&T)//按先序扩展序列建立二叉树的递归算法
{ scanf(&ch);
if(ch==’‘)T=Null;
else{if(!
(T=(BinNode*)malloc(sizeof(BinNode))));
exit(overflow);
T->data=ch;
CreatBitree(T->lchild);
CreatBitree(T->rchild);
}
returnok;
}
7.已知按某规律遍历二叉树的非扩展序列(也即由先序,中序,后序遍历而得的序列),是否可以唯一确定该二叉树的结构?
结论:
按某规律遍历二叉树的非扩展序列不能唯一确定该二叉树的结构
8.已知按某规律遍历二叉树的扩展序列,能否唯一确定该二叉树的结构?
结论:
先序扩展序列能唯一确定 中序扩展序列不能唯一确定
后序扩展序列能唯一确定(从后往前推导)
//按后序遍历扩展序列建立二叉树结构的递归算法
Voidcrt_bt_post(Bitreeptr*bt)
{if(i>=s.len)//I是全局变量,初始值为0,s存放后序扩展序列字符和长度
{bt=stack[top];top=top-1;}//入栈
else
{i++;c=s.ch[i];
if(c=’‘)*bt=Null;
else{*bt=(BiNode*)malloc(sizeof(BiNode));
(*bt)->data=c;
(*bt)->rch=stack[top];top=top-1;
(*bt)->lch=stack[top];top=top-1;
}
top=top+1;stack[top]=*bt;
crt_bt_post(&bt);
}
}
9.层次遍历某二叉树的扩展序列可以唯一确定二叉树的存储结构
按层次遍历的扩展序列建立二叉树非递归算法(pascal)
getnode(varbt:
bitreptr)
begin
i=i+1;e=s.ch[i];
if(c=’‘)thenbt=nil;
elsebegin
new(bt);bt->data=c;que.rear=que.rear+1;que.elem[que.rear]=bt;
end
end
proceedecrt_bt_level(varbt:
bitreptr)
varp:
bitreptr;
begin
que.front=0;que.rear=0;getnode(bt);
whileque.rear<>que.frontdo
begin
que.front=que.front+1;
p=que.elem[que.front];
getnode(p