数据结构学习笔记其一

fufhaha2025-04-062025-04-06

数据结构作业笔记

1.基于顺序存储结构的线性表实现

1.1 思路：

因为是顺序存储结构的线性表，就要考虑用数组实现，而平时的数组静态的增删麻烦，我的思路是动态分配一个数组来做。

1.2各部分的功能实现：

头文件：

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

主体由数组组成的线性表的构成：

typedef struct
{
    int *data;//用于存储指向数据的指针
    int length;//数组的长度，跟随后面的增删改操作一起增减
    bool state;//用来标记该数组是否被销毁
} list;

因为要弄99个线性表，所以我选择开100个list指针变量，用来存储每个线性表数组的首地址

1	list*L[100];

初始化表：

void InitList(list *L)
{
    L->data = (int *)malloc(sizeof(int));//先给每个表（后续主函数的开始给每个表动态分配内存）data指针所指向的地址分配一个int大小的初始空间，后续直接对根据length对内容进行操作
    L->length = 0;
    L->state = true; //状态更新为存在
    printf("\n线性表创建成功！");
}

获取表中对应元素的序号：

根据长度，遍历该表找到序号即可(后续的查找，查找前后驱，插入和删除，履历，都是一样的遍历操作)

for (int j = 0; j <= L.length; ++j)
        {
            if (j == i - 1)
            {
                *e = L.data[j];
            }
        }

存入文件和存出文件：

我这里当时为了能看到文件的内容，所以用fprintf函数进行操作：

//存入操作基本流程：
ELIF*a=fopen("xxx.txt",w);//如果找不到就创一个
fprintf(a,"xxx%d",x);
fclose(a);
//读取操作基本流程：
ELIF*a=fopen("xxx.txt",r);//如果找不到就创一个
while (1)
        {
            int id, len;
            int *new_data2;
            if (fscanf(a, "Table[%d] %d", &id, &len) == 2)//这里是我存入的格式Table[表号] 长度 +表内容
            {
                new_data2 = (int *)malloc(len * sizeof(int));//先分配一个临时的空间用来存新的表
                for (int i = 0; i < len; ++i)
                {
                    fscanf(a, " %d", &new_data2[i]);
                }
                free(L->data);//释放掉要存储表的内存
                L->data = new_data2;
                L->length = len;
                printf("\n读取成功！");
                break;
            }
        }
fclose(a);

1.3原码

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

int *w;
typedef struct
{
    int *data;
    int length;
    bool state;
} list;

list *L[100];

void InitList(list *L)
{
    L->data = (int *)malloc(sizeof(int)); // 初始??
    L->length = 0;
    L->state = true; // 状态更新为存在
    printf("\n线性表创建成功");
}
void DestroyList(list *L)
{
    if (L->state == true)
    {
        free(L->data);
        L->data = NULL;
        L->state = false;
        printf("\n线性表销毁成功！");
    }
}
void ClearList(list *L)
{
    if (L->state == true)
    {
        L->length = 0;
        L->data = NULL;
        printf("\n清空线性表");
    }
}
void ListEmpty(list L)
{
    if (L.state == true)
    {
        printf("线性表不为空！");
    }
    else
    {
        printf("线性表为空");
    }
}
int ListLength(list L)
{
    printf("线性表的长度为%d", L.length); // 后续添加和删除操作的时候，??++??--??
}
void GetElem(list L, int i, int *e)
{
    if (i < 1 || i > L.length + 1)
    {
        printf("ERROR");
    }
    else
    {
        for (int j = 0; j <= L.length; ++j)
        {
            if (j == i - 1)
            {
                *e = L.data[j];
            }
        }
    }
}
int LocateElem(list L, int e) //----------------查找
{
    for (int i = 0; i <= L.length; ++i)
    {
        if (L.data[i] == e)
        {
            return i + 1;
        }
    }
}
void PriorElem(list L, int cur, int *pre) // 前驱---------------------
{
    *pre = -2;
    if (L.state == true)
    { // 每次前驱这个初始化一??
        for (int i = 0; i < L.length; ++i)
        {
            if (L.data[i] == cur && i != 0)
            {
                *pre = L.data[i - 1];
                return;
            }
        }
        /*if (pre == NULL)
         {
             printf("不存??");
             return;
         }*/
    }
    else
    {
        printf("请先创建一个表");
    }
}
void NextElem(list L, int cur, int *next_e)
{
    // printf("111");
    *next_e = -1;
    if (L.state == true)
    {
        // printf("222");
        for (int i = 0; i < L.length; ++i)
        {
            // printf("333");
            if (L.data[i] == cur && i != L.length - 1)
            {
                // printf("%d", L.data[0]);
                *next_e = L.data[i + 1];
                // printf("444");
                return;
            }
        }
    }
    else
    {
        printf("请先创建一个表");
    }
}
void ListInsert(list *L, int i, int e)
{
    if (i < 1 || i > L->length + 1)
    {
        printf("ERROR\n");
        return;
    }
    int new_length = L->length + 1;
    int *new_data = (int *)malloc(new_length * sizeof(int));
    for (int j = 0; j < i - 1; j++)
    {
        new_data[j] = L->data[j];
    }
    new_data[i - 1] = e;
    for (int j = i - 1; j < L->length; j++)
    {
        new_data[j + 1] = L->data[j];
    }
    free(L->data);
    L->data = new_data;
    L->length = new_length;

    printf("插入成功");
}

void ListDelete(list *L, int i, int j)
{
    if (i < 1 || j > L->length || i > j)
    {
        printf("ERROR\n");
        return;
    }
    int new_length = L->length - (j - i + 1);
    int *new_data1 = (int *)malloc(new_length * sizeof(int));
    int index = 0;
    for (int m = 0; m < L->length; ++m)
    {
        if (m < i - 1 || m > j - 1)
        {
            new_data1[index++] = L->data[m];
        }
    }
    free(L->data);
    L->data = new_data1;
    L->length = new_length;
    printf("删除成功\n");
}

void ListTraverse(list L)
{
    if (L.state == true)
    {
        for (int i = 0; i < L.length; ++i)
        {
            printf("%d ", L.data[i]);
        }
    }
    else
    {
        printf("\n先建表\n");
    }
}
void fifth(list *L, int k)
{
    if (k == 1)
    {
        for (int i = 0; i < L->length; ++i)
        {
            L->data[i]++;
        }
    }
    else
    {
        for (int i = 0; i < L->length; ++i)
        {
            L->data[i]--;
        }
    }
}
void sixth(list *L1, list *L2)
{
    if (L2->state == true)
    {
        free(L2->data);
    }
    L2->data = (int *)malloc(L1->length * sizeof(int));
    for (int i = 0; i < L1->length; ++i)
    {
        L2->data[i] = L1->data[i];
    }
    L2->length = L1->length;
    L2->state = true;
    printf("复制成功\n");
}

void Write(list L)
{
    if (L.state == true)
    {
        FILE *a = fopen("存档.txt", "r+");
        bool found = false;
        int id, len;
        long long int pos1, pos2;

        while (fscanf(a, "Table[%d] %d", &id, &len) == 2)
        {
            if (id == *w)
            {
                found = true;
                pos1 = ftell(a);
                while (getchar() != '\n')
                    ;
                pos2 = ftell(a);
                fseek(a, pos1 - 1, SEEK_SET);
                for (int i = 0; i < (pos2 - pos1 + 2); ++i)
                {
                    fputc(' ', a);
                }

                fseek(a, pos1 - 1, SEEK_SET);
                fprintf(a, "%d ", L.length);
                for (int i = 0; i < L.length; ++i)
                {
                    fprintf(a, "%d ", L.data[i]);
                }
                fprintf(a, "\n");
                fclose(a);
                return;
            }
        }
        if (!found)
        {
            fclose(a);
            a = fopen("存档.txt", "a");
            fprintf(a, "Table[%d] %d ", *w, L.length);
            for (int i = 0; i < L.length; ++i)
            {
                fprintf(a, "%d ", L.data[i]);
            }
            fprintf(a, "\n");
            fclose(a);
            printf("写入成功！\n");
        }
    }
    else
    {
        printf("请先创建表！\n");
    }
}

