ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据结构- [打印本页]
作者: 欢乐狗    时间: 2024-9-1 13:14
标题: 数据结构-
代码库：dataStructure: 数据结构部门代码

数据结构

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


存储结构


算法


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

时间复杂度和空间复杂度



线性表

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

线性表的进一步细节


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

  1. #include "dynamicArray.h"  
  2. DA * initList(){
  3.      DA* header = (DA *)malloc(sizeof(DA));
  4.      ERROE_CHECK(NULL,header,"malloc");
  5.     header->data = (type *)malloc(sizeof(type));
  6.     ERROE_CHECK(NULL,header->data,"malloc");
  7.     header->index = -1;
  8.     header->data_size = 1;
  9.     printf("11111\n");
  10.     return header;
  11. }
  13. void addList(DA * header,int val){
  14.     if (header->index+1 == header->data_size)
  15.     {
  16.        int new_size = header->data_size*2;
  17.         header->data = (type *)realloc(header->data,new_size*sizeof(type));
  18.         if (NULL == header->data)
  19.         {
  20.             perror("realloc");
  21.             exit(1);
  22.         }
  23.         header->data_size = new_size;
  24.       
  25.     }
  26.      header->data[++header->index] = val;
  27.    
  28. }
  29. void showList(DA *header){
  30.     for (size_t i = 0; i <= header->index; i++)
  31.     {
  32.         printf("%d ",header->data[i]);
  33.     }
  34.     puts("");
  36. }
  37. void delList(DA * header,int index){
  38.     if (header->index+1 <= header->data_size / 2)
  39.     {
  40.        int new_size = header->data_size / 2;
  41.         header->data = (type *)realloc(header->data,new_size*sizeof(type));
  42.         if (NULL == header->data)
  43.         {
  44.             perror("realloc");
  45.             exit(1);
  46.         }
  47.         header->data_size = new_size;   
  48.     }
  49.     if (index <= header->index)
  50.     {
  51.         for (size_t i = index; i < header->index; i++)
  52.         {
  53.             header->data[i] = header->data[i+1];
  54.         }
  55.         header->index--;
  56.     }
  57.    
  58. }
复制代码
 2、平凡数组线性表
  1. #include "seqList.h"
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <43func.h>
  6. LT *createList()
  7. {
  8.     LT *header = (LT *)malloc(sizeof(LT));
  9.     ERROE_CHECK(NULL, header, "malloc");
  10.     header->count = -1;
  11.     return header;
  12. }
  13. bool insertList(LT *header, type data)
  14. {
  15.     if (isFullList(header))
  16.     {
  17.         printf("Full\n");
  18.         exit(1);
  19.     }
  21.     if (header->count < LEN)
  22.     {
  23.         header->count++;
  24.         header->data[header->count] = data;
  25.         return true;
  26.     }
  27.     else
  28.     {
  29.         return false;
  30.     }
  31. }
  32. void showList(LT *header)
  33. {
  34.     if (isEmptyList(header))
  35.     {
  36.         puts("empty!");
  37.         exit(1);
  38.     }
  39.     for (size_t i = 0; i <= header->count; i++)
  40.     {
  41.         printf("%d ", header->data[i]);
  42.     }
  43.     puts("");
  44. }
  45. // full
  46. bool isFullList(LT *header)
  47. {
  48.     return (LEN - 1 == header->count) ? true : false;
  49. }
  50. // empty
  51. bool isEmptyList(LT *header)
  52. {
  54.     return (-1 == header->count) ? true : false;
  55. }
  56. // length
  57. int lengthList(LT *header)
  58. {
  59.     return header ? header->count + 1 : -1;
  60. }
  61. // select
  62. /// @brief  表头，要查找的值
  63. /// @return 索引，
  64. int selectListVal(LT *header, type val)
  65. {
  66.     if (isEmptyList(header))
  67.     {
  68.         puts("empty");
  69.         exit(1);
  70.     }
  71.     for (size_t i = 0; i <= header->count; i++)
  72.     {
  73.         if (val == header->data[i])
  74.         {
  75.             return i;
  76.         }
  77.     }
  78.     return -1;
  79. }
  80. /// @brief  header   valSrc valDest
  81. /// @return void
  82. void changeListVal(LT *header, type valSrc, type valDest)
  83. {
  84.     int ret = selectListVal(header, valSrc);
  85.     while (ret >= 0)
  86.     {
  87.         header->data[ret] = valDest;
  88.         ret = selectListVal(header, valSrc);
  89.     }
  90. }
  91. // del 按值删除,删第一个
  92. /// @brief  header   val
  93. /// @return void
  94. void delListVal(LT *header, type val)
  95. {
  96.     int index = selectListVal(header, val);
  97.     if (index >= 0)
  98.     {
  99.         for (size_t i = index; i < header->count; i++)
  100.         {
  101.             header->data[i] = header->data[i + 1];
  102.         }
  103.         header->count--;
  104.     }
  105. }
  106. // 清空free
  107. /// @brief  header   
  108. /// @return void
  109. void freeList(LT **header){
  110.     free(*header);
  111.     *header = NULL;
  112. }
  113. void init_header(LT *header){
  114.     header->count = -1;
  115. }
