复学数据结构

1.for循环

c中的for循环和js的for循环用法一样
 

for (初始化表达式; 条件表达式; 递增/递减表达式) {// 循环体
}

2.数组

1)时间复杂度

算法	平均情况	最坏情况
访问	O(1)	O(1)
搜索	O(n)	O(n)
插入	O(n)	O(n)
删除	O(n)	O(n)

2)C++ 将高维维数组存储为一维数组。因此,如果我们将 A 定义为也包含 M * N 个元素的二维数组,那么实际上 A[i][j] 就等于 A[i * N + j]。

3)STL(标准模板库)是C++标准库的一部分)提供两种灵活的数组结构。

array<int, 5> arr = {1, 2, 3, 4, 5};//STL模板数组
vector<int> vec ={3,4,3};//STL模板向量,可变长度的数组

4) 由于二维数组在内存中的存储方式有两种(按行存储和按列存储),所以计算元素地址的公式也有所不同。具体公式如下:

  1. 按行存储

    • 公式:Address(a[i][j]) = BA + (i * n + j) * size
    • 说明:BA是数组的基地址,i是行索引,j是列索引,n是列数,size是每个元素的大小。
  2. 按列存储

    • 公式:Address(a[i][j]) = BA + ((j * m) + i) * size
    • 说明:BA是数组的基地址,i是行索引,j是列索引,m是行数,size是每个元素的大小。
假设有一个二维数组a[3][4],基地址BA为0x1000,每个元素大小为4字节。
按行存储时,计算a[1][2]的地址:
Address(a[1][2]) = 0x1000 + (1 * 4 + 2) * 4= 0x1000 + 6 * 4= 0x1000 + 24= 0x1018
按列存储时,计算a[1][2]的地址:
Address(a[1][2]) = 0x1000 + (2 * 3 + 1) * 4= 0x1000 + 7 * 4= 0x1000 + 28= 0x101C

5)有关数组代码

//数组的创建、遍历、插入、删除
#include<iostream>
using namespace std;int main(){// 定义数组int size =20;//容量int numbers =10;//数据量int a[20]={1,3,4,5,6,7,4,2,4,5};// 数组遍历for(int i=0;i<10;i++){cout<<a[i];}//数组插入,尾插入int value=9;if(numbers<size){a[numbers]=value;numbers++;}else{cout<<"overflow"<<endl;}// 数组插入,头插入int value2=10;if(numbers<size){for(int i=1;i<=numbers;i++){a[numbers]=a[numbers-i];}a[0]=value2;}else{cout<<"overflow"<<endl;}// 删除int aim=8;if(aim>=numbers){cout<<"overbound"<<endl;}else{for(int i=aim;i<numbers-1;i++){a[i]=a[i+1];}}}

 3.链表

1)链表概念

链表是一种数据结构,它由一系列节点(Node)组成,每个节点包含两部分:存储数据的部分和指向下一个节点的指针(或引用)。链表的第一个节点称为头节点(Head),最后一个节点的指针指向空(NULL或None),表示链表的结束。

2)链表特点

  • 动态大小:链表可以在运行时动态增加或删除节点,大小不固定。
  • 插入和删除操作高效:在已知节点位置的情况下,链表插入和删除操作只需改变指针,时间复杂度为O(1)。
  • 顺序访问:链表不支持随机访问,只能从头节点开始,逐个节点访问,直到找到目标节点或到达链表末尾。

3)链表与数组的对比

特性链表数组
大小动态变化固定大小
内存使用分散,节点在内存中不连续连续,所有元素在内存中连续
访问时间O(n),需要顺序访问O(1),可以随机访问
插入/删除O(1),在已知位置高效O(n),需要移动元素
内存分配按需分配预先分配整个数组的内存

4)链表的类型

  1. 单向链表(Singly Linked List)

    • 每个节点只有一个指向下一个节点的指针。
    • 适合简单的顺序操作。

    Head -> Node1 -> Node2 -> Node3 -> NULL

  2. 双向链表(Doubly Linked List)

    • 每个节点有两个指针,一个指向下一个节点,一个指向前一个节点。
    • 可以从任意节点向前或向后遍历。

    NULL <- Node1 <-> Node2 <-> Node3 -> NULL

  3. 循环链表(Circular Linked List)

    • 最后一个节点的指针指向头节点,形成一个循环。
    • 可以是单向循环链表或双向循环链表。

    Head -> Node1 -> Node2 -> Node3 -> Head (循环)

  4. 双向循环链表(Doubly Circular Linked List)

    • 是双向链表的扩展,最后一个节点的下一个指针指向头节点,头节点的前一个指针指向最后一个节点。

    Head <-> Node1 <-> Node2 <-> Node3 <-> Head (循环)

5)单链表

链表复杂度

操作平均复杂度最坏复杂度
访问θ(n)θ(n)
搜索θ(n)θ(n)
插入θ(1)θ(1)
删除θ(1)θ(1)

链表的实现

链表通过结构体和指针实现
struct node   
{  int data;   struct node *next;  
};  
struct node *head, *ptr;   
ptr = (struct node *)malloc(sizeof(struct node *));

有关代码 

