将一个单链表分解为两个单链表A和B
问题描述:
将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A表中含有原表中序号为奇数的元素,而B表中含有原表中序号为偶数的元素,且保持其相对顺序不变。问题解答:
算法思想:设置一个访问序号变量(初值为0),每访问一个结点序号自动加1,然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾。LinkList DisCreat_1(LinkList &A){ //将表A中结点按序号的奇偶性分解到表A或表B中 i=0; //i记录表A中结点的序号 B= (LinkList) malloc (sizeof (LNode) ); //创建 B 表表头 B->next=NULL; //B 表的初始化 LNode *ra = A, *rb=B; //ra和rb将分别指向将创建的A表和B表的尾结点 p=A->next; //p为链表工作指针,指向待分解的结点 A->next=NULL; //置空新的 A 表 while (p!=NULL) { i++; //序号加 1 if (i%2==0) { //处理序号为偶数的链表结点 rb->next=p; // 若B表尾描入新结点 rb=p; //rb指向新的尾结点 }else{ //处理原序号为奇数的结点 ra->next=p; //在A表尾插入新结点 ra=p; } p=p->next; //将p恢复为指向新的待处理结点 } //while 结束 ra->next=NULL; rb->next=NULL; return B; }为了保持原来结点中的顺序,本题釆用尾插法建立单链表。此外,本算法完全可以不用设置序号变量。while循环中的代码改为将结点插入到表A中和将下一结点插入到表B中,这样while中第一处理的结点就是奇数号结点,第二处理的结点就是偶数号结点。