[C++知识库]C++&&C&&DS代码复习

C++类与友元函数：

//auxil.h的内容
#ifndef AUXIL_H
#define AUXIL_H
// Aux class declaration.
class Aux
{
    private:
        double auxBudget;
    public:
        Aux() { auxBudget = 0; }
        void addBudget(double);
        double getDivBudget() const { return auxBudget; }
};
#endif
//budget3.h的内容
#ifndef BUDGET3_H
#define BUDGET3_H
#include "auxil.h" // For Aux class declaration
//Budget class declaration.
class Budget {
    private:
        static double corpBudget;
        double divBudget;
    public:
        Budget() { divBudget =0; }
        void addBudget(double b)
        {
            divBudget += b;
            corpBudget += divBudget;
        }
        double getDivBudget() const {return divBudget;}
        static double getCorpBudget() {return corpBudget;}
        static void mainOffice(double);
        friend void Aux::addBudget(double);
};
#endif
//budget3.cpp的内容
#include "budget3.h"
//Definition of static member.
double Budget::corpBudget = 0;
void Budget:imainOffice(double budReq)
{
    corpBudget += budReq;
}
//auxil.cpp的内容
#include "auxil.h"
#include "budget3.h"
void Aux::addBudget(double b)
{
    auxBudget += b;
    Budget::corpBudget += auxBudget;
}
//main程序的内容
//This program demonstrates a static class member variable. #include <iostream>
#include <iomanip>
#include "budget3.h"
using namespace std;
int main()
{
    const int N_DIVISIONS = 4;
    // Get the budget requests for the divisions and offices
    cout << "Enter the main office's budget request:";
    double amount;
    cin >> amount;
    Budget:imainOffice(amount);
    // Create the division and auxiliary offices
    Budget divisions [N_DIVISIONS];
    Aux auxOffices[N_DIVISIONS];
    cout << "\nEnter the budget requests for the divisions and" << "\ntheir auxiliary offices as prompted:\n";
    for (int count = 0; count < N_DIVISIONS; count++)
    {
        double bud;
        cout << "Division " << (count + 1) << ": ";
        cin >> bud;
        divisions[count].addBudget(bud);
        cout << "Division " << (count + 1) << "'s auxiliary office:";
        cin >> bud;
        auxOffices[count].addBudget(bud);
    }
    // Print the budgets
    cout << setprecision (2);
    cout << showpoint << fixed;
    cout << "Here are the division budget requests:\n";
    for (int count = 0; count < N_DIVISIONS; count++)
    {
        cout << "\tDivision: " << (count + 1) << "\t\t\t$ ";
        cout << setw(7);
        cout << divisions[count].getDivBudget() << endl;
        cout << "\tAuxiliary Office of Division " << (count+1);
        cout << "\t$ ";
        cout << auxOffices[count].getDivBudget() << endl;
    }
    // Print total requests
    cout << "\tTotal Requests (including main office): $ ";
    cout << Budget::getCorpBudget() << endl;
    return 0;
}

数据结构：快速排序

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

数据结构：堆排序

#include <stdio.h>

void display(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int array[], int x, int y) {
    int key  = array[x];
    array[x] = array[y];
    array[y] = key;
}

// 从大到小排序
// void Down(int array[], int i, int n) {
//     int child = 2 * i + 1;
//     int key   = array[i];
//     while (child < n) {
//         if (child + 1 < n && array[child] > array[child + 1]) {
//             child++;
//         }
//         if (key > array[child]) {
//             swap(array, i, child);
//             i = child;
//         } else {
//             break;
//         }
//         child = child * 2 + 1;
//     }
// }

// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
    int parent = i;                    // 父节点下标
    int child  = 2 * i + 1;            // 子节点下标
    while (child < n) {
        if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if (array[parent] < array[child]) { // 判断父节点是否小于子节点
            swap(array, parent, child);     // 交换父节点和子节点
            parent = child;                 // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1; // 换行，比较下面的父节点和子节点
    }
}

void BuildHeap(int array[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(array, i, size);                 // 否则有的不符合大顶堆定义
    }
}

void HeapSort(int array[], int size) {
    printf("初始化数组：");
    BuildHeap(array, size); // 初始化堆
    display(array, size);   // 查看初始化结果
    for (int i = size - 1; i > 0; i--) {
        swap(array, 0, i); // 交换顶点和第 i 个数据
                           // 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
        Down(array, 0, i); // 重新建立大顶堆

        printf("排序的数组：");
        display(array, size);
    }
}

