数据结构-

欢乐狗 · 2024-9-1 13:14:45

代码库：dataStructure: 数据结构部门代码

数据结构

数据结构是计算机存储、构造数据的方式，以便高效地访问和修改数据。它主要包括数据的逻辑结构和物理存储结构。
逻辑结构

聚集：元素之间无特定关系。
线性结构（如列表、栈、队列）：元素之间一对一的关系。
树形结构：元素之间一对多的关系。
图结构：元素之间多对多的关系。

存储结构

次序存储：数据元素在物理内存中连续存放，通过数组实现。
链式存储：数据元素在物理内存中非连续存放，通过指针（或引用）连接。
索引存储：在存储数据的同时，创建索引表，以快速定位数据。
散列存储（哈希存储）：通过哈希函数计算数据的存储位置，实现快速存取。

算法

算法是解决特定问题的一系列步骤的聚集。

特性：有穷性（步骤有限）、确定性（每一步都有明确寄义）、可行性（步骤可在有限时间内完成）、输入（0个或多个）、输出（1个或多个）。

时间复杂度和空间复杂度

时间复杂度：衡量算法执行时间随输入规模增长而增长的速率。常用大O表示法（如O(n)，O(n^2)，O(log n)等）来形貌。
空间复杂度：衡量算法执行过程中所需的最大存储空间。同样使用大O表示法来形貌。

线性表

线性表是最基本的数据结构之一，具有次序性和线性关系。

特点：
- 非空线性表有且仅有一个头节点和一个尾节点。
- 头节点无前驱，尾节点无后继。
- 除头尾节点外，每个节点有且仅有一个前驱和一个后继。
实现方式：
- 次序表：基于数组实现，支持随机访问，但插入和删除操纵可能须要移动大量元素。
- 链表：基于节点和指针（或引用）实现，插入和删除操纵高效，但不支持随机访问。
操纵：增、删、改、查、求长度等。

线性表的进一步细节

次序表：
- 静态分配：数组大小固定，不可动态改变。
- 动态分配：使用动态数组（如C++中的std::vector），大小可按需调解。
链表：
- 单链表：每个节点包含数据和指向下一个节点的指针。
- 双链表：每个节点包含数据、指向前一个节点的指针和指向下一个节点的指针。
- 循环链表：尾节点指向头节点，形成环。

代码：
1、动态数组线性表

#include "dynamicArray.h"
DA * initList(){
DA* header = (DA *)malloc(sizeof(DA));
ERROE_CHECK(NULL,header,"malloc");
header->data = (type *)malloc(sizeof(type));
ERROE_CHECK(NULL,header->data,"malloc");
header->index = -1;
header->data_size = 1;
printf("11111\n");
return header;
}
void addList(DA * header,int val){
if (header->index+1 == header->data_size)
{
int new_size = header->data_size*2;
header->data = (type *)realloc(header->data,new_size*sizeof(type));
if (NULL == header->data)
{
perror("realloc");
exit(1);
}
header->data_size = new_size;
}
header->data[++header->index] = val;
}
void showList(DA *header){
for (size_t i = 0; i <= header->index; i++)
{
printf("%d ",header->data[i]);
}
puts("");
}
void delList(DA * header,int index){
if (header->index+1 <= header->data_size / 2)
{
int new_size = header->data_size / 2;
header->data = (type *)realloc(header->data,new_size*sizeof(type));
if (NULL == header->data)
{
perror("realloc");
exit(1);
}
header->data_size = new_size;
}
if (index <= header->index)
{
for (size_t i = index; i < header->index; i++)
{
header->data[i] = header->data[i+1];
}
header->index--;
}
}

复制代码

2、平凡数组线性表

#include "seqList.h"
#include <stdlib.h>
#include <stdio.h>
#include <43func.h>
LT *createList()
{
LT *header = (LT *)malloc(sizeof(LT));
ERROE_CHECK(NULL, header, "malloc");
header->count = -1;
return header;
}
bool insertList(LT *header, type data)
{
if (isFullList(header))
{
printf("Full\n");
exit(1);
}
if (header->count < LEN)
{
header->count++;
header->data[header->count] = data;
return true;
}
else
{
return false;
}
}
void showList(LT *header)
{
if (isEmptyList(header))
{
puts("empty!");
exit(1);
}
for (size_t i = 0; i <= header->count; i++)
{
printf("%d ", header->data[i]);
}
puts("");
}
// full
bool isFullList(LT *header)
{
return (LEN - 1 == header->count) ? true : false;
}
// empty
bool isEmptyList(LT *header)
{
return (-1 == header->count) ? true : false;
}
// length
int lengthList(LT *header)
{
return header ? header->count + 1 : -1;
}
// select
/// @brief 表头，要查找的值
/// @return 索引，
int selectListVal(LT *header, type val)
{
if (isEmptyList(header))
{
puts("empty");
exit(1);
}
for (size_t i = 0; i <= header->count; i++)
{
if (val == header->data[i])
{
return i;
}
}
return -1;
}
/// @brief header valSrc valDest
/// @return void
void changeListVal(LT *header, type valSrc, type valDest)
{
int ret = selectListVal(header, valSrc);
while (ret >= 0)
{
header->data[ret] = valDest;
ret = selectListVal(header, valSrc);
}
}
// del 按值删除,删第一个
/// @brief header val
/// @return void
void delListVal(LT *header, type val)
{
int index = selectListVal(header, val);
if (index >= 0)
{
for (size_t i = index; i < header->count; i++)
{
header->data[i] = header->data[i + 1];
}
header->count--;
}
}
// 清空free
/// @brief header
/// @return void
void freeList(LT **header){
free(*header);
*header = NULL;
}
void init_header(LT *header){
header->count = -1;
}

