C++之算法入门

末蓝、 2022-12-21 06:08 60阅读 0赞

### C++之算法入门 ###

本文介绍：最大公约数和最小公倍数、单链表、直接插入排序、创建各类字符三角形图案，作为抛砖引玉吧。

**一、最大公约数和最小公倍数**

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。

求最大公约数算法很多。这里仅介绍相减法：

有两整数a和b：

① 若a>b，则a=a-b

② 若a<b，则b=b-a

③ 若a=b，则a（或b）即为两数的最大公约数

④ 若a≠b，则再回去执行①

例如求27和15的最大公约数过程为：

27－15＝12( 15>12 ) 15－12＝3( 12>3 )

12－3＝9( 9>3 ) 9－3＝6( 6>3 )

6－3＝3( 3==3 )

因此，3即为最大公约数。

最小公倍数：两个或多个整数公有的倍数成为他们的公倍数，其中一个最小的公倍数是他们的最小公倍数。

求最小公倍数算法：

最小公倍数=两整数的乘积÷最大公约数

**求两数的最大公约数的代码**

\#include <iostream>

using namespace std;

int main()

int n1, n2;

cout << "输入两个整数: ";

cin >> n1 >> n2;

while(n1 != n2)

if(n1 > n2)

n1 -= n2;

else

n2 -= n1;

cout << "求两数的最大公约数：" << n1;

return 0;

运行之，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70][]

相同的算法采用函数调用，代码如下：

\#include <iostream>

using namespace std;

int gcd(int a, int b)

while(a != b)

if(a  > b)

a  -= b;

else

b -= a ;

return a;

int main()

int n1, n2;

cout << "输入两个整数: ";

cin >> n1 >> n2;

cout << "求两数的最大公约数：" << gcd(n1, n2);

return 0;

运行之，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1][]

**求两数的最小公倍数的代码**

\#include <iostream>

using namespace std;

int main()

int n1, n2, hcf, temp, lcm;

cout << "输入两个数: ";

cin >> n1 >> n2;

hcf = n1;

temp = n2;

while(hcf != temp)

if(hcf > temp)

hcf -= temp;

else

temp -= hcf;

lcm = (n1 \* n2) / hcf;

cout << "两数最小公倍数： " << lcm;

return 0;

运行之，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2][]

相同的算法采用函数调用，代码如下：

\#include <iostream>

using namespace std;

int lcm(int a, int b)

int hcf, temp, lcm;

hcf = a;

temp = b;

while(hcf != temp)

if(hcf > temp)

hcf -= temp;

else

temp -= hcf;

lcm = (a \* b) / hcf;

return lcm ;

int main()

int n1, n2;

cout << "输入两个整数: ";

cin >> n1 >> n2;

cout << "两数数最小公倍数：" << lcm(n1, n2);

return 0;

运行之，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3][]

**二、单链表**

在此仅介绍单链表。

单链表: 链表中的数据是以节点来表示的，每个结点的构成：元素( 数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

链表是由一系列连接在一起的结点构成，每个结点都包含一个或多个保存数据的成员，除了数据之外，每个结点还包含一个后继指针指向链表中的下一个结点，参见下图：

![20201115095839676.png][]

非空链表的第一个结点称为链表的头。要访问链表中的结点，需要有一个指向链表头的指针。从链表头开始，可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。

因为指向链表头的指针用于定位链表的头部，所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表，从头开始，后面跟着后续指针，所以也可以很自然地把它看作是代表了整个链表。

下给出了一个由 3 个结点组成的链表，其中显示了指向头部的指针，链表的 3 个结点以及表示链表末尾的 nullptr 指针。

![20201115095839690.png][]

一个结点声明的例子：

struct ListNode

double value;

ListNode \*next;

\};

其中，有一个类型为 double 的数据项，另一个结构成员 next 则被声明为 ListNode 的指针，它是指向下一个结点的后继指针。

请注意，ListNode 结构有一个有趣的属性，它包含一个指向相同类型数据结构的指针，因此可以说是一个包含对自身引用的类型。像这样的类型称为自引用数据类型或自引用数据结构。

在已经声明了一个数据类型来表示结点之后，即可定义一个初始为空的链表，方法是定义一个用作链表头的指针并将其初始化为 nullptr，示例如下：

ListNode \*head = nullptr;

现在可以创建一个链表，其中包含一个结点，存储值为 12.5，如下所示：

纯文本复制

head = new ListNode; //分配新结点

head->value = 12.5; //存储值

head->next = nullptr; //表示链表的结尾

