不带头结点的单循环链表

创建头文件nlist.h

#pragma once
//不带头节点的链表,主要应用在循环链表中,其缺点,操作复杂(会出现二级指针),
//优点:灵活(头指针指向哪个节点哪个节点就是第一个节点)
//不带头节点的单链循环链表,尾节点的next指向第一个节点

typedef struct NNode
{
 int data;//数据
 struct NNode *next;//下一个节点的地址
}NNode,*PNList;

//初始化函数,将头指针置NULL,会出现二级指针
void InitList(PNList *pplist);

//头插,需要修改头指针,会出现二级指针
bool Insert_head(PNList *pplist,int val);

//尾插,有可能需要修改头指针,会出现二级指针
bool Insert_tail(PNList *pplist,int val);

//在plist中查找关键字key,找到返回下标,失败返回NULL
NNode * Search(PNList plist,int key);

//判空
bool IsEmpty(PNList plist);

//删除plist中的第一个key,有可能需要修改头指针,会出现二级指针
bool DeleteVal(PNList *pplist,int key);

//获取数据长度
int GetLength(PNList plist);

//输出所有数据
void Show(PNList plist);

//清空数据，需要修改头指针,会出现二级指针
void Clear(PNList *pplist);

//销毁动态内存，需要修改头指针,会出现二级指针
void Destroy(PNList *pplist);

创建nlist.cpp文件

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "nlist.h"

//初始化函数,将头指针置NULL,会出现二级指针
void InitList(PNList *pplist)
{
 assert(pplist != NULL);
 if(pplist == NULL)
  return;
  
 *pplist = NULL;
}

//头插,需要修改头指针,会出现二级指针
bool Insert_head(PNList *pplist,int val)
{
 NNode *p = (NNode *)malloc(sizeof(NNode));
 p->data = val;
 if(IsEmpty(*pplist))
 {
  p->next = p;
  *pplist = p;
 }
 else
 {
  NNode *q;//找尾巴
  for(q=*pplist;q->next!=*pplist;q=q->next);
  p->next = *pplist;
  *pplist = p;
  q->next = p;
 }
 
 return true;
}

//尾插,有可能需要修改头指针,会出现二级指针
bool Insert_tail(PNList *pplist,int val)
{
 NNode *p = (NNode *)malloc(sizeof(NNode));
 p->data = val;
 if(IsEmpty(*pplist))
 {
  p->next = p;
  *pplist = p;
 }
 else
 {
  NNode *q;//找尾巴
  for(q=*pplist;q->next!=*pplist;q=q->next);
  q->next=p;
  p->next=*pplist;
 }
 
 return true;
}

//在plist中查找关键字key,找到返回节点，失败返回NULL
NNode * Search(PNList plist,int key)
{
 NNode *q;
 for(q=plist;q->next!=plist;q=q->next)
 {
  if(q->data==key)
  {
   return q;
  }
 }
 if(q->data==key)
 {
  return q;
 }
 
 return NULL;
}

//判空,判断plist是否为NULL
bool IsEmpty(PNList plist)
{
 return plist == NULL;
}

//删除plist中的第一个key,有可能需要修改头指针,会出现二级指针
bool DeleteVal(PNList *pplist,int key)
{
 if(IsEmpty(*pplist))
 {
  return false;
 }
 NNode *p;
 NNode *q;
 for(q=*pplist;q->next!=*pplist;q=q->next)
 {
  if(q->next->data==key)
  {
   p=q->next;
   q->next=q->next->next;
   free(p);
   
   return true;
  }
 }
 
 p=*pplist;
 if(p->data==key)
 {
  *pplist=p->next;
  q->next=*pplist;
  free(p);
  
  return true;
 }
 
 return false;
}

//获取数据长度
int GetLength(PNList plist)
{
 int count=1;
 for(NNode *q=plist;q->next!=plist;q=q->next)
 {
  count++;
 }
 return count;
}

//输出所有数据
void Show(PNList plist)
{
 if(IsEmpty(plist))
  return ;
 NNode *p=plist;
 for(;p->next!=plist;p=p->next)//bug
 {
  printf("%d ",p->data);
 }
 printf("%d \n",p->data);
}

//清空数据,需要修改头指针,会出现二级指针
void Clear(PNList *pplist)
{
 *pplist=NULL;
}

//销毁动态内存,需要修改头指针,会出现二级指针
void Destroy(PNList *pplist)
{
 NNode *p;
 NNode *q=*pplist;
 while(q->next!=*pplist)
 {
  p=q->next;
  q->next=p->next;
  free(p);
 }
 *pplist=NULL;
}