阿凡达做网站电话,wordpress 转义,wordpress主题 html,郑州手机软件开发公司节点定义 带头单链表#xff1a;我们只需要一个结点指针指向整个链表的第一个节点#xff0c;这样我们就可以通过next指针访问整个链表内的所有节点 templateclass T
struct ListNode
{T _val;ListNode* _next;ListNode(const T val):_val(val),_next(nullptr){…节点定义 带头单链表我们只需要一个结点指针指向整个链表的第一个节点这样我们就可以通过next指针访问整个链表内的所有节点 templateclass T
struct ListNode
{T _val;ListNode* _next;ListNode(const T val):_val(val),_next(nullptr){}
}; 这里默认将节点的_next指针设置成nullptr 构造析构函数 成员变量只需要Node* 的头指针即可这里的_n用来记录整个链表中有几个节点 初始化将_head赋成nullptr 因为开始是空链表 析构直接遍历链表中的节点按顺序删除节点即可 templateclass T
class List
{
public:typedef ListNodeT Node;List(){_head nullptr;_n 0;}~List(){Node* cur _head;while (cur){_head _head-_next;delete cur;cur _head;--_n;}_head nullptr;}private:Node* _head;size_t _n;
};
插入节点 push_back 尾插首先需要找到最后一个节点的地址将新节点连到最后一个节点的_next上完成尾插 需要考虑_head 为nullptr的情况因为 为nullptr时找尾操作会访问野指针 void push_back(const T val)
{Node* newnode new Node(val);if (_head nullptr){_head newnode;_n;}else{Node* cur _head;while (cur-_next){cur cur-_next;}cur-_next newnode;_n;}
} push_front 头插头插不需要找尾只需要让新节点指向原链表头节点_head指向新节点即可 注意还需要考虑_head为nullptr的情况 void push_front(const T val)
{Node* newnode new Node(val);newnode-_next _head;_head newnode;_n;
}
删除节点
pop_back 这里需要分情况这里的0个节点的情况作了温柔处理还可以直接assert暴力处理 有多个节点时需要找到最后一个节点和最后一个的节点的前一个节点进行删除操作并将tailPrev的next指针赋为nullptr void pop_back(){//①0个节点if (_head nullptr){return;}//②一个节点if (_head-_next nullptr){delete _head;_head nullptr;--_n;return;}//③一个节点以上Node* tail _head;Node* tailPrev nullptr;while (tail-_next){tailPrev tail;tail tail-_next;} delete tail;tail nullptr;tailPrev-_next nullptr;--_n;}
pop_front 头删比尾删简单的多还是这里的空链表情况进行了温柔处理还可以assert暴力处理 先将_head指向第二个节点如果只有一个节点的话恰好就是nullptr然后直接删除_head之前指向的节点 void pop_front(){if (_head nullptr){return;}Node* deleteNode _head;_head _head-_next;delete deleteNode;deleteNode nullptr;--_n;}
遍历节点 根据链表的最后一个节点的next指针是空来判断走到了链表的尽头挨个打印即可 void print()
{Node* cur _head;while (cur){cout cur-_val -;cur cur-_next;}cout NULL endl;cout 节点数量 _n endl;
}
测试代码
void test1()
{Listint L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);L1.print();
}void test2()
{ListintL1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.print();
}
void test3()
{ListintL1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.pop_front();L1.print();
}void test4()
{ListintL1;L1.push_front(10);L1.push_front(20);L1.push_front(30);L1.push_front(40);L1.print();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.pop_back();L1.print();
}