void Read(list *L)
{
    if (L->state == true)
    {

        FILE *a = fopen("存档.txt", "r");

        while (1)
        {
            int id, len;
            int *new_data2;
            if (fscanf(a, "Table[%d] %d", &id, &len) == 2)
            {
                new_data2 = (int *)malloc(len * sizeof(int));
                for (int i = 0; i < len; ++i)
                {
                    fscanf(a, " %d", &new_data2[i]);
                }
                free(L->data);
                L->data = new_data2;
                L->length = len;
                printf("\n读取成功");
                break;
            }
        }

        fclose(a);
    }
    else
    {
        printf("\n先建立该表");
        return;
    }
}
int main()
{
    int select = 1;
    while (select != 0)
    {
        printf("\n请输入对哪个线性表进行操作(1-99),输入0退出！\n");
        scanf("%d", &select);
        w = &select;
        if (select == 0)
        {
            printf("欢迎下次再使用本系统");
            break;
        }
        // 先给每个表分配下内存0的时候记得free
        if (L[select] == NULL)
        {
            L[select] = (list *)malloc(sizeof(list));
            L[select]->state = false;
        }
        // InitList(L[select]);
        int s1;
        s1 = 1;
        while (s1 != 0)
        {
            printf("\n  Menu for Linear Table On Sequence Structure\n");
            printf("----------------------------------------------\n");
            printf("  1.InitList\t8.PriorElem\t\n");
            printf("  2.DestoryList\t9.NextElem\t\n");
            printf("  3.ClearList\t10.ListInsert\t\n");
            printf("  4.ListEmpty\t11.ListDelete改\t\n");
            printf("  5.ListLength\t12.ListTrabverse\t\n");
            printf("  6.GetElem\t13.Write\t\n");
            printf("  7.LocateElem\t14.Read\t\n");
            printf("  0.Exit\t15.增减全部元素\n");
            printf("  16.复制表\t\n");
            printf("----------------------------------------------\n");
            printf("  请选择你要输入的操作[0~14]\n");
            scanf("%d", &s1);
            if (s1 == 1)
            {
                InitList(L[select]);
            }
            if (s1 == 2)
            {
                DestroyList(L[select]);
            }
            if (s1 == 3)
            {
                ClearList(L[select]);
            }
            if (s1 == 4)
            {
                ListEmpty(*L[select]);
            }
            if (s1 == 5)
            {
                ListLength(*L[select]);
            }
            if (s1 == 6)
            {
                int i, e;
                printf("\n请输入想要获得元素的位置：\n");
                scanf(" %d", &i);
                GetElem(*L[select], i, &e);
                printf("\n第%d的元素为%d!", i, e); // 几个房间还是一样的转来转去
            }
            if (s1 == 7)
            {
                int i;
                printf("\n请输入需要查找的元素：\n");
                scanf(" %d", &i);
                printf("\n第%d个元素与该元素相同\n", LocateElem(*L[select], i));
            }
            if (s1 == 8) //** */
            {
                int i, pre1;
                // pre = NULL;
                printf("\n请输入需要获得前驱的元素：\n");
                while (getchar() != '\n')
                    ;
                scanf("%d", &i);
                PriorElem(*L[select], i, &pre1);
                if (&pre1 == NULL)
                {
                    printf("不存在前驱");
                }
                else
                {
                    printf("\n该元素的前驱_%d\n", pre1);
                }
            }
            if (s1 == 9)
            {
                int i, next;
                // next_e = NULL;
                printf("\n请输入需要获得其后继的元素：\n");
                while (getchar() != '\n')
                    ;
                scanf("%d", &i);
                NextElem(*L[select], i, &next);
                if (&next == NULL)
                {
                    printf("不存在后继");
                }
                else
                {
                    printf("\n该元素的后继_%d\n", next);
                }
            }
            if (s1 == 10)
            {
                printf("\n请依次输入：在第_个位置之前插入元素_\n");
                int i, j;
                scanf(" %d %d", &i, &j);
                ListInsert(L[select], i, j);
            }
            if (s1 == 11)
            {
                printf("\n请依次输入：删除从_位到第_位的元素\n");
                int i, j;
                scanf(" %d %d", &i, &j);
                ListDelete(L[select], i, j);
                // printf("删除元素为：%d",dele);
            }
            if (s1 == 12)
            {
                printf("\n------------all elements-------------\n");
                printf("\t");
                ListTraverse(*L[select]);
                printf("\n----------------end------------------\n");
            }
            if (s1 == 13)
            {
                Write(*L[select]);
            }
            if (s1 == 14)
            {
                Read(L[select]);
            }
            if (s1 == 15)
            {
                int m;
                printf("你选择?1-增 2-减\n");
                scanf(" %d", &m);
                fifth(L[select], m);
            }
            if (s1 == 16)
            {
                int k;
                printf("把 L[%d] 表复制到 L[_]?\n", select);
                scanf("%d", &k);
                if (L[k] == NULL)
                {
                    L[k] = (list *)malloc(sizeof(list));
                    L[k]->state = false;
                }
                sixth(L[select], L[k]);
            }
        }
    }
    /*
    for (int i = 0; i < 100; ++i)
    {
        DestroyList(L[i]);
    }*/

    return 0;
}

2.基于链式存储结构的线性表实现

1.1思路：

这里是链式存储结构，所以应该用链表来实现，我的代码用单向链表来实现的，其余的构造和作业1的基本相同

1.2各部分的功能实现：

头文件：

1
2
3

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

主体链式的线性表的构成：

typedef struct node
{
    int data;
    struct node *next;//用于指向下一个链节（链式所在）
    bool state;
} node;

这里要用100个表，所以还是开一个node类型的指针数组，大小为100，用来存储每个表的头节点的地址：

1	node*L[100];

这时就要注意了，后续只要函数涉及到链表的构造的变化的，比如增删改操作，参数的数据类型就不能是node*

比如：

1
2

void InitList(node **L)
//这里参数的数据类型是node**，即指向指针的指针，因为这里的表本身就是由一个指针存储其头节点来维护的，所以涉及变化的操作要用指向该头节点指针的指针

初始化：

void InitList(node **L)
{
    *L = (node *)malloc(sizeof(node));//还是动态分配，这时是给头节点分配一个内存，此时一个链表只有首节点是有空间的，但无赋值
    (*L)->state = true;
    (*L)->next = NULL;
    printf("线性表创建成功！\n");
}

如增删改，插入，找前后驱的过程，核心的步骤是开一个临时节点new_node然后与原来节点轮流替换删除：

//以删除操作的核心为例
node *current = *L;
while (current != NULL)
{
     node *temp = current;
     current = current->next;
     free(temp);
}
*L = NULL;
//找前驱：(这里也是要开一个临时的node节点)
void GetElem(node *L, int i, int *e)
{
    if (L->state == true)
    {
        if (i <= 0 || i > ListLength(L))
        {
            printf("越界\n");
            return;
        }
        node *current = L->next;
        for (int j = 1; j < i; j++)
        {
            current = current->next;
        }
        *e = current->data;
    }
    else
    {
        printf("请先初始化表\n");
    }
}

清空和判断表是否为空操作都是看首节点的状态

读写操作和作业1相同

void Write(node *L)
{
    if (L->state == true)
    {
        FILE *a;
        a = fopen("链式存档.txt", "a");
        fprintf(a, " ");
        node *current = L->next;
        while (current != NULL)
        {
            fprintf(a, "%d ", current->data);
            current = current->next;
        }
        fprintf(a, "\n");
        fclose(a);
        printf("INPUT FILE NAME:链式存档.txt\n");
    }
    else
    {
        printf("请先创建表\n");
    }
}
void Read(node **L)
{
    if ((*L)->state == true)
    {
        FILE *a;
        a = fopen("链式存档.txt", "r");
        int b;
        int i = 1;
        ClearList(*L);
        while (fscanf(a, " %d", &b) != EOF)
        {
            ListInsert(*L, i, b);
            i++;
        }
        fclose(a);

        printf("OUTPUT FILE NAME:链式存档.txt\n");
    }
}

1.3原码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
    bool state;
} node;
int *w;
node *L[100]; // 存储1-99个链表的头指针
// 指针也是一种变量，它也有对应的地址，链表是靠指针来维护的，要在函数中真正做到更改链表，可以另外搞个指针指向链表的指针的地址，来对其进行操作

//->的优先级要大于*
void InitList(node **L)
{
    *L = (node *)malloc(sizeof(node));
    (*L)->state = true;
    (*L)->next = NULL;
    printf("线性表创建成功！\n");
}

void DestroyList(node **L)
{
    if ((*L)->state == true)
    {
        node *current = *L;
        while (current != NULL)
        {
            node *temp = current;
            current = current->next;
            free(temp);
        }
        *L = NULL;
        printf("线性表已销毁\n");
        return;
    }
    else
    {
        printf("请先建造表\n");
    }
}

void ClearList(node *L)
{
    if (L->state == true)
    {
        L->next = NULL;
        printf("线性表已清空\n");
    }
    else
    {
        printf("请先初始化表\n");
    }
}

int ListEmpty(node *L)
{
    if (L->state == true)
    {
        printf("线性表不为空");
        return true;
    }
    else
    {
        printf("线性表为空");
        return false;
    }
}

int ListLength(node *L)
{
    node *current = L;
    int i = 0;
    while (current != NULL)
    {
        current = current->next;
        i++;
    }
    return i - 1;
}
void GetElem(node *L, int i, int *e)
{
    if (L->state == true)
    {
        if (i <= 0 || i > ListLength(L))
        {
            printf("越界\n");
            return;
        }
        node *current = L->next;
        for (int j = 1; j < i; j++)
        {
            current = current->next;
        }
        *e = current->data;
    }
    else
    {
        printf("请先初始化表\n");
    }
}

int LocateElem(node *L, int e)
{
    if (L->state == true)
    {
        int i = 0;
        node *current;
        while (L != NULL) // 这里
        {
            current = L;

            if (current->data == e)
            {
                return i + 1;
            }
            L = L->next;
        }
        return 0;
    }
    else
    {
        printf("请先创建表\n");
    }
}
void PriorElem(node *L, int cur, int *pre_e)
{
    node *current;
    // 这里，L是第一个的判断
    while (L != NULL)
    {

        current = L;
        L = L->next;
        if (cur == L->data)
        {
            *pre_e = current->data;
            return;
        }
    }
}

void NextElem(node *L, int cur, int *next_e)
{
    node *current;
    while ((L->next) != NULL)
    {
        current = L;
        L = L->next;
        if (cur == current->data)
        {
            *next_e = L->data;
            return;
        }
    }
    printf("该数没有后驱！\n");
    return;
}

