试设计一个算法，将一个头结点指针为a的单链表A分解为两个单链表A和B

Question

试设计一个算法，将一个头结点指针为a的单链表A分解为两个单链表A和B，其头结点指针分别为a和b。使得A链表只包含原链表A中序号为奇数的元素，而B链表中只包含原链表A中序号为偶数的元素，且保持原来的相对顺序。

Answer 1

程序如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char data;
struct node *nextPtr;
}*LinkList, Lnode;
static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch);
static void Decompose(LinkList *headPtrA, LinkList *headPtrB, LinkList *tailPtrB);
static void VisitList(LinkList headPtr);
static void DestroyList(LinkList *headPtr, LinkList *tailPtr);
int main(void)
{
LinkList headPtrA = NULL, tailPtrA = NULL, headPtrB = NULL, tailPtrB = NULL;
char ch;
while (1)
{
printf("Enter ch('@'-quit): ");
scanf(" %c", &ch);
if (ch == '@')
{
break;
}
else
{
CreateList(&headPtrA, &tailPtrA, ch);
}
}
VisitList(headPtrA); /* 打印分解前的链表 */
if (headPtrA != NULL) /* 链表不空的情况对其进行分解 */
{
Decompose(&headPtrA, &headPtrB, &tailPtrB); /* 对链表进行分解*/
}
else
{
printf("headPtrA is empty.\n");
}
VisitList(headPtrA); /* 打印分解后的链表 */
VisitList(headPtrB);
DestroyList(&headPtrA, &tailPtrA); /* 销毁链表 */
DestroyList(&headPtrB, &tailPtrB);
return 0;
}
static void CreateList(LinkList *headPtr, LinkList *tailPtr, char ch)
{
LinkList newPtr;
if ((newPtr = (LinkList)malloc(sizeof(Lnode))) == NULL)
{
exit(1);
}
newPtr -> data = ch;
newPtr -> nextPtr = NULL;
if (*headPtr == NULL)
{
newPtr -> nextPtr = *headPtr;
*headPtr = newPtr;
}
else
{
(*tailPtr) -> nextPtr = newPtr;
}
*tailPtr = newPtr;
}
static void Decompose(LinkList *headPtrA, LinkList *headPtrB, LinkList *tailPtrB)
{
int count = 0;
LinkList cA, pA;
char ch;
cA = NULL;
for (pA = *headPtrA; pA != NULL; cA = pA,pA = pA -> nextPtr)
{
ch = pA -> data;
count++;
if (count % 2 == 0)
{
CreateList(headPtrB, tailPtrB, ch);
cA -> nextPtr = pA -> nextPtr;
}
}
}
static void VisitList(LinkList headPtr)
{
while (headPtr != NULL)
{
printf("%c -> ", headPtr -> data);
headPtr = headPtr -> nextPtr;
}
printf("NULL\n");
}
static void DestroyList(LinkList *headPtr, LinkList *tailPtr)
{
LinkList tempPtr;
while (*headPtr != NULL)
{
tempPtr = *headPtr;
*headPtr = (*headPtr) -> nextPtr;
free(tempPtr);
}
*headPtr = NULL;
*tailPtr = NULL;
}