设计一个算法将一个带头节点的单链表A分解成两个带头结点的单链表A和B,使A中含有原链表中序号为奇数的元素,而B中含有原链表中序号为偶数的元素,并且保持元素原有的相对顺序。
这个题,我不是很清楚,请各位帮帮忙。
设计一个算法将一个带头节点的单链表A分解成两个带头结点的单链表A和B,使A中含有原链表中序号为奇数的元素,而B中含有原链表中序号为偶数的元素,并且保持元素原有的相对顺序。
这个题,我不是很清楚,请各位帮帮忙。
 2006-05-15 17:29
	    2006-05-15 17:29
  #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;
}
    
        
    

 2006-05-16 00:05
	    2006-05-16 00:05
  
 2006-05-17 23:32
	    2006-05-17 23:32