如果你是c语言, "不会"c++, 那么...
把iostream当成stdio.h
把cout当成printf, 不用管啥类型, 变量名字一给输出完事
把cin>>当成scanf, 变量名字一给输入完事
把endl当成\n, 换行.
哦对了, malloc已经不建议使用了, 现在使用new, 把new当作malloc, 把delete当作free就行
ok, 现在你掌握了c++的基础内容, 现在我们接着往下看...
感觉没啥好写的...背一下时空复杂度, 这两个我直接从gpt复制来的, 看看就行.
1. 顺序存储结构（数组）
顺序存储结构用一段连续的内存空间依次存放线性表的元素。
-
特点：
-
内存位置连续，每个元素的存储位置都可以通过首地址和偏移量计算出来，访问速度快（时间复杂度为 (O(1))）。
-
插入和删除操作需要移动大量元素（最坏情况下时间复杂度为 (O(n))）。
-
存储空间在定义时需要预先分配，可能存在内存浪费或空间不足问题。
-
-
常见操作：
-
查找第 (i) 个元素：直接通过数组下标访问，时间复杂度为 O(1)。
-
插入元素：在指定位置插入新元素，需要将插入位置后的元素依次向后移动一位，时间复杂度为 O(n)。
-
删除元素：删除指定位置的元素，需要将删除位置后的元素依次向前移动一位，时间复杂度为 O(n)。
-
2. 链式存储结构（链表）
链式存储结构使用一组任意的存储单元存储线性表的元素，每个元素由一个数据域和一个指针域组成，指针域指向下一个元素的地址。
-
特点：
-
元素的存储位置不连续，通过指针链接各个元素。
-
插入和删除操作不需要移动其他元素，只需修改指针指向，时间复杂度为 (O(1))。
-
查找某个元素需要从头开始遍历，时间复杂度为 (O(n))。
-
-
常见操作：
-
查找第 (i) 个元素：需要从链表头开始遍历，时间复杂度为 (O(n))。
-
插入元素：只需修改插入位置前后的指针关系，时间复杂度为 (O(1))。
-
删除元素：只需修改删除位置前后节点的指针关系，时间复杂度为 (O(1))。
-
然后链表的创建摧毁, 没啥说的...
#include<string>
#include<iostream>
using namespace std;struct Node
{int data;Node* next;
};//print
void Print(Node* head)
{Node* current = head;while (current!= NULL){std::cout << current->data << " ";current = current->next;}std::cout << std::endl;
}//insert
void Insert(Node** head, int data)
{Node* newNode = new Node();newNode->data = data;newNode->next = *head;*head = newNode;
}// 释放链表的内存
void freeList(struct Node* head) {struct Node* current = head;struct Node* next;while (current != NULL) {next = current->next; // 保存下一个节点delete current; // 释放当前节点current = next; // 移动到下一个节点}
}int main()
{Node* head = NULL;Insert(&head, 1);Insert(&head, 2);Insert(&head, 3);Insert(&head, 4);Print(head);freeList(head);head = NULL;
;return 0;
}对于查找, 删除, 写一下数组, 不难理解
#include<iostream>
using namespace std;void printArray(int* arr, int size);
void deleteNode(int* arr, int size, int index);
void searchNode(int* arr, int size, int index);
void gotoNode(int* arr, int size, int index);void test01()
{int array[10] = { 7,3,5,5,6,0,8,9,2,1 };int size = sizeof(array) / sizeof(array[0]);deleteNode(array, size, 3);printArray(array, size);searchNode(array, size, 5);gotoNode(array, size, 7);
}//O(n)
void deleteNode(int* arr,int size, int index)
{for (auto i = 0; i != size;++i){if (arr[i] == index){for (auto j = i; j != size - 1; ++j){arr[j] = arr[j + 1];}arr[size - 1] = 0;}}
}//O(n)
void searchNode(int* arr, int size, int index)
{for (auto i = 0; i != size; ++i){if (arr[i] == index){cout << "Found at index " << i << endl;return;}}cout << "Not found" << endl;
}//O(1)
void gotoNode(int* arr, int size, int index)
{if (index < 0 || index >= size){cout << "Index out of range" << endl; return;}elsecout << "Value at index " << index << " is " << arr[index] << endl;
}void printArray(int* arr, int size) {for (auto i = 0; i != size; ++i){cout << arr[i] << " ";}cout << endl;
}int main()
{test01();
}查找删除也写一下链表, 也不难
#include<iostream>
using namespace std;struct Node
{Node* next;int data;Node(int x = 10){data = x;next = nullptr;}
};//O(1)
void insert_front(Node** head, int x)
{Node* newNode = new Node(x);if (*head == nullptr){*head = newNode;newNode->next = nullptr;}else{newNode->next = *head;*head = newNode;(*head)->next = nullptr;}
}//O(n)
void insert_end(Node** head, int x)
{Node* NewNode = new Node(x);if (*head == nullptr)*head = NewNode;//newnode->next=nullptr;那么head指向新节点，next指向nullptrelse{Node* iterator = (*head)->next;while (iterator->next!= nullptr)iterator = iterator->next;iterator->next = NewNode;}
}
//O(n)
void search(Node** head, int x)
{Node* iterator = *head;while (iterator!= nullptr){if (iterator->data == x)cout << "Found" << endl;iterator = iterator->next;}if (iterator == nullptr)cout << "Not Found" << endl;
}//O(n)
void delete_front(Node** head)
{if (*head == nullptr)cout << "List is empty" << endl;else{Node* temp = *head;*head = (*head)->next;delete temp;}
}
//O(n)
void delete_end(Node** head)
{if (*head == nullptr)cout << "List is empty" << endl;else{Node* iterator = *head;while (iterator->next->next!= nullptr)iterator = iterator->next;delete iterator->next;iterator->next = nullptr;}
}
//O(n) (先查后删,出要是查...)
void delete_node(Node** head, int x)
{if (*head == nullptr)cout << "List is empty" << endl;Node* iterator = *head;while (iterator->next != nullptr && iterator->next->data != x){iterator = iterator->next;}if (iterator->next == nullptr)cout << "Not Found" << endl;else{Node* temp = iterator->next;iterator->next = iterator->next->next;delete temp;}
}
//查不写了, 和上面那个一样.//直接删节点
//也是, 先查后删, 主要是查...后来我发现我们老师讲的就十分幽默...当然也很规范, 使用最好最坏平均分析
翟旭你期末看到这里怎么不给我点赞啊
我们有单向链表双向链表循环链表, 一个个实现的话...
来吧那就.
单向我不写了, 上面那个就是
循环那个也差不多, 就是尾节点->next指向头节点
算了我直接写一下吧, 边写代码边写注释, 理解起来会很快
#include<iostream>
using namespace std;//实现循环链表//我们最好设置一个哨兵头节点//定义节点结构
struct Node{int data;Node* next;Node(int x=0):data(x),next(NULL){};
};//定义循环链表类class CircularLinkedList {
private:Node* sentinel;//可以把他看做你熟知的head, 这有很多好处
public://构造函数CircularLinkedList(){sentinel = new Node();sentinel->next = sentinel;//#1}//析构函数~CircularLinkedList(){Node* current = sentinel->next;Node* temp = NULL;while (current != sentinel){temp = current;current = current->next;delete temp;}delete sentinel;}//插入元素void insert(int value){Node* new_node = new Node(value);new_node->next = sentinel->next;sentinel->next = new_node;}//删除元素void remove(int value){Node* current = sentinel->next;Node* previous = sentinel;while (current->data != value){previous = current;current = current->next;if (current == sentinel->next)return;}previous->next = current->next;delete current;}//查找元素bool find(int value){Node* current = sentinel->next;while (current->data != value){current = current->next;if (current == sentinel->next)return false;}return true;}//打印链表void print(){Node* current = sentinel->next;do {cout << current->data << " ";current = current->next;} while (current != sentinel->next);}
};双向稍微处理一下逻辑就好了
比如删除删除某个节点, 那么就直接考虑前后
我们使用ABC来表示, 删除B
那么BC双向链接断开, AB双向链接断开,有四条指针需要理解, B->next和front<-B都不需要了, B指针先delete然后赋值为nullptr, 然后 B->next和front<-B 都nullptr
A->next和front<-C悬空着, 他们俩正好连在一起
你可以把它想象成一个乐高, 前面和面一个插入一个被插入
再比如插入, 还是ABC距离, 那么AC断开, A->next和front<-C悬空, 接到B上, 然后B一前一后分别插入A和被C插入, ok.
很简单的逻辑. 和单向链表真的很像, 顺便一提, 你可以把单向列表想象成一个平头乐高块, 都见过吧, 顶上是光滑的, 没有头的那种.
今天儿子驾考过了, 开心
ok.
