一、任务需求

1）算法效率的度量（时间复杂度，空间复杂度）
2）线性表，栈和队列的各种基本算法的操作（初始化，取值，查找，插入，删除）；
3）树和二叉树基本概念，遍历二叉树（先序遍历，中序遍历和后序遍历），哈夫曼树的构造和设计哈夫曼编码；
4）图的存储结构（邻接矩阵，邻接表），图的遍历（深度和广度优先搜索），最小生成树；
5）查找的基本概念（平均查找长度image.png），线性表的查找（顺序查找，折半查找（判定树）），树表的查找（二叉排序树，平衡二叉树）；
6）排序方法（插入排序，交换排序，选择排序）。

二、算法的复杂度

2.1时间复杂度
时间复杂度可简单理解为执行语句的条数，用来度量算法执行时间的长短。
大O渐进表示法：
1）找出执行语句的条数。如果有循环和递归，则忽略简单语句，直接算循环和递归的语句执行次数；如果算法中有包含嵌套的循环，则执行次数通常是将两个循环次数相乘，如果算法中包含并列的循环，则将并且的相加；
2）将语句执行次数的数量级放入大Ο记号中，算法中某个基本语句重复执行的次数是问题规模为n的某个函数image.png,则时间复杂度为image.png。
2.2空间复杂度
空间复杂度可简单理解为执行时创建的变量（包括临时变量）个数。算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。空间复杂度记为image.png。

三、顺序表和链表的比较

3.1线性表
3.1.1顺序存储：顺序表
在逻辑上相邻的数据元素，物理存储位置也相邻，并且顺序表的存储空间需要预先分配。
优点：
a) 顺序表具有按元素序号随机存取表中任意结点；
b) 不用为表示节点间的逻辑关系而增加额外的存储空间；
c) 方法简单且容易实现，各种高级语言中都有数组。
缺点：
a) 在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此n较大的顺序表运算效率很低；
b) 静态分配，程序执行之前必须明确规定存储规模预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出，不便于其动态分配。
完整程序：

  1. #include<iostream.h>
  2. //#include<fstream>
  3. //#include<string>
  4. #include<iomanip>      //exit()函数需要;
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2
  9. typedef int status;      //status 是函数返回值类型，其值是函数结果状态代码。
  10. typedef int ElemType;    //ElemType 为可定义的数据类型，此设为int类型
  12. //顺序表的存储结构
  13. #define MAXSIZE 100     //顺序表可能达到的最大长度
  14. typedef struct{
  15.     ElemType *elem;     //存储空间的基地址
  16.     int length;              //当前长度
  17.     }Sqlist;
  20. status InitList(Sqlist &L)             //算法2.1 顺序表的初始化：构造一个空的顺序表L
  21. {                
  22.     L.elem = new ElemType[MAXSIZE];    //为顺序表分配一个大小为MAXSIZE的数组空间
  23.     if(!L.elem) exit(OVERFLOW);               //存储分配失败退出
  24.     L.length = 0;                  //空表长度为0
  25.     return OK;
  26. }
  27. status GetElem(Sqlist L, int i, ElemType &e) //算法2.2 顺序表的取值
  28. {
  29.     if (i<1||i>L.length) 
  30.         return ERROR; //若i值不合理，返回ERROR
  31.     e=L.elem[i-1];   // e为第i个数据元素的值    
  32.     return OK;
  33. }
  35. int LocateElem(Sqlist L, ElemType e) //算法2.3 顺序表的查找 
  36. {
  37.     int i;
  38.     for(i=0;i< L.length;i++)
  39.         if(L.elem[i]==e) return i+1;
  40.      return 0;
  41. }
  43. status ListInsert(Sqlist &L, int i, ElemType e)//算法2.4 顺序表的插入 
  44. {
  45.     int j;
  46.     if((i<1) || (i>L.length+1)) 
  47.         return ERROR;
  48.     if(L.length==MAXSIZE) 
  49.         return ERROR;
  50.     for(j=L.length-1;j>=i-1;j--)
  51.         L.elem[j+1]=L.elem[j];
  52.     L.elem[i-1]=e;
  53.     ++L.length;
  54.     return OK;
  55. }
  57. status ListDelete(Sqlist &L, int i)//算法2.5 顺序表的删除
  58. {
  59.     int j;
  60.     if ((i<1) || (i>L.length)) return ERROR;
  61.     for (j=i;j<=L.length-1;j++)
  62.         L.elem[j-1]=L.elem[j];
  63.     --L.length;
  64.     return OK;
  65. }
  68. int main()
  69. {
  70.     Sqlist L;   //将L定义为Sqlist类型的变量，
  71.     int choose;
  72.     cout << "1. 建立\n";
  73.     cout << "2. 输入\n";
  74.     cout << "3. 取值\n";
  75.     cout << "4. 查找\n";
  76.     cout << "5. 插入\n";
  77.     cout << "6. 删除\n";
  78.     cout << "7. 输出\n";
  79.     cout << "0. 退出\n\n";
  80.     choose = -1;
  82.     while (choose != 0) {
  83.         cout << "请选择:";
  84.         cin >> choose;
  85.         int array[] = {23,33,21,46,67,98};
  86.         switch (choose) {
  87.             case 1://创建顺序表
  88.                 if (InitList(L))
  89.                     cout << "成功建立顺序表\n\n";
  90.                 else
  91.                     cout << "顺序表建立失败\n\n";
  92.                 break;
  93.             case 2: //顺序表信息输入，将数组array中的值放入顺序表中
  94.                 int i;
  95.                 for (i=0;i<=5;i++)
  96.                     L.elem[i]=array[i];
  97.                     L.length=6;
  98.                     cout<<"已成功输入"<<L.length<<"个数据"<<endl;
  99.                 break;
  100.             case 3://顺序表的取值
  101.                 int getnumber,locate;
  102.                 cout << "请输入要取值的位置: ";
  103.                 cin >> locate;
  104.                 GetElem(L, locate, getnumber);
  105.                 cout<<"线性表第"<<locate<<"个位置的值为: "<<getnumber<<endl;
  106.                 break;
  107.             case 4: //顺序表的查找
  108.                 int looknumber,temp;
  109.                 cout << "请输入要查找的数据: ";
  110.                 cin >> looknumber;
  111.                 temp = LocateElem(L, looknumber);
  112.                 if (temp != 0) {
  113.                     cout << "查找成功\n";
  114.                     cout <<"这个数在线性表中的位置是:" << temp << endl;
  115.                 }
  116.                 else
  117.                     cout <<"查找失败，没有找到这个数" <<endl;
  118.                 break;
  119.             case 5://顺序表的插入 
  120.                 int site; 
  121.                 ElemType aa;
  122.                 cout << "请输入插入表的位置: ";
  123.                 cin >> site;
  124.                 cout << "请输入插入的值: ";
  125.                 cin >> aa;
  126.                 cout << "未插入数据前顺序表长度为:"<<L.length<<endl;
  127.                 ListInsert(L, site, aa);
  128.                 cout << "插入数据后顺序表长度为:"<<L.length<<endl;
  129.                 break;
  130.             case 6: //顺序表的删除
  131.                 int delsite;
  132.                 cout << "请输入要删除的位置: ";
  133.                 cin >> delsite;
  134.                 cout <<"未删除数据前顺序表的长度为:"<<L.length<<endl;
  135.                 ListDelete(L,delsite);
  136.                 cout <<"删除数据后顺序表的长度为:"<<L.length<<endl;
  137.                 break;
  138.             case 7: //顺序表的输出，输出顺序表的长度，并输出表中的数据
  139.                 int j;
  140.                 cout <<"当前线性表的长度为:" <<L.length<<endl;
  141.                 for (j=0; j<=L.length-1;j++)
  142.                     cout << L.elem[j] << endl;
  143.                 break; 
  144.         }
  146.     }
  147.     return 0;
  148. }

