前言
学习路线总纲
https://zhuanlan.zhihu.com/p/157355850
讲C++面向对象讲得很好
https://zhuanlan.zhihu.com/p/225175529
C++学习路线
https://tobebetterjavaer.com/xuexiluxian/ccc.html
数组和链表
- 数组特点:首地址已知,数组元素大小已知,存储连续
- 链表特点:存储不连续,根据next指针一个一个找
- 数组缺点:删除元素,后面的元素要挨个往前挪,总之要满足紧凑、连续的特性,有一定代价
- 链表缺点:多存储一个指针的空间
代码实现
数据结构的代码实现主要就是增删查改
数组:
- 检查边界,注意增的边界可以<=
- 末尾增:扩容2倍
- 中间增:数据搬移,赋值
- 末尾删:
小于1/4时,缩容为一半
最后一个元素置空,不能直接size-1
- 中间删:数据搬移,删除最后一个元素
双向链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| //双链表节点结构体 struct LinkedNode { int val; LinkedNode* prev, * next; //struct构造函数 LinkedNode(int _val) : val(_val), prev(nullptr), next(nullptr) {} };
class MyLinkedList { public: //构造函数 MyLinkedList() { this->head = new LinkedNode(0); this->tail = new LinkedNode(0); head->next = tail; tail->prev = head; this->size = 0; } private: int size; LinkedNode* head; LinkedNode* tail;
public: //***** 增 ***** void add(int index, int val) { //找到index对应的node,pred //pred <-> x <-> succ LinkedNode* pred, * succ; //前向遍历 if (index < size - index) { pred = head; for (int i = 0; i < index; i++) { pred = pred->next; } succ = pred->next; } //后向遍历 else { succ = tail; for (int i = 0; i < size - index; i++) { succ = succ->prev; } pred = succ->prev; } //新插入node,x LinkedNode* x = new LinkedNode(val);
pred->next = x; succ->prev = x;
x->prev = pred; x->next = succ; size++; } }
|