1. 找出数组中仅出现了1|2|3次的数
(1)找出数组中唯一出现1次的数，其他数都出现了两次：
所有数的异或和。
(2)找出数组中唯一出现1次的数，其他数都出现了三次：
累加所有数对应的二进制每一位的1的个数，
并对每一位%3的结果即为解。如下：
int singleNumber(int A[], int n) {
int bit_time[32] = {0};
int i = 0;
int j = 0;
int result = 0;
for(i = 0; i < 32; i++){
for(j = 0; j < n; j++){
bit_time[i] += (A[j] >> i) & 0x01;
}
result |= (bit_time[i] % 3) << i;
}
return result;
}
但这种方法复杂度为O(n log n)。另解如下，
同样从位运算的角度来看，我希望一个数用来表示出现一次的位，
也就是说这个数的为1的位就表示这个位上面的数出现过了一次，
比如0x10001，就表示bit[0]和bit[4]就是出现过了一次的位。
然后再用一个数表示出现过了两次的位，再用一个数表示出现过了3次的位。
只要这个位出现过了3次，我就把这个位拿清除掉，
这样剩余的最后出现过一次的位的这个数就是我们要找的数了。
int singleNumber(int A[], int n) {
int ones = 0;
int twos = 0;
int threes = 0;
int i = 0;
for(i = 0; i < n; i++){
twos |= ones & A[i];
ones ^= A[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
(3)找数组中两个出现1次的数，其他都出现了两次：
令第一个数为x,第二个数为y，易知，全部数的异或和为x^y=S，
对于S的二进制上的任意一位1(一般取最低位或者最高位)，
我们可以把数组分成两个部分，使得x与y分别在不同的两个子数组中。
2. 链表
(1)单顺序链表：最简单的数据结构，
开辟一块连续的存储空间，用数组实现。
#pragma once
#ifndef SQLIST_H
#define SQLIST_H
#define MaxSize 50
typedef int DataType;
struct SqList //顺序表相当于一个数组，这个结构体就已经表示了整个顺序表
{
DataType data[MaxSize];
int length; //表示顺序表实际长度
};//顺序表类型定义
void InitSqList(SqList * &L);
void DestroySqList(SqList * L); //释放顺序表
int isSqListEmpty(SqList * L); //判断是否为空表
int SqListLength(SqList * L); //返回顺序表的实际长度
DataType SqListGetElem(SqList * L, int i); //获取顺序表中第i个元素值
int GetElemLocate(SqList * L, const DataType e); //在顺序表中查找元素e,并返回在顺序表哪个位置
int SqListInsert(SqList *&L, int i, DataType e); //在第i个位置插入元素
DataType SqListElem(SqList* L, int i); //删除第i个位置元素,并返回该元素的值
#endif
#include<iostream>
#include"SqList.h"
using namespace std;
void InitSqList(SqList * &L){//初始化顺序表
L = (SqList*)malloc(sizeof(SqList)); // 开辟内存
L->length = 0;
}
void DestroySqList(SqList * L){ //释放顺序表
if (L == NULL) {
return;
}
free(L);
}
int isSqListEmpty(SqList * L){ //判断是否为空表
if (L == NULL) {
return 0;
}
return (L->length == 0);
}
int SqListLength(SqList * L){ //返回顺序表的实际长度
if (L == NULL) {
cout << "顺序表分配内存失败" << endl;
return 0;
}
return L->length;
}
DataType SqListGetElem(SqList * L,int i){ //获取顺序表中第i个元素值
if (L == NULL) {
cout << "No Data in SqList" << endl;
return 0;
}
return L->data[i - 1];
}
int GetElemLocate(SqList * L, const DataType e){
//在顺序表中查找元素e,并返回在顺序表哪个位置
if( L == NULL) {
cout << "Empty SqList" << endl;
return 0;
}
int i = 0;
while(i < L->length && L->data[i] != e){
i++;
}
if (i > L->length){
return 0;
}
return i + 1;
}
int SqListInsert(SqList *&L, int i, DataType e){ //在第i个位置插入元素
if(L == NULL){
cout << "error" << endl;
return 0;
}
if (i > L->length + 1 || i < 1){
cout << "error" << endl;
return 0;
}
for (int j = L->length; j>=i - 1; j--){ //将i之后的元素后移，腾出空间
L->data[j] = L->data[j - 1];
}
L->data[i] = e;
L->length++;
return 1;
}
DataType SqListElem(SqList* L, int i){
//删除第i个位置元素,并返回该元素的值
if (L == NULL) {
cout << "error" << endl;
return 0;
}
if (i < 0 || i > L->length){
cout << "error" << endl;
return 0;
}
DataType e = L->data[i - 1];
for (int j = i; j < L->length;j++){
L->data[j] = L->data[j + 1];
}
L->length--;
return e;
}
(2)单链式链表
#pragma once
#ifndef LINKLIST_H
#define LINKLIST_H
typedef int DataType;
//单链表：单链表是一个节点一个节点构成，
//先定义一个节点，节点为一个结构体，当这些节点连在一起，
// 链表为指向头结点的结构体型指针，即是LinkList型指针
typedef struct LNode{ //定义的是节点的类型
DataType data;
struct LNode *next; //指向后继节点
}LinkList;
void InitLinkList(LinkList * &L); //初始化链表
void DestroyLinkList(LinkList * L); //销毁单链表
int isEmptyLinkList(LinkList * L); //判断链表是否为空
int LinkListLength(LinkList * L); //求链表长度
void DisplayLinkList(LinkList * L); //输出链表元素
DataType LinkListGetElem(LinkList * L,int i);//获取第i个位置的元素值
int LinkListLocate(LinkList * L,DataType e); //元素e在链表的位置
int LinkListInsert(LinkList * &L,int i,DataType e);//在第i处插入元素e
DataType LinkListDelete(LinkList * &L,int i); //删除链表第i处的元素
#endif
#include<iostream>
#include"LinkList.h"
using namespace std;
void InitLinkList(LinkList * &L) {//初始化链表
L = (LinkList*)malloc(sizeof(LinkList)); //创建头结点
L->next = NULL;
}
void DestroyLinkList(LinkList * L){ //销毁单链表
LinkList *p = L, *q = p->next;//创建辅助节点指针
if(L == NULL) {
return;
}
while (q != NULL){ //销毁一个链表，必须一个节点一个节点的销毁
free(p);
p = q;
q = p->next;
}
free(p);
}
int isEmptyLinkList(LinkList * L){ //判断链表是否为空
return (L->next == NULL);// 1：空；0：非空
}
int LinkListLength(LinkList * L){ //求链表长度，链表的长度必须一个节点一个节点的遍历
LinkList *p = L;
if (L == NULL) {
return 0;
}
int i = 0;
while (p->next != NULL) {
i++;
p = p->next;
}
return i;
}
void DisplayLinkList(LinkList * L){//输出链表元素
LinkList * p = L->next; //此处一点要指向next,这样是第一个节点，跳过了头结点
while (p != NULL){
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
DataType LinkListGetElem(LinkList * L, int i){//获取第i个位置的元素值
LinkList *p = L;
if (L == NULL || i < 0){
return 0;
}
int j = 0;
while (j < i && p->next != NULL){
j++; p = p->next;
}
if (p == NULL) {
return 0;
}else{
return p->data;
}
}
int LinkListLocate(LinkList * L, DataType e) {//元素e在链表的位置
LinkList *p = L;
if (L == NULL) {
return 0;
}
int j = 0;
while (p->next != NULL && p->data == e){
j++;
}
return j+1;
}
int LinkListInsert(LinkList * &L, int i, DataType e){//在第i处插入元素e
LinkList *p = L,*s;
int j = 0;
if (L == NULL ) {
return 0;
}
while (j < i-1 && p != NULL){ //先将指针移到该处
j++;
p = p->next;
}
s = (LinkList*)malloc(sizeof(LinkList)); //添加一个节点，需开辟一个新的内存
s->data = e;
s->next = p->next; //先将下一地址给新节点
p->next = s; //将原来的指针指向新节点
return 1;
}
DataType LinkListDelete(LinkList * &L, int i) {//删除链表第i处的元素
LinkList *p = L,*q; //p用来存储临时节点
DataType e; //用来存被删除点的元素
int j = 0;
while (j < i - 1 && p != NULL){ //将p指向第i-1节点
j++;
p = p->next;
}
if (p == NULL) {
return 0;
}else{
q = p->next; //q指向第i个节点*p
e = q->data;
//从链表中删除p节点，即是p->next = p->next->next,将第i个节点信息提取出来
p->next = q->next;
free(q); //释放p点内存
return e;
}
}
(3)双链表
#pragma once
#ifndef DLINKLIST_H
#define DLINKLIST_H
typedef int DataType;
typedef struct DLNode{
DataType Elem;
DLNode *prior;
DLNode *next;
}DLinkList;
void DLinkListInit(DLinkList *&L);//初始化双链表
void DLinkListDestroy(DLinkList * L); //双链表销毁
bool isDLinkListEmpty(DLinkList * L);//判断链表是否为空
int DLinkListLength(DLinkList * L); //求双链表的长度
void DLinkListDisplay(DLinkList * L); //输出双链表
DataType DLinkListGetElem(DLinkList * L, int i); //获取第i个位置的元素
bool DLinkListInsert(DLinkList * &L, int i, DataType e);//在第i个位置插入元素e
DataType DLinkListDelete(DLinkList * &L, int i);//删除第i个位置上的值，并返回其值
#endif
#include<iostream>
#include"DLinkList.h"
using namespace std;
void DLinkListInit(DLinkList *&L){//初始化双链表
L = (DLinkList *)malloc(sizeof(DLinkList)); //创建头结点
L->prior = L->next = NULL;
}
void DLinkListDestroy(DLinkList * L){ //双链表销毁
if (L == NULL) {
return;
}
DLinkList *p = L, *q = p->next;//定义两个节点，第一个表示当前节点，第二个表示第二个节点
while (q != NULL) //当第二个节点指向null，说明p是最后一个节点，如果不是，则
{ //释放掉p，q就为第一个节点，将q赋给p，p->给q，这样迭代
free(p);
p = q;
q = p->next;
}
free(p);
}
bool isDLinkListEmpty(DLinkList * L){//判断链表是否为空
return L->next == NULL;
}
int DLinkListLength(DLinkList * L){ //求双链表的长度
DLinkList *p = L;
if (L == NULL) {
return 0;
}
int i = 0;
while (p->next != NULL){
i++;
p = p->next;
}
return i;
}
void DLinkListDisplay(DLinkList * L) {//输出双链表
DLinkList *p = L->next; //跳过头结点，指向第一个节点
while (p != NULL){
cout << p->Elem << " ";
p = p->next;
}
}
DataType DLinkListGetElem(DLinkList * L, int i) {//获取第i个位置的元素
DLinkList *p = L;//指向头结点
if (L == NULL) {
cout << "Function DLinkListGetElem" << "链表为空表" << endl;
return 0;
}
int j = 0;
while (p != NULL && j < i){ //将指针指向第i个位置处
j++;
p = p->next;
}
if (p == NULL) {
return 0;
}else{
return p->Elem;
}
}
bool DLinkListInsert(DLinkList * &L, int i, DataType e){//在第i个位置插入元素e
int j = 0;
DLinkList *p = L, *s;//其中s节点是表示插入的那个节点，所以要给它开辟内存
while (p != NULL && j < i - 1){ //插入节点前，先找到第i-1个节点
j++;
p = p->next;
}
if( p == NULL) {
return 0;
}else{
s = (DLinkList *)malloc(sizeof(DLinkList));
s->Elem = e;
s->next = p->next;//插入点后继的指向
if (p->next != NULL) {
p->next->prior = s; //插入点的后继的前驱指向
}
s->prior = p; //插入点前驱的前驱指向
p->next = s; //插入点后前驱的后继指向
}
}
DataType DLinkListDelete(DLinkList * &L, int i){//删除第i个位置上的值，并返回其值
DLinkList *p = L, *s;
int j = 0;
if (L == NULL) {
cout << "Function DLinkListDelete" << "删除出错" << endl;
return 0;
}
while (j < i - 1 && p != NULL){
j++;
p = p->next;
}
if (p == NULL) {
return 0;
}else{
s = p->next;
if (s == NULL){
return 0;
}
DataType e = p->Elem;
p->next = s->next;
if (p->next != NULL) {
p->next->prior = p;
}
free(s);
return e;
}
3. 队列
(1)顺序队列
#pragma once
#ifndef SQQUEUE_H
#define SQQUEUE_H
#define MaxSize 50
typedef int DataType;
typedef struct SQueue {//创建一个结构体，里面包含数组和队头和队尾
DataType data[MaxSize];
int front, rear; //front表示队头，rear表示队尾，入队头不动尾动，出队尾不动头动
}SqQueue;
void SqQueueInit(SqQueue *&Q); //队列初始化
void SqQueueClear(SqQueue *$Q); //清空队列
bool isSqQueueEmpty(SqQueue *Q); //判断队列长度
int SqQueueLength(SqQueue *Q); //求队列的长度
void SqQueueDisplay(SqQueue *Q); //输出队列
void EnSqQueue(SqQueue *& Q,DataType e); //进队
DataType DeSqQueue(SqQueue *& Q); //出队
#endif
#include<iostream>
#include"SqQueue.h"
using namespace std;
void SqQueueInit(SqQueue *&Q) {//队列初始化
Q = (SqQueue *)malloc(sizeof(Q));
Q->front = Q->rear = 0;
}
void SqQueueClear(SqQueue *&Q) {//清空队列
free(Q); //对于顺序栈，直接释放内存即可
}
bool isSqQueueEmpty(SqQueue *Q) {//判断队列长度
return (Q->front == Q->rear);
}
int SqQueueLength(SqQueue *Q) {//求队列的长度
return Q->rear - Q->front; //此处有问题
}
void EnSqQueue(SqQueue *& Q,DataType e) {//进队
if (Q == NULL) {
cout << "分配内存失败！" << endl;
return;
}
if (Q->rear >= MaxSize) {//入队前进行队满判断
cout << "The Queue is Full!" << endl;
return;
}
Q->rear++;
Q->data[Q->rear] = e;
}
DataType DeSqQueue(SqQueue *& Q) {//出栈
if (Q == NULL) {
return 0;
}
if (Q->front == Q->rear) {//出队前进行空队判断
cout << "This is an Empty Queue!" << endl;
return 0;
}
Q->front--;
return Q->data[Q->front];
}
void SqQueueDisplay(SqQueue *Q) {//输出队列
if (Q == NULL) {
return;
}
if (Q->front == Q->rear) {
return;
}
int i = Q->front + 1;
while (i <= Q->rear) {
cout << Q->data[i] << " ";
i++;
}
}
(2)链式队列
#pragma once
#ifndef LINKQUEUE_H
#define LINKQUEUE_H
typedef int DataType;
/* 队列的链式存储中，由于需要指针分别指向
队头和队尾，因此造成了链队节点与数据节点不同
链队节点：包含两个指向队头队尾的指针
数据节点：一个指向下一个数据节点的指针和数据
*/
//定义数据节点结构体
typedef struct qnode{
DataType Elem;
struct qnode *next;
}QDataNode;
//定义链队节点结构体
typedef struct {
QDataNode *front;
QDataNode *rear;
}LinkQueue;
void LinkQueueInit(LinkQueue *&LQ); //初始化链队
void LinkQueueClear(LinkQueue *&LQ); //清空链队
bool isLinkQueueEmpty(LinkQueue *LQ); //判断链队是否为空
int LinkQueueLength(LinkQueue *LQ); //求链队长度
bool EnLinkQueue(LinkQueue *&LQ,DataType e); //进队
DataType DeLinkQueue(LinkQueue *&LQ); //出队
#endif
#include<iostream>
#include"LinkQueue.h"
using namespace std;
void LinkQueueInit(LinkQueue *&LQ) {//初始化链队
LQ = (LinkQueue*)malloc(sizeof(LQ));
LQ->front = LQ->rear = NULL;
}
void LinkQueueClear(LinkQueue *&LQ) {//清空链队,清空队列第一步：销毁数据节点
// 第二步：销毁链队节点
QDataNode *p = LQ->front, *r;
if (p != NULL) {
r = p->next;
while (r != NULL){
free(p);
p = r;
r = p->next;
}
}
free(LQ);
}
bool isLinkQueueEmpty(LinkQueue *LQ) {//判断链队是否为空
return LQ->rear == NULL; //1：空；0：非空
}
int LinkQueueLength(LinkQueue *LQ) {//求链队长度
QDataNode *p = LQ->front;
int i = 0;
while (p != NULL){
i++;
p = p->next;
}
return i;
}
bool EnLinkQueue(LinkQueue *&LQ, DataType e) {//进队
QDataNode *p;
if (LQ == NULL){
return 0;
}
p = (QDataNode*)malloc(sizeof(QDataNode));
p->Elem = e;
p->next = NULL; //尾插法
if (LQ->front == NULL){//如果队列中还没有数据时
LQ->front = LQ->rear = p; //p为队头也为队尾
}else{
LQ->rear->next = p;
LQ->rear = p;
}
}
DataType DeLinkQueue(LinkQueue *&LQ) {//出队
QDataNode *p;
DataType e;
if (LQ->rear == NULL){
cout << "This is an Empty queue!" << endl;
return 0;
}
if (LQ->front == LQ->rear){
p = LQ->front;
LQ->rear = LQ->front = NULL;
}else{
p = LQ->front;
LQ->front = p->next;
e = p->Elem;
}
free(p);
return e;
}
4. 栈
(1)顺序栈
#pragma once
#ifndef SQSTACK_H
#define SQSTACK_H
#define MaxSize 50//根据实际情况设置大小
typedef int DataType;
//顺序栈也是一种特殊的顺序表，创建一个
//结构体，里面包含一个数组，存储数据
//顺序栈其实是将数组进行结构体包装
typedef struct Stack{
DataType Elem[MaxSize];
int top; //栈指针
}SqStack;
void SqStackInit(SqStack *&S); //初始化栈
void SqStackClear(SqStack *&S); //清空栈
int SqStackLength(SqStack *S); //求栈的长度
bool isSqStackEmpty(SqStack *S); //判断栈是否为空
void SqStackDisplay(SqStack *S); //输出栈元素
bool SqStackPush(SqStack *&S, DataType e);//元素e进栈
DataType SqStackPop(SqStack *&S);//出栈一个元素
DataType SqStackGetPop(SqStack *S);//取栈顶元素
#endif
#include<iostream>
#include"SqStack.h"
using namespace std;
void SqStackInit(SqStack *&S) {//初始化栈
S = (SqStack*)malloc(sizeof(SqStack)); //开辟内存,创建栈
S->top = -1;
}
void SqStackClear(SqStack *&S) {//清空栈
free(S);
}
int SqStackLength(SqStack *S) {//求栈的长度
return S->top + 1;
}
bool isSqStackEmpty(SqStack *S) {//判断栈是否为空
return (S->top == -1);
}
void SqStackDisplay(SqStack *S){ //输出栈元素
for (int i = S->top; i > -1; i--){
cout << S->Elem[i] << " ";
}
}
bool SqStackPush(SqStack *&S, DataType e)//元素e进栈
if ( S->top == MaxSize - 1){
cout << "The Stack Full!" << endl; //满栈判断
return 0;
}
S->top++;
S->Elem[S->top] = e;
return 1;
}
DataType SqStackPop(SqStack *&S){//出栈一个元素
DataType e;
if(S->top== -1){ //空栈判断
cout << "The Stack is Empty!" << endl;
return 0;
}
e = S->Elem[S->top];//出栈元素存储
S->top--;
return e;
}
DataType SqStackGetPop(SqStack *S){//取栈顶元素
if (S->top == -1){ //空栈判断
cout << "The Stack is Empty" << endl;
return 0;
}
return S->Elem[S->top];
}
(2)链式栈
#pragma once
#ifndef LINKSTACK_H
#define LINKSTACK_H
typedef int DataType;
typedef struct LinkNode {//链式栈的结点定义和链表的结点定义是一样的
DataType Elem; //数据域
struct LinkNode *next; //指针域
}LinkStack;
void LinkStackInit(LinkStack *& S); //初始化列表
void LinkStackClear(LinkStack*&S); //清空栈
int LinkStackLength(LinkStack * S); //求链表的长度
bool isLinkStackEmpty(LinkStack *S); //判断链表是否为空
bool LinkStackPush(LinkStack *S, DataType e);//元素e进栈
DataType LinkStackPop(LinkStack *S); //出栈
DataType LinkStackGetPop(LinkStack *S); //输出栈顶元素
void LinkStackDisplay(LinkStack *S); //从上到下输出栈所有元素
#endif
#include<iostream>
#include"LinkStack.h"
using namespace std;
void LinkStackInit(LinkStack *& S) {//初始化列表
S = (LinkStack *)malloc(sizeof(LinkStack)); //分配内存
S->next = NULL;
}
void LinkStackClear(LinkStack*&S) {//清空栈
LinkStack *p = S,*q = S->next;
if (S == NULL) {
return;
}
while (p != NULL){ //注意：与书中有点不同，定义两个节点，一个当前节点，一个下一个节点
free(p);
p = q;
q = p->next;
}
}
int LinkStackLength(LinkStack * S){//求链表的长度
int i = 0;
LinkStack *p = S->next; //跳过头结点
while (p != NULL){
i++;
p = p->next;
}
return i;
}
bool isLinkStackEmpty(LinkStack *S){//判断链表是否为空
return S->next == NULL; //1：空；0：非空
}
bool LinkStackPush(LinkStack *{
LinkStack *p;
p = (LinkStack*)malloc(sizeof(LinkStack)); //创建结点
if (p == NULL) {
return 0;
}
p->Elem = e; //将元素赋值
p->next = S->next; //将新建结点的p->next指向原来的栈顶元素
S->next = p; //将现在栈的起始点指向新建结点
return 1;
}
DataType LinkStackPop(LinkStack *S){//出栈
LinkStack *p;
DataType e;
if (S->next == NULL){
cout << "The Stack is Empty!" << endl;
return 0;
}
p = S->next; //跳过头结点
e = p->Elem;
S->next = p->next;
return e;
}
DataType LinkStackGetPop(LinkStack *S){//输出栈顶元素
if (S->next == NULL){
cout << "The Stack is Empty!" << endl;
return 0;
}
return S->next->Elem; //头结点
}
void LinkStackDisplay(LinkStack *S){//从上到下输出栈所有元素
LinkStack *p = S->next;
while(p != NULL){
cout << p->Elem << " ";
p = p->next;
}
cout << endl;
}
5. 二叉树
#pragma once
#ifndef LINKBTREE_H
#define LINKBTREE_H
#define MaxSize 100 //树的深度
typedef char DataType;
typedef struct BTNode {//定义一个二叉树节点
DataType Elem;
BTNode *Lchild;
BTNode *Rchild;
}LinkBTree;
void LinkBTreeCreate(LinkBTree *& BT, char *str);//有str创建二叉链
LinkBTree* LinkBTreeFindNode(LinkBTree * BT, DataType e); //返回e的指针
LinkBTree *LinkBTreeLchild(LinkBTree *p);//返回*p节点的左孩子节点指针
LinkBTree* LinkBTreeRight(LinkBTree *p);//返回*p节点的右孩子节点指针
int LinkBTreeDepth(LinkBTree *BT);//求二叉链的深度
void LinkBTreeDisplay(LinkBTree * BT);//以括号法输出二叉链
int LinkBTreeWidth(LinkBTree *BT);//求二叉链的宽度
int LinkBTreeNodes(LinkBTree * BT);//求节点个数
int LinkBTreeLeafNodes(LinkBTree *BT);//求二叉链的叶子节点个数
void LinkBTreeProOeder(LinkBTree *BT); //前序递归遍历
void LinkBTreeProOederRecursion(LinkBTree *BT);//前序非递归遍历
void LinkBTreeInOeder(LinkBTree *BT);//中序递归遍历
void LinkBTreeInOederRecursion(LinkBTree *BT);//中序非递归遍历
void LinkBTreePostOeder(LinkBTree *BT);//后序递归遍历
void LinkBTreePostOederRecursion(LinkBTree *BT);//后序非递归遍历
#endif
#include<iostream>
#include"LinkBTree.h"
using namespace std;
void LinkBTreeCreate(LinkBTree *& BT, char *str){//有str创建二叉链
LinkBTree *St[MaxSize], *p = NULL;
int top = -1, k, j = 0;
char ch;
BT = NULL;
ch = str[j];
while (ch != '\0'){
switch (ch){
case '(':top++; St[top] = p; k = 1; break;
//为左节点，top表示层数，k表示左右节点，碰到一个'('二叉树加一层,碰到一个','，变成右子树
case ')':top--; break;
case ',':k = 2; break; //为右节点
default:
p = (LinkBTree *)malloc(sizeof(LinkBTree));
p->Elem = ch;
p->Lchild = p->Rchild = NULL;
if (BT == NULL){
BT = p; //根节点
}else{
switch (k){
case 1:St[top]->Lchild = p; break;
case 2:St[top]->Rchild = p; break;
}
}
}
j++;
ch = str[j];
}
}
LinkBTree *LinkBTreeFindNode(LinkBTree * BT, DataType e) {//返回元素e的指针
LinkBTree *p;
if (BT == NULL){
return NULL;
}else if (BT->Elem == e){
return BT;
}else{
p = LinkBTreeFindNode(BT->Lchild, e); //递归
if (p != NULL){
return p;
}else{
return LinkBTreeFindNode(BT->Lchild, e);
}
}
}
LinkBTree *LinkBTreeLchild(LinkBTree *p){//返回*p节点的左孩子节点指针
return p->Lchild;
}
LinkBTree *LinkBTreeRight(LinkBTree *p){//返回*p节点的右孩子节点指针
return p->Rchild;
}
int LinkBTreeDepth(LinkBTree *BT){//求二叉链的深度
int LchildDep, RchildDep;
if (BT == NULL){
return 0;
}else{
LchildDep = LinkBTreeDepth(BT->Lchild);
RchildDep = LinkBTreeDepth(BT->Rchild);
}
return (LchildDep > RchildDep) ? (LchildDep + 1) : (RchildDep + 1);
}
void LinkBTreeDisplay(LinkBTree * BT){//以括号法输出二叉链
if (BT != NULL){
cout << BT->Elem;
if (BT->Lchild != NULL || BT->Rchild != NULL) {
cout << '(';
LinkBTreeDisplay(BT->Lchild);
if (BT->Rchild != NULL){
cout << ',';
}
LinkBTreeDisplay(BT->Rchild);
cout << ')';
}
}
}
int LinkBTreeWidth(LinkBTree *BT){//求二叉链的宽度
return 0;
}
int LinkBTreeNodes(LinkBTree * BT){//求节点个数
if (BT == NULL){
return 0;
}else if (BT->Lchild == NULL && BT->Rchild == NULL) {//为叶子节点的情况
return 1;
}else{
return (LinkBTreeNodes(BT->Lchild) +LinkBTreeNodes(BT->Rchild) + 1);
}
}
int LinkBTreeLeafNodes(LinkBTree *BT){//求二叉链的叶子节点个数
if (BT == NULL){
return 0;
}else if (BT->Lchild == NULL && BT->Rchild == NULL){ //为叶子节点的情况
return 1;
}else{
return (LinkBTreeLeafNodes(BT->Lchild) + LinkBTreeLeafNodes(BT->Rchild));
}
}
void LinkBTreeProOeder(LinkBTree *BT){ //前序非递归遍历
LinkBTree *St[MaxSize], *p;
int top = -1;
if (BT != NULL){
top++;
St[top] = BT; //将第一层指向根节点
while (top > -1){
p = St[top]; //第一层
top--; //退栈并访问该节点
cout << p->Elem << " ";
if (p->Rchild != NULL){
top++;
St[top] = p->Rchild;
}
if (p->Lchild != NULL){
top++;
St[top] = p->Lchild;
}
}
cout << endl;
}
}
void LinkBTreeProOederRecursion(LinkBTree *BT){//前序递归遍历
if (BT != NULL){
cout << BT->Elem<<" ";
LinkBTreeProOeder(BT->Lchild);
LinkBTreeProOeder(BT->Rchild);
}
}
void LinkBTreeInOeder(LinkBTree *BT){//中序非递归遍历
LinkBTree *St[MaxSize], *p;
int top = -1;
if (BT != NULL){
p = BT;
while (top > -1 || p != NULL){
while (p != NULL){
top++;
St[top] = p;
p = p->Lchild;
}
if (top> -1){
p = St[top];
top--;
cout << p->Elem <<" ";
p = p->Rchild;
}
}
cout << endl;
}
}
void LinkBTreeInOederRecursion(LinkBTree *BT){//中序递归遍历
if (BT != NULL){
LinkBTreeProOeder(BT->Lchild);
cout << BT->Elem << " ";
LinkBTreeProOeder(BT->Rchild);
}
}
void LinkBTreePostOeder(LinkBTree *BT){//后序非递归遍历
LinkBTree *St[MaxSize], *p;
int top = -1,flag;
if (BT != NULL){
do{
while (BT != NULL){
top++;
St[top] = BT;
BT = BT->Lchild;
}
p = NULL;
flag = 1;
while (top != -1 && flag){
BT = St[top];
if (BT->Rchild == p){
cout << BT->Elem << " ";
top--;
p = BT;
}else{
BT = BT->Lchild;
flag = 0;
}
}
} while (top != -1);
cout << endl;
}
}
void LinkBTreePostOederRecursion(LinkBTree *BT){//后序递归遍历
if (BT != NULL){
LinkBTreeProOeder(BT->Lchild);
LinkBTreeProOeder(BT->Rchild);
cout << BT->Elem << " ";
}
}
6. 哈夫曼树
在许多应用上，常常将树中的节点附上一个有着某种意义的数值，
称此数值为该节点的权，
从树根节点到该节点的路径长度与该节点权值之积称为带权路径长度。
树中所有叶子节点的带权路径长度之和称为该树的带权路径长度，如下：
gif.gif
，其中共有n个叶子节点的数目，Wi表示叶子节点i的权值，
Li表示根节点到叶子节点的路径长度。
在n个带有权值结点构成的二叉树中，
带权路径长度WPL最小的二叉树称为哈夫曼树。又称最优二叉树。
哈夫曼树算法：
（1）根据给定的n个权值，使对应节点构成n颗二叉树的森林T，
其中每颗二叉树中都只有一个带权值的Wi的根节点，其左右节点均为空
（2）在森林中选取两颗根节点权值最小的子树分别作为
左、右子树构造一颗新二叉树，
且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。
（3）在森林中，用新得到的二叉树代替选取的两棵树
（4）重复（2）和（3），直到T只含一棵树为止
定理：对于具有n个叶子节点的哈夫曼树，共有2n-1个节点
代码如下：
#pragma once
typedef double Wi; //假设权值为双精度
struct HTNode{ //每一个节点的结构内容，
Wi weight; //节点的权值
HTNode *left; //左子树
HTNode *right; //右子树
};
void PrintHuffman(HTNode * HuffmanTree); //输出哈夫曼树
HTNode * CreateHuffman(Wi a[], int n); //创建哈夫曼树
#include"Huffman.h"
#include<iostream>
/* 哈夫曼算法：
（1）根据给定的n个权值创建n个二叉树的森林，其中n个二叉树的左右子树均为空
（2）在森林中选择权值最小的两个为左右子树构造一颗新树，根节点
为权值最小的之和
（3）在森林中，用新的树代替选取的两棵树
（4）重复（2）和（3）
定理：n个叶子节点的哈夫曼树共有2n-1个节点
*/
/* a[] I 存放的是叶子节点的权值
n I 叶子节点个数
return O 返回一棵哈夫曼树
*/
HTNode* CreateHuffman(Wi a[], int n) {//创建哈夫曼树
int i, j;
HTNode **Tree, *HuffmanTree;
//根据n个权值声明n个二叉树的森林，二级指针表示森林（二叉树的集合）
Tree = (HTNode**)malloc(n * sizeof(HTNode));//代表n个叶节点，为n棵树分配内存空间
HuffmanTree = (HTNode*)malloc(sizeof(HTNode));
//实现第一步：创建n棵二叉树，左右子树为空
for (i = 0; i < n; i++) {
Tree[i] = (HTNode*)malloc(sizeof(HTNode));
Tree[i]->weight = a[i];
Tree[i]->left = Tree[i]->right = nullptr;
}
//第四步：重复第二和第三步
for (i = 1; i < n; i++) {//z这里表示第i次排序
//第二步：假设权值最小的根节点二叉树下标为第一个和第二个
//打擂台选择最小的两个根节点树
int k1 = 0, k2 = 1;
for (j = k2; j < n; j++) {
if (Tree[j] != NULL){
if (Tree[j]->weight < Tree[k1]->weight) {
//表示j比k1和k2的权值还小，因此两个值都需要更新
k2 = k1;
k1 = j;
}else if(Tree[j]->weight < Tree[k2]->weight) { //k1 < j < k2，需要更新k2即可
k2 = j;
}
}
}
//第三步：一次选择结束后，将更新一颗树
HuffmanTree = (HTNode*)malloc(sizeof(HTNode));//每次一轮结束，创建一个根节点
//更新后的根节点权值为左右子树权值之和
HuffmanTree->weight = Tree[k1]->weight +Tree[k2]->weight;
HuffmanTree->left = Tree[k1]; //最小值点为左子树
HuffmanTree->right = Tree[k2]; //第二小点为右子树
Tree[k1] = HuffmanTree;
Tree[k2] = nullptr;
}
free(Tree);
return HuffmanTree;
}
//先序遍历哈夫曼树
void PrintHuffman(HTNode * HuffmanTree){ //输出哈夫曼树
if (HuffmanTree == nullptr){
return;
}
std::cout << HuffmanTree->weight;
if (HuffmanTree->left != nullptr || HuffmanTree->right != nullptr){
std::cout << "(";
PrintHuffman(HuffmanTree->left);
if (HuffmanTree->right != nullptr){
std::cout << ",";
}
PrintHuffman(HuffmanTree->right);
std::cout << ")";
}
}
7. 查找算法
线性表查找：
顺序查找：
int seqSearch(int a[n],int n,int key){
int i=0;
int isFind=0;
while(i<n ){
if(a[i] == key){ isFind=1; break;}
++i;
}
return isFind;
}
折半查找(前提是：线性表有序)：eg如下(假设线性表升序)
int binSearch(int a[n],int n,int key){
int low=0,high=n-1,mid;
int isFind=0;
while(low<=high){
mid=(low+high)/2;
if(a[mid] == key ){
isFind=1; break;
}else if(a[mid] > key){
high=mid-1;
}else{
low =mid +1;
}
}
return isFind;
}
树查找：
二叉排序树(B 树)：
#pragma once
#ifndef BSTREE_H
#define BSTREE_H
#define Max 100
typedef int KeyType;
typedef char InfoType[10];
typedef struct node{
KeyType key; //关键字项
InfoType data; //其他数据项
struct node *Lchild, *Rchild;
}BSTNode;
//由数组A（含有n个关键字）中的关键字创建一个二叉排序树
BSTNode *BSTreeCreat(KeyType A[], int n);
//在以*BST为根节点的二叉排序树中插入一个关键字为k的结点
int BSTreeInsert(BSTNode *& BST, KeyType k);
int BSTreeDelete(BSTNode *& BST, KeyType k); //在bst中删除关键字为k的结点
void BSTreeDisplay(BSTNode * BST); //以括号法输出二叉排序树
int BSTreeJudge(BSTNode * BST); //判断BST是否为二叉排序树
#endif
#include<iostream>
#include"BSTree.h"
using namespace std;
BSTNode *BSTreeCreat(KeyType A[], int n) {
//由数组A（含有n个关键字）中的关键字创建一个二叉排序树
BSTNode *BST = NULL;
int i = 0;
while (i < n) {
if(BSTreeInsert(BST,A[i]) == 1){
cout << "第" << i + 1 << "步，插入" << A[i] << endl;
BSTreeDisplay(BST);
cout << endl;
i++;
}
}
return BST;
}
//在以*BST为根节点的二叉排序树中插入一个关键字为k的结点
int BSTreeInsert(BSTNode *& BST, KeyType k) {
if (BST == NULL) {
BST = (BSTNode *)malloc(sizeof(BSTNode));
BST->key = k;
BST->Lchild = BST->Rchild = NULL;
return 1;
}else if(k == BST->key){
return 0;
}else if(k > BST->key){
return BSTreeInsert(BST->Rchild, k);
}else{
return BSTreeInsert(BST->Lchild, k);
}
}
int BSTreeDelete(BSTNode *& BST, KeyType k) {//在bst中删除关键字为k的结点
if (BST == NULL) {
return 0;
}else{
if (k < BST->key){
return BSTreeDelete(BST->Lchild, k);
}else if (k>BST->key){
return BSTreeDelete(BST->Rchild, k);
}else{
Delete(BST)
}
}
}
void BSTreeDisplay(BSTNode * BST) {//以括号法输出二叉排序树
if (BST != NULL){
cout << BST->key;
if (BST->Lchild != NULL || BST->Rchild != NULL) {
cout << '(';
BSTreeDisplay(BST->Lchild);
if (BST->Rchild != NULL){
cout << ',';
}
BSTreeDisplay(BST->Rchild);
cout << ')';
}
}
}
KeyType predt = -32767;
int BSTreeJudge(BSTNode * BST){ //判断BST是否为二叉排序树
int b1, b2;
if (BST == NULL) {
return 1;
} else{
b1 = BSTreeJudge(BST->Lchild);
if (b1 == 0 || predt >= BST->key){
return 0;
}
predt = BST->key;
b2 = BSTreeJudge(BST->Rchild);
return b2;
}
}
void Delete(BSTNode*& p){ //删除二叉排序树*p节点
BSTNode* q;
if (p->Rchild == nullptr){
//当删除的节点没有右子树，只有左子树时，根据二叉树的特点，
//直接将左子树根节点放在被删节点的位置。
q = p;
p = p->Lchild;
free(p);
}else if (p->Lchild == nullptr){
//当删除的结点没有左子树，只有右子树时，根据二叉树的特点，
//直接将右子树结点放在被删结点位置。
q = p;
p = p->Rchild;
free(p);
}else{
Delete1(p, p->Lchild); //当被删除结点有左、右子树时
}
}
void Delete1(BSTNode* p, BSTNode* &r){
//当删除的二叉排序树*P节点有左右子树的删除过程
BSTNode *q;
if (p->Lchild != nullptr) {
Delete1(p, p->Rchild); //递归寻找最右下节点
} //找到了最右下节点*r
else{ //将*r的关键字赋值个*p
p->key = r->key;
q = r;
r = r->Lchild;
free(q);
}
}
平衡二叉树：若一棵二叉树中的每个节点的左右子树高度至多相差1，则称此二叉树为平衡二叉树。
其中平衡因子的定义为：平衡二叉树中每个节点有一个平衡因子，每个节点的平衡因子是该节点左子树高度减去右子树的高度，若每个平衡因子的取值为0，-1,1则该树为平衡二叉树。
B-树
用作外部查找的数据结构，其中的数据存放在外存中，是一种多路搜索树：
所有的叶子节点放在同一层，并且不带信息
树中每个节点至多有m棵子树
若根节点不是终端节点，则根节点至少有两棵子树
除根节点外的非叶子节点至少有m/2棵子树
每个节点至少存放m/2-1个至多m-1个关键字
非叶子节点的关键字数=指向儿子指针的个数-1
非叶子节点的关键字依次递增
非叶子节点指针：P[1],P[2],...P[m]；
其中P[i]指向关键字小于K[1]的子树，
P[i]指向关键字属于(K[i-1],K[i])的子树
哈希表查找：从根本上说，一个哈希表包含一个数组，
通过特殊的索引值（键）来访问数组中的元素。
哈希表的主要思想是通过一个哈希函数，
在所有可能的键与槽位之间建立一张映射表。
哈希函数每次接收一个键将返回与键对应的哈希编码或者哈希值。
键的数据类型可能多种多样，但哈希值只能是整型。
计算哈希值和在数组中进行索引都只消耗固定的时间，
因此哈希表的最大亮点在于它是一种运行时间在常量级的检索方法。
当哈希函数能够保证不同的键生成的哈希值互不相同时，
就说哈希值能直接寻址想要的结果。
散列表（Hash table，也叫哈希表），
是根据关键码值(Key value)而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，
以加快查找的速度。这个映射函数叫做散列函数，
存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，
代入函数后若能得到包含该关键字的记录在表中的地址，
则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
散列函数能使对一个数据序列的访问过程更加迅速有效，
通过散列函数，数据元素将被更快地定位。
实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：
计算哈希函数所需时间、关键字的长度、哈希表的大小、
关键字的分布情况、记录的查找频率
直接寻址法：
取关键字或关键字的某个线性函数值为散列地址。
即H(key)=key或H(key) = a·key + b，其中a和b为常数
（这种[散列函数](参见百科)叫做自身函数）。
若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
这种哈希函数计算简单，并且不可能有冲突产生，当关键字连续时，
可用直接寻址法；否则关键字的不连续将造成内存单元的大量浪费。
数字分析法：
分析一组数据，比如一组员工的出生年月日，
这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，
但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，
如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
平方取中法：
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，
然后按需要取平方值的中间几位作为哈希地址。这是因为：
平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
除留取余法：
用关键字k除以某个不大于哈希表长度m的数p，将所得的余数作为哈希地址的方法。
h(k) = k mod p，其中p取不大于m的素数最佳。
#pragma once
#define MaxSize 20 //此处表示哈希表长度m
#define NULLKEY -1 //表示该节点为空节点，未存放数据
#define DELEKEY -2 //表示该节点数据被删除，
typedef int Key; //关键字类型
typedef struct{
Key key; //关键字值
int count; //探查次数
}HashTable[MaxSize];
void HTInsert(HashTable HT,int &n,Key k,int p); //将关键字插入哈希表中
void HTCreate(HashTable HT, Key x[], int n, int m, int p); //创建哈希表
int HTSearch(HashTable HT, int p, Key k); //在哈希表中查找关键字
int HTDelete(HashTable HT, int p, Key k, int &n); //删除哈希表中关键字k
void HTDisplay(HashTable HT,int n,int m);
#include"HT.h"
#include<iostream>
/*解决冲突用开地址的线性探查法*/
void HTInsert(HashTable HT, int &n, Key k, int p) {//将关键字k插入哈希表中
int i,addr; //i:记录探查数;adddr:记录哈希表下标
addr = k % p;
if (HT[addr].key == NULLKEY || HT[addr].key == DELEKEY){
//表示该出为空，可以存储值
HT[addr].key = k;
HT[addr].count = 1;
}else{ //表示存在哈希冲突
i = 1;
do{
addr = (addr + 1) % p;
//哈希冲突解决办法：开地址法中的线性探查法，从当前冲突地址开始依次往后排查
i++;
} while (HT[addr].key != NULLKEY || HT[addr].key != DELEKEY);
}
n++;//表示插入一个元素后哈希表共存储的元素数量
}
/*HT I/O 哈希表
x[] I 关键字数组
n I 关键字个数
m I 哈希表长度
p I 为小于m的数p，取不大于m的素数最好
*/
void HTCreate(HashTable HT, Key x[], int n, int m, int p){//创建哈希表
for (int i = 0; i < m; i++){ //创建一个空的哈希表
HT[i].key = NULLKEY;
HT[i].count = 0;
}
int n1 = 0;
for (int i = 0; i < n; i++){
HTInsert(HT, n1, x[i], p);
}
}
int HTSearch(HashTable HT, int p, Key k) {//在哈希表中查找关键字
int addr; //用来保存关键字k在哈希表中的下标
addr = k % p;
while(HT[addr].key != NULLKEY || HT[addr].key != k){
addr = (addr + 1) % p; //存在着哈希冲突
}
if (HT[addr].key == k){
return addr;
}else{
return -1;
}
}
/* 注：删除并非真正的删除，而是标记*/
int HTDelete(HashTable HT, int p, Key k, int &n){//删除哈希表中关键字k
int addr;
addr = HTSearch(HT, p, k);
if (addr != -1){
HT[addr].key = DELEKEY;
n--;
return 1;
}else{
return 0;
}
}
void HTDisplay(HashTable HT, int n, int m) {//输出哈希表
std::cout << " 下标：";
for (int i = 0; i < m; i++){
std::cout<< i << " ";
}
std::cout << std::endl;
std::cout << " 关键字：";
for (int i = 0; i < m; i++){
std::cout << HT[i].key << " ";
}
std::cout << std::endl;
std::cout << "探查次数：";
for (int i = 0; i < m; i++){
std::cout << HT[i].key << " ";
}
std::cout << std::endl;
}
8.排序算法
(1)直接插入排序：
假设待排序的元素存放在数组R[0...n-1]中，
排序过程中的某一时刻R被划分为两个子区间R[0..i-1]和R[i..n-1]，
其中，前一个子区间是已排好序的有序区间，后一个则是未排序。
直接插入排序的一趟操作是将当前无序区间的开头元素R[i]插入到
有序区间R[0..i-1]中适当的位置中，使R[0..i]变成新的区间。
void InsertSort(int a[], int n){//升序排序,n是数组大小
int i,j;
for(i=1;i<n;++i){
j=i-1;
int tmp=a[i];
while(j>=0 && tmp < a[j]){
a[j+1]=a[j];
--j;
}
a[j+1]=tmp;
}
}
(2)希尔排序(缩小增量排序)：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
算法步骤如下，
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为m 的子序列，
分别对各子表进行直接插入排序，仅增量因子为1 时，
整个序列作为一个表来处理，表长度即为整个序列的长度。
void ShellInsert(int a[], int n){//升序排序,n是数组大小
int i,j,d,tmp;
d=n/2;
while(d>0){ //增量每次都/2
for(i=d;i<n;++i){ //从增量那组开始进行插入排序，直至完毕
tmp=a[i];
j=i-d;
while(j>=0 ){
if(a[j]<tmp){
break;
}
a[j+d]=a[j];
j-=d;
}
a[j+d]=tmp;
}
d/=2;
}
}
(3)冒泡排序：
比较相邻的元素。如果第一个比第二个大，就交换他们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，
这步做完后，最后的元素会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
void BubbleSort(int a[],int n){ //升序排序,n是数组大小
int isSwap;
for (int i = 0; i < n; i++){
isSwap=0;
for (int j = 0; j < n-i-1; j++){
if (a[j+1] < a[j]){
a[j+1]^=a[j];
a[j]^=a[j+1];
a[j+1]^=a[j];
isSwap=1;
}
}
if(isSwap==0){ break;}
}
}
其它改进方法：
方法一：
设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。
由于pos位置之后的记录均已交换到位,
故在进行下一趟排序时只要扫描到pos位置即可。
void BubbleSort(int a[],int n){ //升序排序,n是数组大小
int isSwap;
int lastExchangeIndex=0;
int sortBorder= n-1;
for(int i=0;i< n;++i){
isSwap=0;
for(int j=0;j< sortBorder;++j){
if(a[j]> a[j+1]){
a[j+1]^=a[j];
a[j]^=a[j+1];
a[j+1]^=a[j];
isSwap=1;
lastExchangeIndex=j;
}
}
if(isSwap==0){ break;}
sortBorder= lastExchangeIndex;
}
}
方法二：
传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,
我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法
一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
void BubbleSort(int a[],int n){ //升序排序,n是数组大小
int low=0;
int high=n-1;
int i;
while(low < high){
for(i=low;i<high;++i){
if( a[i]>a[i+1]){
a[j+1]^=a[j];
a[j]^=a[j+1];
a[j+1]^=a[j];
}
}
--high;
for(i=high;i>low;--i){
if( a[i] > a[i-1]){
a[j+1]^=a[j];
a[j]^=a[j+1];
a[j+1]^=a[j];
}
}
++low;
}
}
(4)快速排序：
从数列中挑出一个元素，称为 “基准”（pivot）；(以升序排序为例)
重新排序数列，所有元素比基准值小的摆放在基准前面，
所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），
在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。
虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，
它至少会把一个元素摆到它最后的位置去。
void Quick_Sort(int a[], int left, int right){
if (left < right){
int pivot=a[left];/*用字表的第一个记录作为枢轴*/
int low=left;
int high=right;
while(low<hight){
while(low <high && a[high] >= pivot){
--high;
}
a[low]=a[high];/*将比第一个小的移到低端*/
while( low< high && a[low]<=pivot){
++low;
}
a[high] = a[low];/*将比第一个大的移到高端*/
}
a[low]=pivot;/*枢轴记录到位*/
Quick_Sort(a, left, low - 1); //左半部分排序
Quick_Sort(a, low + 1, right); //右半部分排序
}
}
(5)选择排序：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
重复第二步，直到所有元素均排序完毕。
void select_sort(int *a,int n){ //升序排序，n为数组大小
register int i,j,min,t;
for(i = 0;i < n-1;i++) {
min = i;//查找最小值
for(j = i + 1;j < n;j++){
if(a[min] > a[j]){
min = j;//交换
}
}
if(min != i) {
int t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
(6)堆排序：
在排序过程中，将R[1..n]看成是一颗顺序存储的完全二叉树，
利用完全二叉树中双亲节点和孩子节点之间的内在关系，
在当前无序区中选择关键字最小或最大的元素。算法步骤如下，
创建一个堆H[0..n-1]；；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置；
重复步骤2，直到堆的尺寸为1；
用大根堆排序的基本思想 ：
① 先将初始数组建成一个大根堆，此堆为初始的无序区
② 再将最大的元素（即堆顶）和无序区的最后一个记录交换，
由此得到新的无序区和有序区，且满足的值<=的值。
③由于交换后新的根可能违反堆性质，故应将当前无序区调整为堆。
然后再次将中最大的元素和该区间的最后一个记录交换，
由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将调整为堆。
……
直到无序区只有一个元素为止。
大根堆排序算法的基本操作：
①建堆，建堆是不断调整堆的过程，从len/2处开始调整，
一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，
从len/2到0处一直调用调整堆的过程，
相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，
这是一个求和的过程，结果是线性的O(n)。
②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。
利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，
如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，
然后再调用调整堆过程，这是一个递归的过程。
调整堆的过程时间复杂度与堆的深度有关系，
是lgn的操作，因为是沿着深度方向进行调整的。
③堆排序：堆排序是利用上面的两个过程来进行的。
首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，
将前面len-1个节点继续进行堆调整的过程，
然后再将根节点取出，这样一直到所有节点都取出。
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength){
int nChild;
int nTemp;
for(; 2 * i + 1 < nLength;i = nChild){//子结点的位置=2*（父结点位置）+1
nChild = 2 * i + 1; //得到子结点中较大的结点
if(nChild < nLength - 1 && array[nChild + 1] > array[nChild]) {
++nChild;
}
//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if(array[i] < array[nChild]) {
nTemp = array[i];
array[i] = array[nChild];
array[nChild] = nTemp;
} else{
break; //否则退出循环
}
}
}
//堆排序算法
void HeapSort(int array[],int length){
int i; //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点，此处"/"为整除
for(i = length / 2 - 1;i >= 0;--i){
HeapAdjust(array,i,length);
}
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i = length - 1;i > 0;--i) { //把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i] = array[0] ^ array[i];
array[0] = array[0] ^ array[i];
array[i] = array[0] ^ array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}
(7)归并排序：
申请空间，使其大小为两个已经排序序列之和，
该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复上一步骤直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。
(要提高效率可改为多路归并；m路归并，增量每次/m，首次增量为序列长度/m)。
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){
int i = startIndex, j=midIndex+1, k = startIndex;
while(i != midIndex + 1 && j != endIndex + 1) {
if(sourceArr[i] >= sourceArr[j]){
tempArr[k++] = sourceArr[j++];
} else{
tempArr[k++] = sourceArr[i++];
}
}
while(i != midIndex+1){
tempArr[k++] = sourceArr[i++];
}
while(j != endIndex+1){
tempArr[k++] = sourceArr[j++];
}
for(i = startIndex; i <= endIndex; i++){
sourceArr[i] = tempArr[i];
}
}
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){
int midIndex;
if(startIndex < endIndex) {
midIndex = (startIndex + endIndex) / 2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
(8). 基数排序/桶排序
是将阵列分到有限数量的桶子里。每个桶子再个别排序
（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。
桶排序是鸽巢排序的一种归纳结果。
当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。
但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，
然后对每个桶里面的在进行排序。
int maxbit(int data[], int n){ //辅助函数，求数据的最大位数
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i) {
while(data[i] >= p) {
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) {//基数排序
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) {//进行d次排序
for(j = 0; j < 10; j++){
count[j] = 0; //每次分配前清空计数器
}
for(j = 0; j < n; j++) {
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++){
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
}
for(j = n - 1; j >= 0; j--) {//将所有桶中记录依次收集到tmp中
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) {//将临时数组的内容复制到data中
data[j] = tmp[j];
}
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
网友评论