当前位置：网站首页>c—线性表

c—线性表

2022-07-07 21:53:00 【敏儿好xun】

文章目录

线性表基本概念

基本概念

  • 线性表是零个或者多个数据元素的有限序列。
  • 特性：
    在这里插入图片描述

数学定义

  • 定义
    在这里插入图片描述
  • 性质
    在这里插入图片描述

线性表的顺序存储

顺序存储的概念

在这里插入图片描述

线性表顺序存储设计与实现

  • 案例：动态数组
    在这里插入图片描述

示例：

  1. 建立头文件——DynamicArray.h
#pragma once//防止头文件重复包含
//#ifndef DYNAMIC_ARRAY_H
//#define DYNAMIC_ARRAY_H


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//声明
//头文件放一些接口

//动态增长内存，将数据放到堆上

//动态数组结构体定义
typedef struct DYNAMICARRAY
{
    
	int* pAdder;//存放数据的地址
	int size;//当前元素个数
	int capacity;//容量，容器当前能容纳多少元素
}Dynamic_Array;

//写一些关于DYNAMICARRAY结构体操作的函数
//初始化
Dynamic_Array* Init_Array();
//插入
void Push_Array(Dynamic_Array* arr, int value);
//根据位置删除
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos);
//根据值删除
void RemoveByValue_Array(Dynamic_Array* arr, int value);
//查找
 int Find_Array(Dynamic_Array* arr, int value);
 //打印
 void Printf_Array(Dynamic_Array* arr);
//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr);
//清空数组
void Clear_Array(Dynamic_Array* arr);
//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr);
//获得动态数组当前元素个数
int Size_Array(Dynamic_Array* arr);
//根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos);

//#endif
  1. 建立 DynamicArray.c 源文件，进行各个函数的编写
#include"DynamicArray.h"

//初始化
Dynamic_Array* Init_Array()
{
    
	Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array));
	myArray->size = 0;
	myArray->capacity = 20;
	myArray->pAdder = (int*)malloc(sizeof(int)*myArray->capacity);
	return myArray;
}


//插入
void Push_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	//判断空间是否足够
	if (arr->size == arr->capacity)
	{
    
		//第一步，开辟更大的一块空间 ，新空间是就空间的2倍
		int* newpAdder= (int*)malloc(sizeof(int)*arr->capacity * 2);
		//第二部拷贝数据
		memcpy(newpAdder, arr->pAdder, arr->capacity * sizeof(int));
		//释放就空间
		free(arr->pAdder);
		//更新容量
		arr->capacity = arr->capacity * 2;
		arr->pAdder = newpAdder;
		
	}
	// 插入新元素
		arr->pAdder[arr->size] = value;
		arr->size++;
}


//根据位置删除
void RemoveByPos_Arrray(Dynamic_Array* arr, int pos)
{
    

	if (arr == NULL)
	{
    
		return ;
	}
	//判断位置是否有效
	if (pos < 0 || pos >= arr->size)
	{
    
		return;
	}
	//删除元素
	for (int i = pos; i < arr->size - 1; i++)
	{
    
		arr->pAdder[i] = arr->pAdder[i + 1];
	}
	arr->size--;
}


//根据值删除value（第一次出现时）
void RemoveByValue_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	//找到值的位置
	int pos= Find_Array(arr,value);
	
	//根据位置删除，调用位置删除函数
	RemoveByPos_Arrray(arr, pos);
}


//查找
int Find_Array(Dynamic_Array* arr, int value)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	int pos = -1;
	for (int i = 0; i < arr->size; i++)
	{
    
		if (arr->pAdder[i] == value)
		{
    
			pos = i;
			break;
		}
	}
	return pos;
}


//打印
void Printf_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return;
	}
	for (int i = 0; i < arr->size; i++)
	{
    
		printf("%d ", arr->pAdder[i]);
	}
	printf("\n");
}


//释放动态数组的内存
void FreeSpace_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return;
	}
	if (arr->pAdder != NULL)
	{
    
		free(arr->pAdder);
		
	}
	free(arr);
}


//清空数组
void Clear_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return ;
	}
	arr->size = 0;
}


//获得动态数组容量
int Capacity_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	return arr->capacity;
}