复制代码
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;
}
}
单向链表：

单向链表的特点：

  1. #include "singleLinkedList.h"
  3. ND *createList()
  4. {
  5.     ND *header = (ND *)malloc(sizeof(ND));
  6.     ERROR_CHECK(NULL, header, "malloc");
  7.     header->next = NULL;
  8.     return header;
  9. }
  10. void insertNodeTail(ND *header, type val)
  11. {
  12.     ND *p = header;
  13.     while (p->next)
  14.     {
  15.         p = p->next;
  16.     };
  17.     ND *new_node = (ND *)malloc(sizeof(ND));
  18.     ERROR_CHECK(NULL, new_node, "mallocTail");
  20.     new_node->data = val;
  21.     new_node->next = NULL;
  22.     p->next = new_node;
  23. }
  24. void insertNodeHead(ND *header, type val)
  25. {
  26.     ND *new_node = (ND *)malloc(sizeof(ND));
  27.     ERROR_CHECK(NULL, new_node, "mallocHeadnewHead");
  28.     new_node->data = val;
  29.     new_node->next = header->next;
  30.     header->next = new_node;
  31. }
  32. void showList(ND *header)
  33. {
  34.     if (NULL == header)
  35.     {
  36.         printf("List is NULL\n");
  37.         exit(1);
  38.     }
  39.     while (header = header->next)
  40.     {
  41.         printf("%d ", header->data);
  42.     }
  43.     puts("");
  44. }
  45. // void showList2(ND header){
  46. //      ND p = header;
  48. //     while (p.next != NULL)
  49. //     {
  50. //         p = *p.next;
  51. //         printf("%d ",p.data);
  52. //     }
  53. //     puts("");
  54. // }
  55. void delNode1(ND *header, int val)
  56. {
  58.     while (header->next)
  59.     {
  60.         if (header->next->data == val)
  61.             break;
  62.         header = header->next;
  63.     }
  64.     if (header->next)
  65.     {
  66.         ND *temp = header->next;
  67.         header->next = temp->next;
  68.         free(temp);
  69.     }
  70. }
  71. void delNode0(ND *header, int val)
  72. {
  73.     ND *pVal = header->next;
  74.     ND *pCur = NULL;
  75.     if (pVal->data == val)
  76.     {
  77.         header->next = pVal->next;
  78.         free(pVal);
  79.         return;
  80.     }
  81.     while ((pVal != NULL) && (pVal->data != val))
  82.     {
  83.         pCur = pVal;
  84.         pVal = pVal->next;
  85.     }
  86.     if (pVal == NULL)
  87.     {
  88.         puts("not found");
  89.     }
  90.     else
  91.     {
  92.         ND *temp = pCur->next;
  93.         pCur->next = pCur->next->next;
  94.         free(temp);
  95.     }
  96.     // return delNode(header,val);
  97. }
  98. int lengthList(ND *header)
  99. {
  100.     int ret = 0;
  101.     while (header = header->next)
  102.     {
  103.         ret++;
  104.     }
  105.     return ret;
  106. }
  107. int isEmptyList(ND *header)
  108. {
  109.     if (NULL == header)
  110.     {
  111.         puts("NULL list");
  112.         exit(1);
  113.     }
  114.     return header->next ? 0 : 1;
  115. }
  116. ND *slectNodeByVal(ND *header, int val)
  117. {
  118.     if (NULL == header)
  119.     {
  120.         puts("NULL list");
  121.         exit(1);
  122.     }
  123.     while (header = header->next)
  124.     {
  125.         if (header->data == val)
  126.         {
  127.             return header;
  128.         }
  129.     }
  130.     return NULL;
  131. }
  132. //init
  133. void initList(ND *header){
  134.     if (NULL == header)
  135.     {
  136.         puts("NULL list");
  137.         return;
  138.     }
  139.     while (header->next)
  140.     {
  141.         ND * temp = header->next;
  142.         header->next = temp->next;
  143.         free(temp);
  144.     }
  145.    
  146. }
  147. //freeList
  148. void freeList(ND **header){
  149.     initList(*header);
  150.     free(*header);
  151.     *header = NULL;
  152. }
