循环链表：拉丁方阵问题

迈不过友情╰ 2022-06-01 02:50 184阅读 0赞

# 拉丁方阵问题介绍 #

**拉丁方阵是一种n×n的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，并且每种元素在一行和一列中 恰好出现一次**。著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号，拉丁方阵因此而得名。例如下面是一个3×3的拉丁方阵:

1 2 3

2 3 1

3 1 2

# 拉丁方阵问题分析 #

矩阵的第一行是 1 2 3 从第一个元素开始到最后一个元素。

矩阵的第二行是 2 3 1 从第二个元素开始到 循环1圈的最后一个元素。

矩阵的第三行是 1 2 3 从第三个元素开始到 循环1圈的最后一个元素。

不难找出**规律：矩阵的第n行，元素是从第n个元素 循环遍历完一圈的数据**。

那我们自己推导2  5  8  10的拉丁方阵是

2 5 8 10

5 8 10 2

8 10 2 5

10 2 5 8

符合拉丁方阵的要求吧。

**从代码角度来实现，主要思路如下**：

**1、用循环链表来接受n个不同的数据。**

**2、矩阵第i行数据，是从循环链表的第i个位置的数据遍历完整个循环链表 将其数据取出。**

# 拉丁方阵代码展示 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #define OK 1
    #define ERROR 0
    
    typedef struct Node
    {
    	int data;
    	struct Node* next;
    } Node, *LinkList;
    /*
    创建循环链表
    */
    int CreatCircleList(Node** circle_list,int n)
    {
    	
    	printf("请输入%d个不同的数字：",n);
    	int i = 0;
    	//创建头结点
    	Node* head = (Node*)malloc(sizeof(Node));
    	Node* temp = head;//temp 移动指针，刚开始指向头结点
    	while (i < n)
    	{
    		int data=0;
    		scanf("%d",&data);
    		//创建结点并初始化数据
    		Node* node = (Node*)malloc(sizeof(Node));
    		node->data = data;
    		node->next = NULL;
    		//将结点添加到循环链表中
    		temp->next = node;
    		temp = node;
    
    		i++;
    	}
    	//循环结束 temp指向最后一个结点,让其指向第一个结点，形参循环列表
    	temp->next = head->next;
    	//循环链表指向第一个结点
    	*circle_list = head->next;
    	//释放头结点
    	free(head);
    	return OK;
    
    }
    //获取循环链表长度
    int LengthCircleList(Node* circle_list)
    {
    	if (circle_list == NULL)
    	{
    		return 0;
    	}
    	int i = 1;
    	Node* node = circle_list;//node为移动指针，node 开始指向循环链表第一个结点
    	//循环链表遍历完判断，尾结点的指针域指向第一个结点
    	while (node->next != circle_list)
    	{
    		node = node->next;
    		i++;
    	}
    	return i;
    }
    /*
    显示拉丁方阵
    */
    int ShowLatin(Node* latin_list)
    {
    	int len = LengthCircleList(latin_list);
    	Node* first = latin_list;
    	for (size_t i = 0; i < len; i++)
    	{
    		Node* node = first;
    		int j = 0;
    		/*
    		找到开始结点
    		第一行 开始结点为 循环链表第1个位置结点
    		第二行 开始结点为 循环链表第2个位置结点
    		第N 行 开始结点为 循环链表第n个位置结点
    		*/
    		while(j < i)
    		{
    			node = node->next;
    			j++;
    		}
    		Node * begin = node;
    		int k = 0;
    		//遍历完这个循环列表
    		while(k<len)
    		{
    			printf("%d\t",begin->data); 
    			begin = begin->next;
    			k++;
    		}
    		printf("\n");
    		
    	}
    
    	return OK;
    }
    //销毁链表释放内存
    int DestroyCricleList(Node* circle_list)
    {
    	if (circle_list == NULL)
    	{
    		return ERROR;
    	}
    	Node* node = circle_list;//node为移动指针，node 开始指向循环链表第一个结点
    	//循环链表遍历完判断，尾结点的指针域指向第一个结点
    	while (node->next!= circle_list)
    	{
    		Node* temp = node;
    		node = node->next;
    		free(temp);
    	}
    	//释放最后一个结点
    	free(node);
    	return OK;
    }
    
    
    int main(int argc, char *argv[])
    {
    	Node* circle_list = NULL;
    	while (1)
    	{
    		printf("请输入拉丁方阵的阶数(0退出)：");
    		int n = 0;
    		scanf("%d", &n);
    		if (n == 0)
    		{
    			break;
    		}
    		CreatCircleList(&circle_list,n);
    		ShowLatin(circle_list);
    		DestroyCricleList(circle_list);
    	}
    	circle_list = NULL;
    	return 0;
    }

# 拉丁方阵结果展示 #

![SouthEast][]

[SouthEast]: /images/20220601/d904ac66d4e045709ee537346005a402.png