数据结构课程设计

提醒1：本篇所有内容已开源至gitee，项目地址：

提醒2：本篇篇幅极长，请点击右侧目录查看

提醒3：提醒1和提醒2是本篇课设的食用方法

一 线性结构 链表

Joseph环

任务：编号是1,2,…,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据：m的初值为20，n=7 ，7个人的密码依次为3，1，7，2，4，7，4，则正确的输出是什么？

要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列

提供的数据结构：

typedef struct Node
{
   int data;
   int password;
   struct Node *next;
}Node, *LinkList;

基本操作：初始化单链表；给每个人赋密码；确定需要处理的人数；确定开始的上限值；得到正确的顺序；输出结果。

import java.util.*

class Node(var value: Int, var password: Int) {
    var next: Node? = null
}

fun main(args: Array<String>) {
    println("请输入报数上限值m")
    var M: Int = Integer.valueOf(readLine())
    println("请输入人数n：")
    val N: Int = Integer.valueOf(readLine())
    //val data = intArrayOf(3, 1, 7, 2, 4, 7, 4) // 编写初期为了方便直接加入测试数据
    //var data = Array(N) { readLine()!!.split(' ').map { it.toInt() }.toIntArray() } // 此法读入后数据类型为IntArray，与所需Int不匹配
    var data = IntArray(N)
    println("请输入每个人持有的密码，以空格分隔：")
    val scan = Scanner(System.`in`) // 使用Java的Scanner类
    var i = 0
    data[i] = scan.nextInt()
    while(scan.hasNextInt())
    {
        i += 1
        data[i] = scan.nextInt()
    }
    val t = Node(1, data[0]) // 头结点单独拿出来，方便形成循环链表
    var x: Node? = t
    for (i in 2..N) x = Node(i, data[i - 1]).also { x!!.next = it } //建立单向链表
    x!!.next = t // 最后一个结点的next指向第一个节点，形成循环链表
    println("出列的顺序为：")
    while (x !== x!!.next) {
        for (i in 1 until M) x = x!!.next
        // 报数到M，此人出列
        print(x!!.next!!.value.toString() + " ")
        M = x.next!!.password // 上限更新为此人密码
        x.next = x.next!!.next
    }
    println()
    println("最后的获胜者是：" + x!!.value)
}

git项目中为应用到安卓的工程，您可以下载源代码参考

二 栈和队列

迷宫问题求解

任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

#include <iostream>
#include <graphics.h>
//#include <easyx.h>
#include <conio.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#define MAXNUM 3600
using namespace std;

struct Point {
	int x, y, sum;
	bool dirc[4]; // direction: [0]-up [1]-down [2]-left [3]-right
	char ch;
	bool visit[4];
	Point& operator=(Point& test) // 重载等号
	{
		x = test.x;
		y = test.y;
		sum = test.sum;
		ch = test.ch;
		for (int i = 0; i < 4; i++)
		{
			dirc[i] = test.dirc[i];
			visit[i] = test.visit[i];
		}
		return *this;
	}
}point[MAXNUM][MAXNUM];

typedef struct {
	Point base[MAXNUM];
	int top;
}Sqstack;


// 对话框交互
LRESULT CALLBACK CBTHookProc(int nCode, WPARAM wParam, LPARAM lParam)
{
	HWND hwnd = (HWND)wParam;
	if (nCode == HCBT_ACTIVATE)
	{
		SetDlgItemText(hwnd, IDYES, L"好的");
		SetDlgItemText(hwnd, IDNO, L"退出");
		SetDlgItemText(hwnd, IDOK, L"好的");
	}
	return 0;
}
int MyMessageBox(HWND hwnd, const TCHAR* szText, const TCHAR* szCaption, UINT uType)
{
	int ret;
	HHOOK hHook = SetWindowsHookEx(WH_CBT, CBTHookProc, nullptr, GetCurrentThreadId());
	ret = MessageBoxEx(hwnd, szText, szCaption, uType, MAKELANGID(LANG_ENGLISH, SUBLANG_ENGLISH_US));
	UnhookWindowsHookEx(hHook);
	return ret;
}

// 载入图片
IMAGE maze_wall, maze_ground, maze_path;
void _InitImage()
{
	loadimage(&maze_wall, _T("IMG"), _T("wall"));
	loadimage(&maze_ground, _T("IMG"), _T("ground"));
	loadimage(&maze_path, _T("IMG"), _T("path"));
}

// 栈相关操作函数
Sqstack InitStack() // 栈的初始化
{
	Sqstack S;
	S.top = -1;
	return S;
}

bool isEmpty(Sqstack S) // 判断栈空
{
	if (S.top == -1) return true;
	return false;
}

void PushIntoStack(Sqstack& S, Point x) // 入栈
{
	if (S.top == MAXNUM - 1)
	{
		/*MyMessageBox(0, TEXT("栈已满！"), TEXT("Warning!"), MB_OK | MB_SETFOREGROUND);
		exit(0);*/
		cout << "栈满！";
		return;
	}
	S.base[++S.top] = x;
}

void PopOutofStack(Sqstack& S) // 出栈
{
	if (S.top == -1)
	{
		cout << "栈空！";
		return;
	}
	S.top--;
}

Point GetStackTop(Sqstack S) // 取栈顶元素
{
	return S.base[S.top];
}

char Maze[MAXNUM][MAXNUM];
Sqstack S = InitStack();
int cnt = 0;
// 迷宫使用函数
void MazePrint(int n, int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cout << Maze[i][j];
		cout << endl;
	}
	//initgraph(n * 15, m * 15);
	//_InitImage();
	initgraph(m * 15, n * 15);
	//initgraph(m * 15, n * 15, SHOWCONSOLE);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			switch (Maze[i+1][j+1])
			{
			case '.':
				putimage(j * 15, i * 15, &maze_ground);
				break;
			case '#':
				putimage(j * 15, i * 15, &maze_wall);
				break;
			case '@':
				putimage(j * 15, i * 15, &maze_path);
				break;
			}
}