#include<stdio.h>  
#include<stdlib.h>  
struct node
{int data;struct node *next;
};
struct node *head;void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();int main()
{int choice = 0;while (choice != 9){printf("\n\n********* 主菜单 *********\n");printf("从以下菜单列表中选择一个选项操作 ...\n");printf("===============================================\n");printf("1.插入到开头\n");printf("2.插入到结尾\n");printf("3.插入任何随机位置\n");printf("4.从头部删除\n");printf("5.从尾部删除\n");printf("6.删除指定位置后的节点\n");printf("7.搜索元素\n");printf("8.显示链表中的数据\n");printf("9.退出\n\n"); printf("===============================================\n");printf("请输入您的选择:");scanf("%d", &choice);switch (choice){case 1:beginsert();break;case 2:lastinsert();break;case 3:randominsert();break;case 4:begin_delete();break;case 5:last_delete();break;case 6:random_delete();break;case 7:search();break;case 8:display();break;case 9:exit(0);break;default:printf("请输入有效的选项...");}}return 0;
}
void beginsert()
{struct node *ptr;int item;ptr = (struct node *) malloc(sizeof(struct node *));if (ptr == NULL){printf("内存不够!\n");}else{printf("请输入一个整数值:");scanf("%d", &item);ptr->data = item;ptr->next = head;head = ptr;printf("节点已经成功插入\n");}}
void lastinsert()
{struct node *ptr, *temp;int item;ptr = (struct node*)malloc(sizeof(struct node));if (ptr == NULL){printf("内存不够!\n");}else{printf("请输入一个整数值:");scanf("%d", &item);ptr->data = item;if (head == NULL){ptr->next = NULL;head = ptr;printf("节点已经成功插入\n");}else{temp = head;while (temp->next != NULL){temp = temp->next;}temp->next = ptr;ptr->next = NULL;printf("节点已经成功插入\n");}}
}
void randominsert()
{int i, loc, item;struct node *ptr, *temp;ptr = (struct node *) malloc(sizeof(struct node));if (ptr == NULL){printf("内存不够!\n");}else{printf("请输入一个整数值:");scanf("%d", &item);ptr->data = item;printf("输入要插入的位置:");scanf("%d", &loc);temp = head;for (i = 0;i < loc;i++){temp = temp->next;if (temp == NULL){printf("此处不能插入节点\n");return;}}ptr->next = temp->next;temp->next = ptr;printf("节点已经成功插入\n");}
}
void begin_delete()
{struct node *ptr;if (head == NULL){printf("链表为空,没有什么可以删除!\n");}else{ptr = head;head = ptr->next;free(ptr);printf("已经删除头部节点 ...\n");}
}
void last_delete()
{struct node *ptr, *ptr1;if (head == NULL){printf("链表为空,没有什么可以删除!\n");}else if (head->next == NULL){head = NULL;free(head);printf("唯一的节点已经被删除了...\n");}else{ptr = head;while (ptr->next != NULL){ptr1 = ptr;ptr = ptr->next;}ptr1->next = NULL;free(ptr);printf("已删除最后一个节点...\n");}
}
void random_delete()
{struct node *ptr, *ptr1;int loc, i;printf("输入要在此节点之后执行删除的节点的位置:");scanf("%d", &loc);ptr = head;for (i = 0;i < loc;i++){ptr1 = ptr;ptr = ptr->next;if (ptr == NULL){printf("不能删除\n");return;}}ptr1->next = ptr->next;free(ptr);printf("\n第 %d 个节点已经被删除了", loc + 1);
}
void search()
{struct node *ptr;int item, i = 0, flag;ptr = head;if (ptr == NULL){printf("链表为空!\n");}else{printf("请输入要搜索的项目:");scanf("%d", &item);while (ptr != NULL){if (ptr->data == item){printf("在 %d 位置找到数据项\n", i + 1);flag = 0;}else{flag = 1;}i++;ptr = ptr->next;}if (flag == 1){printf("数据项未找到\n");}}}/*** 显示链表中的数据 */
void display()
{struct node *ptr;ptr = head;if (ptr == NULL){printf("链表为空,没有数据可以显示。");}else{printf("链表中的数据值如下所示:\n");printf("--------------------------------------------------\n");while (ptr != NULL){printf("\n%d", ptr->data);ptr = ptr->next;}}printf("\n\n\n");}

6)双链表

数据实现

  • 使用结构体和指针实现。
struct node   
{  struct node *prev;   int data;  struct node *next;   
}
  • 使用STL中的list实现
#include<list>
list<int> li;

基本操作

#include<stdio.h>  
#include<stdlib.h>  
struct node
{struct node *prev;struct node *next;int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main()
{int choice = 0;while (choice != 9){printf("*********Main Menu*********\n");printf("Choose one option from the following list ...\n");printf("===============================================\n");printf("1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");  printf("Enter your choice?\n");scanf("%d", &choice);switch (choice){case 1:insertion_beginning();break;case 2:insertion_last();break;case 3:insertion_specified();break;case 4:deletion_beginning();break;case 5:deletion_last();break;case 6:deletion_specified();break;case 7:search();break;case 8:display();break;case 9:exit(0);break;default:printf("Please enter valid choice..");}}
}
void insertion_beginning()
{struct node *ptr;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{printf("Enter Item value");scanf("%d", &item);if (head == NULL){ptr->next = NULL;ptr->prev = NULL;ptr->data = item;head = ptr;}else{ptr->data = item;ptr->prev = NULL;ptr->next = head;head->prev = ptr;head = ptr;}printf("Node inserted\n");}}
void insertion_last()
{struct node *ptr, *temp;int item;ptr = (struct node *) malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{printf("Enter value");scanf("%d", &item);ptr->data = item;if (head == NULL){ptr->next = NULL;ptr->prev = NULL;head = ptr;}else{temp = head;while (temp->next != NULL){temp = temp->next;}temp->next = ptr;ptr->prev = temp;ptr->next = NULL;}}printf("node inserted\n");
}
void insertion_specified()
{struct node *ptr, *temp;int item, loc, i;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{temp = head;printf("Enter the location ");scanf("%d", &loc);for (i = 0;i < loc;i++){temp = temp->next;if (temp == NULL){printf("There are less than %d elements", loc);return;}}printf("Enter value");scanf("%d", &item);ptr->data = item;ptr->next = temp->next;ptr->prev = temp;temp->next = ptr;temp->next->prev = ptr;printf("node inserted\n");}
}
void deletion_beginning()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW\n");}else if (head->next == NULL){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;head = head->next;head->prev = NULL;free(ptr);printf("node deleted\n");}}
void deletion_last()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW\n");}else if (head->next == NULL){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;if (ptr->next != NULL){ptr = ptr->next;}ptr->prev->next = NULL;free(ptr);printf("node deleted\n");}
}
void deletion_specified()
{struct node *ptr, *temp;int val;printf("Enter the data after which the node is to be deleted : ");scanf("%d", &val);ptr = head;while (ptr->data != val)ptr = ptr->next;if (ptr->next == NULL){printf("Can't delete\n");}else if (ptr->next->next == NULL){ptr->next = NULL;}else{temp = ptr->next;ptr->next = temp->next;temp->next->prev = ptr;free(temp);printf("node deleted\n");}
}
void display()
{struct node *ptr;printf("printing values...\n");ptr = head;while (ptr != NULL){printf("%d\n", ptr->data);ptr = ptr->next;}
}
void search()
{struct node *ptr;int item, i = 0, flag;ptr = head;if (ptr == NULL){printf("Empty List\n");}else{printf("Enter item which you want to search?\n");scanf("%d", &item);while (ptr != NULL){if (ptr->data == item){printf("item found at location %d ", i + 1);flag = 0;break;}else{flag = 1;}i++;ptr = ptr->next;}if (flag == 1){printf("Item not found\n");}}}

 7)循环单链表

数据实现

  • 链表通过结构体和指针实现
struct node   
{  int data;   struct node *next;  
};  
struct node *head, *ptr;   
ptr = (struct node *)malloc(sizeof(struct node *));
  • C++ STL提供了链表的实现
#include<list>list<int> li;
forward_list<int> li;

基本操作代码实现

