实验一 -1-2：利用单链表实现职工信息的综合运算。

线性结构典型算法的实现

一、实验目的及要求

1.掌握线性表的顺序表示与实现

2.掌握线性表的链式表示与实现

3.掌握线性表的插入、删除、查找、排序、合并等操作

4.加深对线性表的理解，逐步培养解决实际问题的能力

二、实验内容

1.实现单链表存储及其基本操作，完成课本73-74页实验题2后，按要求：将线性链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，以此类推。

2.利用单链表实现职工信息的综合运算。

三、实验设备与环境

Windows 11系统

Codeblocks

四、实验设计方案

任务一设计步骤：

任务二设计步骤：

1.建立一个带头结点的单链表L。

使用文件输入流来读取文件中的记录，并将其添加到链表中。由于链表需要带头结点，在程序开始时先创建一个空头结点。

2.输入一个职工记录。

可以使用键盘输入或者其他方式接收用户输入的职工记录，并将其添加到链表的尾部。

3.显示所有职工记录。

使用循环遍历链表中的每个节点，并输出每个节点的信息。

4.按编号no对所有职工记录进行递增排序。

使用选择排序或插入排序等算法对链表进行排序。排序后，需要将链表重新链接，使其成为一个有序链表。

5.按部门号depno对所有职工记录进行递增排序。

同样可以使用选择排序或插入排序等算法对链表进行排序。排序后，需要将链表重新链接，使其成为一个有序链表。

6.按工资数salary对所有职工记录进行递增排序。

同样可以使用选择排序或插入排序等算法对链表进行排序。排序后，需要将链表重新链接，使其成为一个有序链表

7.删除指定职工号的职工记录。

使用链表遍历找到指定编号的节点，并将其从链表中删除。

8.删除职工文件中的全部记录。

使用文件输出流来写入空字符串或其他标记来删除文件中的所有记录。

10.将单链表L中的所有职工记录存储到职工文件中。

五、实验结果

任务一运行结果：

 任务二运行结果：

六、附录源码

任务一：

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	char data;
	struct LNode *next;
}LinkNode;

//1初始化链表
void InitList(LinkNode *&H){
	H=(LinkNode *)malloc(sizeof(LinkNode));
	H->next=NULL;
}

//2依次采用尾插法插入字符（即创建链表）
void CreateList(LinkNode *&H,char a[],int n){
	LinkNode *s,*r;
	H=(LinkNode *)malloc(sizeof(LinkNode));
	r=H;
	for(int i=0;i<n;i++){
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}

//3输出单链表L
void DispList(LinkNode *H){
	LinkNode *p=H->next;
	while(p!=NULL){
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}

//4输出单链表的长度
int ListLength(LinkNode *H){
	int n=0;
	LinkNode *p=H;
	while(p->next!=NULL){
		n++;
		p=p->next;
	}
	return n;
}

//5判断单链表h是否为空
bool ListEmpty(LinkNode *H){
	return(H->next==NULL);
}

//6输出单链表h的第三个元素
bool GetElem(LinkNode *H,int i,char &e){
	int j=0;
	if(i<1) return false;
	LinkNode *p=H;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL) return false;
	else{
		e=p->data;
		return true;
	}
}

//7输出元素a的位置
int LocateElem(LinkNode *L,char a){
	int i=1;
	LinkNode *p=L->next;
	while(p->data!='a' && p!=NULL){
		p=p->next;
		i++;
	}
	if(p==NULL) return(0);
	else return(i);
}

//8在第四个元素的位置上插入元素f
bool ListInsert(LinkNode *&H,int i,char e){
	int j=0;
	LinkNode *p=H,*s;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
}

//9输出单链表h（直接与三同理）

//10删除单链表h的第三个元素
bool ListDelete(LinkNode *&H,int i,char &e){
	int j=0;
	LinkNode *p=H,*q;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		q=p->next;
		if(q==NULL)
			return false;
		e=q->data;
		p->next=q->next;
		free(q);
		return true;
	}
}

//11输出单链表h（直接与三同理）

//12释放单链表h
void DestroyList(LinkNode *&H){
	LinkNode *pre=H,*p=p->next;
	while(p!=NULL){
		free(pre);
		pre=p;
		p=p->next;
	}
	free(pre);
}



