devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

基础数据结构与算法总结1（附有完整代码，适合小白）_基本的数据结构与算法

作者：你好赵伟 | 2024-04-27 11:02:34

赞

踩

基本的数据结构与算法

前言

以下算法和数据结构代码都可以在本人的GitHub仓库中找到，欢迎大家来下载，可以的话，请给博主的GitHub来一个star，GitHub链接如下https://github.com/hifuda/algorithm-and-data-structure，但是我还是把完整的代码也放在了我的本篇博客上，为了照顾不玩GitHub的朋友。本篇博客是跟着b站视频来学习的，链接如下数据结构与算法特训班365天_哔哩哔哩_bilibili，由于篇幅有限，我打算分篇更新。感谢大家的观看，求个赞！

1，算法复杂度分析与计算

1，时间复杂度：算法运行所需要的时间，一般将算法执行的次数作为时间复杂度是我度量标准。

实例如下：

其中我们注意到为什么for循环执行n+1次呢？明明是1~n，为什么不是执行n次呢？因为，在最后一次，for循环要判断这个条件已经不符合循环了，所以说要加上这一次，同理下面的for循环也是这样！

注：f(n)取T(n)中幂最高的项，且去掉系数。这里的f(n)=n^2

我们通常使用时间复杂度的渐近上界来描述一个算法的时间复杂度。

T(n) = 1+2x。

注意寻找对算法时间复杂度贡献最大的代码块。

上面的算法，我们无法知道x在数组中的那个位置，所以我们要分最好和最坏两种情况来讨论：最好的情况就是x就是数组a的第一个元素，那么直接一次找到，（最坏的情况）如果是最后一个，那么要找n次，像这种分布概率均等的算法，计算其平均执行次数，算的n*（n+1）/2=（n+1）/2

2,空间复杂度

只要算法的空间复杂度是常数那么统统都是O(1)。

递归算法的空间复杂度：

实例如下：

int fac(int n){ if(n < 0){ cout << "小于零的数没有阶乘" << endl; return -1; } else if(n == 0 || n == 1){ return 1; } else{ return n*fac(n-1); } }

递归包括递推和回归。递推就是将原问题不断地分解成子问题直到达到结束条件，返回子问题的解，然后逐一回归，最终到达递推开始的原问题，然后返回原问题的解。

出栈：

进栈：

递归算法的时间复杂度如下：

3，常见的时间复杂度：

实例：神奇的兔子序列

解法一：递归算法

