您当前的位置:首页 > 计算机 > 编程开发 > C语言

将一个线性表拆解为两个线性表

时间:01-03来源:作者:点击数:

问题描述:

设C={a1, b1, a2, b2, …, an, bn}为线性表,用带头结点的hc单链表存放,设计一个就地算法,将其拆分为两个线性表,使得A={a1, a2,…, an}, B={bn, …, b2, b1}。

问题解答:

算法思想:用上题的思路,不设序号变量。二者的差别仅在于对B,表的建立不采用尾插法,而是用头插法。

LinkList DisCreat_2(LinkList &A){
    LinkList B= (LinkList)malloc(sizeof(LNode)) ;  //创建B 表表头
    B->next=NULL;  //B 表的初始化
    LNode *p=A->next, *q;  //p 为工作指针
    LNode *ra=A;  //ra始终指向A的尾结点
    while(p!=NULL){
        ra->next=p;  ra=p;  //将*p 链到 A 的表尾
        p=p->next;
        q=p->next;  //头插后,将断链,因此用q记忆*p的后继
        p->next=B->next;  //将插入到 B 的前端
        B->next=p;
        p=q
    }
    ra->next=NULL;  //A尾结点的next域置空
    return B;
}

该算法特别需要注意的是,用头插法插入结点后,*p的指针域已改变,如果不设变量保存其后继结点会引起断链,从而导致算法出错。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
    无相关信息
栏目更新
栏目热门