复制代码
双向链表：

双向链表的特点：
  1. #include "doubleLinkedList.h"
  3. ND *createList()
  4. {
  5.     ND *head = (ND *)malloc(sizeof(head));
  6.     ERROR_CHECK(NULL, head, "malloc");
  7.     head->Precursor_node = NULL;
  8.     head->successor_node = NULL;
  9.     return head;
  10. }
  12. void insertNodeHead(ND *head, int val)
  13. {
  14.     if (NULL == head)
  15.     {
  16.         puts("invalid head NULL");
  17.         exit(1);
  18.     }
  19.     ND *new_node = (ND *)malloc(sizeof(ND));
  20.     ERROR_CHECK(NULL, new_node, "malloc_new_node_head");
  21.     new_node->data = val;
  22.     new_node->Precursor_node = head;
  23.     new_node->successor_node = head->successor_node;
  25.     if (head->successor_node)
  26.     {
  27.         head->successor_node->Precursor_node = new_node;
  28.     }
  29.         head->successor_node = new_node;
  30.    
  31. }
  32. void insertNodeTail(ND *head, int val)
  33. {
  34.     if (NULL == head)
  35.     {
  36.         puts("invalid head NULL");
  37.         exit(1);
  38.     }
  39.     ND *new_node = (ND *)malloc(sizeof(ND));
  40.     ERROR_CHECK(NULL, new_node, "malloc_new_node_tail");
  41.     new_node->data = val;
  42.     while (head->successor_node)
  43.         head = head->successor_node;
  44.     new_node->successor_node = head->successor_node;
  45.     new_node->Precursor_node = head;
  46.     head->successor_node = new_node;
  47. }
  48. void showList(ND *head)
  49. {
  50.     if (NULL == head)
  51.     {
  52.         puts("invalid head NULL");
  53.         exit(1);
  54.     }
  55.     while (head = head->successor_node)
  56.     {
  57.         printf("%d ", head->data);
  58.     }
  59.     puts("");
  60. }
  62. ND *selectVal(ND *head, int val)
  63. {
  64.     if (NULL == head)
  65.     {
  66.         puts("invalid head NULL");
  67.         exit(1);
  68.     }
  69.     while (head = head->successor_node)
  70.     {
  71.         if (head->data == val)
  72.             return head;
  73.     }
  75.     return NULL;
  76. }
  77. void changeVal(ND *head, int srcVal, int destVal)
  78. {
  79.     if (NULL == head)
  80.     {
  81.         puts("invalid head NULL");
  82.         exit(1);
  83.     }
  84.     ND *temp;
  85.     while (temp = selectVal(head, srcVal)){
  86.         if (destVal == temp->data)
  87.         {
  88.             break;
  89.         }
  90.         temp->data = destVal;}
  91. }
  92. void delVal(ND *head, int val)
  93. {
  94.     if (NULL == head)
  95.     {
  96.         puts("invalid head NULL");
  97.         exit(1);
  98.     }
  99.     ND *temp1;
  100.     while (temp1 = selectVal(head, val))
  101.     {
  102.          temp1->Precursor_node->successor_node = temp1->successor_node;
  103.         if (temp1->successor_node != NULL)
  104.         {      
  105.             temp1->successor_node->Precursor_node = temp1->Precursor_node;
  106.         }
  107.       
  108.         free(temp1);
  109.     }
  110. }
  111. int listLen(ND *head)
  112. {
  113.     if (NULL == head)
  114.     {
  115.         puts("invalid head NULL");
  116.         exit(1);
  117.     }
  118.     int ret;
  119.     while (head = head->successor_node)
  120.     {
  121.         ret++;
  122.     }
  123.     return ret;
  124.     //递归求长度
  125.     // if (head->successor_node == NULL)
  126.     // {
  127.     //    return 0;
  128.     // }
  129.     // return 1 + listLen(head->successor_node);
  130. }
  131. int isEmpty(ND *head)
  132. {
  133.     if (NULL == head)
  134.     {
  135.         puts("invalid head NULL");
  136.         exit(1);
  137.     }
  138.     return NULL == head->successor_node ? 0 : 1;
  139. }
  140. void initList0(ND *head)
  141. {
  143.     ND *temp = head->successor_node;
  144.     head->successor_node = NULL;
  145.     while (temp)
  146.     {
  147.         ND *next = temp->successor_node;
  148.         free(temp);
  149.         temp = next;
  150.     }
  151. }
  152. void initList1(ND *head)
  153. {
  154.     while (head->successor_node)
  155.     {
  156.         ND *temp = head->successor_node;
  157.          temp->Precursor_node->successor_node = temp->successor_node;
  158.         if (temp->successor_node != NULL)
  159.         {
  160.             temp->successor_node->Precursor_node = temp->Precursor_node;
  161.         }
  162.         free(temp);
  163.     }
  164. }
  165. void freeList(ND **head)
  166. {
  168.     initList0(*head);
  169.     free(*head);
  170.     *head = NULL;
  171. }