void GetMaze(int n, int m) // 输入迷宫
{
	cout << "请输入迷宫(.代表空地，#代表障碍：)" << endl;
	for(int i=1; i<=n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> point[i][j].ch;
			point[i][j].x = i;
			point[i][j].y = j;
			Maze[i][j] = point[i][j].ch;
		}
}

void InitMaze(int n, int m)
{
	int a[4] = { 1, -1, 0, 0 }, b[4] = { 0, 0, -1, 1 };
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			point[i][j].sum = 0;
			for (int k = 0; k < 4; k++)
			{
				if (point[i][j].ch == '.' && point[i + a[k]][j + b[k]].ch == '.')
				{
					point[i][j].dirc[k] = 1;
					point[i][j].visit[k] = 0;
					point[i][j].sum++;
				}
				else
				{
					point[i][j].dirc[k] = 0;
					point[i][j].visit[k] = 1;
				}
			}
		}
	}
}

void SeekBegin(int& x, int& y, int n, int m)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (Maze[i][j] == '.' && (i == 1 || i == n || j == 1 || j == m))
			{
				x = i;
				y = j;
				return;
			}
}

void SeekEnd(int& x, int& y, int n, int m)
{
	for (int i = n; i >= 1; i--)
		for (int j = m; j >= 1; j--)
			if (Maze[i][j] == '.' && (i == 1 || i == n || j == 1 || j == m))
			{
				x = i;
				y = j;
				return;
			}
}

void Solve(int n, int m)
{
	//int x = 1, y = 1;
	int x, y, xend, yend;
	SeekBegin(x, y, n, m);
	SeekEnd(xend, yend, n, m);
	PushIntoStack(S, point[x][y]);
	cnt++;
	if (isEmpty(S)) cout << "NULL";
	while (!isEmpty(S))
	{
		Point top = GetStackTop(S);
		if (!point[x][y].visit[0] && point[x][y].dirc[0])
		{
			point[x++][y].visit[0] = 1;
			point[x][y].visit[1] = 1;
			PushIntoStack(S, point[x][y]);
			cnt++;
		}
		else if (!point[x][y].visit[1] && point[x][y].dirc[1])
		{
		//cout << 1 << endl;
			point[x--][y].visit[1] = 1;
			point[x][y].visit[0] = 1;
			PushIntoStack(S, point[x][y]);
			cnt++;
		}
		else if (!point[x][y].visit[2] && point[x][y].dirc[2])
		{
			point[x][y--].visit[2] = 1;
			point[x][y].visit[3] = 1;
			PushIntoStack(S, point[x][y]);
			cnt++;
		}
		else if (!point[x][y].visit[3] && point[x][y].dirc[3])
		{
			point[x][y++].visit[3] = 1;
			point[x][y].visit[2] = 1;
			PushIntoStack(S, point[x][y]);
			cnt++;
		}
		else if (point[x][y].visit[0] && point[x][y].visit[1] && point[x][y].visit[2] && point[x][y].visit[3])
		{
			PopOutofStack(S);
			if (isEmpty(S))
			{
				cout << "No way." << endl;
				(MyMessageBox(0, TEXT("找不到路了啦！"), TEXT("呜呜呜"), MB_OK | MB_SETFOREGROUND));
				break;
			}
		}
		x = GetStackTop(S).x;
		y = GetStackTop(S).y;
		//if (point[x][y].x == n || point[x][y].y == m)
		if (point[x][y].x == xend && point[x][y].y == yend)
		{
			cout << "Success" << endl;
			while (!isEmpty(S))
			{
				Point anspr; // ansprint
				anspr.x = GetStackTop(S).x;
				anspr.y = GetStackTop(S).y;
				PopOutofStack(S);
				Maze[anspr.x][anspr.y] = '@';
			}
			(MyMessageBox(0, TEXT("找到走法并绘制完成！"), TEXT("乌拉！"), MB_OK | MB_SETFOREGROUND));
			MazePrint(n, m);
			//cout << cnt << endl;
			break;
		}
	}
}

int main()
{
    //std::cout << "Hello World!\n";
	if (MyMessageBox(0, TEXT("请输入60*60以内大小的迷宫"), TEXT("Hello!"), MB_YESNO | MB_SETFOREGROUND) == IDYES)
	{
		//initgraph(750, 750);
		//fill(point[0], point[0] + MAXNUM * MAXNUM, '#');
		_InitImage();
		memset(point, '#', sizeof(point));
		int n, m;
		cout << "请输入行数和列数：" << endl;
		cin >> n >> m;
//initgraph(n * 15, m * 15, SHOWCONSOLE);
		while (n > 60 || m > 60 || n < 0 || m < 0)
		{
			MyMessageBox(0, TEXT("请重新输入！"), TEXT("Bia!"), MB_OK | MB_SETFOREGROUND);
			cout << "请重新输入行数和列数：" << endl;
			cin >> n >> m;
		}
		GetMaze(n, m);
		InitMaze(n, m);
		//MazePrint(n, m);
		Solve(n, m);
		system("pause");
		closegraph();
	}
	return 0;
}

三 树型结构

家谱

采用树型结构实现如下系统功能：

1)输入文件以存放最初家谱中各成员的信息。 成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）也可附加其它信息、但不是必需的。
2)实现数据的存盘和读盘。
3)以图形方式显示家谱。
4)显示第n代所有人的信息。
5)按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。
6)按照出生日期查询成员名单。
7)输入两人姓名，确定其关系。
8)某成员添加孩子。
9)删除某成员（若其还有后代，则一并删除）。
10)修改某成员信息。
11)按出生日期对家谱中所有人排序。
12)打开一家谱时，提示当天生日的健在成员。