//获得动态数组当前元素个数
int Size_Array(Dynamic_Array* arr)
{
    
	if (arr == NULL)
	{
    
		return -1;
	}
	return arr->size;
}


//根据位置获得某个位置元素
int At_Array(Dynamic_Array* arr, int pos)
{
    
	return arr->pAdder[pos];
}
  1. 建立 01动态数组.c 源文件，进行测试
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#include"DynamicArray.h"

void test01()
{
    
	//初始化动态数组
	Dynamic_Array* myArray=Init_Array();

	printf("数组容量：%d\n", Capacity_Array(myArray));
	printf("数组大小：%d\n", Size_Array(myArray));
	
	//插入元素
	for (int i = 0; i <30; i++)
	{
    
		Push_Array(myArray, i);
	}
	Printf_Array(myArray);
	printf("数组容量：%d\n", Capacity_Array(myArray));
	printf("数组大小：%d\n", Size_Array(myArray));

	RemoveByPos_Arrray(myArray, 2);
	RemoveByValue_Array(myArray, 8);
	//打印
	Printf_Array(myArray);
	//查找元素5的位置
	int pos = Find_Array(myArray, 5);
	printf("元素5的位置为：%d\n", pos);

	//释放
	FreeSpace_Array(myArray);
}
int main()
{
    
	test01();
	system("pause");
	return 0;
}

结果：

数组容量：20
数组大小：0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
数组容量：40
数组大小：30
0 1 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
元素5的位置为：4

线性表的链式存储

基本概念

在这里插入图片描述

单项链表的设计与实现

  • 单向链表的数据域与指针域是放在一起的，插入新结点的时候，需要开辟新的空间来创建新结点。
    指定位置插入元素的过程
    在这里插入图片描述
  • 示例：单项列表
  1. 先建立一个头文件，LinkList.h 头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//链表节点
typedef struct LINKNODE
{
    
	void* data;//无类型指针可以指向任何类型的数据的地址
	struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef struct LINKLIST
{
    
	LinkNode* head;//头结点，属于结构体嵌套 
	int size;//当前元素个数
	//链表不需要提前设置容量
}LinkList;

//打印函数指针
typedef void(*PRINTLINKNODE)(void*);//typedef定义函数指针
//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list,int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list, void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);//???
//释放链表内存
void FreeSpace_LinkList(LinkList* list);
  1. 建立一个 LinkList.c 的源文件，进行各个函数的编写
#include"LinkList.h"


//初始化链表
LinkList* Init_LinkList()//维护结构体，对结构体进行操作
{
    
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head = 0;
	//给头节点开辟空间，头结点不保存数据信息
	list->head = (LinkNode*)malloc(sizeof(LinkNode));
	//头结点初始化,头结点的下一个结点才是链表的第一个结点
	list->head->data = NULL;
	list->head->next = NULL;
	return list;
}


//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data)
{
    
	if (list ==NULL ||data==NULL)
	{
    
		return;
	}
	//对于pos越界的友好处理
	if (pos<0 || pos>list->size)
	{
    
		pos = list->size;
	}
	//创建新结点
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	newnode->data = data;
	newnode->next = NULL;
	//找寻结点,辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
    
		pCurrent = pCurrent->next;
	}
	//将新结点插入链表
	newnode->next = pCurrent->next;
	pCurrent->next = newnode;

	list->size++;
}


//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
    
		return;
	}
	//查找待删除结点的上一个结点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
    
		pCurrent = pCurrent->next;
	}
	//缓存删除的结点
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	//释放删除结点的内存
	free(pDel);
	list->size--;
}


//获得链表的长度
int Size_LinkList(LinkList* list)
{
    
	return list->size;
}


