作者：静净精时 | 来源：互联网 | 2023-09-23 20:41
算法是编程的灵魂，一直想研究一下算法，选了一本入门书《数据结构与算法分析--c语言描述》，空闲的时候翻一番，写一写。在3.2.6小节中有个多重表，百度了一下，可能比较简单，较少人实现--！，百度到的
算法是编程的灵魂，一直想研究一下算法，选了一本入门书《数据结构与算法分析--c语言描述》，空闲的时候翻一番，写一写。在3.2.6小节中有个多重表，百度了一下，可能比较简单，较少人实现- -！，百度到的一些博主的实现方法，定义的节点包含的信息较多且比较浪费空间，没有书上描述的那么简洁，所以自己实现了一下，建议先看下书里的内容：
情景：在一所有40000名学生和2500门课程的大学生需要生成两种类型的报告。第一个报告列出每个班的注册者，第二个报告列出每个学生注册的班级。
分析：常用的实现方法是使用二维数组。这样一个数组将有1亿项。平均大约一个学生注册三门课程，因此实际上有意义的数据只有120000项，大约占0.1%
解决办法：现在需要的是列出每个班级及每个班所包含的学生的表，也需要每个学生及其所注册的班级的表。如下图，我们把两个表合成一个表，使用多重表来实现
比如，为了列出C3班的所有学生，我们从C3开始通过向右行进而遍历其表。第一个单元属于学生S1。虽然不存在明显的信息，但是可以通过跟踪该生链表直达到该表表头，从而确定该生的信息。一旦找到该生信息，我们就转回到C3的表（在遍历该生的表之前，我们存储了我们在课程表中的位置）并找到可以确定属于S3的另外一个单元，我们继续并发现S4和S3也在班上。对任意一名学生，我们也可以用类似的方法确定该生注册的所有课程。
代码实现：
struct node;
typedef struct node * node_t;
//节点
struct node
{
node_t next_student;
node_t next_course;
};
//学生表头
struct student
{
char name_student[20];
node_t first_student;
};
//课程表头
struct course
{
char name_course[20];
node_t first_course;
};
说明：
1. 学生表头和课程表头包含对应的学生和课程信息，每个学生注册一门课程就产生一个节点，该节点即指向该学生注册的下一个节点，也指向该课程的下一个节点。
2. 如何获取学生表头/课程表头的信息，以下以打印s1学生(如下图)注册的课程为例来说明：
1).现在已知s1表头，通过表头可找到节点1
2).找到节点1，向右推进，可以找到课程的表头c1(可以通过判断next_student的参数判断节点是否为表头)
3).获取c1的信息：如上图，最后一个课程节点的next_course指向的只是课程表头c1中node_t结构体的起始位置，需要减去name_course的大小才能得到课程表头c1的起始位置(不知道为什么，name_course数组的大小应该是20字节，直接用课程最后一个节点next_course-20，得到的却不是c1的位置)，在本来代码中，是利用一个struct course类型的变量，然后算出一个偏移量offset = next_student - name_course[0]，然后用最后一个节点的next_course-offset就可以算出c1的位置了。
4).转回节点1，获取学生选的下一个课程的节点，然后依照上面的逻辑，继续获取该节点对应的课程信息，直到遍历完s1的链表。
#ifndef _MULTITABLE_H
#define _MULTITABLE_H
//struct node;
//typedef struct node node_t;
struct node;
typedef struct node * node_t;
typedef struct student * student_t;
typedef struct course *course_t;
//节点
struct node
{
node_t next_student;
node_t next_course;
};
//学生表头
struct student
{
char name_student[20];
node_t first_student;
};
//课程表头
struct course
{
char name_course[20];
node_t first_course;
};
#define COUNT_STUDENT 6
#define COUNT_COURSE 5
student_t g_student[COUNT_STUDENT];
course_t g_course[COUNT_COURSE];
char g_student_name[COUNT_STUDENT][20] = {"学生1", "学生2", "学生3", "学生4", "学生5", "学生6"};
char g_course_name[COUNT_COURSE][20] = {"课程1", "课程2", "课程3", "课程4", "课程5"};
/**
*@brief 初始化一个空的学生头
*
*/
student_t make_empty_head_student(student_t L);
/**
*@brief 初始化一个空的课程头
*
*/
course_t make_empty_head_course(course_t L);
/**
*初始化表头信息
*/
void init_linktable();
/**
*@brief 插入学生节点
*
*/
void insert_student_behind(node_t head, node_t inset_node);
/**
*@brief 插入课程节点
*
*/
void insert_course_behind(node_t head, node_t inset_node);
/**
*@brief 注册课程
*@param head_student:相应学生的头
*@param head_course: 相应课程的头
*/
bool register_course(student_t head_student, course_t head_course);
/**
*@brief 根据一个node节点查找对应的课程信息
*
*@param p:要查询的节点
*/
node_t find_course_head(node_t p);
/**
*@brief 打印学生的课程信息
*
*@param student_t:传入学生的表头
*/
void printf_student_choose_course(student_t head_student);
student_t malloc_student_node();
#endif
#include "multitable.h"
#include
#include
#include <string.h>
/**
*@brief 初始化一个空的学生头
*
*/
student_t make_empty_head_student(student_t L)
{
//if(L != NULL)
//delete_link(L);
L = malloc_student_node();
if(L == NULL)
{
return NULL;
}
memset(L->name_student, 0, 20);
L->first_student = (node_t)malloc(sizeof(struct node));
L->first_student->next_student = L->first_student;
L->first_student->next_course = NULL;
if(L->first_student == NULL)
{
free(L);
return NULL;
}
return L;
}
/**
*@brief 初始化一个空的课程头
*
*/
course_t make_empty_head_course(course_t L)
{
//if(L != NULL)
//delete_link(L);
L = (course_t)malloc(sizeof(struct course));
if(L == NULL)
{
return NULL;
}
memset(L->name_course, 0, 20);
L->first_course = (node_t)malloc(sizeof(struct node));
L->first_course->next_student = NULL;
L->first_course->next_course = L->first_course;
if(L->first_course == NULL)
{
free(L);
return NULL;
}
return L;
}
/**
*初始化表头信息
*/
void init_linktable()
{
int i = 0;
for(i = 0; i i)
{
g_student[i] = make_empty_head_student(g_student[i]);
strcpy(g_student[i]->name_student, g_student_name[i]);
}
for(i = 0; i i)
{
g_course[i] = make_empty_head_course(g_course[i]);
strcpy(g_course[i]->name_course, g_course_name[i]);
}
}
/**
*@brief 插入学生节点
*
*/
void insert_student_behind(node_t head, node_t insert_node)
{
if(head == NULL || insert_node == NULL)
{
return;
}
node_t p = head;
while(p->next_student != head)
{
p = p->next_student;
}
insert_node = p->next_student;
p->next_student = insert_node;
}
/**
*@brief 插入课程节点
*
*/
void insert_course_behind(node_t head, node_t insert_node)
{
if(head == NULL || insert_node == NULL)
{
return;
}
node_t p = head;
while(p->next_course != head)
{
p = p->next_course;
}
insert_node = p->next_course;
p->next_course = insert_node;
}
/**
*@brief 注册课程
*@param head_student:相应学生的头
*@param head_course: 相应课程的头
*/
bool register_course(student_t head_student, course_t head_course)
{
//if(head_student == NULL || head_course == NULL)
// return false;
node_t temp_node = (node_t)malloc(sizeof(struct node));
if(temp_node == NULL)
{
return false;
}
node_t p = head_student->first_student;
while(p->next_student != head_student->first_student)
{
p = p->next_student;
}
temp_node->next_student = p->next_student;
p->next_student = temp_node;
p = head_course->first_course;
while(p->next_course != head_course->first_course)
{
p = p->next_course;
}
temp_node->next_course = p->next_course;
p->next_course = temp_node;
return true;
}
/**
*@brief 根据一个node节点查找对应的头节点的课程信息
*
*@param p:要查询的节点
*/
node_t find_course_head(node_t p)
{
if(p == NULL)
{
return NULL;
}
while(p->next_student != NULL)
{
p = p->next_course;
}
return p;
}
/**
*@brief 打印学生的课程信息
*
*@param student_t:传入学生的表头
*/
void printf_student_choose_course(student_t head_student)
{
if(head_student == NULL)
{
return;
}
node_t p = head_student->first_student;
node_t temp_node = NULL;
course_t temp_course_head = NULL;
while(p->next_student != head_student->first_student)
{
temp_node = find_course_head(p->next_student);
//找到课程链表头，并计算头节点的开始位置，才能取到头节点的信息
long offest = (long)(g_course[0]->first_course) - (long)(g_course[0]->name_course);
temp_course_head = (course_t)(long(temp_node) - offest);
printf("###########course name:%s\n",temp_course_head->name_course);
p = p->next_student;
}
}
student_t malloc_student_node()
{
student_t p = (student_t)malloc(sizeof(struct student));
return p;
}
int main(int argc, char *argv[])
{
init_linktable();
register_course(g_student[0], g_course[0] );
register_course(g_student[0], g_course[2] );
register_course(g_student[0], g_course[3] );
register_course(g_student[1], g_course[0] );
register_course(g_student[1], g_course[1] );
register_course(g_student[1], g_course[1] );
register_course(g_student[1], g_course[2] );
register_course(g_student[2], g_course[0] );
register_course(g_student[2], g_course[1] );
register_course(g_student[2], g_course[2] );
printf_student_choose_course(g_student[0]);
printf_student_choose_course(g_student[1]);
printf_student_choose_course(g_student[2]);
return 0;
}
以上只是实现了学生注册课程表及打印学生所选课程的代码，未实现打印课程包含所包含的学生的函数。
效率分析：
使用循环链标节省空间但是要花费时间，在最坏的情况下，如果第一个学生注册了每一门课程，那么表中的每一项都要检测以确定该生的所有课程名(即遍历每个课程表，以查找表头的课程信息)。因为在本例中每个学生注册了每一门课程相对很少并且每门课程的注册学生也很少，最坏的情况是不可能发生的。
如果怀疑会产生问题，那么每一个(非表头)单元的节点就要有直接指向学生头和班的表头的指针(可改写结构体如下所示)。这将使空间的需求加倍，但是却简化和加速实现的过程。
//节点
struct node
{
struct student *student_head;
struct course *course_head;
node_t next_student;
node_t next_course;
};
//学生表头
struct student
{
char name_student[20];
node_t first_student;
};
//课程表头
struct course
{
char name_course[20];
node_t first_course;
};
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号