單鏈錶結點删除

稚幻君 2021-08-15 22:20:33 阅读数:839

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

單鏈錶結點删除

本題要求實現兩個函數,分別將讀入的數據存儲為單鏈錶、將鏈錶中所有存儲了某給定值的結點删除。鏈錶結點定義如下:

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

函數接口定義:

struct ListNode *readlist();
struct ListNode *deletem( struct ListNode *L, int m );

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

函數deletem將單鏈錶L中所有存儲了m的結點删除。返回指向結果鏈錶頭結點的指針。

裁判測試程序樣例:

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

輸入樣例:

10 11 10 12 10 -1
10
結尾無空行

輸出樣例:

11 12
結尾無空行

我的思路

先弄兩個指針,讓其中的p指向鏈錶頭,q置為NULL(q指向的是p的上一個節點)。然後弄個循環不斷地判斷 移動 判斷,在程序裏面有好幾個容易出錯的地方,首先一定要判斷q是否為空,為什麼要判斷 p 呢!因為我們要删的數可能在第一個節點,在第一個節點的話我們無法將p賦值給q,如果在這裏把p賦給q的話(p將指向下一節點),就會跳過q(賦值後的)指向的節點的判斷(判斷是否是m),還有一個要注意的是如果q為空,我們一定要移動鏈錶的頭結點 L,使 L 指向下一節點。

代碼

struct ListNode* readlist()
{
struct ListNode* head = NULL, * p = NULL, * last=NULL;
int number;
last = head;
do
{
scanf("%d", &number); //輸入值
if (number != -1) //等於 -1 跳出循環
{
p = (struct ListNode*)malloc(sizeof(struct ListNode)); //為節點開辟空間
p->data = number; //給節點賦值
p->next = NULL; //將節點指向的比特置 設置成NULL
if (last==NULL) //判斷是否有 頭結點
{
head = p;
}
else
last->next = p; //連接新節點p
last = p; //last指向新的鏈尾
}
else
break;
} while (number != -1);
return head; //返回鏈錶的頭節點
}
struct ListNode* deletem(struct ListNode* L, int m){
struct ListNode* p = L, * q = NULL;
while(p) { //判斷是否到達鏈尾
if (p->data == m) { //若節點的值等於 m
if (q) { //判斷 q 是否為空
q->next = p->next;//保存 p 指向下一節點的指針 其實就是把 p->next 指向的節點和 q 節點鏈起來
free(p); //釋放內存
p = q->next; //因為釋放內存後 p的指向改變了 需要重新設置 不能直接讓p指向下一個節點
}
else {
L = p->next; // q為空 代錶鏈錶的第一個節點的值等於m 是要删除的節點 。需要移動鏈錶的頭結點,不然的話 L 將指向一個奇怪的地方。
free(p); //釋放內存
p = L; //釋放內存後 p的指向改變了 讓 p 指向新的鏈錶頭
}
}
else {
q = p; //移動節點
p = p->next;
}
}
return L; //返回鏈錶的頭節點
}

加油啊!

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