//查找
int Find_LinkList(LinkList* list, void* data)
{
    
	if (list == NULL)
	{
    
		return -1;
	}
	if (data == NULL)
	{
    
		return -1;
	}
	LinkNode* pCurrent = list->head->next;
	int i=0;
	while (list != NULL)
	{
    
		if (pCurrent->data == data)
		{
    
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}	
	return i;
}


//返回第一个节点的元素
void* Front_LinkList(LinkList* list)
{
    
	return list->head->next->data;
}


//打印链表节点的元素
void Print_LinkList(LinkList* list, PRINTLINKNODE print)//???
{
    
	if (list == NULL)
	{
    
		return;
	}
	//辅助指针变量
	LinkNode* pCurrent = list->head->next;
	while (pCurrent != NULL)
	{
    
		print(pCurrent->data);//调用函数
		pCurrent = pCurrent->next;
	}
}


//释放链表内存
void FreeSpace_LinkList(LinkList* list)
{
    
	if (list == NULL)
		return;
	//辅助指针变量，先释放结点内存
	LinkNode* pCurrent = list->head;
	while (pCurrent!=NULL)
	{
    
		//缓存下一个结点，要不然每遍历一个就释放一个，会不好查找下一个结点
		LinkNode* pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;
	}
	//释放链表
	list->size = 0;
	free(list);
}
  1. 建立 02单项列表.c 源文件，进行测试
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include"LinkList.h"

//自定义的数据类型
typedef struct PERSON
{
    
	char name[21];
	int age;
	int score;
}person;

//打印函数
void myPrint(void* data)
{
    
	person* p = (person*)data;
	printf("名字：%s 年龄：%d 成绩：%d\n", p->name, p->age, p->score);
}
int main()
{
    
	//创建列表
	LinkList* list = Init_LinkList();
	//创建数据类型
	person p1 = {
     "张三",18,98 };
	person p2 = {
     "李四",16,89 };
	person p3 = {
     "王五",15,99 };
	person p4 = {
     "刘六",19,86 };
	person p5 = {
     "陈七",23,87 };
	//数据插入链表
	printf("-------------插入--------------\n");
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);
	//打印
	Print_LinkList(list, myPrint);

	//查找
	printf("-------------查找---------------\n");
	int pos=Find_LinkList(list, &p2);//当调用的为有返回值的函数的时候，要设置返回值
	printf("所查找的元素位置为：%d\n",pos );
	
	//删除
	printf("--------------删除位置3的元素---------------\n");
	RemoveByPos_LinkList(list, 3);
	Print_LinkList(list,myPrint);
	
	//返回第一个结点
	printf("-----------------返回第一个结点元素--------------\n");
	person* ret = Front_LinkList(list);
	printf("姓名：%s 年龄：%d 成绩： %d\n", ret->name, ret->age, ret->score);
	//释放列表
	FreeSpace_LinkList(list);


	return 0;
}

结果：

-------------插入--------------
名字：陈七 年龄：23 成绩：87
名字：刘六 年龄：19 成绩：86
名字：王五 年龄：15 成绩：99
名字：李四 年龄：16 成绩：89
名字：张三 年龄：18 成绩：98
-------------查找---------------
所查找的元素位置为：3
--------------删除位置3的元素---------------
名字：陈七 年龄：23 成绩：87
名字：刘六 年龄：19 成绩：86
名字：王五 年龄：15 成绩：99
名字：张三 年龄：18 成绩：98
-----------------返回第一个结点元素--------------
姓名：陈七 年龄：23 成绩： 87

企业链表的设计与实现

  • 企业链表的数据域与指针域是分离的，且代码量较少。
    示例：企业链表
  1. 建立一个 LinkList.h 头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//链表小结点
typedef struct LINKNODE
{
    
	struct LINKNODE* next;
}LinkNode;

//链表结点
typedef struct LINKLIST
{
    
	LinkNode head;
	int size;
}LinkList;


//定义打印函数指针
typedef void(*PRIENTFNODE)(LinkNode*);
//比较函数指针
typedef int(*COMPARENODE)(LinkNode*, LinkNode*);

//初始化
LinkList* Init_LinkList();
//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);//插入的数据为LinkNode*类型的
//删除
void Remove_LinkList(LinkList* list, int pos);
//查找
int Find_LinkList(LinkList* list, LinkNode* data,COMPARENODE compare);
//返回链表大小
int Size_LinkList(LinkList* list);
//打印
void Printf_LinkList(LinkList* list, PRIENTFNODE printf);
//释放链表内存
void Free_LinkList(LinkList* list);
  1. 建立一个 LinkList.c 的源文件
#include"LinkList.h"