3.1.2链式存储：单链表 循环链表
逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。
优点：
a)插入和删除只需要改变指针即可，运算方便；
b)存储空间易于扩充，便于其动态分配。
缺点：
a)需要占用额外的存储空间存储元素之间的逻辑关系，存储密度比顺序表低。
（存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比）；
b)链表不是一种随机存储结构，不能随机存取元素。
完整程序：

  1. #include<iostream.h>
  2. //#include<fstream>
  3. //#include<string>
  4. #include<iomanip>      //exit()函数需要;
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2
  9. typedef int status;      //status 是函数返回值类型，其值是函数结果状态代码。
  10. typedef int ElemType;    //ElemType 为可定义的数据类型，此设为int类型
  11. #define MAXSIZE 100
  13. //单链表的存储结构
  14. typedef struct LNode
  15. {
  16.     ElemType data;     //结点的数据域
  17.     struct LNode *next; //结点的指针域
  18. }LNode, *LinkList;
  21. status InitList(LinkList &L)       //单链表的初始化：构造一个空的单链表L
  22. {                
  23.     L=new LNode;                 //生成新结点作为头结点，用头指针L指向头节点
  24.     L->next=NULL;               //头结点的指针域置空
  25.     return OK;
  26. }
  27. void CreateList(LinkList &L, int n)//单链表数据的录入
  28. {
  29.     LNode *p;
  30.     int i;
  31.     int array[]={23,33,21,45,67,98};//或array[]={98,67,45,21,33,23}
  32.     for (i=n-1;i>=0;i--)            //或for (i=0;i<=n;i++)
  33.     {
  34.         p=new LNode;
  35.         p->data=array[i];
  36.         p->next=L->next;
  37.         L->next=p;
  38.     }
  40. }
  41. status length(LinkList &L)//单链表的长度
  42. {
  43.     LinkList p;
  44.     p=new LNode;    //或不定义头结点;
  45.     int len=0;
  47.     p=L;           //无头结点时：p=L->next;
  48.     while(p->next) //即p的next指向的地址不为空
  49.     {
  50.         len++;
  51.         p=p->next;
  52.     }
  53.                    //无头结点时：len++;
  55.     return len;
  56. }
  60. void output(LinkList &L)//单链表数据的输出
  61. {
  62.     LinkList p;
  63.     p=L->next;
  64.     cout<<"单链表中的元素为:"<<endl;
  65.     while(p!=NULL) //即p指向的地址不为空
  66.     {
  67.         cout<<p->data<<endl;
  68.         p=p->next;
  69.     }
  70. }
  72. void find(LinkList L, int m) //单链表取第m个元素值
  73. {
  74.     LinkList p;
  75.     int i=1;
  77.     p=L->next;
  78.     while(i!=m)
  79.     {
  80.         p=p->next;
  81.         i++;
  82.     }
  83.     cout<<"线性表第"<<m<<"个位置的值为: "<<p->data<<endl;
  84. }
  86. status ListInsert(LinkList &L, int i, ElemType e) //单链表中元素的插入 
  87. {
  88.     LinkList p,s;
  89.     int j=0;
  91.     p=L->next;
  92.     while(p && (j<i-1))
  93.     {
  94.         p=p->next;
  95.         ++j;
  96.     }
  97.     if (!p || j>i-1) return ERROR;
  98.     s=new LNode;
  99.     s->data=e;
  100.     s->next=p->next;
  101.     p->next=s;
  102.     return OK;
  103. }
  105. status ListDelete(LinkList &L, int i)//单链表中元素的删除
  106. {
  107.     LinkList p,q;
  108.     int j=0;
  109.     p=L;
  110.     while ((p->next)&&(j<i-1))
  111.     {
  112.         p=p->next;
  113.         j++;
  114.     }
  116.     if(!(p->next)||(j>i-1)) return ERROR;
  117.     q=p->next;
  118.     p->next=q->next;
  119.     delete q;
  120.     return OK;
  121. }
  124. int main()
  125. {
  126.     LinkList L;   //将L定义为LinkList类型的变量，
  127.     int choose;
  128.     cout << "1. 建立空表\n";
  129.     cout << "2. 录入数据\n";
  130.     cout << "3. 求表长\n";
  131.     cout << "4. 输出数据\n";
  132.     cout << "5. 取值\n";
  133.     cout << "6. 插入\n";
  134.     cout << "7. 删除\n";
  135.     cout << "0. 退出\n\n";
  136.     choose = -1;
  138.     while (choose != 0) {
  139.         cout << "请选择:";
  140.         cin >> choose;
  141.         int array[] = {22,33,21,46,67,98};
  142.         switch (choose) {
  143.             case 1://创建单链表
  144.                 if (InitList(L))
  145.                     cout << "成功建立单链表\n\n";
  146.                 else
  147.                     cout << "单链表建立失败\n\n";
  148.                 break;
  149.             case 2: //录入数据
  150.                 CreateList(L, 6);
  151.                 cout<<"已成功输入数据"<<endl;
  152.                 break;
  153.             case 3: //单链表的表长
  154.                 cout<<"单链表的表长为"<<length(L)<<endl;
  155.                 break;
  156.             case 4://单链表的输出
  157.                 output(L);
  158.                 break; 
  159.             case 5://单链表的取值
  160.                 int site;
  161.                 cout << "请输入要取值的位置: ";
  162.                 cin >> site;
  163.                 find(L, site);
  164.                 break;
  165.             case 6: //单链表的插入
  166.                 int number,temp;
  167.                 cout << "请输入要插入的位置: ";
  168.                 cin >> temp;
  169.                 cout << "请输入要插入的数据: ";
  170.                 cin >> number;
  171.                 ListInsert(L,temp, number); 
  172.                 break;
  173.             case 7://单链表的删除
  174.                 int weizhi; 
  175.                 cout << "请输入删除表的位置: ";
  176.                 cin >> weizhi;
  177.                 ListDelete(L, weizhi);
  178.                 break;
  179.         }
  181.     }
  182.     return 0;
  183. }


