一、设计任务
    设计一个应用程序（C/C++），利用多级菜单实现单链表、栈、队列、二叉树及图五种结构的基本操作及应用。具体内容包括：

    1. 单链表的基本操作及应用
      1. 创建
      2. 插入
      3. 删除
      4. 查找
      5. 应用
    2. 栈的基本操作及应用
      1. 进栈
      2. 出栈
      3. 取栈顶元素
      4. 应用
    3. 队列的基本操作及应用
      1. 入列
      2. 出列
      3. 取队头元素
      4. 取队尾元素
      5. 应用
    4. 二叉树的基本操作及应用
      1. 创建
      2. 遍历（先序、中序、后序）
      3. 求树的深度
      4. 查找双亲
      5. 查找兄弟（左/右）
      6. 查找孩子（左/右）
      7. 应用
    5. 图的基本操作及应用
      1. 创建（邻接矩阵/邻接表）
      2. 遍历（深度/广度）
      3. 定位
      4. 找第一个邻接点
      5. 找下一个邻接点
      6. 应用

    注：在各种结构中，利用该结构的基本操作完成其应用的实现。例如，利用栈的进栈、出栈和取栈顶元素等操作实现如括号匹配、表达式求值等应用问题。具体要求见后续说明。

    二、设计指导（参考）

    1. #include<stdio.h>
    2. void ShowMainMenu(){
    3.     printf("\n");
    4.     printf("*******************算法与数据结构******************\n");
    5.     printf("* 1  单链表的基本操作及应用                       *\n");
    6.     printf("* 2  栈的基本操作及应用                           *\n");
    7.     printf("* 3  队列的基本操作及应用                         *\n");
    8.     printf("* 4  二叉树的基本操作及应用                       *\n");
    9.     printf("* 5  图的基本操作及应用                           *\n");
    10.     printf("* 6  退出                                         *\n");
    11.     printf("***************************************************\n");
    12. }
    14. void LinkList(){
    15.     int n;
    16.     do{
    17.         printf("\n");
    18.         printf("**************单链表的基本操作及应用***************\n");
    19.         printf("* 1  创建                                         *\n");
    20.         printf("* 2  插入                                         *\n");
    21.         printf("* 3  删除                                         *\n");
    22.         printf("* 4  查找                                         *\n");
    23.         printf("* 5  应用                                         *\n");
    24.         printf("* 6  退出                                         *\n");
    25.         printf("***************************************************\n");
    26.         printf("请选择：");
    27.         scanf("%d",&n);
    28.         switch(n){
    29.             case 1:
    30.                 printf("--------创建单链表---------");break;
    31.             case 2:
    32.                 printf("--------插入元素-------");break;
    33.             case 3:
    34.                 printf("--------删除元素-------");break;
    35.             case 4:
    36.                 printf("--------查找元素-------");break;
    37.             case 5:
    38.                 printf("--------应用---------");break;
    39.             case 6: break;
    40.             default:
    41.                 printf("ERROR!");break;        
    42.         }
    43.     }while(n!=6);
    44. }
    46. void Stack(){ 
    47.     int n;
    48.     do{
    49.         printf("\n");
    50.         printf("****************栈的基本操作及应用*****************\n");
    51.         printf("* 1  进栈                                         *\n");
    52.         printf("* 2  出栈                                         *\n");
    53.         printf("* 3  取栈顶元素                                   *\n");
    54.         printf("* 4  应用                                         *\n");
    55.         printf("* 5  退出                                         *\n");
    56.         printf("***************************************************\n");
    57.         printf("请选择：");
    58.         scanf("%d",&n);
    59.         switch(n){
    60.             case 1:
    61.                 printf("--------进栈-------");break;
    62.             case 2:
    63.                 printf("--------出栈-------");break;
    64.             case 3:
    65.                 printf("--------取栈顶元素-------");break;
    66.             case 4:
    67.                 printf("--------应用-------");break;
    68.             case 5:break;
    69.             default:
    70.                 printf("ERROR!");break;
    71.         }
    72.     }while(n!=5);
    73. }
    75. void Queue(){ 
    76.     int n;
    77.     do{
    78.         printf("\n");
    79.         printf("*************队列的基本操作及应用**************\n");
    80.         printf("* 1  入列                                     *\n");
    81.         printf("* 2  出列                                     *\n");
    82.         printf("* 3  取队头元素                               *\n");
    83.         printf("* 4  取队尾元素                               *\n");
    84.         printf("* 5  应用                                     *\n");
    85.         printf("* 6  退出                                     *\n");
    86.         printf("***********************************************\n");
    87.         printf("请选择：");
    88.         scanf("%d",&n);
    89.         switch(n){
    90.             case 1:
    91.                 printf("---------入列-------");break;
    92.             case 2:
    93.                 printf("---------出列-------");break;
    94.             case 3:
    95.                 printf("---------取队头元素-------");break;
    96.             case 4:
    97.                 printf("---------取队尾元素-------");break;
    98.             case 5:
    99.                 printf("---------应用-------");break;
    100.             case 6:break;
    101.             default:
    102.                 printf("ERROR!");break;
    103.         }
    104.     }while(n!=6);
    105. }
    107. void BiTree(){ 
    108.     int n;
    109.     do{
    110.         printf("\n");
    111.         printf("**************二叉树的基本操作及应用***************\n");
    112.         printf("* 1  创建                                         *\n");
    113.         printf("* 2  遍历（先/中/后）                             *\n");
    114.         printf("* 3  求结点个数                                   *\n");
    115.         printf("* 4  求树的深度                                   *\n");
    116.         printf("* 5  查找双亲                                     *\n");
    117.         printf("* 6  查找兄弟（左/右）                            *\n");
    118.         printf("* 7  查找孩子（左/右）                            *\n");
    119.         printf("* 8  应用                                         *\n");
    120.         printf("* 9  退出                                         *\n");
    121.         printf("***************************************************\n");
    122.         printf("请选择：");
    123.         scanf("%d",&n);
    124.         switch(n){
    125.             case 1:
    126.                 printf("---------创建--------");break;
    127.             case 2:
    128.                 printf("---------遍历（先/中/后）-------");break;
    129.             case 3:
    130.                 printf("---------求结点个数-------");break;
    131.             case 4:
    132.                 printf("---------求树的深度-------");break;
    133.             case 5:
    134.                 printf("---------查找双亲-------");break;
    135.             case 6:
    136.                 printf("---------查找兄弟（左/右）-------");break;
    137.             case 7:
    138.                 printf("---------查找孩子（左/右）-------");break;
    139.             case 8:
    140.                 printf("---------应用-------");break;
    141.             case 9:break;
    142.             default:
    143.                 printf("ERROR!");break;
    144.         }
    145.     }while(n!=9);
    146. }
    148. void Graph(){ 
    149.     int n;
    150.     do{
    151.         printf("\n");
    152.         printf("****************图的基本操作及应用*****************\n");
    153.         printf("* 1  创建（邻接矩阵/邻接表）                      *\n");
    154.         printf("* 2  遍历（深度/广度）                            *\n");
    155.         printf("* 3  定位                                         *\n");
    156.         printf("* 4  找第一个邻接点                               *\n");
    157.         printf("* 5  找下一个邻接点                               *\n");
    158.         printf("* 6  应用                                         *\n");
    159.         printf("* 7  退出                                         *\n");
    160.         printf("***************************************************\n");
    161.         printf("请选择：");
    162.         scanf("%d",&n);
    163.         switch(n){
    164.             case 1:
    165.                 printf("---------创建（邻接矩阵/邻接表）-------");break;
    166.             case 2:
    167.                 printf("---------遍历（深度/广度）-------");break;
    168.             case 3:
    169.                 printf("---------定位-------");break;
    170.             case 4:
    171.                 printf("---------找第一个邻接点-------");break;
    172.             case 5:
    173.                 printf("---------找下一个邻接点-------");break;
    174.             case 6:
    175.                 printf("---------应用-------");break;
    176.             case 7:break;
    177.             default:
    178.                 printf("ERROR!");break;
    179.         }
    180.     }while(n!=7);
    181. }
    183. void main(){
    184.     int n;
    185.     do{
    186.         ShowMainMenu();
    187.         printf("请选择：");
    188.         scanf("%d",&n);
    189.         switch(n){
    190.             case 1:LinkList();break;
    191.             case 2:Stack();break;
    192.             case 3:Queue();break;
    193.             case 4:BiTree();break;
    194.             case 5:Graph();break;
    195.             case 6:break;
    196.             default:printf("ERROR!");break;
    197.         }
    198.     }while(n!=6);
    199. }

    三、设计要求
    1）应用要求：参考文件（文件名：应用选题（参考）.doc）里的选题。
    2）程序要求：
    ①程序独立完成，运行正确，无编译错误，无逻辑错误。
    ②所有二级菜单中的基础操作可根据应用需求扩展，原则上不能少于所列出的操作。
    ③应用完成的越多得分越高，其中每种结构的应用也可根据自身兴趣自行设计。
    3）课设报告要求：报告格式规范，语言流畅，功能实现描述清楚，测试设计合理，结论准确。具体内容包括：
    ①设计方案；
    ②实现过程；
    ③实现代码；
    ④测试与结论；
    ⑤难点与收获。

    四、上机安排
    第 16 周

    星期一 星期二 星期三 星期四 星期五 星期六 星期日
    第一、二大节
    （8:00-11:00）    		 物联12001-2 物联12001-2
    第三、四大节
    （14:00-17:00）    		 物联12001-2 物联12001-2 物联12001-2

    地点：主教1301机房

    课设报告封面、封底附后：
    应用选题（参考）

    • 选题1：（队列）线程池。CPU资源有限，当需要使用CPU的线程过多时可利用线程池调度。当向线程池请求一个线程时，如果线程池中没有空闲线程，则将请求排队；当有空闲线程时，取出排队请求的线程。要求：1）满足先请求先服务原则 2）排队线程数不受限制。

    线程池的组成主要分为 3 个部分，这三部分配合工作就可以得到一个完整的线程池：

    任务队列，存储需要处理的任务，由工作的线程来处理这些任务 1.通过线程池提供的 API 函数，将一个待处理的任务添加到任务队列，或者从任务队列中删除

    1. 已处理的任务会被从任务队列中删除
    2. 线程池的使用者，也就是调用线程池函数往任务队列中添加任务的线程就是生产者线程.

    工作的线程（任务队列任务的消费者） ，N个 1.线程池中维护了一定数量的工作线程，他们的作用是是不停的读任务队列，从里边取出任务并处理. 2.工作的线程相当于是任务队列的消费者角色， 3.如果任务队列为空，工作的线程将会被阻塞 (使用条件变量 / 信号量阻塞) 4.如果阻塞之后有了新的任务，由生产者将阻塞解除，工作线程开始工作

    管理者线程（不处理任务队列中的任务），1个

    它的任务是周期性的对任务队列中的任务数量以及处于忙状态的工作线程个数进行检测 当任务过多的时候，可以适当的创建一些新的工作线程 当任务过少的时候，可以适当的销毁一些工作的线程 ———————————————— 版权声明：本文为CSDN博主「houxian1103」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/houxian1103/article/details/122749014

    • [x] 选题2：（栈，一个不够，两个）浏览器前进和后退功能。当我们依次浏览了页面A、B、C后，当前页面为C。若使用浏览器后退功能时，则可依次回到页面B和A。当退到A之后，使用浏览器前进功能，则可以依次回到页面B和C。但若退到B之后浏览了新页面D，则前进或后退到C都不可实现了。

    • [x] 选题3：Top N 热门搜索关键词。搜索引擎每天会接受大量用户的搜索请求，把这些用户输入的搜索关键词存储，并离线统计分析就可得到前N个热门的搜索关键词。如何存储搜索关键词和对应的搜索次数并高效地找出搜索次数最多的前N个热门关键词。

    • [x] 选题4：（图）找社交网络中的用户的“好友”。在社交网络中，常常通过用户之间的“好友关系”来推荐“可能认识的人”。比如，若用户A的好友是用户B，则称用户是用户A一度好友；若用户B的好友为用户C，则用户C是用户A的二度好友；若用户D是用户C的好友，则用户D是用户A的三度好友。如何找到指定用户的三度好友。

    • [x] 选题5：箱子装载问题的最优匹配。若有n个不同容量的箱子，现需将重量为m的物品装载到某个箱子中，如何找到最佳的装载物品的箱子。比如七个不同的箱子a，b，c，d，e，f，g的容量分别为9，10，5，6，4，8，12。当物品的重量为3时，最佳箱子为e；当物品的重量为7时，最佳箱子为8。要求：平均性能O(logn)。

    AVL树的应用_小段学长的博客-CSDN博客_avl树应用
    C语言实现二叉树的非递归遍历Future_LL的博客-CSDN博客二叉树的非递归遍历c语言
    其他：自行设计相应结构的应用。

    算法与数据结构课程设计-物联20级 - 图1
    算法与数据结构课程设计报 告

    系 （院）：_
    专业班级：
    姓 名：
    学 号：
    指导教师：

    指导老师意见：

    成绩: 教师签名：

    年 月 日