复制代码

3、单链表：
约定一：第一个节点不存值

在这种约定下，链表的第一个节点（通常称为哑节点或哨兵节点）不存储实际的数据值，而是仅用作链表的起始点，其next指针指向链表中第一个存储数据的节点。
头插法：

头插法意味着新节点将被插入到链表的头部（即哑节点的后面）。但由于哑节点不存储值，以是实际上新节点成为了链表中第一个存储数据的节点。

	// 假设Node结构体已经界说，且链表有一个哑节点head
	void insertAtHead(Node **head, int value) {
	Node newNode = (Node )malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = (*head)->next; // 将新节点的next指向原来的第一个数据节点
	(*head)->next = newNode; // 更新哑节点的next为新节点
	}

留意：这里head是一个指向头节点的指针的指针，因为我们须要修改头节点（哑节点）内部的next指针。
尾插法：

尾插法则须要遍历链表以找到末了一个存储数据的节点，并将新节点插入到厥后。

	// 假设Node结构体已经界说，且链表有一个哑节点head
	void insertAtTail(Node **head, int value) {
	Node newNode = (Node )malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = NULL;
	Node current = head;
	// 遍历链表找到末了一个节点
	while (current->next != NULL) {
	current = current->next;
	}
	// 将末了一个节点的next指向新节点
	current->next = newNode;
	}

约定二：第一个节点存值

在这种约定下，链表的第一个节点就存储了实际的数据值，而且没有哑节点。
头插法：

头插法意味着新节点将被插入到链表的头部，即成为新的第一个节点。

	// 假设Node结构体已经界说，且head直接指向链表的第一个数据节点
	void insertAtHead(Node **head, int value) {
	Node newNode = (Node )malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = *head; // 将新节点的next指向原来的头节点
	*head = newNode; // 更新头指针为新节点
	}

尾插法：

尾插法仍然须要遍历链表以找到末了一个节点，并将新节点插入到厥后。

	// 假设Node结构体已经界说，且head直接指向链表的第一个数据节点
	void insertAtTail(Node **head, int value) {
	Node newNode = (Node )malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = NULL;
	if (*head == NULL) {
	// 如果链表为空，则新节点即为头节点
	*head = newNode;
	} else {
	Node current = head;
	// 遍历链表找到末了一个节点
	while (current->next != NULL) {
	current = current->next;
	}
	// 将末了一个节点的next指向新节点
	current->next = newNode;
	}
	}

单向链表：

单向链表的特点：

结构简朴：单向链表的每个节点包含数据和指向下一个节点的指针。
增删机动：在单向链表中插入或删除节点时，仅需修改相干节点的指针，而不须要移动数据元素本身，这使得操纵相对机动和高效。
访问服从低：由于访问任何一个节点都须要从头节点开始次序遍历，因此访问服从较低，尤其是在链表较长时。
内存分配机动：链表节点可以在运行时动态分配和开释内存，相比数组等结构更加机动。

#include "singleLinkedList.h"
ND *createList()
{
ND *header = (ND *)malloc(sizeof(ND));
ERROR_CHECK(NULL, header, "malloc");
header->next = NULL;
return header;
}
void insertNodeTail(ND *header, type val)
{
ND *p = header;
while (p->next)
{
p = p->next;
};
ND *new_node = (ND *)malloc(sizeof(ND));
ERROR_CHECK(NULL, new_node, "mallocTail");
new_node->data = val;
new_node->next = NULL;
p->next = new_node;
}
void insertNodeHead(ND *header, type val)
{
ND *new_node = (ND *)malloc(sizeof(ND));
ERROR_CHECK(NULL, new_node, "mallocHeadnewHead");
new_node->data = val;
new_node->next = header->next;
header->next = new_node;
}
void showList(ND *header)
{
if (NULL == header)
{
printf("List is NULL\n");
exit(1);
}
while (header = header->next)
{
printf("%d ", header->data);
}
puts("");
}
// void showList2(ND header){
// ND p = header;
// while (p.next != NULL)
// {
// p = *p.next;
// printf("%d ",p.data);
// }
// puts("");
// }
void delNode1(ND *header, int val)
{
while (header->next)
{
if (header->next->data == val)
break;
header = header->next;
}
if (header->next)
{
ND *temp = header->next;
header->next = temp->next;
free(temp);
}
}
void delNode0(ND *header, int val)
{
ND *pVal = header->next;
ND *pCur = NULL;
if (pVal->data == val)
{
header->next = pVal->next;
free(pVal);
return;
}
while ((pVal != NULL) && (pVal->data != val))
{
pCur = pVal;
pVal = pVal->next;
}
if (pVal == NULL)
{
puts("not found");
}
else
{
ND *temp = pCur->next;
pCur->next = pCur->next->next;
free(temp);
}
// return delNode(header,val);
}
int lengthList(ND *header)
{
int ret = 0;
while (header = header->next)
{
ret++;
}
return ret;
}
int isEmptyList(ND *header)
{
if (NULL == header)
{
puts("NULL list");
exit(1);
}
return header->next ? 0 : 1;
}
ND *slectNodeByVal(ND *header, int val)
{
if (NULL == header)
{
puts("NULL list");
exit(1);
}
while (header = header->next)
{
if (header->data == val)
{
return header;
}
}
return NULL;
}
//init
void initList(ND *header){
if (NULL == header)
{
puts("NULL list");
return;
}
while (header->next)
{
ND * temp = header->next;
header->next = temp->next;
free(temp);
}
}
//freeList
void freeList(ND **header){
initList(*header);
free(*header);
*header = NULL;
}