3.1.3顺序表与链表的区别
顺序表和链表都具有增、删、查、改的相同功能，但算法复杂度却不相同，如下表所示：


 顺序表 链表


增		 指定位置，不覆盖的添加一个值，后面的值要往后移动，算法复杂度为O(n)。 指定位置添加一个节点，需要从表头遍历到指定位置，算法复杂度为O(n)。如果带有索引的节点，算法复杂度为O(1)。



删		 指定位置，删除一个值时，需要将后面的值向前移动，算法复杂度为O(n)。 指定一个位置，删除一个时，如果没有对指定节点进行索引，需要从表头遍历到指定位置，然后将指定节点删除，算法复杂度为O(n)。如果对指定节点做索引，删除节点的算法复杂度为O(1)。


改		 增和删表数量规模比较大时，平均移动一半的元素，效率不高。 对于有索引的链表，添加和删除只需要O(1)算法复杂度，效率高。因此，链表用于频繁的添加和删除数据时，有优势。


查		 直接查询指定位置值算法复杂度为O(1)。

| 需要遍历节点到指定位置，算法复杂度为O(n)。如果节点指定位置节点有索引，算法复杂度为O(1)。

| |

内存 | 由数组组成的线性表，数组是一组地址连续的单元存储块，分配于栈区，可以自动释放。 | 由不连续的地址节点组成的线性表，每个节点可以是一个单元的地址块或连续地址块，分配于堆区，节点必须手动释放，内存管理比较不方便。 |

四、栈（先进后出）