接下来再看一看如何创建一个新结点，在其中存储 13.5 的值，并将其作为链表中的第二个结点。可以使用第二个指针来指向新分配的结点（其中将存储 13.5 的值），示例如下：

ListNode \*secondPtr = new ListNode;

secondPtr->value = 13.5;

secondPtr->next = nullptr; //第二个结点是链表的结尾

head->next = secondPtr; //第一个结点指向第二个

以上语句通过将其后继指针 secondPtr->next 设置为 nullptr，可以使第二个结点成为链表的结尾，通过 head->next = secondPtr; 语句将链表头的后继指针改为指向第二个结点。

下面的程序代码演示说明了如何创建一个简单的链表：

\#include <iostream>

using namespace std;

struct ListNode

double value;

ListNode \*next;

\};

int main()

ListNode \*head = nullptr;

// 创建第一个节点

head = new ListNode; // 分配新节点

head->value = 12.5;    // 存储值

head->next = nullptr; // 表示链表的结尾

//  创建第二个节点

ListNode \*secondPtr = new ListNode;

secondPtr->value = 13.5;

secondPtr->next = nullptr; // 第二个结点是链表的结尾

head->next = secondPtr; //第一个结点指向第二个

// Print the list

cout << "第一项是 " << head->value << endl;

cout << "第二项是 " << head->next->value << endl;

return 0;

【提示：其中 ListNode \*head = nullptr; 这句编译（compile）时可能报错\[Error\] 'nullptr' was not declared in this scope ，若碰到怎么处理？

需要令Dev-c++开启使用C++11新特性

gcc4.8以后的版本都是支持c++11新特性的，只是需要在编译的时候设置-std的参数。默认未开启，需要设置：

设置方法是:在Tools里面找到Compiler Options打开它，然后把那个Add the following commands when calling compiler:选上勾，在里面加入-std=c++11就可以了，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 4][]

】

运行之，参见下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 5][]

单链表初始化及其增、删、改、查、遍历，代码如下：

\#include<bits/stdc++.h>  
\#include <stdio.h>  
\#include <stdlib.h>  
using namespace std;  
typedef int ElemType;

typedef struct pNode\{  
    ElemType data;  
    struct pNode \*next;  
\}LinkList;

//头插法建立单链表  
LinkList \*Creat\_LinkList()  
\{  
    ElemType x;  
    LinkList \*head,\*p;  
    head = (LinkList\*)malloc(sizeof(LinkList));  
    if(head == NULL)  
        return head;  
    head -> next = NULL;  
    cout<<"请输入要录入的数以0结束"<<endl;  
    cin >> x;  
    while(x != 0)  
    \{  
        p = (LinkList\*) malloc(sizeof(LinkList));  
        if(p == NULL)  
            return head;  
        p -> data = x;  
        p -> next = head -> next;  
        head -> next = p;  
        cin >> x;  
     \}  
     return head;  
\}

//尾插法建立单链表  
LinkList \* Creat\_LinkList\_R()  
\{  
    ElemType x;  
    LinkList \*head,\*p,\*tail;//tail是尾指针  
    head = (LinkList\*)malloc(sizeof(LinkList));  
    if(head == NULL)  
        return head;  
    head -> next = NULL;  
    tail = head; //一开始尾指针指向头指针的位置  
    cout<<"请输入要录入的数以0结束"<<endl;  
    cin >> x;  
    while(x != 0)  
    \{  
        p = (LinkList\*) malloc(sizeof(LinkList));  
        if(p == NULL)  
            return head;  
        p -> data = x;  
        tail -> next = p; //将p插入到尾节点的后面  
        tail = p;   //修改尾节点的指向  
        tail -> next = NULL;    //将尾节点的指针域修改为空  
        cin >> x;  
    \}  
    return head;  
\}

//单链表的遍历  
int Print\_LinkList(LinkList \*head)  
\{  
    LinkList\* p = head -> next;  
    if(p == NULL)  
        return 0;  
    while(p != NULL)  
    \{  
        cout << p -> data << endl;  
        p = p -> next;  
    \}  
    return 1;  
\}

//单链表求长度  
int LinkList\_Length(LinkList\* head)  
\{  
    ElemType num = 0;  
    LinkList \* p = head;  
    while(p -> next != NULL)  
    \{  
        num++;  
        p = p -> next;  
    \}  
    return num;  
\}

//单链表的查找(返回指定位置的元素)  
LinkList \* GetDara\_LinkList(LinkList \* head,int i)\{  
    LinkList \* p = head;  
    int num = 0; //计数器，每次加1，p的指向向后面改变一次  
    if(i < 0)  
        return NULL;  
    while((p -> next != NULL )&&(num < i))  
    \{  
        num++;  
        p = p -> next;  
    \}  
    if(num == i)  
        cout<< p -> data <<endl;  
    else  
        return NULL;  
\}

