循环单链表的操作

阳光穿透心脏的1/2处 2024-04-17 21:01 73阅读 0赞

## 创建循环单链表 ##

// 循环链表
    // 最后一个结点的指针指向头结点
    // 
    // 有时候可以设置尾指针，更方便表的连接操作
    typedef struct Node
    {
    	int elem;
    	struct Node * next;
    }clinklist, *pclinklist;

## 生成循环单链表 ##

*  函数声明

pclinklist clinklist_create(int size);

*  函数实现

pclinklist clinklist_create(int size)
    {
        
    	pclinklist node, head;
    	head = (pclinklist)malloc(sizeof(clinklist));
    
    	// 头结点 elem 表示链表大小，头结点 next 指向第一个元素
    	// 尾巴结点指向第一个元素节点
    	head->elem = size;
    	head->next = NULL;
    
    	node = head;
    
    	for (int i = 0; i < size; i++)
    	{
        
    		node->next = (pclinklist)malloc(sizeof(clinklist));
    		node = node->next;
    		node->elem = rand() % 100;
    		node->next = NULL;
    	}
    	node->next = head->next;
    
    	return head;
    }

## 插入 ##

*  函数声明

void clinklist_insert(pclinklist list, int locate, int elem);

*  函数实现

void clinklist_insert(pclinklist plist, int location, int elem)
    {
    	if (location < 0 || location > plist->elem) return;
    
    	pclinklist inode = (pclinklist)malloc(sizeof(clinklist));
    	inode->elem = elem;
    	inode->next = NULL;
    
    	pclinklist prev = clinklist_find(plist, location - 1);
    	pclinklist tail = clinklist_find(plist, plist->elem - 1);
    
    	inode->next = prev->next;
    	prev->next = inode;
    
    	if (location == 0)
    		tail->next = plist->next;
    
    	clinklist_update_head(plist);
    }

## 删除 ##

*  函数声明

void clinklist_delete(pclinklist list, int locate);

*  函数实现

void clinklist_delete(pclinklist plist, int location)
    {
    	if (location < 0 || location >= plist->elem) return;
    
    	pclinklist prev = clinklist_find(plist, location - 1);
    	pclinklist tail = clinklist_find(plist, plist->elem - 1);
    
    	pclinklist dnode = prev->next;
    	prev->next = prev->next->next;
    	free(dnode);
    
    	if (location == 0)
    		tail->next = plist->next;
    
    	clinklist_update_head(plist);
    }

## 遍历 ##

*  函数声明

void clinklist_display(pclinklist plist);

*  函数实现

void clinklist_display(pclinklist plist)
    {
        
    	pclinklist node = plist->next;
    	for (int i = 0; i < plist->elem; i++)
    	{
        
    		printf("%4d", node->elem);
    		node = node->next;
    	}
    	printf("\n");
    }

## 查找 ##

*  函数声明

pclinklist clinklist_find(pclinklist list, int location);

*  函数实现

// -1 是 header 结点
    pclinklist clinklist_find(pclinklist list, int location)
    {
        
    	if (location < -1 || location >= list->elem) return NULL;
    
    	pclinklist node = list;
    
    	for (int i = -1; i < location; i++)
    	{
        
    		node = node->next;
    	}
    
    	return node;
    }

## 完整实例 ##

*  头文件 `clinklist.h`

#pragma once
    #ifndef CLINKLIST_H
    #define CLINKLIST_H
    
    // 循环链表
    // 最后一个结点的指针指向头结点
    // 
    // 有时候可以设置尾指针，更方便表的连接操作
    typedef struct Node
    {
        
    	int elem;
    	struct Node * next;
    }clinklist, *pclinklist;
    
    pclinklist clinklist_create(int size);
    void clinklist_insert(pclinklist list, int locate, int elem);
    void clinklist_delete(pclinklist list, int locate);
    void clinklist_display(pclinklist list);
    pclinklist clinklist_find(pclinklist list, int location);
    int clinklist_is_same(pclinklist head, pclinklist node);
    int clinklist_is_empty(pclinklist list);
    int clinklist_size(pclinklist list);
    void clinklist_update_head(pclinklist list);
    
    #endif

*  源文件 `clinklist.c`

