单向循环链表和单向链表差不多，只不过是最后的尾节点指向的不是空，而是指向头节点。理解这一点很重要，因为这是我们写程序的关键
image.png
下面用代码实现以下，不带头节点的
1.创建
准备条件：定义节点，状态
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
分为2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
注意：这里使用尾插法实现的，更符合逻辑，也可以用头插发实现
/*
判断是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
*/
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;//创建的新节点
LinkList target = NULL;//尾结点
printf("输入节点的值，输入0结束\n");
while(1)
{
scanf("%d",&item);
if(item==0) break;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L==NULL)
{
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
}
else
{
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
for (target = *L; target->next != *L; target = target->next);
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新节点指向头节点
target->next=temp;//尾节点指向新节点
/// 🌹加上这一行就成了头插法
//*L = temp;
}
}
return OK;
}
这里寻找尾结点用了一个for循环，我们可以在每次新增节点是，用一个变量记录尾结点的位置
Status CreateList2(LinkList *L){
int item;
LinkList temp = NULL;//新加的node
LinkList r = NULL;//记录尾结点
printf("请输入新的结点, 当输入0时结束: ");
while (1) {
scanf("%d",&item);
if (item == 0) {
break;
}
//第一次创建
if(NULL == *L){
*L = (LinkList)malloc(sizeof(Node));
if(!*L) return ERROR;
(*L)->data = item;
(*L)->next = *L;
r = *L;//记录尾结点
}else{
temp = (LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data = item;
temp->next = *L;
//尾结点的指针域指向新创建的节点
r->next = temp;
//更新尾结点
r = temp;
///🌹注释上一行r = temp;，打开这一行成头插法
//*L = temp;//头插法
}
}
return OK;
}
image.png
2.遍历
遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
void show(LinkList p)
{
//如果链表是空
if(p == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = p;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != p);
printf("\n");
}
}
3.插入
插入分为2种情况，在首元结点插入和非首元结点插入，因为首元结点插入要处理头指针
Status ListInsert(LinkList *L, int place, int num){
if (place < 1 || place > getLength(*L)) {
printf("位置不合法");
return ERROR;
}
//temp是要插入的新节点，
LinkList temp ,target;
int i;
if (place == 1) {
//target是尾结点
//如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
//1\. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2\. 找到链表最后的结点_尾结点,
//3\. 让新结点的next 指向首元结点.
//4\. 尾结点的next 指向新的首元结点;
//5\. 让头指针指向temp(临时的新结点)
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
//寻找尾结点 target
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
*L = temp;
}else
{
//target是插入位置的前一个结点
//如果插入的位置在其他位置;
//1\. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2\. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
//3\. 通过target找到要插入位置的前一个结点, 让target->next = temp;
//4\. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
//寻找插入位置的前一个结点 target
for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
//先链后断
temp->next = target->next;
target->next = temp;
}
return OK;
}
首元节点位置插入
image.png
非首元节点位置插入
image.png
4.删除
删除和插入一样，也分为2种情况，在首元结点删除和非首元结点删除，因为首元结点要处理头指针
Status LinkListDelete(LinkList *L,int place){
if (place < 1 || place > getLength(*L)) {
printf("位置不合法");
return ERROR;
}
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
//②.链表还有很多数据,但是删除的是首结点;
//1\. 找到尾结点, 使得尾结点next 指向首元结点的下一个结点 target->next = (*L)->next;
//2\. 新结点做为首元结点,则释放原来的首元结点
for (target = *L; target->next != *L; target = target->next);
//记录首元结点，即要删除的节点
temp = *L;
//有指针后移一位
*L = (*L)->next;
//尾结点指向头指针
target->next = *L;
free(temp);
}else
{
//如果删除其他结点--其他结点
//1\. 找到删除结点前一个结点target
//2\. 使得target->next 指向下一个结点
//3\. 释放需要删除的结点temp
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++);
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
5.查询
int findValue(LinkList L,int value){
int i = 1;
LinkList p;
p = L;
//寻找链表中的结点 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
//当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i;
}
6.判断链表是否为空
Status isEmpty(LinkList L)
{
if (NULL == L)
return 1;
if (L->next == L)
return 1;
else
return 0;
}
7.计算链表长度
int getLength(LinkList L)
{
int length = 1;
LinkList pt = L->next;
while (pt != L)
{
length++;
pt = pt->next;
}
return length;
}
8.删除整个链表，释放内存
void FreeList(LinkList *L)
{
LinkList pt = NULL;
while (*L != NULL)
{
//如果只有头节点一个
if (*L == (*L)->next) {
free(*L);
*L = NULL;
}
else //如果不止头节点一个
{
pt = (*L)->next->next;
free((*L)->next);
(*L)->next = pt;
}
}
}
网友评论