#include<stdio.h>  
#include<stdlib.h>  
struct node
{int data;struct node *next;
};
struct node *head;void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
int main()
{int choice = 0;while (choice != 7){printf("*********Main Menu*********\n");printf("Choose one option from the following list ...\n");printf("===============================================\n");printf("1.Insert in begining\n2.Insert at last\n");printf("3.Delete from Beginning\n4.Delete from last\n");printf("5.Search for an element\n6.Show\n7.Exit\n");printf("Enter your choice?\n");scanf("%d", &choice);switch (choice){case 1:beginsert();break;case 2:lastinsert();break;case 3:begin_delete();break;case 4:last_delete();break;case 5:search();break;case 6:display();break;case 7:exit(0);break;default:printf("Please enter valid choice..");}}
}
void beginsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW");}else{printf("Enter the node data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head)temp = temp->next;ptr->next = head;temp->next = ptr;head = ptr;}printf("node inserted\n");}}
void lastinsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{printf("Enter Data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = ptr;ptr->next = head;}printf("node inserted\n");}}void begin_delete()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head)ptr = ptr->next;ptr->next = head->next;free(head);head = ptr->next;printf("node deleted\n");}
}
void last_delete()
{struct node *ptr, *preptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head){preptr = ptr;ptr = ptr->next;}preptr->next = ptr->next;free(ptr);printf("node deleted\n");}
}void search()
{struct node *ptr;int item, i = 0, flag = 1;ptr = head;if (ptr == NULL){printf("Empty List\n");}else{printf("Enter item which you want to search?\n");scanf("%d", &item);if (head->data == item){printf("item found at location %d", i + 1);flag = 0;}else{while (ptr->next != head){if (ptr->data == item){printf("item found at location %d ", i + 1);flag = 0;break;}else{flag = 1;}i++;ptr = ptr->next;}}if (flag != 0){printf("Item not found\n");}}}void display()
{struct node *ptr;ptr = head;if (head == NULL){printf("nothing to print");}else{printf("printing values ... \n");while (ptr->next != head){printf("%d\n", ptr->data);ptr = ptr->next;}printf("%d\n", ptr->data);}}

 8)循环双列表

数据实现

  • 使用结构体和指针实现。
struct node   
{  struct node *prev;   int data;  struct node *next;   
}
  • 使用STL中的list实现
#include<list>
list<int> li;

基本操作代码实现

#include<stdio.h>  
#include<stdlib.h>  
struct node
{struct node *prev;struct node *next;int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
int main()
{int choice = 0;while (choice != 9){printf("*********Main Menu*********\n");printf("Choose one option from the following list ...\n");printf("===============================================\n");printf("1.Insert in Beginning\n2.Insert at last\n");printf("3.Delete from Beginning\n4.Delete from last\n");printf("5.Search\n6.Show\n7.Exit\n");printf("Enter your choice?\n");scanf("\n%d", &choice);switch (choice){case 1:insertion_beginning();break;case 2:insertion_last();break;case 3:deletion_beginning();break;case 4:deletion_last();break;case 5:search();break;case 6:display();break;case 7:exit(0);break;default:printf("Please enter valid choice..");}}
}
void insertion_beginning()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW");}else{printf("Enter Item value");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;ptr->prev = head;}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = ptr;ptr->prev = temp;head->prev = ptr;ptr->next = head;head = ptr;}printf("Node inserted\n");}}
void insertion_last()
{struct node *ptr, *temp;int item;ptr = (struct node *) malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW");}else{printf("Enter value");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;ptr->prev = head;}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = ptr;ptr->prev = temp;head->prev = ptr;ptr->next = head;}}printf("node inserted\n");
}void deletion_beginning()
{struct node *temp;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = head->next;head->next->prev = temp;free(head);head = temp->next;}}
void deletion_last()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;if (ptr->next != head){ptr = ptr->next;}ptr->prev->next = head;head->prev = ptr->prev;free(ptr);printf("node deleted\n");}
}void display()
{struct node *ptr;ptr = head;if (head == NULL){printf("nothing to print");}else{printf("printing values ... \n");while (ptr->next != head){printf("%d\n", ptr->data);ptr = ptr->next;}printf("%d\n", ptr->data);}}void search()
{struct node *ptr;int item, i = 0, flag = 1;ptr = head;if (ptr == NULL){printf("Empty List\n");}else{printf("Enter item which you want to search?\n");scanf("%d", &item);if (head->data == item){printf("item found at location %d", i + 1);flag = 0;}else{while (ptr->next != head){if (ptr->data == item){printf("item found at location %d ", i + 1);flag = 0;break;}else{flag = 1;}i++;ptr = ptr->next;}}if (flag != 0){printf("Item not found\n");}}}

 4.栈

1)用数组实现栈

#include <stdio.h>   
int stack[100], i, j, choice = 0, n, top = -1;
void push();
void pop();
void show();
void main()
{printf("Enter the number of elements in the stack ");scanf("%d", &n);printf("*********Stack operations using array*********");printf("----------------------------------------------\n");while (choice != 4){printf("Chose one from the below options...\n");printf("1.Push\n2.Pop\n3.Show\n4.Exit");printf("Enter your choice \n");scanf("%d", &choice);switch (choice){case 1:{push();break;}case 2:{pop();break;}case 3:{show();break;}case 4:{printf("Exiting....");break;}default:{printf("Please Enter valid choice ");}};}
}void push()
{int val;if (top == n)printf("Overflow");else{printf("Enter the value?");scanf("%d", &val);top = top + 1;stack[top] = val;}
}void pop()
{if (top == -1)printf("Underflow");elsetop = top - 1;
}
void show()
{for (i = top;i >= 0;i--){printf("%d\n", stack[i]);}if (top == -1){printf("Stack is empty");}
}

2)用链表实现栈

#include <stdio.h>  
#include <stdlib.h>  
void push();
void pop();
void display();
struct node
{int val;struct node *next;
};
struct node *head;void main()
{int choice = 0;printf("*********Stack operations using linked list*********\n");printf("----------------------------------------------\n");while (choice != 4){printf("Chose one from the below options...\n");printf("1.Push\n2.Pop\n3.Show\n4.Exit");printf("Enter your choice \n");scanf("%d", &choice);switch (choice){case 1:{push();break;}case 2:{pop();break;}case 3:{display();break;}case 4:{printf("Exiting....");break;}default:{printf("Please Enter valid choice ");}};}
}
void push()
{int val;struct node *ptr = (struct node*)malloc(sizeof(struct node));if (ptr == NULL){printf("not able to push the element");}else{printf("Enter the value");scanf("%d", &val);if (head == NULL){ptr->val = val;ptr->next = NULL;head = ptr;}else{ptr->val = val;ptr->next = head;head = ptr;}printf("Item pushed");}
}void pop()
{int item;struct node *ptr;if (head == NULL){printf("Underflow");}else{item = head->val;ptr = head;head = head->next;free(ptr);printf("Item popped");}
}
void display()
{int i;struct node *ptr;ptr = head;if (ptr == NULL){printf("Stack is empty\n");}else{printf("Printing Stack elements \n");while (ptr != NULL){printf("%d\n", ptr->val);ptr = ptr->next;}}
}