复制代码

双向链表：

双向链表的特点：

双向遍历：每个节点包含数据、指向前一个节点的指针和指向下一个节点的指针，因此可以从两个方向遍历链表。
增删高效：在双向链表中插入或删除节点时，可以直接访问到目标节点的前一个和/或后一个节点，从而制止了对链表的遍历，进步了操纵服从。
空间开销略大：每个节点须要额外存储一个指针来指向前一个节点，因此相比单向链表，双向链表在节点存储上会有额外的空间开销。
应用场景广泛：由于双向遍历和增删操纵的高效性，双向链表在很多场景中都得到了广泛应用，如LRU缓存淘汰策略等。

#include "doubleLinkedList.h"
ND *createList()
{
ND *head = (ND *)malloc(sizeof(head));
ERROR_CHECK(NULL, head, "malloc");
head->Precursor_node = NULL;
head->successor_node = NULL;
return head;
}
void insertNodeHead(ND *head, int val)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
ND *new_node = (ND *)malloc(sizeof(ND));
ERROR_CHECK(NULL, new_node, "malloc_new_node_head");
new_node->data = val;
new_node->Precursor_node = head;
new_node->successor_node = head->successor_node;
if (head->successor_node)
{
head->successor_node->Precursor_node = new_node;
}
head->successor_node = new_node;
}
void insertNodeTail(ND *head, int val)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
ND *new_node = (ND *)malloc(sizeof(ND));
ERROR_CHECK(NULL, new_node, "malloc_new_node_tail");
new_node->data = val;
while (head->successor_node)
head = head->successor_node;
new_node->successor_node = head->successor_node;
new_node->Precursor_node = head;
head->successor_node = new_node;
}
void showList(ND *head)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
while (head = head->successor_node)
{
printf("%d ", head->data);
}
puts("");
}
ND *selectVal(ND *head, int val)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
while (head = head->successor_node)
{
if (head->data == val)
return head;
}
return NULL;
}
void changeVal(ND *head, int srcVal, int destVal)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
ND *temp;
while (temp = selectVal(head, srcVal)){
if (destVal == temp->data)
{
break;
}
temp->data = destVal;}
}
void delVal(ND *head, int val)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
ND *temp1;
while (temp1 = selectVal(head, val))
{
temp1->Precursor_node->successor_node = temp1->successor_node;
if (temp1->successor_node != NULL)
{
temp1->successor_node->Precursor_node = temp1->Precursor_node;
}
free(temp1);
}
}
int listLen(ND *head)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
int ret;
while (head = head->successor_node)
{
ret++;
}
return ret;
//递归求长度
// if (head->successor_node == NULL)
// {
// return 0;
// }
// return 1 + listLen(head->successor_node);
}
int isEmpty(ND *head)
{
if (NULL == head)
{
puts("invalid head NULL");
exit(1);
}
return NULL == head->successor_node ? 0 : 1;
}
void initList0(ND *head)
{
ND *temp = head->successor_node;
head->successor_node = NULL;
while (temp)
{
ND *next = temp->successor_node;
free(temp);
temp = next;
}
}
void initList1(ND *head)
{
while (head->successor_node)
{
ND *temp = head->successor_node;
temp->Precursor_node->successor_node = temp->successor_node;
if (temp->successor_node != NULL)
{
temp->successor_node->Precursor_node = temp->Precursor_node;
}
free(temp);
}
}
void freeList(ND **head)
{
initList0(*head);
free(*head);
*head = NULL;
}

复制代码

约瑟夫环
判断链表是否有环（快慢指针）
栈;

栈的特点：

后进先出（LIFO）：栈是一种遵循后进先出原则的数据结构，即末了加入的元素会最先被移除。
限定操纵端：栈只答应在栈顶进行插入（压栈）和删除（弹栈）操纵。
应用场景多样：栈在计算机科学中有广泛应用，如函数调用栈、表达式求值、页面回退等。

用线性表都可以实现，但是用次序表更方便

