2023-03-31 数据结构【四】线性表，单链表，双链表，顺序

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个空
指针。

大量的空余指针能否利用起来？

指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化