5.队列

1)概念

  • 队列可以定义为有序列表。在一端执行插入操作rear,删除操作在另一端执行,称为front

2)应用

  • 单个共享资源(如打印机,磁盘,CPU)的等待列表。
  • 异步数据传输。管道,文件IO,套接字。
  • 缓冲区.
  • 操作系统中处理中断。

 3)时间复杂度

时间复杂性访问搜索插入删除
平均情况θ(n)θ(n)θ(1)θ(1)
最坏情况θ(n)θ(n)θ(1)θ(1)

4)队列的数组实现

#include<stdio.h>   
#include<stdlib.h>  
#define maxsize 5  
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main()
{int choice;while (choice != 4){printf("*************************Main Menu*****************************\n");printf("=================================================================\n");printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");printf("Enter your choice ?");scanf("%d", &choice);switch (choice){case 1:insert();break;case 2:delete();break;case 3:display();break;case 4:exit(0);break;default:printf("Enter valid choice??\n");}}
}
void insert()
{int item;printf("\nEnter the element\n");scanf("\n%d", &item);if (rear == maxsize - 1){printf("OVERFLOW\n");return;}if (front == -1 && rear == -1){front = 0;rear = 0;}else{rear = rear + 1;}queue[rear] = item;printf("Value inserted ");}
void delete()
{int item;if (front == -1 || front > rear){printf("UNDERFLOW\n");return;}else{item = queue[front];if (front == rear){front = -1;rear = -1;}else{front = front + 1;}printf("value deleted ");}}void display()
{int i;if (rear == -1){printf("Empty queue\n");}else{printf("printing values .....\n");for (i = front;i <= rear;i++){printf("\n%d\n", queue[i]);}}
}

 5)队列的链表实现

#include<stdio.h>   
#include<stdlib.h>  
struct node
{int data;struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main()
{int choice;while (choice != 4){printf("*************************Main Menu*****************************\n");printf("=================================================================\n");printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");printf("Enter your choice ?");scanf("%d", &choice);switch (choice){case 1:insert();break;case 2:delete();break;case 3:display();break;case 4:exit(0);break;default:printf("Enter valid choice??\n");}}
}
void insert()
{struct node *ptr;int item;ptr = (struct node *) malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");return;}else{printf("Enter value?\n");scanf("%d", &item);ptr->data = item;if (front == NULL){front = ptr;rear = ptr;front->next = NULL;rear->next = NULL;}else{rear->next = ptr;rear = ptr;rear->next = NULL;}}
}
void delete ()
{struct node *ptr;if (front == NULL){printf("UNDERFLOW\n");return;}else{ptr = front;front = front->next;free(ptr);}
}
void display()
{struct node *ptr;ptr = front;if (front == NULL){printf("Empty queue\n");}else{printf("printing values .....\n");while (ptr != NULL){printf("%d\n", ptr->data);ptr = ptr->next;}}
}

6)循环队列

概念

  • 在循环队列中,最后一个索引紧跟在第一个索引之后。
  • 当front = -1和rear = max-1时,循环队列将满。循环队列的实现类似于线性队列的实现。只有在插入和删除的情况下实现的逻辑部分与线性队列中的逻辑部分不同。

时间复杂度

操作
FrontO(1)
RearO(1)
enQueue()O(1)
deQueue()O(1)

 循环队列的数组实现

#include<stdio.h>   
#include<stdlib.h>  
#define maxsize 5  
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main()
{int choice;while (choice != 4){printf("*************************Main Menu*****************************\n");printf("=================================================================\n");printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");printf("Enter your choice ?");scanf("%d", &choice);switch (choice){case 1:insert();break;case 2:delete();break;case 3:display();break;case 4:exit(0);break;default:printf("Enter valid choice??\n");}}
}
void insert()
{int item;printf("Enter the element\n");scanf("%d", &item);if ((rear + 1) % maxsize == front){printf("OVERFLOW");return;}else if (front == -1 && rear == -1){front = 0;rear = 0;}else if (rear == maxsize - 1 && front != 0){rear = 0;}else{rear = (rear + 1) % maxsize;}queue[rear] = item;printf("Value inserted ");
}
void delete()
{int item;if (front == -1 & rear == -1){printf("UNDERFLOW\n");return;}else if (front == rear){front = -1;rear = -1;}else if (front == maxsize - 1){front = 0;}elsefront = front + 1;
}void display()
{int i;if (front == -1)printf("Circular Queue is Empty!!!\n");else{i = front;printf("Circular Queue Elements are : \n");if (front <= rear) {while (i <= rear)printf("%d %d %d\n", queue[i++], front, rear);}else {while (i <= maxsize - 1)printf("%d %d %d\n", queue[i++], front, rear);i = 0;while (i <= rear)printf("%d %d %d\n", queue[i++], front, rear);}}
}

6.哈希表

哈希表的概念

  • 哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。
  • 通过选择合适的哈希函数,哈希表可以在插入和搜索方面实现出色的性能

哈希表的分类

  • 有两种不同类型的哈希表:哈希集合和哈希映射。
    • 哈希集合集合set数据结构的实现之一,用于存储非重复值
    • 哈希映射映射map 数据结构的实现之一,用于存储(key, value)键值对。

哈希表的关键——冲突解决

问题分析

  • 理想情况下,如果我们的哈希函数是完美的一对一映射,我们将不需要处理冲突。不幸的是,在大多数情况下,冲突几乎是不可避免的。例如,在我们之前的哈希函数(y = x % 5)中,1987 和 2 都分配给了桶 2,这是一个冲突

  • 根据我们的哈希函数,这些问题与桶的容量和可能映射到同一个桶键的数目有关。

  • 让我们假设存储最大键数的桶有 N 个键。如果 N是常数且很小,我们可以简单地使用一个数组将键存储在同一个桶中。如果 N 是可变的或很大,我们可能需要使用高度平衡的二叉树来代替。

开放寻址法(open addressing)

  • 这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
Hi=(H(key)+di)% m i=1,2,…,n
  • 其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。

 哈希表的实现

C++STL中的实现

  • 哈希集合
#include<set>
set<int> s;
multiset<int> ms;
unordered_multiset<int> ums;
  • 哈希映射
#include<map>
map<map> m;
multimap<map> mm;
unordered_multimap<map> umm;

7.并查集

1)用途

并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:

