鏈結串列指標型

99 年公務人員普通考試試題 代號：
類 科： 資訊處理
科 目： 程式設計概要
考試時間： 1 小時 30 分 座號：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

二、用 C 語言撰寫一個函式，能將一只含有數字的單向鏈結串列（singly linked list）切
割成兩個單向鏈結串列，其一只包含奇數元素，另一只包含偶數元素，請勿複製節
點，切割前後都是以數字由小到大排序，假設此函式的原型（prototype）如下：
void split (node *h, node **h1, node **h2)，h是切割前鏈結串列兩個單向鏈結串列指
標，h1,h2 是切割後兩個單向鏈結串列的指標。（25 分）
其中節點的資料結構為
typedef struct node {
3 4 8
3 5 7
h1 切割 h2
4 8
5 7
h
int d;
struct node *next;
} node;
單向鏈結串列範例



#include <stdio.h>
typedef struct node{
int d;
struct node *next;
}node;

typedef node *nodeptr;

void split(node *h,node **h1,node **h2){
node *ptr,*current;
current = h->next;
while(current!=NULL){
ptr=(node *)malloc(sizeof(node));
ptr->d=current->d;
ptr->next=NULL;
if((current->d%2)==1){
(*h1)->next=ptr;
*h1=ptr;
}
else{
(*h2)->next=ptr;
*h2=ptr;
}
current=current->next;
}

}
insert(nodeptr h,int value){
nodeptr previous,current;
nodeptr ptr;
previous = h;
current =h->next;
while(current!=NULL && value>current->d){
previous = current;
current=current->next;
}
ptr = (nodeptr)malloc(sizeof(node));
ptr->d=value;
ptr->next=current;
previous->next = ptr;
}

print(node *h){
node *current;
current = h->next;
while(current!=NULL){
printf("%d\n",current->d);
current=current->next;
}
}

void main()
{
node *h,**h1,**h2;
node *hp1,*hp2;
h=(node *)malloc(sizeof(node));
h->next=NULL;
h1=(node **)malloc(sizeof(node));
(*h1)->next=NULL;
h2=(node **)malloc(sizeof(node));
(*h2)->next=NULL;
insert(h,23);
insert(h,64);
insert(h,25);
insert(h,17);
insert(h,24);
insert(h,38);
hp1=h1;
hp2=h2;
split(h,&h1,&h2);
clrscr();
print(h);
printf("\n");
print(&*hp1);
printf("\n");
print(&*hp2);
getch();
}