2023-03-30 数据结构【三】 线性表，单链表，双链表，顺

2.3.1 线性表

• i值，存储空间校验
• 新元素e放入 i;
• i后元素后移
• 表增长1

Status ListInsert_Sq(SqList &L,int i,ElemType e){       //算法2.3 顺序表的插入
    //在顺序表L中第i个位置之前插入新的元素e
    //i值的合法范围是1<=i<=L.length+1
    if(i<1 || i>L.length+1) return ERROR;       //i值不合法
    if(L.length==MAXSIZE)   return ERROR;       //当前存储空间已满
    for(int j=L.length-1;j>=i-1;j--)
        L.elem[j+1]=L.elem[j];                  //插入位置及之后的元素后移
    L.elem[i-1]=e;                              //将新元素e放入第i个位置
    ++L.length;                                 //表长增1
    return OK;
}

• 寻找第i-1个结点
• 校验 i大于表长+1或者小于1
• 生成新结点s
• 将结点s的数据域置为e
• 将结点s插入L中

2.3.2 单链表

Status ListInsert_L(LinkList &L,int i,ElemType &e){     //算法2.8 单链表的插入
    //在带头结点的单链表L中第i个位置之前插入元素e
    int j;
    LNode *p,*s;
    p=L;j=0;
    while(p && j<i-1){p=p->next;++j;}       //寻找第i-1个结点
    if(!p||j>i-1)   return ERROR;           //i大于表长+1或者小于1
    s=new LNode;                            //生成新结点s
    s->data=e;                              //将结点s的数据域置为e
    s->next=p->next;                        //将结点s插入L中
    p->next=s;
    return OK;
}   

2.3.3 双链表

• 第i个位置之前插入元素e，i的合法值为1<=i<=表长+1
• 在L中确定第i个元素的位置指针p
• 校验 p为NULL时，第i个元素不存在
• 生成新结点s
• 将结点s数据置为e
• 将结点s插入L中，需要修改4个指针域

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){      //算法2.12 双向链表的插入
    //在带头结点的双向链表L中第i个位置之前插入元素e，i的合法值为1<=i<=表长+1
    DuLNode *s,*p;
    if(!(p=GetElemP_DuL(L,i)))              //在L中确定第i个元素的位置指针p
        return ERROR;                       //p为NULL时，第i个元素不存在
    s=new DuLNode;                          //生成新结点s
    s->data=e;                              //将结点s数据置为e
    s->prior=p->prior;                      //将结点s插入L中，需要修改4个指针域
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
}       

2.3.4 顺序栈

• 插入元素e为新的栈顶元素
• 校验 栈满
• 元素e压入栈顶，栈顶指针加1

//算法3.2　顺序栈的入栈
Status Push(SqStack &S,SElemType &e)
{ // 插入元素e为新的栈顶元素
    if(S.top-S.base==S.stacksize)
        return ERROR;   //栈满
    *(S.top++) = e; //元素e压入栈顶，栈顶指针加1
    return OK;
}

2.3.5 链栈

• 在栈顶插入元素e
• 生成新结点p，并校验是否可以生成
• 将新结点数据域置为e
• 新结点p插入栈顶
• 修改栈顶指针

//算法3.6　链栈的入栈
Status Push(LinkStack &S , SElemType e)
{//在栈顶插入元素e
    SNode *p = new SNode;//生成新结点p
    if(!p)
    {
        return OVERFLOW;
    }
    p->data = e;//将新结点数据域置为e
    p->next = S;//将新结点p插入栈顶
    S = p;//修改栈顶指针
    return OK;
}

2.3.6 循环队列

• 插入元素e为Q的新的队尾元素
• 校验栈满 if((Q.rear+1)%MAXQSIZE == Q.front)

//算法3.15　循环队列的入队
Status EnQueue(SqQueue &Q,QElemType e)
{// 插入元素e为Q的新的队尾元素
    if((Q.rear+1)%MAXQSIZE == Q.front)
    {
        return ERROR;//尾指针在循环意义上加1后等于头指针，表明队满
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1)%MAXQSIZE;
    return OK;
}

2.3.7 链队

//算法3.18　链队的入队
Status EnQueue(LinkQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素
    QNode *p = new QNode;
    if(p == NULL)
    {
        return OVERFLOW;// 存储分配失败
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p; // 修改队尾指针
    return OK;
}

2.3.8 二叉链表

2.3.9 二叉链栈

void Push(LinkStack &S,BiTree e)
{
    //在栈顶插入元素*e
    StackNode *p=new StackNode;
    p->data=*e;
    p->next=S;
    S=p;
}