嵌入式面试常见算法题
单链表链表操作和基本排序算法：
1.单链表及其基本操作：
#include
#include
#include
using namespace std;
//链表节点构造
template < class T>
class Node
{
public:
T data;
Node *Next;
Node()
{
this->Next = NULL;
}
Node(T data, Node*Next = NULL)
{
this->data = data;
this->Next = Next;
}
};
template < class T> class LinkList { //friend ostream& operator<<(ostream &out, LinkList &list);//操作符重载，输出单链表的所有元素
public: Node*head;//单链表成员为一个指向Node节点的指针
LinkList() {this->head = new Node();} //无参构造函数，创建一个指向Node的空的动态指针
LinkList(T value[], int n); //创建链表（利用数组进行创建）
~LinkList(); //析构函数
//头指针，指向单链表的头结点
Node*InsertNode(int i, T d);//指定位置插入节点
int GetLength(); //链表长度
T DeleteNode(int i); //删除指定位置节点,返回删除的元素
void DeleteAllNode(); //删除整个链表
T Get(int i);//按位查找，返回值 int Locate(T data);//按值查找
void Invert();//逆置 //void Merge(LinkList &a, LinkList &b); 合并有序单链表
};
template < class T> int LinkList::Locate(T data)
{
Node*p = this->head->Next;
int j = 1;
while ((p->data)!=(data)) //找到i的前一个节点
{
p = p->Next;//移动指针p
j++;
}
if(p)
return j;
return 0;
}
template < class T> T LinkList::Get(int n)
{
Node*p = this->head->Next;
int j = 1;
while (p && j < n)//找到i的前一个节点
{
p = p->Next;//移动指针p
j++;
}
if (!p) { cerr << "查找位置非法"; exit(1); }
return p->data;
}
template < class T> ostream& operator<<(ostream &out, LinkList &list)//遍历，输出
{
if (list.head == NULL)
{
cout << "链表为空！" << endl;
return out;
}
for (Node *p = list.head->Next; p != NULL; p = p->Next)
{
cout << p->data << " ";
}
return out;
}
template < class T> LinkList::LinkList(T value[], int n)//带头节点单链表，尾插法，接收一个T类型数组和一个int参数，把n个数组元素插入单链表尾部。
{
if (n <= 0)
{
cerr << "链表个数不合理，请重新设定！";
}
this->head = new Node();//创建一个指向Node的空的动态指针：head
Node *rear = this->head;//新建Node动态指针Temp接收head赋值, 指针rear用于指向当前单链表最后一个节点
for (int i = 0; i < n; i++)
{
rear->Next = new Node();//rear指向对象 的Next成员 接收新建的Node空动态指针赋值
rear->Next->data = value[i];//rear指针指向对象 的Next成员 指向的对象 的data成员 接收value[i]的赋值
rear = rear->Next;//将rear的Next成员赋值给rear,即rear由原先的节点指向新建的节点，开始进行下一次循环
}
rear->Next = NULL;//单链表建立完毕，将最后一个节点指针域置空
}
/* template < class T> LinkList::LinkList(T value[], int n)//头插法尝试，相应函数也需改变
{
if (n <= 0)
{
cout << "链表个数不合理，请重新设定！" << endl;
}
this->head = new Node();
Node *rear = this->head;
for (int i = 0; i < n; i++) { Node *h = new Node();
h->data = value[i];
h->Next = rear;
rear = h;
}
rear->Next = NULL;
}
*/
template < class T> Node* LinkList::InsertNode(int i, T d)//后插法，接收插入位置和数据两个参数
{
Node*p = this->head;
int j = 0;
while (p && j < i - 1)//找到i的前一个节点
{
p = p->Next;//移动指针p
j++;
}
if (!p)
{
cerr<<"插入位置非法";
exit(1);
}
Node*s = new Node();//建立新节点
s->data = d;
s->Next = p->Next;//新节点的Next成员接收节点P的Next成员赋值
p->Next = s;//将节点p的Next成员指向s;
return 0; }
template
int LinkList::GetLength()
{
Node*p = new Node();
p = this->head;
int num = 0;
while (p->Next != NULL)//创建p节点，然后移动p节点，p节点Next成员非空则递加num
{
num ++;
p = p->Next;
}
return num;
}
template
T LinkList::DeleteNode(int i)//接收位置参数i
{
Node*p = new Node();
p = this->head;
int j = 0; T e;
while (p && j < i - 1)//找到i前一个节点
{
p = p->Next;
j++;
}
if (!p || !p->Next )
{
throw out_of_range("该位置指针为空或者输入位置不合法！");
}
Node*s = p->Next;//新建节点接收p后一节点赋值
e = s ->data;//提取data
p->Next = s->Next;//p节点Next成员接收s节点Next成员赋值
delete(s);//删除s
return e;
}
template
void LinkList::DeleteAllNode()
{
while (this->head)
{
auto a = head;//记录地址
head = head->Next;//移到下一个节点
delete a;//释放上一个节点内存
}
}
templateLinkList::~LinkList()
{
while (this->head)
{
auto a = head;
head = head->Next;
delete a;
}
}
//单链表其他操作：
//逆置 template void LinkList::Invert()
{
auto p = this->head->Next;
head->Next = NULL;//将逆置的单链表初始化为空表
while (p!=NULL)//遍历节点
{
auto q = p;
p = p->Next;//移动节点
q->Next = head->Next;//q=NULL,后面的头插，原第一个节点成为尾节点
head->Next = q;
}
}
//合并有序单链表,对于无序链表合并可先进行排序操作 template
void Merge(LinkList &L1, LinkList &L2)
{
auto p1 = L1.head->Next, p2 = L2.head->Next, p3 = L1.head;
while ((p1 != NULL) && (p2 != NULL)) { if ((p1->data) < (p2->data)) { p3->Next = p1; p1 = p1->Next; p3 = p3->Next; } else //包含等于情况，直接上p2 { p3->Next = p2; p2 = p2->Next; p3 = p3->Next; } }
if (p1 != NULL) p3->Next = p1; if (p2 != NULL) p3->Next = p2; delete L2.head; L2.head = NULL; } 2.常见排序算法： 排序的稳定性：假如排序列中有相同的量，排序完成后他们的顺序不变是稳定了，改变则不稳定。有些场合对稳定性有要求。 #include
using namespace std;
////////////////////直接插入排序，稳定排序 void InsertSort(int r[], int n) //接收一个数组和排序范围 { int i, j; for (i = 1; i < n; i++) { auto temp = r[i]; for (j = i - 1; j >= 0 && temp < r[j]; j--) { r[j + 1] = r[j]; } r[j + 1] = temp; } } void InsertSorts(int r[], int n) //直接插入排序，接收一个向量，和排序范围，设置哨兵 { int i, j; for (i = 2; i <= n; i++) { r[0] = r[i]; for (j = i - 1; r[0] < r[j]; j--) { r[j + 1] = r[j]; } r[j + 1] = r[0]; } } //////////////////折半插入排序，稳定 void BinInsertSort(int r[], int n) //接收一个数组和排序范围 { int i, j; for (i = 1; i < n; i++) { auto temp = r[i]; int mid, low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (temp < r[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= low; j--) { r[j + 1] = r[j]; } r[low] = temp; } } //////希尔排序，不稳定排序 void ShellSort(int r[], int n) //希尔排序 { int d, i, temp, j; for (d = n / 2; d >= 1; d = d / 2) { for (i = d; i < n; i++) { temp = r[i]; for (j = i - d; j >= 0 && temp < r[j]; j = j - d) { r[j + d] = r[j]; } r[j + d] = temp; } } } ///////////////////////////////////////////冒泡排序，不稳定排序 void BubbleSort(int r[], int n) { for (int i = 1; i < n; i++) for (int j = 0; j < n - 1; j++) if (r[j] > r[j + 1]) { auto temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; } } ///////////////////////////////////////////冒泡排序改进，当没有进行交换操作即结束排序 void GBubbleSort(int r[], int n) { bool exchange = true; while (exchange) { exchange = false; int i = 1; for (int j = 0; j < n - 1; j++) //由n-1来控制 已经排过的最大值不用再排 if (r[j] > r[j + 1]) { auto temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; exchange = true; } ++i; } } ////////////////////////////简单选择排序，不稳定 void SelectSort(int r[], int n) { int i, k, j; for (i = 0; i < n - 1; i++) { int k = i; for (j = i + 1; j < n; j++) // k的后一个小于k,让k指向其后一个 if (r[j] < r[k]) k = j; if (k != i) //如果k发生了移动，交换i和k指向的值，即把最小值移动到第一个，循环完成排序 { auto temp = r[i]; r[i] = r[k]; r[k] = temp; } } }
//////////////////////////////快速排序，不稳定排序
int Partition(int r[], int low, int high) //接收排序数组和排序范围 { auto pivot = r[low]; while (low < high) // low=high时完成一次遍历，结束循环 { while (low < high && r[high] >= pivot) //当high大于基准时前移，当指向的值小于基准时结束循环，将其赋值到low high--; r[low] = r[high]; while (low < high && r[low] <= pivot) //当low小于基准时后移，当指向值大于基准时结束循环，将其赋值到high，完成交换赋值 low++; r[high] = r[low]; } r[low] = pivot; return low; //返回基准所在位置 } void QuickSort(int r[], int i, int j) //递归完成快速排序 { if (i < j) { auto pivot = Partition(r, i, j); QuickSort(r, i, pivot - 1); //排序基准前半部分 QuickSort(r, pivot + 1, j); //排序基准后半部分 } } //////////////////堆排序，不稳定，大根堆 void AdjustDown(int r[], int k, int len) { r[0] = r[k]; for (int i = 2 * k; i <= len; i *= 2) { if (i < len && r[i] < r[i + 1]) i++; if (r[0] = r[i]) break; else { r[k] = r[i]; k = i; } } } void BuildMaxHeap(int r[], int len) //递归遍历整个完全二叉树 { for (int i = len / 2; i > 0; i--) AdjustDown(r, i, len); } void HeapSort(int r[], int len) //输出堆顶元素 { int i; BuildMaxHeap(r, len); for (i = len; i > 1; i--) swap(r[i], r[1]); AdjustDown(r, 1, i - 1); } /////////////////////////二路归并排序 void Merge(int r[], int r1[], int s, int m, int t) //两个相邻序列为r[s]`r[m],r[m+1]`r[t] { int i = s, j = m + 1, k = s; while (i <= m && j <= t) if (r[i] <= r[j]) r1[k++] = r[i++]; //取r[i]和r[j]中的较小者放入r1[k] else r1[k++] = r[j++]; if (i <= m) while (i <= m) r1[k++] = r[i++]; //若第一个子序列没有处理完，则进行收尾处理 else while (j <= t) r1[k++] = r[j++]; //若第二个子序列没有处理完，则进行收尾处理 } void MergeSort(int r[], int r1[], int s, int t) { if (s == t) r1[s] = r[s]; else { int m = (s + t) / 2; MergeSort(r, r1, s, m); //归并排序前半部分 MergeSort(r, r1, m + 1, t); //归并排序后半部分 Merge(r1, r, s, m, t); //将两个已排序的子序列归并 } }
int main() { std::cout << "Hello World!\n";
int a[8] = {8, 2, 43, 3, 5, 0, 9, 6};
// InsertSort(a, 8); // InsertSorts(a, 8); // BinInsertSort(a, 8); // ShellSort(a, 8); // BubbleSort(a, 8); // GBubbleSort(a, 8); // SelectSort(a, 8); QuickSort(a, 0, 8 - 1); // low与high为数组下标
for (int m = 0; m < size(a); m++) cout << a[m] << " "; }
template < class T> class LinkList { //friend ostream& operator<<(ostream &out, LinkList
public: Node
LinkList() {this->head = new Node
T Get(int i);//按位查找，返回值 int Locate(T data);//按值查找
void Invert();//逆置 //void Merge(LinkList &a, LinkList &b); 合并有序单链表
};
template < class T> int LinkList
template < class T> T LinkList
template < class T> ostream& operator<<(ostream &out, LinkList
template < class T> LinkList
/* template < class T> LinkList
for (int i = 0; i < n; i++) { Node
template < class T> Node
return 0; }
template
template
Node
template
template
//单链表其他操作：
//逆置 template
//合并有序单链表,对于无序链表合并可先进行排序操作 template
while ((p1 != NULL) && (p2 != NULL)) { if ((p1->data) < (p2->data)) { p3->Next = p1; p1 = p1->Next; p3 = p3->Next; } else //包含等于情况，直接上p2 { p3->Next = p2; p2 = p2->Next; p3 = p3->Next; } }
if (p1 != NULL) p3->Next = p1; if (p2 != NULL) p3->Next = p2; delete L2.head; L2.head = NULL; } 2.常见排序算法： 排序的稳定性：假如排序列中有相同的量，排序完成后他们的顺序不变是稳定了，改变则不稳定。有些场合对稳定性有要求。 #include
////////////////////直接插入排序，稳定排序 void InsertSort(int r[], int n) //接收一个数组和排序范围 { int i, j; for (i = 1; i < n; i++) { auto temp = r[i]; for (j = i - 1; j >= 0 && temp < r[j]; j--) { r[j + 1] = r[j]; } r[j + 1] = temp; } } void InsertSorts(int r[], int n) //直接插入排序，接收一个向量，和排序范围，设置哨兵 { int i, j; for (i = 2; i <= n; i++) { r[0] = r[i]; for (j = i - 1; r[0] < r[j]; j--) { r[j + 1] = r[j]; } r[j + 1] = r[0]; } } //////////////////折半插入排序，稳定 void BinInsertSort(int r[], int n) //接收一个数组和排序范围 { int i, j; for (i = 1; i < n; i++) { auto temp = r[i]; int mid, low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (temp < r[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= low; j--) { r[j + 1] = r[j]; } r[low] = temp; } } //////希尔排序，不稳定排序 void ShellSort(int r[], int n) //希尔排序 { int d, i, temp, j; for (d = n / 2; d >= 1; d = d / 2) { for (i = d; i < n; i++) { temp = r[i]; for (j = i - d; j >= 0 && temp < r[j]; j = j - d) { r[j + d] = r[j]; } r[j + d] = temp; } } } ///////////////////////////////////////////冒泡排序，不稳定排序 void BubbleSort(int r[], int n) { for (int i = 1; i < n; i++) for (int j = 0; j < n - 1; j++) if (r[j] > r[j + 1]) { auto temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; } } ///////////////////////////////////////////冒泡排序改进，当没有进行交换操作即结束排序 void GBubbleSort(int r[], int n) { bool exchange = true; while (exchange) { exchange = false; int i = 1; for (int j = 0; j < n - 1; j++) //由n-1来控制 已经排过的最大值不用再排 if (r[j] > r[j + 1]) { auto temp = r[j]; r[j] = r[j + 1]; r[j + 1] = temp; exchange = true; } ++i; } } ////////////////////////////简单选择排序，不稳定 void SelectSort(int r[], int n) { int i, k, j; for (i = 0; i < n - 1; i++) { int k = i; for (j = i + 1; j < n; j++) // k的后一个小于k,让k指向其后一个 if (r[j] < r[k]) k = j; if (k != i) //如果k发生了移动，交换i和k指向的值，即把最小值移动到第一个，循环完成排序 { auto temp = r[i]; r[i] = r[k]; r[k] = temp; } } }
//////////////////////////////快速排序，不稳定排序
int Partition(int r[], int low, int high) //接收排序数组和排序范围 { auto pivot = r[low]; while (low < high) // low=high时完成一次遍历，结束循环 { while (low < high && r[high] >= pivot) //当high大于基准时前移，当指向的值小于基准时结束循环，将其赋值到low high--; r[low] = r[high]; while (low < high && r[low] <= pivot) //当low小于基准时后移，当指向值大于基准时结束循环，将其赋值到high，完成交换赋值 low++; r[high] = r[low]; } r[low] = pivot; return low; //返回基准所在位置 } void QuickSort(int r[], int i, int j) //递归完成快速排序 { if (i < j) { auto pivot = Partition(r, i, j); QuickSort(r, i, pivot - 1); //排序基准前半部分 QuickSort(r, pivot + 1, j); //排序基准后半部分 } } //////////////////堆排序，不稳定，大根堆 void AdjustDown(int r[], int k, int len) { r[0] = r[k]; for (int i = 2 * k; i <= len; i *= 2) { if (i < len && r[i] < r[i + 1]) i++; if (r[0] = r[i]) break; else { r[k] = r[i]; k = i; } } } void BuildMaxHeap(int r[], int len) //递归遍历整个完全二叉树 { for (int i = len / 2; i > 0; i--) AdjustDown(r, i, len); } void HeapSort(int r[], int len) //输出堆顶元素 { int i; BuildMaxHeap(r, len); for (i = len; i > 1; i--) swap(r[i], r[1]); AdjustDown(r, 1, i - 1); } /////////////////////////二路归并排序 void Merge(int r[], int r1[], int s, int m, int t) //两个相邻序列为r[s]`r[m],r[m+1]`r[t] { int i = s, j = m + 1, k = s; while (i <= m && j <= t) if (r[i] <= r[j]) r1[k++] = r[i++]; //取r[i]和r[j]中的较小者放入r1[k] else r1[k++] = r[j++]; if (i <= m) while (i <= m) r1[k++] = r[i++]; //若第一个子序列没有处理完，则进行收尾处理 else while (j <= t) r1[k++] = r[j++]; //若第二个子序列没有处理完，则进行收尾处理 } void MergeSort(int r[], int r1[], int s, int t) { if (s == t) r1[s] = r[s]; else { int m = (s + t) / 2; MergeSort(r, r1, s, m); //归并排序前半部分 MergeSort(r, r1, m + 1, t); //归并排序后半部分 Merge(r1, r, s, m, t); //将两个已排序的子序列归并 } }
int main() { std::cout << "Hello World!\n";
int a[8] = {8, 2, 43, 3, 5, 0, 9, 6};
// InsertSort(a, 8); // InsertSorts(a, 8); // BinInsertSort(a, 8); // ShellSort(a, 8); // BubbleSort(a, 8); // GBubbleSort(a, 8); // SelectSort(a, 8); QuickSort(a, 0, 8 - 1); // low与high为数组下标
for (int m = 0; m < size(a); m++) cout << a[m] << " "; }