#include "stack.h"
ST * createStack(){
ST *stack = (ST*)malloc(sizeof(ST));
ERROR_CHECK(NULL,stack,"malloc stack");
stack->data = (type*)malloc(sizeof(type));
if (NULL == stack->data)
{
perror("malloc stack->data");
free (stack);
exit(1);
}
stack->data_size = 1;
stack->top = -1;
return stack;
}
void pushStack(ST *stack,type val){
if (NULL == stack)
{
puts("NULL stack");
exit(1);
}
if (stack->top == stack->data_size - 1 )
{
int new_size = stack->data_size * 2;
stack->data = (type*)realloc(stack->data,new_size * sizeof(type));
ERROR_CHECK(NULL,stack->data,"realloc push");
stack->data_size = new_size;
}
stack->data[++stack->top] = val;
}
type popStack(ST *stack){
if (NULL == stack)
{
puts("NULL stack");
exit(1);
}
if (isEmpty(stack))
{
if (stack->top <= stack->data_size/2 -1)
{
int new_size = stack->data_size /2;
stack->data = (type*)realloc(stack->data,new_size * sizeof(type));
ERROR_CHECK(NULL,stack->data,"realloc pop");
stack->data_size = new_size;
}
return stack->data[stack->top--];
}
puts("stack empty!");
}
void clearStack(ST *stack){
stack->top = -1;
stack->data_size = 1;
}
int isEmpty(ST* stack){
if (NULL == stack)
{
puts("NULL stack");
exit(1);
}
return stack->top == -1 ? 0 : 1;
}

复制代码

队列：

队列的特点：

先进先出（FIFO）：队列是一种遵循先进先出原则的数据结构，即先加入的元素会最先被移除。
两端操纵限制：队列通常在一端（队尾）进行插入操纵，在另一端（队头）进行删除操纵。
线性结构：队列中的元素按照一定的次序排列，形成线性结构。
应用场景广泛：队列在任务调度、消息传递、缓存等场景中有广泛应用，如操纵系统中的进程调度、网络通讯中的数据包管理等。

首尾相连（取余，约定末了一个不存值）

#include "queue.h"
QL *createQueueList()
{
QL *queue = (QL *)malloc(sizeof(QL));
ERROR_CHECK(NULL, queue, "malloc create");
queue->front = queue->rear = 0;
}
int isEmpty(QL *queue)
{
if (NULL == queue)
{
puts("NULL queue");
exit(1);
}
return queue->rear == queue->front ? 1 : 0;
}
int isFull(QL *queue)
{
if (NULL == queue)
{
puts("NULL queue");
exit(1);
}
return queue->rear == queue->front -1 ? 1 : 0;
}
void enQueue(QL *queue, type val)
{
if (isFull(queue))
{
puts("full queue");
exit(1);
}
queue->data[queue->rear] = val;
queue->rear = (queue->rear + 1) % LEN;
}
type deQueue(QL *queue)
{
if (isEmpty(queue))
{
puts("empty queue");
exit(1);
}
type temp = queue->data[queue->front];
queue->front = (queue->front + 1) % LEN;
return temp;
}
void showQueue(QL *queue)
{
for (size_t i = 0; i < LEN; i++)
{
printf("%c ", queue->data[i]);
}
puts("");
}
void clearQueue(QL *queue)
{
queue->front = queue->rear = 0;
}
void freeQueue(QL **queue)
{
free(*queue);
*queue = NULL;
}

复制代码

链表实现队列：

#include "queueLink.h"
QUEUE *createQueueLink()
{
QUEUE *qlink = (QUEUE *)malloc(sizeof(QUEUE));
ERROR_CHECK(NULL, qlink, "malloc");
qlink->front = NULL;
qlink->rear = NULL;
return qlink;
}
void enQueue(QUEUE *qlink, type val)
{
if (NULL == qlink)
{
puts("NULL param");
exit(1);
}
QL *new_node = (QL *)malloc(sizeof(QL));
ERROR_CHECK(NULL, new_node, "malloc new_node");
new_node->data = val;
new_node->next = NULL;
if (qlink->rear == NULL)
{
qlink->front = new_node;
}
else
{
qlink->rear->next = new_node;
}
qlink->rear = new_node;
}
type deQueue(QUEUE *qlink)
{
if (NULL == qlink)
{
puts("NULL param");
exit(1);
}
if (isEmpty(qlink))
{
puts("empty");
exit(1);
}
QL *temp = qlink->front;
qlink->front = temp->next;
int ret = temp->data;
free(temp);
if (qlink->front == NULL)
{
qlink->rear = NULL;
}
temp = NULL;
return ret;
}
int isEmpty(QUEUE *qlink)
{
if (NULL == qlink)
{
puts("NULL param");
exit(1);
}
return qlink->rear == NULL ? 1 : 0;
}
void freeQueue(QUEUE **qlink)
{
if (NULL == qlink)
{
puts("NULL param");
exit(1);
}
init(*qlink);
free(*qlink);
*qlink = NULL;
}
void init(QUEUE *qlink)
{
if (NULL == qlink)
{
puts("NULL param");
exit(1);
}
while (qlink->front)
{
QL *temp = qlink->front;
qlink->front = qlink->front->next;
free(temp);
}
qlink->rear = NULL;
}

复制代码

树：

