东莞网站推广设计,博物馆设计网站推荐,如何做企业网站的更新,什邡网站建设目录
一、手写List成员方法
1.1 打印链表
1.2 删除链表节点
1.3 链表中倒数第k个节点
1.4 反转链表
1.5 合并两个排序链表
二、完整代码 一、C实现链表成员方法 在上一篇博客《手写链表C》#xff0c;实现了基本的List类。在面试中#xff0c;经常被问到List如何反转、…目录
一、手写List成员方法
1.1 打印链表
1.2 删除链表节点
1.3 链表中倒数第k个节点
1.4 反转链表
1.5 合并两个排序链表
二、完整代码 一、C实现链表成员方法 在上一篇博客《手写链表C》实现了基本的List类。在面试中经常被问到List如何反转、删除元素等同时也为了丰富List类的成员这一节本文实现如题等list操作。 C链表一种重要的数据结构由一系列节点构成每个节点包含两部分数据和指向下一个节点的指针。链表是一种物理存储单元上非连续、非顺序的存储结构数据结构的逻辑顺序是通过链表中的指针链接次序实现的。链表的最简单形式是单向链表它只包含一个信息域和一个指针域。链表的优点是可以动态地分配内存空间实现高效的数据操作。在C中链表的每个节点都是通过指针链接在一起从而形成一个连续的链式结构。
1.1 打印链表
为了方便debug代码先写一个打印链表的函数
void List::print()
{if (size_ 0){cout size 0 endl;return;}//遍历Node* p_curr head_-next_;//【注意这里next】while (p_curr ! nullptr){cout p_curr-data_ ;p_curr p_curr-next_;}cout endl;
}
1.2 删除链表节点
思想就是找到要删除的Node的前一个节点让前一个节点的指针指向Node的下一个节点就行了。
例如pos 3的时候for循环执行完毕p_curr表示索引值为2的节点地址接着我们让p_curr-next 指向 下一个节点的下一个节点。
//功能删除索引位置为pos的节点
void List::remove(int pos)
{if (pos 0 || pos size_){return;}Node* p_curr head_;for (int i 0; i pos; i)// 3{p_curr p_curr-next_;}p_curr-next_ p_curr-next_-next_;size_--;
}
1.3 链表中倒数第k个节点
你可以去看看剑指offer上的做法我这里类List维护了一个size_所以比较简单。
//链表中倒数第k个节点
int List::get_reverse_element(int reverse_pos)
{int pos size_ - reverse_pos;Node* p_curr head_;for (int i 0; i pos; i){p_curr p_curr-next_;}return p_curr-data_;
}
1.4 反转链表
这个方法是必学的因为面试中经常问甚至需要现场手撕。
//反转链表
void List::reverse()
{// head - 1 - 2 - 3 - 4 - nullptr//nullptr - 1 - 2 - 3 - 4Node* p_curr head_-next_;Node* p_prev nullptr;while (p_curr ! nullptr){Node* p_next p_curr-next_;if (p_next nullptr){head_-next_ p_curr;}p_curr-next_ p_prev;p_prev p_curr;p_curr p_next;}
}
下图是反转效果 1.5 合并两个排序链表
//合并两个排序链表
void mergeLists(List list3, List list4, List list34)
{Node* p_curr3 list3.head_-next_;Node* p_curr4 list4.head_-next_;Node* p_curr34 list34.head_-next_;int location 0;while ((p_curr3 ! nullptr) || (p_curr4 ! nullptr)){if ((p_curr3 ! nullptr) (p_curr4 ! nullptr)){if (p_curr3-data_ p_curr4-data_){list34.insert(location, p_curr3-data_);location;list34.insert(location, p_curr4-data_);location;}else{list34.insert(location, p_curr4-data_);location;list34.insert(location, p_curr3-data_);location;}p_curr3 p_curr3-next_;p_curr4 p_curr4-next_;}else if ((p_curr3 ! nullptr) (p_curr4 nullptr)){list34.insert(location, p_curr3-data_);location;p_curr3 p_curr3-next_;}else if ((p_curr3 nullptr) (p_curr4 ! nullptr)){list34.insert(location, p_curr4-data_);location;p_curr4 p_curr4-next_;}}
}
例如现在有两个升序序列
A0 2 4 6 8 14 B1 3 5 7 9 12 21 31
要将他们变成一个生序序列
思路假设现在两个序列元素个数相等我们将 0 1对比将得到 0 1 再将1和2 3 对比 得到 0 1 2 3再将3和4 5 对比依次类推对应第10行代码
现在考虑 A序列长度 B序列长度对应第29行代码 A序列长度 B序列长度对应上述第35行代码。
//合并两个排序链表List list3,list4;for (int i 0; i 5; i){list3.insert(i, 2*i);list4.insert(i, 2 * i 1);}list3.insert(5, 14);list4.insert(5, 12);list4.insert(6, 21);list4.insert(7, 31);list3.print();list4.print();List list34;mergeLists(list3, list4, list34);list34.print();
测试用例 二、链表完整代码
以下代码包含List的实现节点定义链表的插入、删除、合并、反转等。
#includeiostream
using namespace std;class Node
{
public:int data_;//数据阈Node* next_;//指针阈
public:Node() :data_(-1), next_(nullptr) {}
};class List
{
public:List(){this-head_ new Node();// 不分配空间下面赋值是不合理的//this-head_-data_ 0;//多余this-head_-next_ nullptr;this-size_ 0;};void insert(int pos, int value);void remove(int pos);int get_reverse_element(int reverse_pos);//链表中倒数第k个节点void reverse();int operator[](int i);void print();~List();
public:Node* head_;int size_;//维护一个size
};
//在第pos个元素前一个位置插入创建、找到位置、入链表
void List::insert(int pos, int value)
{if (pos 0 || pos size_)return;//创建新的节点接受数据Node* newnode new Node();newnode-data_ value;//cout newnode-data_ *newnode-data_ endl;newnode-next_ nullptr;//利用辅助指针找到pos前一个节点// 其实这里不断next无非就是希望p_curr nullptr// 然后56行 让newnode-next_ nullptr这个nullptr是从head_-next 传过来的也就是尾部插入嘛// 而循环链表 同理 让newnode-next_ (head_)这个 (head_) 是从head_-next 传过来的Node* p_curr head_;for (int i 0; i pos; i) //这个for循环本质上是head_-next_-next_......{p_curr p_curr-next_;}//现在p_curr就是pos前一个节点的指针阈//新节点入链表newnode-next_ p_curr-next_;//右边p_curr-next_ newnode;//左边size_;
}void List::remove(int pos)
{if (pos 0 || pos size_){return;}Node* p_curr head_;for (int i 0; i pos; i)// 3{p_curr p_curr-next_;}p_curr-next_ p_curr-next_-next_;size_--;
}//链表中倒数第k个节点
int List::get_reverse_element(int reverse_pos)
{int pos size_ - reverse_pos;Node* p_curr head_;for (int i 0; i pos; i){p_curr p_curr-next_;}return p_curr-data_;
}//反转链表
void List::reverse()
{// head - 1 - 2 - 3 - 4 - nullptr//nullptr - 1 - 2 - 3 - 4Node* p_curr head_-next_;Node* p_prev nullptr;while (p_curr ! nullptr){Node* p_next p_curr-next_;if (p_next nullptr)if (p_curr-next_ nullptr){head_-next_ p_curr;}p_curr-next_ p_prev;p_prev p_curr;p_curr p_next;}
}int List::operator[](int i)
{Node* p_curr head_;int count 0;while (count i){p_curr p_curr-next_;count;}return p_curr-data_;
}
void List::print()
{if (size_ 0){cout size 0 endl;return;}//遍历Node* p_curr head_-next_;//【注意这里next】while (p_curr ! nullptr){cout p_curr-data_ ;p_curr p_curr-next_;}cout endl;
}
List::~List()
{while (size_ ! 0){Node* p_curr head_;for (int i 0; i (size_ - 1); i)// 012345 i 5{p_curr p_curr-next_;//for循环执行完p_curr指向4}delete p_curr-next_;//删除最后一个元素p_curr-next_ nullptr;//末尾元素 空指针size_--;print();}delete head_; //【这个容易忘记】cout delete! endl;
}//合并两个排序链表
void mergeLists(List list3, List list4, List list34)
{Node* p_curr3 list3.head_-next_;Node* p_curr4 list4.head_-next_;Node* p_curr34 list34.head_-next_;int location 0;while ((p_curr3 ! nullptr) || (p_curr4 ! nullptr)){if ((p_curr3 ! nullptr) (p_curr4 ! nullptr)){if (p_curr3-data_ p_curr4-data_){list34.insert(location, p_curr3-data_);location;list34.insert(location, p_curr4-data_);location;}else{list34.insert(location, p_curr4-data_);location;list34.insert(location, p_curr3-data_);location;}p_curr3 p_curr3-next_;p_curr4 p_curr4-next_;}else if ((p_curr3 ! nullptr) (p_curr4 nullptr)){list34.insert(location, p_curr3-data_);location;p_curr3 p_curr3-next_;}else if ((p_curr3 nullptr) (p_curr4 ! nullptr)){list34.insert(location, p_curr4-data_);location;p_curr4 p_curr4-next_;}}
}int main()
{List list1;//插入for (int i 0; i 15; i){list1.insert(i, i);}//删除list1.remove(10);list1.remove(5);//打印list1.print();list1.reverse();list1.print();//访问倒数元素for (int i 1; i 4; i){cout 倒数第 i 个元素是 list1.get_reverse_element(i) endl;}list1.insert(2, 9999);//重载符[]for (int i list1.size_ - 1; i 0; i--){cout list1[i] ;}cout endl;List list2;list2.insert(0, 10);list2.insert(1, 20);list2.insert(2, 30);list2.print();int size2 list2.size_;//合并两个排序链表List list3, list4;for (int i 0; i 5; i){list3.insert(i, 2 * i);list4.insert(i, 2 * i 1);}list4.insert(5, 12);list4.insert(6, 21);list3.print();list4.print();List list34;mergeLists(list3, list4, list34);list34.print();return 1;
}