复制代码
约瑟夫环
判断链表是否有环 （快慢指针）
栈;

栈的特点：
用线性表都可以实现，但是用次序表更方便

  1. #include "stack.h"  
  2. ST * createStack(){
  3.     ST *stack   = (ST*)malloc(sizeof(ST));
  4.     ERROR_CHECK(NULL,stack,"malloc stack");
  5.     stack->data = (type*)malloc(sizeof(type));  
  6.     if (NULL == stack->data)
  7.     {
  8.         perror("malloc stack->data");
  9.         free (stack);
  10.         exit(1);
  11.     }
  12.     stack->data_size = 1;
  13.     stack->top = -1;
  14.     return stack;
  15. }
  17. void pushStack(ST *stack,type val){
  18.     if (NULL == stack)
  19.     {
  20.         puts("NULL stack");
  21.         exit(1);
  22.     }
  23.     if (stack->top == stack->data_size - 1 )
  24.     {
  25.         int new_size = stack->data_size * 2;
  26.         stack->data = (type*)realloc(stack->data,new_size * sizeof(type));
  27.         ERROR_CHECK(NULL,stack->data,"realloc push");
  28.         stack->data_size = new_size;
  29.     }
  30.    
  31.     stack->data[++stack->top] = val;
  32. }  
  33. type popStack(ST *stack){
  34.      if (NULL == stack)
  35.     {
  36.         puts("NULL stack");
  37.         exit(1);
  38.     }
  39.     if (isEmpty(stack))
  40.     {
  41.          if (stack->top <= stack->data_size/2 -1)
  42.     {
  43.         int new_size = stack->data_size /2;
  44.         stack->data = (type*)realloc(stack->data,new_size * sizeof(type));
  45.         ERROR_CHECK(NULL,stack->data,"realloc pop");
  46.         stack->data_size = new_size;
  47.     }
  48.     return stack->data[stack->top--];
  49.     }
  50.     puts("stack empty!");
  51. }
  52. void clearStack(ST *stack){
  53.     stack->top = -1;
  54.     stack->data_size = 1;
  55. }
  56. int isEmpty(ST* stack){
  57.         if (NULL == stack)
  58.     {
  59.         puts("NULL stack");
  60.         exit(1);
  61.     }
  62.     return stack->top == -1 ? 0 : 1;
  63. }
复制代码
队列：

队列的特点：