  • 合并(Union):把两个不相交的集合合并为一个集合。
  • 查询(Find):查询两个元素是否在同一个集合中。

2) 基本概念和操作

  1. 初始化

    • 每个元素初始时视为一个独立的集合,每个元素的父节点指向自身。
  2. 查询

    • 通过递归查找父节点,确定元素所属的集合(根节点)。用于判断两个元素是否属于同一集合。
  3. 合并

    • 将两个集合合并为一个集合。找到两个集合的根节点,将其中一个根节点的父节点指向另一个根节点,实现合并操作。
  4. 路径压缩

    • 在查询操作中,将每个访问过的节点直接连接到根节点,减少后续查询的时间复杂度。

3)代码实现

class SetUnion{
public:vector<int> vec;// 初始化并查集SetUnion(int n){vec=vector<int>(n);for(int i=0;i<n;i++){vec[i]=i;}}// 没有路径压缩的递归查找int find_r(int x){if(x==vec[x])return x;else{return find_r(vec[x]);}}// 合并两个非连通图。void merge(int i,int j){vec[find(i)]=find(j);}// 有路径压缩的递归查找int find(int x){if(x==vec[x]){return x;}else{vec[x]=find(vec[x]);return vec[x];}}};

 8.树

1)特点

  • 每个节点都只有有限个子节点或无子节点。
  • 树有且仅有一个根节点。
  • 根节点没有父节点;非根节点有且仅有一个父节点。
  • 每个非根节点可以分为多个不相交的子树。
  • 树里面没有环路。

2)术语

  • 祖先节点: 节点的祖先是从根到该节点的路径上的任何前节点。根节点没有祖先节点。

  • 父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

  • 子节点:一个节点含有的子树的根节点称为该节点的子节点;

  • 根节点: 根节点是树层次结构中的最顶层节点。 换句话说,根节点是没有任何父节点的节点.

  • 叶子节点终端节点:度为零的节点;

  • 兄弟节点:具有相同父节点的节点互称为兄弟节点;

  • 非终端节点分支节点:度不为零的节点;

  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

  • 节点的度:一个节点含有的子树的个数称为该节点的度;

  • 树的度:一棵树中,最大的节点度称为树的度;

  • 节点的层次:从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推;

  • 深度:对于任意节点 n,n 的深度为从根到 n 的唯一路径长,根节点的深度为0

  • 高度:对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长,所有叶节点的高度为0

  • 森林:由 m(m>=0)棵互不相交的树的集合称为森林;

  • 路径: 连续边的序列称为路径。 在上图所示的树中,节点E的路径为A→B→E。

  • 级别=水平: 为树的每个节点分配一个级别编号,使得每个节点都存在于高于其父级的一个级别。根节点级别0

  • :节点总存储的值。

  • 索引:该节点子节点的个数。

 

二叉树:每个节点最多含有两个子树的树称为二叉树;

  • 严格二叉树:对于一颗二叉树,假设其深度为 d(d>1)。除了第 d 层外,其它各层的节点数目均已达最大值,且第 d 层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;
  • 完全二叉树:所有叶节点都在最底层的完全二叉树;
  • 平衡二叉树(AVL 树):当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树;
  • 搜多二叉树(二叉查找树):也称二叉搜索树、有序二叉树;
  • B 树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树。

3)数据实现

  • 使用结构体和指针实现树
struct treenode
{int root;  struct treenode *father;//父节点struct treenode *son;//子节点struct treenode *next;//兄弟节点
}

4)二叉树

概念

  • 二叉树是一种特殊类型的通用树,它的每个节点最多可以有两个子节点。 二叉树通常被划分为三个不相交的子集。
    • 节点的根
    • 左二叉树
    • 右二叉树

性质

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

5)遍历搜索方法

  • 深度优先搜索(DFS)

    • 在这个策略中,我们采用 深度 作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回到达另一个分支。深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为先序遍历中序遍历后序遍历
  • 广度优先搜索(BFS)

    • 我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。又称为层序遍历
遍历描述
前序遍历首先遍历根,然后分别遍历左子树和右子树。 该过程将递归地应用于树的每个子树。
中序遍历首先遍历左子树,然后分别遍历根和右子树。 该过程将递归地应用于树的每个子树。
后序遍历遍历左子树,然后分别遍历右子树和根。 该过程将递归地应用于树的每个子树。
层序遍历按照层次的方法,依次遍历每一层的节点,一般使用队列实现

 9.差分数组

1)概念

是一种用于高效处理区间修改的技术,特别是在需要频繁对数组的某个区间进行增减操作时。通过差分数组,我们可以将复杂的区间修改操作简化为对差分数组的简单操作,从而提升效率。

2)如何构造差分数组

给定原数组 a,差分数组 d 的构造方法如下:

  1. d[0] = a[0]
  2. 对于 i 从 1 到 n-1d[i] = a[i] - a[i-1]

例如,对于数组 a = [1, 2, 3, 4, 5],其差分数组 d 为:

  • d[0] = 1
  • d[1] = 2 - 1 = 1
  • d[2] = 3 - 2 = 1
  • d[3] = 4 - 3 = 1
  • d[4] = 5 - 4 = 1

因此,差分数组 d = [1, 1, 1, 1, 1]

3)差分数组的用途

差分数组主要用于高效处理区间修改操作。例如,如果我们要将原数组 a 的某个区间 [l, r] 内的每个元素都增加 k,我们可以通过修改差分数组来实现:

  1. d[l] += k
  2. d[r + 1] -= k(如果 r + 1 超出数组范围,则忽略此操作)

这种操作的优势在于将区间修改的复杂度从 O(n) 降低到 O(1)

4)例子

假设我们有原数组 a = [1, 2, 3, 4, 5],并且我们要将区间 [1, 3] 内的每个元素增加 2,即将 a[1], a[2], a[3] 都增加 2。构造差分数组 d = [1, 1, 1, 1, 1]
执行区间修改操作:
d[1] += 2,因此 d 变为 [1, 3, 1, 1, 1]
d[4] -= 2,因此 d 变为 [1, 3, 1, 1, -1]
最后,我们通过差分数组 d 重建修改后的原数组 a:a[0] = d[0] = 1
a[1] = a[0] + d[1] = 1 + 3 = 4
a[2] = a[1] + d[2] = 4 + 1 = 5
a[3] = a[2] + d[3] = 5 + 1 = 6
a[4] = a[3] + d[4] = 6 + (-1) = 5
结果数组 a = [1, 4, 5, 6, 5]。

5)实例 区间涂色

问题描述

  • N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

问题分析

  • 多次区间修改后求数组的值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int mm=1e5+10;int a[mm],b[mm];
