数据结构---不带头结点的单项非循环链表

2024-02-24 12:44:28

因为顺序表的底层空间是连续的，所以如果对元素进行大量的任意位置添加或删除，在顺序表里就要移动大量的元素，效率很低，因此我们需要让元素存储在不连续的空间中，但如果直接存储，就不知道它的下一个元素是什么，这时就可以利用链表这个结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的链接次序实现（除了存储元素信息外，还要给下一个节点的位置）
找到第一个节点，就可以通过链式结构找到下一个节点
链表：
1.单链表（从前往后）、双链表（循环）
2.带头（链表中第一个节点的不存储有效数据）
不带头（一个节点存储有效数据）
3.循环、非循环

下面来实现下不带头结点的单项非循环链表

SList.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
//无头单项非循环
//不带头结点，第一个结点存的是有效元素
typedef int SDataType;
//节点的结构  
typedef struct SListNode
{
 SDataType _data;//保存数据
 struct SListNode* _pNext;//指向下一个 节点的地址
}Node;
//链表的结构
//把链表记录下来，只要知道头节点就行
typedef struct SList
{
 Node* _pHead;
}SList,*PSList;

void SListInit(PSList pl);//初始化
void SListDestory(PSList pl);//销毁

Node* BuySListNode(SDataType data);

void SListPushBack(PSList pl, SDataType data);//尾插
void SListPopBack(PSList pl);//尾删

void SListPushFront(PSList pl, SDataType data);//头插
void SListPopFront(PSList pl);//头删

Node* SListFind(PSList pl, SDataType data);//找位置
void SListInsert(PSList pl, Node* pos, SDataType data);//任意位置插入
void SListErase(PSList pl, Node* pos);//任意位置删除

void SListIsFindData(PSList pl, SDataType data);//检测data是否在链表中
void SListRemove(PSList pl, SDataType data);// 移除链表中第一个值为data的元素 
//void SListRemoveAll(PSList pl, SDataType data);// 移除链表中所有值为data的元素 

void SListSize(PSList pl);//// 获取链表有效元素个数 
void SListCapacity(PSList pl);// 获取链表的容量 
int SListEmpty(PSList pl);// 检测链表是否为空

SDataType SListFront(PSList pl);// 获取链表中第一个元素 
SDataType SListBack(PSList pl);// 获取链表中最后一个元素
///////////////////////////////////////////////////////
void PrintSList(PSList pl);
//////////////////////////////////
void SListTest();

SList.c文件