根（Root）：
- 在一棵树中，根是唯一的节点，它没有父节点。整棵树从这个节点开始生长。
度数（Degree）：
- 一个节点的度数是指与该节点直接相连的边的数目。在树中，这通常等同于子节点的数目（因为树是无环的）。
树叶（Terminal Node）/叶子节点（Leaf Node）：
- 叶子节点是没有子节点的节点。在树中，叶子节点位于最底层。
分支节点（Branch Node）：
- 分支节点是至少有一个子节点的节点。在树中，除了根和叶子节点以外的全部节点都是分支节点。
子节点（Child Node）：
- 子节点是某个节点直接连接的下一个层级的节点。每个节点可以有多个子节点。
父节点（Parent Node）：
- 父节点是连接到某个节点的上一个层级的节点。每个非根节点都有一个父节点。
兄弟节点（Sibling Node）：
- 兄弟节点是具有相同父节点的节点。
路径（Path）：
- 路径是指从树的一个节点到另一个节点所颠末的节点序列。路径上的每个节点（除了起点和终点）都恰恰出现两次（一次作为进入节点，一次作为离开节点），而且路径上的节点是连续的。
边数（Edge Count）：
- 边数是指连接树中节点的边的总数。在一棵树中，边数通常即是节点数减一（因为树是无环的）。
高度（Height）/深度（Depth）：
- 这两个术语在树中经常交替使用，但详细寄义可能根据上下文有所不同。一般来说，节点的高度是从该节点到最远叶子节点的最长路径上的边数。而节点的深度是从根节点到该节点的路径上的边数。整棵树的高度是从根节点到最远叶子节点的最长路径上的边数。
有序树（Ordered Tree）：
- 在有序树中，子节点之间有特定的次序。这种次序对于树的操纵和遍历可能是重要的。
森林（Forest）：
- 森林是零棵或多棵不相交的树的聚集。换句话说，如果删除一棵树的全部根节点之间的连接（假设它们之间存在连接），则得到的结果是一个森林

二叉树

遍历：

从左往右连，按次序，
1绿色连起来是先序
2蓝色是中序；
3红色是后序；

通过中序+（先序或后序）来确定二叉树：

1. 前序遍历（Pre-order Traversal）

遍历次序：根节点 -> 左子树 -> 右子树。
操纵：起首访问根节点，然后遍历左子树，末了遍历右子树。
特点：在访问每个节点时，先处理该节点，再递归进行左右子树的遍历。
实现方式：通常使用递归实现，也可以使用栈实现非递归遍历。

2. 中序遍历（In-order Traversal）

遍历次序：左子树 -> 根节点 -> 右子树。
操纵：起首遍历左子树，然后访问根节点，末了遍历右子树。
特点：在中序遍历中，对于二叉搜索树（BST），遍历结果将是有序的。
实现方式：同样，可以使用递归或栈来实现非递归遍历。

3. 后序遍历（Post-order Traversal）

遍历次序：左子树 -> 右子树 -> 根节点。
操纵：起首遍历左子树，然后遍历右子树，末了访问根节点。
特点：后序遍历是末了处理根节点的遍历方式。
实现方式：递归实现较为直观，非递归实现则相对复杂，须要借助栈来辅助判断节点是否已被访问过。

4. 层序遍历（Level-order Traversal）

遍历次序：从上到下、从左到右逐层遍历。
操纵：从根节点开始，逐层遍历二叉树的节点，同一层的节点从左到右依次访问。
特点：层序遍历须要使用队列这一数据结构来实现。
实现方式：将根节点入队，然后循环进行出队操纵，并将出队节点的左右子节点（如果存在）依次入队，直到队列为空。

typedef struct QueueNode
{
TREE *treeNode;
struct QueueNode *next;
} QueueNode;
typedef struct
{
QueueNode *front;
QueueNode *rear;
} Queue;
void enqueue(Queue *q, TREE *node)
{
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
newNode->treeNode = node;
newNode->next = NULL;
if (q->rear)
{
q->rear->next = newNode;
}
q->rear = newNode;
if (!q->front)
{
q->front = newNode;
}
}
TREE *dequeue(Queue *q)
{
if (!q->front)
return NULL;
QueueNode *temp = q->front;
TREE *node = temp->treeNode;
q->front = q->front->next;
if (!q->front)
{
q->rear = NULL;
}
free(temp);
return node;
}
void level_showQueue(TREE *root)
{
if (NULL == root)
{
return;
}
Queue q = {NULL, NULL};
enqueue(&q, root);
while (q.front)
{
TREE *node = dequeue(&q);
OUT(node->data);
if (node->lchild)
{
enqueue(&q, node->lchild);
}
if (node->rchild)
{
enqueue(&q, node->rchild);
}
}
}
void level_showArry(TREE *root)
{
if (NULL == root)
{
return;
}
TREE *queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;
queue[rear++] = root; // 入队根节点
while (front < rear)
{
TREE *node = queue[front++]; // 出队
OUT(node->data);
if (node->lchild)
{
if (rear < MAX_QUEUE_SIZE)
{
queue[rear++] = node->lchild; // 入队左子节点
}
}
if (node->rchild)
{
if (rear < MAX_QUEUE_SIZE)
{
queue[rear++] = node->rchild; // 入队右子节点
}
}
}
}

复制代码

哈夫曼树：

        哈夫曼编码：
哈夫曼树（Huffman Tree），又称最优二叉树，是一种用于数据压缩的广泛使用的数据结构。它由美国数学家David A. Huffman在1952年提出，主要用于数据压缩中的变长编码表（Huffman Coding）。哈夫曼树是一种特别的二叉树结构，此中权重越大的节点离根节点越近，而权重越小的节点则离根节点越远。
  哈夫曼树的特点：

