奇數值結點鏈錶

稚幻君 2021-08-15 22:07:30 阅读数:900

本文一共[544]字,预计阅读时长:1分钟~

奇數值結點鏈錶

本題要求實現兩個函數,分別將讀入的數據存儲為單鏈錶、將鏈錶中奇數值的結點重新組成一個新的鏈錶。
鏈錶結點定義如下:

struct ListNode {
int data;
ListNode *next;
};

函數接口定義:

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );

函數readlist從標准輸入讀入一系列正整數,按照讀入順序建立單鏈錶。當讀到−1時錶示輸入結束,函數應返回指向單鏈錶頭結點的指針。

函數getodd將單鏈錶L中奇數值的結點分離出來,重新組成一個新的鏈錶。返回指向新鏈錶頭結點的指針,同時將L中存儲的地址改為删除了奇數值結點後的鏈錶的頭結點地址(所以要傳入L的指針)。

裁判測試程序樣例:

#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
void printlist( struct ListNode *L )
{
struct ListNode *p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
struct ListNode *L, *Odd;
L = readlist();
Odd = getodd(&L);
printlist(Odd);
printlist(L);
return 0;
}
/* 你的代碼將被嵌在這裏 */

代碼

我的思路
首先,判斷首個節點的奇偶。然後根據判斷的結果,在原鏈錶的基礎上創建一個奇數鏈錶。
呃·····
其實並沒有創建新的鏈錶,而是將原鏈錶中的偶數節點拽出來連在一起,將奇數節點拽出來連在一起,這樣一個原鏈錶就變成了兩個鏈錶,一個奇數鏈錶,一個偶數鏈錶。
在這裏插入圖片描述

創建鏈錶

//創建鏈錶
struct ListNode* readlist()
{
struct ListNode* head = NULL; //鏈錶的頭節點
struct ListNode* p = NULL; //創建新節點
struct ListNode* last = NULL; //用來移動 連接新節點
int number;
do
{
scanf("%d", &number); //輸入的值
if (number != -1)
{
p = (struct ListNode*)malloc(sizeof(struct ListNode)); // 為新節點開辟空間
p->data = number; //將number賦給新節點中的data
p->next = NULL; //將新節點下指向的地方設置為NULL
if (last == NULL) //設置頭結點
head = p;
else //
last->next = p; //p與鏈錶尾連接
last = p; //移動到新節點 成為新的鏈錶尾
}
else
break;
}while (number != -1);
return head;
}
//初始版
struct ListNode* getodd(struct ListNode** L)
{
struct ListNode* p, * q, * head, * odd, * even;
head = NULL; //奇數的頭
odd = NULL; //奇數節點
even = NULL; //偶數節點
p = *L; //第一個節點
q = NULL; //第一個的上一個節點
for (; p; q = p, p = p->next){
if (q){
if (p->data % 2 != 0){ //奇數
if (even) //看偶數鏈錶的首節點是否確定
{
if (odd==NULL) //看奇數鏈錶的首節點是否確定
{
head = p;
odd = head;
}
else
{
odd->next = p;
odd = odd->next;
}
}
else {
odd->next = p;
odd = odd->next;
*L = p->next;
}
}
else if(p->data % 2 == 0 ){//偶數
if (even){
even->next = p;
even = even->next;
}
else{/
even = *L;
}
}
}
else{//第一個節點的判斷 只進行一次
if (p->data % 2 != 0){ //為奇數
*L = p->next;//移動 *L 到下一個節點
head = p; //奇數鏈錶的頭
odd = p; //用來連接奇數節點
}
else {//偶數
even = *L; //偶數鏈錶的頭 *L
}
}
}
//將最後一個節點所指向的比特置設置為NULL
//如果最後一個數為偶數,那麼奇數鏈錶最後一個節點一定不為NULL;若為奇數,則偶數鏈錶最後一個節點一定不為NULL。
//if()的作用是判斷是否有奇數或者偶數,如果輸入的全為偶數,那麼奇數鏈錶就無法進行 odd->next = NULL ,因為 odd 本身就是NULL
if(even)
even->next = NULL;
if(odd)
odd->next = NULL;
return head;
}

改進後

這個其實和上面的那個代碼沒有太大的區別,唯一的區別就是它變短了。

 //改進版
struct ListNode* getodd(struct ListNode** L)
{
struct ListNode* p, * head, * odd, * even;
head = NULL; //奇數的頭
odd = NULL; //奇數節點
even = NULL; //偶數節點
for (p = *L; p; p = p->next) {
if (p->data % 2 == 0) { //偶數
if (even) { //看偶數鏈錶的首節點是否確定
even->next = p;
even = even->next;
}
else {
even = *L;
}
}
else { //奇數
if (odd) { //看奇數鏈錶的首節點是否確定
odd->next = p;
odd = odd->next;
if (even==NULL) //看偶數鏈錶的首節點是否確定 若不確定將 *L 往後挪一節點
*L = p->next;
}
else {
head = p; //奇數鏈錶的頭
odd = p; //奇數節點
if (even == NULL) //看偶數鏈錶的首節點是否確定 若不確定將 *L 往後挪一節點
*L = p->next;
}
}
}
//將最後一個節點所指向的比特置設置為NULL
//如果最後一個數為偶數,那麼奇數鏈錶最後一個節點一定不為NULL;若為奇數,則偶數鏈錶最後一個節點一定不為NULL。
//if()的作用是判斷是否有奇數或者偶數,如果輸入的全為偶數,那麼奇數鏈錶就無法進行 odd->next = NULL ,因為 odd 本身就是NULL
if (even)
even->next = NULL;
if (odd)
odd->next = NULL;
return head;
}

好累,但是不能停下,所以還是加油吧!

版权声明:本文为[稚幻君]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815220712922l.html