[c语言]单链表的实现
一、基础知识:链表(线性表的链式存储结构)
(1)特点:逻辑关系相邻,物理位置不一定相邻。
(2)分类:
a.不带头节点
b.带头节点
(3)单链表的存储结构:
typedef struct SListNode { DataType data; struct SListNode* next; }SListNode;
二、代码实现(因避开使用二级指针,所以代码中使用了c++中的引用):此处构造的为不带头节点的链表
(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 { //先找尾,再插入新节点 SListNode* tail = pHead; while(tail->next != NULL) { tail = tail->next; } tail->next = MakeNode(d); } } void PopBack(SListNode* & pHead) { //1.空 //2.一个节点 //3.多个节点 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() { //不带头节点 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;