当前位置:网站首页>Linear list --- circular linked list
Linear list --- circular linked list
2022-07-07 02:27:00 【Programming a small program】
Circular linked list : The characteristic of circular linked list is that the address of the head node can be found through the pointing of the tail node ;
The structure design is the same as that of the single linked list :
typedef int ELEM_TYPE;
typedef struct Clist
{
ELEM_TYPE data; // Data fields
struct Clist* next; // Pointer to the domain
} Clist, * PClist;
The main functions are as follows :
1. Initialization operation
In the initialization operation of the circular list, the first node's next The domain points to its own address
void Init_clist(struct Clist* plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return;
}
plist->next = plist;
}
2. Tail interpolation function
First apply for a new node pnewnode, And then take it. next The domain points to the address of the first node , Then apply for a temporary node p Point it to the address of the tail node , And then let p Of next Domain points to pnewnode The address of .
bool Insert_tail(PClist plist, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
//1. Buy new nodes
struct Clist *pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;// New nodes purchased Finished processing
//2. Find the insertion location ( Through... With precursors for loop )
struct Clist *p = plist;
for(p; p->next!=plist; p=p->next);
// here for Loop execution ends p Point to the tail node
//3. Insert
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
Circular linked list complete code
clist.h
// Circular linked list structure design
typedef int ELEMTYPE;
typedef struct Clist
{
ELEMTYPE data; // Data fields Storing data
struct Clist* next;// Pointer to the domain The address of the next node ( At the end next Save the address of the header node )
}Clist, *PClist;
// Circular linked list owned Executable function declaration :
// initialization
void InitClist(struct Clist* plist);
// Head insertion
bool Insert_head(PClist plist, ELEMTYPE val);
// Tail insertion
bool Insert_tail(PClist plist, ELEMTYPE val);
// Insert by position
bool Insert_pos(PClist plist, int pos, ELEMTYPE val);
// Head deletion
bool Del_head(PClist plist);
// Deletion at the end
bool Del_tail(PClist plist);
// Delete by location
bool Del_pos(PClist plist, int pos);
// Delete... By value
bool Del_val(PClist plist, ELEMTYPE val);
// lookup ( If I find , You need to return the address of the found node )
struct Clist* Search(struct Clist *plist, ELEMTYPE val);
// Sentenced to empty
bool IsEmpty(PClist plist);
// Full sentence ( Circular linked list does not need this operation )
// To obtain the length of the
int Get_length(PClist plist);
// Empty
void Clear(PClist plist);
// The destruction 1
void Destroy1(PClist plist);
// The destruction 2
void Destroy2(PClist plist);
// Print
void Show(struct Clist *plist);
clist.cpp
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include "clist.h"
// There are few in the circular linked list NULL, nullptr
// initialization
void InitClist(struct Clist* plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return;
}
//plist->data; // Data fields do not handle
plist->next = plist;
}
// Head insertion
bool Insert_head(PClist plist, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
//1. Buy new nodes
struct Clist *pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;// New nodes purchased Finished processing
//2. Find the insertion location ( Head insertion Don't look for )
//3. Insert
pnewnode->next = plist->next;
plist->next = pnewnode;
return true;
}
// Tail insertion
bool Insert_tail(PClist plist, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
//1. Buy new nodes
struct Clist *pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;// New nodes purchased Finished processing
//2. Find the insertion location ( Through... With precursors for loop )
struct Clist *p = plist;
for(p; p->next!=plist; p=p->next);
// here for Loop execution ends p Point to the tail node
//3. Insert
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
// Insert by position
bool Insert_pos(PClist plist, int pos, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
assert(pos>=0 && pos<=Get_length(plist));
//1. Buy new nodes
struct Clist *pnewnode = (struct Clist*)malloc(1 * sizeof(struct Clist));
assert(pnewnode != NULL);
pnewnode->data = val;// New nodes purchased Finished processing
//2. Find the insertion location ( Through... With precursors for loop )
struct Clist *p = plist;
for(int i=0; i<pos; i++)
{
p = p->next;
}
// here for Loop execution ends p Point to the appropriate location to be inserted
//3. Insert
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
// Head deletion
bool Del_head(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
if(IsEmpty(plist))// Not empty Then there is at least one valid value
{
return false;
}
//1. The pointer p Point to the node to be deleted
struct Clist *p = plist->next;
//2. The pointer q Point to the node before the node to be deleted
//q Namely Head node There will be no additional processing here
//3. Crossing direction
plist->next = p->next;
free(p);
return true;
}
// Deletion at the end
bool Del_tail(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
if(IsEmpty(plist))// Not empty Then there is at least one valid value
{
return false;
}
//1. The pointer p Point to the node to be deleted ( If the tail is deleted , This points to the tail node )
struct Clist *p = plist;
for(p; p->next!=plist; p=p->next);
// here for Point to the end Represents the p Point to the tail node
//2. The pointer q Point to the penultimate node
struct Clist *q = plist;
for(q; q->next!=p; q=q->next);
// here for Point to the end Represents the q Point to p The previous node of
//3. Crossing direction
q->next = p->next;
free(p);
return true;
}
// Delete by location
bool Del_pos(PClist plist, int pos)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
assert(pos>=0 && pos<Get_length(plist));
if(IsEmpty(plist))
{
return false;
}
//1. The pointer p Point to the node to be deleted
//2. The pointer q Point to the previous node of the node to be deleted
// Here we use the second scheme to find pq, Look for the q Look again p
struct Clist *q = plist;
for(int i=0; i<pos; i++)
{
q = q->next;
}
struct Clist *p = q->next;
//3. Crossing direction
q->next = p->next;
free(p);
return true;
}
// Delete... By value
bool Del_val(PClist plist, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
struct Clist* p = Search(plist, val);
if(p == NULL)
{
return false;
}
struct Clist *q = plist;
for(q; q->next!=p; q=q->next);
q->next = p->next;
free(p);
return true;
}
// lookup ( If I find , You need to return the address of the found node )
struct Clist* Search(struct Clist *plist, ELEMTYPE val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
for(struct Clist *p=plist->next; p!=plist; p=p->next)
{
if(p->data == val)
{
return p;
}
}
return NULL;
}
// Sentenced to empty
bool IsEmpty(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
return plist->next == plist;
}
// Full sentence ( Circular linked list does not need this operation )
// To obtain the length of the
/* The pointer p Run backward from the next node of the head node , If p Encountered the header node again ,
prove p I walked around and came back , This is a valid node. The traversal must have ended */
int Get_length(PClist plist)
{
// Without precursors for loop Just run once
int count = 0;
for(struct Clist *p=plist->next; p!=plist; p=p->next)
{
count++;
}
return count;
}
// Empty
void Clear(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
Destroy1(plist);
}
// The destruction 1( Infinite header deletion )
void Destroy1(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
while(plist->next != plist)
{
struct Clist *p = plist->next;
plist->next = p->next;
free(p);
}
plist->next = plist;
}
// The destruction 2( You need two pointer variables )
void Destroy2(PClist plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
struct Clist *p = plist->next;
struct Clist *q = NULL;
plist->next = plist;
while (p!=plist)
{
q = p->next;
free(p);
p = q;
}
}
// Print
void Show(struct Clist *plist)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
for(struct Clist *p=plist->next; p!=plist; p=p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
边栏推荐
- 遇到慢SQL该怎么办?(下)
- Introduction to RC oscillator and crystal oscillator
- Argo workflows source code analysis
- Several classes and functions that must be clarified when using Ceres to slam
- Summer Challenge database Xueba notes (Part 2)~
- Big guys gather | nextarch foundation cloud development meetup is coming!
- The boss is quarantined
- Freeswitch dials extension number source code tracking
- [leetcode] day97 remove linked list elements
- 3D laser slam: time synchronization of livox lidar hardware
猜你喜欢
Summer Challenge database Xueba notes (Part 2)~
Alibaba cloud middleware open source past
[paper reading | deep reading] dngr:deep neural networks for learning graph representations
How can reinforcement learning be used in medical imaging? A review of Emory University's latest "reinforcement learning medical image analysis", which expounds the latest RL medical image analysis co
Processus général de requête pour PostgreSQL
大咖云集|NextArch基金会云开发Meetup来啦!
Big guys gather | nextarch foundation cloud development meetup is coming!
Web3的先锋兵:虚拟人
1500万员工轻松管理,云原生数据库GaussDB让HR办公更高效
FLIR blackfly s industrial camera: auto exposure configuration and code
随机推荐
长安链学习笔记-证书研究之证书模式
freeswitch拨打分机号源代码跟踪
SchedulX V1.4.0及SaaS版发布,免费体验降本增效高级功能!
fiddler的使用
强化学习如何用于医学影像?埃默里大学最新《强化学习医学影像分析》综述,阐述最新RL医学影像分析概念、应用、挑战与未来方向
C#/VB.NET 删除Word文档中的水印
Apifox,你的API接口文档卷成这样了吗?
Collection recommandée!! Quel plug - in de gestion d'état flutter est le plus fort? Regardez le classement des manons de l'île, s'il vous plaît!
6 seconds to understand the book to the Kindle
Jacob Steinhardt, assistant professor of UC Berkeley, predicts AI benchmark performance: AI has made faster progress in fields such as mathematics than expected, but the progress of robustness benchma
STM32项目 -- 选题分享(部分)
Word wrap when flex exceeds width
Draco - gltf model compression tool
Lumion 11.0软件安装包下载及安装教程
所谓的消费互联网仅仅只是做行业信息的撮合和对接,并不改变产业本身
纽约大学 CITIES 研究中心招聘理学硕士和博士后
Halcon实例转OpenCvSharp(C# OpenCV)实现--瓶口缺陷检测(附源码)
【论文阅读|深读】DNGR:Deep Neural Networks for Learning Graph Representations
【Unity】升级版·Excel数据解析,自动创建对应C#类,自动创建ScriptableObject生成类,自动序列化Asset文件
Station B's June ranking list - feigua data up main growth ranking list (BiliBili platform) is released!