数据结构与算法分析

算法 cpp 数据结构 C语言
数据结构
发布日期:   2020-10-15
文章字数:   14.6k
阅读时长:   64 分
阅读次数:  

第一章 数据结构和算法分析

一、数据结构

  1. 逻辑结构：线性结构、非线性结构。
  2. 存储结构：顺序（随机存取）、链式（顺序存取）、索引、散列。
  3. 运算：运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
  4. 抽象数据类型：ADT只是一个数学模型以及定义在模型上的一组操作。

二、算法

  1. 五特征：有穷性、确定性、可行性、输入、输出。

  2. 时间复杂度：时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到具体的值，但我们一般并不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入时间频度（语句频度）的概念。时间频度中，n称为问题的规模，当n不断变化时,时间频度T(n)也会不断变化。一般情况下，算法中的基本操作重复次数的是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n))，称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

  3. 空间复杂度：指运行完一个程序所需内存的大小，其包括两个部分。

    • 固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，属于静态空间。
    • 可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，大小与算法有关。

  4. O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n).

程序 = 数据结构 + 算法

三、内存分配

  1. 常规的内存分配，使用到释放的过程如下：

    #include<stdio.h>
#include<stdlib.h>
#define SIZE 5
int main(void)
{
    int *p;
    p = (int*)malloc(SIZE*sizeof(int));//申请SIZE歌整形大小的内存并返回首地址给p
    if(p == NULL)
        exit(1);
    p[0] = 123;//为空间添加数据
    printf("%d",p[0]);
    free(p);//释放p所指空间，但p依旧存在为野指针
    p = NULL;//此时不是野指针    
    return 0;
}

    C语言中malloc函数从堆上动态分配内存，free函数释放已分配的对应内存。

第二章 线性表

一、单链表

  1. 单链表，每个结点可以使用结构体struct设计：

    image-20230314220830970

    Data为数据元素，可以是数组、基本数据类型、结构体，next为指向下一个结点的指针，链尾指向NULL。

    //定义结点类型
typedef struct Node
{
    int data;
    struct Node *next;
} Node, *LinkedList;
//Node表示结点类型，LinkedList表示指向Node结点类型的指针类型

  2. 单链表初始化

    LinkedList listinit()
{	/*初始化是创建一个单链表的前置结点并向后逐步添加结点，
	即申请结点的空间，同时对一个结点赋以空值(NULL)*/
    Node *L;
    L = (Node*)malloc(sizeof(Node));//开辟空间
    if(L==NULL)
    {	
        printf("申请失败");
     	exit(0);
    }
    L -> next = NULL;//指针指向空
    return L;
}

  3. 创建单链表

    单链表的创建分为头插入法和尾插入法两种，都是利用指针指向下一个结点元素的方式进行逐个创建，使用头插入法最终得到的结果是逆序的。

    LinkedList ListCreatH(LinkedList h)
{//头插法，插在表头，头结点之后
    Node *L;
    L = h;
    int x;
    while(scanf("%d", &x) != EOF)//输入类型正确,按ctrl+z结束
    {
        Node * p;
        p = (Node*)malloc(sizeof(Node));
        p -> data = x;
        p -> next = L -> next;//L-->|2|-->|1|-->NULL
        L -> next = p;
    }
    return L;
}

LinkedList ListCreatT(LinkedList L)
{//尾插法
    Node *r = L;//r始终指向终端结点，开始指向头结点
    int x;
    while(scanf("%d", &x) != EOF)//按ctrl+z结束
    {
        Node *p;
        p = (Node*)malloc(sizeof(Node));
        p -> data = x;
        r -> next = p;//L-->|1|-->|2|-->NULL
        r = p;
    }
    r -> next = NULL;//尾插法细结
    return L;
}

  4. 遍历单链表

    遍历单链表可以查询元素、修改元素、获取元素个数、打印链表数据。

    void printList(LinkedList L)
{//遍历打印
    Node *p = L -> next;
    int i = 0;
    while(p)
    {
        printf("第%d个元素值为%d\n", ++i, p -> data);
        p = p -> next;
    }
}
LinkedList ListReplace(LinkedList L, int x, int k)
{//将链表中值为x的元素改为k
    Node *p = L -> next;
    while (p)
    {
        if(p -> data == x)
            p -> data = k;
        p = p -> next;
    }
    return L;
}

  5. 单链表插入操作

    插入到第i个位置

    LinkedList ListInsert(LinkedList L, int i, int x)
{//插入到第i位置操作
    LinkedList p, s;
    p = L;
    int j = 0;
    while (p && j < i-1)//p为第i-1处
    {
        p = p -> next;
        ++j;
    }
    if (!p || j > i-1)
    {
        printf("不存在该位置\n");
        exit(0);
    }
    s = (Node*)malloc(sizeof(Node));
    s -> data = x;
    s -> next = p -> next;
    p -> next = s;
    return L;
    // Node *pre;
    // pre = L;
    // int count;
    // for(count = 1; count < i; count++)
    //     pre = pre -> next;
    // Node *p;
    // p = (Node*)malloc(sizeof(Node));
    // p -> data = x;
    // p -> next = pre -> next;
    // pre -> next = p;
    //return L;
}

  6. 单链表的删除操作

    LinkedList ListDelete(LinkedList L, int x)
{//删除值为x的结点
    Node *p, *pre;
    p = L -> next;
    while(p -> data != x)
    {
        pre = p;
        p = p ->next;
    }
    pre -> next = p -> next;
    free(p);
    return L;
}
int ListDeletei(LinkedList L, int i)
{//删除第i处的结点，并取出值
    LinkedList pre, q;//q为第i个结点
    pre = L;//pre指向第i个结点的前驱
    int j = 0;
    int e;
    while ((pre->next) && j < i-1)
    {
        pre = pre -> next;
        ++j;
    }
    if (!(pre->next) || j > i-1)
    {
        printf("不存在该位置\n");
        exit(0);
    }
    q = pre -> next;
    pre -> next = q -> next;
    e = q -> data;
    free(q);
    return e;
}

