数据结构(C++)--学习单链表时发现的一些小坑

基于类的链表类无相应构造函数报错

#include<bits/stdc++.h>
using namespace std;
const int MaxSize = 10;
template <class T>
class Seqlist {
    public:
    	Seqlist() { length = 0;}
    	Seqlist(T [],int);
    private:
    	int length;
    	T data[MaxSize];
};    
class B {
    public:
    	B(T);
    	B() {} //这个默认的构造函数十分重要
    private:
    	T data;
};
B::B(T n) {
    data = n;
}

template <class T>
Seqlist<T>::Seqlist(T arr[], int n) {
    if (n > MaxSize) throw "invalid num";
    for (int i = 0;i < n;i++) {
        data[i] = arr[i];
    }
    length = n;
}

int main() {
    B b[3] = {B(10), B(20), B(30)};
    Seqlist<B> list(b,3);
}

在上面部分代码中,如果把有注释的那一行代码删去,则这部分代码不能正常运行,报错信息是

no matching function for call to 'B::B()'[25, 35]

根据这个报错信息找到相应行数,居然在int n这里报错,我寻思着这关n什么事,后面查阅了资料,原因出在第34行的B b[3]这里,定义了一个B类型的数组,没有参数传入,而B类中无适配该成员的构造函数,于是编译器报错

解决方法是,加上相应的构造函数B() {}

线性链表的反转和复制功能

#include<bits/stdc++.h>
using namespace std;
template <class T>
struct Node {
    T data;
    Node<T>* next;
};

template <class T>
class LinkList {
    public: 
    	LinkList(); // create an empty list
    	LinkList(T[], int);
    	//~LinkList();
    	
    	void Reverse(Node<T>* head);
    	Node<T>* Copy(Node<T>* head);
    	Node<T>* first;
}

template <class T>
LinkList<T>::LinkList() {
    first = new Node<T>;
    first->next = NULL;
}

template <class T>
LinkList<T>::LinkList(T arr[], int n) {
    first = new Node<T>;
    Node<T>* p = first;
    for (int i = 0;i < n;i++) {
        Node<T>* s = new Node<T>;
        s->data = arr[i];
        p->next = s;//让first指向第一个节点
        p = s;//虽说把s的地址赋给p,但是first的地址和p不一样,对p操作不会改变first
        //因此first永远指向链表第一个位置
    }
    p->next = NULL;
}

template <class T>
void LinkList<T>::Reverse(Node<T>* head) {
    Node<T>* pre, *cur;
    cur = head->next;
    head->next = NULL;
    while (cur) {
        pre = cur;//让当前节点的上一节点移动到当前节点位置
        cur = cur->next;//当前节点移动到下一个位置
        pre->next = head->next;//这一操作就是让pre不断指向前一个节点
        head->next = pre;//更新节点,让head的next指向pre
    }
    //在画图理解时,要让cur和pre同时向后移动
    //这一部分,建议自己在纸上画出若干个节点和用三个小部件(代表三个指针)模拟一边才能够真正地理解
}
//复盘时自己有个小细节没注意到,这里都是指针变量的赋值操作,这里的赋值只是赋予地址,给予者的值改变,接收者的值不会改变

template <class T>
Node<T>* LinkList<T>::Copy(Node<T>* head) {
    Node<T>* headB = new Node<T>;
    Node<T>* pb = headB;
    Node<T>* pa = head->next;
    while (pa != NULL) {
        Node<T>* temp = new Node<T>;
        temp->data = pa->data;
        temp->next = NULL;//这里用到了一个临时指针变量
        pb->next = temp;//让pb连上temp
        pb = pb->next;
        pa = pa->next;
        //这里向后移动
    }
    return headB;
    //注意这里返回的是headB,在调用时记得再加一个"->next"
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    LinkList<int> list(arr,5);
    cout << "the origin state: " << endl;
    list.PrintList();
    
    cout << endl << "copy list a to list b\n";
    Node<int>* ptr = new Node<int>;
    ptr = list.copy(list.first)->next;
    while (ptr != NULL) {
        cout << ptr->data << ' ';
        ptr = ptr->next;
    }
    
    cout << endl << "reverse the list a\n";
    list.Reverse(list.first);
    list.PrintList();
}

链表反转参考视频

LeetCode力扣刷题 | 剑指Offer 24. 反转链表_哔哩哔哩_bilibili [小姐姐声音很温柔doge]

一分钟教你链表反转_哔哩哔哩_bilibili [这个动画模拟比较贴合代码框的函数]

//谁知道我当时居然还去断点debug把每个节点以及他们的next的地址抄下来去对比
原文出处:Jayden's Blog--数据结构--关于单链表小细节的一些补充

上一篇:数据结构前三章(*回忆)


下一篇:24.判断带头结点的B是不是A的连续子序列