int main() {
    int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
    int size    = sizeof(array) / sizeof(int);

    // 打印数据
    printf("%d \n", size);
    printf("排序前数组：");
    display(array, size);
    HeapSort(array, size);

    return 0;
}

数据结构：链表相关

linkList reverse(linkList head){ //单向链表进行转置
  linkList p,q,pr;
  p = head->next;
  q = NULL;
  head->next = NULL;
  while(p){
    pr = p->next;
    p->next = q;
    q = p;
    p = pr;
  }
  head->next = q;
  return head;
}

#include <stdio.h>
#include <stdlib.h>

struct link *AppendNode (struct link *head);
void DisplyNode (struct link *head);
void DeletMemory (struct link *head);

struct link
{
    int data;
    struct link *next;
};

int main(void)
{
    int i = 0;
    char c;
    struct link *head = NULL;    //链表头指针
    printf("Do you want to append a new node(Y/N)?");
    scanf_s(" %c", &c);
    while (c == 'Y' || c == 'y')
    {
        head = AppendNode(head);//向head为头指针的链表末尾添加节点
        DisplyNode(head);        //显示当前链表中的各节点的信息
        printf("Do your want to append a new node(Y/N)");
        scanf_s(" %c", &c);
        i++;
    }
    printf("%d new nodes have been apended", i);
    DeletMemory(head);    //释放所有动态分配的内存

    return 0;
}
/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */
struct link *AppendNode(struct link *head)
{
    struct link *p = NULL, *pr = head;
    int data;
    p = (struct link *)malloc(sizeof(struct link));//让p指向新建的节点
    if (p == NULL)        //若新建节点申请内存失败，则退出程序
    {
        printf("No enough memory to allocate\n");
        exit(0);
    }
    if (head == NULL)    //若原链表为空表
    {
        head = p;        //将新建节点置为头节点
    }
    else                //若原链表为非空，则将新建节点添加到表尾
    {
        while (pr->next != NULL)//若未到表尾，则移动pr直到pr指向表尾
        {
            pr = pr->next;        //让pr指向下一个节点
        }
        pr->next = p;            //让末节点的指针指向新建的节点
    }
    printf("Input node data\n");
    scanf_s("%d", &data); //输入节点数据
    p->data = data;        //将新建节点的数据域赋值为输入的节点数据值
    p->next = NULL;        //将新建的节点置为表尾
    return head;        //返回添加节点后的链表的头指针
}
/* 函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容*/
void DisplyNode (struct link *head)
{
    struct link *p = head;
    int j = 1;
    while (p != NULL)  //若不是表尾，则循环打印节点的数值
    {
        printf("%5d%10d\n", j, p->data);//打印第j个节点数据
        p = p->next;  //让p指向下一个节点
        j++;
    }
}
//函数的功能：释放head所指向的链表中所有节点占用的内存
void DeletMemory(struct link *head)
{
    struct link *p = head, *pr = NULL;
    while (p != NULL)  //若不是表尾，则释放节点占用的内存
    {
        pr = p;        //在pr中保存当前节点的指针
        p = p->next;//让p指向下一个节点
        free(pr);    //释放pr指向的当前节点占用的内存
    }
}

数据结构：队列相关

/*****************************************/
//LQueue.h

typedef int QElemType;
//typedef struct BTNode* QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode *_pNext;
}QNode;

typedef struct LQueue
{
	QNode *pFront;
	QNode *pRear;
}LQueue;


//初始化
void LQueueInit(LQueue *q);

//入队列
void LQueuePush(LQueue *q, QElemType data);

//出队列
void LQueuePop(LQueue *q);

//返回队头元素
QElemType LQueueTop(LQueue *q);

//返回返回队列长度
int LQueueSize(LQueue *q);

//队列是否为空
int LQueueEmpty(LQueue *q);


/************************************************/
//LQueue.c

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

//创建新结点
static QNode *BuyLQNode(QElemType data)
{
	QNode *pLQNode = (QNode *)malloc(sizeof(QNode));
	if (NULL == pLQNode)
	{
		printf("申请空间失败!\n");
		assert(pLQNode);
	}
	pLQNode->data = data;
	pLQNode->_pNext = NULL;

	return pLQNode;
}