二、双向链表

  1. 双向链表简称为双链表，在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

    image-20230319093746932

    typedef struct DouList
{
    int data;
    struct DouList *pre;
    struct DouList *next;
} DouList, *DoubList;

  2. 双链表的创建

    双链表的头结点是有元素的，与带头结点的单链表不同。

    DoubList initLin(DoubList head)
{
    int num, pos = 1, in;
    //结点数，当前位置，输入数据
    printf("input node num:");
    scanf("%d", &num);
    if(num < 1)
        return NULL;
    head = (DouList*)malloc(sizeof(DouList));
    head -> pre = NULL;
    head -> next = NULL;
    printf("input No.%d:", pos++);
    scanf("%d", &in);
    head -> data = in;

    DouList *list = head;
    while (pos <= num)
    {
        DouList * body = (DouList*)malloc(sizeof(DouList));
        body -> pre = NULL;
        body -> next = NULL;
        printf("input No.%d:", pos++);
        scanf("%d", &in);
        body -> data = in;
        list -> next = body;
        body -> pre = list;
        list = list -> next;
        return head;
    }
    return head;
}

  3. 双链表的插入操作

    DoubList InsertList(DoubList head, int x, int i)
{
    DouList *temp = (DouList*)malloc(sizeof(DouList));
    temp -> data = x;
    temp -> pre = NULL;
    temp -> next = NULL;
    if(1 == i)//插入到表头
    {
        temp -> next = head;
        head -> pre = temp;
        head = temp;
    }
    else
    {
        DouList *body = head;
        for(int j = 1; j < i-1; j++)
        {
             body = body -> next;
        }
        if (body -> next == NULL)//插在表尾
        {
            body -> next = temp;
            temp -> pre = body;
        }
        else
        {
            body -> next -> pre = temp;
            temp -> next = body -> next;
            body -> next = temp;
            temp -> pre = body;
        }
    }
    return head;
}

  4. 双链表的删除操作

    void Deletev(DoubList head, int x)
{
    DouList *p = head;
    if(p -> data == x && p -> next == NULL)
    {
        printf("only one number\n");
        head = NULL;
        free(p);
        printf("delete done!\n");
    }
    else if(p -> data == x && p -> next != NULL)
    {//first
        head = head -> next;
        head -> pre = NULL;
        free(p);
        printf("delete done!\n");
    }
    else if(p -> next != NULL)
    {
        while (p -> data != x)
            p = p -> next;
        if(p -> next == NULL)//最后一个元素
        {
            p -> pre -> next = NULL;
            free(p);
            printf("delete done!\n");
        }
        else
        {
            p -> pre -> next = p -> next;
            p -> next -> pre = p -> pre;
            free(p);
            printf("delete done!\n");
        }    
    }    
}

  5. 双向链表的遍历

    void printDList(DoubList head)
{
    DouList *p = head;
    int pos = 1;
    while (p)
    {
        printf("No.%d: %d\n", pos++, p -> data);
        p = p -> next;
    }
}

