用C语言实现基础单链表
结构体
首先,我们定义一个结构体Node
typedef int DataType; typedef struct Node { int data; struct Node* next; }Node,*PNode;
Node这个结构体中,包含一个数据元素,和一个指向下一个节点的指针
初始化链表
void InitList(PNode* pHead) { *pHead = NULL; }
申请一个新的节点
PNode BuyNewNode(DataType data) { PNode New = NULL; New = (PNode)malloc(sizeof(Node)); New->data = data; New->next = NULL; return New; }
打印链表
void PrintList(PNode pHead) { PNode Cur = pHead; while (Cur) { printf("%d ",Cur->data); Cur = Cur->next; } printf("\n"); }
尾插一个节点
void PushBack(PNode* pHead,DataType data) { assert(pHead!=NULL); PNode Cur = NULL; PNode NewNode = BuyNewNode(data); Cur = *pHead; if (*pHead == NULL) { *pHead = NewNode; } else { while (Cur->next) { Cur = Cur->next; } Cur->next = NewNode; } }
前插一个节点
void PushFront(PNode* pHead,DataType data) { assert(pHead != NULL); PNode Cur = *pHead; PNode NewNode = BuyNewNode(data); if (*pHead == NULL) { *pHead = NewNode; } else { NewNode->next = *pHead; *pHead = NewNode; } }
从尾部删除一个节点
void PopBack(PNode* pHead) { assert(pHead!=NULL); PNode Cur = *pHead; PNode DelNode = NULL; if (*pHead == NULL) { return; } if (Cur->next == NULL) { free(Cur); *pHead = NULL; } while (Cur->next->next != NULL) { Cur = Cur->next; } //Cur->next = NULL; DelNode = Cur->next; free(DelNode); //free(*(Cur->next)); DelNode = NULL; Cur->next = NULL; }
从前面删除一个节点
void PopFront(PNode* pHead) { assert(pHead!=NULL); if ((*pHead) == NULL)//无节点 { return; } else//有多个节点 { PNode Del = (*pHead)->next; //(*pHead) = (*pHead)->next; free((*pHead)->next); Del = NULL; } }
查找一个节点
PNode Find(PNode pHead,DataType data) { assert(pHead != NULL); PNode Cur = pHead; while (Cur != NULL) { if (Cur->data == data) { return Cur; } Cur = Cur->next; } return NULL; }
根据一个节点来插入一个节点
void Insert(PNode pos,DataType data) { assert(pos != NULL); PNode NewNode = BuyNewNode(data); if (pos->next == NULL) { pos->next = NewNode; } else { PNode Cur = pos->next; pos->next = NewNode; NewNode->next = Cur; } } // Insert(Find(&pHead,4),5);
销毁单链表
void Destroy(PNode* pHead) { PNode Node = (*pHead); PNode NodeNext = Node->next; while (NodeNext != NULL) { free(Node); Node = NodeNext; NodeNext = NodeNext->next; } free(Node); *pHead = NULL; Node = NULL; }
返回尾节点
PNode Back(PNode pHead) { //assert(pHead != NULL); PNode Cur = pHead; if (Cur == NULL) { return Cur; } while (Cur->next != NULL) { Cur = Cur->next; } return Cur; }
完整代码
头文件 SeqList.h
#ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include<stdlib.h> #include<assert.h> #include<stdio.h> #include<malloc.h> typedef int DataType; typedef struct Node { int data; struct Node* next; }Node,*PNode; void InitList(PNode* pHead); PNode BuyNewNode(DataType data); void PrintList(PNode pHead); void PushBack(PNode* pHead,DataType data); void PushFront(PNode* pHead,DataType data); void PopBack(PNode* pHead); void PopFront(PNode* pHead); PNode Find(PNode pHead,DataType data); void Insert(PNode pos,DataType data); void Destroy(PNode* pHead); PNode Back(PNode pHead); #endif __SEQLIST_H__
函数实现 SeqList.c
#include "SeqList.h" void InitList(PNode* pHead) { *pHead = NULL; } PNode BuyNewNode(DataType data) { PNode New = NULL; New = (PNode)malloc(sizeof(Node)); New->data = data; New->next = NULL; return New; } void PrintList(PNode pHead) { PNode Cur = pHead; while (Cur) { printf("%d ",Cur->data); Cur = Cur->next; } printf("\n"); } void PushBack(PNode* pHead,DataType data) { assert(pHead!=NULL); PNode Cur = NULL; PNode NewNode = BuyNewNode(data); Cur = *pHead; if (*pHead == NULL) { *pHead = NewNode; } else { while (Cur->next) { Cur = Cur->next; } Cur->next = NewNode; } } void PushFront(PNode* pHead,DataType data) { assert(pHead != NULL); PNode Cur = *pHead; PNode NewNode = BuyNewNode(data); if (*pHead == NULL) { *pHead = NewNode; } else { NewNode->next = *pHead; *pHead = NewNode; } } void PopBack(PNode* pHead) { assert(pHead!=NULL); PNode Cur = *pHead; PNode DelNode = NULL; if (*pHead == NULL) { return; } if (Cur->next == NULL) { free(Cur); *pHead = NULL; } while (Cur->next->next != NULL) { Cur = Cur->next; } //Cur->next = NULL; DelNode = Cur->next; free(DelNode); //free(*(Cur->next)); DelNode = NULL; Cur->next = NULL; } void PopFront(PNode* pHead) { assert(pHead!=NULL); if ((*pHead) == NULL)//无节点 { return; } else//有多个节点 { PNode Del = (*pHead)->next; //(*pHead) = (*pHead)->next; free((*pHead)->next); Del = NULL; } } PNode Find(PNode pHead,DataType data) { assert(pHead != NULL); PNode Cur = pHead; while (Cur != NULL) { if (Cur->data == data) { return Cur; } Cur = Cur->next; } return NULL; } void Insert(PNode pos,DataType data) { assert(pos != NULL); PNode NewNode = BuyNewNode(data); if (pos->next == NULL) { pos->next = NewNode; } else { PNode Cur = pos->next; pos->next = NewNode; NewNode->next = Cur; } } // Insert(Find(&pHead,5); void Destroy(PNode* pHead) { PNode Node = (*pHead); PNode NodeNext = Node->next; while (NodeNext != NULL) { free(Node); Node = NodeNext; NodeNext = NodeNext->next; } free(Node); *pHead = NULL; Node = NULL; } PNode Back(PNode pHead) { //assert(pHead != NULL); PNode Cur = pHead; if (Cur == NULL) { return Cur; } while (Cur->next != NULL) { Cur = Cur->next; } return Cur; }