4.1.1顺序存储：顺序栈
栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top是栈顶元素在顺序栈中的位置。栈底位置固定不变，栈顶位置随着入栈和出栈操作而变化。初始时顺序栈必须确定一个固定的长度，所以有存储个数的限制和空间浪费的问题。
4.1.2链式存储：链栈（单链）
链栈是一种特殊的线性链表，和所有链表一样，是动态存储结构，无需预先分配存储空间。而链栈没有栈满的问题，只有当内存没有空间可用时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。当栈的使用过程中元素个数变化较大时，用链栈是适宜的；反之，应该使用顺序栈。
完整程序：

  1. //问题：
  2. //1.当出栈元素的个数已经超过栈长时，输出结果出现空白；
  3. //2.不能正确理解*S.top++=e与e=*--S.top的含义，可能对这种表示形式不太熟悉;
  4. /*3.实现出栈过程中开始使用的是输入出栈的元素，然后出栈。但是如果输入的不是栈中元素怎么出栈，
  5. 或者输入的元素不遵循“先进后出”的原则又怎么出栈，运行之后果然出现了错误结果；*/
  6. //4.入栈过程中是每次输入一个想要入栈的数据，但是如果想要一次性将多个数据元素入栈操作起来就很麻烦；
  8. //解决：
  9. //1.出栈时应当判断是否栈已空，同理入栈时也应当判断是否栈满；
  10. /*2.通过查看相关资料知道，当S为对象top为指针时，入栈时*S.top++=e与*S.top=e，S.top++是等价的。
  11. 出栈时e=*--S.top与S.top--，e=*S.top是等价的;*/
  12. //3.当已录入栈中元素时，每次出栈的都是栈顶元素，同时可以利用循环结构，输入想要出栈的个数，就可以得到最后栈中的元素；
  13. //4.通过尝试改进，运行结果出现了多处错误，需要重新修改前面定义的算法，所以仍使用的原代码。
  15. #include<iostream.h>
  16. //#include<fstream>
  17. //#include<string>
  18. #include<iomanip>      //exit()函数需要;
  20. #define OK 1
  21. #define ERROR 0
  22. #define OVERFLOW -2
  23. typedef int status;      //status 是函数返回值类型，其值是函数结果状态代码。
  24. typedef int SElemType;    //ElemType 为可定义的数据类型，此设为int类型
  27. //顺序栈的存储结构
  28. #define MAXSIZE 100;
  29. typedef struct 
  30. {
  31.     SElemType *base;     //栈底指针，在栈构造之前和销毁之后，base的值为NULL
  32.     SElemType *top;      //栈顶指针
  33.     int stacksize;       //栈可用的最大容量，当前已分配的存储空间，以元素为单位
  34. }SqStack;
  36. status InitStack(SqStack &S)       //为顺序栈动态分配一个最大容量为MAXSIZEL的数组空间
  37. {                
  38.     S.base=new SElemType[];  //存储分配失败
  39.     if(!S.base) exit(OVERFLOW);    //头结点的指针域置空
  40.     S.top=S.base;                  //top初始为base，空栈
  41.     S.stacksize=MAXSIZE;           //stacksize置为栈的最大容量MAXSIZE
  42.     return OK;
  43. }
  45. status input(SqStack &S, int array[])//录入数据元素
  46. {
  47.     int i;
  48.     if(S.top-S.base==S.stacksize) return ERROR; //栈满
  49.     for (i=0;i<5;i++)
  50.     {
  51.         *S.top++=array[i];
  52.     }
  53.     return OK;
  55. }
  57. status length(SqStack &S)//顺序栈的长度
  58. {
  59.     int len=0;
  61.     len=S.top-S.base;
  63.     return len;
  64. }
  66. status output(SqStack &S)  //显示栈中数据元素
  67. {
  68.     int i;
  69.     if (S.top)
  70.     {
  71.         for (i=0;i<(S.top-S.base);i++)
  72.         {
  73.             cout<<*(S.base+i)<<" ";
  74.         }
  75.         cout<<endl;
  76.     }
  77.     return OK;
  78. }
  80. SElemType push(SqStack &S,int &e)        //实现入栈
  81. {
  82.     if(S.top-S.base==S.stacksize) return ERROR;
  83.     *S.top++ = e;
  84.     return OK; 
  85. }
  87. SElemType gettop(SqStack S)   //获取栈顶元素
  88. {
  89.     if(S.top != S.base) 
  90.         return *(S.top-1);
  91. }
  93. SElemType pop(SqStack &S,int &e)       //实现出栈
  94. {
  95.     if (S.top==S.base) return ERROR;
  96.     e=*--S.top;
  97.     return e;
  98. }
  101. int main()
  102. {
  103.     SqStack S;   
  104.     int choose;
  105.     cout << "1. 栈的初始化\n";
  106.     cout << "2. 录入数据\n";
  107.     cout << "3. 求栈长\n";
  108.     cout << "4. 实现入栈\n";
  109.     cout << "5. 实现出栈\n";
  110.     cout << "0. 退出\n\n";
  111.     choose = -1;
  113.     while (choose != 0) {
  114.         cout << "请选择:";
  115.         cin >> choose;
  116.         int array[]={11,13,15,17,19};
  117.         switch (choose) {
  118.             case 1://创建空栈
  119.                 if (InitStack(S))
  120.                     cout << "成功建立空栈\n\n";
  121.                 else
  122.                     cout << "空栈建立失败\n\n";
  123.                 break;
  124.             case 2: //录入数据
  125.                 input(S,array);
  126.                 output(S);
  127.                 break;
  128.             case 3: //栈长
  129.                 int changdu;
  130.                 changdu=length(S);
  131.                 cout<<"栈长为"<<changdu<<endl;
  132.                 changdu=0;
  133.                 break;
  134.             case 4://实现入栈
  135.                 int aa;
  136.                 cout<<"请输入入栈数据："<<endl;
  137.                 cin>>aa;
  138.                 push(S,aa);
  139.                 output(S);
  140.                 break;
  141.             case 5://实现出栈
  142.                 int n,bb;
  143.                 cout<<"请输入出栈元素的个数："<<endl;
  144.                 cin>>n;
  145.                 if(n<length(S))
  146.                 {
  147.                     cout<<"出栈后栈中元素依次为："<<endl;
  148.                     for(int i=0;i<n;i++)
  149.                     {
  150.                         gettop(S);
  151.                         bb=gettop(S);
  152.                         pop(S,bb);
  153.                     }
  154.                     output(S);
  155.                 }
  156.                 else
  157.                 {
  158.                     cout<<"栈已空"<<endl;
  159.                 }
  160.                 break;
  161.         }
  162.     }
  163.     return 0;
  164. }