//初始化
LinkList* Init_LinkList()
{
    
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->head.next = NULL;
	list->size = 0;
	return list;
}


//插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data)//插入的数据为LinkNode*类型的
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>list->size)
	{
    
		pos = list->size;
	}
	//插入新节点
	LinkNode* pcurrent = &(list->head);//因为在LinkList.h中定义LinkList时，head不是指针类型，所以要转换成地址类型
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	//插入新结点
	data->next = pcurrent->next;
	pcurrent->next = data;
	list->size++;
}


//删除
void Remove_LinkList(LinkList* list, int pos)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>list->size)
	{
    
		return;
	}
	//辅助结点
	LinkNode* pcurrent = &(list->head);
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	//删除结点
	pcurrent->next = pcurrent->next->next;
	list->size--;

}


//查找
int Find_LinkList(LinkList* list, LinkNode* data, COMPARENODE compare)
{
    
	if (list == NULL)
	{
    
		return;
	}
	if (data == NULL)
	{
    
		return;
	}
	LinkNode* pcurrent = list->head.next;
	int index = 0;
	while (pcurrent != NULL)
	{
    
		if (compare(pcurrent, data) == 0)
		{
    
			break;
		}
		pcurrent = pcurrent->next;
		index++;
	}
	return index;
}


//返回链表大小
int Size_LinkList(LinkList* list)
{
    
	return 0;
}


//打印
void Printf_LinkList(LinkList* list, PRIENTFNODE printf)
{
    
	if (list == NULL)
	{
    
		return;
	}
	//辅助指针
	LinkNode* pcurrent = list->head.next;
	while (pcurrent != NULL)
	{
    
		printf(pcurrent);
		pcurrent = pcurrent->next;
	}
}


//释放链表内存
void Free_LinkList(LinkList* list)
{
    
	if (list == NULL)
	{
    
		return;
		free(list);
	}
}
  1. 建立一个 03企业链表.c 的源文件，进行测试
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkList.h"

typedef struct PERSON
{
    
	LinkNode node;
	char name[21];
	int age;
}person;
void myprintf(LinkNode* data)
{
    
	person* p = (person*)data;
	printf("姓名：%s 年龄：%d\n", p->name, p->age);
}
int main()
{
    
	//创建链表
	LinkList* list = Init_LinkList();
	//创建数据
	/*person p1 = { "张三",18 }; person p2 = { "李四",19 }; person p3 = { "王五",17 };*/   //不能这样写，因为person还有定义个node

	person p1, p2, p3;
	strcpy(p1.name, "张三");
	strcpy(p2.name, "李四");
	strcpy(p3.name, "王五");
	p1.age = 18;
	p2.age = 17;
	p3.age = 19;
	//将节点插入链表
	Insert_LinkList(list, 0, (LinkNode*)&p1);
	Insert_LinkList(list, 0, (LinkNode*)&p2);
	Insert_LinkList(list, 0, (LinkNode*)&p3);
	
	
	//打印
	Printf_LinkList(list, myprintf);

	//删除结点
	Remove_LinkList(list, 1);
	printf("删除1位置的结点后链表元素为：\n");
	Printf_LinkList(list, myprintf);
	//释放链表内存
	Free_LinkList(list);
}

结果：

姓名：王五 年龄：19
姓名：李四 年龄：17
姓名：张三 年龄：18
删除1位置的结点后链表元素为：
姓名：王五 年龄：19
姓名：张三 年龄：18

循环链表的设计与实现

在这里插入图片描述
示例：

  1. 建立一个 CircleLinkList.h 头文件
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define CIRCLELINKLIST_TRUE 1 //宏定义
#define CIRCLELINKLIST_FALSE 0

typedef struct CIRCLELINKNODE
{
    
	struct CIRCLELINKNODE* next;
	
}CircleLinkNode;
typedef struct CIRCLELINKLIST
{
    
	CircleLinkNode head;
	int size;
}CirecleLinkList;

typedef int(*COMPARENODE)(CircleLinkNode*, CircleLinkNode*);//比较回调

typedef void(*PRINTFNODE)(CircleLinkNode*);//打印回调

//编写针对链表结构体操作的API函数