带权路径长度（WPL, Weighted Path Length）最小：在哈夫曼树中，从根节点到每个叶子节点的路径长度（即边的数目）与相应叶子节点权值的乘积之和到达最小。
叶子节点包含数据：在哈夫曼编码中，每个叶子节点都代表一个字符或数据项，并存储其频率（或概率）作为权重。
非叶子节点是归并节点：非叶子节点（内部节点）表示其两个子树中全部叶子节点权重的和。

  哈夫曼编码（Huffman Coding）：

  哈夫曼编码是一种使用可变长度编码表对源符号（如文件中的一个字符）进行编码的方法，编码的长度依赖于符号出现的概率。详细步骤如下：

统计频率：起首，统计每个字符在数据中出现的频率（或概率）。
构建哈夫曼树：
- 初始化：为每个字符创建一个叶子节点，节点的权重为字符的频率。
- 归并：选择两个权重最小的节点，将它们归并为一个新的内部节点，新节点的权重为两个子节点权重的和。将这两个节点从列表中删除，并将新节点添加到列表中。
- 重复：重复上述归并过程，直到列表中只剩下一个节点（即根节点）。
生成编码：从根节点到每个叶子节点，颠末的左子边记作“0”，右子边记作“1”。这样，每个叶子节点（即每个字符）都对应一个唯一的二进制编码。
编码数据：使用生成的哈夫曼编码表更换原始数据中的每个字符，得到压缩后的数据。

哈夫曼编码的优点：

高效压缩：通过为更常见的字符分配较短的编码，为不常见的字符分配较长的编码，从而实现数据的有效压缩。
无损压缩：由于每个字符都有唯一的编码，因此可以无损地规复原始数据。

图：

在图论中，图是由极点（或称为节点）和连接这些极点的边组成的结构。
  有向图

  有向图（Directed Graph）是图中的边具有方向性的图。在有向图中，每条边都从一个极点指向另一个极点，表示一种单向关系。例如，在社交网络中，用户A关注用户B，但用户B不一定关注用户A，这种关系就可以用有向图来表示。
  无向图

  无向图（Undirected Graph）是图中的边没有方向性的图。在无向图中，如果两个极点之间存在边，则它们是相互连接的，表示一种双向关系。例如，在朋友关系中，如果A是B的朋友，那么B也是A的朋友，这种关系可以用无向图来表示。
  极点的度（有向和无向）

在无向图中，一个极点的度（Degree）是与该极点相连的边的数目。
在有向图中，一个极点的度分为入度（In-degree）和出度（Out-degree）。入度是指向该极点的边的数目，而出度是从该极点出发的边的数目。极点的度（通常指总度）是入度和出度之和，但在某些上下文中，可能仅指此中一个。

  路径

  路径（Path）是图中一系列极点和连接这些极点的边，使得从第一个极点开始，沿着边可以到达末了一个极点，且每条边只被使用一次（除非路径答应环）。
  连通性

连通图：在无向图中，如果图中恣意两个极点之间都存在路径，则称该图为连通图。
强连通图：在有向图中，如果图中恣意两个极点之间都存在双向路径，则称该图为强连通图。
弱连通图：在有向图中，如果忽略边的方向后，图是连通的，则称该图为弱连通图。

  图的基本运算

  图的基本运算包括但不限于：

添加极点
删除极点
添加边
删除边
查找极点
查找边
遍历图（如深度优先搜索DFS、广度优先搜索BFS）

  极点

  极点（Vertex）是图的基本组成元素之一，用于表示图中的实体或对象。
  图的存储

  图的存储方式主要有两种：

毗邻矩阵：使用二维数组（矩阵）来表示图中极点之间的连接关系。对于有向图，如果极点i到极点j有边，则矩阵中对应位置(i, j)的值为1（或边的权重），否则为0。无向图的毗邻矩阵是对称的。
毗邻表：使用数组或链表来表示图中每个极点的全部毗邻点。对于有向图，每个极点都有一个指向其全部出边的链表；对于无向图，通常有两种实现方式：一种是为每个极点维护一个指向其全部毗邻点的链表（不考虑边的方向），另一种是为每个极点维护两个链表，分别表示出边和入边（但在无向图中，这实际上是多余的）。

  有向图的毗邻矩阵

  对于有向图，毗邻矩阵的大小由极点个数决定。假设图中有n个极点，则毗邻矩阵是一个n×n的矩阵。矩阵中的元素(i, j)表示极点i到极点j是否存在边（或边的权重）。如果存在边，则值为1（或边的权重）；如果不存在边，则值为0。

	A	B	C	D	E
A	0	0	1	1	0
B	0	0	0	0	0
C	0	1	0	0	0
D	0	1	0	0	1
E	0	0	0	0	0

无向图

毗邻表：

A	->C->D->NULL
B	->NULL
C	->B->NULL
D	->B->E
E	->NULL

图的遍历

是图论中的一个基本问题，它指的是从图中的某一极点出发，沿着边访问图中的每一个极点，且每个极点仅被访问一次。图的遍历算法主要有两种：深度优先搜索（DFS, Depth-First Search）和广度优先搜索（BFS, Breadth-First Search）。这两种算法既可以用于无向图，也可以用于有向图。
深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的地点边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程不停进行到已发现从源节点可达的全部节点为止。
DFS算法的基本步骤：