int x,y;
int main()
{int n;while(scanf("%d",&n)&&n){mem(a,0);mem(b,0);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);b[x]++;b[y+1]--;}for(int i=1;i<=n;i++)a[i]=a[i-1]+b[i];for(int i=1;i<n;i++)printf("%d ",a[i]);printf("%d\n",a[n]);}return 0;
}

 10.树状数组

1)树状数组(Binary Indexed Tree, BIT),也叫做Fenwick树,是一种用于高效处理动态数组前缀和查询和更新的数据结构。它可以在对数组进行修改的同时,快速计算前缀和,具有较低的时间复杂度。

2)树状数组的基本原理

树状数组利用二进制位的特性,通过存储部分区间和来支持快速的前缀和查询和单点更新。它可以在 O(log⁡n)O(\log n)O(logn) 时间内完成前缀和查询和更新操作。

3)主要操作

  1. 初始化

    • 通常我们会从一个全零的数组开始,然后通过一系列更新操作将其构造出来。
  2. 单点更新

    • 将数组的某个元素增加一个值,并相应地更新树状数组。
    • 更新操作的时间复杂度是 O(log⁡n)。
  3. 前缀和查询

    • 计算数组从第一个元素到指定位置的前缀和。
    • 查询操作的时间复杂度是 O(log⁡n)。

4)示例

假设我们有一个数组 a,初始值如下:a = [0, 0, 0, 0, 0, 0, 0, 0]
我们将使用树状数组来支持高效的前缀和查询和单点更新操作。初始构建
我们从一个全零的树状数组开始:BIT = [0, 0, 0, 0, 0, 0, 0, 0]
操作 1:更新 a[3] += 5
我们要将 a[3] 增加 5,更新操作如下:初始位置 i = 3。
BIT[3] += 5,BIT 变为 [0, 0, 0, 5, 0, 0, 0, 0]。
更新下一个相关节点 i = 3 + (3 & -3) = 4。
BIT[4] += 5,BIT 变为 [0, 0, 0, 5, 5, 0, 0, 0]。
更新下一个相关节点 i = 4 + (4 & -4) = 8。
BIT[8] += 5,BIT 变为 [0, 0, 0, 5, 5, 0, 0, 5]。
终止更新,因为 i = 8 超出数组范围。
此时 BIT 表示的区间和变化为:
BIT = [0, 0, 0, 5, 5, 0, 0, 5]操作 2:查询前缀和 query(3)
我们要查询数组 a 的前缀和到位置 3,查询操作如下:初始位置 i = 3。
sum = 0 + BIT[3] = 5。
更新到前一个相关节点 i = 3 - (3 & -3) = 2。
sum = 5 + BIT[2] = 5(因为 BIT[2] 为 0)。
更新到前一个相关节点 i = 2 - (2 & -2) = 0。
终止查询,因为 i = 0。
前缀和 query(3) = 5。操作 3:更新 a[5] += 2
我们要将 a[5] 增加 2,更新操作如下:初始位置 i = 5。
BIT[5] += 2,BIT 变为 [0, 0, 0, 5, 5, 2, 0, 5]。
更新下一个相关节点 i = 5 + (5 & -5) = 6。
BIT[6] += 2,BIT 变为 [0, 0, 0, 5, 5, 2, 2, 5]。
更新下一个相关节点 i = 6 + (6 & -6) = 8。
BIT[8] += 2,BIT 变为 [0, 0, 0, 5, 5, 2, 2, 7]。
终止更新,因为 i = 8 超出数组范围。
此时 BIT 表示的区间和变化为:BIT = [0, 0, 0, 5, 5, 2, 2, 7]

 5)通过树状数组,我们可以高效地进行单点更新和前缀和查询操作。例如,通过上述操作,我们可以看到:

  • 更新 a[3] += 5a[5] += 2,分别只需更新与之相关的几个节点,更新操作时间复杂度为 O(log⁡n)。
  • 前缀和查询 query(3)query(5),只需查询与之相关的几个节点,查询操作时间复杂度为 O(logn)。

这种高效性使得树状数组特别适用于频繁的区间查询和单点更新的场景。

11.线段树

1)线段树是一种强大的数据结构,特别适用于处理数组上频繁的区间查询和修改操作。它通过分治和递归的方法,能够高效地完成这些操作,适用于许多实际问题,如区间和、区间最小值/最大值查询等。线段树的时间复杂度为 O(log⁡n)O(\log n)O(logn),在需要频繁更新和查询的场景中非常有效。

2) 示例

假设初始数组如下:

temperatures = [23, 27, 30, 26, 24, 28, 29, 25]

构建线段树

线段树的每个节点将存储一个区间内的最高温度。构建过程如下:

  1. 将数组分割成两半,递归地构建子树。
  2. 每个叶节点存储一个元素,每个非叶节点存储其子节点区间的最高值。

构建后的线段树如下:

                                 [30]/                     \[30]                             [29]/        \                        /         \[27]           [30]             [28]            [29]/    \         /    \            /     \         /      \[23]  [27]      [30]  [26]         [24]  [28]      [29]  [25]

操作1:区间查询(查询第2小时到第5小时的最高温度)

我们需要查询区间 [2, 5] 内的最高温度。过程如下:

  1. 从根节点 [30] 开始,区间 [2, 5] 与根节点的区间 [0, 7] 有部分重叠,因此递归地查询其左右子树。
  2. 查询左子树 [30](区间 [0, 3])和右子树 [29](区间 [4, 7])。
  3. 区间 [2, 5] 与左子树的区间 [0, 3] 部分重叠,因此进一步查询左子树的右子树 [30](区间 [2, 3])。
  4. 区间 [2, 5] 与右子树的区间 [4, 7] 部分重叠,因此进一步查询右子树的左子树 [28](区间 [4, 5])。
  5. 合并查询结果,得到 [30][28],最终结果是 max(30, 28) = 30

查询第2小时到第5小时的最高温度是 30

操作2:单点更新(更新第3小时的温度为32)

我们需要将第3小时的温度更新为 32。过程如下:

  1. 从根节点 [30] 开始,更新第3小时对应的叶节点,并递归地更新其祖先节点。
  2. 更新叶节点 [26][32]
  3. 更新其父节点 [30]max(30, 32) = 32
  4. 更新祖先节点,重新计算区间 [0, 3] 的最高温度为 max(27, 32) = 32
  5. 最终更新根节点的最高温度为 max(32, 29) = 32

更新后的线段树如下:

                                 [32]/                     \[32]                             [29]/        \                        /         \[27]           [32]             [28]            [29]/    \         /    \            /     \         /      \[23]  [27]      [30]  [32]        [24]  [28]       [29]  [25]

此时数组更新为:temperatures = [23, 27, 30, 32, 24, 28, 29, 25]

12.图