测试要求：

1)建立至少10个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。
2)对界面的要求是：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

generation.h

#pragma once
typedef struct Infomation {
    char name[20]; // 姓名
    char sex; // 性别，M男F女
    char birth[10]; // 出生日期
    bool wedding; // 婚否 1是0否
    char address[20]; // 地址
    bool alive; // 健在 1是0否
    char death[10]; // 死亡日期，先决条件：alive
}Info;
typedef struct binode {
    Info person;
    struct binode* lc, * rc;
}BitNode, *BiTree;

void newLeft(BiTree& p, Info One); // 添加左孩子
void newRight(BiTree& p, Info One); // 添加右孩子
BiTree createTree(Info Human[]); // 建树

void outputTitle(); // 输出信息
void outputInfo(BiTree p); // 输出结点

void levelTrav(BiTree Tree); // 层次遍历
void showNGene(BiTree p, int n); // 显示第n代所有人的信息
void showFamily(BiTree Tree); // 显示整个家谱

// 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）
BiTree findParent(BiTree BT, BitNode* p); // 找到结点父亲
BiTree searchName(BiTree BT, char* str); // 按照姓名查询
void findChild(BiTree p, BiTree* child); // 找到结点孩子
void searchThreeGeneration(BiTree Tree); // 三代查询

// 按照出生日期查询成员名单
BiTree findBirthday(BiTree BT, char* birth); // 按照出生日期查询
void searchBirthday(BiTree Tree); // 查询成员

// 输入两人姓名，确定其关系
bool isSameFather(BiTree BT, BitNode* p, BitNode* q); // 判断是否具有共同父亲
void judgeRelationship(BiTree Tree); // 确定两个人的关系

void addChild(BiTree& Tree); // 某成员添加孩子
void deletePerson(BiTree& Tree); //删除某成员
void updateInfo(BiTree Tree); // 修改某成员信息

// 按出生日期对家谱中所有人排序
void transportBirth(BiTree BT, char bir[][20], int& i); // 生日信息
void sortBirthday(BiTree Tree, int n); // 排序

generation.cpp

#include "generation.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>

void newLeft(BiTree& p, Info One)
{
    BitNode* q = new BitNode;
    q->person = One;
    q->lc = q->rc = NULL;
    p->lc = q;
}

void newRight(BiTree& p, Info One)
{
    BitNode* q = new BitNode;
    q->person = One;
    q->lc = q->rc = NULL;
    p->rc = q;
}

BiTree createTree(Info Human[])
{
    BiTree Bt;
    Bt = new BitNode;
    Bt->person = Human[0];
    Bt->lc = Bt->rc = NULL;
    newLeft(Bt, Human[1]);
    newRight(Bt, Human[2]);
    newLeft(Bt->lc, Human[3]);
    newRight(Bt->lc, Human[4]);
    newLeft(Bt->rc, Human[5]);
    newRight(Bt->rc, Human[6]);
    newLeft(Bt->lc->lc, Human[7]);
    newRight(Bt->lc->lc, Human[8]);
    newLeft(Bt->lc->rc, Human[9]);
    newRight(Bt->lc->rc, Human[10]);
    newRight(Bt->rc->lc, Human[11]);
    return Bt;
}

void outputTitle()
{
    //printf("姓名     性别 出生日期    婚否    地址    健在  死亡日期\n");
    printf("%-10s", "姓名");
    printf("%-5s", "性别");
    printf("%-10s", "出生日期");
    printf("%-5s", "婚否");
    printf("%-12s", "地址");
    printf("%-5s", "健在");
    printf("%s\n", "死亡日期");
}

void outputInfo(BiTree p)
{
    if (p)
    {
        printf("%-10s", p->person.name);
        //printf("%-5c", p->person.sex);
        if (p->person.sex == 'M')
            printf("%-6s", "男");
        else
            printf("%-6s", "女");
        printf("%-10s", p->person.birth);
        //printf("%-5d", p->person.wedding);
        if (p->person.wedding)
            printf("%-6s", "是");
        else
            printf("%-6s", "否");
        printf("%-12s", p->person.address);
        //printf("%-5d", p->person.alive);
        if (p->person.alive)
            printf("%-6s", "是");
        else
            printf("%-6s", "否");
        printf("%s\n", p->person.death);
    }
    else printf("查无此人\n");
}

void levelTrav(BiTree Tree)
{
    BiTree Q[20];
    int front = 0, rear = 0;
    outputTitle();
    //printf("姓名        性别      出生日期     婚否      地址      健在       死亡日期\n");
    if (Tree)
    {
        rear++;
        Q[rear] = Tree;
        while (front != rear)
        {
            front = (front + 1) % 20;
            BitNode* p = Q[front];
            outputInfo(p);
            if ((rear + 1) % 20 != front && p->lc != NULL)
            {
                rear = (rear + 1) % 20;
                Q[rear] = p->lc;
            }
            if ((rear + 1) % 20 != front && p->rc != NULL)
            {
                rear = (rear + 1) % 20;
                Q[rear] = p->rc;
            }
        }
    }
}

void showNGene(BiTree p, int n)
{
    static int depth = 0;
    depth++;
    if (p)
    {
        if (depth == n)
            outputInfo(p);
        showNGene(p->lc, n);
        showNGene(p->rc, n);
    }
    depth--;
}

void showFamily(BiTree Tree)
{
    std::queue<BiTree> q1, q2;
    int i = 0;
    if (Tree)
    {
        q1.push(Tree);
        while (!q1.empty())
        {
            while (!q1.empty())
            {
                q2.push(q1.front());
                q1.pop();
            }
            i++;
            switch (i)
            {
            case 1:
                printf("第%d代：         ", i);
                break;
            case 2:
                printf("第%d代：      ", i);
                break;
            case 3:
                printf("第%d代：   ", i);
                break;
            case 4:
                printf("第%d代：", i);
                break;
            default:
                break;
            }
            while (!q2.empty())
            {
                BitNode* tmp = q2.front();
                q2.pop();
                printf("%s ", tmp->person.name);
                if (tmp->lc)
                    q1.push(tmp->lc);
                if (tmp->rc)
                    q1.push(tmp->rc);
            }
            printf("\n");
        }
    }
}