//初始化
void LQueueInit(LQueue *q)
{
	assert(q);
	q->pFront = q->pRear = NULL;
}

//入队列
void LQueuePush(LQueue *q, QElemType data)
{
	assert(q);
	if (NULL == q->pFront)
	{
		q->pFront = q->pRear = BuyLQNode(data);
		return;
	}
	q->pRear->_pNext = BuyLQNode(data);
	q->pRear = q->pRear->_pNext;
}

//出队列
void LQueuePop(LQueue *q)
{
	assert(q);
	QNode *pDel;
	if (NULL == q->pFront)
	{
		return;
	}

	if (q->pFront == q->pRear)
	{
		q->pRear = NULL;
	}

	pDel = q->pFront;
	q->pFront = q->pFront->_pNext;
	free(pDel);
}

//返回队头元素
QElemType LQueueTop(LQueue *q)
{
	assert(q);
	return q->pFront->data;
}

//返回队尾元素
QElemType LQueueBack(LQueue *q)
{
	assert(q);
	return q->pRear->data;
}

//返回返回队列长度
int LQueueSize(LQueue *q)
{
	int count = 0;
	QNode *pCur;
	assert(q);
	pCur = q->pFront;
	while (pCur)
	{
		pCur = pCur->_pNext;
		count++;
	}
	return count;
}

//队列是否为空
int LQueueEmpty(LQueue *q)
{
	return NULL == q->pFront;
}

数据结构：哈夫曼树相关

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
#define N 10         // 带编码字符的个数，即树中叶结点的最大个数
#define M (2*N-1)    // 树中总的结点数目
 
class HTNode{        // 树中结点的结构
public: 
	unsigned int weight;
	unsigned int parent,lchild,rchild;
};                    
 
class HTCode{
public:
	char data;      // 待编码的字符
	int weight;     // 字符的权值
	char code[N];   // 字符的编码
};
 
void Init(HTCode hc[], int *n){
// 初始化，读入待编码字符的个数n，从键盘输入n个字符和n个权值
	int i;
	printf("input n = ");
	scanf("%d",&(*n));
 
	printf("\ninput %d character\n",*n);
 	
	fflush(stdin);
	for(i=1; i<=*n; ++i)
		scanf("%c",&hc[i].data);
 
	printf("\ninput %d weight\n",*n);
	
	for(i=1; i<=*n; ++i)
		scanf("%d",&(hc[i].weight) );
	fflush(stdin);
}//
 
void Select(HTNode ht[], int k, int *s1, int *s2){
// ht[1...k]中选择parent为0，并且weight最小的两个结点，其序号由指针变量s1，s2指示
	int i;
	for(i=1; i<=k && ht[i].parent != 0; ++i){ 
		; ;
	}
	*s1 = i;
 
	for(i=1; i<=k; ++i){
		if(ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
			*s1 = i;
	}
 
	for(i=1; i<=k; ++i){
		if(ht[i].parent==0 && i!=*s1)
			break;
	}
	*s2 = i;
 
	for(i=1; i<=k; ++i){
		if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
			*s2 = i;
	}
}
 
void HuffmanCoding(HTNode ht[],HTCode hc[],int n){
// 构造Huffman树ht，并求出n个字符的编码
	char cd[N];
	int i,j,m,c,f,s1,s2,start;
	m = 2*n-1;
	
	for(i=1; i<=m; ++i){
		if(i <= n)
			ht[i].weight = hc[i].weight;
		else
			ht[i].parent = 0;
		ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
	}
 
	for(i=n+1; i<=m; ++i){
		Select(ht, i-1, &s1, &s2);
		ht[s1].parent = i;
		ht[s2].parent = i;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
		ht[i].weight = ht[s1].weight+ht[s2].weight;
	}
 
	cd[n-1] = '\0';
 
	for(i=1; i<=n; ++i){
		start = n-1;
		for(c=i,f=ht[i].parent; f; c=f,f=ht[f].parent){
			if(ht[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		strcpy(hc[i].code, &cd[start]);
	}
}
 
 
int main()
{
	int i,m,n,w[N+1];
	HTNode ht[M+1];
	HTCode hc[N+1];
	Init(hc, &n);     // 初始化
 	HuffmanCoding(ht,hc,n);   // 构造Huffman树，并形成字符的编码
 
	for(i=1; i<=n; ++i)  
		printf("\n%c---%s",hc[i].data,hc[i].code);  
	printf("\n");
 
	return 0;
}