软件技术基础第三次实验

先放工程文件内容

• 第一个实验提取密码：dkl8。
• 第二个实验提取密码：q2ea。

第一个实验代码

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#pragma warning(disable:4996)
typedef struct student//结构体本体
{
	int elem;
	char num;
	struct student *next;
}link;
link * creatLink(int * initelem, int len) //头插法初始化链表
{
	int i;
	//最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H
	link *H = (link*)malloc(sizeof(link));
	H->elem = initelem[0];
	H->next = NULL;
	//如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前
	for (i = 2; i < len*2; i++) 
	{
		link * a = (link*)malloc(sizeof(link));
		a->elem = initelem[i];
		//插入元素时，首先将插入位置后的链表链接到新结点上
		scanf_s("%c", &(a->num));
		a->next = H;
		//然后再链接头指针 H
		H = a;
	}
	return H;
}
void display(struct student *p) //打印函数
{
	while (((p->elem) > 1) && ((p->elem) = 1)) {
		printf("%c", p->num);
		p = p->next;
	}
	printf("\n");
}
int Length(struct student * L)//表长统计函数
{
	int len = 0; //统计表长
	struct student *p = L;
	while (p->next != NULL) {
		p = p->next;
		len = len + 1;
	}
	return len/2;
}
int main(void)
{
	int a, i;
	int elem[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
	printf(" 栈长度：");
	scanf("%d", &i);
	link *Head = creatLink(elem, i + 1);//建立动态存储链表
	printf("\n结构体总长度：%d\n", Length(Head));//调用长度统计函数
	if (Head->next == NULL)
		printf("空\n");
	else
		printf("非空\n");//判断单链表是否为空
	display(Head);//调用输出函数
	free(Head);//释放栈
	system("pause");
	return 0;
}

第二个实验代码

// 队列（链队列）还有，这不是我的原创代码，但我稍微改了改，并补充了注释。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>
#pragma warning(disable:4996)

#define OK 1      // 执行成功
#define ERROR 0   // 执行失败
#define TRUE 1    // 返回值为真
#define FALSE 0   // 返回值为假

typedef int Status; // 函数返回结果类型


typedef struct QNode // 队列节点
{
	char data; // 元素值
	struct QNode *next; // 指向下一个节点的指针
} QNode, *QueuePtr;

typedef struct // 链队列结构
{
	QueuePtr front, rear; // 队头指针、队尾指针
} LinkQueue;

Status InitQueue(LinkQueue *Q) // 初始化队列
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));// 为队头和队尾指针分配内存
	if (!Q->front || !Q->rear) // 内存分配失败，结束程序
	{
		exit(OVERFLOW);
	}
	Q->front->next = NULL; // 队头节点指向NULL
	return OK;
}

Status DestroyQueue(LinkQueue *Q) // 销毁队列
{
	
	while (Q->front) // 当队列中还有元素的情况
	{
		Q->rear = Q->front->next;// 队尾指针指向队头指针的下一个元素
		free(Q->front); // 释放队头指针所在节点
		Q->front = Q->rear; // 队头指针指向队尾指针（即原来的下一个元素）
	}
	return OK;
}

Status ClearQueue(LinkQueue *Q) // 清空队列
{
	QueuePtr p, q; // p用来遍历队列节点，q用来指向被删除的节点

	Q->rear = Q->front; // 队尾指针指向队头指针
	p = Q->front->next; // p指向队头指针的下一个节点
	Q->front->next = NULL; // 队头指针的下一个节点指向NULL（表示删除之后的所有元素）
	while (p) // 当队列中还有元素，释放头节点之后的所有节点
	{
		q = p; // q节点指向被删除节点
		p = p->next; // p指向队列的下一个节点
		free(q); // 释放q节点
	}
	return OK;
}

Status QueueEmpty(LinkQueue Q)// 判断队列是否为空
{
	if (Q.front == Q.rear) // 头指针和尾指针位置相等，队列为空
	{
		return TRUE;
	}
	else 
	{
		return FALSE;
	}
}

int QueueLength(LinkQueue Q) // 统计队列长度
{
	int i = 0; // 用于统计队列长度的计数器
	QueuePtr p; // 用于遍历队列的元素
	p = Q.front; // p指向队头节点
	while (p != Q.rear) // 当p没有移动到队尾指针位置
	{
		i++; // 计数器加1
		p = p->next; // p移动到队列的下一个节点
	}
	return i/2; // 返回队列长度
}