void ListInsert(node *L, int i, int e)
{
    if (L->state == true && i > 0 && i <= ListLength(L) + 1)
    {
        node *newnode = (node *)malloc(sizeof(node));
        newnode->data = e;
        newnode->next = NULL;

        node *current = L;
        for (int j = 1; j < i; j++)
        {
            current = current->next;
        }
        newnode->next = current->next;
        current->next = newnode;
        printf("插入成功！\n");
    }
    else
    {
        printf("请先创建表\n");
    }
}

void ListDelete(node *L, int i, int j, int *e)
{
    if (L->state == true)
    {
        if (i <= 0 || j <= 0 || i > ListLength(L) || j > ListLength(L) || i > j)
        {
            printf("删除位置无效！\n");
            return;
        }

        node *prev = L;
        node *current = L->next;
        int count = 1;
        while (current != NULL && count <= j)
        {
            if (count >= i)
            {
                *e = current->data;
                prev->next = current->next;
                free(current);
                current = prev->next;
            }
            else
            {
                prev = current;
                current = current->next;
            }
            count++;
        }
        printf("删除成功！\n");
    }
    else
    {
        printf("请先创建表\n");
    }
}

void ListTraverse(node *L)
{
    if (L->state == true)
    {
        node *current;
        current = L->next;
        while (current != NULL)
        {
            printf("%d ", current->data);
            current = current->next;
        }
    }
}

void Write(node *L)
{
    if (L->state == true)
    {
        FILE *a;
        a = fopen("链式存档.txt", "a");
        fprintf(a, " ");
        node *current = L->next;
        while (current != NULL)
        {
            fprintf(a, "%d ", current->data);
            current = current->next;
        }
        fprintf(a, "\n");
        fclose(a);
        printf("INPUT FILE NAME:链式存档.txt\n");
    }
    else
    {
        printf("请先创建表\n");
    }
}
void Read(node **L)
{
    if ((*L)->state == true)
    {
        FILE *a;
        a = fopen("链式存档.txt", "r");
        int b;
        int i = 1;
        ClearList(*L);
        while (fscanf(a, " %d", &b) != EOF)
        {
            ListInsert(*L, i, b);
            i++;
        }
        fclose(a);

        printf("OUTPUT FILE NAME:链式存档.txt\n");
    }
}
void fifth(node **L, int i, int j, int m, int key)
{
    if ((*L)->state == true)
    {
        if (i <= 0 || j <= 0 || i > ListLength(*L) || j > ListLength(*L) || i > j)
        {
            printf("无效范围！\n");
            return;
        }
        node *current = (*L)->next;
        int count = 1;
        while (current != NULL && count <= j)
        {
            if (count >= i)
            {
                if (key == 1)
                    current->data += m;
                if (key == 0)
                    current->data -= m;
            }
            current = current->next;
            count++;
        }
        printf("更新完成！");
    }
    else
    {
        printf("请先初始化表\n");
    }
}
void sixteenth(node **L)
{
    if ((*L)->state == true)
    {
        int select2;
        printf("请输入你要拼接到的目标表1-99：\n");
        scanf(" %d", &select2);
        if (select2 < 1 || select2 > 99 || L[select2] == NULL || L[select2]->state != true)
        {
            printf("范围无效\n");
            return;
        }

        node *p1 = *L;
        node *p2 = L[select2];
        if (p1->next == NULL)
        {
            printf("请先初始化自己这个表\n");
            return;
        }
        if (p2->next == NULL)
        {
            p2->next = p1->next;
            p1->next = NULL;
        }
        else
        {
            node *current = p2;
            while (current->next != NULL)
            {
                current = current->next;
            }
            current->next = p1->next;
            p1->next = NULL;
        }
    }
    else
    {
        printf("请先初始化表\n");
    }
}
int main()
{
    int select = 1;
    InitList(&L[0]);
    while (select != 0)
    {
        printf("\n请输入对哪个线性表进行操作(1-99),输入0退出！\n");
        scanf("%d", &select);
        w = &select;
        if (select == 0)
        {
            printf("欢迎下次再使用本系统！");
            break;
        }
        if (L[select] == NULL)
        {
            L[select] = (node *)malloc(sizeof(node));
            InitList(&L[select]);
        }

        int s1;
        s1 = 1;
        while (s1 != 0)
        {
            printf("\n  Menu for Linear Table On Sequence Structure\n");
            printf("----------------------------------------------\n");
            printf("  1.InitList\t8.PriorElem\t\n");
            printf("  2.DestroyList\t9.NextElem\t\n");
            printf("  3.ClearList\t10.ListInsert\t\n");
            printf("  4.ListEmpty\t11.ListDelete(改)\t\n");
            printf("  5.ListLength\t12.ListTrabverse\t\n");
            printf("  6.GetElem\t13.Write\t\n");
            printf("  7.LocateElem\t14.Read\t\n");
            printf("  0.Exit\t15.指定范围i-j对该范围所有元素增减m\n");
            printf("  16.表与表的拼接\n");
            printf("----------------------------------------------\n");
            printf("  请选择你要输入的操作[0~14]\n");
            scanf("%d", &s1);
            if (s1 == 1)
            {
                InitList(&L[select]);
            }
            if (s1 == 2)
            {
                DestroyList(&L[select]);
            }
            if (s1 == 3)
            {
                ClearList(L[select]);
            }
            if (s1 == 4)
            {
                ListEmpty(L[select]);
            }
            if (s1 == 5)
            {
                printf("链表长度为：%d", ListLength(L[select]));
            }
            if (s1 == 6)
            {
                int i, e;
                printf("\n请输入想要获得元素的位置：\n");
                scanf(" %d", &i);
                GetElem(L[select], i, &e);
                printf("\n第%d的元素为%d!", i, e);
            }
            if (s1 == 7)
            {
                int i;
                printf("\n请输入需要查找的元素：\n");
                scanf(" %d", &i);
                printf("\n第%d个元素与该元素相同\n", LocateElem(L[select], i) + 1);
            }
            if (s1 == 8)
            {
                int i, pre1;
                printf("\n请输入需要获得前驱的元素：\n");
                while (getchar() != '\n')
                    ;
                scanf("%d", &i);
                PriorElem(L[select], i, &pre1);
                if (&pre1 == NULL)
                {
                    printf("不存在前驱");
                }
                else
                {
                    printf("\n该元素的前驱为%d\n", pre1);
                }
            }
            if (s1 == 9)
            {
                int i, next;
                printf("\n请输入需要获得其后继的元素：\n");
                while (getchar() != '\n')
                    ;
                scanf("%d", &i);
                NextElem(L[select], i, &next);
                if (&next == NULL)
                {
                    printf("不存在后继");
                }
                else
                {
                    printf("\n该元素的后继为%d\n", next);
                }
            }
            if (s1 == 10)
            {
                printf("\n请依次输入：在第_个位置之前插入元素_\n");
                int i, j;
                scanf(" %d %d", &i, &j);
                ListInsert(L[select], i, j);
            }
            if (s1 == 11)
            {
                printf("\n请输入要删除的范围_到_:[闭区间]\n");
                int i, j, dele;
                scanf(" %d %d", &i, &j);
                ListDelete(L[select], i, j, &dele);
            }
            if (s1 == 12)
            {
                printf("\n------------all elements-------------\n");
                printf("\t");
                ListTraverse(L[select]);
                printf("\n----------------end------------------\n");
            }
            if (s1 == 13)
            {
                Write(L[select]);
            }
            if (s1 == 14)
            {
                Read(&L[select]);
            }
            if (s1 == 15)
            {
                printf("\n请输入要增减元素的范围_到_，以及增减的值_,以及1-增 0-减:\n");
                int i, j, m, key;
                scanf(" %d %d %d %d", &i, &j, &m, &key);
                fifth(&L[select], i, j, m, key);
            }
            if (s1 == 16)
            {

                sixteenth(&L[select]);
            }
        }
    }

    return 0;
}

3.基于二叉链表的二叉树实现

1.1思路：

首先，二叉树的前中后序遍历的原理：

//前序：根左右
//中序：左根右
//后序：左右根

//先给出一个二叉树为例：
						A1
                        /    \
                      B2      C3
                     /       /   \
                   D4       E5    F6
                 /   \     /   \
               G7   H8  I9   J10
//对于这棵树的前序：
                                1【2】3
                                1 2【4】 #3
                                12 478 #【3】
                                12478#356
                                12478#359106##
                                ABDG##H###CEI##J##F##//这里注意最后一层节点的后一层都是空的，都是读到下一层
                                //即每个左右节点都是下一子树的根，由此，递归可补充该部分的空隙，来完成二叉树的序的遍历

1.2各部分的功能实现：

头文件：

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

组成二叉树节点的结构：

typedef struct node {
    int data;            // 节点存储的数值
    struct node *l;      // 左子树指针
    struct node *r;      // 右子树指针
    char key;            // 节点标识符（如'A'、'B'等）
} Tree;

创建二叉树：

根据上面的前序原理进行递归创建，这里有#字填充，如果没有#字，则需要前序+中序或者后序+中序才能创建一个完整的二叉树