//初始化函数
CirecleLinkList* Init_CircluLinkList();
//插入函数
void Insert_CircluLinkList(CirecleLinkList* clist, int pos, CircleLinkNode*data);
//获得第一个元素
CircleLinkNode* Front_CircleLinkList(CirecleLinkList* clist);
//根据位置删除元素
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos);
//根据值删除元素
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode*data,COMPARENODE compare);
//获得链表的长度
int Size_CircleLinkList(CirecleLinkList* clist);
//判断是否为空
int IsEmpty_CircleLinkList(CirecleLinkList* clist);
//查找
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare);
//打印结点
void Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print);
//释放内存
void FreeSpace_CircleLinkList(CirecleLinkList* clist);
  1. 建立一个 CircleLinkList.c 源文件
#include "CircleLinkList.h"

//初始化函数
CirecleLinkList* Init_CircluLinkList()
{
    
	CirecleLinkList* clist = (CirecleLinkList*)malloc(sizeof(CirecleLinkList));
	clist->size = 0;
	clist->head.next = &(clist->head);
	return clist;
}


//插入函数
void Insert_CircluLinkList(CirecleLinkList* 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* Front_CircleLinkList(CirecleLinkList* clist)
{
    
	
	return clist->head.next;
}


//根据位置删除元素
void RemovByPos_CircleLinkList(CirecleLinkList* clist, int pos)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	if (pos<0 || pos>clist->size)
	{
    
		return;
	}
	CircleLinkNode* pcurrent = &(clist->head);
	for (int i = 0; i < pos; i++)
	{
    
		pcurrent = pcurrent->next;
	}
	//缓存当前节点的下一个结点，即需要删除的结点
	CircleLinkNode* pnext = pcurrent->next;
	pcurrent->next = pnext->next;
	clist->size--;
}


//根据值删除元素
void RemoveByValue_CircleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	if (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;
			break;
		}
		pprev=pcurrent;
		pcurrent = pprev->next;
	}
	clist->size--;

}


//获得链表的长度
int Size_CircleLinkList(CirecleLinkList* clist)
{
    
	return clist->size;
}


//判断是否为空
int IsEmpty_CircleLinkList(CirecleLinkList* clist)
{
    
	if (clist->size == 0)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}


//查找
int Find_CiecleLinkList(CirecleLinkList* clist, CircleLinkNode* data, COMPARENODE compare)
{
    
	if (clist == NULL)
	{
    
		return -1;
	}
	if (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 Printf_CircleLinkList(CirecleLinkList* clist, PRINTFNODE print)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	//辅助指针变量
	CircleLinkNode* pcurrent = clist->head.next;
	for (int i = 0; i < clist->size; i++)//打印两遍的话得乘2，还需要判断一下，是否为头结点（因为是循环链表）
	{
    
		if (pcurrent == &(clist->head))
		{
    
			pcurrent = pcurrent->next;//判断如果为头结点 则指向下一个结点，因为头结点没有存放数据
			printf("-----------------------\n");
		}
		print(pcurrent);
		pcurrent = pcurrent->next;
	}
}


//释放内存
void FreeSpace_CircleLinkList(CirecleLinkList* clist)
{
    
	if (clist == NULL)
	{
    
		return;
	}
	free(clist);
}
  1. 建立一个 01循环链表.c 的源文件，进行功能测试
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"CircleLinkList.h"



typedef struct PERSON
{
    
	CircleLinkNode node;
	char name[21];
	int age;
	int score;
}person;

void myprintf(CircleLinkNode* data)//回调函数的编写
{
    
	person* p = data;
	printf("姓名：%s 年龄：%d 成绩：%d\n", p->name, p->age, p->score);
}

int mycompare(CircleLinkNode* data1, CircleLinkNode* data2)
{
    
	person* p1 = data1;
	person* p2 = data2;
	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age&&p1->score == p2->score)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}
