題目描述
已知有一個亂序的字符序列L，序列中的字符可能是英文字母、數字字符或其它字符，字符的個數未知，每個字符之間用空格分開。字符序列用“-1”作為輸入結束標志，這里你要把-1當做一個字串對待，并且不算作字符序列中的元素。如下即為一個合法的字符序列：“a c 3 b a d 6 , & j m 8 7 2 V -1”。你的任務是將這個字符序列拆分為三個獨立的序列A、B和C，其中序列A存放序列L中的字母，序列B存放序列L中的數字，序列C存放序列L中的其他字符，然后，將序列A、B和C分別按照ASCII碼的大小關系進行升序排序。最終序列L將變為空序列。
要求：
建立四個單鏈表，分別存盤序列L、A、B、C中的元素。字符序列的輸入用“-1”作為結束標志。建立鏈表L時，建議使用scanf(“%s”,s);來讀取字符序列中的字符，即把單獨的字符看做一個字串讀取。當L建立后，你要按照問題描述中所述，將L拆分為A、B、C三個鏈表，然后對每個鏈表都進行排序，這部分的操作都應該是對指標進行修改，而不是洗掉節點與建立新節點。在程式結束前要釋放鏈表A、B、C中的所有節點。
Sample 1:
a c 3 b a d 6 , & j m 8 7 2 V -1
Sample 2:
z m v 1 a K 2 m p 9 a 0 a d -1
輸出
Sample 1:
The list A is: V a a b c d j m
The list B is: 2 3 6 7 8
The list C is: & ,
Sample 2:
The list A is: K a a a d m m p v z
The list B is: 0 1 2 9
There is no item in C list.
uj5u.com熱心網友回復：
我的代碼：/*問題 B: 實驗11_15_拆分鏈表*/
#include<stdio.h>
#include<stdlib.h>
typedef struct byte{
char data;
struct byte *nextPtr;
}ITEM;
ITEM* build(void);
void destroy(ITEM* headPtr);
void change(ITEM*headPtr);
void break1(ITEM*headPtr,ITEM*aPtr,ITEM*bPtr,ITEM*cPtr,ITEM**aPtrPtr,ITEM**bPtrPtr,ITEM**cPtrPtr);
void print(ITEM* headPtr);
int main(void){
ITEM*headPtr,*aPtr,*bPtr,*cPtr;
ITEM**aPtrPtr,**bPtrPtr,**cPtrPtr;
headPtr=build();
aPtr=(ITEM*)malloc(sizeof(ITEM));
aPtr->nextPtr=NULL;
aPtrPtr = &aPtr;
bPtr=(ITEM*)malloc(sizeof(ITEM));
bPtr->nextPtr=NULL;
bPtrPtr = &bPtr;
cPtr=(ITEM*)malloc(sizeof(ITEM));
cPtr->nextPtr=NULL;
cPtrPtr = &cPtr;
break1(headPtr,aPtr,bPtr,cPtr,aPtrPtr,bPtrPtr,cPtrPtr);
change(aPtr);change(bPtr);change(cPtr);
if(aPtr){
printf("The list A is: ");
print(aPtr->nextPtr);
printf("\n");
}
else
printf("There is no item in A list.\n") ;
if(bPtr){
printf("The list B is: ");
print(bPtr->nextPtr);
printf("\n");
}
else
printf("There is no item in B list.\n");
if(cPtr){
printf("The list C is: ");
print(cPtr->nextPtr);
}
else
printf("There is no item in C list.");
destroy(headPtr);
destroy(aPtr);
destroy(bPtr);
destroy(cPtr);
aPtrPtr=NULL;
bPtrPtr=NULL;
cPtrPtr=NULL;
}
//創建鏈表函式
ITEM*build(void){
ITEM*head=NULL,*current,*pre=NULL;
char n;
scanf("%c",&n);
while((int)n!=45){//判斷是不是-1
current=(ITEM*)malloc(sizeof(ITEM));
current->data=https://bbs.csdn.net/topics/n;
if(!head)
head=pre=current;
else{
pre->nextPtr=current;
pre=current;
}
scanf("%c",&n);
}
pre->nextPtr=NULL;
return head;
}
//釋放鏈表函式
void destroy(ITEM *headPtr){
ITEM*tempPtr;
while(headPtr){
tempPtr=headPtr;
headPtr = headPtr->nextPtr;
free(tempPtr);
}
}
//鏈表排序函式
void change(ITEM*headPtr){
char min,a;
ITEM* currentPtr=headPtr,*tempPtr,*minPtr;
while(currentPtr){
tempPtr=currentPtr;//記錄當前位置
min=currentPtr->data ;
minPtr=currentPtr;//初始化最小值，指向最小值的指標
while(tempPtr){
if(tempPtr->data < min){
min=tempPtr->data ;
minPtr=tempPtr;
}
tempPtr=tempPtr->nextPtr ;
} //找出current及后續鏈表中的最小值與其指標
a=currentPtr->data ;
currentPtr->data =min;
minPtr->data =a;//將最小值與current中的值交換
currentPtr=currentPtr->nextPtr ;//current跳到下一鏈表
}
minPtr=NULL;
tempPtr=NULL;
}
//分割鏈表函式
void break1(ITEM*headPtr,ITEM*aPtr,ITEM*bPtr,ITEM*cPtr,ITEM**aPtrPtr,ITEM**bPtrPtr,ITEM**cPtrPtr){
ITEM*aCurrent=aPtr,*bCurrent=bPtr,*cCurrent=cPtr,*current=headPtr,*temp;
char n;
int flaga=0,flagb=0,flagc=0;//用來判斷a，b，c鏈表是否為空，為空就將其頭指標設為NULL
while(current){
temp=current;//記錄current指標
n=current->data;//記錄current 所指向的值
current=current->nextPtr;//current指向下一個鏈表
if((n>='a'&&n<='z')||(n>='A')&&(n<='Z')&&n!=' '){
temp->nextPtr=NULL;
aCurrent->nextPtr=temp;
aCurrent=temp;
flaga=1;
} //判斷是否為字母，是就將其接到a鏈表后面
else if(n>='0'&&n<='9'&&n!=' '){
temp->nextPtr=NULL;
bCurrent->nextPtr=temp;
bCurrent=temp;
flagb=1;
}
else if(n==' ')
continue;//如果為空格就跳過
else{
temp->nextPtr=NULL;
cCurrent->nextPtr=temp;
cCurrent=temp;
flagc=1;
}
}
if(flaga==0)
*aPtrPtr=NULL;
if(flagb==0)
*bPtrPtr=NULL;
if(flagc==0)
*cPtrPtr=NULL;//判斷a，b，c是否為空
aCurrent=bCurrent=cCurrent=current=temp=NULL;
}
void print(ITEM*headPtr){
while(headPtr){
printf("%c ",headPtr->data);
headPtr=headPtr->nextPtr;
}
}
uj5u.com熱心網友回復：
結果是運行錯誤
uj5u.com熱心網友回復：
問題大概出在分離函式上
uj5u.com熱心網友回復：
分割完成之后，headPtr實際上已經是空的了但是headPtr并沒有被設定為NULL
destroy(headPtr); 就出錯了
實際上，注釋掉它就完事了
//destroy(headPtr);
你的代碼還有疑問的地方
1 判斷是否結束的條件不合理， 遇到 - 字符就認為結束， 但是輸入的并一定是-1啊， 也許單獨輸入一個-呢
2 if(
(n>='a'&&n<='z') ||
(n>='A') &&
(n<='Z') &&
n!=' '
) 這個條件很奇怪的，也許是沒有是沒理解你的意圖
uj5u.com熱心網友回復：
你是說在分割后把headptr設為null，然后就不用destroy（headptr）了嗎。我試了一下還是不對
uj5u.com熱心網友回復：
break1之后， headptr里面就不應該還有東西了主函式呼叫break1之后， headptr是否改為NULL都無所謂，只要不用它就對了
你可以直接注釋掉destory（headptr) 那就可以
至少你最初貼上的代碼是這樣，要是你改了別的地方，那就沒準了
a c 3 b a d 6 , & j m 8 7 2 V -1
The list A is: V a a b c d j m
The list B is: 2 3 6 7 8
The list C is: & , Program ended with exit code: 0
uj5u.com熱心網友回復：
謝謝你，問題已經解決，出錯在build函式上。應該初始化pre為null，同時在末尾增加if（pre）以保證不會在pre為null時再讓pre—>nextptr為null
uj5u.com熱心網友回復：
暈了， 沒覺得build函式有問題啊ITEM*build(void){
ITEM*head=NULL,*current,*pre=NULL;// 這已經是NULL了啊
char n;
scanf("%c",&n);
while((int)n!=45){//判斷是不是-1
current=(ITEM*)malloc(sizeof(ITEM));
current->data=https://bbs.csdn.net/topics/n;
if(!head)
head=pre=current;//何況還有這個
else{
pre->nextPtr=current;
pre=current;
}
scanf("%c",&n);
}
pre->nextPtr=NULL; // 除非build的時候輸入就是一個-1 開頭，否則到這里pre都不會是NULL
return head;
}
uj5u.com熱心網友回復：
當輸入的第一個值是—1，build函式將—1讀入n，while回圈就不會進入，pre不會被賦值仍然是null，這樣再讓pre—>nextptr為null就會出錯，因為pre本身就是null，就像沒有爸爸，哪來的兒子一樣。所以在pre—>next ptr=null前面加一個判斷if（pre）就行了
uj5u.com熱心網友回復：
知道你說的這個意思， 所以才在哪個標注了; // 除非build的時候輸入就是一個-1 開頭但是，這個和前面的釋放有個球關系？！
那個釋放出現問題的原因是 headptr對應的串列已經空了， 還去destory（headptr)
測驗的例子也不是-開頭的輸入
如果按照原題要求，肯定是不可以的， build里面的遇到-就結束的做法是不符合要求的
題目的本意不是讓一個一個char的獲得字符判斷，實際上是用scanf %s 一個字串一個字串的提取并判斷
scanf遇到空格自然回傳了%s， 通過strcmp獲得字串和"-1"來判定輸入的結束的
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/118703.html
標籤：新手樂園
上一篇：c語言資料結構