BiTree findParent(BiTree BT, BitNode* p)
{
    BiTree L_result, R_result;
    if (!BT || BT == p)
        return NULL;
    if (BT->lc == p || BT->rc == p)
        return BT;
    else
    {
        L_result = findParent(BT->lc, p);
        R_result = findParent(BT->rc, p);
        return L_result ? L_result : (R_result ? R_result : NULL);
    }
}

BiTree searchName(BiTree BT, char* str)
{
    BiTree L_result, R_result;
    if (!BT)
        return NULL;
    if (strcmp(BT->person.name, str) == 0)
        return BT;
    else
    {
        L_result = searchName(BT->lc, str);
        R_result = searchName(BT->rc, str);
        return L_result ? L_result : (R_result ? R_result : NULL);
    }
}

void findChild(BiTree p, BiTree *child)
{
    child[0] = p->lc ? p->lc : NULL;
    child[1] = p->rc ? p->rc : NULL;
}

void searchThreeGeneration(BiTree Tree)
{
    char name[20];
    BiTree parent, trnode, child[2];
    printf("请输入被查找成员的姓名：");
    scanf_s("%s", name, 20); // VS认为scanf是不安全的
    trnode = searchName(Tree, name);
    if (!trnode)
        printf("查无此人\n");
    else
    {
        parent = findParent(Tree, trnode);
        findChild(trnode, child);
        printf("此人信息为:\n");
        outputTitle();
        outputInfo(trnode);
        printf("他的父亲结点的信息为：\n");
        if (parent)
            outputTitle();
        outputInfo(parent);
        printf("他的左孩子的信息为：\n");
        if (child[0])
            outputTitle();
        outputInfo(child[0]);
        printf("他的右孩子的信息为：\n");
        if (child[1])
            outputTitle();
        outputInfo(child[1]);
    }
}

BiTree findBirthday(BiTree BT, char* birth)
{
    BiTree L_result, R_result;
    if (!BT)
        return NULL;
    if (strcmp(BT->person.birth, birth) == 0)
        return BT;
    else
    {
        L_result = findBirthday(BT->lc, birth);
        R_result = findBirthday(BT->rc, birth);
        return L_result ? L_result : (R_result ? R_result : NULL);
    }
}

void searchBirthday(BiTree Tree)
{
    char birth[10];
    printf("请输入要查找的成员的生日：");
    scanf_s("%s", birth, 10);
    BitNode* p = findBirthday(Tree, birth);
    if (!p)
    {
        printf("查无此人\n");
        return;
    }
    outputTitle();
    outputInfo(p);
}

bool isSameFather(BiTree BT, BitNode* p, BitNode* q)
{
    BiTree f1 = findParent(BT, p), f2 = findParent(BT, q);
    if (f1 == f2) return true;
    else return false;
}

void judgeRelationship(BiTree Tree)
{
    char name1[20], name2[20];
    printf("请输入第一个人的姓名：");
    scanf_s("%s", name1, 20);
    printf("请输入第二个人的姓名：");
    scanf_s("%s", name2, 20);
    BiTree s1 = searchName(Tree, name1), s2 = searchName(Tree, name2);
    if (isSameFather(Tree, s1, s2)) 
        printf("两人是亲兄弟\n");
    else
    {
        BiTree f1 = findParent(Tree, s1), f2 = findParent(Tree, s2);
        if (isSameFather(Tree, f1, f2))
            printf("两人是堂兄弟\n");
        else if (s1->lc == s2)
            printf("%s是%s的左孩子\n", s2->person.name, s1->person.name);
        else if (s2->lc == s1)
            printf("%s是%s的左孩子\n", s1->person.name, s2->person.name);
        else if (s1->rc == s2)
            printf("%s是%s的右孩子\n", s2->person.name, s1->person.name);
        else if (s2->rc == s1)
            printf("%s是%s的右孩子\n", s1->person.name, s2->person.name);
        else
            printf("关系有点远，年长就叫老祖宗，同龄人就叫美女帅哥吧~\n");
    }
}

void addChild(BiTree& Tree)
{
    char name_get_child[20];
    Info new_Child;
    printf("请输入要为其添加孩子的人的名字：");
    scanf_s("%s", name_get_child, 20);
    BitNode* p = searchName(Tree, name_get_child);
    if (p == NULL)
    {
        printf("查无此人\n");
        return;
    }
    if (p->lc && p->rc)
        printf("此人已有两个孩子，添加失败！\n");
    else
    {
        printf("请输入孩子的姓名：");
        scanf_s("%s", new_Child.name, 20);
        printf("请输入孩子的出生日期：");
        scanf_s("%s", new_Child.birth, 10);
        printf("如果孩子结婚了，请输入1， 否则输入0：");
        int i;
        scanf_s("%d", &i);
        if (i != 1 && i != 0)
            printf("您输入了非法数字，系统将自动处理！\n");
        new_Child.wedding = i % 2;
        printf("请输入孩子的地址：");
        scanf_s("%s", new_Child.address, 20);
        printf("如果孩子健在，请输入1， 否则输入0：");
        scanf_s("%d", &i);
        if (i != 1 && i != 0)
            printf("您输入了非法数字，系统将自动处理！\n");
        new_Child.alive = i % 2;
        if (!i)
        {
            printf("请输入孩子的死亡时间：");
            scanf_s("%s", new_Child.death, 10);
        }
        else
            strcpy_s(new_Child.death, "null");
        if (p->lc)
            newLeft(p, new_Child);
        else
            newRight(p, new_Child);
        printf("添加成功！\n");
    }
}