Status GetHead(LinkQueue Q, char *e) // 获取队列头元素
{
	QueuePtr p;
	if (Q.front == Q.rear) // 队列为空，获取失败
	{
		return ERROR;
	}
	p = Q.front->next; // p指向队列的第一个元素
	*e = p->data; // 将队列头元素的值赋值给e元素
	return OK;
}

Status EnQueue(LinkQueue *Q, char e) // 在队列的队尾处插入元素
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));// 给新节点分配空间
	if (!s) // 分配空间失败，结束程序
	{
		exit(OVERFLOW);
	}
	s->data = e; // 将值赋值给新节点
	s->next = NULL; // 新节点指向NULL
	Q->rear->next = s; // 队尾指针的下一个元素指向新节点
	Q->rear = s; // 队尾指针指向新节点（新节点成为队尾指针的指向的节点）
	return OK;
}

Status DeQueue(LinkQueue *Q, char *e) // 删除队头元素
{
	QueuePtr p; // 用于指向被删除节点	
	if (Q->front == Q->rear) // 队列为空，出队失败
	{
		return ERROR;
	}
	p = Q->front->next; // p指向队列的第一个元素
	*e = p->data; // 将队列头节点的值赋值给元素e
	Q->front->next = p->next; // 头指针的下一个节点指向下下个节点（跳过头节点）
	if (Q->rear == p) // 如果被删除节点是队尾指针指向的节点（删除后队列为空）
	{
		Q->rear = Q->front; // 队尾指针指向队头指针
	}
	free(p); // 释放队头节点
	return OK;
}

Status visit(char e) // 打印单个元素
{
	printf("%s",&e);
	return OK;
}

Status QueueTravel(LinkQueue Q) // 遍历队列中的元素
{
	QueuePtr p; // 用于遍历队列中的节点
	p = Q.front->next; // p指向头节点
	printf("[ ");
	while (p) // 当队列中还有元素
	{
		visit(p->data); // 打印当前节点的值
		p = p->next; // p移动到队列下一个位置
	}
	printf("]\n");
	return OK;
}
             /**写在主函数前的注释**/
/**所有的函数返回值均为执行状态确定函数是否执行成功**/
int main() 
{
	Status status; // 定义执行状态（所有的函数返回值均为这个数据结构）的结构类型
	int j,len; // j用来遍历，len用于设定链队长度
	char i; //i用来传递字符信息
	char e; //e用来临时储存输出字符信息
	LinkQueue Q; // 队列
	InitQueue(&Q); // 初始化队列
	printf("初始化队列后，队列是否为空？%s\n", QueueEmpty(Q) == TRUE ? "是" : "否");//确认初始化后队列为空
	/***开始向队列插入元素，并打印队列***/
	printf("请输入生成队列长度:"); scanf("%d", &len);
	printf("\n请输入队列元素\n");
	for (j = 1; j <= len*2; ++j) //向队列中插入len个元素
	{
		scanf("%c",&i);
		EnQueue(&Q, i); // 调用EnQueue函数依次将元素i插入队列
	}
	printf("插入%d个元素后队列的值为：",len);//输出队列
	QueueTravel(Q); // 遍历队列
	printf("队列的长度为：%d\n", QueueLength(Q)); // 获取队列长度并输出
	/*** 删除队列中的全部元素，并打印对应的值 ***/
	printf("开始删除元素：\n");
	for (j = 0; j < len*2; ++j) //在队列中出队len个元素
	{
		DeQueue(&Q, &e); // 删除队头元素，将值存到e中
		printf("元素%s出队\n", &e);
	}
	printf("%d个元素出队后，队列中的值为：",len);//全部出队后再输出
	QueueTravel(Q); // 遍历队列
	printf("队列的长度为：%d\n", QueueLength(Q));  // 获取队列长度
	/*** 清空队列元素，并释放头指针 ***/
	ClearQueue(&Q); // 清空队列元素
	printf("清空队列后，队列是否为空：%s\n", QueueEmpty(Q) == TRUE ? "是" : "否");
	printf("队列中的元素为：");
	QueueTravel(Q); // 遍历元素
	return 0;
}
/**唯一的BUG就是会在出队的时候输出锟斤拷，但依旧可以看到依次输出的a,b,c,d**/