void CreateBiTree(Tree **T, char **definition)//Tree **T: 根节点指针的指针,char **definition: 前序序列字符串指针
{
    if (**definition == '#')
    {
        *T = NULL;
        (*definition)++;
    }
    else
    {
        *T = (Tree *)malloc(sizeof(Tree));
        (*T)->key = **definition;
        (*definition)++;
        (*T)->data = 0;
        CreateBiTree(&((*T)->l), definition);
        CreateBiTree(&((*T)->r), definition);
    }
}

清空二叉树：

只释放左右节点的空间，保留根节点，这样既能通过递归清空，又能保留最后的根结点

void DestroyBiTree(Tree **T)
{
    if (*T)
    {
        DestroyBiTree(&(*T)->l);
        DestroyBiTree(&(*T)->r);
        free(*T);
        *T = NULL;
    }
    printf("二叉树已销毁！\n");
}

void ClearBiTree(Tree *T) // 清空和销毁的本质在于根节点是否被删除
{
    if (T)
    {
        DestroyBiTree(&T->l);//这里是以最初结点的左右节点为递归开始清空的
        DestroyBiTree(&T->r);
    }
    printf("二叉树已清空！\n");
}

求二叉树深度：

也是用递归

int BiTreeDepth(Tree *T)
{
    int dep, ld, rd;
    if (T == NULL)//首先边界条件
    {
        return 0;
    }
    else
    {
        ld = BiTreeDepth(T->l);//不断递归，然后最终回溯到第一个
        rd = BiTreeDepth(T->r);
        dep = (ld > rd ? ld : rd) + 1;//比较
    }
    return dep;
}
//注意，这些递归的条件都是当层的和下一层的，而下下层的都是通过递归不断地获得，但是当前和下一层的条件一定要有

剩余查找的函数都是递归，比如：

Tree *LocateNode(Tree *T, char e)
{
    if (T == NULL)
    {
        // printf("二叉树为空！");
        return NULL;
    }
    else
    {
        Tree *P = T;
        if (P->key == e)
        {
            return P;
        }
        else
        {
            P = LocateNode(T->l, e);
            if (P != NULL)
            {
                return P;
            }

            P = LocateNode(T->r, e);
            return P;
        }
    }
}//这个返回的是节点

下面的找父母节点也是，返回的节点，递归的时候就参数多延伸一层

Tree *parents(Tree *T, char e)
{
    if (T == NULL)
        return NULL;
    if (T->l && T->l->key == e)
        return T;
    if (T->r && T->r->key == e)
        return T;

    Tree *leftParent = parents(T->l, e);
    if (leftParent != NULL)
        return leftParent;
    return parents(T->r, e);
}

删除函数：

删除操作就要分3种情况讨论了：

每次操作都要用到父母函数，然后修改父母的指针

1.删除无子节点

2.删除单叶子结点：单节点直接替上

3.删除双叶子结点：左节点替上，右节点成为左节点孩子

Tree *DeleteNode(Tree *T, char e)
{
    Tree *p = LocateNode(T, e);
    if (!p)
    {
        printf("节点 %c 不存在！\n", e);
        return T;
    }
    Tree *parent = parents(T, e);
    if (p->l == NULL && p->r == NULL)//删除节点没有子节点情况
    {
        if (parent)//父节点存在
        {
            if (parent->l == p)//若 p 是父节点的左子节点,若 p 是父节点的左子节点
                parent->l = NULL;
            else
                parent->r = NULL;
        }
        else//父节点不存在（p 是根节点）,把子节点更新为根节点
        {
            T = NULL;
        }
        free(p);
    }
    else if (p->l == NULL || p->r == NULL)//删除节点有1个子节点情况
    {
        Tree *child = (p->l) ? p->l : p->r;//判断孩子是左节点还是右节点
        if (parent)
        {
            if (parent->l == p)
                parent->l = child;
            else
                parent->r = child;
        }
        else
        {
            T = child;
        }
        free(p);
    }
    else//删除节点有2个子节点的情况
    {
        if (p->l == NULL)
        {
            Tree *child = p->r;
            if (parent)
            {
                if (parent->l == p)
                    parent->l = child;
                else
                    parent->r = child;
            }
            else
            {
                T = child;
            }
            free(p);
        }
        else
        {
            Tree *rightmost = p->l;//找到左子树的最右节点 rightmost
            while (rightmost->r)//循环直到右子树为空
                rightmost = rightmost->r;
            rightmost->r = p->r;//p 的右子树成为 rightmost 的右子树
            if (parent)
            {
                if (parent->l == p)
                    parent->l = p->l;
                else
                    parent->r = p->l;
            }
            else
            {
                T = p->l;
            }
            free(p);
        }
    }
    printf("删除完毕！\n");
    return T;
}

遍历操作：

前中后序：

主要是递归和输出的不同，导致序的不同：

void OrderTraverse(Tree *T)
{
    if (T == NULL)
        return;
    //printf("%c:%d\n", T->key, T->data);前序
    PreOrderTraverse(T->l);
    //printf("%c:%d\n", T->key, T->data);中序
    PreOrderTraverse(T->r);
    //printf("%c:%d\n", T->key, T->data);后序
}

由这可知，如果没有#占位空格，通过2序我们可以得到整个二叉树

int post[50];
int in[50];
tepydef struct nod{
	struct nod*lef,rig;
	int val;
}nod;
nod *build(int postl,int postr,int inl,int inr){
	if(postl>postr) return NULL;
	nod *p=(nod*)malloc(sizeof(nod));
	p->val=post[postr];
	int x=post[postr];
	int i;
	for(i=inl;in[i]!=x&&i<=inr;++i);
	p->lef=build(postl, postl + i - inl - 1, inl, i - 1);
	p->rig=build(postl + i - inl, postr - 1, i + 1, inr);
	return p;
}
build(0,n-1,0,n-1);

层序遍历：主要是队列，要用一个队列的结构体

typedef struct
{
    Tree *node;
    int level;
    int pos;
} QueueItem; 
void LevelOrderTraverse(Tree *T)
{
    if (T == NULL)
    {
        printf("二叉树不存在\n");
    }
    else
    {
        Tree *q[100];
        Tree *p;
        int front = 0;
        int rear = 1;
        q[0] = T;
        while (front < rear)
        {
            p = q[front];
            printf("%c:%d\n", p->key, p->data);
            if (p->l)
                q[rear++] = p->l;
            if (p->r)
                q[rear++] = p->r;

            front++;
        }
    }
}

写入和读取操作：

这里我是用fwrite二进制的方式进行的

void TreeWrite(Tree *T, FILE *fp) {
    if (T == NULL) {                     // 当前节点为空
        fputc('#', fp);                  // 写入'#'标记空节点
        return;
    } else {
        fputc(T->key, fp);               // 写入节点的字符标识符（如'A'）
        fwrite(&T->data, sizeof(int), 1, fp); // 写入节点的整数值（二进制格式）
        TreeWrite(T->l, fp);             // 递归写入左子树
        TreeWrite(T->r, fp);             // 递归写入右子树
    }
}
void Wirte(Tree *T) {
    FILE *fp;
    fp = fopen("二叉树存档.bin", "wb");    // 以二进制写模式打开文件
    if (fp == NULL) { 
        printf("无法打开文件\n");
        return;
    }
    TreeWrite(T, fp);                    // 调用递归写入函数
    fclose(fp);                          // 关闭文件
}
void TreeRead(Tree **T, FILE *fp, int *Arch) {
    char c;
    fread(&c, sizeof(char), 1, fp);      // 读取一个字符（节点标识符或'#'）
    if (c == '#') {                      // 空节点标记
        *T = NULL;                       // 当前节点指针置空
        (*Arch)++;
        return;
    } else {
        *T = (Tree *)malloc(sizeof(Tree)); // 为非空节点分配内存
        (*T)->key = c;                   // 设置节点标识符
        fread(&((*T)->data), sizeof(int), 1, fp); // 读取节点的整数值
        (*Arch)++;                       // 计数器递增
        TreeRead(&((*T)->l), fp, Arch);  // 递归读取左子树
        TreeRead(&((*T)->r), fp, Arch);  // 递归读取右子树
    }
}
void Read(Tree **T) {
    FILE *fp;
    fp = fopen("二叉树存档.bin", "rb");    // 以二进制读模式打开文件
    if (fp == NULL) {                    // 文件打开失败处理
        printf("无法打开文件\n");
        return;
    }
    int w = 0; 
    TreeRead(T, fp, &w);                 // 调用递归读取函数
    fclose(fp);                          // 关闭文件
}

1.3原码：

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

typedef struct node
{
    int data;
    struct node *l;
    struct node *r;
    char key;

} Tree;
typedef struct
{
    Tree *node;
    int level;
    int pos;
} QueueItem; // ABDG##H###CEI##J##F##
int sum = 0;
int *w = NULL;
void CreateBiTree(Tree **T, char **definition)
{
    if (**definition == '#')
    {
        *T = NULL;
        (*definition)++;
    }
    else
    {
        *T = (Tree *)malloc(sizeof(Tree));
        (*T)->key = **definition;
        (*definition)++;
        (*T)->data = 0;
        CreateBiTree(&((*T)->l), definition);
        CreateBiTree(&((*T)->r), definition);
    }
}

void DestroyBiTree(Tree **T)
{
    if (*T)
    {
        DestroyBiTree(&(*T)->l);
        DestroyBiTree(&(*T)->r);
        free(*T);
        *T = NULL;
    }
    printf("二叉树已销毁！\n");
}