1)术语

  • 阶(Order) - 图 G 中点集 V 的大小称作图 G 的阶。
  • 子图(Sub-Graph) - 当图 G'=(V',E')其中 V‘包含于 V,E’包含于 E,则 G'称作图 G=(V,E)的子图。每个图都是本身的子图。
  • 生成子图(Spanning Sub-Graph) - 指满足条件 V(G') = V(G)的 G 的子图 G'。
  • 导出子图(Induced Subgraph) - 以图 G 的顶点集 V 的非空子集V1 为顶点集,以两端点均在 V1 中的全体边为边集的 G 的子图,称为 V1 导出的导出子图;以图 G 的边集 E 的非空子集 E1 为边集,以 E1 中边关联的顶点的全体为顶点集的 G 的子图,称为 E1 导出的导出子图。
  • 度(Degree) - 一个顶点的度是指与该顶点相关联的边的条数,顶点 v 的度记作 d(v)。
  • 入度(In-degree)和出度(Out-degree) - 对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。
  • 自环(Loop) - 若一条边的两个顶点为同一顶点,则此边称作自环。
  • 路径(Path) - 从 u 到 v 的一条路径是节点序列v0,e1,v1,e2,v2,...ek,vk,其中 ei 的顶点为 vi 及 vi - 1,k 称作路径的长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。一条路径称为一简单路径(simple path),如果路径中除起始与终止顶点可以重合外,所有顶点两两不等。
  • 行迹(Trace) - 如果路径 P(u,v)中的边各不相同,则该路径称为 u 到 v 的一条行迹。闭的行迹称作回路(Circuit)。
  • 轨迹(Track) - 如果路径 P(u,v)中的顶点各不相同,则该路径称为 u 到 v 的一条轨迹。闭的轨迹称作圈(Cycle)。
  • 桥(Bridge) - 若去掉一条边,便会使得整个图不连通,该边称为桥。
  • 相邻节点如果两个节点u和v通过边e连接,则节点u和v被称为邻居或相邻节点。

分类

  • 有向图 - 如果给图的每条边规定一个方向,那么得到的图称为有向图。
  • 无向图 - 边没有方向的图称为无向图。
  • 连通图连通图是在V中的每两个顶点(u,v)之间存在一些路径的图。连通图中没有孤立的节点。
  • 完整图完整图是每个节点与所有其他节点连接的图。 完整图包含n(n-1/2个边,其中n是图中节点的数量。
  • 权重图在权重图中,为每个边分配一些数据,例如长度或重量。 边e的权重可以给定为w(e),其必须是指示穿过边缘的成本的正(+)值。

2)图的实现

邻接矩阵

  • 在顺序表示中,使用邻接矩阵来存储由顶点和边表示的映射。在邻接矩阵中,行和列由图顶点表示。 具有n个顶点的图将具有尺寸n×n。

  • 如果在Vi和Vj之间存在边缘,则无向图G的邻接矩阵表示中的项目Mij将为1。

  • 无向图及其邻接矩阵表示如下图所示。

 

 

邻接链表

  • 邻接列表用于将图存储到计算机的内存中。考虑下图中显示的无向图并检查邻接列表表示。要为图中存在的每个节点维护邻接列表,邻接列表将节点值和指向下一个相邻节点的指针存储到相应节点。 如果遍历所有相邻节点,则将NULL存储在列表的最后一个节点的指针字段中。 邻接列表的长度之和等于无向图中存在的边数的两倍

 

3)基本操作

  • 创建一个图结构 - CreateGraph(G)
  • 检索给定顶点 - LocateVex(G,elem)
  • 获取图中某个顶点 - GetVex(G,v)
  • 为图中顶点赋值 - PutVex(G,v,value)
  • 返回第一个邻接点 - FirstAdjVex(G,v)
  • 返回下一个邻接点 - NextAdjVex(G,v,w)
  • 插入一个顶点 - InsertVex(G,v)
  • 删除一个顶点 - DeleteVex(G,v)
  • 插入一条边 - InsertEdge(G,v,w)
  • 删除一条边 - DeleteEdge(G,v,w)
  • 遍历图 - Traverse(G,v)

4)搜索——广度优先搜索

  • 广度优先搜索是一种图遍历算法,它从根节点开始遍历图并探索所有相邻节点。 然后,它选择最近的节点并浏览所有未探测的节点。 对于每个最近的节点,该算法遵循相同的过程,直到找到目标为止。

  • 下面给出了广度优先搜索的算法。算法从检查节点A及其所有邻居开始。在下一步中,搜索A的最近节点的邻居,并且在后续步骤中继续处理。 该算法探索所有节点的所有邻居,并确保每个节点只访问一次,并且没有访问任何节点两次。

  • 算法

第1步:设置状态 = 1(就绪状态)对于G中的每个节点
第2步:将起始节点A排队并设置其状态 = 2(等待状态)
第3步:重复第4步和第5步,直到队列是空的
第4步:使节点N出列。处理它并设置其状态 = 3(处理状态)。
第5步:将所有邻居排队N处于就绪状态(其STATUS = 1)并设置它们状态 = 2(等待状态)[循环结束]
第6步:退出

 

5)搜索——深度优先搜索

  • 深度优先搜索(DFS)算法从图G的初始节点开始,然后越来越深,直到找到目标节点或没有子节点的节点。该算法然后从死角回溯到尚未完全未探索的最新节点。
  • 在DFS中使用的数据结构是堆栈。该过程类似于BFS算法。 在DFS中,通向未访问节点的边称为发现边,而通向已访问节点的边称为块边。
  • 算法
第1步:为G中的每个节点设置STATUS = 1(就绪状态)
第2步:将起始节点A推入堆栈并设置其STATUS = 2(等待状态)
第3步:重复第4步和第5步,直到STACK为空
第4步:弹出顶部节点N.处理它并设置其STATUS = 3(处理状态)
第5步:将处于就绪状态(其STATUS = 1)的N的所有邻居推入堆栈并设置它们STATUS = 2(等待状态)[循环结束]
第6步:退出

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1483976.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

10个常见的电缆载流表,值得收藏!

众所周知,电线电缆的载流是所有电工、电气人员都必须具备的基本储备,但是如果要将那么多的“数字”都记得清清楚楚,还是有一点困难的!今天咱们就做了一个电力电缆载流量对照表,速度收藏!下次参考不迷路! 1、0.6/1KV聚氯乙烯绝缘电力电缆载流量 以上电缆载流量计算条件:…

一个小问题导致,AI大模型集体翻车?

9.11大还是9.9大&#xff1f; 这两天大家都在说ChatGPT大模型翻车了 &#xff01; 这到底是怎么个事儿呢&#xff1f; 原来是最近有人想ChatGPT等大模型提了一个简单的问题&#xff1a; 9.11 大还是 9.9 大&#xff1f; 答案显而易见&#xff0c;然而众多大模型却给出了错误…

