C++之算法入門

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;

}

運行之，參見下圖：

 

相同的算法采用函數調用，代碼如下：

#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;

}

 

運行之，參見下圖：

 

求兩數的最小公倍數的代碼

#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;

}

運行之，參見下圖：

 

相同的算法采用函數調用，代碼如下：

#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;

}

運行之，參見下圖：

 

二、單鏈錶

在此僅介紹單鏈錶。

單鏈錶: 鏈錶中的數據是以節點來錶示的，每個結點的構成：元素( 數據元素的映象) + 指針(指示後繼元素存儲比特置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。

鏈錶是由一系列連接在一起的結點構成，每個結點都包含一個或多個保存數據的成員，除了數據之外，每個結點還包含一個後繼指針指向鏈錶中的下一個結點，參見下圖：

非空鏈錶的第一個結點稱為鏈錶的頭。要訪問鏈錶中的結點，需要有一個指向鏈錶頭的指針。從鏈錶頭開始，可以按照存儲在每個結點中的後繼指針訪問鏈錶中的其餘結點。最後一個結點中的後繼指針被設置為 nullptr 以指示鏈錶的結束。

因為指向鏈錶頭的指針用於定比特鏈錶的頭部，所以也可以認為它代錶了鏈錶頭。同樣的指針也可以用來定比特整個鏈錶，從頭開始，後面跟著後續指針，所以也可以很自然地把它看作是代錶了整個鏈錶。

下給出了一個由 3 個結點組成的鏈錶，其中顯示了指向頭部的指針，鏈錶的 3 個結點以及錶示鏈錶末尾的 nullptr 指針。

 

一個結點聲明的例子：

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就可以了，參見下圖：

】

運行之，參見下圖：

 

單鏈錶初始化及其增、删、改、查、遍曆，代碼如下：

#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

 

三、直接插入排序（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

四、創建各類字符三角形圖案

#include <iostream>

using namespace std;

 

int main()

{

    int rows;

 

    cout << "輸入行數: ";

    cin >> rows;

 

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

    {

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

        {

            cout << "* ";

        }

        cout << "\n";

    }

    return 0;

}

 

以上程序執行輸出5行的結果為：

*

* *

* * *

* * * *

* * * * *

 

 

#include <iostream>

using namespace std;

 

int main()

{

    int rows;

 

    cout << "輸入行數: ";

    cin >> rows;

 

    for(int i = rows; i >= 1; --i)

    {

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

        {

            cout << "* ";

        }

        cout << endl;

    }

   

    return 0;

}

 

以上程序執行輸出5行的結果為：

* * * * *

* * * *

* * *

* *

*

 

#include <iostream>

using namespace std;

 

int main()

{

    int space, rows;

 

    cout <<"輸入行數: ";

    cin >> rows;

 

    for(int i = 1, k = 0; i <= rows; ++i, k = 0)

    {

        for(space = 1; space <= rows-i; ++space)

        {

            cout <<"  ";

        }

 

        while(k != 2*i-1)

        {

            cout << "* ";

            ++k;

        }

        cout << endl;

    }   

    return 0;

}

 

以上程序執行輸出5行的結果為：

    *

   ***

  *****

 *******

*********

 

#include <iostream>

using namespace std;

 

int main()

{

    int rows;

 

    cout << "輸入行數: ";

    cin >> rows;

 

    for(int i = rows; i >= 1; --i)

    {

        for(int space = 0; space < rows-i; ++space)

            cout << "  ";

 

        for(int j = i; j <= 2*i-1; ++j)

            cout << "* ";

 

        for(int j = 0; j < i-1; ++j)

            cout << "* ";

 

        cout << endl;

    }

 

    return 0;

}

 

以上程序執行輸出5行的結果為：

*********

 *******

  *****

   ***

    *