long long fib1(int n){//第50项时，耗费时间为 82939 if(n < 1){ return -1; } else if(n == 1 || n == 2){ return 1; } else{ return fib1(n - 1) + fib1(n - 2); } }

缺点：重复的动作太多，导致时间过久

递归树如下：

我们可以看到，f(4)算了两次，f(3)算了3次，依次类推，所以说斐波那契数列用递归来解答的话太浪费了。

空间复杂度：O(n)

解法二：动态规划

long double fib2(int n){//第50项时，耗费时间为 1 long double temp; if(n < 1){ return -1; } long double *a = new long double[n+1]; a[1] = a[2] = 1; for(int i = 3;i <= n; i++){ a[i] = a[i-1]+a[i-2]; } temp = a[n]; delete []a; //动态数组创建之后记得删除 return temp; }

我们可以改进算法如上，我们使用数组来记录当前项的前两项。

这样的话，时间复杂度O(n),空间复杂度就是O(n).

解法三：采集法

//迭代法 long double fib3(int n){ long double i,s1,s2; if(n < 0){ return -1; } if(n == 1 || n == 2){ return 1; } s1 = 1; s2 = 2; for(i = 3; i <=n;i++){ s2 = s1+s2; s1 = s2-s1; } return s2; }

这样的话我们的空间复杂度就是O(1),时间复杂度O(n).

2，线性数据结构

线性表简介：

线性表又分为顺序表和链表：

顺序表：

2.1，链表：

链表模型：

1，头节点一般不存放数据。

2，头节点之后的第一个节点，叫做首元节点

链表的几种基本操作：

1，初始化：

2，创建

头插法：每次创建的节点都在头节点的后面。

尾插法：每次都在链表的最后一个元素后面插入。

3，查询

4，删除

注意：改变p->next的在地址信息之后，记得使用delete 删除q节点。

双向列表的新增：

注意：要先去连上没有指针标记的节点给。

双向链表的删除：

2.2，链表完整代码与算法分析

1，首先定义一种结构体，作为节点类型

代码如下：

  1. //创建结构体
  2. typedef struct LNode{
  3.     int data;//节点中存入的数据
  4.     struct LNode *next;//定义指向下一个节点的指针 
  5. }LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

1，节点中的data还可以按照自己的需求定义成想要的类型。

2，使用typedef struct LNode将结构体取别名为LNode。

3，LinkList为指向结构体LNode的指针类型。

4，注意在定义结构体的时候要写struct LNode *next，而不可以写LNode *next，因为typedef struct LNode还没有执行完。

2，初始化节点

代码如下：

  1. bool InitList_L(LinkList &L){//创建一个空的单链表 
  2.     L = new LNode;
  3.     if(!L){//生成节点失败 
  4.         return false;
  5.     } 
  6.     L->next = NULL;//头节点指针域置为空 
  7.     return true;
  8. }

1，注意这里的形参列表传入的是引用，而不是简单的指针L，这样是为了在main方法中创建的头指针L做关联。

2，如果在执行过L = new LNode之后，L == NULL则生成节点失败。

3，创建节点

3.1，头插法实现

代码如下：

  1. //创建节点 ，头插法实现
  2. void CreateList_H(LinkList &L){
  3.      int n;//输入n个元素的值
  4.     LinkList s;//定义一个指针变量
  5.     L = new LNode;
  6.     L->next=NULL;//置空
  7.     cout <<"请输入元素个数n: " << endl;
  8.     cin >> n;
  9.     cout << "请依次输入n个元素：" << endl;
  10.     while(n--){
  11.         s = new LNode;//生成新节点 
  12.         cin >> s->data;
  13.         s->next = L->next;//首先将头节点后面的节点和新增的节点相连 
  14.         L->next = s;//然后，再将头节点和新建的节点相连，相连后断 
  15.         
  16.     } 
  17. }

1，这里的形参列表传入的是引用，而不是简单的指针L，理由同上。

2，在使用头插法的时候，我们只需要创建一个新的指针来保存节点地址，因为我们是直接插入在被指针标记的头节点后面。——LinkList s;//定义一个指针变量。

3，一定要注意这段代码s->next = L->next;好好理解，可能一开始添加第一个节点的时候会迷惑，因为这个时候L->next == NULL，但是如果添加第三个第四个呢？这时这句话的作用就一目了然了。

4，一定要记住先连上未被指针标记的，然后再连上被指针标记的。

3.2，尾插法实现

代码如下：

  1. //创建节点，尾插法实现 
  2. void CreateList_L(LinkList &L){
  3.     //输入n个元素的值，建立带头结点的单链表
  4.     int n;
  5.     LinkList s,r;//这里要创建两个指针 
  6.     L = new LNode;
  7.     L->next = NULL;
  8.     r = L;
  9.     cout << "请输入元素个数n: " <<endl; 
  10.     cin >> n;
  11.     cout << "请依次输入n个元素：" << endl;
  12.     cout <<"尾插法创建单链表：" << endl;
  13.     while(n--){
  14.         s = new LNode;//创建新的节点
  15.         cin >> s->data;
  16.         s->next = NULL;
  17.         r->next = s;//将新节点插入尾节点r后面 
  18.         r = s;//更新尾指针     
  19.     } 
  20. }

1，尾插法需要创建两个新的指针，由于是不断地从最后面的位置插入，所以需要尾指针的帮助，来标记最后一个元素的位置。

2，节点不断的增加，尾指针也需要不断的更新。

3.3，尾插法和头插法的运行时的区别：

尾插法创建链表如下：我们可以看到，我们输入的1，2，3，4，5。被顺序输出

头插法运行如下：我们可以看到，我们输入的1，2，3，4，5。被逆序输出

4，查找节点

4.1，顺序查找

代码如下：

  1. //单链表的顺序查找
  2. bool GetElem_L(LinkList L,int i,int &e){
  3.     //在带头结点的单链表L中查找第i个元素
  4.     //用e记录L中第i个元素的值
  5.     int j;
  6.     LinkList p;
  7.     p = L->next;
  8.     j = 1; //计数器
  9.     while(j < i && p){//当p指向NULL，或者j<i时退出循环 
  10.         p = p->next;//p指向下一个节点 
  11.         j++;//计数器加一 
  12.     } 
  13.     if(!p || j > i){
  14.         //j > i是为了以防特殊数据，比如说i=-1 
  15.         return false;
  16.     }
  17.     e = p->data;
  18.     return true;
  19. }

1，形参列表使用引用，理由同上。

2，注意遍历链表的时候不可以对指针进行++或者--操作，C可以，但是C++不行，所以这里创建了一个计数器来辅助遍历。

3，注意if和while语句的条件。

4.2，按值查找

代码如下：

  1. //按值查找 
  2. bool LocateElem_L(LinkList L,int e){
  3.     //注意头节点的指针不可以移动
  4.     LinkList p;
  5.     p = L->next;
  6.     while(p && p->data!=e){//p不指向NULL或者值不相等 
  7.         p = p->next;
  8.     } 
  9.     if(!p){//如果遍历完都没找到，那么p指针肯定为空 
  10.         return false;
  11.     } 
  12.     return true;
  13. }

1，注意头节点的指针不可以移动

5，插入节点

代码如下：

  1. //插入节点 
  2. bool ListInsert_L(LinkList &L,int i,int e){
  3.     int j;
  4.     LinkList p,s;
  5.     p = L;
  6.     j = 0;
  7.     while(p && j < i-1){//把指针移动到被插入节点的前一个节点
  8.     p = p->next;//移动指针 
  9.     j++;//计数器加一 
  10.     } 
  11.     if(!p && j > i-1){
  12.     //p为空，看是否遍历到最后
  13.     // j > i-1 同上是为了以防特殊数据 
  14.         return false;
  15.     } 
  16.     s = new LNode;
  17.     s->data = e;
  18.     s->next = p->next;//先连接未被标记的节点 
  19.     p->next = s;//然后再连上被标记的节点
  20.     return true;      
  21. }

1，注意再插入结点的时候，也创建了两个指针，一个用来标记标记被插入节点的前一个节点i-1，另一个用来保存要插入的节点。

2，注意while和if语句中的条件。

6，删除节点

代码如下：

  1. //单链表的删除
  2. bool ListDelete_L(LinkList &L,int i){
  3.     //删除第i个位置的元素
  4.     LinkList q,p;
  5.     int j;
  6.     p = L;
  7.     //j从0开始计数是为了可以让头节点后面的节点也可以删除
  8.     j = 0;
  9.     while((p->next) && (j<i-1)){
  10.         //最多遍历到最后一个节点，p->next=NULL 
  11.         p = p->next;
  12.         j++;
  13.     }
  14.     if(!(p->next) || (j>i-1)){
  15.         return false;
  16.     }
  17.     q = p->next;//让q指向p后面的节点 
  18.     p->next = q->next;//再让p->next指向q后面的节点 
  19.     delete q;//删除指针 
  20.     return true;    
  21. }

1，首先这里创建了两指针q和p，分别用于指向被删除的i节点和i-1节点。

2，将p遍历到i-1的位置，然后q = p->next;//让q指向p后面的节点 。

3，p->next = q->next;//再让p->next指向q后面的节点 。

4，最后记得删除指针。

7，输出链表

代码如下：

  1. //输出单链表 
  2. void Listprint_L(LinkList L){
  3.     LinkList p;
  4.     p = L->next;
  5.     while(p){//此处的判断条件要注意，不要写p->next 
  6.         cout << p->data << "\t";
  7.         p = p->next;
  8.     } 
  9.     cout <<endl;
  10. }

就是在p!=NULL的时候不断地执行p = p->next，将p指针遍历到后面去。

8，完整的代码如下

  1. #include<iostream>
  2. #include<string>
  3. //在iomanip库中，比较常用的有关于进制的转换，小数点的保留，以及域宽等的使用。
  4. #include<iomanip>
  5. //包含了c语言中的一些常用的库函数 
  6. #include<stdlib.h>
  7. using namespace std;
  8.  
  9. //创建结构体
  10. typedef struct LNode{
  11.     int data;//节点中存入的数据
  12.     struct LNode *next;//定义指向下一个节点的指针 
  13. }LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
  14.  
  15. bool InitList_L(LinkList &L){//创建一个空的单链表 
  16.     L = new LNode;
  17.     if(!L){//生成节点失败 
  18.         return false;
  19.     } 
  20.     L->next = NULL;//头节点指针域置为空 
  21.     return true;
  22. } 
  23.  
  24. //创建节点 ，头插法实现
  25. void CreateList_H(LinkList &L){
  26.     int n;//输入n个元素的值
  27.     LinkList s;//定义一个指针变量
  28.     L = new LNode;
  29.     L->next=NULL;
  30.     cout <<"请输入元素个数n: " << endl;
  31.     cin >> n;
  32.     cout << "请依次输入n个元素：" << endl;
  33.     while(n--){
  34.         s = new LNode;//生成新节点 
  35.         cin >> s->data;
  36.         s->next = L->next;//首先将头节点后面的节点和新增的节点相连 
  37.         L->next = s;//然后，再将头节点和新建的节点相连，相连后断 
  38.         
  39.     } 
  40. } 
  41. //创建节点，尾插法实现 
  42. void CreateList_L(LinkList &L){
  43.     //输入n个元素的值，建立带头结点的单链表
  44.     int n;
  45.     LinkList s,r;//这里要创建两个指针 
  46.     L = new LNode;
  47.     L->next = NULL;
  48.     r = L;
  49.     cout << "请输入元素个数n: " <<endl; 
  50.     cin >> n;
  51.     cout << "请依次输入n个元素：" << endl;
  52.     cout <<"尾插法创建单链表：" << endl;
  53.     while(n--){
  54.         s = new LNode;//创建新的节点
  55.         cin >> s->data;
  56.         s->next = NULL;
  57.         r->next = s;//将新节点插入尾节点r后面 
  58.         r = s;//更新尾指针     
  59.     } 
  60. }
  61.  
  62. //单链表的顺序查找
  63. bool GetElem_L(LinkList L,int i,int &e){
  64.     //在带头结点的单链表L中查找第i个元素
  65.     //用e记录L中第i个元素的值
  66.     int j;
  67.     LinkList p;
  68.     p = L->next;
  69.     j = 1; //计数器
  70.     while(j < i && p){//当p指向NULL，或者j<i时退出循环 
  71.         p = p->next;//p指向下一个节点 
  72.         j++;//计数器加一 
  73.     } 
  74.     if(!p || j > i){
  75.         //j > i是为了以防特殊数据，比如说i=-1 
  76.         return false;
  77.     }
  78.     e = p->data;
  79.     return true;
  80. } 
  81. //按值查找 
  82. bool LocateElem_L(LinkList L,int e){
  83.     //注意头节点的指针不可以移动
  84.     LinkList p;
  85.     p = L->next;
  86.     while(p && p->data!=e){//p不指向NULL或者值不相等 
  87.         p = p->next;
  88.     } 
  89.     if(!p){//如果遍历完都没找到，那么p指针肯定为空 
  90.         return false;
  91.     } 
  92.     return true;
  93. } 
  94. //插入节点 
  95. bool ListInsert_L(LinkList &L,int i,int e){
  96.     int j;
  97.     LinkList p,s;
  98.     p = L;
  99.     j = 0;
  100.     while(p && j < i-1){//把指针移动到被插入节点的前一个节点
  101.     p = p->next;//移动指针 
  102.     j++;//计数器加一 
  103.     } 
  104.     if(!p && j > i-1){
  105.     //p为空，看是否遍历到最后
  106.     // j > i-1 同上是为了以防特殊数据 
  107.         return false;
  108.     } 
  109.     s = new LNode;
  110.     s->data = e;
  111.     s->next = p->next;//先连接未被标记的节点 
  112.     p->next = s;//然后再连上被标记的节点
  113.     return true;      
  114. } 
  115. //单链表的删除
  116. bool ListDelete_L(LinkList &L,int i){
  117.     //删除第i个位置的元素
  118.     LinkList q,p;
  119.     int j;
  120.     p = L;
  121.     //j从0开始计数是为了可以让节点可以插入头节点的后面 
  122.     j = 0;
  123.     while((p->next) && (j<i-1)){
  124.         //最多遍历到最后一个节点，p->next=NULL 
  125.         p = p->next;
  126.         j++;
  127.     }
  128.     if(!(p->next) || (j>i-1)){
  129.         return false;
  130.     }
  131.     q = p->next;//让q指向p后面的节点 
  132.     p->next = q->next;//再让p->next指向q后面的节点 
  133.     delete q;//删除指针 
  134.     return true;    
  135. }
  136. //输出单链表 
  137. void Listprint_L(LinkList L){
  138.     LinkList p;
  139.     p = L->next;
  140.     while(p){//此处的判断条件要注意，不要写p->next 
  141.         cout << p->data << "\t";
  142.         p = p->next;
  143.     } 
  144.     cout <<endl;
  145. } 
  146.  
  147. int main()
  148. {
  149.     int i,x,e,choose;
  150.     LinkList L;
  151.     cout << "1. 初始化\n";
  152.     cout << "2. 创建单链表（前插法）\n";
  153.     cout << "3. 创建单链表（尾插法）\n";
  154.     cout << "4. 取值\n";
  155.     cout << "5. 查找\n";
  156.     cout << "6. 插入\n";
  157.     cout << "7. 删除\n";
  158.     cout << "8. 输出\n";
  159.     cout << "0. 退出\n";
  160.     choose=-1;
  161.     while (choose!=0)
  162.     {
  163.         cout<<"请输入数字选择:";
  164.         cin>>choose;
  165.         switch (choose)
  166.         {
  167.         case 1: //初始化一个空的单链表
  168.             if (InitList_L(L))
  169.                 cout << "初始化一个空的单链表!\n";
  170.             break;
  171.         case 2: //创建单链表（前插法）
  172.             CreateList_H(L);
  173.             cout << "前插法创建单链表输出结果:\n";
  174.             Listprint_L(L);
  175.             break;
  176.         case 3: //创建单链表（尾插法）
  177.             CreateList_L(L);
  178.             cout << "尾插法创建单链表输出结果:\n";
  179.             Listprint_L(L);
  180.             break;
  181.         case 4: //单链表的按序号取值
  182.             cout << "请输入一个位置i用来取值:";
  183.             cin >> i;
  184.             if (GetElem_L(L,i,e))
  185.             {
  186.                 cout << "查找成功\n";
  187.                 cout << "第" << i << "个元素是："<<e<< endl;
  188.             }
  189.             else
  190.                 cout << "查找失败\n\n";
  191.             break;
  192.         case 5: //单链表的按值查找
  193.             cout<<"请输入所要查找元素x:";
  194.             cin>>x;
  195.             if (LocateElem_L(L,x))
  196.                 cout << "查找成功\n";
  197.             else
  198.                 cout << "查找失败! " <<endl;
  199.             break;
  200.         case 6: //单链表的插入
  201.             cout << "请输入插入的位置和元素（用空格隔开）:";
  202.             cin >> i;
  203.             cin >> x;
  204.             if (ListInsert_L(L, i, x))
  205.                 cout << "插入成功.\n\n";
  206.             else
  207.                 cout << "插入失败!\n\n";
  208.             break;
  209.         case 7: //单链表的删除
  210.             cout<<"请输入所要删除的元素位置i:";
  211.             cin>>i;
  212.             if (ListDelete_L(L, i))
  213.                 cout<<"删除成功!\n";
  214.             else
  215.                 cout<<"删除失败!\n";
  216.             break;
  217.         case 8: //单链表的输出
  218.             cout << "当前单链表的数据元素分别为:\n";
  219.             Listprint_L(L);
  220.             cout << endl;
  221.             break;
  222.         }
  223.     }
  224.     return 0;
  225. }

9，应用题一

步骤如下：

1，首先创建三个指针，p和q用于比较，r用来指向最后一个节点。

2，最开始的时候，r指向头节点，q，p分别指向两个不同的链表的第一个元素节点。

3，比较p和q的数据域的大小，2next = q。

4，然后更新辅助指针r = q，并且q指针移动到下一个数q = q->next。

5，然后再比较6和4，由于6>4,所以r->next = p。

6，然后更新辅助指针r = p，并且p指针移动到下一个数p = p->next。

完整代码如下：

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4.  
  5. typedef struct LNode{
  6.     int data;
  7.     struct LNode *next;
  8. }LNode,*LinkList;
  9.  
  10. //创建数组尾插法创建 
  11. bool CreateList(LinkList &L){
  12.     int n,j;//
  13.     LinkList p,q;//p不断指向最后一个节点，q保存新的节点
  14.     L = new LNode;
  15.     if(!L){
  16.         cout << "创建失败" << endl;
  17.         return false;
  18.     }
  19.     L->next = NULL;
  20.     p = L;
  21.     cout << "请输入要放入的元素个数n:" << endl;
  22.     cin >> n;
  23.     cout << "请输入要放入的元素值data(数据之间用空格分割):";
  24.     for (j = 0; j < n;j++){
  25.         q = new LNode;//创建新的节点 
  26.         q->next = NULL;
  27.         cin >> q->data;
  28.         p->next = q;//p->next 指向新节点 
  29.         p = p->next;//p向后移 
  30.     } 
  31.     return true;
  32. } 
  33. //合并数组
  34. void MergeList(LinkList La,LinkList Lb,LinkList &Lc){
  35.     LinkList r,p,q;//创建三个指针
  36.     r = La;
  37.     Lc = r;
  38.     p = La->next;
  39.     q = Lb->next;
  40.     while(p&&q){
  41.         if(p->data > q->data){
  42.             r->next = q;
  43.             r = r->next;
  44.             q = q->next;
  45.         }else{
  46.             r->next = p;
  47.             r = r->next;
  48.             p = p->next;
  49.         }    
  50.     }
  51.     r->next=p?p:q;//相当于if(p) r->next=p; else r->next=q;
  52.     delete Lb;
  53. }
  54. //输出数组 
  55. void PrintList(LinkList L){
  56.     LinkList s;
  57.     s = L->next; //直接指向头指针的后一个节点 
  58.     cout << "链表输出如下：" << endl; 
  59.     while(s){
  60.         cout << s->data << "\t"; 
  61.         s = s->next; 
  62.     }
  63.     cout << endl;
  64. }
  65.  
  66. int main(){
  67.     LinkList La,Lb,Lc;
  68.     cout << "创建链表La" << endl;
  69.     CreateList(La);
  70.     PrintList(La);
  71.     cout << "创建链表Lb" << endl;
  72.     CreateList(Lb);
  73.     PrintList(Lb);
  74.     cout << "合并链表后：" << endl; 
  75.     MergeList(La,Lb,Lc);
  76.     PrintList(Lc);
  77.     return 0;
  78. }

运行示例如下：

9，应用题二

步骤如下：

当节点数是偶数的时候，那么中间节点就是3。

当节点数是奇数时，如下，快指针在到达6的时候，慢指针到达3，这时快指针到达7后面的节点后（这时快指针等于空NULL），慢指针到达4，中间节点就是4。

完整代码如下：

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4.  
  5. typedef struct LNode{
  6.     int data;
  7.     struct LNode *next;
  8. }LNode,*LinkList;
  9.  
  10. //创建数组尾插法创建 
  11. bool CreateList(LinkList &L){
  12.     int n,j;//
  13.     LinkList p,q;//p不断指向最后一个节点，q保存新的节点
  14.     L = new LNode;
  15.     if(!L){
  16.         cout << "创建失败" << endl;
  17.         return false;
  18.     }
  19.     L->next = NULL;
  20.     p = L;
  21.     cout << "请输入要放入的元素个数n:" << endl;
  22.     cin >> n;
  23.     cout << "请输入要放入的元素值data(数据之间用空格分割):";
  24.     for (j = 0; j < n;j++){
  25.         q = new LNode;//创建新的节点 
  26.         q->next = NULL;
  27.         cin >> q->data;
  28.         p->next = q;//p->next 指向新节点 
  29.         p = p->next;//p向后移 
  30.     } 
  31.     return true;
  32. } 
  33.  
  34. //输出数组 
  35. void PrintList(LinkList L){
  36.     LinkList s;
  37.     s = L->next; //直接指向头指针的后一个节点 
  38.     cout << "链表输出如下：" << endl; 
  39.     while(s){
  40.         cout << s->data << "\t"; 
  41.         s = s->next; 
  42.     }
  43.     cout << endl;
  44. }
  45. //找寻中间节点 
  46. LinkList findmiddle(LinkList L)
  47. {
  48.     LinkList p,q;
  49.     p=L; //p为快指针，初始时指向L
  50.     q=L; //q为慢指针，初始时指向L
  51.     while(p!=NULL&&p->next!=NULL)//注意这里的条件，要仔细思考为什么这么写 
  52.     {
  53.         p=p->next->next;//p为快指针一次走两步；
  54.         q=q->next; //q为慢指针一次走一步
  55.     }
  56.     return q;//返回中间结点指针
  57. }
  58.  
  59. int main(){
  60.     LinkList L,s;
  61.     cout << "创建链表L" << endl;
  62.     CreateList(L);
  63.     PrintList(L);
  64.     s = findmiddle(L);
  65.     cout << "中间节点为：" << s->data;
  66. }

运行实例图：

10，课后练习

练习一

1，对于第一题，我的想法是，使用两个辅助指针去q和p，一开始两个辅助指针都指向第一个元素节点，其中一个指针q不断地向后遍历，并且使用一个变量n记录链表的长度，当q遍历到最后的时候，链表长度也就记录在n中了。

2，然后再计算出元素在顺序中的位置，在用另一个指针去得到这个元素节点。

完整代码如下

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4.  
  5. typedef struct LNode{
  6.     int data;
  7.     struct LNode *next;
  8. }LNode, *LinkList;
  9.  
  10. //创建链表（头插法） 
  11. bool CreateList(LinkList &L){
  12.     LinkList p;
  13.     int n,j;
  14.     L = new LNode;
  15.     if(!L){
  16.         return false;
  17.     }
  18.     L->next = NULL;
  19.     cout << "请输入要创建的节点个数n：" << endl;
  20.     cin >> n;
  21.     cout << "请输入元素值data（值之间用空格分割）：" ; 
  22.     for(j = 0;j < n;j++){
  23.         p = new LNode;
  24.         p->next = NULL;
  25.         cin >> p->data; 
  26.         p->next = L->next;//首先让新增节点连上头节点后面的节点 
  27.         L->next = p;//然后头节点再连上新节点 
  28.     }
  29.     return true; 
  30. }
  31. //打印链表 
  32. void PrintList(LinkList L){
  33.     LinkList s;
  34.     s = L->next; //直接指向头指针的后一个节点 
  35.     cout << "链表输出如下：" << endl; 
  36.     while(s){
  37.         cout << s->data << "\t"; 
  38.         s = s->next; 
  39.     }
  40.     cout << endl;
  41. }

练习二

步骤如下：

首先，创建三个指针r，p，q，还有一个数组a[ ];我考虑使用一个数组来存储节点元素出现的次数，p指针用于遍历整个链表，然后得到各个节点的元素的绝对值出现的次数；然后，r指向头指针，q指向第一个元素节点，r指针永远再q指针的前一位，用于连接要删除的元素的后一位元素，而q则标记要删除的元素节点。而这里的判断条件就是看a[ ]数组中对应的元素的出现次数是否大于1，如果成立，则删除此节点，且保存在数组中的次数减一，如果不成立，则r和q指针都向前移动一位。

完整代码如下：

  1. #include<iostream>
  2. #include<string>
  3. #include<cmath> //需要使用他的绝对值函数abs()，所以引入 
  4. using namespace std;
  5.  
  6. typedef struct LNode{
  7.     int data;
  8.     struct LNode *next;
  9. }LNode, *LinkList;
  10.  
  11. //创建链表（头插法） 
  12. bool CreateList(LinkList &L){
  13.     LinkList p;
  14.     int n,j;
  15.     L = new LNode;
  16.     if(!L){
  17.         return false;
  18.     }
  19.     L->next = NULL;
  20.     cout << "请输入要创建的节点个数n：" << endl;
  21.     cin >> n;
  22.     cout << "请输入元素值data（值之间用空格分割）：" ; 
  23.     for(j = 0;j < n;j++){
  24.         p = new LNode;
  25.         p->next = NULL;
  26.         cin >> p->data; 
  27.         p->next = L->next;//首先让新增节点连上头节点后面的节点 
  28.         L->next = p;//然后头节点再连上新节点 
  29.     }
  30.     return true; 
  31. }
  32. //打印链表 
  33. void PrintList(LinkList L){
  34.     LinkList s;
  35.     s = L->next; //直接指向头指针的后一个节点 
  36.     cout << "链表输出如下：" << endl; 
  37.     while(s){
  38.         cout << s->data << "\t"; 
  39.         s = s->next; 
  40.     }
  41.     cout << endl;
  42. }
  43.  
  44. bool AbandonTwo(LinkList &L){
  45.     int a[1024] = {0};//用于存储链表中的数据对应的出现的次数 
  46.     LinkList p,q,r;//p用于遍历链表中的数据 
  47.     if(L->next){//判断该链表是不是一个空链表，如果不是让p和q指向第一个元素节点 
  48.         p = L->next;
  49.         q = L->next;
  50.         r = L;
  51.     }else{
  52.         return false;
  53.     }
  54.     while(p){
  55.         a[abs(p->data)]++;//0-1,1-2,3---
  56.         p = p->next; 
  57.     }
  58. //    cout << "输出数组" <<endl; 
  59. //    cout << "输出数组:" << sizeof(a)/sizeof(int) <<endl; 获取数组长度 
  60. //    for(int i = 0;i < sizeof(a)/sizeof(int);i++){
  61. //        cout << a[i] << "\t";
  62. //    }
  63.     while(q){
  64.         if(a[abs(q->data)] > 1){//如果该节点的数值的绝对值出现超过1次，就删除 
  65.             a[abs(q->data)]--; //元素出现次数减一 
  66.             r->next = q->next;
  67.             q = q->next;
  68.             //r = r->next; //注意这个时候不用更新r指针 
  69.         }else{//如果该节点数值的绝对值只有1次，那么直接移动指针到下一位 
  70.             r = q;
  71.             q = q->next;
  72.         }
  73.     } 
  74. //    cout << "输出数组2" <<endl; 
  75. //    cout << "输出数组:" << sizeof(a)/sizeof(int) <<endl; 获取数组长度 
  76. //    for(int i = 0;i < sizeof(a)/sizeof(int);i++){
  77. //        cout << a[i] << "\t";
  78. //    }
  79.     return true;     
  80. }
  81.  
  82. int main(){
  83.     LinkList L;
  84.     cout << "创建链表L:" <<endl;
  85.     if(CreateList(L)) {
  86.         cout << "创建链表成功" << endl;
  87.     }else{
  88.             cout << "创建链表失败" << endl;
  89.             return 0;
  90.     }
  91.     PrintList(L); 
  92.     if(AbandonTwo(L)) {
  93.         cout << "去除成功，去除后链表如下" <<endl;
  94.         PrintList(L); 
  95.     }else{
  96.         cout << "该链表是一个空链表" <<endl;
  97.     } 
  98.     return 0; 
  99.  
  100. }

空间复杂度分析：其实，可以看出，由于题目没有对算法的空间复杂度提出要求，那么我就可以申请无限的数组长度，而如上算法的空间复杂度是由链表中的最大数决定的。

时间复杂度分析：在这里我们只遍历了两次链表，所以时间复杂度为O(n).

补充：C++数组长度的获取方法

  1. length = sizeof(array)/sizeof(*array);            //表达式1
  2. //length = sizeof(array)/sizeof(array[0]);        //表达式2
  3. //length = sizeof(array)/sizeof(int);             //表达式3

上述三个表达式都能得到正确的结果，虽然表达式略有不同，但原理是相同的，即通过sizeof(array)获取整个数组所占的内存字节数，再通过sizeof(*array)或者sizeof(array[0])或者sizeof(int)来获取每个元素所占的字节数，数组所占的字节数除以每个元素所占的字节数就是该数组的元素个数了。

2.3，栈和队列

1，栈知识点简介

通常使用的是顺序存储，最好不要使用链式存储。

2，栈

2.1,栈的操作简介：

1，top指针在栈内有元素的情况下为空，出栈时top--，入栈时top++。

2，当top==base时，判断此栈为空。

2.2，栈结构体

1，动态分配

2，静态分配

最好使用const int Maxsize = ？来定义数组长度。

3，顺序栈的操作

3.1，栈的初始化

3.2，入栈

  1. S.top-S.base == Maxsize //栈满条件
  2. *(S.top++) = e; //元素e压入栈顶，然后栈顶指针加1，
  3. //上一行代码等价于*S.top=e; S.top++;
  4. //一开始top指针和base指针都指向栈底，而不是像图中分开

 

3.2，入栈

3.3，取栈顶

4，链栈

4.1，入栈

链栈只需要两个指针，一个用来指向栈顶，一个用来保存新的入栈元素。操作步骤如上。

4.2，出栈

4.3，取栈顶元素

5，队列

5.1，顺序队列

队列结构体动态分配：

队列结构体静态分配：

初始化：

入队：

为了方式”假溢出“，我们通常使用循环队列

注意图中的表达式。

队列空和队列满的表达式：

我们在这里浪费了一个空间，方便我们来标识队满。

入队：

出队：

队列中的元素个数计算：

加上Maxsize是为了防止负数，取余Maxsize是为了防止正数。

5.2，链队

2.4，栈完整代码和算法分析

顺序栈完整代码如下：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define Maxsize 100
  5.  
  6. typedef struct SqStack {
  7.     int *top;
  8.     int *base;
  9. }SqStack;
  10.  
  11. bool InitStack(SqStack &S){
  12.     S.base = new int[Maxsize];
  13.     if(!S.base){
  14.         return false;
  15.     }
  16.     S.top = S.base; //空栈条件
  17.     return true; 
  18. }
  19.  
  20. bool Push(SqStack &S,int e){
  21.     if((S.top - S.base) == Maxsize){//判断栈满 
  22.         return false;
  23.     }
  24.     *S.top = e;//只需要把值存入这个指针指向的内存地址就好 
  25.     S.top++;
  26.     return true;
  27. }
  28.  
  29. bool Pop(SqStack &S,int &e){
  30.     if (S.base == S.top){//栈空
  31.         return false;
  32.     } 
  33.     e = *(S.top - 1);    
  34.     S.top--; //栈顶指针减1，将栈顶元素赋给e
  35.     return true;
  36.     
  37. }
  38.  
  39. int GetTop(SqStack &S){
  40.     int z;
  41.     if(S.top != S.base){
  42.         z = *(S.top-1);//要记得先对栈顶指针减一，再取元素，因为栈顶指针一直为空（但是实际上不为空）,但是我们不需要移动栈顶指针 
  43.         return z;
  44.     }
  45. }
  46.  
  47. int main(){
  48.     int n,x;//n存储元素个数，x存储入栈元素 
  49.     SqStack S;
  50.     if(InitStack(S)){
  51.         cout << "初始化栈成功！" << endl;
  52.     } else{
  53.         cout << "初始化栈失败！" << endl;
  54.         return 0;
  55.     }
  56.     cout << "请输入入栈元素个数n：";
  57.     cin >> n;
  58.     cout << endl << "请输入入栈元素x(用空格分割)：";
  59.     while(n--){
  60.         cin >> x; 
  61.         if(Push(S,x)){
  62.         cout << "入栈成功！" << endl;
  63.         } else{
  64.         cout << "入栈失败！" << endl;
  65.         return 0;
  66.         }
  67.     }
  68.     cout << "元素依次出栈：" << endl;
  69.     while(S.top!=S.base)//如果栈不空，则依次出栈
  70.     {
  71.         /*
  72.         GetTop(S)：输出栈顶元素
  73.         Pop(S, x); 栈顶元素出栈，并且将元素指针下移一位 
  74.         */ 
  75.         cout<<GetTop(S)<<"\t";//输出栈顶元素
  76.         Pop(S, x);   //栈顶元素出栈
  77.     }
  78.     return 0;
  79. }

解读

和链栈不同，这里创建的顺序栈的结构体如下：

  1. typedef struct SqStack {
  2.     int *top;
  3.     int *base;
  4. }SqStack;

当我们初始化一个栈的时候，会让结构体中的top和base指针同时指向一个数组，如下：

  1. bool InitStack(SqStack &S){
  2.     S.base = new int[Maxsize];
  3.     if(!S.base){
  4.         return false;
  5.     }
  6.     S.top = S.base; //空栈条件
  7.     return true; 
  8. }

我们在对顺序栈出入栈的时候，top指针（栈顶指针）上下移动，这样便可以控制出入栈元素存入在数组中的位置。所以说我们的数据还是存储在我们新建的数组中。

运行示例：

链栈完整代码如下：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef struct SqStack {
  5.     int data;
  6.     struct SqStack *next;
  7. }SqStack, *LinkSqStack;
  8. //初始化栈
  9. bool InitSqStack(LinkSqStack &sq,int e) {
  10.     sq = new SqStack;
  11.     sq->data = e;
  12.     sq->next = NULL;
  13.     if(!sq){
  14.         return false;
  15.     }
  16.     return true;
  17. }
  18.  
  19. //入栈 
  20. void Push(LinkSqStack &sq,int x){
  21.     LinkSqStack p;
  22.     p = new SqStack;
  23.     p->data = x;
  24.     p->next = sq;
  25.     sq = p;
  26.     
  27. }
  28.  
  29. //出栈
  30. void Pop(LinkSqStack &sq) {
  31.     if(sq){
  32.         sq = sq->next;//sq指针移动到下一位 
  33.     }
  34. }
  35. //取栈顶元素,这个对于链栈来说sq指针就是栈顶元素，所以不用在调用了,这个方法如果写了，好鸡肋呀！哈哈哈
  36. //但是工作的时候增加代码量还是不错的哈哈哈 
  37. //LinkSqStack GetElem(LinkSqStack sq){
  38. //    if(sq){
  39. //        return sq;
  40. //    }
  41. //} 
  42.  
  43.  
  44. int main(){
  45.     LinkSqStack sq;//创建一个栈顶节点指针，注意这个栈顶结点也有data，不为空 
  46.     int n,x,e;//n存储入栈元素个数，x存储入栈元素,e用来初始化第一个元素
  47.     cout << "请输入初始化元素e:";
  48.     cin >> e;
  49.     if(!InitSqStack(sq,e)) {
  50.          cout << "初始化栈失败！";
  51.          return 0; 
  52.     }
  53.     cout << "请输入入栈元素个数n：";
  54.     cin >> n;
  55.     cout << "请输入入栈元素x（用空格分割）：";
  56.     while(n--){
  57.         cin >> x;
  58.         Push(sq,x);
  59.     } 
  60.     cout << "取栈顶元素" << endl;
  61.     while(sq){//当指针指向栈底元素时，该循环还会执行一次，然后sq就会为NULL
  62.         cout << sq->data << "\t";
  63.         Pop(sq);
  64.     }
  65.     return 0;
  66. }

解读

和顺序栈不同，链栈中的元素，都是存储在我们自己创建定义的结构体类型的节点中，其实和我们的链表类似，只不过操作的方式不一样。

  1. typedef struct SqStack {
  2.     int data;
  3.     struct SqStack *next;
  4. }SqStack, *LinkSqStack;

出入栈：

  1. //入栈 
  2. void Push(LinkSqStack &sq,int x){
  3.     LinkSqStack p;
  4.     p = new SqStack;
  5.     p->data = x;
  6.     p->next = sq;
  7.     sq = p;
  8.     
  9. }
  10.  
  11. //出栈
  12. void Pop(LinkSqStack &sq) {
  13.     if(sq){
  14.         sq = sq->next;//sq指针移动到下一位 
  15.     }
  16. }

运行示例：

2.5，队列的完整代码和算法分析

链队完整代码：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define Maxsize 10
  5.  
  6. typedef struct SqQueue {
  7.     int *base;//基指针，指向数组的头部 
  8.     int front,rear;//头指针和尾指针 
  9. }SqQueue;
  10.  
  11. bool InitQueue(SqQueue &S){
  12.     S.base = new int[Maxsize];//指向数组的头部 
  13.     if(!S.base){
  14.         return false;
  15.     }
  16.     S.front = 0;//头指针和尾指针队空时，全都指向 S.base[0] 
  17.     S.rear = 0;
  18.     return true;
  19. }
  20.  
  21. void EnQueue(SqQueue &S,int x){
  22.     if((S.rear+1)%Maxsize == S.front){
  23.         cout << "栈满，无法入栈" << endl;
  24.     }
  25.     S.base[S.rear]=x; //新元素插入队尾
  26.     S.rear = (S.rear+1)%Maxsize;//队尾指针加1
  27. }
  28.  
  29. int QueueLength(SqQueue S){
  30.     return (S.rear-S.front+Maxsize)%Maxsize;//计算队列元素的表达式 
  31. }
  32.  
  33. int GetHead(SqQueue S){
  34.     if (S.front!=S.rear) //队列非空
  35.         return S.base[S.front];
  36.     return -1;
  37. }
  38.  
  39. bool DeQueue(SqQueue &S, int &x) {//删除S的队头元素，用x返回其值
  40.     if(S.front == S.rear){//判断栈是否空 
  41.         return false; 
  42.     }
  43.     x = S.base[S.front];
  44.     S.front = (S.front + 1)%Maxsize;//头指针减一的表达式 
  45.     return true; 
  46. }
  47.  
  48. int main(){
  49.     SqQueue S;
  50.     int n,x;//n保存入队元素个数，c存储入队元素
  51.     if(!InitQueue(S)){
  52.         cout << "初始化错误" << endl;
  53.         return 0;
  54.     } 
  55.     cout << "请输入入队元素个数n:";
  56.     cin >> n;
  57.     cout << "请输入入队元素（用空格分割元素）x:";
  58.     while(n--){
  59.         cin >> x;
  60.         EnQueue(S,x);
  61.     }
  62.     cout <<"队列内元素个数，即长度："<<QueueLength(S)<<endl;
  63.     cout <<"队头元素：" <<GetHead(S)<<endl;
  64.     cout << "依次出队" << endl; 
  65.     while(true)//如果栈不空，则依次出栈
  66.     {
  67.         if(DeQueue(S,x))
  68.             cout<<x<<"\t";//出队元素
  69.         else
  70.             break;
  71.     }
  72.     cout <<endl;
  73.     cout <<"队列内元素个数，即长度："<<QueueLength(S)<<endl;
  74.     return 0;
  75. }

注意点：

1，入队时，要判断队是否已满，判断条件要理解并熟记

(S.rear+1)%Maxsize == S.front

2，入队后，队尾指针加一；S.rear = (S.rear+1)%Maxsize

3，出队时，判断队是否空，S.front!=S.rear

4，出队后，队头指针加一；S.front = (S.front + 1)%Maxsize;

5，计算队列元素个数；(S.rear-S.front+Maxsize)%Maxsize;

2.6，数组

知识点概述

数据存储：

使用sizeof（）函数来获得某种数据类型的所占字节

按行存储：

按列存储：

小试炼：

我一上来就算错了，还是踩坑了hhh，要牢记呀！

从一开始的计算方式：

计算这个元素前面有多少个元素，而不包含他本身。

课后作业：

2.7，压缩矩阵 

1，概述

0

1.1，对称矩阵

按行存储下三角矩阵：

k代表的是，元素在一维数组中存储的位置。

0

两种方法：

1，先包含这个元素构成一个完整的三角形，然后再减一去除这个元素。

2，先算第i+1行上面的元素所构成的三角形，然后再当前i+1行剩余的元素

0

0

注意：要是本来是个下三角矩阵，而他给的元素i

0

1.2，三角矩阵

0

压缩前存储元素个数：n^2

压缩后存储元素个数：n(n+1) /2

上三角存储元素：

i-1 = n -(n-i+2)+1；

小试炼

注意：这题是从1开始存储的，与0开始寻出的不同

1.3，对角矩阵

存储对角矩阵：

注意：只可以去除最上面和最下面两行的0

总结：千万注意，数组的存储是从0开始还是一开始

小试炼：

3，BF算法和KMP算法 

1，字符串

1.1，使用size()和length()函数，可以返回当前调用元素的字符串的字符个数。

1.2 ，假如你使用cin来接收的字符串中含有空格，则输入程序会终止，我们可以使用getline(cin,s)【s表示要输入的字符串】函数来读入字符串。

2，字符串的存储

2.1，字符串顺序存储

存在溢出的风险。

2.2，字符串链式存储（很少用）

字符串使用普通的链式存储的的话，每一个节点只存储一个字符串，虽然插入删除方便，但是会浪费大量的空间，其实也不是浪费，存储的效率太低了。

如果采取块链存储的话（如上，三个元素一组），除非你对字符串的添加和删除操作很少，或者基本没有，否则添加和删除操作会导致大量的元素移动。

3，模式匹配

3.1，BF算法思想

3.2，BF算法复杂度

最好的情况时间复杂度为O(n+m)。

最好的情况时间复杂度为O(n*m)。

4，KMP算法

特点：i不回退，j的回退位置

j的回退位置：

没有相等的公共前后缀的时候，还是从子串的第一个位置开始比较。使用next[]数组来存储l+1，就是公共前后缀所包含的字符个数加一，也就是j要回退的位置。

4.1，疑问

我们可以通过j来推出j+1.

求next[]数组

主程序

3.1，BF算法完整代码和算法分析 

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4.  
  5. int BF(string s,string t,int op){
  6.  int i=op,j=1,sum=0;//sum用来保存比较次数
  7.     int slen = s.size(); 
  8.     int tlen = t.length();
  9.     cout << slen << endl << tlen << endl;
  10.     while(i <= slen && j <= tlen){
  11.         sum++;
  12.         //cout << "s[i-1]：" << s[i-1] << endl; 
  13.         if(s[i-1] == t[j-1]){//如果字符相等，则指针都加1 
  14.             i++;
  15.             j++;
  16.         }else{//如果字符不相等，则返回上一轮比较的节点的下一个节点 
  17.             i = i-j+2;//公式 
  18.             j = 1;
  19.         }
  20.     }
  21.     cout << "匹配次数：" << sum-1 <<endl;
  22.     if(j > tlen){
  23.         //cout << "j:" << j << endl; 
  24.         return i-tlen;
  25.     }else{
  26.         return -1;
  27.     }
  28. } 
  29.  
  30. int main(){
  31.     string s,t;//主串和子串 
  32.     int op; //指定从什么位置开始匹配,注意不要输入下标，不要从0开始
  33.     getline(cin,s);
  34.     getline(cin,t);
  35.     cin >> op;
  36.     cout << "在位置" << BF(s,t,op) << "成功匹配";
  37. }

对以上的代码，可能最后有疑惑的地方有两个！

1，i = i-j+2;//公式 怎么来的？

2，为什么比较成功地位置是i-tlen？

1，首先，我们来看下面这张图主串abcabcd，子串abcd，在第一轮比较的时候，当比较到a和d的时候，第一轮比较终止，我们要计算下一轮比较开始的位置，通过计算得到下一个在主串比较的位置是2：b，然后依次类推。

切不可在如下的位置写上i++，因为这个表达式起不到回溯的效果。大家可以用上面的例子代入试一下。

2，在如下的例子中，我们可以很轻易的知道，一共比较了5次，最后一次i=6，j=3.

输入示例：

3.2，KMP算法完整代码如下：

 

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4.  
  5. int next[1000];
  6.  
  7. void getNext(string t){
  8.     int k = 0,j = 1;
  9.     next[1] = 0;
  10.     while(j < t.length()){
  11.         if(k == 0 || t[k-1]==t[j-1]){
  12.             next[++j] = ++k;
  13.         }else{
  14.             k = next[k];
  15.         }
  16.     }
  17.     for(int i = 1;i <= t.length();i++){
  18.         cout << "next[" << i << "]:" << next[i] << endl;
  19.     }
  20. }
  21.  
  22. int KMP(string s,string t, int op){
  23.     getNext(t);
  24.     int i = op, j = 1,sum = 0;//这里的i和j都代表的是长度而不是字符串的下标 
  25.     int slen = s.length();
  26.     int tlen = t.length();
  27.     while(i<=slen && j<=tlen){//比较长度是否大于字符串本身长度 
  28.         sum++;
  29.         if(s[i-1] == t[j-1]){//相等则i和j指针都加一 
  30.             i++;
  31.             j++;
  32.         }else{//不相等时，i指针不动，j指针回退到next[j] 
  33.             j = next[j];
  34.         }
  35.     }
  36.     cout << "匹配次数：" << sum <<endl;
  37.     if(j > tlen){
  38.         cout << "j:" << j << endl;
  39.         cout << "i:" << i << endl; 
  40.         return i-tlen;
  41.     }else{
  42.         return -1;
  43.     }
  44. }
  45. int main(){
  46.     string s,t;//主串和子串 
  47.     int op; //指定从什么位置开始匹配,注意不要输入下标 
  48.     getline(cin,s);
  49.     getline(cin,t);
  50.     cin >> op;
  51.     cout << "在位置" << KMP(s,t,op) << "成功匹配";
  52. }

运行示例：

首先我们来看看是如何计算出next[]数组的。

算法如下：

  1. void getNext(string t){
  2.     int k = 0,j = 1;
  3.     next[1] = 0;
  4.     while(j < t.length()){
  5.         if(k == 0 || t[k-1]==t[j-1]){
  6.             next[++j] = ++k;
  7.         }else{
  8.             k = next[k];
  9.         }
  10.     }
  11.     for(int i = 1;i <= t.length();i++){
  12.         cout << "next[" << i << "]:" << next[i] << endl;
  13.     }
  14. }

过程如下：

然后我们再来看看KMP算法如何执行

算法如下：

  1. int KMP(string s,string t, int op){
  2.     getNext(t);
  3.     int i = op, j = 1,sum = 0;//这里的i和j都代表的是长度而不是字符串的下标 
  4.     int slen = s.length();
  5.     int tlen = t.length();
  6.     while(i<=slen && j<=tlen){//比较长度是否大于字符串本身长度 
  7.         sum++;
  8.         if(s[i-1] == t[j-1]){//相等则i和j指针都加一 
  9.             i++;
  10.             j++;
  11.         }else{//不相等时，i指针不动，j指针回退到next[j] 
  12.             j = next[j];
  13.         }
  14.     }
  15.     cout << "匹配次数：" << sum <<endl;
  16.     if(j > tlen){
  17.         cout << "j:" << j << endl;
  18.         cout << "i:" << i << endl; 
  19.         return i-tlen;
  20.     }else{
  21.         return -1;
  22.     }
  23. }

当在位置4时，由于a!=b，这时j回退到next[j] = 1,,也就是说子串又从头开始比较，但是主串从比较失败的地方再次开始比较，主串的i指针不会回退。

4，二叉树的存储和遍历

1，树

1.2，树的存储结构

链式存储用的多一点。

树的三种顺序表示法：

-1表示不存在。

树的链式表示法：

2，二叉树

性质：

顺序存储：

不是完全二叉树就补0

可以使用一个数组，也可以使用两个数组

但是使用两个数组的时候，我们需要指明树的根。如上图。

链式存储：

3，遍历二叉树

遍历的秘诀：遍历到那个节点就把这个节点当作更节点

3.1，先序遍历

遍历顺序：先根，后左，再右

先序：ABDECFG

先序：ABCDEFGHJI

3.2，中序遍历

遍历顺序：先左，后根，再右

中序遍历：DBEAFGC

中序：BCDAFEJHIG

3.3,后序遍历

后序：DEBGFCA

后序：DCBFJIHGEA

3.4，层次遍历

同一层从左向右遍历

4，创建二叉树

5，还原二叉树

注意：只有给出中序和后序，或者中序和先序才可以还原出树。中序遍历必不可少。

练习：

4.1，二叉树的完整代码和算法分析：

遍历二叉树，完整代码如下：

  1. #include<iostream>
  2. #include <queue>//引入队列头文件
  3. using namespace std;
  4.  
  5. typedef struct Bnode{
  6.     char data;
  7.     struct Bnode *lchild,*rchild; 
  8. }Bnode,*Btree;
  9. //先序遍历创建二叉树 
  10. void Createtree(Btree &T){//传入根节点 
  11.     char p;
  12.     cin >> p;
  13.     if(p!='#'){
  14.         T = new Bnode;
  15.         T->data = p;
  16.         Createtree(T->lchild);
  17.         Createtree(T->rchild);
  18.     }else{
  19.         T = NULL;
  20.     }
  21. }
  22. //先序遍历输出二叉树
  23. void preNode(Btree T){//传入根节点
  24.     if(T){
  25.         cout << T->data << "\t";
  26.         preNode(T->lchild);
  27.         preNode(T->rchild);
  28.     }
  29. } 
  30. //中序遍历输出二叉树
  31. void inNode(Btree T){
  32.     if(T){
  33.         inNode(T->lchild);
  34.         cout << T->data << "\t";
  35.         inNode(T->rchild);
  36.     }
  37. } 
  38. //后序遍历输出二叉树
  39. void posNode(Btree T){
  40.     if(T){
  41.         posNode(T->lchild);
  42.         posNode(T->rchild);
  43.         cout << T->data << "\t";
  44.     }
  45. }
  46. //层次遍历输出二叉树
  47. bool LevelNode(Btree T){
  48.     Btree p;
  49.     queue<Btree> Q;
  50.     if(T){
  51.         Q.push(T);
  52.     }else{
  53.         return false;
  54.     }
  55.     while(!Q.empty()){
  56.         p=Q.front();//取出队头元素作为当前扩展结点livenode
  57.         Q.pop(); //队头元素出队
  58.         cout <<p->data<<"\t";
  59.         if(p->lchild){
  60.             Q.push(p->lchild); //左孩子指针入队
  61.         } 
  62.         if(p->rchild){
  63.             Q.push(p->rchild); //右孩子指针入队
  64.         }            
  65.     }
  66.     return true;
  67. } 
  68. int main()
  69. {
  70.     Btree mytree;
  71.     cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
  72.     Createtree(mytree);//创建二叉树
  73.     cout<<endl;
  74.     cout<<"二叉树的先序遍历结果："<<endl;
  75.     preNode(mytree);//先序遍历二叉树
  76.     cout<<endl;
  77.     cout<<"二叉树的中序遍历结果："<<endl;
  78.     inNode(mytree);//中序遍历二叉树
  79.     cout<<endl;
  80.     cout<<"二叉树的后序遍历结果："<<endl;
  81.     posNode(mytree);//后序遍历二叉树
  82.     cout<<endl;
  83.     cout<<"二叉树的层次遍历结果："<<endl;
  84.     LevelNode(mytree);//层次遍历二叉树
  85.     return 0;
  86. }

运行实例：

还原二叉树

  1. #include<iostream>
  2.  
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef struct Bnode{
  8.     char data;
  9.     struct Bnode *lchild,*rchild;
  10. }Bnode,*Btree;
  11. //通过前序遍历和中序遍历还原二叉树 
  12. Btree pre_mid_createBiTree(char *pre,char *mid,int len){
  13.          //作用1，判断是否有节点，结束递归的标志
  14.         if(len == 0){
  15.         return NULL;
  16.     }                 
  17.     char p = pre[0];//保存根节点
  18.     int index = 0;//记录左子树有多少个节点，也可以通过len-1-index算出右子树
  19.     while(mid[index] != p){//找寻根节点在中序中的位置
  20.         index++;
  21.     }
  22.     cout << index << endl;
  23.     Btree T = new Bnode;//创建新的节点保存这个节点
  24.     T->data = p;
  25.     T->lchild = pre_mid_createBiTree(pre+1, mid, index);//创建左子树
  26.         //pre+1：根节点的位置，mid：中序遍历不用做处理，因为左子树的创建，只需要从mid
  27.         //的0位置开始遍历，index在这里标识了左子树的节点个数，
  28.     T->rchild = pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);
  29.         //pre+index：是前序遍历中的根节点，pre+index+1：是右子树开始的位置
  30.         //mid+index：是中序遍历中的根节点的位置，mid+index+1：也是右子树开始的位置
  31.         //len-index-1：标识着右子树的节点数
  32.         return T;
  33. }
  34.  
  35. Btree pro_mid_createBiTree(char *last,char *mid,int len){
  36.     if(len == 0){
  37.         return NULL;
  38.     }
  39.     char p = last[0];
  40.     int index = 0;
  41.     while(mid[index] != p){
  42.         index++;
  43.     }
  44.     cout << index << "\t";bg 
  45.     Btree T = new Bnode;
  46.     T->data = p;
  47.     T->lchild = pro_mid_createBiTree(last+index+1, mid, index);
  48.     T->rchild = pro_mid_createBiTree(last+1,mid+index+1,len-index-1);
  49.     return T;
  50. }
  51.  
  52. //通过后序遍历和中序遍历还原二叉树 
  53. //Btree pro_mid_createBiTree(char *last,char *mid,int len){
  54. //    if(len == 0){
  55. //        return NULL;
  56. //    }
  57. //    char p = last[len-1];
  58. //    int index = 0;//因为是在中序遍历里面找，所以不用写last.size()-1 
  59. //    while(mid[index] != p){
  60. //        index++;
  61. //    }
  62. //    Btree T = new Bnode;
  63. //    T->data = p;
  64. //    T->lchild = pro_mid_createBiTree(last-1 ,mid ,index);
  65. //    T->rchild = pro_mid_createBiTree(last+index,mid+index+1,len-index-1);
  66. //    return T;
  67. //}
  68. //前序遍历输出 
  69. void pre_order(Btree T){
  70.     if(T){
  71.         cout << T->data << "\t";
  72.         pre_order(T->lchild);
  73.         pre_order(T->rchild);
  74.     }
  75. }
  76. //后序遍历输出 
  77. void pro_order(Btree T){
  78.     if(T){
  79.         pro_order(T->lchild);
  80.         pro_order(T->rchild);
  81.         cout << T->data << "\t";
  82.     }
  83. }
  84. int main()
  85. {
  86.     Btree T;
  87.     int n;
  88.     char pre[100],mid[100],last[100];
  89.     cout<<"1. 前序中序还原二叉树\n";
  90.     cout<<"2. 后序中序还原二叉树\n";
  91.     cout<<"0. 退出\n";
  92.     int choose=-1;
  93.     while(choose!=0)
  94.     {
  95.         cout<<"请选择:";
  96.         cin>>choose;
  97.  
  98.         switch (choose)
  99.         {
  100.             case 1://前序中序还原二叉树
  101.                 cout<<"请输入结点的个数:"<<endl;
  102.                 cin>>n;
  103.                 cout<<"请输入前序序列:"<<endl;
  104.                 for(int i=0;i<n;i++)
  105.                     cin>>pre[i];
  106.                 cout<<"请输入中序序列:"<<endl;
  107.                 for(int i=0;i<n;i++)
  108.                     cin>>mid[i];
  109.                 T=pre_mid_createBiTree(pre,mid,n);
  110.                 cout<<endl;
  111.                 cout<<"二叉树还原成功，输出其后序序列:"<<endl;
  112.                 pro_order(T);
  113.                 cout<<endl<<endl;
  114.                 break;
  115.             case 2://后序中序还原二叉树
  116.                 cout<<"请输入结点的个数:"<<endl;
  117.                 cin>>n;
  118.                 cout<<"请输入后序序列:"<<endl;
  119.                 for(int i=0 ;i<n;i++)
  120.                     cin>>last[i];
  121.                 cout<<"请输入中序序列:"<<endl;
  122.                 for(int i=0 ;i<n;i++)
  123.                     cin>>mid[i];
  124.                 reverse(last,last+n);
  125.                 cout << last;
  126.                 T=pro_mid_createBiTree(last,mid,n);
  127.                 cout<<endl;
  128.                 cout<<"二叉树还原成功，输出其先序序列:"<<endl;
  129.                 pre_order(T);
  130.                 cout<<endl<<endl;
  131.                 break;
  132.         }
  133.     }
  134.     return 0;
  135. }

运行实例：

统计节点数和叶子树

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef struct Bnode{
  5.     char data;
  6.     struct Bnode *lchild,*rchild; 
  7. }Bnode,*Btree;
  8.  
  9. //先序遍历创建二叉树 
  10. void Createtree(Btree &T){//传入根节点 
  11.     char p;
  12.     cin >> p;
  13.     if(p!='#'){
  14.         T = new Bnode;
  15.         T->data = p;
  16.         Createtree(T->lchild);
  17.         Createtree(T->rchild);
  18.     }else{
  19.         T = NULL;
  20.     }
  21. }
  22. //统计叶子节点 
  23. int LeafCount(Btree T){
  24.     int n = 0;
  25.     if(T== NULL){
  26.         //cout << "这是个空树" << endl;
  27.         return 0;
  28.     }else{
  29.                 //如果T->lchild == NULL && T->rchild == NULL
  30.                 //则表示这是一个叶子节点               
  31.         if(T->lchild == NULL && T->rchild == NULL){
  32.             return 1;
  33.         }else{
  34.             return LeafCount(T->lchild)+LeafCount(T->rchild);
  35.         }
  36.     }
  37. }
  38. //统计节点数 
  39. int NodeCount(Btree T){
  40.     if(T==NULL){
  41.         return 0;
  42.     }else{
  43.         return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
  44.     }
  45. }
  46.  
  47. int main(){
  48.     Btree T;
  49.     cout << "请输入先序遍历节点顺序:" << endl;
  50.     Createtree(T);
  51.     cout << "叶子节点有：" << LeafCount(T) << endl;
  52.     cout << "节点数有：" << NodeCount(T) << endl;
  53.     return 0; 
  54. }

运行实例：

部分代码解释：

  1. //统计节点数 
  2. int NodeCount(Btree T){
  3.     if(T==NULL){
  4.                 //此节点为空，直接不计数返回0                 
  5.         return 0;
  6.     }else{
  7.                 //其实这个代码就是说返回左子树节点和右子树节点
  8.                 //最后的加一其实加的是根节点
  9.                 //注意：请把每一个节点都当作根节点                
  10.         return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
  11.     }
  12. }

计算树的深度

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef struct Bnode    /*定义二叉树存储结构*/
  5. { char data;
  6.   struct Bnode *lchild,*rchild;
  7. }Bnode,*Btree;
  8.  
  9. void Createtree(Btree &T)    /*创建二叉树函数*/
  10. {
  11.     //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
  12.     char ch;
  13.     cin >> ch;
  14.     if(ch=='#')
  15.         T=NULL;            //递归结束，建空树
  16.     else{
  17.         T=new Bnode;
  18.         T->data=ch;                    //生成根结点
  19.         Createtree(T->lchild);    //递归创建左子树
  20.         Createtree(T->rchild);    //递归创建右子树
  21.     }
  22. }
  23.  
  24. int Depth(Btree T)//求二叉树的深度
  25. {
  26.     int m,n;
  27.     if(T==NULL)//如果为空树，深度为0
  28.         return 0;
  29.     else
  30.     {
  31.        m=Depth(T->lchild);//递归计算左子树深度
  32.        n=Depth(T->rchild);//递归计算左子树深度
  33.        if(m>n)//返回深度最大的子树
  34.           return m+1;//返回左右子树最大值加1
  35.        else
  36.           return n+1;
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     Btree mytree;
  43.     cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
  44.     //ABD##E##CF#G###
  45.     Createtree(mytree);//创建二叉树
  46.     cout<<endl;
  47.     cout<<"二叉树的深度为："<<Depth(mytree)<<endl;
  48.     return 0;
  49. }

附上一张比较好理解的图：

运行实例：

心得体会

1，体会：

手写完二叉树的遍历，创建，还原和统计之后，我感觉自己对递归的思想有了更深一步的理解，其实递归，就是使用一种可以解决这一类问题的通式，来不断的递推这个问题中的子问题，并且这些子问题可以自动回归，而二叉树就可以使用一种通式来解决二叉树的某一种问题，因为二叉树是一个十分有规律的结构，一棵最简单的树只有四种情况，1，没有左右子树；2，只有左子树；3，只有右子树；4，没有子树。我们解决问题的时候，只要构造出解决这四种情况的通式，所有的问题就可以因迎刃而解。

2，秘诀：

解决二叉树问题的秘诀：把每一个节点都当做根节点，每一个节点都有左子树和右子树（null也是一种子树状态）。

3，构造通式的秘诀：

其实构造通式并不困难，只要可以知道如何解决这个问题的子问题的步骤就好，然后按照步骤来就好。如下代码：

先序遍历创建二叉树

  1. //先序遍历创建二叉树 
  2. void Createtree(Btree &T){//传入根节点 
  3.     char p;
  4.     cin >> p;//1，传入节点数据
  5.     if(p!='#'){//2，判断这个节点是否为空，不为空就创建根结点，为空则返回0
  6.         T = new Bnode;
  7.         T->data = p;//2.1，创建并保存根节点
  8.         Createtree(T->lchild);//2.2保存好之后，我们开始创建他的左子树
  9.         Createtree(T->rchild);//2.3然后开始创建他的右子树
  10.     }else{
  11.         T = NULL;//2.1，返回空值
  12.     }
  13. }

5，哈夫曼树和哈夫曼编码

1，哈夫曼树概述

有时候，要是没有给出某个字符的出现频率，就要自己去算，公式为：字符频率=该字符出现的次数/所有字符的个数

哈夫曼树的构建步骤：

1，选没有双亲权值最小的两个节点t1，t2.

2，t1，t2作为左右子树构建一颗新树。

3，新树的根的权值为左右子树t1，t2的和。

举例

我们可以对字符的出现频率进行扩大，方便于我们计算。

最小的作为左子树，次小的作为右子树，左0，右1

作业：

哈夫曼树结构：

n：叶子树，2n-1：总结点数

2，哈夫曼编码

使用start标识读取编码的开始位置

存：从后往前存

读：从前往后读

两个指针不断地迭代，不断的指向父亲节点和父亲的父亲节点

如上图：哈夫曼编码的长度是2.37*10^6,而使用等长编码长度就是3*10^6，

2.37=0.05*4+0.32*2+0.18*2+0.07*4+0.25*2+0.13*3

而3的由来是因为，3位的编码可以表示8种不同的字符，而2位的编码可以表示4种不同的字符，所以要表示6种的不同的字符，只可以使用3位的编码方式。

 5.1，哈夫曼树和编码完整代码和算法解析

  1. #include<iostream>
  2. using namespace std;
  3. //预处理不需要加分号 
  4. #define MaxSize 100
  5. #define MaxWeight 100
  6. #define MaxLeave 0x3fff
  7. #define MaxNode MaxLeave*2-1
  8.  
  9. typedef struct HufuNode{
  10.     int parent;    //记录双亲节点 
  11.     int lchild;    //左孩子 
  12.     int rchild;    //右孩子 
  13.     double weight;    //权重 ,权重是小数时，使用double类型 
  14.     char value;    //字符 
  15. }HufuNode;
  16.  
  17. typedef struct HufuCode{
  18.     int start;                //记录存储和读取开始的位置 
  19.     int hfbit[MaxSize];    //保存编码信息，也就是0101的编码 
  20. }HufuCode;
  21. //类型名和变量名不可以重名 
  22. HufuNode hfNode[MaxNode];//保存节点信息 
  23. HufuCode hfCode[MaxLeave];//保存叶子节点信息
  24.  
  25. //构建哈夫曼树 
  26. void HufuTree(HufuNode hfNode[MaxNode],int n){
  27.      double m1,m2;
  28.      int x1,x2,i,j;
  29.     for(i = 0;i < 2*n-1;i++){//初始化，总共要初始化2*n-1个节点 
  30.         hfNode[i].parent = -1;
  31.          hfNode[i].lchild = -1;
  32.          hfNode[i].rchild = -1;
  33.          hfNode[i].weight = -1;
  34.          //hfNode[i].value = '';
  35.     } 
  36.     for(i = 0;i < n;i++){//为叶子节点赋值赋权重 
  37.         cout<<"请输入叶子节点的值和权重（使用空格分割）"<<i+1<<endl;
  38.         cin>>hfNode[i].value>>hfNode[i].weight;
  39.         cout << "hfNode[i].value:" << hfNode[i].value << "\t" << "hfNode[i].weight" << hfNode[i].weight << endl;
  40.     }    
  41.     //构建哈夫曼树
  42.     for(i = 0;i < n-1;i++){//执行n-1次合并
  43.         m1 = m2 = MaxWeight;
  44.          x1 = x2 = 0;
  45.         for(j = 0;j < n+i;j++){//不断的取最小的两个叶子节点 
  46.             if(hfNode[j].parent == -1 && hfNode[j].weight < m1){//首先要看这个节点是否有双亲节点 
  47.                 m2 = m1;                                        //有则不参与比较，这也是我们为什么要执行，如下语句的原因 
  48.                 x2 = x1;                                        //hfNode[x1].parent = i+n;
  49.                 m1 = hfNode[j].weight;                            //hfNode[x2].parent = i+n;
  50.                 x1 = j;
  51.             }else if(hfNode[j].parent == -1 && hfNode[j].weight < m2){
  52.                 m2 = hfNode[j].weight;
  53.                 x2 = j;
  54.             }
  55.         }
  56.         hfNode[i+n].weight = m1 + m2;//新节点的权重等于左右子树权重之和 
  57.         hfNode[i+n].lchild = x1;     //将最小的节点作为新节点的左子树 ,注意不要写成m1 
  58.         hfNode[i+n].rchild = x2;     //将此小的节点作为新节点的右子树 ,注意不要写成m2 
  59.         hfNode[x1].parent = i+n;     //将左子树的双亲节点置为i+n，也就是新节点的位置 
  60.         hfNode[x2].parent = i+n;     //将右子树的双亲节点置为i+n，也就是新节点的位置，也是通过这种方式防止子节点再次参与比较 
  61.         cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<hfNode[x1].weight<<"\t"<<hfNode[x2].weight<<endl;
  62.         //cout << "hfNode[x1].parent：" << hfNode[x1].parent <<endl; 
  63.     } 
  64.      
  65. }
  66. //产生哈弗曼编码
  67. void CHufuCode(HufuCode hfCode[MaxLeave],int n){
  68.     HufuCode hc;
  69.     int i,j,c,p;//c用来指向当前节点位置，p用来指向节点的父亲节点的下标
  70.     for(i = 0;i < n;i++){
  71.         hc.start = n-1;
  72.         c = i;
  73.         p = hfNode[i].parent;
  74.         while(p != -1){//当当前节点还有父亲节点，继续循环 
  75.             if(hfNode[p].lchild == c){//父节点的左子树是否等于当前节点 
  76.                 hc.hfbit[hc.start] = 0;
  77.                 hc.start--;
  78.                 //cout << "左子树" << endl; 
  79.             } else{//节点的右子树是否等于当前节点 
  80.                 hc.hfbit[hc.start] = 1;
  81.                 hc.start--;
  82.                 //cout << "右子树";
  83.             }
  84.             c = p;
  85.             p = hfNode[c].parent;
  86.             //cout << p << endl;
  87.         }
  88.         //把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组
  89.         for(j = hc.start+1; j < n;j++){//从hc.start+1开始存储编码，start不存 
  90.             hfCode[i].hfbit[j] = hc.hfbit[j];
  91.         }
  92.         hfCode[i].start = hc.start;    
  93.     } 
  94.     
  95. } 
  96.  
  97. int main(){
  98.     int n,i,j;
  99.     cout << "请输入叶子节点的个数：";
  100.     cin >> n;
  101.     HufuTree(hfNode,n);
  102.     CHufuCode(hfCode,n);
  103.     //输出叶子结点的哈弗曼编码
  104.     for(i = 0;i < n;i++){
  105.         cout << "叶子节点：" << hfNode[i].value << "对应的哈夫曼编码：";
  106.         for(j = hfCode[i].start+1;j < n;j++){//也是从hfCode[i].start+1开始读取编码 
  107.             cout << hfCode[i].hfbit[j];
  108.         }
  109.         cout << endl;
  110.     } 
  111.     return 0;
  112. }

生成哈夫曼编码的步骤：

1，构建哈夫曼树

1.1，选没有双亲权值最小的两个节点t1，t2.

1.2，t1，t2作为左右子树构建一颗新树。

1.3，新树的根的权值为左右子树t1，t2的和。

  1. //构建哈夫曼树
  2.     for(i = 0;i < n-1;i++){//执行n-1次合并
  3.         m1 = m2 = MaxWeight;
  4.          x1 = x2 = 0;
  5.         for(j = 0;j < n+i;j++){//不断的取最小的两个叶子节点 
  6.             if(hfNode[j].parent == -1 && hfNode[j].weight < m1){//首先要看这个节点是否有双亲节点 
  7.                 m2 = m1;                                        //有则不参与比较，这也是我们为什么要执行，如下语句的原因 
  8.                 x2 = x1;                                        //hfNode[x1].parent = i+n;
  9.                 m1 = hfNode[j].weight;                            //hfNode[x2].parent = i+n;
  10.                 x1 = j;
  11.             }else if(hfNode[j].parent == -1 && hfNode[j].weight < m2){
  12.                 m2 = hfNode[j].weight;
  13.                 x2 = j;
  14.             }
  15.         }
  16.         hfNode[i+n].weight = m1 + m2;//新节点的权重等于左右子树权重之和 
  17.         hfNode[i+n].lchild = x1;     //将最小的节点作为新节点的左子树 ,注意不要写成m1 
  18.         hfNode[i+n].rchild = x2;     //将此小的节点作为新节点的右子树 ,注意不要写成m2 
  19.         hfNode[x1].parent = i+n;     //将左子树的双亲节点置为i+n，也就是新节点的位置 
  20.         hfNode[x2].parent = i+n;     //将右子树的双亲节点置为i+n，也就是新节点的位置，也是通过这种方式防止子节点再次参与比较 
  21.         cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<hfNode[x1].weight<<"\t"<<hfNode[x2].weight<<endl;
  22.         //cout << "hfNode[x1].parent：" << hfNode[x1].parent <<endl; 
  23.     }

 

2，生成哈夫曼编码

2.1，从叶子节点开始向上寻找双亲结点，如果当前节点是双亲结点的左子树则编码为0，反之则为1

2.2，重复2.1，知道当前节点没有双亲节点。

  1. for(i = 0;i < n;i++){
  2.         hc.start = n-1;
  3.         c = i;
  4.         p = hfNode[i].parent;
  5.         while(p != -1){//当当前节点还有父亲节点，继续循环 
  6.             if(hfNode[p].lchild == c){//父节点的左子树是否等于当前节点 
  7.                 hc.hfbit[hc.start] = 0;
  8.                 hc.start--;
  9.                 //cout << "左子树" << endl; 
  10.             } else{//节点的右子树是否等于当前节点 
  11.                 hc.hfbit[hc.start] = 1;
  12.                 hc.start--;
  13.                 //cout << "右子树";
  14.             }
  15.             c = p;
  16.             p = hfNode[c].parent;
  17.             //cout << p << endl;
  18.         }
  19.         //把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组
  20.         for(j = hc.start+1; j < n;j++){//从hc.start+1开始存储编码，start不存 
  21.             hfCode[i].hfbit[j] = hc.hfbit[j];
  22.         }
  23.         hfCode[i].start = hc.start;    
  24.     }

运行示例如下：

哈夫曼树如下：

6，图（邻接矩阵和邻接表） 

1，图的概述

四种数据结构包括：集合，线性，树，图

图中至少有一个顶点，可以没有边。

无向图

有向图

简单图：不含平行边也不含自环

无向完全图和有向完全图

n：顶点

无向完全图边=n(n-1)/2

有向完全图边=n(n-1)

0

0

无向图中的概念：

连通图和连通分量

0

有向图中的概念：

强连通图和强连通分量：

0

二分图

0

2，图的存储

0

2.1，邻接矩阵

1，无向图的邻接矩阵（一定对称）

2，有向图的邻接矩阵（不一定对称 ）

3，网的邻接矩阵

邻接矩阵的数据结构

邻接矩阵的优缺点

2.2，邻接表

无向图的邻接表：

有向图的邻接表：

找出度容易，找入度难。

创建邻接表的过程：

1，保存顶点信息

2，输入边（使用头插法实现）

邻接表优缺点：

邻接矩阵遍历所有的邻接点的时间复杂度为O（n^2）,空间复杂度为O(n^2)，所以说稠密图可以使用邻接矩阵存储。

邻接表遍历所有邻接点的时间复杂度为O(n+e)，空间复杂度：O(n+2e)[无向图]，O(n+e)[有向图]

 6.1，邻接矩阵和邻接表完整代码

示例图：

1，邻接矩阵存储有向图

以下代码运行的大致流程：

1，首先我们输入顶点数，边数和相互邻接的两个顶点m，n。

2，查询m和n在顶点表中的位置并且返回。

3，然后在矩阵中找到这两个元素的位置并且——f.Edge[y][z] = 1（这时有向图的做法，存储无向图也只是在这个步骤上做了改动）

  1. //邻接矩阵存储有向图
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. #define MaxVnum 100      //顶点数最大值
  6. typedef char VexType;   //顶点的数据类型，根据需要定义
  7. typedef int EdgeType;   //边上权值的数据类型，若不带权值的图，则为0或1
  8.  
  9. typedef struct FMGragh{
  10.     int Enum,Vnum;        //存储顶点的个数和边的个数
  11.     EdgeType Edge[MaxVnum][MaxVnum]; 
  12.     VexType v[MaxVnum];
  13. }FMGragh;
  14.  
  15. //寻找顶点在顶点表中的位置 
  16. int Locatevex(FMGragh f,char a){
  17.     int i;
  18.     for(i=0;i < f.Vnum;i++){
  19.         if(f.v[i] == a){
  20.             return i;
  21.         }
  22.     }
  23.     //cout << "无法找到对应顶点" << endl;
  24.     return -1; 
  25. }
  26.  
  27. //初始化有向图
  28. void CreateF(FMGragh &f){
  29.     int i,j,y,z;
  30.     char m,n;
  31.     cout << "请输入图的顶点个数" << endl;
  32.     cin >> f.Vnum;
  33.     cout << "请输入图的边的条数" << endl;
  34.     cin >> f.Enum;
  35.     cout << "请输入图的顶点元素的值" << endl;
  36.     for(i = 0;i < f.Vnum;i++){
  37.         cin >> f.v[i]; 
  38.     }
  39.     for(j = 0;j < f.Enum;j++){
  40.     cout << "请输入边的邻接的两个顶点(第一个元素为弧头，第二个元素为弧尾)" << endl;
  41.     cin >> m >> n;
  42.     y = Locatevex(f,m);        //寻找m元素在顶点表中的位置,弧头
  43.     z = Locatevex(f,n);        //寻找n元素在顶点表中的位置,弧尾
  44.     if(y != -1 && z != -1){
  45.         //a.Edge[y][z] = a.Edge[z][y] = 1;
  46.         f.Edge[y][z] = 1; 
  47.     }else{
  48.         cout << "无法找到对应顶点,请重新输入" << endl;
  49.         j--;
  50.     }     
  51.     } 
  52. } 
  53.  
  54. //打印有向图
  55. void printF(FMGragh f){
  56.     int i,j;
  57.     for(i = 0;i < f.Vnum;i++){
  58.         for(j = 0;j < f.Vnum;j++){
  59.             cout << f.Edge[i][j] << "\t";
  60.         }
  61.         cout << endl;
  62.     }
  63. } 
  64.  
  65. int main(){
  66.     FMGragh f;
  67.     CreateF(f);
  68.     printF(f);
  69.     return 0;
  70. }

 

运行示例：

分析：

首先我们要知道，有向图和无向图我们在用邻接矩阵存储的时候有什么差异：

我们可以看到有向图使用邻接矩阵存储的示意图如下：

无向图使用邻接矩阵存储的示意图如下：

可以看到无向图在邻接矩阵中的存储是对称的，而有向图则不是。所以我们在存储的使用也应当使用不同的策略。

2，邻接矩阵存储无向图

以下代码运行的大致流程：

1，首先我们输入顶点数，边数和相互邻接的两个顶点m，n。

2，查询m和n在顶点表中的位置并且返回。

3，然后在矩阵中找到这两个元素的位置并且——a.Edge[y][z] = a.Edge[z][y] = 1;（这时无向图的做法，存储有向图也只是在这个步骤上做了改动）

  1. //邻接矩阵存储无向图
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. #define MaxVnum 100      //顶点数最大值
  6. typedef char VexType;   //顶点的数据类型，根据需要定义
  7. typedef int EdgeType;   //边上权值的数据类型，若不带权值的图，则为0或1
  8.  
  9. typedef struct AMGragh {
  10.     EdgeType Edge[MaxVnum][MaxVnum]; //存储边的信息 
  11.     VexType v[MaxVnum];         //存储顶点值 
  12.     int Enum,Vnum;                //存储顶点和边的个数 
  13. }AMGragh;
  14.  
  15. //查找顶点所在的位置便且返回 
  16. int Locatevex(AMGragh a,char c){
  17.     int i;
  18.     for(i=0;i < a.Vnum;i++){
  19.         if(a.v[i] == c){
  20.             return i;
  21.         }
  22.     }
  23.     //cout << "无法找到对应顶点" << endl;
  24.     return -1; 
  25. }
  26.  
  27. //初始化邻接矩阵
  28. void CreateL(AMGragh &a){
  29.     int i,j,y,z;
  30.     char m,n;
  31.     cout << "请输入图的顶点个数" << endl;
  32.     cin >> a.Vnum;
  33.     cout << "请输入图的边的条数" << endl;
  34.     cin >> a.Enum;
  35.     cout << "请输入图的顶点元素的值" << endl;
  36.     for(i = 0;i < a.Vnum;i++){
  37.         cin >> a.v[i]; 
  38.     }
  39.     for(j = 0;j < a.Enum;j++){
  40.     cout << "请输入边的邻接的两个顶点" << endl;
  41.     cin >> m >> n;
  42.     y = Locatevex(a,m);        //寻找m元素在顶点表中的位置 
  43.     z = Locatevex(a,n);        //寻找n元素在顶点表中的位置 
  44.     if(y != -1 && z != -1){
  45.         a.Edge[y][z] = a.Edge[z][y] = 1;
  46.     }else{
  47.         cout << "无法找到对应顶点,请重新输入" << endl;
  48.         j--;
  49.     }     
  50.     } 
  51.     
  52. } 
  53.  
  54. //打印邻接矩阵
  55. void printL(AMGragh a){
  56.     int i,j;
  57.     for(i = 0;i < a.Vnum;i++){
  58.         for(j = 0;j < a.Vnum;j++){
  59.             cout << a.Edge[i][j] << "\t";
  60.         }
  61.         cout << endl;
  62.     }
  63. }  
  64.  
  65. int main(){
  66.     AMGragh a;
  67.     CreateL(a);
  68.     printL(a);
  69.     return 0;
  70. }

运行示例：

3，邻接表存储有向图

以下的代码运行流程如下：

1，首先我们输入图的顶点数和边数。

2，输入顶点值

3，输入相互邻接的顶点

  1. //邻接表存储有向图
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. #define MaxVnum 100
  6. typedef char NodeType;
  7.  
  8. typedef struct LNode{    //定义邻接节点数据结构 
  9.     struct LNode *next;    //用于指向下一个邻接节点 
  10.     NodeType Ndata;        //节点中的值 
  11. }LNode,*ListNode; 
  12.  
  13. typedef struct LVex{    //定义顶点数据结构 
  14.     ListNode first;        //用于指向第一个邻接节点 
  15.     NodeType Vdata;        //存储顶点信息 
  16. }LVex,*ListVex;
  17.  
  18. typedef struct Vexs{    //用于保存图的简要信息的数据结构 
  19.     LVex lv[MaxVnum];    //用于线性保存顶点信息 
  20.     int Enum,Vnum;        //用于保存边数和顶点数 
  21. }Vexs; 
  22.  
  23. //最好把方法先声明，然后再调用 
  24. void Insertedge(Vexs &v);
  25. int LocateVex(Vexs v,NodeType a);
  26. void CreateFG(Vexs &v);
  27. void printFG(Vexs v);
  28.  
  29. int main(){
  30.     Vexs v;
  31.     CreateFG(v);
  32.     printFG(v);
  33.     return 0;
  34. }
  35.  
  36. //插入边 
  37. void Insertedge(Vexs &v){
  38.     int i,j,z;
  39.     NodeType m,n;
  40.     ListNode s;
  41.     for(z = 0;z < v.Enum;z++){
  42.         cout << "请输入邻接的顶点" << endl;
  43.         cin >> m >> n;
  44.         i = LocateVex(v,m);    //弧头节点的位置 
  45.         j = LocateVex(v,n);    //弧尾节点的位置 
  46.         cout << "弧头" << i << "\t" << "弧尾" << j << endl; 
  47.         if(i != -1 && j != -1){
  48.             s = new LNode;
  49.             s->Ndata = n;
  50.             s->next = NULL;
  51.             s->next = v.lv[i].first;
  52.             v.lv[i].first = s; //注意这里first指针已经指向第一个邻接节点，而不是它本身 
  53.             cout << "头插法插入" << v.lv[i].first->Ndata << endl; 
  54.         }else{
  55.             cout << "顶点不存在，请重新输入" << endl;
  56.             z--; 
  57.         }
  58.     } 
  59.     
  60. }
  61.  
  62. //用于寻找该字符在顶点线性表中的位置 
  63. int LocateVex(Vexs v,NodeType a){
  64.     int i;
  65.     for(i = 0;i < v.Vnum;i++){
  66.         if(v.lv[i].Vdata == a){
  67.             return i;
  68.         }
  69.     }
  70.     return -1;
  71. } 
  72. //创建邻接表保存有向图
  73. void CreateFG(Vexs &v){
  74.     int i;
  75.     cout << "请输入有向图的顶点的个数" << endl;
  76.     cin >> v.Vnum;
  77.     cout << "请输入有向图的边的条数" << endl;
  78.     cin >> v.Enum;
  79.     cout << "请输入有向图的顶点值" << endl;
  80.     for(i = 0;i < v.Vnum;i++){
  81.         cin >> v.lv[i].Vdata;
  82.         v.lv[i].first = NULL;
  83.     }
  84.     for(i = 0;i < v.Vnum;i++){//打印输入的顶点 
  85.         cout << v.lv[i].Vdata << "\t";
  86.     }
  87.     cout << endl; 
  88.     Insertedge(v);
  89. } 
  90.  
  91. //打印有向图
  92. void printFG(Vexs v){
  93.     int i,j;
  94.     ListNode p;
  95.     for(i = 0;i < v.Vnum;i++){
  96.         //p = v.lv[i].first->next;千万注意这里不可以这么写 
  97.         p = v.lv[i].first;
  98.         cout << "[" << v.lv[i].Vdata << "]："; 
  99.         while(p){
  100.             cout << p->Ndata << "\t";
  101.             p = p->next;
  102.         }
  103.         cout << endl;
  104.     }
  105. }

 

运行示例：

4，邻接表存储无向图

无向图和有向图的存储，只有在存储边的时候，步骤有所改变，它不仅仅插入弧尾，还会插入弧头节点

  1. //邻接表存储无向图
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. #define MaxVnum 100
  6. typedef char NodeType;
  7.  
  8. typedef struct LNode{    //定义邻接节点数据结构 
  9.     struct LNode *next;    //用于指向下一个邻接节点 
  10.     NodeType Ndata;        //节点中的值 
  11. }LNode,*ListNode; 
  12.  
  13. typedef struct LVex{    //定义顶点数据结构 
  14.     ListNode first;        //用于指向第一个邻接节点 
  15.     NodeType Vdata;        //存储顶点信息 
  16. }LVex,*ListVex;
  17.  
  18. typedef struct Vexs{    //用于保存图的简要信息的数据结构 
  19.     LVex lv[MaxVnum];    //用于线性保存顶点信息 
  20.     int Enum,Vnum;        //用于保存边数和顶点数 
  21. }Vexs; 
  22.  
  23. //最好把方法先声明，然后再调用 
  24. void Insertedge(Vexs &v);
  25. int LocateVex(Vexs v,NodeType a);
  26. void CreateFG(Vexs &v);
  27. void printFG(Vexs v);
  28.  
  29. int main(){
  30.     Vexs v;
  31.     CreateFG(v);
  32.     printFG(v);
  33.     return 0;
  34. }
  35.  
  36. //插入边 
  37. void Insertedge(Vexs &v){
  38.     int i,j,z;
  39.     NodeType m,n;
  40.     ListNode s,q;
  41.     for(z = 0;z < v.Enum;z++){
  42.         cout << "请输入邻接的顶点" << endl;
  43.         cin >> m >> n;
  44.         i = LocateVex(v,m);    //弧头节点的位置 
  45.         j = LocateVex(v,n);    //弧尾节点的位置 
  46.         cout << "弧头" << i << "\t" << "弧尾" << j << endl; 
  47.         if(i != -1 && j != -1){
  48.             s = new LNode;
  49.             s->Ndata = n;
  50.             s->next = v.lv[i].first;
  51.             v.lv[i].first = s; //注意这里first指针已经指向第一个邻接节点，而不是它本身 
  52.             q = new LNode;
  53.             q->Ndata = m;
  54.             q->next = v.lv[j].first;
  55.             v.lv[j].first = q;
  56.             cout << "头插法插入" << v.lv[i].first->Ndata << endl; 
  57.             cout << "头插法插入" << v.lv[j].first->Ndata << endl; 
  58.         }else{
  59.             cout << "顶点不存在，请重新输入" << endl;
  60.             z--; 
  61.         }
  62.     } 
  63.     
  64. }
  65.  
  66. //用于寻找该字符在顶点线性表中的位置 
  67. int LocateVex(Vexs v,NodeType a){
  68.     int i;
  69.     for(i = 0;i < v.Vnum;i++){
  70.         if(v.lv[i].Vdata == a){
  71.             return i;
  72.         }
  73.     }
  74.     return -1;
  75. } 
  76. //创建邻接表保存有向图
  77. void CreateFG(Vexs &v){
  78.     int i;
  79.     cout << "请输入有向图的顶点的个数" << endl;
  80.     cin >> v.Vnum;
  81.     cout << "请输入有向图的边的条数" << endl;
  82.     cin >> v.Enum;
  83.     cout << "请输入有向图的顶点值" << endl;
  84.     for(i = 0;i < v.Vnum;i++){
  85.         cin >> v.lv[i].Vdata;
  86.         v.lv[i].first = NULL;
  87.     }
  88.     for(i = 0;i < v.Vnum;i++){//打印输入的顶点 
  89.         cout << v.lv[i].Vdata << "\t";
  90.     }
  91.     cout << endl; 
  92.     Insertedge(v);
  93. } 
  94.  
  95. //打印有向图
  96. void printFG(Vexs v){
  97.     int i,j;
  98.     ListNode p;
  99.     for(i = 0;i < v.Vnum;i++){
  100.         //p = v.lv[i].first->next;千万注意这里不可以这么写 
  101.         p = v.lv[i].first;
  102.         cout << "[" << v.lv[i].Vdata << "]："; 
  103.         while(p){
  104.             cout << p->Ndata << "\t";
  105.             p = p->next;
  106.         }
  107.         cout << endl;
  108.     }
  109. }

运行示例：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/496382
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号