数据结构实验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);
}
运行结果
数据结构实验1--线性表
https://blog.loststar.tech/posts/e6fc5c45/