int main(){
	LinkNode *H;
	//1初始化链表H
	printf(" (1)初始化顺序表h\n");
	InitList(H);
	//2依次插入元素a,b,c,d,e元素
	printf("\n (2)依次插入元素a,b,c,d,e元素\n");
	char a[5]={'a','b','c','d','e'};
	CreateList(H,a,5);
	//3输出链表H
	printf("\n (3)输出单链表h:");
	DispList(H);
	//4输出链表H的长度
	printf("\n (4)单链表h的长度:");
	ListLength(H);
	printf("长度为：%d \n",ListLength(H));
	//5判断H是否为空
	printf("\n (5)判断h是否为空:");
	ListEmpty(H);
	if(ListEmpty(H))
		printf("表为空\n");
	else
		printf("表非空\n");
	//6输出链表H的第三个元素
	printf("\n (6)输出单链表h的第三个元素:");
	char e;
	GetElem(H,3,e);
	printf("单链表h的第3个元素为:%c \n",e);
	//7输出元素a的位置
	printf("\n (7)元素a的位置:");
	LocateElem(H,'a');
	printf("%d\n",LocateElem(H,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n (8)在第4个元素的位置上插入元素f\n");

	ListInsert(H,4,'f');
	//9输出链表H
    printf("\n (9)输出单链表h:");
	DispList(H);
	//10删除链表H第三个元素
	printf("\n (10)删除h第3个元素");
	ListDelete(H,3,e);
	//11输出链表H
	printf("\n (11)输出单链表h:");
	DispList(H);
	//12释放链表H
	printf("\n (12)释放单链表h");
	DestroyList(H);
	return(0);
}

任务二：

#include <stdio.h>
#include <malloc.h>
typedef struct
{
	int no;						//职工号
	char name[10];				//姓名
	int depno;					//部门号
	float salary;				//工资数
} EmpType;						//职工类型

typedef struct node
{
	EmpType data;				//存放职工信息
	struct node *next;			//指向下一个结点的指针
}  EmpList;						//职工单链表结点类型

void DestroyEmp(EmpList *&L)	//释放职工单链表L
{
	EmpList *pre = L, *p = pre->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}

void DelAll(EmpList *&L)		//删除职工文件中全部记录
{
	FILE *fp;
	if ((fp = fopen("emp.dat", "wb")) == NULL)	//重写清空emp.dat文件
	{
		printf("  提示:不能打开职工文件\n");
		return;
	}
	fclose(fp);
	DestroyEmp(L);						//释放职工单链表L
	L = (EmpList *)malloc(sizeof(EmpList));
	L->next = NULL;						//建立一个空的职工单链表L
	printf("  提示:职工数据清除完毕\n");
}

void ReadFile(EmpList *&L)		//读emp.dat文件建立职工单键表L
{
	FILE *fp;
	EmpType emp;
	EmpList *p, *r;
	int n = 0;
	L = (EmpList *)malloc(sizeof(EmpList));	//建立头结点
	r = L;
	if ((fp = fopen("emp.dat", "rb")) == NULL) //不存在emp.dat文件
	{
		if ((fp = fopen("emp.dat", "wb")) == NULL)
			printf("  提示:不能创建emp.dat文件\n");
	}
	else		//若存在emp.dat文件
	{
		while (fread(&emp, sizeof(EmpType), 1, fp) == 1)
		{	//采用尾插法建立单链表L
			p = (EmpList *)malloc(sizeof(EmpList));
			p->data = emp;
			r->next = p;
			r = p;
			n++;
		}
	}
	r->next = NULL;
	printf("  提示:职工单键表L建立完毕,有%d个记录\n", n);
	fclose(fp);
}

void SaveFile(EmpList *L)	//将职工单链表数据存入数据文件
{
	EmpList *p = L->next;
	int n = 0;
	FILE *fp;
	if ((fp = fopen("emp.dat", "wb")) == NULL)
	{
		printf("  提示:不能创建文件emp.dat\n");
		return;
	}
	while (p != NULL)
	{
		fwrite(&p->data, sizeof(EmpType), 1, fp);
		p = p->next;
		n++;
	}
	fclose(fp);
	DestroyEmp(L);				//释放职工单链表L
	if (n > 0)
		printf("  提示:%d个职工记录写入emp.dat文件\n", n);
	else
		printf("  提示:没有任何职工记录写入emp.dat文件\n");
}

void InputEmp(EmpList *&L)	//添加一个职工记录
{
	EmpType p;
	EmpList *s;
	printf("  >>输入职工号(-1返回):");
	scanf("%d", &p.no);
	if (p.no == -1) return;
	printf("  >>输入姓名 部门号 工资:");
	scanf("%s%d%f", &p.name, &p.depno, &p.salary);
	s = (EmpList *)malloc(sizeof(EmpList));
	s->data = p;
	s->next = L->next;		//采用头插法插入结点s
	L->next = s;
	printf("  提示:添加成功\n");
}

void DelEmp(EmpList *&L)	//删除一个职工记录
{
	EmpList *pre = L, *p = L->next;
	int no;
	printf("  >>输入职工号(-1返回):");
	scanf("%d", &no);
	if (no == -1) return;
	while (p != NULL && p->data.no != no)
	{
		pre = p;
		p = p->next;
	}
	if (p == NULL)
		printf("  提示:指定的职工记录不存在\n");
	else
	{
		pre->next = p->next;
		free(p);
		printf("  提示:删除成功\n");
	}
}

void Sortno(EmpList *&L)	//采用直接插入法单链表L按no递增有序排序
{
	EmpList *p, *pre, *q;
	p = L->next->next;
	if (p != NULL)
	{
		L->next->next = NULL;
		while (p != NULL)
		{
			q = p->next;
			pre = L;
			while (pre->next != NULL && pre->next->data.no < p->data.no)
				pre = pre->next;
			p->next = pre->next;
			pre->next = p;
			p = q;
		}
	}
	printf("  提示:按no递增排序完毕\n");
}

void Sortdepno(EmpList *&L) //采用直接插入法单链表L按depno递增有序排序
{
	EmpList *p, *pre, *q;
	p = L->next->next;
	if (p != NULL)
	{
		L->next->next = NULL;
		while (p != NULL)
		{
			q = p->next;
			pre = L;
			while (pre->next != NULL && pre->next->data.depno < p->data.depno)
				pre = pre->next;
			p->next = pre->next;
			pre->next = p;
			p = q;
		}
	}
	printf("  提示:按depno递增排序完毕\n");
}

void Sortsalary(EmpList *&L) //采用直接插入法单链表L按salary递增有序排序
{
	EmpList *p, *pre, *q;
	p = L->next->next;
	if (p != NULL)
	{
		L->next->next = NULL;
		while (p != NULL)
		{
			q = p->next;
			pre = L;
			while (pre->next != NULL && pre->next->data.salary < p->data.salary)
				pre = pre->next;
			p->next = pre->next;
			pre->next = p;
			p = q;
		}
	}
	printf("  提示:按salary递增排序完毕\n");
}

void DispEmp(EmpList *L)	//输出所有职工记录
{
	EmpList *p = L->next;
	if (p == NULL)
		printf("  提示:没有任何职工记录\n");
	else
	{
		printf("    职工号  姓名  部门号       工资\n");
		printf("   ----------------------------------\n");
		while (p != NULL)
		{
			printf("  %3d%10s    %-8d%7.2f\n", p->data.no, p->data.name, p->data.depno, p->data.salary);
			p = p->next;
		}
		printf("   ----------------------------------\n");
	}
}

int main()
{
	EmpList *L;
	int sel;
	printf("由emp.dat文件建立职工单键表L\n");
	ReadFile(L);
	do
	{
		printf(">1:添加 2:显示 3:按职工号排序 4:按部门号排序 5:按工资数排序\n");
		printf(">6:删除 9:全删 0:退出 请选择:");
		scanf("%d", &sel);
		switch (sel)
		{
		case 9:
			DelAll(L);
			break;
		case 1:
			InputEmp(L);
			break;
		case 2:
			DispEmp(L);
			break;
		case 3:
			Sortno(L);
			break;
		case 4:
			Sortdepno(L);
			break;
		case 5:
			Sortsalary(L);
			break;
		case 6:
			DelEmp(L);
			break;
		}
	} while (sel != 0);
	SaveFile(L);
	return 1;
}