void deletePerson(BiTree& Tree)
{
    char name_be_deleted[20];
    printf("请输入要删除的人的名字：");
    scanf_s("%s", name_be_deleted, 20);
    BitNode* p = searchName(Tree, name_be_deleted);
    if (p == NULL)
    {
        printf("查无此人\n");
        return;
    }
    if (p->lc || p->rc)
    {
        printf("请注意，此人的后代也将一并删除！\n确认删除吗？(Y/N)  ");
        char ch;
        scanf_s(" %c", &ch, 1);
        if (ch == 'N' || ch == 'n') return;
    }
    BitNode* f = findParent(Tree, p); // 判断是否为根结点
    if (f)
    {
        if (f->lc == p)
        {
            f->lc = NULL;
            delete p;
        }
        if (f->rc == p)
        {
            f->rc = NULL;
            delete p;
        }
    }
    else
        Tree = NULL;
    printf("删除成功！\n");
}

void updateInfo(BiTree Tree)
{
    char name_change[20];
    printf("请输入要修改信息的成员的姓名：");
    scanf_s("%s", name_change, 20);
    BitNode* p = searchName(Tree, name_change);
    if (p == NULL)
    {
        printf("查无此人\n");
        return;
    }
    char tmp[20];
    printf("请输入姓名，0为不修改：");
    scanf_s("%s", tmp, 20);
    if (tmp[0] != '0')
        strcpy_s(p->person.name, tmp);
    printf("请输入出生日期，no为不修改：");
    scanf_s("%s", tmp, 20);
    if (tmp[0] != 'n')
        strcpy_s(p->person.birth, tmp);
    printf("如果结婚了，请输入1， 否则输入0，输入-1则为不修改：");
    int i;
    scanf_s("%d", &i);
    if (i != -1)
    {
        if (i != 1 && i != 0)
            printf("您输入了非法数字，系统将自动处理！\n");
        p->person.wedding = i % 2;
    }
    printf("请输入地址，0为不修改：");
    scanf_s("%s", tmp, 20);
    if (tmp[0] != '0')
        strcpy_s(p->person.address, tmp);
    printf("如果健在，请输入1， 否则输入0，输入-1则为不修改：");
    scanf_s("%d", &i);
    if (i != -1)
    {
        if (i != 1 && i != 0)
            printf("您输入了非法数字，系统将自动处理！\n");
        p->person.alive = i % 2;
    }
    if (!i)
    {
        printf("请输入死亡时间，no为不修改：");
        scanf_s("%s", tmp, 20);
        if (tmp[0] != 'n')
            strcpy_s(p->person.death, tmp);
    }
    else
        strcpy_s(p->person.death, "null");
    /*BiTree L_result, R_result;
    if (strcmp(Tree->person.name, name_change) == 0)
        Tree = p;
    else
    {
        L_result = searchName(Tree->lc, name_change);
        R_result = searchName(Tree->rc, name_change);
        if (L_result)
            L_result = p;
        else
            R_result = p;
    }*/
    printf("更新成功！\n");
}

void transportBirth(BiTree BT, char bir[][20], int& i)
{
    if (BT)
    {
        strcpy_s(bir[i++], BT->person.birth);
        transportBirth(BT->lc, bir, i);
        transportBirth(BT->rc, bir, i);
    }
}

void sortBirthday(BiTree Tree, int n)
{
    char birth[20][20];
    transportBirth(Tree, birth, n);
    //printf("sfesfe %d\n", n);
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (strcmp(birth[i], birth[j]) > 0)
            {
                char tmp[20];
                strcpy_s(tmp, birth[i]);
                strcpy_s(birth[i], birth[j]);
                strcpy_s(birth[j], tmp);
            }
    outputTitle();
    for (int i = 0; i < n; i++)
    {
        //printf("%s\n", birth[i]);
        BitNode* p = findBirthday(Tree, birth[i]);
        //printf("%s\n", p->person.name);
        outputInfo(p);
    }
    printf("\n");
}

Main.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <Windows.h>
#include "generation.h"
using namespace std;

/*Info human[12] = { {"Havoc",'M',"19030611",1,"Moscow",0,"19800528"},
                   {"Jenny",'F',"19201120",1,"Washington",0,"19890416"},
                   {"Carville",'M',"19230526",1,"Paris",0,"19971231"},
                   {"Ivan",'M',"19440501",1,"Macau",0,"20080419"},
                   {"Tanya",'F',"19470811",0,"nefu",0,"20010501"},
                   {"Mary",'F',"19480505",1,"Tibet",0,"20070412"},
                   {"Jones",'M',"19490541",1,"London",0,"20161004"},
                   {"Mark",'M',"19601227",0,"Tokyo",1,"null"},
                   {"Lucy",'F',"19770324",0,"Jupyter",1,"null"},
                   {"Steven",'M',"19770519",1,"Mars",1,"null"},
                   {"Romanov",'M',"20000102",0,"M87",1,"null"},
                   {"Libra",'F',"20030518",0,"M87",1,"null"} };*/
char timeNow[27];
int wedding, alive;
bool flag = 0;
Info human[12];
//char name[20], sex, birth[10], address[20], deadth[10];

int calcDay(char *_day, int tag) // 计算当前日期为整数
{
    int today = 0, ten = 1;
    for (int i = tag-1; i >= tag-4; i--)
    {
        today += (_day[i] - '0') * ten;
        ten *= 10;
    }
    return today;
}

