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.****.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行的结果为：
*********
*******
*****
***
*