选择一个极点作为起始点，将其标记为已访问。
从当前极点出发，访问其一个未被访问的毗邻点，并标记为已访问。
递归地执行步骤2，直到当前极点的全部毗邻点都被访问过。
如果当前极点还有未被访问的毗邻点，则选择此中一个，返回步骤2。
如果全部极点都被访问过，则算法结束。

随机一个极点，随机一条路径，碰到NULL再回到上一个极点，如果有路径就走，没有继续回退到上一个极点，如果找不完，就换个极点继续)：

广度优先搜索（BFS）

广度优先搜索是一种对图进行遍历的算法。它从根节点开始，沿着树的宽度遍历树的节点。如果全部节点均被访问，则算法中止。
BFS算法的基本步骤：

选择一个极点作为起始点，将其加入队列，并标记为已访问。
当队列非空时，执行以下步骤：
- 从队列中取出一个极点，并访问它。
- 遍历该极点的全部未被访问的毗邻点，将它们加入队列，并标记为已访问。
重复步骤2，直到队列为空。

随机一个极点，展开路径，继续展开路径的路径

留意事项

在实际应用中，DFS和BFS都可以使用栈或队列来实现。DFS通常使用递归或栈来实现，而BFS则使用队列来实现。
对于非连通图，DFS或BFS可能须要从多个未访问的极点开始遍历，以确保访问到图中的全部极点。
在遍历过程中，可能须要记载极点的访问状态，以制止重复访问。
DFS和BFS在解决某些问题时具有不同的优势。例如，在探求最短路径时，BFS通常更有效；而在解决某些递归或回溯问题时，DFS可能更合适。

Dijkstra算法概述

Dijkstra算法从一个源点开始，渐渐找到该源点到其他全部极点的最短路径。算法使用了一个优先队列（通常是最小堆）来存储待处理的极点，以及一个间隔数组来记载从源点到图中每个极点的当前最短估计间隔。
使用Dijkstra算法求解固定两点间最短路径

初始化：选择一个固定点作为源点（记为source），并初始化间隔数组，将源点到自身的间隔设为0，源点到其他全部极点的间隔设为无穷大（或图中的最大可能间隔），并将源点加入优先队列。
循环处理：从优先队列中取出间隔最小的极点（记为current），如果这个极点恰恰是另一个固定点（记为target），则算法结束，current到源点的间隔即为所求的最短路径长度。否则，对于current的每个毗邻点（记为neighbor），更新其间隔值（如果通过current到达neighbor的间隔比当前已知的更短）。
重复步骤2：直到优先队列为空，或者找到了target的最短路径（如果target在图中可达的话）。
构建路径（如果须要）：固然Dijkstra算法本身不直接构建路径，但你可以通过记载每个极点的前驱极点来在算法结束后构建路径。这通常是在更新间隔时完成的。

注

如果图中有负权边，则Dijkstra算法可能无法正确工作。在这种情况下，你可以考虑使用Bellman-Ford算法或A*算法（如果有一个好的开导式函数）。
Dijkstra算法在边权值非负的情况下总是能正确工作，而且它的时间复杂度依赖于实现方式（通常是O((V+E)logV)，此中V是极点数，E是边数，如果使用优先队列如最小堆）。
如果只须要求解两点间的最短路径，而且图中边的数目不黑白常大，那么Floyd-Warshall算法（只管其时间复杂度为O(V^3)）可能在实际应用中更快，因为它通过一次计算就能得到图中全部极点对之间的最短路径。但是，如果图很大且只须要求解一对极点之间的路径，则这种方法可能不是最高效的。

算法（查找、排序）：

算法（  Algorithm  ）是一个有穷规则（或语句、指令）的有序聚集。    算法的特性    (  1  ) 有穷性 —— 算法执行的步骤（或规则）是有限的；    (  2  ) 确定性 —— 每个计算步骤无二义性；    (  3  ) 可行性 —— 每个计算步骤可以或许在有限的时间内完成；    (  4  ) 输入 —— 算法有零个或多个外部输入；    (  5  ) 输出 —— 算法有一个或多个输出。    时间复杂度的概念先容：    问题的规模：输入数据量的大小，用  n  来表示。    算法的时间复杂度：算法消耗时间，它是问题规模的函数 T  (  n  )  。 //log n < n <nlog n< n2    算法的空间复杂度：须要的额外空间量查找：

1. 次序查找（Sequential Search）

  次序查找是最基本的查找技能。它的工作原理是遍历整个列表，逐个检查每个元素，直到找到所需的元素或搜索完备个列表。次序查找的时间复杂度是O(n)，此中n是列表中元素的数目。这种方法不须要列表是有序的，但它在处理大数据集时可能非常慢。
  2. 二分查找（Binary Search）

  二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中央元素开始，如果中央元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中央元素，则在数组大于或小于中央元素的那一半中查找，而且跟开始一样从中央元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法的时间复杂度是O(log n)，此中n是数组中的元素数目。

int searchVal(int *data, int val, int low, int high) {
if (low > high) {
return -1; // 如果没有找到，返回-1
}
int mid = low + (high - low) / 2; // 防止溢出
if (data[mid] == val) {
return mid; // 如果中间元素就是目标值，直接返回
}
// 判断哪边是有序的
if (data[low] <= data[mid]) { // 左边有序
if (val >= data[low] && val < data[mid]) {
// 如果目标值在左半边有序区间内，则继续在左半边查找
return searchVal(data, val, low, mid - 1);
} else {
// 否则，在右半边查找
return searchVal(data, val, mid + 1, high);
}
} else { // 右边有序
if (val > data[mid] && val <= data[high]) {
// 如果目标值在右半边有序区间内，则继续在右半边查找
return searchVal(data, val, mid + 1, high);
} else {
// 否则，在左半边查找
return searchVal(data, val, low, mid - 1);
}
}
}