int fetchTime() // 处理读取到的时间
{
    char _month[4], _day[5];
    for (int i = 0; i < 3; i++)
    {
        _month[i] = timeNow[i + 4];
        //printf("%c", _month[i]);
    }
    _month[3] = '\0';
    //printf("%s\n", _month);
    for (int i = 0; i < 2; i++)
    {
        if (timeNow[i + 8] == ' ')
            _day[i + 2] = '0';
        else
            _day[i + 2] = timeNow[i + 8];
        //printf("%c", _day[i]);
    }
    _day[0] = '0';
    if (strcmp(_month, "Jan") == 0)
        _day[1] = '1';
    else if (strcmp(_month, "Feb") == 0)
        _day[1] = '2';
    else if (strcmp(_month, "Mar") == 0)
        _day[1] = '3';
    else if (strcmp(_month, "Apr") == 0)
        _day[1] = '4';
    else if (strcmp(_month, "May") == 0)
        _day[1] = '5';
    else if (strcmp(_month, "Jun") == 0)
        _day[1] = '6';
    else if (strcmp(_month, "Jul") == 0)
        _day[1] = '7';
    else if (strcmp(_month, "Aug") == 0)
        _day[1] = '8';
    else if (strcmp(_month, "Sep") == 0)
        _day[1] = '9';
    else 
    {
        _day[0] = '1';
        if (strcmp(_month, "Oct") == 0)
            _day[1] = '0';
        if (strcmp(_month, "Nov") == 0)
            _day[1] = '1';
        if (strcmp(_month, "Dec") == 0)
            _day[1] = '2';
    }
    _day[4] = '\0'; // 手持两把锟斤拷，口中疾呼烫烫烫
    //printf("%s\n", _day);
    return calcDay(_day, 4);
}

void printBirthday(BiTree Tree) // 显示当天生日的健在成员
{
    int dayTime = fetchTime();
    //printf("%d\n", dayTime);
    int n = 0, cnt = 0;
    char birth[20][20];
    transportBirth(Tree, birth, n);
    //printf("%d\n", n);
    for (int i = 0; i < n; i++)
    {
        int tmp = calcDay(birth[i], 8);
        //printf("%d %d\n", tmp, dayTime);
        if (!cnt && tmp == dayTime)
        {
            BitNode* p = findBirthday(Tree, birth[i]);
            if (p->person.alive)
            {
                printf("今天过生日的人是：%s ", p->person.name);
                cnt++;
            }
        }
        else if (tmp == dayTime)
        {
            BitNode* p = findBirthday(Tree, birth[i]);
            if (p->person.alive)
            {
                printf("%s ", p->person.name);
                cnt++;
            }
        }
    }
    if (!cnt)
        printf("今天没有过生日的人！");
    printf("\n");
}

void initMenu()
{
    printf("***--------------------------***\n");
    printf("* 1.从文件读取家族信息         *\n");
    printf("* 2.保存信息至文件             *\n");
    printf("| 3.显示家谱                   |\n");
    printf("| 4.显示第n代所有人的信息      |\n");
    printf("| 5.按照姓名查询，输出成员信息 |\n");
    printf("| 6.按照出生日期查询成员名单   |\n");
    printf("| 7.输入两人姓名，确定其关系   |\n");
    printf("| 8.某成员添加孩子             |\n");
    printf("| 9.删除某成员                 |\n");
    printf("| 10.修改某成员信息            |\n");
    printf("* 11.按出生日期对所有人排序    *\n");
    printf("* 12.重置所有信息              *\n");
    printf("* 13.退出系统                  *\n");
    printf("***--------------------------***\n");
}

int main()
{
    // 获取当前日期时间
    time_t now;
    time(&now);
    ctime_s(timeNow, sizeof timeNow, &now);
    printf("当前时间为：%s\n", timeNow);
    BiTree Tree = NULL;
    printf("****欢迎来到莫拉莱斯的家族管理系统！****\n");
    //printf("***--------------------------------***\n");
INIT:if (flag)
    {
        Tree = createTree(human);
        printBirthday(Tree);
    }
START:initMenu();
    printf("请输入要执行的操作：");
    int option;
    scanf_s("%d", &option);
    switch (option)
    {
    case 1:
        {
            ifstream fin("Generation.txt");
            for (int i = 0; i < 12; i++)
            {
                fin >> human[i].name >> human[i].sex >> human[i].birth >> wedding >> human[i].address >> alive >> human[i].death;
                human[i].wedding = wedding;
                human[i].alive = alive;
            }
            fin.close();
            printf("读取成功！\n");
            flag = 1;
            goto INIT;
            break;
        }
    case 2:
        {
            if (!flag)
            {
                MessageBox(NULL, TEXT("无数据可保存！"), TEXT("Warning"), MB_OK);
                goto START;
            }
            ofstream fout("Generation.txt");
            for (int i = 0; i < 12; i++)
                fout << human[i].name <<" " << human[i].sex << " " << human[i].birth << " " << human[i].wedding << " " << human[i].address << " " << human[i].alive << " " << human[i].death << endl;
            fout.close();
            printf("保存成功！\n");
            goto START;
            break;
        }
    case 13:
        MessageBox(NULL, TEXT("感谢您的使用！"), TEXT("即将退出"), MB_OK);
        exit(0);
    default:
    {
        if (!flag)
        {
            printf("请先读取文件！\n");
            MessageBox(NULL, TEXT("请先读取文件！"), TEXT("Warning"), MB_OK);
            goto START;
        }
        else
        {
            switch (option)
            {
            case 3:
                showFamily(Tree);
                goto START;
                break;
            case 4:
            {
                printf("请输入查询代数：");
                int n;
                scanf_s("%d", &n);
                if (n >= 1 && n <= 4)
                {
                    outputTitle();
                    showNGene(Tree, n);
                }
                else printf("输入有误！\n");
                goto START;
                break;
            }
            case 5:
                searchThreeGeneration(Tree);
                goto START;
                break;
            case 6:
                searchBirthday(Tree);
                goto START;
                break;
            case 7:
                judgeRelationship(Tree);
                goto START;
                break;
            case 8:
                addChild(Tree);
                goto START;
                break;
            case 9:
                deletePerson(Tree);
                goto START;
                break;
            case 10:
                updateInfo(Tree);
                goto START;
                break;
            case 11:
                sortBirthday(Tree, 0);
                goto START;
                break;
            case 12:
            {
                ifstream fin("Generation.bak");
                for (int i = 0; i < 12; i++)
                {
                    fin >> human[i].name >> human[i].sex >> human[i].birth >> wedding >> human[i].address >> alive >> human[i].death;
                    human[i].wedding = wedding;
                    human[i].alive = alive;
                }
                fin.close();
                ofstream fout("Generation.txt");
                for (int i = 0; i < 12; i++)
                    fout << human[i].name << " " << human[i].sex << " " << human[i].birth << " " << human[i].wedding << " " << human[i].address << " " << human[i].alive << " " << human[i].death << endl;
                fout.close();
                printf("重置成功！\n");
                goto INIT;
            }
            default:
                printf("输入有误，请重新输入！\n");
                MessageBox(NULL, TEXT("输入有误，请重新输入！"), TEXT("Warning"), MB_OK);
                goto START;
                break;
            }
        }
        break;
    }
    }
    //cout << "Hello World!\n";
    return 0;
}

