C++之算法入門

程序員大本營 2021-09-18 04:19:15 阅读数:197

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行的結果為:

*********

 *******

  *****

   ***

    *

 

 

 

版权声明:本文为[程序員大本營]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918041914749V.html