人防工程做資料的網(wǎng)站sem托管公司
1. 雙向鏈表的結(jié)構(gòu)
注意:這里的“帶頭”跟單鏈表的“頭結(jié)點”是兩個概念,實際上在單鏈表階段稱呼不太嚴(yán)謹(jǐn),但是為了更好地理解就直接稱為單鏈表的頭結(jié)點。帶頭鏈表里的頭結(jié)點,實際為“哨兵位”,哨兵位結(jié)點不存儲任何有效元素,只是站在這里“放哨的”。
“哨兵位”存在的意義:
遍歷循環(huán)鏈表避免死循環(huán)。
2. 雙向鏈表的實現(xiàn)
2.1 雙向鏈表結(jié)構(gòu)體
typedef int LTDataType;
// 定義雙向鏈表節(jié)點的結(jié)構(gòu)
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
2.2 申請結(jié)點
// 申請節(jié)點
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
2.3 初始化
// 初始化
void LTInit(LTNode** pphead)
{// 給鏈表創(chuàng)建一個哨兵位*pphead = LTBuyNode(-1);
}
2.4 鏈表的銷毀
// 銷毀
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}// 此時pcur指向phead,而phead還沒有被銷毀free(phead);phead = NULL;
}
2.5 鏈表的打印
// 打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
2.6 鏈表的尾插
// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 舊的尾結(jié)點就是phead->prev// 先讓新的尾結(jié)點的前指針指向舊的尾結(jié)點newNode->prev = phead->prev;newNode->next = phead; // 再讓新的尾結(jié)點的下一級指針指向頭結(jié)點(哨兵位)// 舊的尾結(jié)點下一級指針指向新的尾結(jié)點phead->prev->next = newNode;phead->prev = newNode; // 再讓頭結(jié)點(哨兵位)的下一級指針指向新的尾結(jié)點
}
2.7 鏈表的頭插
// 頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 要改變的結(jié)點:phead newNode phead->nextnewNode->next = phead->next; // 先讓新的尾結(jié)點的下一級指針指向頭結(jié)點的下一級指針的結(jié)點newNode->prev = phead; // 讓新的尾結(jié)點的前指針指向頭結(jié)點//phead->next->prev = newNode; // 指向頭結(jié)點的下一級指針的結(jié)點的下一級指針指向新的結(jié)點//phead->next = newNode; // 頭結(jié)點的下一級指針指向新的結(jié)點// 這樣也是可行的phead->next = newNode; // 頭結(jié)點的下一級指針指向新的結(jié)點newNode->next->prev = newNode; // 指向頭結(jié)點的下一級指針的結(jié)點的下一級指針指向新的結(jié)點}
2.8 鏈表的尾刪
// 尾刪
void LTPopBack(LTNode* phead)
{// 鏈表必須有效且鏈表不能為空(只有一個哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;// 影響的指針:phead del->prev deldel->prev->next = phead;phead->prev = del->prev;// 刪除del節(jié)點free(del);del = NULL;
}
2.9 鏈表的頭刪
// 頭刪
void LTPopFront(LTNode* phead)
{// 鏈表必須有效且鏈表不能為空(只有一個哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->next;// 影響的指針:phead del del->nextphead->next = del->next;del->next->prev = phead;// 刪除del節(jié)點free(del);del = NULL;
}
2.10 鏈表查找數(shù)據(jù)
// 查找數(shù)據(jù)
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}// 沒有找到return NULL;
}
2.11?在pos位置之后插入數(shù)據(jù)
// 在 pos 位置之后插入數(shù)據(jù)
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = LTBuyNode(x);// 影響的指針:pos newNode pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}
2.12 刪除pos結(jié)點
// 刪除 pos節(jié)點
void LTErase(LTNode* pos)
{// pos理論上來說不能為phead,但是沒有參數(shù)phead,無法增加校驗assert(pos);// 影響的指針:pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}