AI小白也能驾驭!10款免费工具让你秒变高手

市面上的AI工具种类繁多&#xff0c;覆盖了从创意设计到日常工作处理的各个领域。下面列出了10款实用的AI工具&#xff0c;它们能帮你在不同场景下提升效率&#xff0c;解决实际问题&#xff1a; Aicbo&#xff1a;这个在线生成工具可以根据你提供的描述生成图像&#xff0c;适…

鸿蒙开发error: failed to start ability

鸿蒙开发项目编译过后不能启动 项目在模拟器运行报&#xff1a; error: failed to start ability. Error while Launching ability 解决办法&#xff1a; 1&#xff0c;看了一些文章说是把module.json5配置文件中的"exported"由false改成true&#xff0c;没有解…

JavaScript基础 第五弹 学习笔记

一、什么是对象&#xff1f; 对象&#xff1a;JavaScript里的一种数据类型&#xff1b;可以理解为是一种无序的数据集合&#xff0c;但是数据是有序的数据集合。可以详细的描述某个事物 二、对象使用 1.对象声明语法 let 对象名 { } &#xff1b;let 对象名 new Object() le…

Kafka(四) Consumer消费者

一&#xff0c;基础知识 1&#xff0c;消费者与消费组 每个消费者都有对应的消费组&#xff0c;不同消费组之间互不影响。 Partition的消息只能被一个消费组中的一个消费者所消费&#xff0c; 但Partition也可能被再平衡分配给新的消费者。 一个Topic的不同Partition会根据分配…

阿里云DSW实例中安装并运行Neo4J

想尝试使用大模型对接Neo4J&#xff0c;在阿里云DSW实例中安装了Neo4J&#xff0c;却无法通过本地浏览器访问在DSW实例中运行的Neo4J。尝试了改neo4j.conf文件&#xff0c;以及添加专用网络的公共IP地址等方法&#xff0c;均没有成功。最后决定直接在服务器的命令行进行各种Cyp…

算法——双指针(day4)

15.三数之和 15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 题目解析&#xff1a; 这道题目说是三数之和&#xff0c;其实这和我们之前做过的两数之和是一个规律的~无非就是我们需要实时改动target的值。先排好序&#xff0c;然后固定一个数取其负值作target&#xf…

Django select_related()方法

select_related()的作用 select_related()是Django ORM&#xff08;对象关系映射&#xff09;中的一种查询优化方法&#xff0c;主要用于减少数据库查询次数&#xff0c;提高查询效率。当你在查询一个模型实例时&#xff0c;如果这个实例有ForeignKey关联到其他模型&#xff0…

Java文件管理

文件管理 Java中的对文件的管理&#xff0c;通过java.io包中的File类实现。Java中文件的管理&#xff0c;主要是针对文件或是目录路径名的管理&#xff0c;包括文件的属性信息&#xff0c;文件的检查&#xff0c;文件的删除等&#xff0c;但不包括文件的访问 file类 Java中的…

机器人开源调度系统OpenTcs6二开-车辆表定义

前面已经知道opentcs 需要车辆的模型结构数据&#xff0c;将里面的数据结构化&#xff0c;已表的形式生成&#xff0c;再找一个开源的基础框架项目对车辆进行增删改的管理 表结构&#xff1a; CREATE TABLE Vehicle (id INT AUTO_INCREMENT PRIMARY KEY COMMENT 唯一标识符,n…

GPT-4o全方位综合指南:功能解析、使用技巧与最佳实践

探索AI新时代&#xff1a;从GPT-4o特性到实用技巧&#xff0c;解锁高效AI助手的全部潜力 猫头虎是谁&#xff1f; 大家好&#xff0c;我是 猫头虎&#xff0c;别名猫头虎博主&#xff0c;擅长的技术领域包括云原生、前端、后端、运维和AI。我的博客主要分享技术教程、bug解决…

【功能】DOTween动画插件使用

一、下载安装DOTween插件&#xff0c;下载地址&#xff1a;DOTween - Asset Store (unity.com) 使用 Free免费版本即可&#xff0c;导入成功后&#xff0c;Project视图中会出现 DOTween 文件夹 二、使用案例 需求1&#xff1a;控制材质球中的某个属性值&#xff0c;实现美术需…

记录些MySQL题集(16)

MySQL 存储过程与触发器 一、初识MySQL的存储过程 Stored Procedure存储过程是数据库系统中一个十分重要的功能&#xff0c;使用存储过程可以大幅度缩短大SQL的响应时间&#xff0c;同时也可以提高数据库编程的灵活性。 存储过程是一组为了完成特定功能的SQL语句集合&#x…

node-red学习

Node-RED : 起步 1、安装nodejs Node.js — 在任何地方运行 JavaScript 验证 2、更换下载源 // 查看当前下载地址 npm config get registry // 设置淘宝镜像的地址 npm config set registry https://registry.npmmirror.com/ // 查看当前的下载地址 npm config get registry…

辅助类BigDecima/BigInteger

** 大数据的运算** 编号1方法解释1add2subtract-3multiply*4divide/

nginx动静分离配置实例

什么是动静分离 ngnix动静分离简单来说就是把动态请求和静态请求分开。不能理解成只是单纯的把动态页面和静态页面物理分离。 可以理解成使用nginx处理静态页面&#xff0c;使用tomcat处理动态页面。 动静分离目前从实现角度上可以分为两种&#xff1a; 纯粹把静态文件独立成…

程序员极力推荐的一款开发工具

如果你是一个独立开发者&#xff0c;或者你只是想自己动手开发一个应用&#xff0c;你一定会遇到各种麻烦事儿&#xff1a;搭建服务器、开发接口API、处理认证和存储问题……光是想想都头大。但别担心&#xff0c;这里有一款工具能让你省心省力&#xff0c;甚至能让你觉得开发应…

【论文阅读】MCTformer+:弱监督语义分割的多类令牌转换器

【论文阅读】MCTformer:弱监督语义分割的多类令牌转换器 文章目录 【论文阅读】MCTformer:弱监督语义分割的多类令牌转换器一、介绍1.1 WSSS背景1.2 WSSS策略 二、联系工作2.1 弱监督语义分割2.2 transformers的可视化应用 三、MULTI-CLASS TOKEN TRANSFORMER3.1 Multi-class t…

JavaSE学习笔记第三弹之异常抛出

今天我们继续来学习JavaSE相关的知识&#xff0c;希望与大家共同努力。 目录 异常 什么是异常 运行时异常 编译时异常 ​编辑 为什么需要异常处理机制 错误 异常的处理与抛出 异常处理 异常抛出 自定义异常 结语 异常 什么是异常 Java中异常是一种在程序运行时发…