带头节点的单循环链表的插入、删除、查找等操作

建立头结点

#pragma once
typedef struct CNode
{
 int data;
 struct CNode *next;
}CNode,*Clist;//CNode*==Clist

//初始化函数
void InitList(Clist plist);

//头插
bool Insert_head(Clist plist,int val);

//尾插
bool Insert_tail(Clist plist,int val);

//在plist中查找关键字key,找到返回结点,失败返回NULL
CNode * Search(Clist plist,int key);

//判空
bool IsEmpty(Clist plist);

//删除plist中的第一个key
bool DeleteVal(Clist plist,int key);

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

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

//清空数据
void Clear(Clist plist);

//销毁动态内存
void Destroy(Clist plist);

建立list.cpp

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

//判空
static void DeterPointNull(Clist plist)
{
 assert(plist!=NULL);
 if(plist==NULL)
 {
  exit(0);
 }
}

//初始化函数
void InitList(Clist plist)
{
 DeterPointNull(plist);
 plist->next=plist;//使其成为循环链表
}

//头插
bool Insert_head(Clist plist,int val)
{
 DeterPointNull(plist);
 CNode *p=(CNode *)malloc(sizeof(CNode));
 p->next=plist->next;
 p->data=val;
 plist->next=p;
 return true;
}

//尾插
bool Insert_tail(Clist plist,int val)
{
 DeterPointNull(plist);
 CNode *p=(CNode *)malloc(sizeof(CNode));
 assert(p!=NULL);
 p->data=val;
 CNode *q;
 for(q=plist;q->next!=plist;q=q->next);
 p->next=q->next;
 q->next=p;
 //p->next=plist;
 return true;
}

//在plist中查找关键字key,找到返回结点,失败返回NULL
CNode * Search(Clist plist,int key)
{
 DeterPointNull(plist);
 CNode *p;
 for(p=plist->next;p!=NULL;p=p->next)
 {
  if(key==p->data)
  {
   return p;
  }
 }
 return NULL;
}

//判空
bool IsEmpty(Clist plist)
{
 DeterPointNull(plist);
 return plist->next==plist;
}

//删除plist中的第一个key
bool DeleteVal(Clist plist,int key)
{
 DeterPointNull(plist);
 CNode *p=Search(plist,key);
 if(p==NULL)
 {
  return false;
 }
 CNode *q;
 for(q=plist->next;q!=NULL;q=q->next)
 {
  if(q->next==p)
  {
   q->next=p->next;
   free(p);
   return true;
  }
 }
 return false;
}

//获取数据长度
int GetLength(Clist plist)
{
 DeterPointNull(plist);
 int count=0;
 for(CNode *p=plist->next;p!=plist;p=p->next)
 {
  count++;
 }
 return count;
}

//输出所有数据
void Show(Clist plist)
{
 DeterPointNull(plist);
 for(CNode *p=plist->next;p!=plist;p=p->next)
 {
  printf("%d   ",p->data);
 }
 printf("\n");
}

//清空数据
void Clear(Clist plist)
{
 DeterPointNull(plist);
 plist->next=NULL;
}

//销毁动态内存
void Destroy(Clist plist)
{
 DeterPointNull(plist);
 CNode *p;
 while(plist->next!=plist)
 {
  p=plist->next;
  plist->next=p->next;
  free(p);
 }
}

小知识：
顺序表和单链表性能对比：
 1、插入：
  顺序表：头插(O(n)需要将后面的数据后移)，中间插入(O(n)需要将后面的数据后移)，尾部插入（O（1））
  链表：头插（O（1）不需要移动后面的数据），中间插入(O(1)不需要将后面的数据后移)，尾部插入（O（1））
 2、删除
  顺序表：头删（O(n)需要将后面的数据后移），中间插入(O(n)需要将后面的数据前移)，尾部插入（O（1））
  链表：头插（O（1）不需要移动后面的数据），中间插入(O(1)不需要将后面的数据前移)，尾部插入（O（1））
 3、随机访问能力
  顺序表：O（1），通过下标直接访问
  链表：O(n)，必须从头开始遍历