【C语言】链表及单链表基本操作

1、什么是链表？链表的分类？

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

数据结构中：

2、链表的分类

共有8种链表结构

3、单链表的基本操作

类似于顺序表，我们来实现单链表的基本操作，具体见SList.h 代码中语句及注释。

#pragma once
typedef int SDataType;
//链表的节点
typedef struct SListNode
{
 SDataType _data;
 struct SListNode* _PNext;
}Node,*PNode;

typedef struct SList       //封装了链表的结构
{
 PNode _pHead;//指向链表第一个节点
}SList;

void SListInit(SList*s);//链表的初始化

//在链表s最后一个节点后插入一个值为data的节点
void SListPushBack(SList* s, SDataType data);

//删除链表s最后一个节点
void SListPopBack(SList* s);

//在链表s第一个节点前插入值为data的节点
void SListPushFront(SList* s, SDataType data);

//删除链表s的第一个节点
void SListPopFront(SList* s);

//在链表的pos位置后插入值为data的节点
void SListInsert(PNode pos, SDataType data);

//删除链表s中pos位置的节点
void SListErase(SList* s, PNode pos);

// 在链表中查找值为data的节点，找到返回该节点的地址，否则返回NULL 
PNode SListFind(SList* s, SDataType data);

//移除链表中第一个值为data的元素
void SListRemove(SList*s, SDataType data);

// 获取链表中有效节点的个数 
int SListSize(SList* s);

// 检测链表是否为空 
int SListEmpty(SList* s);

// 将链表中有效节点清空 
void SListClear(SList* s);

// 销毁链表 
void SListDestroy(SList* s);
//打印链表
void SListPrint(SList* s);

以下为SList.c具体代码：

#include <stdio.h>
#include "Slist.h"
#include <assert.h>
#include <stdlib.h>
#include <stddef.h>

1.初始化部分，我们只需要将链表的头结点置为NULL即可。

void SListInit(SList*s) {
 assert(s);
 s->_pHead = NULL;
}

2.尾插，首先我们要创建一个新节点，然后判断链表当前是否有节点，若没有，则直接让第一个节点指向新节点，若有，找到最后一个节点，让他指向新节点。

void SListPushBack(SList* s, SDataType data) {
 //找链表最后一个节点
 assert(s);
 PNode pNewNode = BuySListNode(data);
 if (s->_pHead == NULL) {//链表没有节点的情况
  s->_pHead = pNewNode;
 }
 else {
  PNode pCur = s->_pHead;
  while (pCur->_PNext) {
   pCur = pCur->_PNext;
  }
  //让最后一个节点指向新节点
  pCur->_PNext = pNewNode;
 }
}

3.尾删，首先判断链表中有没有节点，若没有，直接返回，若有一个节点，直接让第一个节点指向NULL，若有多个节点，则需要记录下倒数第二个节点，让它指向NULL。

void SListPopBack(SList* s) {
 assert(s);
 if (s->_pHead == NULL) {//链表中没有节点
  return;
 }
 else if (s->_pHead->_PNext == NULL) {//只有一个节点
  free(s->_pHead);
  s->_pHead = NULL;
 }
 else {                           //多个节点
  PNode pCur = s->_pHead;
  PNode pPre = NULL;
  while (pCur->_PNext) {
   pPre = pCur;
   pCur = pCur->_PNext;
  }
  free(pCur);
  pPre->_PNext = NULL;
 }
}

4.头插

void SListPushFront(SList* s, SDataType data) {
 assert(s);
 PNode pNewNode = BuySListNode(data);
 if (s->_pHead == NULL) {//链表为空
  s->_pHead = pNewNode;
 }
 else {
  pNewNode->_PNext = s->_pHead;
  s->_pHead = pNewNode;
 }
}

5.头删

void SListPopFront(SList* s) {
 assert(s);
 if (s->_pHead == NULL) {//链表为空
  return;
 }
 else if (s->_pHead->_PNext == NULL) {//只有一个节点
  free(s->_pHead);
  s->_pHead = NULL;
 }
 else {
  PNode pCur = s->_pHead;
  s->_pHead = pCur->_PNext;
  free(pCur);
 }
}