三、循环单链表

  1. 非循环链表的尾结点指向空（NULL），而循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）。

    typedef struct CirList{
    int data;
    struct list *next;
}CirList; //data为存储的数据，next指针为指向下一个结点

  2. 循环单链表初始化

    CirList *initClist()
{
    CirList *head = (CirList*)malloc(sizeof(CirList));
    if(head == NULL)
    {
        printf("create failed!");
        exit(0);
    }
    else
    {
        head -> next = NULL;
        return head;
    }
}
//main()中
CirList *L = initClist();
L -> next = L;

  3. 循环链表的创建

    int insert_List(CirList *head)
{//插在表尾
    int data;   
    printf("请输入要插入的元素：");
    scanf("%d",&data);
  
    CirList *node=initClist();
    node->data=data;
    //初始化一个新的结点，准备进行链接
  
    if(head!=NULL)
    {
        CirList *p=head;
        //找到最后一个数据
        while(p->next!=head)
        {
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else
    {
        printf("头结点已无元素\n");
        return 0;
    } 
}

  4. 循环单链表的插入

    CirList *insert_list(CirList *head,int pos,int data)
{
    //三个参数分别是链表，位置，参数
    CirList *node=initlist();  //新建结点
    CirList *p=head;       //p表示新的链表
    CirList *t;
    t=p;
    node->data=data;
    if(head!=NULL)
    {
        for(int i=1;i<pos;i++){
            t=t->next;  //走到需要插入的位置处
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}

  5. 循环单链表的删除

    int delete_list(CirList *head) //删除元素
{
    if(head == NULL) 
    {
        printf("链表为空！\n");
        return 0;
    }
//建立临时结点存储头结点信息（目的为了找到退出点）
//不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
//循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    CirList *temp = head;          
    CirList *ptr = head->next;
    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);
  
    while(ptr != head) //至少有两个元素
    {
        if(ptr->data == del) 
        {
            if(ptr->next == head) 
            { 
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;    //核心删除操作代码
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;//temp是ptr的前驱结点
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}

  6. 循环单链表的遍历

    int display(CirList *head)//遍历元素
{
    if(head != NULL) 
    {
        CirList *p  = head;
        while(p->next != head)//遍历头结点到，最后一个数据
        {
            printf("%d ",p->next->data);
            p = p->next;
        }
        return 1;
    } 
    else 
    {
        printf("头结点为空!\n");
        return 0;
    }
}

第三章 栈和队列

一、栈

  1. 栈（stack）是一个线性的数据结构，规定这个数据结构只允许在其中一端进行操作，并禁止直接访问除这一端以外的数据。

  2. 栈结点的设计

    除单链表的结构外，额外添加一个结构体，其主要功效就是设定允许操作元素的指针以及确定栈何时为空：

    • 法一：包括了一个永远指向栈头的指针top和一个计数器count记录元素个数，当count为0时为空；
    • 法二：设计一个指针top和一个指针bottom分别指向栈头和栈尾，两者指向同一个空间时为栈为空。
    #define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
/* 链栈结点结构 */
typedef struct StackNode
{
	ElemType data;
	struct StackNode *next;
}StackNode;

/* 链栈结构 */
typedef struct LinkStack
{
	StackNode  *top;
	int count;
}LinkStack;

  3. 初始化

    Status initStack(LinkStack **stack)
{
	// 注意要给链栈分配内存
	*stack = (LinkStack *)malloc(sizeof(LinkStack));

	(*stack)->top = NULL; // 链栈的空其实就是 top=NULL 的时候
	(*stack)->count = 0;

	return TRUE;
}

  4. 入栈

    // 进栈操作
Status push(LinkStack *stack, ElemType e)
{
	StackNode  *s = (StackNode  *)malloc(sizeof(StackNode));
	s->data = e;
	s->next = stack->top; // 把当前的栈顶元素赋值给新结点的直接后继，见图中①
	stack->top = s; // 将新的结点s赋值给栈顶指针，见图中②
	stack->count++;

	return TRUE;
}

  5. 出栈

    // 出栈操作
Status pop(LinkStack *stack, ElemType *e)
{
	StackNode  *p;
	if (isEmpty(stack))
		return FALSE;
	*e = stack->top->data;
	p = stack->top; // p用来存储要删除的栈顶结点，见图中③
	stack->top = stack->top->next; // 使得栈顶指针下移一位，指向后一结点，见图中④
	free(p); // 释放结点p
	stack->count--;

	return TRUE;
}

  6. 栈的遍历：在栈不为空的情况下，一次从栈顶元素向下访问，直到指针指向空（即到栈尾）为结束。（逆序输出）

    // 遍历栈操作
Status traverseStack(LinkStack *stack)
{
	StackNode  *p;
	p = stack->top;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");

	return TRUE;
}

  7. 其他

    // 清除栈操作
Status clearStack(LinkStack *stack)
{
	StackNode  *p;
	StackNode  *q;
	p = stack->top;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	stack->count = 0;

	return TRUE;
}

// 判断是否为空栈
Status isEmpty(LinkStack *stack)
{
	return stack->count == 0 ? TRUE : FALSE;
}

// 获得栈顶元素
Status getTop(LinkStack *stack, ElemType *e)
{
	if (stack->top == NULL)
		return FALSE;
	else
		*e = stack->top->data;

	return TRUE;
}

// 获得栈的长度
int getLength(LinkStack *stack)
{
	return stack->count;
}

  8. 顺序栈

    • 栈空时：栈顶指针（top）= -1；
    • 栈满时：栈顶指针（top）= MAXSIZE-1；
    • 栈未满：就是栈中存在元素，top 指针还未达到 MAXSIZE-1。
    #define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int ElemType; // ElemType类型根据实际情况而定，这里假设为int 
/* 顺序栈结构 */
typedef struct SeqStack
{
	ElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SeqStack;

  9. 其他

    // 初始化栈操作
Status initStack(SeqStack **stack)
{
	*stack = (SeqStack *)malloc(sizeof(SeqStack));
	(*stack)->top = -1;

	return TRUE;
}

// 进栈操作
Status push(SeqStack *stack, const ElemType e)
{
	if (stack->top == MAXSIZE - 1) // 判断是否栈满
	{
		return FALSE;
	}
	stack->top++; // 栈顶指针加1
	stack->data[stack->top] = e; // 将新插入元素赋值给栈顶空间

	return TRUE;
}

// 出栈操作
Status pop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1) // 判断是否空栈
		return FALSE;

	*e = stack->data[stack->top];   // 将要删除的栈顶元素赋值给e
	stack->top--;               // 栈顶指针减1

	return TRUE;
}

// 遍历栈操作
Status traverseStack(SeqStack *stack)
{
	for (int i = 0; i <= stack->top; i++)
		printf("%d ", stack->data[i]);
	printf("\n");

	return TRUE;
}

// 清空栈操作
Status clearStack(SeqStack *stack)
{
	stack->top = -1;

	return TRUE;
}

// 判断是否为空
Status isEmpty(SeqStack *stack)
{
	return stack->top == -1 ? TRUE : FALSE;
}

// 获得栈顶元素
Status getTop(SeqStack *stack, ElemType *e)
{
	if (stack->top == -1)
		return FALSE;
	else
		*e = stack->data[stack->top];

	return TRUE;
}

// 获取栈的长度
int getLength(SeqStack *stack)
{
	return stack->top + 1;
}

二、队列

  1. 顺序队列：用数组存储队列，为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针：front 指针指向队头元素，rear 指针指向队尾元素的下一个位置，当 front=rear 时，为空队列。

    typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构 */
typedef struct SeqQueue
{
    ElemType data[MAXSIZE];
    int front;      /* 头指针 */
    int rear;       /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SeqQueue;

  2. 解决 “假溢出” 的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为顺序循环队列。

    • 办法一是设置一个标志变量 flag， 当 front == rear，且 flag = 0 时为队列空，当 front== rear，且 flag= 1 时为队列满。
    • 办法二是当队列空时，条件就是 front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲位置。

  3. 针对法二：若队列的最大尺寸为 QueueSize，那么队列满的条件是(rear+1) % QueueSize == front ，因此通用的计算队列长度公式为：(rear - front + QueueSize) % QueueSize 。

    注意：front 指针和 rear 指针后移不能直接使用 ++，而要使用Q->front = (Q->front + 1) % MAXSIZE，因为到达数组尾后需要移动到数组开头。

  4. 程序实现

    #define TRUE 1
#define FALSE 0
#define MAXSIZE 5 /* 存储空间初始分配量 */

typedef int Status;
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
// 初始化队列操作
Status initQueue(SeqQueue *Q)
{
	Q->front = 0;
	Q->rear = 0;

	return  TRUE;
}

// 入队操作
Status enQueue(SeqQueue *Q, const ElemType e)
{
	// 判断队列是否已满
	if ((Q->rear + 1) % MAXSIZE == Q->front) 
		return FALSE;

	Q->data[Q->rear] = e; // 将元素e赋值给队尾
	Q->rear = (Q->rear + 1) % MAXSIZE; // rear指针向后移一位置，若到最后则转到数组头部

	return  TRUE;
}

// 出队操作
Status deQueue(SeqQueue *Q, ElemType *e)
{
	// 判断是否为空队
	if (Q->front == Q->rear) 
		return FALSE;

	*e = Q->data[Q->front]; // 将队头元素赋值给e
	Q->front = (Q->front + 1) % MAXSIZE; // front指针向后移一位置,若到最后则转到数组头部

	return  TRUE;
}

// 遍历队列操作
Status tarverseQueue(const SeqQueue Q)
{
	int cur = Q.front; // 当前指针
	while (cur != Q.rear) // 直到cur指向了队尾元素的下一个位置，即Q.rear，结束循环
	{
		printf("%d ", Q.data[cur]);
		cur = (cur + 1) % MAXSIZE; // 当前指针向后推移
	}
	printf("\n");

	return TRUE;
}

// 清空队列操作
Status clearQueue(SeqQueue *Q)
{
	Q->front = Q->rear = 0;

	return TRUE;
}

// 判断是否为空队列
Status isEmpty(const SeqQueue Q)
{
	return Q.front == Q.rear ? TRUE : FALSE;
}

// 获得队头元素
Status getHead(const SeqQueue Q, ElemType *e)
{
	if (Q.front == Q.rear) // 判断是否为空队列
		return FALSE;
	*e = Q.data[Q.front];

	return TRUE;
}

// 获得队列的长度
int getLength(const SeqQueue Q)
{
	return  (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

  5. 链队列

    typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 结点结构 */
typedef struct QNode 
{
	ElemType data;
	struct QNode *next;
}QNode;

/* 队列的链表结构 */
typedef struct			
{
	QNode *front; // 队头指针
	QNode *rear; // 队尾指针
}LinkQueue;

  6. 基本操作：

    // 初始化链队列操作
Status initQueue(LinkQueue *Q)
{
	Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
	if (!Q->front)
		return FALSE;
	Q->front->next = NULL;
	return TRUE;
}

// 入队操作
Status enQueue(LinkQueue *Q, ElemType e)
{
	QNode *s = (QNode *)malloc(sizeof(QNode));
	if (!s)
		return FALSE;
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;	// 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中①
	Q->rear = s; // 把当前的s设置为队尾结点，rear指向s，见图中②
	return TRUE;
}

/*出队操作就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点*/
Status deQueue(LinkQueue *Q, ElemType *e)
{
	QNode *p;
	if (Q->front == Q->rear)
		return FALSE;
	p = Q->front->next; // 将欲删除的队头结点暂存给p，见图中①
	*e = p->data; // 将欲删除的队头结点的值赋值给e
	Q->front->next = p->next; // 将原队头结点的后继p->next赋值给头结点后继，见图中②
	if (Q->rear == p) // 若队头就是队尾，则删除后将rear指向头结点，见图中③
		Q->rear = Q->front;
	free(p);

	return TRUE;
}

// 遍历队列操作
Status tarverseQueue(const LinkQueue Q)
{
	QNode *p;
	p = Q.front->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return TRUE;
}

// 销毁队列操作
Status destroyQueue(LinkQueue *Q)
{
	while (Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
	return TRUE;
}

// 清空队列操作
Status clearQueue(LinkQueue *Q)
{
	QNode *p;
	QNode *q;

	Q->rear = Q->front;
	p = Q->front->next;
	Q->front->next = NULL;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	return TRUE;
}

// 判断是否为空队列
Status isEmpty(const LinkQueue Q)
{
	return Q.front == Q.rear ? TRUE : FALSE;
}

// 获得队头元素
Status getHead(const LinkQueue Q, ElemType *e)
{
	QNode *p;
	if (Q.front == Q.rear)
		return FALSE;
	p = Q.front->next;
	*e = p->data;
	return TRUE;
}

// 获得队列的长度
int getLength(const LinkQueue Q)
{
	int i = 0;
	QNode *p;
	p = Q.front;
	while (Q.rear != p)
	{
		i++;
		p = p->next;
	}
	return i;
}

第四章 字符串

一、字符串模式匹配

  1. 暴力匹配

    /* 
在文本txt中寻找模式pat 
若找到则返回文本中**模式出现时的首个字母的索引i** 
若没找到（也就是txt中不存在pat模式），返回-1 
*/ 
int baolipipei(char txt[], char pat[])
{
    int i, j;
    int len1 = strlen(txt);
    int len2 = strlen(pat);
    for (i = 0; i <= len1-len2; i++)
    {
        for (j = 0; j < len2; j++)
            if(txt[i+j] != pat[j])
                break;
        if(j == len2)
            return i;
    }
    return -1;
}//O(m*n)

  2. KMP算法

    #include<iostream>
#include<cstring>
using namespace std;
void kmp_next(char x[], int m, int next[]);
int kmp(char x[], int m, char y[], int n);

int main(void)
{
    char zhu[30] = "googooglegobgooglegooogoogle";
    char pi[10] = "google";
    //cout << strlen(pi) << endl;
    int count = kmp(pi, 6, zhu, 28);
    cout << count << endl;

    return 0;
}

void kmp_next(char x[], int m, int next[])//x为模式串，m为模式串长
{
    next[1] = 0;
    int i = 1, j = 0; //i是next的索引，j是x的下标，1开始
    // while (i <= m)
    // {
    //     if(j == 0 || x[i] == x[j]) next[++i] = ++j;
    //     else j = next[j];
    // }
    //优化
    while(i <= m)
    {
        if(j == 0 || x[i] == x[j])
        {
            j++;
            i++;
            if(x[i] == x[j])//当两个字符相同时，就跳过
                next[i] = next[j];
            else
                next[i] = j;
        }
        else
            j = next[j];
    }
}

int kmp(char x[], int m, char y[], int n)//x模式串，y主串
{
    int i, j;
    int ans = 0;
    int next[100];
    kmp_next(x, m, next);
    i = j = 0;
    while(i < n)
    {//x[j]是模式串
        if(j == 0 || y[i] == x[j])
        {
            i++;
            j++;
        }
        else j = next[j];
        // while(j != 0 && y[i] != x[j])
        //     j = next[j];
        // i++;
        // j++;
        if(j >= m)
        {
            ans++;
            j = next[j];
        }
    }
    return ans;//返回模式串在主串中出现次数，在主串位置是i-m
}

二、C++string类

  1. C++中的string字符串类型

    在C++中，通过模板类的操作创建了string类

    #include<iostream>
#include<string>
using namespace std;
int main(){
    string str;       //创建空字符串
  
    string str1 = "Hello hhhcpp.com";
    cout<< str1 <<endl;   //Hello hhhcpp.com
  
    string str2(str1);
    cout << str2 << endl;   //Hello hhhcpp.com
  
    string str3(str1,6);	//丛str1[6]开始取到结束
    cout << str3 << endl;   //hhhcpp.com
  
    string str4(str1,6,6);	//丛str1[6]开始取6个
    cout << str4 << endl;   //hhhcpp
  
    string str5(5,'D'); //str5为5个D
    cout << str5 << endl;   //DDDDD
  
    string str6(str1.begin(),str1.end()); 
    cout << str6 << endl;   //Hello hhhcpp.com
    return 0;
}

  2. 比较和连接

    string str1 = "Hello";
string str2 = "Hello";
if(str1 == str2) 
    cout << "两者相等" << endl;
else
    cout << "两者不相等" << endl;

string totalystring = "a";
cout << totalystring + "b" + "c" + "d" << endl;

  3. 获取长度length，获取当前字符串的长度

    str.length();//C中strlrn(str)
str.size();//获取大小size，获取当前字符串的大小，某种意义上由于字符串的每一个字符开辟的空间均完全相等，因此size可以代替length

  4. strlen(str)和str.length()和str.size()三者的区别

    strlen(str)和str.length()和str.size()都可以求字符串长度。其中 str.length() 和 str.size() 是用于求string类对象的成员函数，而 strlen(str) 是用于求字符数组的长度，其参数是char*，当数组名作为参数传入时，实际上数组就退化成指针了。
返回的长度大小不包括 '\0'。

  5. 其他

    //判断是否为空empty
str.empty();
//填充内容resize：
原型为void resize(int len,char chr)
把字符串当前大小置为len，多去少补，多出的字符chr填充不足的部分，resize将会修改该字符串的占用空间。
string str = "HEllo";
str.resize(8,'K');
cout << str << endl;

三、矩阵乘法

  1. 两个矩阵的乘法仅当第一个矩阵A的列数和另一个矩阵B的行数相等时才能定义。

    #include <iostream>
using namespace std;
#define ROW 100
#define COL 100
int main()
{
	int a[ROW][COL], b[ROW][COL], c[ROW][COL];
	int i, j, k, m, n, q, p;
	cin >> m >> n; // 输入第一个矩阵行数列数
	cin >> p >> q; // 输入第二个矩阵行数列数
	for (i = 0; i < m; ++i)
		for (j = 0; j < n; ++j)
			cin >> a[i][j]; // 输入第一个矩阵
	for (i = 0; i < p; ++i)
		for (j = 0; j < q; ++j)
			cin >> b[i][j]; // 输入第二个矩阵
	for (i = 0; i < m; ++i) // 矩阵相乘
	{
		for (j = 0; j < q; ++j)
		{
			c[i][j] = 0;
			for (k = 0; k < n; ++k)
				c[i][j] += a[i][k] * b[k][j];
		}
	}
	for (i = 0; i < m; ++i) // 输出相乘后的矩阵
	{
		for (j = 0; j < q; ++j)
			cout << c[i][j] << " ";
		cout << endl;
	}
	return 0;
}

  2. 卷积：用一个模板和另一个模板对比，进行卷积运算。目的是是目标与目标之间的差距变得更大，卷积在数字图像处理中常见的应用为锐化和边缘提取。

    • 假设一个卷积核h，将其倒置（翻转180°）

    矩阵翻转

    image-20230322181931132

    • 有一个待处理矩阵x：

      image-20230322181521426

    • h*x = Y：将卷积核h的中心对准x的第一个元素，然后对应元素相乘后相加，没有元素的地方补0。

      image-20230322182256722

    • Y11 = 10+20+10+00+01+02+-10+-25+-1*6=-16.

    • 每个元素都像这样计算出来就可以得到一个输出矩阵，就是卷积结果。

      image-20230322182451531

    • 零填充，单位滑动。

第五章 树

一、树的性质

  1. 树是一种非线性数据结构，树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

  2. 树的定义：n个结点组成的有限集合。n=0，空树；n>0,1个根结点，m个互不相交的有限集，每个子集为根的子树。

  3. 树：

    • 结点的度：树中某个结点的子树的个数。

    • 树的度：树中各结点的度的最大值。

    • 分支结点：度不为零的结点。

    • 叶子结点：度为零的结点。

    • 路径：i->j；路径长度：路径经过结点数目减1。

    • 孩子结点：某结点的后继结点；双亲结点：该结点为其孩子结点的双亲结点（父母结点）；兄弟结点：同一双亲的孩子结点；子孙结点：某结点所有子树中的结点；祖先结点：从树结点到该结点的路径上的结点。

    • 结点的层次：根结点为第一层（以此类推）；树的高度：树中结点的最大层次。

    • 有序树：树中结点子树按次序从左向右安排，次序不能改变；无序树：与之相反

    • 森林：互不相交的树的集合。

  4. 树的性质：

    • 树的结点树为所有结点度数（边）加1（加根结点）。
    • 度为m的树中第i层最多有m^(i-1)个结点。
    • 高度为h的m叉树至多(m^h-1)/(m-1)个结点。
    • 具有n个结点的m叉树的最小高度为logm( n(m-1) + 1 ) 向上取整。

二、二叉树的性质

  1. 二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

  2. 二叉树的特点

    1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

    2）左子树和右子树是有顺序的，次序不能任意颠倒。

    3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

  3. 二叉树的性质

    性质1：二叉树第i层上的结点数目最多为 2的(i-1)次方个节点(i≥1)。
    性质2：深度为k的二叉树至多有2的k次方-1个结点(k≥1)。
    性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
    性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

  4. 满二叉树

    满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

    满二叉树的特点有：

    1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

    2）非叶子结点的度一定是2。

    3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

  5. 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

三、二叉树的操作

  1. 设计代码

    #include <iostream>
using namespace std;
typedef struct biTreeNode
{
    int data;
    struct biTreeNode *left;
    struct biTreeNode *right;
} Node;
typedef struct
{
    biTreeNode *root;
} Tree;

void create(Tree *tree, int value);
void inorder(biTreeNode *node);

int main(void)
{
    Tree tree;
    tree.root = NULL;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        create(&tree, temp);
    }
    inorder(tree.root);

    return 0;
}

void create(Tree *tree, int value)
{
    biTreeNode *node = (biTreeNode *)malloc(sizeof(biTreeNode));
    node->data = value;
    node->left = NULL;
    node->right = NULL;

    if (tree->root == NULL)
        tree->root = node;
    else
    {
        biTreeNode *temp = tree->root;
        while (temp != NULL)
        {
            if (value < temp->data) // 小于就进左孩子
                if (temp->left == NULL)
                {
                    temp->left = node;
                    break;
                }
                else
                {
                    temp = temp->left;
                }
            else // 大于为右孩子
            {
                if (temp->right == NULL)
                {
                    temp->right = node;
                    break;
                }
                else
                {
                    temp = temp->right;
                }
            }
        }
    }
}

void inorder(biTreeNode *node)
{
    if (node != NULL)
    {
        inorder(node->left);
        cout << node->data;
        inorder(node->right);
    }
}

  2. 二叉树的遍历

    //先序遍历 根左右
void preorder(biTreeNode *node)
{
    if (node != NULL)
    {
        cout << node->data << " ";
        preorder(node->left);
        preorder(node->right);
    }
}
//中序遍历 左根右
void inorder(biTreeNode *node)
{
    if (node != NULL)
    {
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
}
//后序遍历 左右根
void postorder(biTreeNode *node)
{
    if (node != NULL)
    {
        postorder(node->left);
        postorder(node->right);
        cout << node->data << " ";
    }
}

  3. 前缀表达式（波兰式）：符号迁移，波兰式表达形式不需要括号，利用栈中缀转后缀。借助括号的形式表示优先级。

  4. 深度优先遍历（DFS）

    vector<int> a;    // 记录每次排列
vector<int> book; // 标记是否被访问
int n;
void DFS(int cur, int k, vector<int> &nums)
{
    if (cur == k)
    { // k个数已经选完，可以进行输出等相关操作
        for (int i = 0; i < cur; i++)
        {
            printf("%d ", a[i]);
        }
        return;
    }
    for (int i = 0; i < k; i++)
    { // 遍历 n个数，并从中选择k个数
        if (book[nums[i]] == 0)
        {                          // 若没有被访问
            a.push_back(nums[i]);  // 选定本输，并加入数组
            book[nums[i]] = 1;     // 标记已被访问
            DFS(cur + 1, n, nums); // 递归，cur+1
            book[nums[i]] = 0;     // 释放，标记为没被访问，方便下次引用
            a.pop_back();          // 弹出刚刚标记为未访问的数
        }
    }
}

四、森林

  1. 森林：m（>=0）棵互不相交的树的集合 ，可以是0棵树。

  2. 树转换成二叉树：左孩子右兄弟法。树转换成二叉树其右子树一定为空。

  3. 二叉树转换成树：左孩子右兄弟法，逆。

  4. 二叉树与森林转换：左孩子右兄弟。

五、哈夫曼树

  1. 哈夫曼树（Huffman Tree），又名：最优二叉树。给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

  2. 名词解释：

    • 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。
    • 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。
    • 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。
    • 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
    • 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。

  3. 哈夫曼树的建立与查找算法

    查找算法：查找权重值最小的两个结点的思想是：从待处理数据的头部位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

    • 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
    • 如果介于两个结点权重值之间，替换原来较大的结点；

  4. 哈夫曼编码：(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。

    • 主要目的是根据使用频率来最大化节省字符（编码）的存储空间。
    • 霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合，也包括文件传输的场合。
    • 如果考虑到进一步节省存储空间，就应该将出现概率大（占比多）的字符用尽量少的0-1进行编码，也就是更靠近根（节点少），这也就是最优二叉树-哈夫曼树。

第六章 图

一、图的基本概念

  1. 一个图G是一个二元组，即序偶<V,E>，或记作G=<V,E> ，其中V是有限非空集合，称为G的顶点集,V中的元素称为顶点或结点；E称为 G的边的集合，所有的边ei都属于E，都有v中的结点与之对应，称ei为 G的边。
  2. 图的基本概念
    • 无向图：每条边都是无向边的图。
    • 有向图：每条边都是有向边的图。
    • 混合图：在一个图中，有些边是有向边，另一些边是无向边。
    • 有限图：一个图的点集和边集都是有穷集的图。
    • 零图：边集为空集的图。
    • 平凡图：仅有一个结点而没有边构成的图。
    • 关联：若有ei=(u,v) 且ei属于E ，则称u是和v相关联的。
    • 孤立点：无边关联的点。
    • 自环：若一条边所关联的两个结点重合，则称此边为自环。
    • 邻接：关联于同一条边的两个点称为邻接的；关联于同一个点的两条边和 是邻接的（或相邻的）。
  3. 在任意图中，度数为奇数的点必然有偶数个或0个。
  4. 所有点入度之和等于出度之和。

二、图的存储

  1. 无向图的邻接矩阵

    邻接矩阵存在以下缺点

    a) 浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素

    b) 浪费时间—— 统计稀疏图中一共有多少条边

    #include <iostream>

using namespace std;

const int maxn = 105;
int adj[maxn][maxn] = {0}; // 定义邻接矩阵

int x, y; // 输入两条边
int n, m; // 供输入n对边 ,m个顶点 (x,y <= m)

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        adj[x - 1][y - 1] = 1;
        adj[y - 1][x - 1] = 1;
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << adj[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

  2. 有向图的邻接表

    #include <stdio.h>
#include <iostream>
#include <malloc.h>
#define maxSize 1000
using namespace std;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct
{
    int data;
    ArcNode *firstarc;
} Vnode;

// 可以利用结构体整体结构，也可以拆分结构体变为单独搜索
typedef struct
{
    Vnode adjlist[maxSize];
    int n, e;
} AGraph;

AGraph *graph;

// 插入链表末尾
void insertNode(ArcNode *node, ArcNode *newNode)
{
    ArcNode *p = node;
    while (p->nextarc != NULL)
    {
        p = p->nextarc;
    }
    p->nextarc = newNode;
}

void create()
{
    graph = (AGraph *)malloc(sizeof(AGraph));
    cout << "输入顶点的数目: " << endl;
    cin >> graph->n;
    cout << "输入图中边的数目: " << endl;
    cin >> graph->e;

    int u = -1, v = -1;
    for (int i = 0; i < graph->n; i++)
    {
        graph->adjlist[i].firstarc = NULL;
    }

    ArcNode *node;
    for (int i = 0; i < graph->e; i++)
    {
        cout << "请输入联通点A与B" << endl;
        cin >> u >> v;
        node = (ArcNode *)malloc(sizeof(ArcNode));
        node->adjvex = v;
        node->nextarc = NULL;
        graph->adjlist[u].data = u;
        if (graph->adjlist[u].firstarc == NULL)
        {
            // 边
            graph->adjlist[u].firstarc = node;
        }
        else
        {
            // 插入边
            insertNode(graph->adjlist[u].firstarc, node);
        }
    }
}

void travseTree()
{
    for (int i = 0; i < graph->n; i++)
    {
        if (graph->adjlist[i].firstarc != NULL)
        {
            cout << "与" << i << "连接的点有：";
            ArcNode *p = graph->adjlist[i].firstarc;
            while (p != NULL)
            {
                cout << p->adjvex << " ";
                p = p->nextarc;
            }
            cout << endl;
        }
    }
}

int main(void)
{
    create();
    travseTree();
    return 0;
}

  3. BFS

    void BFSL(int pos, pGraph G, int visited[30]) // 从pos点开始进行广度优先遍历无向图
{
    int queue[G->Vnum];     // 队列辅助BFS遍历
    int head = 0, tail = 0; // 队头、队尾指针
    Arcnode *p;
    queue[tail] = pos;
    visited[pos] = 1; // 标记遍历过
    tail++;
    while (head != tail)
    {
        pos = queue[head]; // 出队操作
        head++;
        printf("%d ", pos);
        p = G->vertice[pos].firstarc;
        while (p != NULL)
        {
            if (visited[p->adjvex] == 0) // 判断是否遍历过
            {
                queue[tail] = p->adjvex; // 入队操作
                visited[p->adjvex] = 1;  // 标记遍历过
                tail++;
            }
            p = p->next;
        }
    }
}

  4. DFS

    void dfs()//参数用来表示状态  
{  
    if(到达终点状态)  
    {  
        ...//根据需求添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝，去除一些不需要访问的场景，不一定i俺家
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
        }  
  
    }  
}

三、最小生成树

  1. 将给出的所有点连接起来（即从一个点可到任意一个点），且连接路径之和最小的图叫最小生成树。最小生成树属于一种树形结构（树形结构是一种特殊的图），或者说是直链型结构，因为当n个点相连，且路径和最短，那么将它们相连的路一定是n-1条。
  2. 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。
  3. 普利姆算法加点，克鲁斯卡尔算法加边。

四、最短路径

  1. 迪杰斯特拉(Dijkstra)算法
  2. 弗洛伊德(Floyd)算法

第七章 查找算法

一、顺序查找

  1. 从一些数据之中，找到一个特殊的数据的实现方法。查找算法与遍历有极高的相似性，唯一的不同就是查找算法可能并不一定会将每一个数据都进行访问，有些查找算法如二分查找等，并不需要完全访问所有的数据。

  2. 顺序查找：线性的从一个端点开始，将所有的数据依次访问，并求得所需要查找到的数据的位置，此时，线性查找可以称呼为遍历。

  3. 代码实现

    #include<iosteam>
using namespace std;
int main(){
    int Shangping[6]={10,10,9,10,10,10}
    for(int i=0;i<6;i++){
        if(Shangping[i]==9){
            printf("找到次品，他的位置在：%d",i+1);
        }
    }
    return 0;
}

二、二分查找

  1. 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，注意必须要是有序排列。

  2. 二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x

  3. 代码实现

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

// 二分查找算法，找不到就返回-1，找到了就返回值
int binary_search(int *list, int len, int target)
{
    int low = 0;
    int hight = len - 1;
    int middle;
    while (low <= hight)
    {
        middle = (low + hight) / 2;
        if (list[middle] = target)
        {
            printf("已找到该值，数组下标为:%d\n", middle);
            return list[middle];
        }
        else if (list[middle] > target)
        {
            hight = middle - 1;
        }
        else if (list[middle] < target)
        {
            low = middle + 1;
        }
    }
    printf("未找到该值");
    return -1;
}

int main()
{

    int a[] = {2, 4, 5, 8, 9, 44};
    int b = binary_search(a, sizeof(a) / 4, 5);
    printf("b=%d\n", b);
    printf("Hello world!\n");
    return 0;
}

三、分块查找

  1. 分块查找

    分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况，其核心有二索引表，二是分块处理。

  2. 分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。

    image-20230323130627544

四、二叉排序树

  1. 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。该树属于一种输入数据就默认产生一种顺序的数据结构。

  2. 性质：

    a) 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

    b) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

    c) 左、右子树也分别为二叉排序树；

    即对于每一个根结点，其左孩子永远小于根，右孩子永远大于根。

  3. 代码实现

    typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode /* 结点结构 */
{
    int data;                        /* 结点数据 */
    struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree t, int key, BiTree f, BiTree *p)
{
    if (!t) /*  查找不成功 */
    {
        *p = f;
        return FALSE;
    }
    else if (key == t->data) /*  查找成功 */
    {
        *p = t;
        return TRUE;
    }
    else if (key < t->data)
        return SearchBST(t->lchild, key, t, p); /*  在左子树中继续查找 */
    else
        return SearchBST(t->rchild, key, t, p); /*  在右子树中继续查找 */
}

  4. 插入

    struct BiTree
{
    int data;
    BiTree *lchild;
    BiTree *rchild;
};

// 在二叉排序树中插入查找关键字key
BiTree *InsertBST(BiTree *t, int key)
{
    if (t == NULL)
    {
        t = new BiTree();
        t->lchild = t->rchild = NULL;
        t->data = key;
        return t;
    }

    if (key < t->data)
        t->lchild = InsertBST(t->lchild, key);
    else
        t->rchild = InsertBST(t->rchild, key);

    return t;
}

// n个数据在数组d中，tree为二叉排序树根
BiTree *CreateBiTree(BiTree *tree, int d[], int n)
{
    for (int i = 0; i < n; i++)
        tree = InsertBST(tree, d[i]);
}

  5. 删除

    /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
    if(!*T) /* 不存在关键字等于key的数据元素 */ 
        return FALSE;
    else
    {
        if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
  
    }
}
/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
    {
        q=*p; *p=(*p)->lchild; free(q);
    }
    else if((*p)->lchild==NULL) /* 只需重接它的右子树 */
    {
        q=*p; *p=(*p)->rchild; free(q);
    }
    else /* 左右子树均不空 */
    {
        q=*p; s=(*p)->lchild;
        while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
        {
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
        if(q!=*p)
            q->rchild=s->lchild; /*  重接q的右子树 */ 
        else
            q->lchild=s->lchild; /*  重接q的左子树 */
        free(s);
    }
    return TRUE;
}

五、平衡二叉树

  1. 平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 其中最为经典当属AVL树。

  2. 平衡二叉树是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。

  3. 性质：

    • 它必须是一颗二叉查找树
    • 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
    • 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.
    • 只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去了平衡。

  4. 通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。各个调整的方法分为LL型、RR型、LR型和RL型4种类型，其余的操作与一般的树进行插入和修改数据无异。

  5. 代码

    #include<stdio.h>
#include<stdlib.h>
  
//结点设计 
typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    int height;
} BTNode;
  
int height(struct Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}
  
int max(int a, int b) {
    return (a > b) ? a : b;
}
  
BTNode* newNode(int key) {
    struct Node* node = (BTNode*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
  
//ll型调整 
BTNode* ll_rotate(BTNode* y) {
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;
  
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
  
    return x;
}
  
//rr型调整 
BTNode* rr_rotate(BTNode* y) {
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
  
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
  
    return x;
}
  
//判断平衡
int getBalance(BTNode* N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
  
//插入结点&数据
BTNode* insert(BTNode* node, int key) {
    if (node == NULL)
        return newNode(key);
  
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
  
    node->height = 1 + max(height(node->left), height(node->right));
  
    int balance = getBalance(node);
  
    if (balance > 1 && key < node->left->key) //LL型
        return ll_rotate(node);
  
    if (balance < -1 && key > node->right->key)     //RR型
        return rr_rotate(node);
  
    if (balance > 1 && key > node->left->key) {   //LR型
        node->left = rr_rotate(node->left);
        return ll_rotate(node);
    }
  
    if (balance < -1 && key < node->right->key) {   //RL型
        node->right = ll_rotate(node->right);
        return rr_rotate(node);
    }
  
    return node;
}
  
//遍历
void preOrder(struct Node *root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
  
int main() {
    BTNode *root = NULL;
  
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 3);
    root = insert(root, 4);
    root = insert(root, 4);
    root = insert(root, 5);
    root = insert(root, 6);
    root = insert(root, 9);
    root = insert(root, 8);
    root = insert(root, 7);
  
    printf("前序遍历：");
    preOrder(root);
    return 0;
}

第八章 排序

一、冒泡排序

  1. 从第一个元素开始逐个比较相邻的元素。如果第一个比第二个大（a[1]>a[2]），就交换他们两个。

    对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。此时在这一点，最后的元素应该会是最大的数，我们也称呼一遍这样的操作为：一趟冒泡排序。

    针对所有的元素重复以上的步骤，每一趟冒泡排序的最大值已放在最后，下一次操作则不需要将此最大值纳入计算计算。

    持续对每次对越来越少的元素，重复上面的步骤，直到没有任何一对数字需要比较，即完成冒泡排序。

    image-20230323160119801

    到了第四趟的时候，整个数据已经排序结束了，但是程序还在进行，直到第5，6，7趟结束程序才算真正的结束，这其实是一种浪费算力的表现。

  2. 代码

    #include <iostream>
using namespace std;
void bubble_sort(int a[], int n);
int main(void)
{
    int num[8] = {70, 50, 30, 20, 10, 70, 40, 60};
    int n = 7;
    bubble_sort(num, 7);
    for (int i = 0; i < n; i++)
    {
        cout << num[i] << endl;
    }
    return 0;
}

void bubble_sort(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i; j++)
        {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }//namespace std命名空间的使用，std自带了交换函数swap(a,b)
    }
}

  3. 最坏情况：O(n^2)

    最好情况：O(n)

    平均情况：O(n^2)

    空间复杂度：S(n)=O(1)

    稳定性：稳定排序

二、简单选择排序

  1. 设置两个记录i和j，i自数组第一个元素开始，j自i+1个元素开始。

    接着j遍历整个数组，选出整个数组最小的值，并让这个最小的值和i的位置交换（如果i选择的元素是最小的则不需要交换），我们称这个过程为一趟选择排序。

    i选中下一个元素(i++)，重复进行每一趟选择排序。

    持续上述步骤，使得i到达n-1处，即完成排序 。

  2. image-20230323161628741

  3. 代码

    #include <iostream>
using namespace std;
void select_sort(int a[], int n);
int main(void)
{
    int num[8] = {2, 10, 9, 4, 8, 1, 6, 5};
    int n = 8;
    select_sort(num, n);
    for (int i = 0; i < n; i++)
    {
        cout << num[i] << endl;
    }

    return 0;
}

void select_sort(int a[], int n)
{
    int min;
    for (int i = 0; i < n - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (a[min] > a[j])
                min = j;
        }
        swap(a[min], a[i]);
    }
}

  4. 每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完，我们只需要进行n-1趟排序即可，因为最后剩下的一个数据一定是整体数据中最大的数据。

  5. 最坏情况：O(n^2)

    最好情况：O(1) //即不需要排序，本身已是正序

    平均情况：O(n^2)

    空间复杂度：S(n)=O(1)

    稳定性：不稳定排序

三、直接插入排序

  1. 每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。

  2. image-20230323163134895

  3. 代码

    #include <iostream>
using namespace std;
void insert_sort(int a[], int n);
int main(void)
{
    int a[8] = {70, 50, 30, 20, 10, 70, 40, 60};
    int n = 8;
    insert_sort(a, n);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << ' ';
    }

    return 0;
}

void insert_sort(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        if (a[i] < a[i - 1]) // 后移插入
        {
            int temp = a[i];
            for (j = i - 1; j >= 0 && a[j] > temp; j--)
            {
                a[j + 1] = a[j];
            }
            a[j + 1] = temp; // 跳出是做过j--，但没有移动，所以j+1
        }
    }
}

  4. 最坏情况：O(N^2)

    最好情况：O(N^2)

    平均情况：O(N^2)

    稳定性：稳定排序

四、希尔排序

  1. 递减增量排序算法，是一种非稳定的更高效的插入排序。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

  2. 过程如下：

    1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
    2. 按增量序列个数 k，对序列进行 k 趟排序；
    3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

  3. image-20230323165944967

  4. 代码

    /*
 * 希尔排序
 * 参数说明：
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
#include <iostream>
using namespace std;
void shell_sort(int a[], int n);
int main(void)
{
    int num[8] = {80, 30, 60, 40, 20, 10, 50, 70};
    int n = 8;
    shell_sort(num, n);
    for (int i = 0; i < n; i++)
    {
        cout << num[i] << endl;
    }
    return 0;
}

void shell_sort(int a[], int n)
{
    int i, j, gap;
    // gap为步长，每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组，对每一组都执行直接插入排序
        for (i = 0; i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap)
            {
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，
                // 并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}

  5. 算法时间复杂度

    最坏情况：O(n^2)

    最好情况：O(n)

    平均情况：O(n^2)

    稳定性：不稳定排序

五、堆排序

  1. 堆是一种非线性的数据结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组。

  2. 按照堆的特点可以把堆分为大顶堆和小顶堆

    a)大顶堆：每个结点的值都大于或等于其左右孩子结点的值

    b)小顶堆：每个结点的值都小于或等于其左右孩子结点的值

  3. 代码

    #include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end)
{
    // 建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)
    {                                                  // 若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父节点大于子节点代表调整完毕，直接跳出函数
            return;
        else
        { // 否则交换父子内容再继续子节点和孙节点比较
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len)
{
    // 初始化，i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main()
{
    int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
    int len = (int)sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

  4. 算法时间复杂度

    最坏情况：O(n^2)

    最好情况：O(n)

    平均情况：O(nlogn)

    稳定性：不稳定排序

六、归并排序

  1. 将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并，归并排序的算法效率仅次于快速排序，是一种稳定的算法，需要建立两倍的数组空间，一般用于对总体而言无序，但是各子项又相对有序【并不是完全乱序】的情况比较适用。

  2. a)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

    b)设定两个指针，最初位置分别为两个已经排序序列的起始位置

    c)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

    重复步骤c直到某一指针超出序列尾

    将另一序列剩下的所有元素直接复制到合并序列尾

  3. image-20230323175449875

  4. 代码

    // 归并排序（C-递归版）
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

  5. 算法时间复杂度

    最坏情况O(nlogn)

    最好情况O(nlogn)

    平均情况O(nlogn)

    空间复杂度O(n) 注：归并排序需要创建一个与原数组相同长度的数组来辅助排序

七、快速排序

  1. 首先在数组中选择一个基准点，然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫描，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。

    以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

  2. image-20230323180124494

  3. 代码

    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);
}

  4. 算法时间复杂度

    最坏情况：O(n^2)

    最好情况：O(nlogn)

    平均情况：O(nlogn)

    稳定性：不稳定排序

附录

image-20230323180441922

文章作者: nusqx
文章链接: https://nusqx.top
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 nusqx !
算法 cpp 数据结构 C语言
赏
评论
  目录