顺序表的插入操作 伪代码如下
1.如果表满了,则抛出上溢异常;
2.如果元素的插入位置不合理,则抛出位置异常;
3.将最后一个元素直至第 i 个元素分别向后移动一位置;
4.将元素 x 填入位置 i 处; 5.表长加一; 算法如下
void SeqList<DataType>::Insert(int i,DataType x) {
If(length>=MaxSize)throw”上溢”;
If(i<1||i>length+1)throw”位置”;
for(j=length;j>=i;j- -) { Data[j]=data[j-1]; }
//注意第 j 个元素存在于数组下标为 j-1 处
Data[i-1]=x; length++; } 平均 O(n)
顺序表的删除操作 伪代码如下
1.如果表空,则抛出下溢异常;
2.如果删除位置不合理,则抛出位置异常;
3.取出被删元素; 5.表长减一,返回被删元素值;
4.将下标 i,i+1,...,n-1 处的元素分别移到下标 i-1,i,...,n-2 处;
DataType SeqList<DataType>::Delete(int i) {
If(length==0)throw”下溢”;
If(i<1||i>length)throw”位置”;
x=data[i-1]; //取出位置 i 的元素
for(j=i;j<length;j++) { data[j-1]=data[j]; }
//注意此处 j 已经是元素所在的数组下标
Length- -; return x; } 平均 O(n)
单链表的插入算法 伪代码如下
1.工作指针 p 初始化; 2. 查找第 i-1 个结点并使工作指
针 p 指向该结点; 3.若查找不成功,说明插入的位
置不合理,抛出插入位置异常;
否则,3.1 生成一个元素值为 x 的新结点 s;
3.2 将新结点 s 插入到结点 p 之后; 算法如下
void LinkList<DataType>::insert(int i,DataType x) {
p=first; count=0; //工作指针 p 指向头结点
while(p!=NULL&&count<i-1) //查找第 i-1 个结点
{ p=p->next; count++; } //工作指针后移
if(p==NULL)throw”位置”; //没有找到第 i-1 个结点
else{ s=new Node; s->next=x; //申请一个结点 s,其数据域
为 x s->next=p->next; p->next=s;
//将结点 s 插入到结点 p 之后 } }
头插法建立单链表算法
LinkList<DataType>::LinkList(DataType a[ ],int n) {
first=new Node; first->next=NULL;//初始化一个空链表
for(i=0;i<n;i++) { s=new Node; s->data=a[i];
// 为 每 个 数 组 元 素 建 立 一 个 结 点 s->next=first->next;
first ->next=s; //将结点 s 插到头结点之后 } }
尾插法建立单链表算法
LinkList<DataType>::LinkList(DataType a[ ],int n) {
first=new Node; //生成头结点
r=first; //尾指针初始化 for(i=0;i<n;i++) { s=new Node;
s->data=a[i]; //为每个数组元素建立一个结点
r->next=s; r=s; //将结点 s 插入到终端结点之后 }
r->next=NULL; //单链表建立完毕,将终端结点的指针域
置空 }
单链表的删除操作
DataType LinkList<DataType>::Delete(ine i) {
p=first; count=0; //注意工作指针 p 要指向头结点
while(p!=NULL&&count<i-1) //查找第 i-1 个结点 {
p=p->next; count++; }
If(p==NULL||p->next==NULL) //结点 p 不存在或 p 的后继
结点不存在 throw”位置”; else {
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q; return x; } } 时间复杂度 O(n)
顺序表与链表的比较
1.时间性能的比较:若线性表需频繁查找却很少进行插
入和删除操作,或其操作和”数据元素在线性表的位置”
密切相关时,宜采用顺序表作为存储结构;若线性表需
频繁的进行插入和删除操作,宜采用链表作为存储结构
2.空间性能的比较:当线性表中元素个数变化较大或者
未知时,最好使用链表实现;如果事先知道线性表的大
致长度,使用顺序表的空间效率会更高.
总之,不能笼统的说哪种存储结构更好,得根据实际问
题的需要来判断.
栈(特性后进先出,限定在表尾进行插入删除操作)
顺序栈的入栈操作 伪代码如下
在栈中插入一个元素 x 只需将栈顶指针 top 加 1,然后在
top 指向的位置填入元素 x, 算法如下
void SeqStack<DataType>::Push(DataType x) {
if(top==StackSize - 1)throw”上溢”;
data[++top]=x; } 时间复杂度 O(1)
顺序栈的出栈操作 伪代码如下
删除栈顶元素只需取出栈顶元素,然后将栈顶指针 top
减 1,算法如下
DataType SeqStack<DataType>::Pop( ) {
if(top== -1)throw”下溢”;
x=data[top- -]; return x; } 时间复杂度 O(1)
链栈的入栈操作 伪代码如下
链栈的插入操作只需处理栈顶即第一个位置的情况,而
无需考虑其他位置的情况. 算法如下
void LinkList<DataType>::Push(DataType x) {
s=new Node; s->data=x; //申请一个数据域为 x 的结点 s
s->next=top; top=s; //将结点 s 插在栈顶}时间复杂度 O(1)
链栈的出栈操作 伪代码如下
链栈的出栈操作只需处理栈顶即第一个位置的情况,而
无需考虑其他位置的情况. 算法如下
DataType LinkList<DataType>::Pop( ) {
if(top==NULL)throw”下溢”;
x=top->data; p=top; //暂存栈顶元素
top=top->next; //将栈顶结点摘链
delete p; return x; } 时间复杂度 O(1)
顺序栈与链栈的比较:只需比较空间性能,初始时顺序栈
必须确定一个固定的长度,所以存在空间浪费.链栈的每
个元素都需要一个指针域,所以产生了结构性开销.所以
当栈的使用过程中元素个数变化较大时,用链栈是适宜
的;反之,应该使用顺序栈.
队列(具有线性关系,先进先出)
队列这种首尾相接的顺序存储结构称为循环队列,可以
解决假溢出,通过取模操作很容易实现.
判断队空的条件是 front=rear; 判断队满的条件是:
(rear + 1) % QueueSize = front.
循环队列的入队操作 伪代码如下
循环队列的入队操作只需将队尾指针 rear 在循环意义下
加 1,然后将待插元素 x 插入队尾位置. 算法如下
void CirQueue<DataType>::EnQueue(DataType x) {
if((rear+1)%QueueSize==front)throw”上溢”;
rear=(rear+1)%QueueSize; //队尾指针在循环意义下加 1
data[rear]=x; //在队尾处插入元素 } 时间复杂度 O(1)
循环队列的出队操作 伪代码如下
循环队列的出队操作只需将队头指针 front 在循环意义
下加 1,然后读取并返回队头元素. 算法如下
DataType CirQueue<DataType>::DeQueue( ) {
if(rear==front)throw”下溢”;
i=(front + 1)%QueueSize; //注意不要给队头指针赋值
Return data[i]; } 时间复杂度 O(1)
队列的链接存储结构称为链队列,为了使空队列和非空
队列的操作一致,链队列也加上头结点.
链队列的构造函数操作 伪代码如下
构造函数的作用是初始化一个空的链队列,只需申请一
个头结点,然后让队头指针和队尾指针均指向头结点.
算法如下:LinkQueue<DataType>::LinkQueue( ) {
s=new Node; s->next=NULL; //创建一个头结点 s
Front= rear = s; //将队头指针和队尾指针都指向头结点
s } 时间复杂度 O(1)
链队列的入队操作 伪代码如下
链队列的插入操作只考虑在链表的尾部进行,由于链队
列带头结点,空链队列和非空列队列的入队操作语句一
致. 算法如下
void LinkQueue<DataType>::EnQueue(DataType x) {
s=new Node; s->data=x; //申请一个数据域为 x 的结点 s
s->next=NULL;
rear->next=s; //将结点 s 插入到队尾
rear=s ; } 时间复杂度 O(1)
链队列的出队操作 伪代码如下
链队列的删除操作只考虑在链队列的头部进行,需要注
意队列长度等于 1 的特殊情况. 算法如下
DataType LinkQueue<DataType>::DeQueue( ) {
if(rear= =front)throw”下溢”;
p=front->next; x=p->data; //暂存队头元素
front->next=p->next; //将队头元素所在结点摘链
If(p->next= =NULL)rear=front; //判断出队前队列长度是
否为 1 delete p;
return x; } 时间复杂度 O(1)
二叉树的特点:1.每个结点最多有两棵子树,所以二叉树
不存在度大于 2 的结点; 2.二叉树是有序的,其次序不能
任意颠倒,即使树中的某个结点只有一棵子树,也要区分
它是左子树还是右子树.所以二叉树和树是两种树结构.
二叉树的前序遍历操作,定义如下
若二叉树为空,则空操作返回;否则 1.访问根结点
2.前序遍历根结点的左子树 3.前序遍历根结点的右子树
void BiTree<DataType>::PreOrder(BiNode<DataType>*bt)
{
if(bt==NULL)return; //递归调用的结束条件 else {
cout<<bt->data; //访问根结点 bt 的数据域
PreOrder(br->lchild); //前序递归遍历 bt 的左子树
PreOrder(bt->rchild); //前序递归遍历 bt 的右子树} }
二叉树的中序遍历操作,定义参考前序遍历,算法如下
void BiTree<DataType>::InOrder(BiNode<DataType>*bt) {
if(bt==NULL)return; //递归调用的结束条件 else {
InOrder(bt->lchild); //中序递归遍历 bt 的左子树
cout<<bt->data; //访问根结点 bt 的数据域
InOrder(bt->rchild); //中序递归遍历 bt 的右子树} }
二叉树的后序遍历操作,定义参考前序遍历,算法如下
void
BiTree<DataType>::PostOrder(BiNode<DataType>*bt){
if(bt==NULL)return; //递归调用的结束条件 else {
PostOrder(bt->lchild); //后序递归遍历 bt 的左子树
PostOrder(bt->rchild); //后序递归遍历 bt 的右子树
cout<<bt->data; //访问根结点 bt 的数据域 } }
二叉树的层序遍历操作 伪代码如下
1.队列 Q 初始化 2.如果二叉树非空,将根结点入队
3.循环直到队列 Q 为空 3.1 q=队列 Q 的队头元素出队
3.2 访问结点 q 的数据域 3.3 若结点 q 存在左孩子,则将
左孩子指针入队 3.4 若结点 q 存在右孩子,则将右孩子
指针入队. 算法如下
void BiTree<DataType>::LeverOrder( ) {
front=rear= -1; //采用顺序队列,并假定不会发生上溢
if(root==NULL)return; //二叉树为空,算法结束
Q[++rear]=root; //根指针入队
while(front!=rear) //当队列非空时 {
q=Q[++front]; //出队 cout<<q->data;
if(q->lchild!=NULL) Q[++rear]=q->lchild;
if(q->rchild!=NULL) Q[++rear]=q->rchild; } }
如何构造二叉树,需要中序序列和前序或后序中的一个
才能写出一个确定的二叉树.
1.树转换为二叉树.方法是 1.1 加线——树中所有相邻兄
弟结点之间加一条连线. 1.2 去线——对树中的每个结点,
只保留它与第一个孩子结点之间的连线,删去它与其他
孩子结点之间的连线. 1.3 层次调整——以根结点为轴心,
将树顺时针转动一定的角度,使之层次分明.
注:树的前序遍历对应二叉树的前序遍历
树的后序遍历对应二叉树的中序遍历
2.森林转换为二叉树.方法是 2.1 将森林中的每棵树转换
成二叉树; 2.2 从第二棵二叉树开始,依次把后一棵二叉树
的根结点作为前一棵二叉树根结点的右孩子,当所有二
叉树连起来后,此时所得到的二叉树就是由森林转换得
到的二叉树.
3.二叉树转换成树或森林.方法是 3.1 加线——若某结点
x 是其双亲 y 的左孩子,则把结点 x 的右孩子丶右孩子的
右孩子······,都与结点 y 用线连起来. 3.2 去线
——删去原二叉树中所有的双亲结点与右孩子结点的连
线. 3.3 层次调整——整理由 3.1 丶 3.2 两步所得到的树
或森林,使之层次分明.
4.森林的遍历方法有两种:前序(根)遍历和后序(根)遍历
前序遍历森林即为后序遍历森林的每一棵树,后序遍历
同样后序遍历森林的每一棵树.
哈夫曼树也称最优二叉树,给定一组具有确定权值的叶
子结点,可以构造出不同的二叉树,将其中带权路径长度
最小的二叉树称为哈夫曼树.
叶子结点的权值是对叶子结点赋予的一个有意义的数值
量.设二叉树具有 n 个带权值的叶子结点,从根结点到每
个叶子结点的路径长度与相应叶子结点权值的乘积之和
叫做二叉树的带权路径长度(WPL).
哈夫曼算法:(1)初始化:由给定的 n 个权值构造 n 棵
只有一个根结点的二叉树,得到一个二叉树集合 F.
(2)选取与合并:在 F 中选取根结点的权值最小的两棵
二叉树分别作为左丶右子树构造一棵新的二叉树,这棵
新二叉树的根结点的权值为其左丶右子树根结点的权值
之和.
(3)删除与加入:在 F 中删除作为左丶右子树的两棵二
叉树,并将新建立的二叉树加入到 F 中.
(4)重复(2)(3)两步,当集合 F 中只剩下一棵二叉树
时,这棵二叉树便是哈夫曼树.
注:在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度
均为 2,根据二叉树的性质可知,具有 n 个叶子结点的哈夫
曼树共有 2n-1 个结点,其中有 n-1 个非叶子结点,它们是
在 n-1 次的合并过程中生成的.
根据所给的一串编码构造哈夫曼编码树,规定哈夫曼编
码树的左分支代表 0,右分支代表 1,从根结点到每个叶子
结点所经过的路径组成的 0 和 1 的序列便为该叶子结点
对应字符的编码,称为哈夫曼编码.
前缀编码:如果一组编码中任一编码都不是其他任何一
个编码的前缀,我们称这组编码为前缀编码.前缀编码保
证了编码被编码时不会有多种可能.
图是由顶点的有穷非空集合和顶点之间边的集合组成,
注:边集可以为空,顶点集不能为空.
若两个顶点之间的边没有方向,称做无向边,用小括号表
示. 若两个顶点之间的边有方向,称做有向边,用尖括号
表示,有箭头的一端称为弧头.
如果图的任意两个顶点之间的边都是无向边,则称该图
为无向图,否则称为有向图.
若不存在顶点到其自身的边,且同一条边不重复出现,则
称这样的图为简单图.
在无向图中,若两个顶点之间有边,则称两个顶点互为邻
接点,同时称边依附于这两个顶点.
在有向图中,对于任意两个顶点 A 和 B,若存在弧<A,B>,则
称顶点 A 邻接到 B,顶点 B 邻接自 A,同时称弧<A,B>依附
于顶点 A 和 B.
在无向图中,如果任意两个顶点之间都存在边,则称该图
为无向完全图.含有 n 个顶点的无向完全图有 n*(n-1)/2
条边.
在有向图中,如果任意两顶点之间都存在方向互为相反
的两条弧,则称该图为有向完全图.含有 n 个顶点的有向
完全图有 n*(n-1)条边.
在完全图中,边(或弧)的数目达到最多.
顶点的度时依附于该顶点的边的个数.
在图中,权通常是指对边赋予的有意义的数值量.
边上带权的图称为网或网图.
在路径序列中,顶点不重复出现的路径称为简单路径.除
了第一个顶点和最后一个顶点之外,其余顶点不重复出
现的回路称为简单回路.
在无向图中,若任意顶点 A 和 B 之间有路径,则称该图是
连通图.非连通图的极大连通子图称为连通分量,“极大”
评论0
最新资源