四 图型结构

行车路线

小明和小芳出去乡村玩，小明负责开车，小芳来导航。
　小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
　例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=16+2+4=22。
　现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。

输入格式

输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。
接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。

输出格式

输出一个整数，表示最优路线下小明的疲劳度。

样例输入

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

样例输出

76

样例说明

从1走小道到2，再走小道到3，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。

数据规模和约定

对于30%的评测用例，1≤n≤8，1≤m≤10；
对于另外20%的评测用例，不存在小道；
对于另外20%的评测用例，所有的小道不相交；
对于所有评测用例，1≤n≤500，1≤m≤105，1≤a, b≤n，t是0或1，c≤105。保证答案不超过106。

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MaxV = 1010;
const ll inf = 0x7FFFFFFFFFFFFFFF;

typedef struct node{
    int v;
    long long dis;
    bool road; // 1-big 0-small
}car;

int n, m;
vector<car> Adj[MaxV];
long long D[MaxV], R[MaxV];
bool S[MaxV];

void Dijkstra(int v0)
{
    fill(D, D+MaxV, inf);
    D[v0] = 0;
    for(int i=0; i<n; i++)
    {
        int u = -1;
        long long minn = inf;
        for(int j=1; j<=n; j++)
            if(!S[j] && D[j]<minn)
            {
                u = j;
                minn = D[j];
            }
        if(u == -1) return;
        S[u] = 1;
        for(int j=0; j<Adj[u].size(); j++)
        {
            int v = Adj[u][j].v;
            long long dis = Adj[u][j].dis;
            bool flag = Adj[u][j].road;
            if(!S[v])
            {
                if(!flag && D[u]-R[u]*R[u]+(R[u]+dis)*(R[u]+dis)<D[v])
                {
                    D[v] = D[u]-R[u]*R[u]+(R[u]+dis)*(R[u]+dis);
                    R[v] = R[u]+dis;
                }
                if(flag && D[u]+dis<D[v])
                {
                    D[v] = D[u]+dis;
                    R[v] = 0;
                }
            }
        }
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    cin>>n>>m;
    int t;
    for(int i=0; i<m; i++)
    {
        car t1, t2;
        cin>>t>>t2.v>>t1.v>>t1.dis;
        t2.dis = t1.dis;
        t1.road = t2.road = t^1;
        Adj[t1.v].push_back(t2);
        Adj[t2.v].push_back(t1);
    }
    Dijkstra(1);
    cout<<D[n]<<endl;
    return 0;
}

五 查找、排序、文件

二叉排序树

功能要求：
（1）从键盘输入一组学生记录建立二叉排序树；
（2）中序遍历二叉排序树；
（3）求二叉排序树深度；
（4）求二叉排序树的所有节点数和叶子节点数；
（5）向二叉排序树插入一条学生记录；
（6）从二叉排序树中删除一条学生记录；
（7）从二叉排序树中查询一条学生记录；
（8）以广义表的形式输出二叉排序树

//定义学生记录类型

Struct student 
{
  Char num[6];  //学号
  Int  grade;  //成绩
};

//定义二叉排序树节点值的类型为学生记录类型

typedef student  ElemType;

//定义二叉排序树的节点类型

typedef Struct BSTNode
{
  ElemType data;
  Struct BSTNode *left;
  Struct BSTNode *rchild;
} BSTNode;

binary.h

#pragma once
struct student {
	char num[10]; // 学号
	double grade; // 成绩
};
typedef student ElemType;
typedef struct BSTNode {
	ElemType data;
	struct BSTNode* lc, * rc;
}BSTNode, *BSTree;

void insertBST(BSTree& T, student elem); // 插入 - 5
void createBST(BSTree& T); // 创建 - 1
void inOrderTraverse(BSTree T); // 中序遍历 - 2
int calcDepth(BSTree T); // 计算深度 - 3
int cntLeaves(BSTree T); // 数叶子结点 - 4
int cntNodes(BSTree T); // 数结点 - 4
void deleteBST(BSTree& T, char* key); // 删除 - 6
double queryBST(BSTree T, char* name); // 查询成绩 - 7
void printBST(BSTree T); // 广义表 - 8

binary.cpp

#include "binary.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

void insertBST(BSTree& T, student elem)
{
	if (!T)
	{
		BSTNode* s = new BSTNode;
		s->data = elem;
		s->lc = NULL;
		s->rc = NULL;
		T = s;
	}
	else if (strcmp(elem.num, T->data.num) < 0)
		insertBST(T->lc, elem);
	else if (strcmp(elem.num, T->data.num) > 0)
		insertBST(T->rc, elem);
}

void createBST(BSTree& T)
{
	T = NULL;
	int n;
	cout << "请输入学生人数：" << endl;
	cin >> n;
	cout << "请依次输入" << n << "个学生的成绩和学号：" << endl;
	while (n--)
	{
		student elem;
		cin >> elem.grade >> elem.num;
		insertBST(T, elem);
	}
	cout << "创建完成！" << endl;
}

void inOrderTraverse(BSTree T)
{
	if (T)
	{
		inOrderTraverse(T->lc);
		cout << "学号: " << T->data.num << "  " << "成绩: " << T->data.grade << endl;
		inOrderTraverse(T->rc);
	}
}

int calcDepth(BSTree T)
{
	int Ldepth, Rdepth;
	if (!T) return 0;
	else
	{
		Ldepth = calcDepth(T->lc);
		Rdepth = calcDepth(T->rc);
		if (Ldepth > Rdepth)
			return Ldepth + 1;
		else return Rdepth + 1;
	}
}

int cntLeaves(BSTree T)
{
	int cnt = 0;
	if (!T)
		return 0;
	else if (!T->lc && !T->rc)
		return 1;
	else
		return cntLeaves(T->lc) + cntLeaves(T->rc);
}

int cntNodes(BSTree T)
{
	if (!T)
		return 0;
	else
		return cntNodes(T->lc) + cntNodes(T->rc) + 1;
}

void deleteBST(BSTree& T, char* key)
{
	BSTNode* p = T, * f = NULL;
	while (p)
	{
		//cout << "p->data " << p->data.num << endl;
		if (!strcmp(p->data.num, key))
			break;
		f = p; // *f为*p的双亲结点
		if (strcmp(p->data.num, key) > 0)
			p = p->lc;
		else
			p = p->rc;
	}
	if (!p)
	{
		cout << "查无此人！" << endl;
		return;
	}
	/*---左右均不空，右空，左空---*/
	BSTNode* q = p;
	if (p->lc && p->rc)
	{
		BSTNode* s = p->lc;
		while (s->rc)
		{
			q = s;
			s = s->rc;
		}
		p->data = s->data;
		if (q != p)
			q->rc = s->lc;
		else
			q->lc = s->lc;
		delete s;
		cout << "删除成功！" << endl;
		return;
	}
	else if (!p->rc)
		p = p->lc;
	else if (!p->lc)
		p = p->rc;
	/*---将p所指的子树挂接到其双亲结点*f的相应位置---*/
	if (!f)
		T = p;
	else if (q == f->lc)
		f->lc = p;
	else
		f->rc = p;
	delete q;
	cout << "删除成功！" << endl;
	return;
}

double queryBST(BSTree T, char* num)
{
	if (!T) return -1;
	BSTNode* p = T;
	while (p)
	{
		if (!strcmp(p->data.num, num))
			return p->data.grade;
		else if (strcmp(p->data.num, num) > 0)
			p = p->lc;
		else if (strcmp(p->data.num, num) < 0)
			p = p->rc;
	}
	return -1;
}

void printBST(BSTree T)
{
	cout << T->data.num;
	if (T->lc)
	{
		cout << "(";
		printBST(T->lc);
		if (!T->rc)
			cout << ")";
	}
	if (T->rc)
	{
		cout << ",";
		if (!T->lc)
			cout << "(";
		printBST(T->rc);
		cout << ")";
	}
}

main.cpp

#include "binary.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

void menu()
{
    std::cout << "-------二叉排序树------" << std::endl;
    std::cout << "输入数字，执行相应操作：" << std::endl;
    std::cout << "1.从键盘读入以建立二叉排序树" << std::endl;
    std::cout << "2.中序遍历二叉排序树" << std::endl;
    std::cout << "3.求二叉排序树深度" << std::endl;
    std::cout << "4.求二叉排序树的所有节点数和叶子节点数" << std::endl;
    std::cout << "5.向二叉排序树插入一条学生记录" << std::endl;
    std::cout << "6.从二叉排序树中删除一条学生记录" << std::endl;
    std::cout << "7.从二叉排序树中查询一条学生记录" << std::endl;
    std::cout << "8.以广义表的形式输出二叉排序树" << std::endl;
    std::cout << "0.退出" << std::endl;
}

int main()
{
    BSTree T = NULL;
    int q;
    ElemType data;
    while (1)
    {
        menu();
        std::cin >> q;
        switch (q)
        {
        case 1:
            createBST(T);
            break;
        case 2:
            std::cout << "中序遍历结果为：" << std::endl;
            inOrderTraverse(T);
            break;
        case 3:
            std::cout << "树的深度为" << calcDepth(T) << std::endl;
            break;
        case 4:
            std::cout << "共有" << cntNodes(T) << "个结点，" << cntLeaves(T) << "个叶子结点" << std::endl;
            break;
        case 5:
            std::cout << "请输入学号：";
            std::cin >> data.num;
            std::cout << "请输入成绩：";
            std::cin >> data.grade;
            insertBST(T, data);
            std::cout << "插入完成！" << std::endl;
            break;
        case 6:
            std::cout << "请输入学号：";
            std::cin >> data.num;
            deleteBST(T, data.num);
            break;
        case 7:
        {
            std::cout << "请输入学号：";
            std::cin >> data.num;
            double tmp = queryBST(T, data.num);
            if (tmp == -1) std::cout << "查无此人" << std::endl;
            else
                std::cout << "该生成绩为" << tmp << std::endl;
            break;
        }
        case 8:
            std::cout << "广义表形式为：";
            printBST(T);
            std::cout << std::endl;
            break;
        case 0:
            return 0;
        default:
            std::cout << "输入有误，请重新输入！" << std::endl;
            break;
        }
    }
    // std::cout << "Hello World!\n";
}

完结。