## 問題描述 > 將一個帶頭結點的單鏈表分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數的元素，而B表中含有元表中序號為偶數的元素，且保持其相對順序不變。 ## 算法思想 > 因為本題中涉及到到按序號拆分單鏈表的操作，因此我們對單鏈表的定義進行一次修改，加入序號元素num，這樣只需要對num元素判斷奇偶便可。因為題目中需要拆分成兩個不同的鏈表，因此這里創建了兩個空的單鏈表，頭節點分別為head1，head2。用指針p對原來的單鏈表進行一次遍歷，如果結點的num域為偶數，則將該結點拆下，為了讓其相對順序不發生變化，采用尾插法將該結點插入到第二個單鏈表中，這樣以來，便成功的將一個鏈表拆分稱為兩張鏈表，head1表中存放的是原表中序號為奇數的元素，而head2表中含有元表中序號為偶數的元素。 ## 算法描述 ~~~ //單鏈表定義 typedef int ElemType; typedef struct LNode{ ElemType data; int num; struct LNode *next; }LNode, *LinkList; /*------------------------------------------------------*/ //拆分單鏈表 LinkList SeparateList(LNode *head1) { LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); LNode *r=head2; LNode *pre=head1; LNode *p=pre->next; while(p){ if(p->num%2){ pre=p; p=p->next; }else{ pre->next=p->next; r->next=p; r=p; p=pre->next; } } r->next=NULL; return head2; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; int num; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList SeparateList(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1->next=NULL; head1=CreatList(head1); printf("head :"); Print(head1); LNode *head2; head2=SeparateList(head1); printf("head1:"); Print(head1); printf("head2:"); Print(head2); return 0; } //尾插法建立單鏈表 LinkList CreatList(LNode* head) { int cnt=1; LNode *r=head; LNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->num=cnt++; r->next=s; r=s; scanf("%d",&x); } r->next=NULL; return head; } //拆分單鏈表 LinkList SeparateList(LNode *head1) { LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); LNode *r=head2; LNode *pre=head1; LNode *p=pre->next; while(p){ if(p->num%2){ pre=p; p=p->next; }else{ pre->next=p->next; r->next=p; r=p; p=pre->next; } } r->next=NULL; return head2; } //打印全部結點 void Print(LNode* head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~