首尾相连（取余，约定末了一个不存值）
  1. #include "queue.h"
  3. QL *createQueueList()
  4. {
  5.     QL *queue = (QL *)malloc(sizeof(QL));
  6.     ERROR_CHECK(NULL, queue, "malloc create");
  7.     queue->front = queue->rear = 0;
  8. }
  9. int isEmpty(QL *queue)
  10. {
  11.     if (NULL == queue)
  12.     {
  13.         puts("NULL queue");
  14.         exit(1);
  15.     }
  17.     return queue->rear == queue->front ? 1 : 0;
  18. }
  19. int isFull(QL *queue)
  20. {
  21.     if (NULL == queue)
  22.     {
  23.         puts("NULL queue");
  24.         exit(1);
  25.     }
  27.     return queue->rear == queue->front -1  ? 1 : 0;
  28. }
  30. void enQueue(QL *queue, type val)
  31. {
  32.     if (isFull(queue))
  33.     {
  34.         puts("full queue");
  35.         exit(1);
  36.     }
  37.     queue->data[queue->rear] = val;
  38.     queue->rear = (queue->rear + 1) % LEN;
  39. }
  40. type deQueue(QL *queue)
  41. {
  42.     if (isEmpty(queue))
  43.     {
  44.         puts("empty queue");
  45.         exit(1);
  46.     }
  47.     type temp = queue->data[queue->front];
  48.     queue->front = (queue->front + 1) % LEN;
  49.     return temp;
  50. }
  51. void showQueue(QL *queue)
  52. {
  53.     for (size_t i = 0; i < LEN; i++)
  54.     {
  55.         printf("%c ", queue->data[i]);
  56.     }
  57.     puts("");
  58. }
  59. void clearQueue(QL *queue)
  60. {
  61.     queue->front = queue->rear = 0;
  62. }
  63. void freeQueue(QL **queue)
  64. {
  65.     free(*queue);
  66.     *queue = NULL;
  67. }
复制代码
链表实现队列：
    
  1. #include "queueLink.h"
  3. QUEUE *createQueueLink()
  4. {
  5.     QUEUE *qlink = (QUEUE *)malloc(sizeof(QUEUE));
  6.     ERROR_CHECK(NULL, qlink, "malloc");
  7.     qlink->front = NULL;
  8.     qlink->rear = NULL;
  9.     return qlink;
  10. }
  11. void enQueue(QUEUE *qlink, type val)
  12. {
  13.     if (NULL == qlink)
  14.     {
  15.         puts("NULL param");
  16.         exit(1);
  17.     }
  18.     QL *new_node = (QL *)malloc(sizeof(QL));
  19.     ERROR_CHECK(NULL, new_node, "malloc new_node");
  20.     new_node->data = val;
  21.     new_node->next = NULL;
  22.     if (qlink->rear == NULL)
  23.     {
  24.         qlink->front = new_node;
  25.     }
  26.     else
  27.     {
  28.         qlink->rear->next = new_node;
  29.     }
  30.     qlink->rear = new_node;
  31. }
  32. type deQueue(QUEUE *qlink)
  33. {
  34.     if (NULL == qlink)
  35.     {
  36.         puts("NULL param");
  37.         exit(1);
  38.     }
  39.     if (isEmpty(qlink))
  40.     {
  41.         puts("empty");
  42.         exit(1);
  43.     }
  44.     QL *temp = qlink->front;
  45.     qlink->front = temp->next;
  46.     int ret = temp->data;
  47.     free(temp);
  48.     if (qlink->front == NULL)
  49.     {
  50.         qlink->rear = NULL;
  51.     }
  52.     temp = NULL;
  53.     return ret;
  54. }
  55. int isEmpty(QUEUE *qlink)
  56. {
  57.     if (NULL == qlink)
  58.     {
  59.         puts("NULL param");
  60.         exit(1);
  61.     }
  62.     return qlink->rear == NULL ? 1 : 0;
  63. }
  64. void freeQueue(QUEUE **qlink)
  65. {
  66.     if (NULL == qlink)
  67.     {
  68.         puts("NULL param");
  69.         exit(1);
  70.     }
  71.     init(*qlink);
  72.     free(*qlink);
  73.     *qlink = NULL;
  74. }
  75. void init(QUEUE *qlink)
  76. {
  78.     if (NULL == qlink)
  79.     {
  80.         puts("NULL param");
  81.         exit(1);
  82.     }
  83.     while (qlink->front)
  84.     {
  85.         QL *temp = qlink->front;
  86.         qlink->front = qlink->front->next;
  87.         free(temp);
  88.     }
  89.     qlink->rear = NULL;
  90. }
复制代码
树：



     二叉树 

 

 