int main()
{
    
	//创建循环列表
	CirecleLinkList* clist = Init_CircluLinkList();

	person p1, p2, p3,p4,p5;
	strcpy(p1.name, "张三");
	strcpy(p2.name, "李四");
	strcpy(p3.name, "王五");
	strcpy(p4.name, "刘六");
	strcpy(p5.name, "陈七");
	p1.age = 20;
	p2.age = 18;
	p3.age = 21;
	p4.age = 19;
	p5.age = 22;
	p1.score = 98;
	p2.score = 97;
	p3.score =99;
	p4.score = 87;
	p5.score = 90;

	//插入,数据入链表
	Insert_CircluLinkList(clist,100, (CircleLinkNode*)&p1);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p2);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p3);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p4);
	Insert_CircluLinkList(clist, 100, (CircleLinkNode*)&p5);

	//打印
	Printf_CircleLinkList(clist, myprintf);


	//根据值删除
	/*person pdel; strcpy(pdel.name, "王五"); pdel.age = 21; pdel.score = 99; RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&pdel, mycompare);*/ //==

	RemoveByValue_CircleLinkList(clist, (CircleLinkNode*)&p3, mycompare); //==
	printf("删除后的链表为：\n");
	Printf_CircleLinkList(clist, myprintf);
	//释放内存
	FreeSpace_CircleLinkList(clist);

	return 0;
}

结果：

姓名：张三 年龄：20 成绩：98
姓名：李四 年龄：18 成绩：97
姓名：王五 年龄：21 成绩：99
姓名：刘六 年龄：19 成绩：87
姓名：陈七 年龄：22 成绩：90
删除后的链表为：
姓名：张三 年龄：20 成绩：98
姓名：李四 年龄：18 成绩：97
姓名：刘六 年龄：19 成绩：87
姓名：陈七 年龄：22 成绩：90

约瑟夫问题——循环链表的典型应用

在这里插入图片描述
在这里插入图片描述
示例：

  1. 建立一个 CircleLinkList.h 的头文件
    如上： 循环链表所示
  2. 建立一个 CircleLinkList.c 的源文件
    如上：循环链表所示
  3. 建立一个 02约瑟夫问题.c 的源文件，进行主函数的编写
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "CircleLinkList.h"
#define M 8
#define N 3


typedef struct MYNUM
{
    
	CircleLinkNode node;
	int value;
}mynum;

void myprintf(CircleLinkNode* data)
{
    
	mynum* num = (mynum*)data;
	printf("%d ", num->value);
}
void mycompare(CircleLinkNode*data1, CircleLinkNode* data2)
{
    
	mynum* num1 = data1;
	mynum* num2 = data2;
	if (num1->value == num2->value)
	{
    
		return CIRCLELINKLIST_TRUE;
	}
	return CIRCLELINKLIST_FALSE;
}

int main()
{
    
	CirecleLinkList* clist = Init_CircluLinkList();
	//链表插入数据
	mynum num[M];
	for (int i = 0; i < M; i++)
	{
    
		num[i].value= i + 1;
		Insert_CircluLinkList(clist, i,(CircleLinkNode*)&num[i]);
	}

	//打印
	Printf_CircleLinkList(clist, myprintf);
	printf("\n");

	int index = 1;
	//辅助指针
	CircleLinkNode* pcurrent = clist->head.next;
	while (Size_CircleLinkList(clist) > 1)
	{
    
		if (index == N)
		{
    
			mynum* tempnum = (mynum*)pcurrent;
			printf("%d ", tempnum->value);
			//缓存待删除结点的下一个结点
			CircleLinkNode* pnext = pcurrent->next;
			//根据值删除
			RemoveByValue_CircleLinkList(clist, pcurrent, mycompare);
			pcurrent = pnext;
			if (pcurrent == &(clist->head))
			{
    
				pcurrent = pcurrent->next;
			}
			index = 1;
		}
		pcurrent = pcurrent->next;
		if (pcurrent == &(clist->head))
		{
    
			pcurrent = pcurrent->next;
		}

		index++;
	}
	if (Size_CircleLinkList(clist) == 1)
	{
    
		mynum* tempnum=(mynum*)Front_CircleLinkList(clist);
		printf("%d ", tempnum->value);
	}
	else
	{
    
		printf("出错！！！");
	}
	//释放
	FreeSpace_CircleLinkList(clist);

}

结果：

1 2 3 4 5 6 7 8
3 6 1 5 2 8 4 7
原网站

版权声明
本文为[敏儿好xun]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_44921148/article/details/125493110

边栏推荐

猜你喜欢

随机推荐