循环链表的设计与基本操作的实现

链表的设计与基本操作的实现"/>

循环链表的设计与基本操作的实现

目录

一.循环链表的设计

二.循环链表的实现

三.循环链表的总结

一.循环链表的设计

1.循环链表的结构设计:

typedef struct CNode{int data;struct CNode* next;}CNode ,*CList;

2.循环链表的示意图:

3.循环链表和单链表的区别:

唯一区别,没有空指针,尾节点的后继为头,为循环之意.

二.循环链表的实现

//初始化
void InitList(CList plist)
{assert(plist != NULL);if (plist == NULL)return;//头节点的数据域不使用plist->next = plist;//环形
}//头插
bool Insert_head(CList plist, int val)
{assert(plist != NULL);if (plist == NULL)return false;//申请节点CNode* p = (CNode*)malloc(sizeof(CNode));assert(p != NULL);//放入数据p->data = val;//头插p->next = plist->next;plist->next = p;return true;}//尾插
bool Insert_tail(CList plist, int val)
{assert(plist != NULL);if (plist == NULL)return false;//创建新节点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;//p->next=plist;q->next = p;return true;
}//插入数据，在plist链表的pos位置插入val;
bool Insert(CList plist, int pos, int val)
{if (pos<0 || pos>GetLength(plist)){return false;}//申请节点CNode* p = (CNode*)malloc(sizeof(CNode));assert(p != NULL);p->data = val;//找位置CNode* q;int i = 0;for(q=plist;i<pos;i++,q=q->next){;}//插入p->next = q->next;q->next = p;return true;
}//判空
bool IsEmpty(CList plist)
{return plist->next == plist;
}//获取数据节点的个数
int GetLength(CList plist)
{assert(plist != NULL);if (plist == NULL)return 0;int count = 0;for (CNode* p = plist->next; p != plist; p = p->next){count++;}return count;
}//在plist中查找第一个key值，找到返回节点地址，没有找到返回NULL；
CNode* Search(CList plist, int key)
{assert(plist != NULL);if (plist == NULL)return NULL;for (CNode* p = plist->next; p != plist; p = p->next){if (p->data == key){return p;}}return NULL;
}//删除pos位置的值
bool DelPos(CList plist, int pos)
{if (pos < 0 || pos >= GetLength(plist)){return false;}CNode* p;int i;for (p = plist, i = 0; i < pos; i++, p = p->next){;}CNode* q = p->next;//q是要删除的点p->next = q->next;free(q);return true;}bool DelVal(CList plist, int val)
{	CNode* p = GetPrio(plist, val);if (p == NULL){return false;}CNode* q = p->next;//q为要删除的点p->next = q->next;free(q);return true;
}//返回key的前驱地址，如果不存在返回NULL；
CNode* GetPrio(CList plist, int key)
{CNode* p;for (p = plist; p->next != plist; p = p->next){if (p->next ->data == key){return p;}}return NULL;}//返回key的后继地址，如果不存在返回NULL；
CNode* GetNext(CList plist, int key)
{CNode* p = Search(plist, key);if (p == NULL)return NULL;return p->next;
}//输出
void Show(CList plist)
{for (CNode* p = plist->next; p != plist; p = p->next){printf("%d  ", p->data);}printf("\n");
}//清空数据
void Clear(CList plist)
{Destroy(plist);
}//销毁整个内存
void Destroy(CList plist)
{//总是删除第一个数据节点CNode* p;while (plist->next != plist){p = plist->next;plist->next = p->next;free(p);}
}

三.循环链表的总结

循环链表其实和单链表是一样的操作,只是在处理的时候处理好尾节点即可,切记,遍历循环链表中不可出现NULL,若遍历的时候出现NULL就错了.