2.4 刪除
2.4.1 线性表
Status ListDelete_Sq(SqList &L,int i,ElemType &e){ //算法2.4 顺序表的删除
//在顺序表L中删除第i个元素，并用e返回其值
//i值的合法范围是1<=i<=L.length
if(i<1 || i>L.length) return ERROR; //i值不合法
e=L.elem[i-1]; //将欲删除的元素保留在e中
for(int j=i;j<=L.length;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}
2.4.2 单链表
Status ListDelete_L(LinkList &L,int i,ElemType &e){ //算法2.9 单链表的删除
//在带头结点的单链表L中，删除第i个位置，并由e返回值
LNode *p,*q;
int j;
p=L;j=0;
while(p->next && j<i-1){p=p->next;++j;} //寻找第i-1个结点
if(!(p->next) || j>i-1) return ERROR; //i大于表长+1或者小于1
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK;
}
2.4.3 双链表
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){ //算法2.13 双向链表的删除
//删除带头结点的双向链表L中第i个位置之前插入元素e，i的合法值为1<=i<=表长
DuLNode *p;
if(!(p=GetElemP_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
e=p->data; //保存被删结点的数据域
p->prior->next=p->next; //修改被删结点的前驱结点的后继指针
p->next->prior=p->prior; //修改被删结点的后继结点的前驱指针
delete p; //释放被删结点的空间
return OK;
} //ListDelete_DuL
2.4.4 顺序栈
//算法3.3 顺序栈的出栈
Status Pop(SqStack &S,SElemType &e)
{// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.base == S.top)
return ERROR;//栈空
e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
return OK;
}
//算法3.4 取顺序栈的栈顶元素
Status GetTop(SqStack S,SElemType &e)
{// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top == S.base)
return ERROR;
e = *(S.top-1);//栈顶指针减1，将栈顶元素赋给e
return OK;
}
2.4.5 链栈
//算法3.7 链栈的出栈
Status Pop (LinkStack &S,SElemType & e)
{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
SNode *p;
if(!S)
return ERROR;
e = S->data;//将栈顶元素赋给e
p = S;
S = S->next;//修改栈顶指针
delete p;//释放原栈顶结点空间
return OK;
}
2.4.6 循环队列
//算法3.16 循环队列的出队
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.rear == Q.front)
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXQSIZE;
return OK;
}
2.4.7 链队
//算法3.19 链队的出队
Status DeQueue(LinkQueue &Q,QElemType &e)
{//删除Q的队头元素，用e返回其值，并返回OK
if(Q.front == Q.rear)
{
return ERROR; //若队列空，则返回 ERROR
}
QNode *p = Q.front->next;//p指向队头元素
e = p->data;//e保存队头元素的值
Q.front->next = p->next;//修改头指针
if(Q.rear == p)
{
Q.rear = Q.front;//最后一个元素被删，队尾指针指向头结点
}
delete p;
return OK;
}
二叉树的遍历
先序遍历：
1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。
递归
非递归
中序遍历：
1）中序遍历左子树；
2）访问根结点；
3）中序遍历右子树。
递归
非递归
后序遍历：
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根结点。
递归
非递归
层次遍历：
若树为空，则什么都不做直接返回。
否则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
线索二叉树
N个结点的二叉链表，每个结点都有指向左右孩子的
结点指针，所以一共有2N个指针，而N个结点的二叉
树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。比如左图二叉树中有6个结点，那么就有7个空
指针。
大量的空余指针能否利用起来？
指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化
网友评论