复制代码

3. 哈希查找（Hashing）

哈希查找是一种通过计算索引位置来快速访问数据项的技能。它通过哈希函数将键（key）映射到表中一个位置来访问记载，以加速查找的速度。抱负情况下，哈希函数应该淘汰辩论，即不同的键映射到同一个索引位置的情况。然而，哈希辩论是不可制止的，因此须要一种策略来解决辩论，比如链地址法（即使用链表解决辩论）、开放定址法（即探求下一个空闲位置）等。

  二叉搜索树（Binary Search Tree, BST）

  二叉搜索树是一种特别的二叉树结构，它满足以下性质：

每个节点都有一个作为搜索键的键（以及相干联的值）。
每个节点的键都大于其左子树中恣意节点的键。
每个节点的键都小于其右子树中恣意节点的键。
左右子树也都是二叉搜索树。

二叉搜索树的中序遍历（左-根-右）会按照键的升序访问全部节点。在最坏的情况下（树退化为链表），二叉搜索树的操纵（如查找、插入、删除）的时间复杂度会退化到O(n)。但在平均情况下，这些操纵的时间复杂度接近O(log n)。

  AVL树

  AVL树是一种自平衡的二叉搜索树。在AVL树中，任何节点的两个子树的高度最大差异为1，这种高度的平衡保证了AVL树的搜索、插入和删除操纵都能保持较高的服从，即在最坏情况下这些操纵的时间复杂度也能维持在O(log n)。当AVL树发生不平衡时，它会通过旋转操纵来重新到达平衡。这些旋转操纵包括单旋转（左旋转和右旋转）和双旋转（左右旋转和右左旋转）。

排序

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简朴的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的次序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再须要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。

for (size_t i = 0; i < len - 1; i++)
{
for (size_t j = i + 1; j < len; j++)
{
if (data[i] > data[j])
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}

复制代码

void bubbleSort(int *data, int len)
{
for (size_t i = 0; i < len - 1; i++)
{
for (size_t j = 0; j < len - i - 1; j++)
{
if (data[j] > data[j + 1])
{
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}

复制代码

2. 选择排序（Selection Sort）

选择排序是一种简朴直观的排序算法。它的工作原理是：起首在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续探求最小（大）元素，然后放到已排序序列的末端。以此类推，直到全部元素均排序完毕。

void chooseSort(int *data,int len){
for (size_t i = 0; i < len -1; i++)
{
int minIndex = i;
for (size_t j = i+1; j < len; j++)
{
if ( data[minIndex] > data[j])
{
minIndex= j;
}
}
int temp = data[minIndex];
data[minIndex] = data[i];
data[i] = temp;
}
}

复制代码

3. 插入排序（Insertion Sort）

插入排序的算法思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。在实际应用中，通常使用in-place排序（即只需用到O(1)的额外空间的排序）。
插入排序可以和折半查找联合淘汰插入的时间复杂度；

void insertSort2(int *data,int len){
int i ,j,key;
for (size_t i = 1; i < len; i++)
{
key = data[i];
j = i -1;
while (j>=0 && data[j] >key)
{
data[j+1] = data[j];
j--;
}
data[j+1] = key;
}
}

复制代码

4. 快速排序（Quick Sort）

快速排序使用分治法（Divide and Conquer）策略来把一个序列分为两个子序列。步骤为：

从数列中挑出一个元素，称为“基准”（pivot）。
重新排序数列，全部元素比基准值小的摆放在基准前面，全部元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中央位置。这个称为分区（partition）操纵。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// pi 是分区后基准值的正确位置
int pi = partition(arr, low, high);
// 分别对基准值左右两边的子数组进行快速排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
while (low < high)
{
while (arr[low] <= pivot && low <high)
{
low++;
}
if (low <high)
{
arr[high--] = arr[low];
}
while (arr[high] >= pivot && low <high)
{
high--;
}
if (low <high)
{
arr[low++] = arr[high];
}
}
arr[low] = pivot;
return low;
}

复制代码

快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如输入数组已经有序）时间复杂度会退化到O(n^2)。通过随机选择基准值可以淘汰最坏情况的发生。
in_place // 原地排序界说： "In-place" 意味着算法在排序过程中不须要额外的存储空间，除了可能须要少量的辅助变量外，全部的排序操纵都在原始的数据结构上进行。优点：节省内存空间，特别适合处理大规模数据集。缺点：由于直接在原始数据上操纵，可能会对数据造成破坏，须要谨慎处理。有些 "in-place" 排序算法可能不是稳定的排序算法（即相等的元素之间的相对次序可能改变）。 out_place // 非原地排序界说： "Out-of-place" 意味着算法在排序过程中须要额外的存储空间来生存数据的临时状态。优点：通常更容易实现，且有些算法可以保持稳定性。缺点：须要额外的存储空间，这在处理大规模数据集时可能会成为一个问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

数据结构-

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块