前言

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

员工储存

题目

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

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

解答

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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;
}
}
}

运行结果

res1
res1

约瑟夫环

题目

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

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

解答

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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);
}

运行结果

res2
res2