遍历：


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

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


            
 


 

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


 

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


 

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



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



  2. typedef struct QueueNode
  3. {
  4.     TREE *treeNode;
  5.     struct QueueNode *next;
  6. } QueueNode;
  7. typedef struct
  8. {
  9.     QueueNode *front;
  10.     QueueNode *rear;
  11. } Queue;
  12. void enqueue(Queue *q, TREE *node)
  13. {
  14.     QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
  15.     newNode->treeNode = node;
  16.     newNode->next = NULL;
  17.     if (q->rear)
  18.     {
  19.         q->rear->next = newNode;
  20.     }
  21.     q->rear = newNode;
  22.     if (!q->front)
  23.     {
  24.         q->front = newNode;
  25.     }
  26. }
  27. TREE *dequeue(Queue *q)
  28. {
  29.     if (!q->front)
  30.         return NULL;
  31.     QueueNode *temp = q->front;
  32.     TREE *node = temp->treeNode;
  33.     q->front = q->front->next;
  34.     if (!q->front)
  35.     {
  36.         q->rear = NULL;
  37.     }
  38.     free(temp);
  39.     return node;
  40. }
  41. void level_showQueue(TREE *root)
  42. {
  43.     if (NULL == root)
  44.     {
  45.         return;
  46.     }
  48.     Queue q = {NULL, NULL};
  49.     enqueue(&q, root);
  51.     while (q.front)
  52.     {
  53.         TREE *node = dequeue(&q);
  54.         OUT(node->data);
  56.         if (node->lchild)
  57.         {
  58.             enqueue(&q, node->lchild);
  59.         }
  60.         if (node->rchild)
  61.         {
  62.             enqueue(&q, node->rchild);
  63.         }
  64.     }
  65. }
  66. void level_showArry(TREE *root)
  67. {
  68.     if (NULL == root)
  69.     {
  70.         return;
  71.     }
  73.     TREE *queue[MAX_QUEUE_SIZE];
  74.     int front = 0, rear = 0;
  76.     queue[rear++] = root; // 入队根节点
  78.     while (front < rear)
  79.     {
  80.         TREE *node = queue[front++]; // 出队
  81.         OUT(node->data);
  83.         if (node->lchild)
  84.         {
  85.             if (rear < MAX_QUEUE_SIZE)
  86.             {
  87.                 queue[rear++] = node->lchild; // 入队左子节点
  88.             }
  89.         }
  90.         if (node->rchild)
  91.         {
  92.             if (rear < MAX_QUEUE_SIZE)
  93.             {
  94.                 queue[rear++] = node->rchild; // 入队右子节点
  95.             }
  96.         }
  97.     }
  98. }
复制代码
 哈夫曼树：

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

    哈夫曼编码（Huffman Coding）：

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

  
  

图：


 



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

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

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

  
  路径

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

  
  图的基本运算

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

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

  图的存储方式主要有两种：
    有向图的毗邻矩阵

  对于有向图，毗邻矩阵的大小由极点个数决定。假设图中有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算法的基本步骤：
        随机一个极点，随机一条路径，碰到NULL再回到上一个极点，如果有路径就走，没有继续回退到上一个极点，如果找不完，就换个极点继续)：
   

    广度优先搜索（BFS）

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

    留意事项

   
   
    Dijkstra算法概述

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

        注

   
      
算法（查找、排序）：

   算法（  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是数组中的元素数目。
  1. int searchVal(int *data, int val, int low, int high) {  
  2.     if (low > high) {  
  3.         return -1; // 如果没有找到，返回-1  
  4.     }  
  5.   
  6.     int mid = low + (high - low) / 2; // 防止溢出  
  7.   
  8.     if (data[mid] == val) {  
  9.         return mid; // 如果中间元素就是目标值，直接返回  
  10.     }  
  11.   
  12.     // 判断哪边是有序的  
  13.     if (data[low] <= data[mid]) { // 左边有序  
  14.         if (val >= data[low] && val < data[mid]) {  
  15.             // 如果目标值在左半边有序区间内，则继续在左半边查找  
  16.             return searchVal(data, val, low, mid - 1);  
  17.         } else {  
  18.             // 否则，在右半边查找  
  19.             return searchVal(data, val, mid + 1, high);  
  20.         }  
  21.     } else { // 右边有序  
  22.         if (val > data[mid] && val <= data[high]) {  
  23.             // 如果目标值在右半边有序区间内，则继续在右半边查找  
  24.             return searchVal(data, val, mid + 1, high);  
  25.         } else {  
  26.             // 否则，在左半边查找  
  27.             return searchVal(data, val, low, mid - 1);  
  28.         }  
  29.     }  
  30. }