五、队列（先进先出）

5.1.1顺序存储：循环队列
1）“假溢出”：队列尚有空间而出现的溢出情况。当front端有元素出队时，front向后移动；当rear端有元素入队时，rear向后移动，若rear已指到队列中下标最大的位置，此时虽然front前面有空间，但再有元素入队也会出现溢出，叫作“假溢出”。当（d）中插入元素出现“假溢出”。
2）改进方案：为充分利用数组的存储空间，将顺序队列的头尾相连，构成一个循环队列，循环队列一般都是用数组来实现的，可将循环队列假想为一个环状的空间。
image.png

“假溢出”
image.png
循环队列
在循环队列中，由于不能以头、尾指针的值是否相同来判断队列空间是“空”还是“满”，所以约定少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为队满。
队空条件：头、尾指针的值相同

  1. Q.front==Q.rear

队满条件：队尾标识的rear在队头标识front的上一个位置

  1. (Q.rear + 1)%MAXSIZE == front

队列长度：

  1. (Q.rear + MAXSIZE - front) % MAXSIZE

5.1.2链式存储：链队（单链）
主要是通过移动对头指针和队尾指针来进行进队的操作，当对头指针和队尾指针同时指向头结点时，队列为空，其余各个功能的实现和单链表相似。初始时循环队列必须确定一个固定长度，所以会有元素个数的限制和浪费空间的问题，链队列不会有溢出的问题，但是每个元素都需要一个指针域，从而也会产生结构性开销。所以当队列元素变化较大时，优先考虑链队列，反之采用循环队列。
完整程序：

  1. //问题：
  2. //1.在录入队中数据元素时参照栈编写Q.base[Q.rear]++=array[i];的错误代码，没有认真思考其中的含义；
  3. //2.循环队列出队时判断是否为空队的方法与栈类似:Q.front == Q.rear，但入队判断是否队满时没能正确写出代码；
  4. //3.编写了output方法后，可以运行，但此方法无任何作用，后面又多次的修改以实现队中数据的输出；
  5. //4.忘记或者错误的使用标点符号，导致运行结果出现了很多错误，逻辑思维还不够严谨；
  6. //5.有时遇到错误时花很多的时间去解决,即使能够成功实现相关步骤，但效率不高。
  7. //解决：
  8. //1.在理解其中的意思后，然后进行了修改Q.base[Q.rear]=array[i]; Q.rear++;
  9. //2.通过查看电子版教科书，循环队列队满时应该为(Q.rear + 1) % MAXQSIZE == Q.front；
  10. //3.由于入队的元素个数远小于队列可能达到的最大长度，所以将队头指针移动，分别获取队中元素值Q.base即可；
  11. //4.修改相关的错误符号，尽量减少出现类似的错误；
  12. //5.记住书本上的重要知识点，同时也要动手操作才行。
  13. #include<iomanip>
  14. #include<iostream.h>
  16. #define OK 1
  17. #define ERROR 0
  18. #define OVERFLOW -1
  20. typedef int Status;
  21. typedef int QElemType;
  23. #define MAXQSIZE   100   //队列可能达到的最大长度
  24. typedef struct
  25. {
  26.     QElemType *base;     //初始化的动态分配存储空间
  27.     int   front;         //头指针，若队列不空，指向队列头元素
  28.     int    rear;     //尾指针，队列不空时,指向队列尾元素的下一个元素
  29. } SqQueue;    
  31. Status InitQueue(SqQueue &Q)  //队列的初始化
  32. {
  33.     Q.base = new QElemType[];
  34.     if(!Q.base) exit(OVERFLOW);
  35.     Q.front = Q.rear = 0;
  36.     return OK;
  37. }
  38. Status input(SqQueue &Q, int array[]) //录入队中数据元素
  39. {
  40.     int i;
  41.     if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; 
  42.     for (i=0;i<5;i++)
  43.     {
  44.         Q.base[Q.rear]=array[i];
  45.         Q.rear++;
  46.     }
  47.     return OK;
  48. }
  50. Status output(SqQueue &Q)  //显示队中数据元素
  51. {
  52.     int i;
  53.     for (i=Q.front;i<Q.rear;i++)
  54.         {
  55.             cout<<Q.base[i]<<" ";
  56.         }
  57.     cout<<endl;
  58.     return OK;
  59. }
  62. QElemType length(SqQueue &Q)   //队列的长度
  63. {
  64.     int len=0;
  65.     len= (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
  66.     return len;
  67. }
  69. Status EnQueue(SqQueue &Q,  QElemType &e) //实现入队
  70. {
  71.     if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; 
  72.     Q.base[Q.rear]= e;
  73.     Q.rear = (Q.rear + 1) % MAXQSIZE;
  74.     return OK;
  75. }
  76. QElemType GetHead(SqQueue &Q)  //取循环队列的对头元素
  77. {
  78.     if(Q.front != Q.rear)
  79.         return Q.base[Q.front];
  80. }
  82. Status DeQueue(SqQueue &Q, QElemType &e) //实现出队
  83. {
  84.     if(Q.front == Q.rear) return ERROR;
  85.     e = Q.base[Q.front];
  86.     Q.front = (Q.front + 1) % MAXQSIZE;
  87.     return OK;
  88. }
  91. Status main()
  92. {
  93.     SqQueue Q; 
  94.     int array[]={11,13,15,17,19};
  95.     int choose;
  96.     cout << "1. 队的初始化\n";
  97.     cout << "2. 录入数据\n";
  98.     cout << "3. 求队长\n";
  99.     cout << "4. 实现入队\n";
  100.     cout << "5. 实现出队\n";
  101.     cout << "0. 退出\n\n";
  102.     choose = -1;
  104.     while(choose != 0)
  105.     {
  106.         cout << "请选择操作内容:";
  107.         cin >> choose;
  108.         switch (choose)
  109.         {
  110.         case 1:   //创建空队列
  111.             if (InitQueue(Q))
  112.                 cout <<"成功建立队列"<<endl;
  113.             else    
  114.                 cout <<"队列建立失败"<<endl;
  115.             break;    
  116.         case 2:     //录入数据
  117.             input(Q,array);
  118.             output(Q);
  119.             cout<<"已成功将元素入队"<<endl;
  120.             break;
  121.         case 3:  //队长
  122.             int changdu;
  123.             changdu = length(Q);
  124.             cout <<"队长为"<<changdu<<endl;
  125.             changdu=0;
  126.             break;
  127.         case 4: //实现入队
  128.             int aa;
  129.             cout <<"请输入要入队的数据: "<<endl;
  130.             cin >> aa;
  131.             EnQueue(Q, aa);
  132.             output(Q);
  133.             break;
  134.         case 5: //实现出队
  135.             int n,bb;
  136.             cout<<"请输入出队元素的个数："<<endl;
  137.             cin>>n;
  138.             if(n<length(Q))
  139.             {
  140.                 cout<<"出队后队中元素依次为："<<endl;
  141.                 for(int i=0;i<n;i++)
  142.                 {
  143.                         GetHead(Q);
  144.                         bb=GetHead(Q);
  145.                         DeQueue(Q, bb);
  146.                 }
  147.                 output(Q);
  148.             }
  149.             else
  150.             {
  151.                 cout<<"队已空"<<endl;
  152.             }
  154.             break;
  155.         }
  156.     }
  157.     return 0;
  158. }

六、树和二叉树

6.1树
由n(n>=0)个结点组成的一个具有层次关系的有限集合，若n=0，则是一棵空树。在一棵树中，度不为0的结点称为分支结点，度为0的结点称为叶子结点，也就是没有后继结点的结点就是叶子结点。
6.2 二叉树
二叉树是树的一种，每个结点最多只能有两个结点。二叉树是有序树，左子树和右子树次序不能颠倒，即使树中某个结点只有一棵子树，也要区别是左子树还是右子树。二叉树还可分为非完全二叉树，完全二叉树，满二叉树。
image.png
6.2.1二叉树的重要特性
（1）在二叉树的第i层上至多有2i-1个结点（i>0）；
（2）深度为k的二叉树至多有2k-1个结点（k>0）；
（3）具有n个结点的完全二叉树，它的深度必为+1；
（4）对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2+1（即n0=n2+1）；
（5）若对完全二叉树中的结点从上至下、从左至右编号，则编号为i（1<=i<=n）的结点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲编号必为i/2（i = 1时除外）。
6.2.2二叉树的遍历
（1）先序遍历 VLR：先根再左再右；
（2）中序遍历 LVR：先左再根再右；
（3）后序遍历 LRV：先左再右再根。

image.png
完整程序：

  1. //问题
  2. //1．把函数createbitree(T)放在if语句里面；
  3. //2．int data; char ch;T->data=ch;导致遍历结果出现错误；
  4. //3. 各种遍历函数中的语句次序有误；
  5. //4. 创建二叉树时，不能理解&T的含义；
  7. //解决
  8. //1. 函数返回值不是真或假，不能直接放在if语句里面；
  9. //2. 将data的类型修改成char类型，否则会自动转换成为int数据类型；
  10. //3. 理解书本上的概念，调整语句次序；
  11. //4. BiTree &T表示传递BiTree T的地址。
  13. #include<iostream.h>
  14. //#include<fstream>
  15. //#include<string>
  16. #include<iomanip>      //exit()函数需要;
  18. #define OK 1
  19. #define ERROR 0
  20. #define OVERFLOW -2
  21. typedef int status;      //status 是函数返回值类型，其值是函数结果状态代码。
  22. typedef int TElemType;    //TElemType 为可定义的数据类型，此设为int类型
  24. #define MAXTSIZE 100     //二叉树的最大结点树
  25. typedef TElemType SqBiTree[100];    //0号单元存储根节点
  26. SqBiTree bt;
  28. //二叉链表的存储结构
  29. typedef struct BiTNode{
  30.     char data;          //结点数据域
  31.     struct BiTNode *lchild,*rchild;    //左右孩子指针
  32. }BiTNode,*BiTree;
  34. //二叉树的建立
  35. void createbitree(BiTree &T) 
  36. {
  37.     char ch;
  38.     cin>>ch;
  39.     if(ch=='#') T=NULL;
  40.     else
  41.     {
  42.         T=new BiTNode;
  43.         T->data=ch;
  44.         createbitree(T->lchild);
  45.         createbitree(T->rchild);
  46.     }
  47. }
  49. //前序遍历
  50. void preordertraverse(BiTree T) 
  51. {
  52.     if(T)
  53.     {
  54.         cout<< T->data<<" ";
  55.         preordertraverse(T->lchild);
  56.         preordertraverse(T->rchild);
  57.     }
  58. }
  60. //中序遍历
  61. void inordertraverse(BiTree &T) 
  62. {
  63.     if(T)
  64.     {
  65.         inordertraverse(T->lchild);
  66.         cout<< T->data<<" ";
  67.         inordertraverse(T->rchild);
  68.     }
  69. }
  73. //后序遍历
  74. void posordertraverse(BiTree &T) 
  75. {
  76.     if(T)
  77.     {
  78.         posordertraverse(T->lchild);
  79.         posordertraverse(T->rchild);
  80.         cout<< T->data<<" ";
  81.     }
  82. }
  84. //深度
  85. int depth(BiTree T)
  86. {
  87.     int m,n;
  88.     if(T==NULL) return 0;
  89.     else
  90.     {
  91.         m=depth(T->lchild);
  92.         n=depth(T->rchild);
  93.         if (m>n) return(m+1);
  94.         else return(n+1);
  95.     }
  96. }
  98. //结点总个数
  99. int nodecount(BiTree T)
  100. {
  101.     if(T==NULL) return 0;
  102.     else return nodecount(T->lchild)+nodecount(T->rchild)+1;
  103. }
  105. //叶子结点
  106. void  leaf(BiTree T) 
  107. {
  108.     if (T!=NULL)
  109.     {
  110.         if (T->lchild==NULL && T->rchild==NULL)
  111.             cout<< T->data<<" ";
  112.         leaf(T->lchild);      
  113.         leaf(T->rchild);      
  114.     }
  116. }
  118.  //叶子结点的个数
  119. int leafcount(BiTree T)
  120. {
  121.     int leafnum;
  122.     if(T==NULL)    
  123.         leafnum=0;
  124.     else 
  125.         if((T->lchild==NULL)&&(T->rchild==NULL))
  126.             leafnum=1;
  127.         else 
  128.             leafnum=leafcount(T->lchild)+leafcount(T->rchild);
  130.     return leafnum;
  131. }
  133. //度为1的结点个数
  134. int count1(BiTree T)
  135. {
  136.     int i=0;
  137.     if(T!=NULL)
  138.     {
  139.         if((T->lchild!=NULL && T->rchild==NULL)||(T->lchild==NULL && T->rchild!=NULL))
  140.         {
  141.             i=count1(T->lchild)+count1(T->rchild)+1;
  142.         }
  143.         else
  144.         {
  145.             i=count1(T->lchild)+count1(T->rchild);
  146.         }
  147.     }
  148.     return i;
  149. }
  151. //每个叶子结点到根节点的路径
  152. void prepath(BiTree T,TElemType path[],int pathlen)//先序遍历方法输出每个叶子结点到根结点的路径序列 
  153. {   
  154.     if(T!=NULL)
  155.     {   if (T->lchild==NULL && T->rchild==NULL) //输出栈中所有叶子结点值
  156.         {   
  157.             printf("%c->",T->data);
  158.             for (int i=pathlen-1;i>0;i--)
  159.                 printf("%c->",path[i]);
  160.             printf("%c\n",path[0]);
  161.         }
  162.         else
  163.         {   path[pathlen++]=T->data;
  164.             prepath(T->lchild, path, pathlen);
  165.             prepath(T->rchild, path, pathlen);
  166.         }
  167.     }
  168. } 
  171. int main()
  172. {
  173.     BiTree T;   
  174.     int choose;
  175.     cout << "1. 建立二叉树\n";
  176.     cout << "2. 前序遍历\n";
  177.     cout << "3. 中序遍历\n";
  178.     cout << "4. 后序遍历\n";
  179.     cout << "5. 深度\n";
  180.     cout << "6. 结点个数\n";
  181.     cout << "7. 叶节点个数\n";
  182.     cout << "8. 度为1的结点个数\n";
  183.     cout << "9. 每个叶结点到根节点路径\n";
  184.     cout << "0. 退出\n\n";
  185.     choose = -1;
  187.     while (choose != 0) {
  188.         cout << "请选择:";
  189.         cin >> choose;
  190.         switch (choose) {
  191.             case 1://创建二叉树
  192.                 createbitree(T);
  193.                 cout<<"二叉树创建完成!"<<endl;
  194.                 break;
  195.             case 2://前序遍历
  196.                 cout<<"前序遍历结果: ";
  197.                 preordertraverse(T);
  198.                 cout<<endl;
  199.                 break;
  200.             case 3://中序遍历
  201.                 cout<<"中序遍历结果: ";
  202.                 inordertraverse(T);
  203.                 cout<<endl;
  204.                 break;
  205.             case 4://后序遍历
  206.                 cout<<"后序遍历结果: ";
  207.                 posordertraverse(T);
  208.                 cout<<endl;
  209.                 break;
  210.             case 5://深度
  211.                 cout<<"树的深度为: "<<depth(T)<<endl;
  212.                 break;
  213.             case 6://结点个数
  214.                 cout<<"树的结点个数为: "<<nodecount(T)<<endl;
  215.                 break;
  216.             case 7://叶子结点个数
  217.                 cout<<"叶子结点为: ";
  218.                 leaf(T);
  219.                 cout<<"叶子结点的个数为: "<<leafcount(T)<<endl;    
  220.                 break;
  221.             case 8://度为1的结点个数
  222.                 cout<<"度为1的结点个数为: "<<count1(T)<<endl;    
  223.                 break;
  224.             case 9://每个叶子结点到根节点的路径
  225.                 int path[3];
  226.                 printf("prepath:\n");
  227.                 prepath(T,path,0);
  228.                 break;
  230.         }
  231.     }
  232.     return 0;
  233. }

6.3哈夫曼树和哈夫曼编码
假设有image.png个权值image.png，n个叶子结点所构成的所有二叉树中，带权路径长度最小的二叉树称为哈夫曼树，树中所有叶子结点的带权路径长度之和记为image.png。
设需要编码的字符集为｛a1,a2,a3,…,an｝，各个字符出现的频率为image.png，以字符出现的频率作为结点字符的权值来构造霍夫曼树。规定左权分支为0，右权分支为1，则从根结点到叶子结点经过的分支所组成的0和1串便是对应字符的编码，称为霍夫曼编码。

image.png

七、图

7.1图的存储结构
7.1.1邻接矩阵：用一个nn的矩阵来表示一张图，矩阵的横纵坐标均表示图的点，若矩阵第i行第j列数字为n，在无向图中表示点i与点j之间则有n条连线，若矩阵第i行第j列数字为m，在有向图中表示在图中有m条由i指向j的边。
7.1.2邻接表：用链表的形式来表示图，若表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
7.2图的遍历
7.2.1深度优先搜索：
（1）从图中某个顶点v0出发并访问v0;
（2）访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤。直到图中所有与v0相通的所有节点都被访问到；
（3）若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复深度优先搜索过程，直到图中的所有节点均被访问过。
image.png
7.2.2广度优先搜索
（1）从图中某个顶点v0出发并访问v0;
（2）依次访问v0的各个未被访问的邻接点；
（3）依次从上述邻接点出发，访问它们的各个未被访问的邻接点；
（4）若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点 作为起始点。重复广度优先搜索过程，直到图中的所有节点均被访问过。
image.png
*7.3最小生成树
从图中的一个起点v1开始，把v1加入集合U，然后寻找从与v1有关联的边，权重最小的那条边并且该边的终点v3在顶点集合V中，再把v3加入到集合U中，并且输出边（v1，v3）的信息，这样我们的集合U为{v1,v3}。然后寻找与v1关联和v3关联的边中，权重最小的那条边并且该边的终点在集合V中，我们把v6加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U为{v1,v3,v6}这三个元素了，依次类推直到所有顶点都加入到了集合U。
从而得到最小生成树。
image.png

八、查找

8.1平均查找长度image.png
即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数成为平均查找长度。其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。一个算法的ASL越大，说明时间性能差，反之时间性能好。
image.png

8.2线性表的查找
顺序查找：查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。
折半查找：以有序表的中间记录作为比较对象，并以中间记录将表分割为两个子表，对子表继续上述操作。所以对表中每个记录的查找过程，可用二叉树来描述。二叉树中的每个结点对应有序表中的一个记录，结点中的值为该记录在表中的位置，这样的二叉树为折半查找判定树。判定树每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值。
image.png

8.3树表的查找
二叉排序树：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；若右子树不空，则右子树上所有节点的值均大于它的根节点的值；左、右子树也分别为二叉排序树。
二叉排序树构造过程如下图所示：
image.png

平衡二叉树：平衡二叉树，它是一棵空树，或者是具有以下性质：它的左右两个子树的深度差的绝对值不超过1；它的左右两个子树也分别是平衡二叉树。二叉树节点的左子树的深度减去它的右子树的深度称为平衡因子，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1，如下图所示：
image.png