#include "SList.h"
void SListInit(PSList pl)//初始化
{
 assert(pl);
 pl->_pHead = NULL; 
}
Node* BuySListNode(SDataType data)//获取新结点
{
 Node* pNode = (Node*)malloc(sizeof(Node));
 if (pNode == NULL)
 {
  assert(0);
  return NULL;
 }
 pNode->_data = data;
 pNode->_pNext = NULL;
 return pNode;
}
void SListPushBack(PSList pl, SDataType data)//尾插
{
 Node* pNewNode = NULL;//新结点
 Node* pCur = NULL;//链表最后一个结点
 assert(pl);
 pNewNode = BuySListNode(data);
 pCur = pl->_pHead;
 //检测链表是否为空
 if (pl->_pHead == NULL)
  pl->_pHead = pNewNode;
 else
 {
  while (pCur->_pNext)
  {
   pCur = pCur->_pNext;
  }
  pCur->_pNext = pNewNode;
 }
}
void SListPopBack(PSList pl)//尾删
{
 //找链表中最后一个结点，保存前一个结点（或倒数第二个结点）  链表至少有两个结点
 assert(pl);
 if (pl->_pHead == NULL)
 {
  printf("空链表\n");
  return;
 }
 else if (pl->_pHead->_pNext == NULL)//有一个结点
 {
  free(pl->_pHead);
  pl->_pHead = NULL;
 }
 else//至少有两个结点
 {
  Node* pCur = pl->_pHead;
  Node* pre = NULL;
  while (pCur->_pNext)
  {
   pre = pCur;//保存pCur的前一个结点
   pCur = pCur->_pNext;
  }
  free(pCur);
  pre->_pNext = NULL;
 }
}
void SListPushFront(PSList pl, SDataType data)//头插
{
 Node* pNewNode = NULL;
 assert(pl);
 pNewNode = BuySListNode(data);
 pNewNode->_pNext = pl->_pHead;;
 pl->_pHead = pNewNode;
}
void SListPopFront(PSList pl)//头删
{
 assert(pl);
 if (pl->_pHead == NULL)//无结点
 {
  printf("空链表\n");
  return;
 }
 else
 {
  Node* DeleteNode = pl->_pHead;
  pl->_pHead = pl->_pHead->_pNext;
  free(DeleteNode);
 }
}
Node* SListFind(PSList pl, SDataType data)//找位置
{
 assert(pl);
 Node* pCur = pl->_pHead;
 while (pCur)
 {
  if (pCur->_data == data)
   return pCur;
  pCur = pCur->_pNext;
 }
 return NULL;
}
void SListInsert(PSList pl, Node* pos, SDataType data)//任意位置插入(插在后面)
{
 Node* pNewNode = NULL;
 assert(pl);
 pNewNode = BuySListNode(data);
 pNewNode->_pNext = pos->_pNext;
 pos->_pNext = pNewNode;
 printf("插入成功:");
}
void SListErase(PSList pl, Node* pos)//任意位置删除
{
 Node* prePos = NULL;
 assert(pl);
 if (pl->_pHead == NULL||pos==NULL)
 {
  printf("链表为空或位置，无法删除\n");
  return;
 }
 if (pos == pl->_pHead)//pos刚好在第一个结点的位置
  pl->_pHead = pos->_pNext;
 else
 {
  prePos = pl->_pHead;
  while (prePos->_pNext != pos)
  {
   prePos = prePos->_pNext;
  }
  prePos->_pNext = pos->_pNext;
 }
 free(pos);
 printf("删除成功:");
}
void SListIsFindData(PSList pl, SDataType data)//检测data是否是链表中
{
 assert(pl);
 Node* pCur = pl->_pHead;
 if (pl->_pHead == NULL)
 {
  printf("链表为空，无法检测");
  return;
 }
 while (pCur)
 {
  if (pCur->_data == data)
  {
   printf("%d在链表中", data);
   return;
  }
  pCur = pCur->_pNext;
 }
 printf("%d不在链表中",data);
 return;
}
void SListRemove(PSList pl, SDataType data)// 移除链表中第一个值为data的元素
{
 assert(pl);
 if (pl->_pHead == NULL)
 {
  printf("链表为空，无法移除元素\n");
  return;
 }
 Node* pCur = pl->_pHead;
 Node* pPre = NULL;//pCur前一个结点
 while (pCur->_pNext!=NULL)
 {
  while (pCur->_data != data)
  {
   if (pCur->_pNext == NULL)
   {
    printf("很遗憾，没有找到：");
    return;
   }
   pPre = pCur;
   pCur = pCur->_pNext;
  }
  if (pCur->_data==data)
  {
   if (pPre == NULL)
    pl->_pHead = pCur->_pNext;
   else
    pPre->_pNext = pCur->_pNext;
   free(pCur);
   pCur = NULL;
   printf("移除成功:   ");
   return;
  }
 } 
}
//void SListRemoveAll(PSList pl, SDataType data)// 移除链表中所有值为data的元素
//{
// assert(pl);
// if (pl->_pHead == NULL)
// {
//  printf("链表为空，无法移除元素\n");
//  return;
// }
// Node* pCur = pl->_pHead;
// Node* pPre = NULL;//pCur的前一个结点
// while (pCur->_pNext!=NULL)
// {
//  if (pCur->_data != data)
//  {
//   pPre = pCur;
//   pCur = pCur->_pNext;
//  }
//  else
//  {
//   if (pPre == NULL)
//    pl->_pHead = pCur->_pNext;
//   else
//    pPre->_pNext = pCur->_pNext;
//   free(pCur);
//   pCur = NULL; 
//  }
// }
//}
void SListSize(PSList pl)//// 获取链表有效元素个数 
{
 assert(pl);
 int count = 1;
 Node* pCur = pl->_pHead;
 while (pCur->_pNext)
 {
  if (pCur->_pNext)
   pCur = pCur->_pNext;
  count++;
 }
 printf("有效元素个数为:%d  :", count);
 return;
}
int SListEmpty(PSList pl)// 检测链表是否为空
{
 assert(pl);
 if (pl->_pHead)
 {
  printf("链表不为空：");
  return 0;
 }
 printf("链表为空：");
 return 0;
}
SDataType SListFront(PSList pl)// 获取链表中第一个元素 
{
 assert(pl);
 printf("链表中第一个元素为：%d:  ", pl->_pHead->_data);
 return pl->_pHead->_data;
}
SDataType SListBack(PSList pl)// 获取链表中最后一个元素
{
 assert(pl);
 Node* pCur = pl->_pHead;
 while (pCur->_pNext)
 {
  pCur = pCur->_pNext;
 }
 printf("链表中最后一个元素为:%d:   ", pCur->_data);
 return pCur->_data;
}
void SListDestory(PSList pl)//销毁
{ 
 Node* pCur = NULL;
 assert(pl);
 pCur = pl->_pHead;
 while (pCur)
 { 
  pl->_pHead = pCur->_pNext;//下个结点为第一个结点了
  free(pCur);
  pCur = pl->_pHead;
 }
 pl->_pHead = NULL;
 printf("销毁成功:");
}
//////////////////////////////////////
void PrintSList(PSList pl)
{
 Node* pCur = NULL;
 assert(pl);
 pCur = pl->_pHead;
 while (pCur)
 {
  printf("%d-->", pCur->_data);
  pCur = pCur->_pNext;
 }
 printf("NULL\n");
}