复制代码
3. 哈希查找（Hashing）

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

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

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

  AVL树

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

  
排序

   1. 冒泡排序（Bubble Sort）

  冒泡排序是一种简朴的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的次序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再须要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。
  1.     for (size_t i = 0; i < len - 1; i++)
  2.     {
  3.         for (size_t j = i + 1; j < len; j++)
  4.         {
  5.             if (data[i] > data[j])
  6.             {
  7.                 int temp = data[i];
  8.                 data[i] = data[j];
  9.                 data[j] = temp;
  10.             }
  11.         }
  12.     }
复制代码
  1. void bubbleSort(int *data, int len)
  2. {
  3.     for (size_t i = 0; i < len - 1; i++)
  4.     {
  5.         for (size_t j = 0; j < len - i - 1; j++)
  6.         {
  7.             if (data[j] > data[j + 1])
  8.             {
  9.                 int temp = data[j];
  10.                 data[j] = data[j + 1];
  11.                 data[j + 1] = temp;
  12.             }
  13.         }
  14.     }
  15. }
复制代码
2. 选择排序（Selection Sort）

  选择排序是一种简朴直观的排序算法。它的工作原理是：起首在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续探求最小（大）元素，然后放到已排序序列的末端。以此类推，直到全部元素均排序完毕。
  1. void chooseSort(int *data,int len){
  2.     for (size_t i = 0; i < len -1; i++)
  3.     {
  4.         int minIndex = i;
  5.         for (size_t j = i+1; j < len; j++)
  6.         {
  7.             if ( data[minIndex] > data[j])
  8.             {
  9.                 minIndex= j;
  10.             }
  11.             
  12.         }
  13.         int temp = data[minIndex];
  14.         data[minIndex]  = data[i];
  15.         data[i] = temp;      
  16.     }
  17.    
  18. }
复制代码
3. 插入排序（Insertion Sort）

  插入排序的算法思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。在实际应用中，通常使用in-place排序（即只需用到O(1)的额外空间的排序）。
  插入排序可以和折半查找联合淘汰插入的时间复杂度；
  1. void insertSort2(int *data,int len){
  2.     int i ,j,key;
  3.     for (size_t i = 1; i < len; i++)
  4.     {
  5.         key = data[i];
  6.         j = i -1;
  7.         while (j>=0 && data[j] >key)
  8.         {
  9.             data[j+1] = data[j];
  10.             j--;
  11.         }
  12.         data[j+1] = key;
  13.         
  14.     }
  15.    
  16. }
复制代码
4. 快速排序（Quick Sort）

  快速排序使用分治法（Divide and Conquer）策略来把一个序列分为两个子序列。步骤为：
  
  1. void quickSort(int arr[], int low, int high)
  2. {
  3.     if (low < high)
  4.     {
  5.         // pi 是分区后基准值的正确位置
  6.         int pi = partition(arr, low, high);
  7.         // 分别对基准值左右两边的子数组进行快速排序
  8.         quickSort(arr, low, pi - 1);
  9.         quickSort(arr, pi + 1, high);
  10.     }
  11. }
  12. int partition(int arr[], int low, int high)
  13. {
  14.     int pivot = arr[high];
  15.     while (low < high)
  16.     {
  17.         while (arr[low] <= pivot && low <high)
  18.         {
  19.             low++;
  20.         }
  21.         if (low <high)
  22.         {
  23.             arr[high--] = arr[low];
  24.         }
  26.         while (arr[high] >= pivot && low <high)
  27.         {
  28.             high--;
  29.         }
  30.           if (low <high)
  31.         {
  32.             arr[low++] = arr[high];
  33.         }  
  35.     }
  36.     arr[low] = pivot;
  37.     return low;
  38. }
复制代码
快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如输入数组已经有序）时间复杂度会退化到O(n^2)。通过随机选择基准值可以淘汰最坏情况的发生。
       in_place    //   原地排序        界说：   "In-place"    意味着算法在排序过程中不须要额外的存储空间，除了可能须要少量的辅助变量        外，全部的排序操纵都在原始的数据结构上进行。        优点：节省内存空间，特别适合处理大规模数据集。        缺点：由于直接在原始数据上操纵，可能会对数据造成破坏，须要谨慎处理。        有些   "in-place"   排序算法可能不是稳定的排序算法（即相等的元素之间的相对次序可能改变）。        out_place    //   非原地排序        界说：   "Out-of-place"    意味着算法在排序过程中须要额外的存储空间来生存数据的临时状态。   优点：通常更容易实现，且有些算法可以保持稳定性。        缺点：须要额外的存储空间，这在处理大规模数据集时可能会成为一个问题       。      

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



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4