您好,登錄后才能下訂單哦!
一、基礎(chǔ)知識(shí):鏈表(線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))
(1)特點(diǎn):邏輯關(guān)系相鄰,物理位置不一定相鄰。
(2)分類:
a.不帶頭節(jié)點(diǎn)
b.帶頭節(jié)點(diǎn)
(3)單鏈表的存儲(chǔ)結(jié)構(gòu):
typedef struct SListNode { DataType data; struct SListNode* next; }SListNode;
二、代碼實(shí)現(xiàn)(因避開(kāi)使用二級(jí)指針,所以代碼中使用了c++中的引用):此處構(gòu)造的為不帶頭節(jié)點(diǎn)的鏈表
(1)sList.h
#pragma once typedef int DataType; typedef struct SListNode { DataType data; struct SListNode* next; }SListNode; void PushBack(SListNode* & pHead, DataType d); void PopBack(SListNode* & pHead); void PushFront(SListNode* & pHead, DataType d); void PopFront(SListNode* & pHead); void PrintList(SListNode* pHead); SListNode* Find(SListNode* & pHead, DataType d); void Insert(SListNode* & pos, DataType d);
(2)sList.cpp
#include <stdio.h> #include <malloc.h> #include <assert.h> #include "sList.h" SListNode* MakeNode(DataType d) { SListNode* tmp = (SListNode*)malloc(sizeof(SListNode)); tmp->data = d; tmp->next = NULL; return tmp; } void PushBack(SListNode* & pHead, DataType d) { //1.空 //2.不空 if(pHead == NULL) { pHead = MakeNode(d); } else { //先找尾,再插入新節(jié)點(diǎn) SListNode* tail = pHead; while(tail->next != NULL) { tail = tail->next; } tail->next = MakeNode(d); } } void PopBack(SListNode* & pHead) { //1.空 //2.一個(gè)節(jié)點(diǎn) //3.多個(gè)節(jié)點(diǎn) if(pHead == NULL) { return; } else if (pHead->next == NULL) { free(pHead); pHead = NULL; } else { SListNode* tail = pHead; SListNode* prev = NULL; while(tail->next != NULL) { prev = tail; tail = tail->next; } prev->next = NULL; free(tail); } } void PushFront(SListNode* & pHead, DataType d) { if(pHead == NULL) { pHead = MakeNode(d); } else { SListNode* tmp = pHead; pHead = MakeNode(d); pHead->next = tmp; } } void PopFront(SListNode* & pHead) { if(!pHead) { printf("List is empty!"); return; } else { SListNode* tmp = pHead; pHead = pHead->next; free(tmp); } } SListNode* Find(SListNode* & pHead, DataType d) { SListNode* find = pHead; while(find) { if(find->data == d) return find; find = find->next; } return NULL; } void Insert(SListNode* & pos, DataType d) { assert(pos); /* 方法一: SListNode* tmp = MakeNode(d); tmp->next = pos->next; pos->next = tmp; */ //方法二: SListNode* next = pos->next; pos->next = MakeNode(d); pos->next->next = next; } void Erase(SListNode*& pHead,SListNode* & pos) { assert(pos&&pHead); SListNode* prev = pHead; while(prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } void PrintList(SListNode* pHead) { SListNode* tmp = pHead; while(tmp) { printf("%d->", tmp->data); tmp = tmp->next; } printf("NULL\n");
(3)test.cpp
#include "sList.h" #include <stdio.h> #include <stdlib.h> void test1() { //不帶頭節(jié)點(diǎn) SListNode* list = NULL; PushBack(list, 1); PushBack(list, 2); PushBack(list, 3); PushBack(list, 4); // PushFront(list,0); // PopFront(list); // PopBack(list); SListNode* ret = Find(list, 2); if(ret == NULL) { printf("No Exist!\n"); return; } // Insert(ret, 4); Erase(list,ret); PrintList(list); } int main() { test1(); system("pause"); return 0;
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。