精华内容
下载资源
问答
  • [循环链表]——单向循环链表
    千次阅读
    2022-02-24 11:22:53

    单向循环链表与普通链表的区别在于:普通链表的最后一个链表的next指向NULL,而单向循环链表的最后一个节点的next指向头结点

     头文件:

    #ifndef CIRCLELINKLIST
    #define CIRCLELINKLIST
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    //链表小节点
    typedef struct CIRCLELINKNODE {
    	struct CIRCLELINKNODE* next;
    }CircleLinkNode;
    
    //链表结构体
    typedef struct CIRCLELINKLIST {
    	CircleLinkNode head;
    	int size;
    }CircleLinkList;
    
    //定义真假宏
    #define CIRCLELINKLIST_TRUE 1
    #define CIRCLELINKLIST_FALSE 0
    
    //比较回调函数
    typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);
    //打印回调函数
    typedef void(*PRINTNODE)(CircleLinkNode*);
    
    //针对链表结构体操作的API函数
    //链表初始化函数
    CircleLinkList* initCircleLinkList();
    //插入函数
    void insertByPos(CircleLinkList* clist, int pos, CircleLinkNode* data);
    //获得第一个元素
    CircleLinkNode* getFront(CircleLinkList* clist);
    //根据位置删除
    void removeByPos(CircleLinkList* clist, int pos);
    //根据值删除
    void removeByValue(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
    //获取链表长度
    int getSize(CircleLinkList* clist);
    //判断是否为空
    int isEmpty(CircleLinkList* clist);
    //根据值查找
    int findByValue(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
    //打印节点
    void printList(CircleLinkList* clist, PRINTNODE print);
    //释放内存
    void freeSpace(CircleLinkList* clist);
    
    #endif

    API实现:

    #include "CircleLinkList.h"
    
    //针对链表结构体操作的API函数
    //链表初始化函数
    CircleLinkList* initCircleLinkList() {
    	CircleLinkList* clist = (CircleLinkList*)malloc(sizeof(CircleLinkList));
    
    	//链表数据初始化
    	clist->head.next = &(clist->head);
    	clist->size = 0;
    	return clist;
    }
    
    //插入函数
    void insertByPos(CircleLinkList* clist, int pos, CircleLinkNode* data) {
    	if (clist == NULL) {
    		return;
    	}
    	if (data == NULL) {
    		return;
    	}
    	if (pos < 0 || pos > clist->size) {
    		pos = clist->size;
    	}
    
    	//找到前驱节点
    	CircleLinkNode* pCurrent = &(clist->head);
    	for (int i = 0; i < pos; i++) {
    		pCurrent = pCurrent->next;
    	}
    	//节点插入
    	data->next = pCurrent->next;
    	pCurrent->next = data;
    	clist->size++;
    }
    
    //获得第一个元素
    CircleLinkNode* getFront(CircleLinkList* clist) {
    	return clist->head.next;
    }
    
    //根据位置删除
    void removeByPos(CircleLinkList* clist, int pos) {
    	if (clist == NULL) {
    		return;
    	}
    	if (pos < 0 || pos > clist->size) {
    		return;
    	}
    
    	CircleLinkNode* pCurrent = clist->head.next;
    	for (int i = 0; i < pos; i++) {
    		pCurrent = pCurrent->next;
    	}
    	//缓存当前节点的下一个节点
    	CircleLinkNode* pNext = pCurrent->next;
    	pCurrent->next = pNext->next;
    	clist->size--;
    }
    
    //根据值删除
    void removeByValue(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare) {
    	if (clist == NULL || data == NULL) {
    		return;
    	}
    
    	CircleLinkNode* pPrev = &(clist->head);
    	CircleLinkNode* pCurrent = pPrev->next;
    	for (int i = 0; i < clist->size; i++) {
    		if (compare(pCurrent, data) == CIRCLELINKLIST_TRUE) {
    			pPrev->next = pCurrent->next;
    			clist->size--;
    			break;
    		}
    		pPrev = pCurrent;
    		pCurrent = pCurrent->next;
    	}
    }
    
    //获取链表长度
    int getSize(CircleLinkList* clist) {
    	return clist->size;
    }
    
    //判断链表是否为空
    int isEmpty(CircleLinkList* clist) {
    	if (clist->size == 0) {
    		return CIRCLELINKLIST_TRUE;
    	}
    
    	return CIRCLELINKLIST_FALSE; //返回0表示,非空
    }
    
    //根据值查找
    int findByValue(CircleLinkList* clist, CircleLinkNode* data, COMPARENODE compare) {
    	if (clist == NULL || data == NULL) {
    		return -1;
    	}
    
    	CircleLinkNode* pCurrent = clist->head.next;
    	int flag = -1;
    	for (int i = 0; i < clist->size; i++) {
    		if (compare(pCurrent, data) == CIRCLELINKLIST_TRUE) {
    			flag = i;
    			break;
    		}
    		pCurrent = pCurrent->next;
    	}
    
    	return flag;
    }
    
    //打印节点
    void printList(CircleLinkList* clist, PRINTNODE print) {
    	if (clist == NULL) {
    		return;
    	}
    
    	CircleLinkNode* pCurrent = clist->head.next;
    	for (int i = 0; i < clist->size; i++) {
    		print(pCurrent);
    		pCurrent = pCurrent->next;
    	}
    }
    
    //释放内存
    void freeSpace(CircleLinkList* clist) {
    	if (clist == NULL) {
    		return;
    	}
    	free(clist);
    }

    测试代码:

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "CircleLinkList.h"
    
    //测试结构体
    typedef struct PERSON {
    	CircleLinkNode node; //连接各个数据
    	char name[64];
    	int age;
    }Person;
    
    void myPrint(CircleLinkNode * data) {
    	Person* person = (Person*)data;
    	printf("name:%s, age:%d\n", person->name, person->age);
    }
    
    //1代表相同,0代表不同
    int myCompare(CircleLinkNode* data1, CircleLinkNode* data2) {
    	Person* p1 = (Person*)data1;
    	Person* p2 = (Person*)data2;
    	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age) {
    		return CIRCLELINKLIST_TRUE;
    	}
    
    	return CIRCLELINKLIST_FALSE;
    }
    
    void test01() {
    	CircleLinkList* clist = initCircleLinkList();
    
    	//创建测试数据
    	Person p1, p2, p3, p4, p5, p6;
    	strcpy(p1.name, "aaa");
    	strcpy(p2.name, "bbb");
    	strcpy(p3.name, "ccc");
    	strcpy(p4.name, "ddd");
    	strcpy(p5.name, "eee");
    	strcpy(p6.name, "fff");
    	p1.age = 30;
    	p2.age = 40;
    	p3.age = 50;
    	p4.age = 60;
    	p5.age = 70;
    	p6.age = 80;
    
    	//插入数据到链表结构
    	insertByPos(clist, 0, (CircleLinkNode*)(&p1));
    	insertByPos(clist, 0, (CircleLinkNode*)(&p2));
    	insertByPos(clist, 0, (CircleLinkNode*)(&p3));
    	insertByPos(clist, 0, (CircleLinkNode*)(&p4));
    	insertByPos(clist, 0, (CircleLinkNode*)(&p5));
    	insertByPos(clist, 0, (CircleLinkNode*)(&p6));
    
    	//打印数据
    	printList(clist, myPrint);
    	printf("===============================\n");
    
    	//删除数据
    	removeByPos(clist, 2);
    	printList(clist, myPrint);
    	printf("===============================\n");
    
    	//查找数据
    	Person findP;
    	strcpy(findP.name, "ccc");
    	findP.age = 50;
    	int flag = findByValue(clist, &findP, myCompare);
    	if (flag == CIRCLELINKLIST_TRUE) {
    		printf("数据 %s 找到了\n", findP.name);
    	} else {
    		printf("数据 %s 未找到了\n", findP.name);
    	}
    }
    
    int main(void) {
    	test01();
    	system("pause");
    	return 0;
    }

    约瑟夫问题:

    约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,我们把问题描述如下:

    • 现有M个人围成一桌坐下,编号从1到M,从编号为1的人开始报数。
    • 报数也从1开始,报到N的人离席,从离席者的下一位在座成员开始,继续从1开始报数。
    • 复现这个过程(各成员的离席次序),或者求最后一个在座的成员编号。
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "CircleLinkList.h"
    
    //环内数据总数,N走一步出列
    #define M 8
    #define N 3
    
    //存储的数据
    typedef struct MYNUM {
    	CircleLinkNode node;
    	int val; //存储的数据编号
    }MyNum;
    
    //打印回调实现
    void myPrint1(CircleLinkNode* data) {
    	MyNum* num = (MyNum*)data;
    	printf("%d ", num->val);
    }
    
    //比较回调打印
    int myCompare1(CircleLinkNode* data1, CircleLinkNode* data2) {
    	MyNum* m1 = (MyNum*)data1;
    	MyNum* m2 = (MyNum*)data2;
    	
    	if (m1->val == m2->val) {
    		return CIRCLELINKLIST_TRUE;
    	}
    	return CIRCLELINKLIST_FALSE;
    }
    
    void josephus() {
    	//创建循环链表
    	CircleLinkList* clist = initCircleLinkList();
    	//链表中插入数据
    	MyNum myNum[8]; //数据数组
    	for (int i = 0; i < 8; i++) {
    		myNum[i].val = i + 1;
    		insertByPos(clist, i, (CircleLinkNode*)&myNum[i]);
    	}
    
    	//打印环内数据
    	printList(clist, myPrint1);
    	printf("\n");
    
    	int index = 1; //表示当前位置
    	CircleLinkNode* pCurrent = clist->head.next;
    	while (getSize(clist) > 1) {
    		if (index == N) {
    			MyNum* tempNum = (MyNum*)pCurrent;
    			printf("%d ", tempNum->val);
    
    			//缓存待删除节点的下一个节点
    			CircleLinkNode* pNext = pCurrent->next;
    			//根据值删除
    			removeByValue(clist, pCurrent, myCompare1);
    
    			//判断是否是头结点,是的话需要跳过去
    			pCurrent = pNext;
    			if (pCurrent == &(clist->head)) {
    				pCurrent = pCurrent->next;
    			}
    
    			//重置index值
    			index = 1;
    		}
    
    		pCurrent = pCurrent->next;
    		if (pCurrent == &(clist->head)) {
    			pCurrent = pCurrent->next;
    		}
    		index++;
    	}
    	printf("\n");
    
    	if (getSize(clist) == 1) {
    		MyNum* font = (MyNum*)getFront(clist);
    		printf("最终筛选出的是 %d\n", font->val);
    	}
    	else {
    		printf("筛选出错!!!!\n");
    	}
    
    	//释放链表内存
    	freeSpace(clist);
    }
    
    int main(void) {
    	josephus();
    	return 0;
    }
    更多相关内容
  • 本篇文章是对用C++实现单向循环链表的解决方法进行了详细的分析介绍,需要的朋友参考下
  • 单向循环链表

    2021-01-20 03:32:26
    循环链表 循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点...
  • 单向循环链表实现约瑟夫环.zip
  • 一、单向循环链表 将单链表的首尾节点相连就形成了单向循环链表。 1、单向循环链表的节点 2、单向循环链表的结构 单向循环链表只有一个节点时: 二、双向循环链表 1、双向循环链表示意图 2、双向循环链表节点...

    一、单向循环链表

    将单链表的首尾节点相连就形成了单向循环链表。
    在这里插入图片描述

    1、单向循环链表的节点

    在这里插入图片描述

    2、单向循环链表的结构

    在这里插入图片描述
    单向循环链表只有一个节点时:
    在这里插入图片描述

    二、双向循环链表

    1、双向循环链表示意图

    在这里插入图片描述

    2、双向循环链表节点设计

    在这里插入图片描述

    struct d_node{
    	int data;	//数据域
    	struct d_node *next;
    	struct d_node *prev;
    };
    

    3、双向循环链表的一般性结构

    1)只有头结点的情况
    在这里插入图片描述
    2)有多个节点的情况
    在这里插入图片描述

    4、双向循环链表头插法插入节点

    在这里插入图片描述
    步骤:
    1)p->next = head->next
    2)head->next = p;
    3)p->next->prev = p;
    4)p->prev = head;

    若双向循环链表只有一个节点
    在这里插入图片描述
    步骤:
    1)head->next = p;
    2)p->prev = head;

    5、双向循环链表尾插法

    在这里插入图片描述
    步骤:
    1)处理前继指针
    p->prev = head->prev;
    head->prev = p;
    2)处理后继指针
    p->prev->next = p;
    p->next = head;

    6、双向循环链表节点的删除

    在这里插入图片描述
    删除指定节点p步骤:
    1)从逻辑上在链表中把p节点删除
    p->prev->next = p->next;
    p->next->prev = p->prev;
    2)从物理上删除节点p——free§

    若p节点是链表的最后一个节点,那就:p->prev->next = NULL;
    示例代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    //0,设计双向循环链表节点
    typedef struct d_node{
    	int data;
    	struct d_node *prev;	//前继指针
    	struct d_node *next;	//后继指针
    }D_NODE;
    
    //1,创建双向循环链表
    D_NODE *D_Loop_List_Create(void)
    {
    	//1)申请链表头结点堆空间
    	D_NODE *d_list = (D_NODE *)malloc(sizeof(D_NODE));
    	if (NULL == d_list)
    	{
    		perror("malloc failed");
    		return NULL;
    	}
    	//2)对头结点进行赋值
    	d_list->prev = d_list;
    	d_list->next = d_list;
    
    	//3)返回头结点地址
    	return d_list;
    }
    
    //2,添加链表节点 -->头插法
    bool D_Loop_List_Insert_Head(D_NODE *head, int data)
    {
    	//1,新节点申请堆空间
    	D_NODE *newnode = (D_NODE *)malloc(sizeof(D_NODE));
    	if (NULL == newnode)
    	{
    		perror("malloc newnode failed");
    		return false;
    	}
    	//2,对新节点进行赋值
    	newnode->data = data;
    	newnode->prev = newnode;
    	newnode->next = newnode;
    
    	//3,头插法插入链表
    	newnode->next = head->next;
    	head->next = newnode;
    
    	newnode->next->prev = newnode;
    	newnode->prev = head;
    	return true;
    }
    //尾插法
    bool D_Loop_List_Insert_End(D_NODE *head, int data)
    {
    	//1,新节点申请堆空间
    	D_NODE *newnode = (D_NODE *)malloc(sizeof(D_NODE));
    	if (NULL == newnode)
    	{
    		perror("malloc newnode failed");
    		return false;
    	}
    	//2,对新节点进行赋值
    	newnode->data = data;
    	newnode->prev = newnode;
    	newnode->next = newnode;
    
    	//尾插法插入节点
    		//1)处理前继指针
    		newnode->prev = head->prev;
    		head->prev = newnode;
    		//2)处理后继指针
    		newnode->prev->next = newnode;
    		newnode->next = head;
    	return true;
    }
    
    //3,链表显示
    void D_Loop_List_Display(D_NODE *head)
    {
    	D_NODE *p = head->next;
    	printf("链表数据:");
    	while( p != head)
    	{
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    //4,链表节点查找
    bool D_Lool_List_Search(D_NODE *head, int data)
    {
    	int i = 1;
    	D_NODE *p = head->next;
    	while(p != head)
    	{
    		if (p->data == data)
    		{
    			printf("找到这个节点!,节点序号[%d]\n", i);
    			return true;
    		}
    		p = p->next;
    		i++;
    	}
    	printf("链表中没有这个节点!\n");
    }
    
    //5,链表节点删除
    bool D_Loop_List_Remove(D_NODE *head, int data)
    {
    	int i = 1;
    	D_NODE *p = head->next;
    	while(p != head)
    	{
    		if (p->data == data)
    		{
    			printf("删除这个节点!,节点序号[%d]\n", i);
    			p->prev->next = p->next;
    			p->next->prev = p->prev;
    			free(p);
    			return true;
    		}
    		p = p->next;
    		i++;
    	}
    	printf("链表中没有这个节点!\n");	
    
    }
    
    //6,链表的销毁
    void D_Lool_List_Destroy(D_NODE *head)
    {
    	int i = 0;
    	D_NODE *p = head;
    	while(p->next != head)
    	{
    		p = p->next;
    		free(p->prev);
    		i++;
    	}
    	free(p);
    	printf("销毁链表成功,一共释放[%d]个节点!\n", i);
    }
    
    /*双向循环链表*/
    int main(int argc, char const *argv[])
    {
    	int i, num;
    
    	D_NODE *dl_list = D_Loop_List_Create();
    
    	for(i=0; i<5; i++)
    	{
    		scanf("%d", &num);
    		D_Loop_List_Insert_End(dl_list, num);
    		D_Loop_List_Display(dl_list);
    	}
    
    	printf("请输入需要查找的数据:");
    	scanf("%d", &num);
    	D_Lool_List_Search(dl_list, num);	
    
    	printf("请输入需要删除的数据:");
    	scanf("%d", &num);
    	D_Loop_List_Remove(dl_list, num);		
    
    	D_Lool_List_Destroy(dl_list);
    
    	return 0;
    }
    
    
    
    
    
    展开全文
  • c语言实现单向循环链表
  • 单向循环链表.zip

    2019-09-18 23:09:54
    单向循环链表源码,包括List的接口定义的源码,实现了List接口的方法。
  • 本文实例讲述了python单向循环链表原理与实现方法。分享给大家供大家参考,具体如下: 单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。 操作 is_...
  • 单向循环链表里面的每一个节点的next都要有指向,最后一个节点的next指向head节点 单向循环链表跟普通的单链表的操作逻辑几乎—模一样,唯一的区别,结尾的判断,区别如下 建议学完单向非循环链表,再来对比 (本人...

    概述

    单向循环链表里面的每一个节点的next都要有指向,最后一个节点的next指向head节点
    单向循环链表跟普通的单链表的操作逻辑几乎—模一样,唯一的区别,结尾的判断,区别如下

    建议学完单向非循环链表,再来对比
    (本人先是在掘金上编辑的,然后复制粘贴自己的博客,所以图片都有掘金的水印,欢迎来我的掘金博客查看原文)

    image.png

    示例代码

    //单向循环链表
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    typedef int DataType;
    
    typedef struct Node
    {
    	DataType data;
    	struct Node *next;
    }listnode, *singly_list;
    
    //typedef struct Node listnode;
    //typedef struct Node *singly_list; 
    
    //初始化链表
    singly_list init_list(void)
    {
    	//为链表申请一个节点作为头结点
    	singly_list head = malloc(sizeof(listnode));
    	if (head != NULL)
    	{
    		head->next = head;
    	}
    	return head;
    }
    
    //判断空链表
    bool empty(singly_list head)
    {
    	return head->next == head;
    }
    
    //新建节点
    singly_list create_node(DataType data)
    {
    	singly_list new = malloc(sizeof(listnode));
    	if (new != NULL)
    	{
    		new->data = data;
    		new->next = NULL;
    	}
    	return new;
    }
    
    //插入节点(尾插)
    void insert_node(singly_list head, singly_list new)
    {
    	//如果不为空,就要找到链表的最后一个节点
    	singly_list p = head;
    	//如果下一个节点不为空,就一直往后找,直到这个节点的next为空
    	while(p->next != head)
    	{
    		p = p->next;
    	}
    	new->next = head;
    	p->next = new;
    }
    
    //插入节点(头插)
    void tail_node(singly_list head, singly_list new)
    {
    	new->next = head->next;
    	head->next = new;
    }
    
    //遍历
    void display(singly_list head)
    {
    	singly_list p = head;
    	while(p->next != head)
    	{
    		p = p->next;
    		printf("%d ", p->data);
    	}
    	printf("\n");
    }
    
    //查找节点
    singly_list find_node(singly_list head, DataType data)
    {
    	singly_list p = head;
    	while(p->next != head)
    	{
    		p = p->next;
    		if (p->data == data)
    		{
    			//如果跟链表的节点数据相同,表示找到这个节点
    			return p;
    		}
    	}
    	//如果遍历了整个链表都没有找到数据data
    	return NULL;
    }
    
    //删除节点(只删除匹配到的第一个节点)
    void delete_node1(singly_list head, DataType data)
    {
    	singly_list p = head;
    	if(find_node(head, data) != NULL)
    	{
    		printf("链表里面有这个值存在\n");
    	}
    	else
    	{
    		printf("链表里面没有这个值存在\n");
    		return ;
    	}
    	while(p->next != head)
    	{
    		if (p->next->data == data)
    		{
    			singly_list delete = p->next;//表示下一个节点就是要删除的节点
    			p->next = delete->next;
    			free(delete);
    			return ;
    		}
    		p = p->next;
    	}
    }
    
    //删除节点(将所有相同的值删掉)
    void delete_node2(singly_list head, DataType data)
    {
    	singly_list p = head;
    	if(find_node(head, data) != NULL)
    	{
    		printf("链表里面有这个值存在\n");
    	}
    	else
    	{
    		printf("链表里面没有这个值存在\n");
    		return ;
    	}
    	while(p->next != head)
    	{
    		if (p->next->data == data)
    		{
    			singly_list delete = p->next;//表示下一个节点就是要删除的节点
    			p->next = delete->next;
    			free(delete);
    			//假设后面有连续的要删除的节点,那么我们不能删除一个之后就往后偏移
    			continue ;
    		}
    		p = p->next;
    	}
    }
    
    //删除节点(要删除的数据是一个节点)
    void delete_node3(singly_list head, singly_list delete)
    {
    	singly_list p = head;
    	if(find_node(head, delete->data) != NULL)
    	{
    		printf("链表里面有这个值存在\n");
    	}
    	else
    	{
    		printf("链表里面没有这个值存在\n");
    		return ;
    	}
    	while(p->next != head)
    	{
    		if (p->next == delete)
    		{
    			p->next = delete->next;
    			free(delete);		
    			return ;
    		}
    		p = p->next;
    	}
    }
    
    //修改节点
    void update_node(singly_list head, DataType old_data, DataType new_data)	
    {
    	singly_list find = find_node(head, old_data);
    	if (find == NULL)
    	{
    		printf("没有找到这个数据\n");
    	}
    	else
    	{
    		find->data = new_data;
    		printf("数据修改成功\n");
    	}
    	return;
    }
    
    //清空链表
    void clear_list(singly_list head)
    {
    	while(head->next != head)
    	{
    		singly_list dele = head->next;
    		head->next = dele->next;
    		free(dele);
    	}
    }
    
    //取出节点
    singly_list get_node(singly_list head, DataType data)
    {
    	if (empty(head))
    	{
    		return NULL;
    	}
    	singly_list p = head;
    	while(p->next != head)
    	{
    		if (p->next->data == data)
    		{
    			singly_list node = p->next;//表示下一个节点就是要删除的节点
    			p->next = node->next;	
    			return node;
    		}
    		p = p->next;
    	}
    	return NULL;
    }
    
    //移动节点()将data2的节点移动到data1的前面
    void move_node(singly_list head, DataType data1, DataType data2)
    {
    	//取出data2的节点
    	singly_list node1 = get_node(head, data2);
    	//找到data1的节点
    	singly_list node2 = find_node(head, data1);
    	node1->next = node2->next;
    	node2->next = node1;
    }
    
    //指定位置插入节点
    void insert_any_node(singly_list node1, singly_list node2)
    {
    	if (node1 == NULL || node2 == NULL)
    	{
    		return ;
    	}
    	// node1->next = node2->next;
    	// node2->next = node1;
    	tail_node(node2, node1);
    }
    
    int main(int argc, char const *argv[])
    {
    	//初始化一个空链表
    	singly_list head = init_list();
    
    	int i;
    	for (i = 0; i < 5; ++i)
    	{
    		insert_node(head, create_node(1+i));
    	}
    
    	// listnode n = {.next = NULL, .data = 7};
    	// insert_node(head, &n);
    
    	display(head);
    
    	singly_list node = get_node(head, 2);
    
    	printf("node->data = %d\n", node->data);
    	display(head);
    	delete_node1(head, 4);
    	// singly_list node1 = find_node(head, 1);
    	// singly_list node3 = find_node(head, 3);
    
    
    	// singly_list node2 = create_node(7);
    	// singly_list node4 = create_node(10);
    	// insert_any_node(node2, node1);
    	// insert_any_node(node4, node3);
    	// move_node(head,1,4);
    
    	
    	display(head);
    	update_node(head, 1, 7);
    	display(head);
    	return 0;
    }
    

    分块剖析

    节点设计及初始化

    和单向非循环的链表区别就是,加了一个prev指针指向上一个数据的地址。

    image.png

    创建新节点

    image.png

    尾插法插入节点

    先将要插入的New节点插在头节点head与head的上一个节点之间,再断开头节点head与head的上一个节点之间的联系。这里为了方便理解,将head的上一个节点命名为tail。
    建议按照图示去理解连接与断开步骤,切不可先断开再连接,否则找不到原来的链表了。

    image.png

    头插法插入节点

    头插法插入节点,即是插在头节点的下一个的位置。(头节点是不带数据的,一定要对头插、尾插理解到位)

    image.png

    遍历链表

    遍历链表分为往前、往后,两种遍历方式(毕竟有prev、next两个指针,自然有两种遍历方式咯)
    注意结束条件都是!=head 而不是 !=NULL

    image.png

    查找节点

    image.png

    删除节点

    先使要删除节点的前后节点连接起来后,再断开要删除的节点。

    image.png

    image.png

    判断空链表与更新节点

    判断空链表时,是
    head->next == head && head->prev == head

    image.png

    清空链表

    image.png

    展开全文
  • 单向循环链表解决约瑟夫问题。使用c++语言,结构体,链表的操作。
  • 目录1 单链表节点实现单链表操作单链表实现测试链表与顺序表对比2 单向循环链表操作实现测试3 双向链表操作实现测试 1 单链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域...

    1 单链表

    单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
    ![在这里插入GLKg==,size_20,color_FFFFFF,t_70,g_se,x_16)

    表元素域elem用来存放具体的数据。
    链接域next用来存放下一个节点的位置(python中的标识)
    变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

    节点实现

    class SingleNode(object):
        """单链表的结点"""
        def __init__(self,item):
            # _item存放数据元素
            self.item = item
            # _next是下一个节点的标识
            self.next = None

    单链表操作

    is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历整个链表
    add(item) 链表头部添加元素
    append(item) 链表尾部添加元素
    insert(pos, item) 指定位置添加元素
    remove(item) 删除节点
    search(item) 查找节点是否存在

    单链表实现

    class SingleLinkList(object):
        #单链表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
    
        def is_empty(self):
            #判断是否为空
            return self.__head==None
    
        def length(self):
            #输出链表的长度
            #定义一个指针进行遍历
            cur=self.__head
            count=0
            while cur!=None:
                count+=1
                cur=cur.next
            return count
    
        def travel(self):
            #遍历整个链表
            cur=self.__head
            while cur != None:
                print(cur.elem,end=" ")
                cur=cur.next
            print('')
    
        def add(self,item):
            #头部插入
            node=SingleNode(item)
            #方法一:头后插入
            if self.is_empty():
                self.__head=node
            else:
                p=self.__head
                self.__head=node
                node.next=p
    
            # #方法二:重置头
            # node.next=self.__head
            # self.__head=node
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = SingleNode(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                pre = self.__head
                count = 0
                while count<(pos-1):#当循环退出后,指向pos-1位置
                    count += 1
                    pre = pre.next
                node.next=pre.next
                pre.next = node
    
        def append(self,item):
            #尾端加入
            node=SingleNode(item)
            if self.is_empty():
                self.__head=node
            else:
                cur=self.__head
                while cur.next != None:
                    cur=cur.next
                cur.next=node
    
        def remove(self,item):
            cur = self.__head
            pre=None
            while cur != None:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        self.__head=cur.next
                    else:
                        pre.next=cur.next
                    break
                else:
                    pre = cur
                    cur = cur.next
    
        def search(self,item):
            #查找
            cur=self.__head
            while cur!=None:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            return False

    测试

    在这里插入图片描述

    链表与顺序表对比

    链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。链表与顺序表的各种操作复杂度如下所示:
    在这里插入图片描述
    注意虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。

    2 单向循环链表

    单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
    在这里插入图片描述

    操作

    is_empty() 判断链表是否为空
    length() 返回链表的长度
    travel() 遍历
    add(item) 在头部添加一个节点
    append(item) 在尾部添加一个节点
    insert(pos, item) 在指定位置pos添加节点
    remove(item) 删除一个节点
    search(item) 查找节点是否存在

    实现

    class Node(object):
        #节点
        def __init__(self,elem):
            self.elem=elem
            self.next=None
    
    class SingleCycleLinkList(object):
        #单项循环列表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
            if node:
                node.next=node
    
        def is_empty(self):
            #判断是否为空
            return self.__head==None
    
        def length(self):
            #输出链表的长度
            if self.is_empty():
                return 0
            #定义一个指针进行遍历
            cur=self.__head
            count=1
            while cur.next!=self.__head:
                count+=1
                cur=cur.next
            return count
    
        def travel(self):
            #遍历整个链表
            if self.is_empty():
                return
            cur=self.__head
            while cur.next!=self.__head:
                print(cur.elem,end=" ")
                cur=cur.next
            #退出循环,cur指向尾节点,但尾节点的元素未打印
            print(cur.elem)
    
        def add(self,item):
            #头部插入
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环,cur指向尾节点,
                node.next=self.__head
                cur.next=node
                self.__head=node
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = Node(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                pre = self.__head
                count = 0
                while count<(pos-1):#当循环退出后,指向pos-1位置
                    count += 1
                    pre = pre.next
                node.next=pre.next
                pre.next = node
    
        def append(self,item):
            #尾端加入
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur=self.__head
                while cur.next !=self.__head:
                    cur=cur.next
                cur.next=node
                node.next=self.__head
    
        def remove(self,item):
            #删除节点
            if self.is_empty():
                return
            cur = self.__head
            pre=None
            while cur.next != self.__head:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        #头节点的情况
                        #先找的尾节点
                        rear=self.__head
                        while rear.next!=self.__head:
                            rear=rear.next
                        self.__head=cur.next
                        rear.next=self.__head
                    else:
                        #中间节点
                        pre.next=cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # 退出循环,cur指向尾节点
            if cur.elem==item:
                if cur==self.__head:
                    #链表只有一个节点
                    self.__head=None
                pre.next = cur.next
    
        def search(self,item):
            #查找
            if self.is_empty():
                return False
            cur=self.__head
            while cur.next!=self.__head:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            if cur.elem == item:
                return True
            return False

    测试

    在这里插入图片描述

    3 双向链表

    每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
    在这里插入图片描述

    操作

    is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历链表
    add(item) 链表头部添加
    append(item) 链表尾部添加
    insert(pos, item) 指定位置添加
    remove(item) 删除节点
    search(item) 查找节点是否存在

    实现

    class Node(object):
        #节点
        def __init__(self,item):
            self.elem=item
            self.next=None
            self.prev=None
    
    class DoubleLinkList(object):
        #双链表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
    
        def is_empty(self):
            #判断是否为空
            return self.__head is None
    
        def length(self):
            #输出链表的长度
            #定义一个指针进行遍历
            cur=self.__head
            count=0
            while cur!=None:
                count+=1
                cur=cur.next
            return count
    
        def travel(self):
            #遍历整个链表
            cur=self.__head
            while cur != None:
                print(cur.elem,end=" ")
                cur=cur.next
            print('')
    
        def add(self,item):
            #头部插入
            node=Node(item)
            node.next=self.__head
            self.__head=node
            node.next.prev=node
    
            # node.next=self.__head
            # self.__head.prev=node
            # self.__head=node
    
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = Node(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                cur=self.__head
                count = 0
                while count<pos:
                    count += 1
                    cur = cur.next
                #当循环退出后,cur就是指向pos这个位置
                node.next=cur
                node.prev=cur.prev
                cur.prev.next=node
                cur.prev=node
    
    
        def append(self,item):
            #尾端加入
            node=Node(item)
            if self.is_empty():
                self.__head=node
            else:
                cur=self.__head
                while cur.next != None:
                    cur=cur.next
                cur.next=node
                node.prev=cur
    
        def remove(self,item):
            cur = self.__head
            while cur != None:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        self.__head=cur.next
                        #判断链表是否只有一个节点
                        if cur.next:
                            cur.next.prev=None
                    else:
                        cur.prev.next=cur.next
                        if cur.next:
                            cur.next.prev=cur.prev
                    break
                else:
                    cur = cur.next
    
        def search(self,item):
            #查找
            cur=self.__head
            while cur!=None:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            return False
    

    测试

    在这里插入图片描述

    展开全文
  • 单向循环链表: 如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是把尾节点的下一跳指向头结点。 单向循环链表 –多个节点和只有一个节点的结构分析 双向...
  • 本篇文章将介绍单向循环链表,它和单链表的区别在于结尾点的指针域不是指向null,而是指向头结点,形成首尾相连的环。这种首尾相连的单链表称为单向循环链表。循环链表可以从任意一个结点出发,访问到链表中的全部...
  • 文章目录单向循环链表操作实现 单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 ...
  • C++单向循环链表实现

    2021-08-15 19:37:13
    单向循环链表与单向链表十分相似,具有关单向链表详细理论与实现...而单向循环链表将尾部node的指针域指向头部node,首位相连构成单向循环链表,具体形式为: 具体实现代码为: 1、链表定义 //定义节点 class...
  • 单向循环链表改为双向循环链表

    千次阅读 2020-08-20 08:17:43
    单项循环链表改双向循环链表 data数据域,next后继结点指针域,prior前驱结点指针域 说明: 这里的链表带头结点 */ #include <iostream> #include <cstdlib> using namespace std; const int flag = -1;...
  • 什么是单向循环链表?将单链表中终端节点的指针端由空指针改为指向头节点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。如下图所示:从上图可以看出,其循环就是尾节点的next指针...
  • C语言实现单向循环链表

    千次阅读 2020-06-14 08:14:48
    C语言实现单向循环链表 循环链表简介 循环链表的结构和单链表结构一样,不过对于单链表,每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,这样知道某个结点却无法找到它的前驱结点。将单链表中的终端...
  • 主要介绍了Python实现的单向循环链表功能,简单描述了单向循环链表的概念、原理并结合实例形式分析了Python定义与使用单向循环链表的相关操作技巧,需要的朋友可以参考下
  • 假定一个单向循环链表来表示队列
  • 1.单向链表 2.单向循环链表 3.双向链表 4.链表与顺序表的对比 5.自定义单向链表 6.自定义单向循环链表 7.自定义双向链表

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,992
精华内容 17,996
关键字:

单向循环链表

友情链接: 2024jiangsu.zip