#include <stdio.h>
    #include <stdlib.h>
    #include "clinklist.h"
    
    int main() {
        
    	int size;
    	int index = 0;
    	pclinklist list;
    
    	printf("输入此循环单链表的大小：");
    	scanf_s("%d", &size);
    
    	list = clinklist_create(size);
    	clinklist_display(list);
    
    	for (index = 0; index < size; index++)
    	{
        
    		pclinklist node = clinklist_find(list, index);
    		printf("位置 %d 的值为：%d \n", index, node->elem);
    	}
    
    	printf("\n在位置5插入元素2后\n");
    	clinklist_insert(list, 4, 2);
    	clinklist_display(list);
    
    	printf("\n在最后一个位置插入元素-1后\n");
    	clinklist_insert(list, clinklist_size(list), -1);
    	clinklist_display(list);
    
    	printf("\n在位置0插入元素1111后\n");
    	clinklist_insert(list, 0, 1111);
    	clinklist_display(list);
    
    	printf("\n删除位置3元素后\n");
    	clinklist_delete(list, 2);
    	clinklist_display(list);
    
    	printf("\n删除位置1元素后\n");
    	clinklist_delete(list, 0);
    	clinklist_display(list);
    
    	printf("\n删除位置最后的元素后\n");
    	clinklist_delete(list, clinklist_size(list) - 1);
    	clinklist_display(list);
    
    	return 0;
    }
    
    pclinklist clinklist_create(int size)
    {
        
    	pclinklist node, head;
    	head = (pclinklist)malloc(sizeof(clinklist));
    
    	// 头结点 elem 表示链表大小，头结点 next 指向第一个元素
    	// 尾巴结点指向第一个元素节点
    	head->elem = size;
    	head->next = NULL;
    
    	node = head;
    
    	for (int i = 0; i < size; i++)
    	{
        
    		node->next = (pclinklist)malloc(sizeof(clinklist));
    		node = node->next;
    		node->elem = rand() % 100;
    		node->next = NULL;
    	}
    	node->next = head->next;
    
    	return head;
    }
    
    void clinklist_display(pclinklist plist)
    {
        
    	pclinklist node = plist->next;
    	for (int i = 0; i < plist->elem; i++)
    	{
        
    		printf("%4d", node->elem);
    		node = node->next;
    	}
    	printf("\n");
    }
    
    void clinklist_insert(pclinklist plist, int location, int elem)
    {
        
    	if (location < 0 || location > plist->elem) return;
    
    	pclinklist inode = (pclinklist)malloc(sizeof(clinklist));
    	inode->elem = elem;
    	inode->next = NULL;
    
    	pclinklist prev = clinklist_find(plist, location - 1);
    	pclinklist tail = clinklist_find(plist, plist->elem - 1);
    
    	inode->next = prev->next;
    	prev->next = inode;
    
    	if (location == 0)
    		tail->next = plist->next;
    
    	clinklist_update_head(plist);
    }
    
    void clinklist_delete(pclinklist plist, int location)
    {
        
    	if (location < 0 || location >= plist->elem) return;
    
    	pclinklist prev = clinklist_find(plist, location - 1);
    	pclinklist tail = clinklist_find(plist, plist->elem - 1);
    
    	pclinklist dnode = prev->next;
    	prev->next = prev->next->next;
    	free(dnode);
    
    	if (location == 0)
    		tail->next = plist->next;
    
    	clinklist_update_head(plist);
    }
    
    // -1 是 header 结点
    pclinklist clinklist_find(pclinklist list, int location)
    {
        
    	if (location < -1 || location >= list->elem) return NULL;
    
    	pclinklist node = list;
    
    	for (int i = -1; i < location; i++)
    	{
        
    		node = node->next;
    	}
    
    	return node;
    }
    
    int clinklist_is_same(pclinklist lnode, pclinklist rnode)
    {
        
    	return (lnode == rnode) ? 1 : 0;
    }
    
    int clinklist_is_empty(pclinklist list)
    {
        
    	return list->next == NULL;
    }
    
    int clinklist_size(pclinklist list)
    {
        
    	return list->elem;
    }
    
    void clinklist_update_head(pclinklist list)
    {
        
    	pclinklist node = list->next;
    	int size = node == NULL ? 0 : 1;
    
    	while ((node = node->next) != list->next)
    		size++;
    
    	list->elem = size;
    }