不带头节点的链表与带了头节点的链表

来源豆包不带头节点第一个节点就是存数据的有效节点链表头直接指向它带头节点多一个不存有效数据的头节点链表头永远指向这个空节点真正的数据节点从头节点的next开始。#include stdio.h #include stdlib.h #define ERROR NULL typedef int ElementType; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; Position Find( List L, ElementType X ); List Insert( List L, ElementType X, Position P ); List Delete( List L, Position P ); int main() { List L; ElementType X; Position P, tmp; int N; L NULL; //可知这是一个没有头节点的链表 scanf(%d, N); 6 while ( N-- ) { scanf(%d, X); 12 2 4 87 10 2 L Insert(L, X, L); //不带头节点头指针为NULL插入第一个节点时必须单独判断head NULL然后赋值头指针 if ( LERROR ) printf(Wrong Answer\n); } scanf(%d, N); 4 while ( N-- ) { scanf(%d, X); 2 12 87 5 P Find(L, X); if ( P ERROR ) printf(Finding Error: %d is not in.\n, X); else { L Delete(L, P); printf(%d is found and deleted.\n, X); if ( LERROR ) printf(Wrong Answer or Empty List.\n); } } L Insert(L, X, NULL); if ( LERROR ) printf(Wrong Answer\n); else printf(%d is inserted as the last element.\n, X); P (Position)malloc(sizeof(struct LNode)); tmp Insert(L, X, P); if ( tmp!ERROR ) printf(Wrong Answer\n); tmp Delete(L, P); if ( tmp!ERROR ) printf(Wrong Answer\n); for ( PL; P; P P-Next ) printf(%d , P-Data); return 0; } /* 你的代码将被嵌在这里 */ Position Find( List L, ElementType X ) { Position pL; while(p!NULLp-Data!X){ pp-Next; } return p; } List Insert( List L, ElementType X, Position P ){ Position newnode(Position)malloc(sizeof(struct LNode)); if(newnodeNULL){ return ERROR; } newnode-DataX; if(PL||LNULL){ //当链表为空或需要在首位插入时应给头节点赋值并返回新的头节点。 newnode-NextL; return newnode; } Position preL; //寻找要插入的位置的前一个位置 while(pre!NULLpre-Next!P){ prepre-Next; } if(preNULL){ //如果没找到则说明位置不合法应释放掉newnode free(newnode); printf(Wrong Position for Insertion\n); return ERROR; } newnode-NextP; pre-Nextnewnode; return L; } List Delete( List L, Position P ){ if(PNULL||LNULL){ //如果是空表或是链表没有此位置 printf(Wrong Position for Deletion\n); return ERROR; } if(PL){ //如果是删除第一个数还需将头节点换到第二位。不带头节点必须修改链表头指针指向第二个节点特殊处理 Position newnodeL-Next; free(P); return newnode; } Position preL; //寻找要删除的数的前一位 while(pre!NULLpre-Next!P){ prepre-Next; } if(preNULL){ printf(Wrong Position for Deletion\n); return ERROR; } pre-NextP-Next; free(P); return L; }带头节点的链表#include stdio.h #include stdlib.h #define ERROR NULL typedef enum {false, true} bool; typedef int ElementType; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool Delete( List L, Position P ); int main() { List L; ElementType X; Position P; int N; bool flag; L MakeEmpty(); scanf(%d, N); 6 while ( N-- ) { scanf(%d, X); 12 2 4 87 10 2 flag Insert(L, X, L-Next); //可知这是一个有头节点的链表。带头节点直接修改头节点的 next 指针和在链表中间插入的逻辑完全一样无特殊处理。 if ( flagfalse ) printf(Wrong Answer\n); } scanf(%d, N); 4 while ( N-- ) { scanf(%d, X); 2 12 87 5 P Find(L, X); if ( P ERROR ) printf(Finding Error: %d is not in.\n, X); else { flag Delete(L, P); printf(%d is found and deleted.\n, X); if ( flagfalse ) printf(Wrong Answer.\n); } } flag Insert(L, X, NULL); if ( flagfalse ) printf(Wrong Answer\n); else printf(%d is inserted as the last element.\n, X); P (Position)malloc(sizeof(struct LNode)); flag Insert(L, X, P); if ( flagtrue ) printf(Wrong Answer\n); flag Delete(L, P); if ( flagtrue ) printf(Wrong Answer\n); for ( PL-Next; P; P P-Next ) printf(%d , P-Data); return 0; } /* 你的代码将被嵌在这里 */ List MakeEmpty(){ //初始化时应创建头节点head,并将head-next赋值NULL List head(List)malloc(sizeof(struct LNode)); head-NextNULL; return head; } Position Find( List L, ElementType X ){ Position PL-Next; while(P!NULLP-Data!X){ PP-Next; } if(PNULL){ return ERROR; } return P; } bool Insert( List L, ElementType X, Position P ){ Position PreL; while(Pre!NULLPre-Next!P){ PrePre-Next; } if(PreNULL){ printf(Wrong Position for Insertion\n); return false; } Position newnode(Position)malloc(sizeof(struct LNode)); newnode-DataX; newnode-NextPre-Next; Pre-Nextnewnode; return true; } bool Delete( List L, Position P ){ if(PNULL){ printf(Wrong Position for Deletion\n); return false; } Position preL; while(pre!NULLpre-Next!P){ prepre-Next; } if(preNULL){ printf(Wrong Position for Deletion\n); return false; } pre-NextP-Next; free(P); return true; }来源豆包带头节点链表 vs 不带头节点链表核心优势核心结论带头节点最大的优势是统一了链表的操作逻辑消除了边界情况的特殊处理代码更简洁、更安全、更易维护。下面用最直观的对比讲清楚优势1. 统一「插入 / 删除」操作不用特殊处理「第一个节点」这是最核心的优势直接看对比场景 1在链表头部插入新节点不带头节点必须修改链表的头指针让头直接指向新节点这是特殊情况带头节点直接修改头节点的 next 指针和在链表中间插入的逻辑完全一样无特殊处理。场景 2删除第一个有效节点不带头节点必须修改链表头指针指向第二个节点特殊处理带头节点直接修改头节点的 next 指针和删除中间节点逻辑一致。2. 空链表时操作逻辑完全统一空链表没有任何有效数据是最容易出 bug 的边界场景不带头节点头指针为NULL插入第一个节点时必须单独判断head NULL然后赋值头指针带头节点头节点永远存在空链表只是head-next NULL插入第一个节点和普通插入逻辑一模一样不用额外判断。3. 统一「前驱节点」的操作链表的插入 / 删除核心都需要找到当前节点的前驱节点不带头节点第一个节点没有前驱必须单独写代码处理带头节点所有有效节点都有前驱节点第一个有效节点的前驱就是头节点一套逻辑遍历全链表无例外。