void ClearBiTree(Tree *T) // 清空和销毁的本质在于根节点是否被删除
{
    if (T)
    {
        DestroyBiTree(&T->l);
        DestroyBiTree(&T->r);
    }
    printf("二叉树已清空！\n");
}

void BiTreeEmpty(Tree *T)
{
    if (T == NULL)
    {
        printf("二叉树不存在！");
    }
    else
    {
        printf("二叉树存在");
    }
}

int BiTreeDepth(Tree *T)
{
    int dep, ld, rd;
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        ld = BiTreeDepth(T->l);
        rd = BiTreeDepth(T->r);
        dep = (ld > rd ? ld : rd) + 1;
    }
    return dep;
}
Tree *LocateNode(Tree *T, char e)
{
    if (T == NULL)
    {
        // printf("二叉树为空！");
        return NULL;
    }
    else
    {
        Tree *P = T;
        if (P->key == e)
        {
            return P;
        }
        else
        {
            P = LocateNode(T->l, e);
            if (P != NULL)
            {
                return P;
            }

            P = LocateNode(T->r, e);
            return P;
        }
    }
}
void Assign(Tree *T, char e, int value)
{
    Tree *P;
    P = LocateNode(T, e);
    P->data = value;
}
Tree *parents(Tree *T, char e)
{
    if (T == NULL)
        return NULL;
    if (T->l && T->l->key == e)
        return T;
    if (T->r && T->r->key == e)
        return T;

    Tree *leftParent = parents(T->l, e);
    if (leftParent != NULL)
        return leftParent;
    return parents(T->r, e);
}
Tree *GetSibling(Tree *T, char e)
{
    Tree *parent = parents(T, e);
    if (parent == NULL)
    {
        printf("节点 %c 是根节点，无兄弟！\n", e);
        return NULL;
    }
    if (parent->l && parent->l->key == e)
    {
        return parent->r; // 可能是NULL这个
    }
    else if (parent->r && parent->r->key == e)
    {
        return parent->l;
    }

    return NULL;
}
void InsertNode(Tree *T, char e, int LR, Tree *c)
{
    if (T == NULL)
    {
        return;
    }
    else if (T->key == e)
    {
        if (LR == 0)
        {
            c->l = T->l;
            c->r = NULL;
            T->l = c;
        }
        else
        {
            c->r = T->r;
            c->l = NULL;
            T->r = c;
        }
    }
    else
    {
        InsertNode(T->l, e, LR, c);
        InsertNode(T->r, e, LR, c);
    }
    return;
}

Tree *FindRightmost(Tree *node)
{
    while (node->r)
        node = node->r;
    return node;
}
Tree *DeleteNode(Tree *T, char e)
{
    Tree *p = LocateNode(T, e);
    if (!p)
    {
        printf("节点 %c 不存在！\n", e);
        return T;
    }
    Tree *parent = parents(T, e);
    if (p->l == NULL && p->r == NULL)
    {
        if (parent)
        {
            if (parent->l == p)
                parent->l = NULL;
            else
                parent->r = NULL;
        }
        else
        {
            T = NULL;
        }
        free(p);
    }
    else if (p->l == NULL || p->r == NULL)
    {
        Tree *child = (p->l) ? p->l : p->r;
        if (parent)
        {
            if (parent->l == p)
                parent->l = child;
            else
                parent->r = child;
        }
        else
        {
            T = child;
        }
        free(p);
    }
    else
    {
        if (p->l == NULL)
        {
            Tree *child = p->r;
            if (parent)
            {
                if (parent->l == p)
                    parent->l = child;
                else
                    parent->r = child;
            }
            else
            {
                T = child;
            }
            free(p);
        }
        else
        {
            Tree *rightmost = p->l;
            while (rightmost->r)
                rightmost = rightmost->r;
            rightmost->r = p->r;
            if (parent)
            {
                if (parent->l == p)
                    parent->l = p->l;
                else
                    parent->r = p->l;
            }
            else
            {
                T = p->l;
            }
            free(p);
        }
    }
    printf("删除完毕！\n");
    return T;
}

Tree *fu(Tree *T, char e)
{
    if (T == NULL)
        return NULL;
    return LocateNode(T, e);
}
void PreOrderTraverse(Tree *T)
{
    if (T == NULL)
        return;
    printf("%c:%d\n", T->key, T->data);
    PreOrderTraverse(T->l);
    PreOrderTraverse(T->r);
}

void InOrderTraverse(Tree *T)
{
    if (T == NULL)
        return;
    InOrderTraverse(T->l);
    printf("%c:%d\n", T->key, T->data);
    InOrderTraverse(T->r);
}
void PostOrderTraverse(Tree *T)
{
    if (T == NULL)
        return;
    PostOrderTraverse(T->l);
    PostOrderTraverse(T->r);
    printf("%c:%d\n", T->key, T->data);
}
void LevelOrderTraverse(Tree *T)
{
    if (T == NULL)
    {
        printf("二叉树不存在\n");
    }
    else
    {
        Tree *q[100];
        Tree *p;
        int front = 0;
        int rear = 1;
        q[0] = T;
        while (front < rear)
        {
            p = q[front];
            printf("%c:%d\n", p->key, p->data);
            if (p->l)
                q[rear++] = p->l;
            if (p->r)
                q[rear++] = p->r;

            front++;
        }
    }
}
void TreeWrite(Tree *T, FILE *fp)
{
    if (T == NULL)
    {
        fputc('#', fp);
        return;
    }
    else
    {
        fputc(T->key, fp);
        fwrite(&T->data, sizeof(int), 1, fp);
        TreeWrite(T->l, fp);
        TreeWrite(T->r, fp);
    }
}

void Wirte(Tree *T)
{
    FILE *fp;
    fp = fopen("二叉树存档.bin", "wb");
    if (fp == NULL)
    {
        printf("无法打开文件\n");
        return;
    }
    TreeWrite(T, fp);
    fclose(fp);
}

void TreeRead(Tree **T, FILE *fp, int *Arch)
{
    char c;
    fread(&c, sizeof(char), 1, fp);
    if (c == '#')
    {
        *T = NULL;
        (*Arch)++;
        return;
    }
    else
    {
        *T = (Tree *)malloc(sizeof(Tree));
        (*T)->key = c;
        fread(&((*T)->data), sizeof(int), 1, fp);
        (*Arch)++;
        TreeRead(&((*T)->l), fp, Arch);
        TreeRead(&((*T)->r), fp, Arch);
    }
}

void Read(Tree **T)
{
    FILE *fp;
    fp = fopen("二叉树存档.bin", "rb");
    if (fp == NULL)
    {
        printf("无法打开文件\n");
        return;
    }

    int w = 0;
    TreeRead(T, fp, &w);
    fclose(fp);
}

void banlk(int x)
{
    for (int i = 0; i < x; ++i)
    {
        printf(" ");
    }
}

