数据结构实验1--线性表

本系列文章广泛借鉴了各种教材和博客文章，由于完成时间比较久远，如果有遗漏标注的请联系我补充或删除解答。本文中解答仅供参考学习。

其他章节实验见：分类 - 数据结构 - Loststar’s blog

前言

数据结构是我大二（2018-2019学年第二学期）的一门课，本文和后续文章将把课程里的约30道实验题补全到博客。

员工储存

题目

​ 某软件公司大约有30名员工，每名员工有姓名、工号、职务等属性，每年都有员工离职和入职。

​ 把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印最新的员工名单。

解答

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MEMBER_NUMBER 30

int maxid = 0;

typedef struct member {
	char name[10];
	int id;
	char job[10];
}Member;

typedef struct company {
	Member* member;
	int length;
	int last;
}Company;

void printMembers(Company* company)
{
	for (int i = 0; i < company->last; i++)
	{
		printf("%s,%d,%s\n", company->member[i].name, company->member[i].id, company->member[i].job);
	}
	printf("*************************************\n");
}

void initCompany(Company* company)
{
	company->member = (Member*)malloc(MEMBER_NUMBER * sizeof(Member));
	company->length = MEMBER_NUMBER;
	company->last = 0;
}

int joinCompany(Company* company, char* name, char* job)
{
	if (company->last >= company->length)
	{
		printf("full");
		return -1;
	}
	else
	{
		strcpy(company->member[company->last].name, name);
		company->member[company->last].id = maxid + 1;
		strcpy(company->member[company->last].job, job);
		company->last += 1;
		maxid += 1;
		printMembers(company);
		return 0;
	}
}

int leaveCompany(Company* company, int id)
{
	if (company->last == 0)
	{
		printf("empty");
		return -1;
	}
	else
	{
		for (int i = 0; i < company->last; i++)
		{
			if (company->member[i].id == id)
			{
				for (int j = i + 1; j < company->last; j++)
				{
					company->member[j - 1] = company->member[j];
				}
				company->last -= 1;
				printMembers(company);
				return 0;
			}
		}
		printf("not found");
		return -1;
	}
}

int main()
{
	Company company;
	char joinname[10], joinjob[10];
	int leaveid;
	int choose;
	initCompany(&company);
	while (1)
	{
		printf("请选择：\n1.入职\n2.离职\n3.退出程序\n");
		scanf("%d", &choose);
		switch (choose)
		{
		case 1:
			printf("输入姓名：\n");
			scanf("%s", &joinname);
			printf("输入职位：\n");
			scanf("%s", &joinjob);
			joinCompany(&company, joinname, joinjob);
			break;
		case 2:
			printf("输入离职id：\n");
			scanf("%d", &leaveid);
			leaveCompany(&company, leaveid);
			break;
		case 3:
			return 0;
		default:
			break;
		}
	}
}

运行结果

约瑟夫环

题目

​ 约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。

​ 建立n个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。

解答

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define N 30

typedef struct node {
	int num;
	int pass;
	struct node* next;
}Node;

int randNumber(int max)
{
	srand((unsigned)time(NULL));
	return rand() % max + 1;
}

int m = randNumber(N * 3);

Node* initList()
{
	srand((int)time(0));
	Node* head = (Node*)malloc(sizeof(Node));
	head->num = 1;
	head->pass = randNumber(N * 3);
	Node* temp = head;
	for (int i = 1; i < N; i++)
	{
		Node* p = (Node*)malloc(sizeof(Node));
		p->num = i + 1;
		p->pass = randNumber(N * 3);
		temp->next = p;
		temp = temp->next;
	}
	temp->next = head; //末尾指向头部，构成单循环链表
	return head;
}

void playGame(Node* head)
{
	Node* temp1 = head, * temp2;
	while (head != head->next)
	{
		if (m == 1) //删除头结点
		{
			while (temp1->next != head)
			{
				temp1 = temp1->next;
			}
			temp2 = head;
			temp1->next = head->next;
			head = head->next;
			m = temp2->pass;
			printf("delete id:%d\n", temp2->num);
			free(temp2);
			//printList(head);
		}
		else
		{
			for (int i = 1; i < m - 1; i++)
			{
				temp1 = temp1->next;
			}
			temp2 = temp1->next;
			temp1->next = temp2->next;
			m = temp2->pass;
			head = temp1->next;
			printf("delete id:%d\n", temp2->num);
			free(temp2);
			//printList(head);
		}
	}
}

int main()
{
	printf("Number m=%d\n", m);
	Node* head = initList();
	//printList(head);
	playGame(head);
}

运行结果