C++数据结构一

**C++数据结构一**

###1. 数组数组是最基本的线性表数据结构。它是一种固定大小的序列，元素都具有相同类型。

####1.1 数组定义

cppint arr[5]; // 定义一个长度为5的整型数组

####1.2 数组初始化

cppint arr[] = {1,2,3,4,5}; // 初始化一个长度为5的整型数组

####1.3 数组访问和修改

cpparr[0] =10; // 修改第一个元素cout << arr[0]; // 输出第一个元素

###2. 链表链表是一种非连续存储的线性表数据结构。每个结点包含一个值和一个指向下一个结点的指针。

####2.1 结点定义

cppstruct Node {
 int data;
 Node* next;
};

####2.2 链表定义

cppclass LinkedList {
private:
 Node* head;

public:
 LinkedList() : head(nullptr) {}

 void push(int newData) {
 Node* newNode = new Node();
 newNode->data = newData;
 newNode->next = head;
 head = newNode;
 }

 int pop() {
 if (head == nullptr) return -1; // 空链表 int data = head->data;
 Node* temp = head;
 head = head->next;
 delete temp;
 return data;
 }
};

####2.3 链表操作

cppLinkedList list;
list.push(10);
list.push(20);
cout << list.pop(); // 输出20

###3. 栈栈是一种后进先出的线性表数据结构。它遵循 LIFO（Last In First Out）原则。

####3.1 栈定义

cppclass Stack {
private:
 int* arr;
 int top;

public:
 Stack(int maxSize) : arr(new int[maxSize]), top(-1) {}

 void push(int data) {
 if (top == maxSize -1) return; // 满栈 arr[++top] = data;
 }

 int pop() {
 if (top == -1) return -1; // 空栈 int data = arr[top--];
 return data;
 }
};

####3.2 栈操作

cppStack stack(5);
stack.push(10);
stack.push(20);
cout << stack.pop(); // 输出20

###4. 队列队列是一种先进先出的线性表数据结构。它遵循 FIFO（First In First Out）原则。

####4.1 队列定义

cppclass Queue {
private:
 int* arr;
 int front;
 int rear;

public:
 Queue(int maxSize) : arr(new int[maxSize]), front(0), rear(-1) {}

 void enqueue(int data) {
 if (rear == maxSize -1) return; // 满队列 arr[++rear] = data;
 }

 int dequeue() {
 if (front > rear) return -1; // 空队列 int data = arr[front++];
 return data;
 }
};

####4.2 队列操作

cppQueue queue(5);
queue.enqueue(10);
queue.enqueue(20);
cout << queue.dequeue(); // 输出10

###5. 哈希表哈希表是一种基于散列函数的数据结构。它用于快速查找、插入和删除元素。

####5.1 哈希表定义

cppclass HashTable {
private:
 int* arr;
 int size;

public:
 HashTable(int maxSize) : arr(new int[maxSize]), size(maxSize) {}

 void insert(int key, int value) {
 int index = hash(key);
 if (arr[index] ==0) arr[index] = value; // 插入 else if (arr[index] == -1) return; // 重复键值对 }

 int search(int key) {
 int index = hash(key);
 return arr[index];
 }
};

####5.2 哈希表操作

cppHashTable table(10);
table.insert(10,20);
cout << table.search(10); // 输出20

###6. 堆堆是一种特殊的完全二叉树数据结构。它遵循堆属性：父结点值大于或等于子结点值。

####6.1 堆定义

cppclass Heap {
private:
 int* arr;
 int size;

public:
 Heap(int maxSize) : arr(new int[maxSize]), size(maxSize) {}

 void insert(int data) {
 if (size == maxSize -1) return; // 满堆 arr[size++] = data;
 heapifyUp(size -1);
 }

 int extract() {
 if (size ==0) return -1; // 空堆 int data = arr[0];
 arr[0] = arr[--size];
 heapifyDown(0);
 return data;
 }
};

####6.2 堆操作

cppHeap heap(5);
heap.insert(10);
heap.insert(20);
cout << heap.extract(); // 输出20

###7. TrieTrie是一种多项式时间复杂度的字符串查找数据结构。

####7.1 Trie定义

cppclass Trie {
private:
 struct Node {
 bool isEnd;
 int children[26];
 };

 Node* root;

public:
 Trie() : root(new Node()) {}

 void insert(const char* str) {
 Node* node = root;
 for (int i =0; str[i]; ++i) {
 int index = str[i] - 'a';
 if (node->children[index] ==0) node->children[index] = new Node();
 node = node->children[index];
 }
 node->isEnd = true;
 }

 bool search(const char* str) {
 Node* node = root;
 for (int i =0; str[i]; ++i) {
 int index = str[i] - 'a';
 if (node->children[index] ==0) return false;
 node = node->children[index];
 }
 return node->isEnd;
 }
};

####7.2 Trie操作

cppTrie trie;
trie.insert("apple");
cout << trie.search("apple"); // 输出true

以上是C++数据结构一的内容，包括数组、链表、栈、队列、哈希表、堆和Trie等基本数据结构。