void seventeen(Tree *T)
{
    if (T == NULL)
    {
        printf("树为空！\n");
        return;
    }

    int depth = BiTreeDepth(T);
    if (depth == 0)
        return;
    int max_width = (1 << depth) - 1;

    // 分配位置映射数组
    Tree ***pos_map = (Tree ***)malloc(depth * sizeof(Tree **));
    for (int i = 0; i < depth; i++)
    {
        pos_map[i] = (Tree **)calloc(max_width, sizeof(Tree *));
    }

    QueueItem queue[100];
    int front = 0, rear = 0;

    // 根节点居中
    int root_pos = (max_width - 1) / 2;
    queue[rear].node = T;
    queue[rear].level = 0;
    queue[rear].pos = root_pos;
    rear++;

    while (front < rear)
    {
        Tree *current = queue[front].node;
        int level = queue[front].level;
        int pos = queue[front].pos;
        front++;

        // 存储节点指针
        if (level < depth && pos >= 0 && pos < max_width)
        {
            pos_map[level][pos] = current;
        }

        int offset = (max_width + 1) >> (level + 2);
        if (current->l && (pos - offset) >= 0)
        {
            queue[rear].node = current->l;
            queue[rear].level = level + 1;
            queue[rear].pos = pos - offset;
            rear++;
        }
        if (current->r && (pos + offset) < max_width)
        {
            queue[rear].node = current->r;
            queue[rear].level = level + 1;
            queue[rear].pos = pos + offset;
            rear++;
        }
    }
    // 打印
    for (int l = 0; l < depth; l++)
    {
        for (int p = 0; p < max_width; p++)
        {
            if (pos_map[l][p] != NULL)
            {
                printf("%-1d", pos_map[l][p]->data);
            }
            else
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    for (int i = 0; i < depth; i++)
    {
        free(pos_map[i]);
    }
    free(pos_map);
}
int eighteen(Tree *T, int dep)
{

    if (T == NULL)
        return 0;
    if (T->l == NULL && T->r == NULL)
    {
        return (T->data) * dep;
    }
    return eighteen(T->l, dep + 1) + eighteen(T->r, dep + 1);
}

int main()
{
    Tree *L[100] = {NULL};
    // int y = 1;
    int select = 1;
    while (select != 0)
    {
        printf("请输入对哪个二叉树进行操作(1-99)，输入0退出\n");
        scanf(" %d", &select);
        if (L[select] == NULL)
        {
            L[select] = (Tree *)malloc(sizeof(Tree));
        }
        if (select == 0)
            break;
        int y = 1;
        while (y != 0)
        {
            printf("\n  Menu for Linear Table On Sequence Structure\n");
            printf("-----------------------------------------------\n");
            printf("1.CreateBiTree\t9.InsertNode\t\n");
            printf("2.DestroyBiTree\t10.DeleteNode\t\n");
            printf("3.ClearBiTree\t11.PreOrderTraverse（改）\t\n");
            printf("4.BiTreeEmpty\t12.InOrderTraverse\t\n");
            printf("5.BiTreeDepth\t13.PostOrderTraverse\t\n");
            printf("6.LocateNode\t14.LevelOrderTraverse\t\n");
            printf("7.Assign\t15.Write\t\n");
            printf("8.GetSibling\t16.Read\t\n");
            printf("0.Exit\t17.图显\t\n");
            printf("18.计算wpl\t\n");
            printf("-----------------------------------------------\n");
            printf("请选择你的操作[0~16]\n"); // ABCDEF####GHI#J

            scanf(" %d", &y);
            if (y == 1)
            {
                printf("请输入你要创建的二叉树的前序遍历：\n"); // ABC##DEH##G##F###

                char definition[100] = {0};
                char *p = definition;
                scanf(" %s", definition);
                L[select]->r = NULL;
                L[select]->key = 0;
                CreateBiTree(&L[select], &p);
                printf("二叉树创建成功！\n");
            }
            if (y == 2)
            {
                DestroyBiTree(&L[select]);
            }
            if (y == 3)
            {
                ClearBiTree(L[select]);
            }
            if (y == 4)
            {
                BiTreeEmpty(L[select]);
            }
            if (y == 5)
            {
                int length = BiTreeDepth(L[select]);
                printf("二叉树的深度为%d\n", length);
            }

            if (y == 6)
            {
                char e;
                printf("请输入你要查询节点的关键词\n");
                scanf(" %c", &e);
                Tree *p;
                p = LocateNode(L[select], e);
                printf("该节点为：%c:%d\n", p->key, p->data);
            }
            if (y == 7)
            {
                char e;
                int value;
                printf("请输入你要赋值的节点的关键词与要赋值的值\n");
                scanf(" %c %d", &e, &value);
                Assign(L[select], e, value);
            }
            if (y == 8)
            {
                char e;
                Tree *p;
                printf("请输入你要查询节点的关键词:\n");
                scanf(" %c", &e);
                p = GetSibling(L[select], e);
                printf("该节点的兄弟节点为%c:%d\n", p->key, p->data);
            }
            if (y == 9)
            {
                Tree *p;
                p = (Tree *)malloc(sizeof(Tree));
                char e;
                int LR;
                printf("请输入你要插入位置的关键词，左(0)右(1)关系，要插入节点的关键词，数据\n");
                scanf(" %c %d %c %d", &e, &LR, &p->key, &p->data);
                InsertNode(L[select], e, LR, p);
            }
            if (y == 10)
            {
                char e;
                printf("请输入你要删除节点的关键词:\n");
                scanf(" %c", &e);
                DeleteNode(L[select], e);
            }
            if (y == 11)
            {
                printf("请输入你要开始前序遍历的节点的关键词：\n");
                char e;
                scanf(" %c", &e);
                Tree *new_p = fu(L[select], e);
                printf("\n前序遍历：\n");
                PreOrderTraverse(new_p);
            }
            if (y == 12)
            {
                printf("中序遍历：\n");
                InOrderTraverse(L[select]);
            }
            if (y == 13)
            {
                printf("后序遍历：\n");
                PostOrderTraverse(L[select]);
            }
            if (y == 14)
            {
                printf("按层遍历：\n");
                LevelOrderTraverse(L[select]);
            }
            if (y == 15)
            {
                Wirte(L[select]);
                printf("input flie name: 二叉树存档\n");
                printf("写入成功！\n");
            }
            if (y == 16)
            {
                Read(&L[select]);
                printf("output flie name：二叉树存档\n");
                printf("读取成功！\n");
            }
            if (y == 17)
            {
                printf("显示二叉树：\n");
                seventeen(L[select]);
            }
            if (y == 18)
            {
                printf("该树的WPL是:%d\n", eighteen(L[select], 1));
            }
        }
    }
    printf("欢迎下次再使用本系统！"); // ABC##DEH##G##F###   5310##2##4##76##8#9###
    // ABCD##E##F##GH##I#J###
    return 0;
}

4.基于邻接表的图实现

1.1思路：

通过链式结构来存图，然后以顶点为入口，通过访问每个顶点的边链表，从而遍历整个图的边

1.2各部分的功能实现：

头文件：

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

这个作业我用了宏，可读性强一些

1 2	#define MAX_GRAPH 100 #define MAX_VERTEX 100

图的结构组成：我是先构造节点，然后再构造图：

typedef struct node
{
    int ver;
    struct node *next;
} Node;

typedef struct
{
    Node *adj[MAX_VERTEX];//表示从第i个顶点出发的边的链表
    char keys[MAX_VERTEX];//第i个顶点的名称（字符）
    bool exists[MAX_VERTEX];//标记顶点是否存在
    int vnum, arcnum;//顶点数和边数
    int values[MAX_VERTEX];
} Graph;

然后就是创建100个图的操作，看起来只有一个指针，但其实根据结构体的嵌套定义，和前面2个作业的定义差不多

1	Graph graphs[MAX_GRAPH];

核心操作就是遍历顶点，然后寻找：

//这是定位顶点操作的核心步骤
for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (g->exists[i] && g->keys[i] == key)
            return i;
    }

创建图：

int CreateGraph(Graph *g, char V[], char VR[][2], int vnum, int arcnum)
{
    memset(g, 0, sizeof(Graph));//初始化图先
    g->vnum = vnum;
    //初始化顶点数组
    for (int i = 0; i < vnum; i++)
    {
        g->keys[i] = V[i];
        g->exists[i] = true;
    }
    //构建邻接表
    for (int i = 0; i < arcnum; i++)
    {
        int u = LocateVex(g, VR[i][0]);
        int v = LocateVex(g, VR[i][1]);
        if (u == -1 || v == -1)
            continue;
		//创建新节点并插入邻接表尾部
        Node *newnode = (Node *)malloc(sizeof(Node));
        newnode->ver = v;
        newnode->next = NULL;

        if (g->adj[u] == NULL)
        {
            g->adj[u] = newnode;
        }
        else
        {
            Node *tail = g->adj[u];
            while (tail->next != NULL)
                tail = tail->next;
            tail->next = newnode;
        }
        g->arcnum++;
    }
    return 1;
}

然后销毁图就是一直履历图到底，一个个销毁：

int DestroyGraph(Graph *g) {
    for (int i = 0; i < MAX_VERTEX; i++) {
        // 释放邻接表节点
        Node *p = g->adj[i];
        while (p) {
            Node *tmp = p;
            p = p->next;
            free(tmp);
        }
        g->adj[i] = NULL;
        g->exists[i] = false;
    }
    g->vnum = 0;
    g->arcnum = 0;
    return 1;
}

插入新顶点

int InsertVex(Graph *g, char key, char value) {//*g: 图指针，key: 顶点关键字，value: 顶点存储的值（注意char到int的类型转换）
    if (LocateVex(g, key) != -1)
        return -1;
    //寻找第一个空闲位置
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (!g->exists[i]) {
            g->keys[i] = key;
            g->values[i] = value; //注意char到int的类型转换
            g->exists[i] = true;
            g->vnum++;
            return i;
        }
    }
    return -1;
}

赋值就调用定位函数，然后赋值

1 2	int idx = LocateVex(g, key); g->values[idx] = value;

获取指定邻接顶点的下一个邻接顶点

int NextAdjVex(Graph *g, char key, char adj_key) {
    int u = LocateVex(g, key);
    int v = LocateVex(g, adj_key);
    if (u == -1 || v == -1) return 0;

    // 遍历邻接表寻找下一个节点
    Node *p = g->adj[u];
    while (p && p->ver != v)
        p = p->next;
    return (p && p->next) ? p->next->ver : 0;
}

插入新边，我是用头插

void InsertArc(Graph *g, char u, char v) {
    int u_idx = LocateVex(g, u);
    int v_idx = LocateVex(g, v);
    if (u_idx == -1 || v_idx == -1) return;//越界要返回，越界处理一定不要忘记

    // 头插法插入新边
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->ver = v_idx;
    newnode->next = g->adj[u_idx];
    g->adj[u_idx] = newnode;
    g->arcnum++;
}

删除边：

void DeleteArc(Graph *g, char u, char v) {
    int u_idx = LocateVex(g, u);
    int v_idx = LocateVex(g, v);
    if (u_idx == -1 || v_idx == -1) return;

    // 遍历邻接表删除指定边
    Node *prev = NULL, *current = g->adj[u_idx];
    while (current) {
        //如果当前节点的目标顶点是 v，说明找到了该边
        if (current->ver == v_idx) {
            //如果 prev 不为空，表示要删除的节点不是链表的第一个节点
            if (prev) {
                //删除当前节点，将前一个节点的 next 指向当前节点的下一个节点
                prev->next = current->next;
            } else {
                //如果 prev 为空,表示当前节点是链表的第一个节点,更新顶点 u 的邻接链表头指针
                g->adj[u_idx] = current->next;
            }
            free(current);
            g->arcnum--;
            return;
        }
        prev = current;
        current = current->next;
    }
}

删除顶点及相关边