test.c文件

#include "SList.h"
int main()
{
  SList s;
  SListInit(&s);
  SListPushBack(&s, 0);//尾插
  SListPushBack(&s, 0);
  SListPushBack(&s, 1);
  SListPushBack(&s, 1);
  SListPushBack(&s, 2);
  SListPushBack(&s, 2);
  SListPushBack(&s, 4);
  SListPushBack(&s, 4);
  SListPushBack(&s, 5);
  SListPushBack(&s, 5);
  SListPushBack(&s, 7);
  SListPushBack(&s, 8);
  SListPushBack(&s, 9);
  SListPushBack(&s, 9);
  PrintSList(&s);
  
  SListPopBack(&s);//尾删
  PrintSList(&s);
  SListPushFront(&s, 0);//头插
  PrintSList(&s);
  SListPopFront(&s);//头删
  PrintSList(&s);
  
  //任意位置插入
  Node* ret = SListFind(&s, 2);//找位置
  SListInsert(&s, ret, 8);
  PrintSList(&s);
  
  //任意位置删除
  ret = SListFind(&s, 2);
  SListErase(&s, ret);
  PrintSList(&s);
  
  //检测data是否是链表中
  SListIsFindData(&s, 2);
  PrintSList(&s);
  
  // 移除链表中第一个值为data的元素 
  SListRemove(&s, 0);
  PrintSList(&s);
  // 移除链表中所有值为data的元素
  //SListRemoveAll(&s, 1);
  //PrintSList(&s);
  
  // 获取链表有效元素个数 
  SListSize(&s);//
  PrintSList(&s);
  
  // 检测链表是否为空
  SListEmpty(&s);
  PrintSList(&s);
  
  //获取链表中的第一个元素
  SListFront(&s);
  PrintSList(&s);
  
  //获取链表中的第一个元素
  SListBack(&s);
  PrintSList(&s);
  
  //销毁链表
  SListDestory(&s);
  PrintSList(&s);
 system("pause");
 return 0; 
}

运行结果如下：数据结构---不带头结点的单项非循环链表

上一篇：剑指offer学习笔记 链表中环的入口节点


下一篇：剑指offer：反转链表 python实现