6.在给定pos位置插入值为data的节点，分两步完成：首先找到pos位置的节点，然后再插入，所以要实现这一个功能需要两个函数来共同完成。

注意：应该先连接好新节点，再断开原来的指针指向。
插入：

void SListInsert(PNode pos, SDataType data) {
 PNode pNewNode = NULL;
 if (pos == NULL) {
  return;
 }
 pNewNode = BuySListNode(data);
 
 pNewNode->_PNext = pos->_PNext;
 pos->_PNext = pNewNode;
}

查找：

PNode SListFind(SList* s, SDataType data) {
 assert(s);
 PNode pCur = s->_pHead;
 while (pCur) {
  if (pCur->_data == data) {
   return pCur;
  }
  pCur = pCur->_PNext;
 }
 return NULL;
}

7.删除给定pos位置的节点。

void SListErase(SList* s, PNode pos) {
 assert(s);
 if (pos == NULL || s->_pHead == NULL) {
  return;
 }
 if (pos== s->_pHead) {
  s->_pHead = pos->_PNext;
 }
 else {
  PNode pPrePos = s->_pHead;
  while (pPrePos&&pPrePos->_PNext != pos) {
   pPrePos = pPrePos->_PNext;
  }
  pPrePos->_PNext = pos->_PNext;
 }
 free(pos);
}

8.删除第一个值为data的节点。要分三种情况：链表为空直接返回、要删除的节点为第一个节点、其它位置的节点。

void SListRemove(SList*s, SDataType data) {
 assert(s);
 if (s->_pHead == NULL) {
  return;
 }
 PNode pPre = NULL;
 PNode pCur = s->_pHead;
 while (pCur) {
  if (pCur->_data == data) {
   if (pCur == s->_pHead) {         //要删除的是第一个位置的节点
    s->_pHead = pCur->_PNext;
   }
   else {
    pPre->_PNext = pCur->_PNext;      //其它位置的情况，让前一个节点指向其后一个节点
   }
   free(pCur);
   return;
  }
  else {
   pPre = pCur;
   pCur = pCur->_PNext;
  }
 }
}

其它：

int SListSize(SList* s) {            //获取链表有效节点的个数
 assert(s);
 int count = 0;
 PNode pCur = s->_pHead;
 while (pCur) {
  count++;
  pCur = pCur->_PNext;
 }
 return count;
}

int SListEmpty(SList* s) {              //检测链表是否为空
 assert(s);
 if (s->_pHead == NULL) {
  return -1;
 }
 return 0;
}

void SListClear(SList* s) {             //清空链表
 assert(s);
 if (s->_pHead == NULL) {
  return;
 }
 PNode pCur = s->_pHead;
 while (pCur->_PNext) {    //循环清空链表中的节点
  PNode Tmp = pCur->_PNext;
  free(pCur);
  pCur = Tmp;
 }
 if (pCur) {      //清空最后一个节点
  free(pCur);
  pCur = NULL;
 }
}

void SListDestroy(SList* s) {            //销毁链表
 assert(s);
 if (s->_pHead == NULL) {
  free(s->_pHead);
  return;
 }
 while (s->_pHead) {    
  PNode Tmp = s->_pHead->_PNext;
  free(s->_pHead);
  s->_pHead = Tmp;
 }
}

void SListPrint(SList* s) {             //打印链表
 assert(s);
 PNode pCur = s->_pHead;
 while (pCur) {
  printf("%d--->", pCur->_data);
  pCur = pCur->_PNext;
 }
 printf("\n");
}
void main() {
 SList s;
 SListInit(&s);
 SListPushBack(&s, 1);
 SListPushBack(&s, 2);
 SListPushBack(&s, 3);
 printf("size=%d\n", SListSize(&s));
 SListPrint(&s);
 SListInsert(SListFind(&s, 2), 0);
 SListPrint(&s);
 SListRemove(&s, 2);
 SListPrint(&s);
  system("pause");
 return;
}

运行结果：