DeleteArc只操作一个顶点的邻接链表，删除该顶点到另一顶点的边。

DeleteVex 需要处理当前顶点的出边，还需要遍历所有其他顶点的邻接链表，删除指向当前顶点的入边。

// 删除顶点的出边
Node *p = g->adj[idx];
while (p) {
    Node *tmp = p;
    p = p->next;
    free(tmp);
    g->arcnum--;
}
g->adj[idx] = NULL;

// 删除其他顶点的入边
for (int i = 0; i < MAX_VERTEX; i++) {
    if (!g->exists[i]) continue;
    Node *prev = NULL, *curr = g->adj[i];
    while (curr) {
        if (curr->ver == idx) {
            if (prev) {
                prev->next = curr->next;
            } else {
                g->adj[i] = curr->next;
            }
            Node *tmp = curr;
            curr = curr->next;
            free(tmp);
            g->arcnum--;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
}

dfs的不断递归遍历：

void DFS(Graph *g, int v, bool visited[]) {
    visited[v] = true;
    printf("%c   %d\n", g->keys[v], g->values[v]);
    Node *p = g->adj[v];
    while (p) {
        if (!visited[p->ver])
            DFS(g, p->ver, visited);
        p = p->next;
    }
}

基于队列的bfs遍历：

void BFSTraverse(Graph *g) {
    bool visited[MAX_VERTEX] = {false};
    printf("\n");
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (g->exists[i] && !visited[i]) {
            // 使用队列实现BFS
            int queue[MAX_VERTEX];
            int front = 0, rear = 0;
            visited[i] = true;
            printf("%c  %d\n", g->keys[i], g->values[i]);
            queue[rear++] = i;
            while (front != rear) {
                int v = queue[front++];
                Node *p = g->adj[v];
                while (p) {
                    int u = p->ver;
                    if (!visited[u]) {
                        visited[u] = true;
                        printf("%c  %d\n", g->keys[u], g->values[u]);
                        queue[rear++] = u;
                    }
                    p = p->next;
                }
            }
        }
    }
    printf("\n");
}

写入操作，这里还是用fwrite二进制存入的方法

void Write(Graph *g, const char *filename) {
    // 打开文件，二进制写入模式
    FILE *fp = fopen(filename, "wb");
    if (!fp) {
        printf("无法写入！\n");
        return;
    }
    // 写入顶点数和边数
    fwrite(&g->vnum, sizeof(int), 1, fp);  //写入顶点数
    fwrite(&g->arcnum, sizeof(int), 1, fp);  //写入边数
    //写入顶点数据
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (g->exists[i]) {  //如果顶点存在
            fwrite(&i, sizeof(int), 1, fp);  //写入顶点索引
            fwrite(&g->keys[i], sizeof(char), 1, fp);  //写入顶点关键字
            fwrite(&g->values[i], sizeof(int), 1, fp);  //写入顶点值
        }
    }
    int end_mark = -1;  //这里定义一个结束标记
    fwrite(&end_mark, sizeof(int), 1, fp);  //写入结束标记
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (!g->exists[i]) continue;  //如果顶点不存在则跳过
        Node *p = g->adj[i];
        while (p) {  //遍历当前顶点的邻接链表
            int u = i;  //当前顶点
            int v = p->ver;  //邻接顶点
            fwrite(&u, sizeof(int), 1, fp);  //写入边的起始顶点
            fwrite(&v, sizeof(int), 1, fp);  //写入边的终止顶点
            p = p->next;  //移动到下一个邻接点
        }
    }
    fwrite(&end_mark, sizeof(int), 1, fp);  //写入结束标记
    fclose(fp);  //关闭文件
}

读取操作：

void Read(Graph *g, const char *filename) {
    //打开文件，二进制读取模式
    FILE *fp = fopen(filename, "rb");
    if (!fp) {
        printf("无法读取!\n");
        return;
    }
    DestroyGraph(g);  //清空图
    //读取顶点数和边数
    fread(&g->vnum, sizeof(int), 1, fp);  //读取顶点数
    fread(&g->arcnum, sizeof(int), 1, fp);  //读取边数

    
    //读取顶点数据
    int pos;
    while (1) {
        fread(&pos, sizeof(int), 1, fp);  //,读取顶点索引
        if (pos == -1) break;  //遇到结束标记-1，则结束读取
        fread(&g->keys[pos], sizeof(char), 1, fp);  //读取顶点关键字
        fread(&g->values[pos], sizeof(int), 1, fp);  //读取顶点值
        g->exists[pos] = true;  //标记该顶点存在
    }
    //读取边数据并重建邻接表
    int u, v;
    while (1) {
        fread(&u, sizeof(int), 1, fp);  //,读取边的起始顶点
        if (u == -1) break;  //遇到结束标记-1，则结束读取
        fread(&v, sizeof(int), 1, fp);  //读取边的终止顶点
        Node *newnode = (Node *)malloc(sizeof(Node));
        newnode->ver = v;  //设置边的终止顶点
        newnode->next = NULL;  //这个边是链表中的最后一个节点
        //这里是用尾插法重建邻接表
        if (g->adj[u] == NULL) {
            g->adj[u] = newnode;  //如果该顶点没有邻接表，直接插入
        } else {
            Node *tail = g->adj[u];
            while (tail->next)  //遍历到邻接链表的尾部
                tail = tail->next;
            tail->next = newnode;  //将新节点插入到链表的末尾
        }
    }
    fclose(fp);  //关闭文件
}

1.3原码

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

#define MAX_GRAPH 100
#define MAX_VERTEX 100
typedef struct node
{
    int ver;
    struct node *next;
} Node;

typedef struct
{
    Node *adj[MAX_VERTEX];
    char keys[MAX_VERTEX];
    bool exists[MAX_VERTEX];
    int vnum, arcnum;
    int values[MAX_VERTEX];
} Graph;

Graph graphs[MAX_GRAPH];
// int current_graph = 0;
int LocateVex(Graph *g, char key)
{
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (g->exists[i] && g->keys[i] == key)
            return i;
    }
    return -1;
}

int CreateGraph(Graph *g, char V[], char VR[][2], int vnum, int arcnum)
{
    memset(g, 0, sizeof(Graph));
    g->vnum = vnum;
    for (int i = 0; i < vnum; i++)
    {
        g->keys[i] = V[i];
        g->exists[i] = true;
    }
    for (int i = 0; i < arcnum; i++)
    {
        int u = LocateVex(g, VR[i][0]);
        int v = LocateVex(g, VR[i][1]);
        if (u == -1 || v == -1)
            continue;

        Node *newnode = (Node *)malloc(sizeof(Node));
        newnode->ver = v;
        newnode->next = NULL;

        if (g->adj[u] == NULL)
        {
            g->adj[u] = newnode;
        }
        else
        {
            Node *tail = g->adj[u];
            while (tail->next != NULL)
                tail = tail->next;
            tail->next = newnode;
        }
        g->arcnum++;
    }
    return 1;
}

int DestroyGraph(Graph *g)
{
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        Node *p = g->adj[i];
        while (p)
        {
            Node *tmp = p;
            p = p->next;
            free(tmp);
        }
        g->adj[i] = NULL;
        g->exists[i] = false;
    }
    g->vnum = 0;
    g->arcnum = 0;
    return 1;
}
int InsertVex(Graph *g, char key, char value)
{
    if (LocateVex(g, key) != -1)
        return -1;
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (!g->exists[i])
        {
            g->keys[i] = key;
            g->exists[i] = true;
            g->vnum++;
            return i;
        }
    }
    return -1;
}
void PutVex(Graph *g, char key, int value)
{
    int idx = LocateVex(g, key);
    if (idx != -1)
    {
        g->values[idx] = value;
        printf("赋值成功！\n");
    }
    else
    {
        printf("赋值失败！\n");
    }
}

int FirstAdjVex(Graph *g, char key)
{
    int u = LocateVex(g, key);
    if (u == -1)
        return 0;
    Node *p = g->adj[u];
    if (p)
        return LocateVex(g, g->keys[p->ver]);
    return 0;
}
int NextAdjVex(Graph *g, char key, char adj_key)//---
{
    int u = LocateVex(g, key);
    int v = LocateVex(g, adj_key);
    if (u == -1 || v == -1)
        return 0;
    Node *p = g->adj[u];
    while (p && p->ver != v)
        p = p->next;
    if (p && p->next)
        return LocateVex(g, g->keys[p->next->ver]);
    return 0;
}
void InsertArc(Graph *g, char u, char v)
{
    int u_idx = LocateVex(g, u);
    int v_idx = LocateVex(g, v);
    if (u_idx == -1 || v_idx == -1)
    {
        return;
    }
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->next = g->adj[u_idx];
    newnode->ver = v_idx; //

    g->adj[u_idx] = newnode;
    g->arcnum++;
}

void DeleteArc(Graph *g, char u, char v)
{
    int u_idx = LocateVex(g, u);
    int v_idx = LocateVex(g, v);
    if (u_idx == -1 || v_idx == -1)
    {
        return;
    }
    Node *prev = NULL, *current = g->adj[u_idx];
    while (current)
    {
        if (current->ver == v_idx)
        {
            if (prev)
                prev->next = current->next;
            else
                g->adj[u_idx] = current->next;
            free(current);
            g->arcnum--;
            return;
        }
        prev = current;
        current = current->next;
    }
}