//单链表的查找(按照值来查找)  
LinkList \* GetDara\_LinkList\_value(LinkList \*head,int value)  
\{  
    LinkList \*p = head -> next;  
    while(p != NULL)  
    \{  
        if(p -> data != value)  
            p = p -> next;  
        else  
            break;  
    \}  
    cout << "查询到" << p -> data <<endl;  
\}

//单链表的插入(后插)  
void InsertAfter\_LinkList(LinkList \* p,LinkList \* s)  
\{  
    s -> next = p -> next;  
    p -> next = s;  
\}

//单链表的插入(前插)  
void InsertBefore\_LinkList(LinkList \*head,LinkList \*p,LinkList \*s)  
\{  
    LinkList \*q = head;  
    while(q -> next != p)   //搜索P的前驱节点  
        q = q -> next;  
    s -> next = p;  
    q -> next = s;  
\}

//在链表中指定位置前插入新节点s  
int InsertIndex\_LinkList(LinkList \* head,LinkList \*s,int i)  
\{  
    LinkList \*p;  
    if(i <= 0) p = NULL;  
    else if(i == 1) p = head;  
    else  
        p = GetDara\_LinkList(head,i-1);  
    if(p == NULL)  
        return 0;  
    else\{  
        InsertAfter\_LinkList(p,s);  
        return 1;  
    \}  
\}

//删除P的后继节点  
int DeleteAfter\_LinkList(LinkList \*p)  
\{  
    LinkList \* r;  
    if(!p) return 0;  
    r = p -> next;  
    if(!r)  
        return 0;  
    p -> next = r -> next;  
    free(r);  
    return 1;  
\}

int main()  
\{  
    LinkList \*L;  
    //L = Creat\_LinkList(); //头插法建立单链表  
    L = Creat\_LinkList\_R(); //尾插法建立单链表  
    Print\_LinkList(L);  //遍历单链表  
    int L\_Length = LinkList\_Length(L); //单链表长度  
    cout << "单链表的长度为：" << L\_Length <<endl;  
    GetDara\_LinkList(L,1); //返回第一个位置的元素  
    GetDara\_LinkList\_value(L,1); //按照链表中的值(1)来查找  
    // InsertAfter\_LinkList(LinkList \* p,LinkList \* s) //单链表的插入(后插)  
    // InsertBefore\_LinkList(LinkList \*head,LinkList \*p,LinkList \*s) //在链表中指定位置前插入新节点s  
    // InsertIndex\_LinkList(LinkList \* head,LinkList \*s,int i) //在链表中指定位置前插入新节点s  
    // int DeleteAfter\_LinkList(p); //删除P的后继节点

return 0;  
\}

再给出一个示网址：

C++双向链表实现简单通讯录 [https://www.jb51.net/article/187263.htm][https_www.jb51.net_article_187263.htm]

**三、直接插入排序（Straight Insertion Sort）**

排序（Sort）算法很多，在此仅价绍直接插入排序。

直接插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序算法的一般步骤：

1.从第一个元素开始，该元素可以认为已被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一个位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后，重复2~5

代码如下：

\#include <iostream>

using namespace std;

void InsertionSort(int A\[\], int n)

for (int i = 1; i < n; i++)

int get = A\[i\];

int j = i - 1;

while (j >= 0 && A\[j\] > get)

A\[j + 1\] = A\[j\];

j--;

A\[j + 1\] = get;

int main()

int A\[\] = \{ 6, 5, 3, 10, 8, 7, 20, 4 \};

int n = sizeof(A) / sizeof(int);

InsertionSort(A, n);

cout <<"插入排序结果："<< endl;

for (int i = 0; i < n; i++)

cout << A\[i\] << " ";

return 0;

更多的排序算法参见 [https://blog.csdn.net/YQMind/article/details/83819339][https_blog.csdn.net_YQMind_article_details_83819339]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70]: /images/20221120/0fe90d37b95d4b799a522c187b81c734.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201115095717468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201115095808493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201115095808598.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[20201115095839676.png]: https://img-blog.csdnimg.cn/20201115095839676.png
[20201115095839690.png]: https://img-blog.csdnimg.cn/20201115095839690.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201115095839708.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201115095839830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM=,size_16,color_FFFFFF,t_70
[https_www.jb51.net_article_187263.htm]: https://www.jb51.net/article/187263.htm
[https_blog.csdn.net_YQMind_article_details_83819339]: https://blog.csdn.net/YQMind/article/details/83819339