int DeleteVex(Graph *g, char key)
{
    int idx = LocateVex(g, key);
    if (idx == -1)
        return 0;
    Node *p = g->adj[idx];
    while (p)
    {
        Node *tmp = p;
        p = p->next;
        free(tmp);
        g->arcnum--;
    }
    g->adj[idx] = NULL;
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (!g->exists[i])
            continue;
        Node *prev = NULL, *curr = g->adj[i];
        while (curr)
        {
            if (curr->ver == idx)
            {
                if (prev)
                    prev->next = curr->next;
                else
                    g->adj[i] = curr->next;
                Node *tmp = curr;
                curr = curr->next;
                free(tmp);
                g->arcnum--;
            }
            else
            {
                prev = curr;
                curr = curr->next;
            }
        }
    }
    g->exists[idx] = false;
    g->vnum--;
    return 1;
}

void DFS(Graph *g, int v, bool visited[])
{
    visited[v] = true;
    printf("%c   %d\n", g->keys[v], g->values[v]);
    Node *p = g->adj[v];
    while (p)
    {
        if (!visited[p->ver])
            DFS(g, p->ver, visited);
        p = p->next;
    }
}

void DFSTraverse(Graph *g)
{
    bool visited[MAX_VERTEX] = {false};
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (g->exists[i] && !visited[i])
            DFS(g, i, visited);
    }
    printf("\n");
}

void BFSTraverse(Graph *g)
{
    bool visited[MAX_VERTEX] = {false};
    printf("\n");
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (g->exists[i] && !visited[i])
        {
            int queue[MAX_VERTEX];
            int front = 0, rear = 0;
            visited[i] = true;
            printf("%c  %d\n", g->keys[i], g->values[i]);
            queue[rear++] = i;
            while (front != rear)
            {
                int v = queue[front++];
                Node *p = g->adj[v];
                while (p)
                {
                    int u = p->ver;
                    if (!visited[u])
                    {
                        visited[u] = true;
                        printf("%c  %d\n", g->keys[u], g->values[u]);
                        queue[rear++] = u;
                    }
                    p = p->next;
                }
            }
        }
    }
    printf("\n");
}
void Write(Graph *g, const char *filename)
{
    FILE *fp;
    fp = fopen(filename, "wb");
    if (!fp)
    {
        printf("无法写入！\n");
        return;
    }

    fwrite(&g->vnum, sizeof(int), 1, fp);//二进制存
    fwrite(&g->arcnum, sizeof(int), 1, fp);
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (g->exists[i])
        {
            fwrite(&i, sizeof(int), 1, fp);
            fwrite(&g->keys[i], sizeof(char), 1, fp);
            fwrite(&g->values[i], sizeof(int), 1, fp);
        }
    }
    int a = -1;
    fwrite(&a, sizeof(int), 1, fp);
    for (int i = 0; i < MAX_VERTEX; i++)
    {
        if (!g->exists[i])
            continue;

        Node *p = g->adj[i];
        while (p)
        {
            int u = i;
            int v = p->ver;
            fwrite(&u, sizeof(int), 1, fp);
            fwrite(&v, sizeof(int), 1, fp);
            p = p->next;
        }
    }
    a = -1;
    fwrite(&a, sizeof(int), 1, fp);

    fclose(fp);
}
void Read(Graph *g, const char *filename)
{
    FILE *fp;
    fp = fopen(filename, "rb");
    if (!fp)
    {
        printf("无法读取!\n");
        return;
    }
    DestroyGraph(g);
    fread(&g->vnum, sizeof(int), 1, fp);
    fread(&g->arcnum, sizeof(int), 1, fp);

    int pos;
    while (1)
    {
        fread(&pos, sizeof(int), 1, fp);
        if (pos == -1)
            break;

        fread(&g->keys[pos], sizeof(char), 1, fp);
        fread(&g->values[pos], sizeof(int), 1, fp);
        g->exists[pos] = true;
    }

    int u, v;
    while (1)
    {
        fread(&u, sizeof(int), 1, fp);
        if (u == -1)
            break;
        fread(&v, sizeof(int), 1, fp);
        Node *newnode = (Node *)malloc(sizeof(Node));
        newnode->ver = v;
        newnode->next = NULL;
        if (g->adj[u] == NULL)
        {
            g->adj[u] = newnode;
        }
        else
        {
            Node *tail = g->adj[u];
            while (tail->next)
                tail = tail->next;
            tail->next = newnode;
        }
    }

    fclose(fp);
}
int main()
{
    int select = 1;

    while (1)
    {
        printf("\n请输入对哪个图进行操作(1-99),输入0退出！\n");
        scanf(" %d", &select);
        Graph *G = &graphs[select];
        if (select == 0)
        {
            break;
        }
        int s1;
        s1 = 1;
        while (1)
        {
            printf("\n  Menu for Linear Table On Sequence Structure\n");
            printf("----------------------------------------------\n");
            printf("  1.CreatGraph\t8.DeleteVex\t\n");
            printf("  2.DestroyGraph 9.InsertArc\t\n");
            printf("  3.LocateVex\t10.DeleteArc\t\n");
            printf("  4.PutVex\t11.DFSTraverse\t\n");
            printf("  5.FirstAdjVex\t12.BFSTraverse\t\n");
            printf("  6.NextAdjVex\t13.Write\t\n");
            printf("  7.InsertVex\t14.Read\t\n");
            printf("  0.Exit\n");
            printf("----------------------------------------------\n");
            printf("  请选择你要输入的操作[0~14]\n");
            scanf("%d", &s1);
            if (s1 == 0)
                break;
            switch (s1)
            {

            case 1:
            {
                int vnum, arcnum;
                printf("请输入图的顶点数和弧数: \n");
                scanf(" %d %d", &vnum, &arcnum);
                char vertices[MAX_VERTEX];
                char arcs[MAX_VERTEX][2];
                printf("请输入%d个顶点:\n", vnum);
                for (int i = 0; i < vnum; i++)
                {
                    scanf(" %c", &vertices[i]);
                }
                printf("请输入%d个弧：\n", arcnum);
                for (int i = 0; i < arcnum; i++)
                {
                    scanf(" %c %c", &arcs[i][0], &arcs[i][1]);
                }
                CreateGraph(G, vertices, arcs, vnum, arcnum);
                printf("图创建成功！\n");
                break;
            }
            case 2:
            {
                DestroyGraph(G);
                printf("图已销毁！\n");
                break;
            }
            case 3:
            {
                char key;
                printf("请输入需要查找的顶点关键字: ");
                scanf(" %c", &key);
                int pos = LocateVex(G, key);
                if (pos != -1)
                    printf("该顶点的位序是: %d\n", pos);
                break;
            }
            case 4:
            {
                char key;
                int value;
                printf("请输入需要赋值顶点的关键字和所赋的值:\n ");
                scanf(" %c %d", &key, &value);
                PutVex(G, key, value);
                break;
            }
            case 5:
            {
                char key;
                printf("请输入需要获取第一邻接点的顶点的关键字:\n ");
                scanf(" %c", &key);
                char adj = FirstAdjVex(G, key);
                if (adj != '\0')
                    printf("该顶点的第一邻接顶点的位序为: %d\n", adj);
                else
                    printf("该顶点不存在邻接顶点\n");
                break;
            }

            case 6:
            {
                char key, adj_key;
                printf("请输入需要获得下一邻接点的 顶点 的关键字及邻接点位序：\n");
                scanf(" %c %c", &key, &adj_key);
                char next_adj = NextAdjVex(G, key, adj_key);
                if (next_adj != '\0')
                    printf("下一邻接顶点的位序为: %d\n", next_adj);
                else
                    printf("顶点没有下一邻接顶点\n", key);
                break;
            }
            case 7:
            {
                char key, value;
                printf("请输入需要插入顶点的关键字和所赋值: \n");
                scanf(" %c %c", &key, &value);
                int pos = InsertVex(G, key, value);
                if (pos != -1)
                    printf("插入成功！\n");
                else
                    printf("顶点已存在，插入失败！\n");
                break;
            }
            case 8:
            {
                char key;
                printf("请输入要删除的顶点的关键字:\n");
                scanf(" %c", &key);
                if (DeleteVex(G, key))
                    printf("删除成功！\n");
                else
                    printf("删除失败！\n");
                break;
            }
            case 9:
            {
                char u, v;
                printf("请输入需要插入弧的顶点的关键字：\n");
                scanf(" %c %c", &u, &v);
                InsertArc(G, u, v);
                printf("插入成功!\n");
                break;
            }
            case 10:
            {
                char u, v;
                printf("请输入需要删除弧的顶点的关键字：\n");
                scanf(" %c %c", &u, &v);
                DeleteArc(G, u, v);
                printf("删除成功！\n");
                break;
            }
            case 11:
            {
                printf("请输入遍历第一个顶点的关键字:\n");
                DFSTraverse(G);
                break;
            }
            case 12:
            {
                printf("BFS遍历结果：");
                BFSTraverse(G);
                break;
            }
            case 13:
            {

                Write(G, "邻接表存档.txt");
                printf("INPUT FILE NAME:邻接表存档.txt\n ");
                break;
            }
            case 14:
            {
                Read(G, "邻接表存档.txt");
                printf("OUTPUT FILE NAME:邻接表存档.txt ");
                break;
            }
            }
        }
        printf("欢迎下次再使用本系统！\n");
    }
    return 0;
}