线性表整理

线性表

线性表的基础

线性表的之间定义我就不再多说了，直接来看一下它的基本运算：

（1）创建一个空的线性表（create） （2）删除数据表中的所有线性结构（clear） （3）求线性表的长度（length） （4）在第i个位置插图一个元素（insert） （5）删除第i个位置的元素（remove） （6）搜索元素，检查某个元素x在线性表中是否出现，并返回x的位置（search） （7）返回线性表中第i个数据元素的值（visit） （8）按序访问线性表的每一个数据元素（traverse）

我们可以直接产生面向对象的程序设计

1
2
3
4
5
6
7
8
9
10
11
12
template<class T>//这里面我使用了一个模板，但是实际上不一定需要，只是为了更具有普适性
class linearlist{
    public:
    	virtual void create() = 0;
    	virtual int length() const = 0;//在类的成员函数里面能加const的都加上const
    	virtual void insert(int i) = 0;
    	virtual void remove(int i) = 0;
    	virtual int search(const T &x) const = 0;//遇到负责类型作为参数的时候，就直接const + 复杂类型 + &这样最节省时间和空间
    	virtual T visit(int i)b const = 0;
    	virtual void traverse() const = 0;
    	virtual ~list(){};//为什么这个地方不再构建纯虚函数，我在后面应该会单开一篇来讲纯虚函数的事
};

在上面的代码里除了析构函数以外，其他基本上都是纯虚函数，这样相当于勒令衍生类解决这些问题，这样一个基本的线性表的就构建好了，我们为什么在上面只是设置成员函数，但是没有去设置数据成员？因为线性表有多种表示方式，既可以是顺序表，也可以是链表，链表又可以分为单双链表，顺序表也有多种表达方式，不同的表示方式我们要设置的私有数据成员也不同，我们只能够放到衍生类里面去实现。

顺序表类

顺序列表基础申明

顺序实现是我们存放数据最自然的一种方式，基本上所有事务我要把它归类，首先都是这么干的，它的基础逻辑就是数组，不过在C++中，数组确实不太好用（主要是在申明的时候就要给定最大容量，这对于经常要使用变量的我们来说还是十分复杂的），但是通过指针，我们就可以很清爽地规避掉这个问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
class seqlist: public linearlist<T>{ //通过public的方式来继承linearlist
    private:
		T *data;
    	int curlength;//当下长度
    	int maxsize;//最大长度
    	void doublespace();//私有的成员函数，将空间双倍，为什么将他设置为私有？因为这个基本上只有在成员函数里面才会运用到，不需要对用户开放，当然，如果你要坚持写在public里面，也没有问题
    public:
    	seqlist(int startsize);//构造函数
    	~seqlist();//析构函数，来清除动态数组的
    	void clear();//来清除其他东西的
    	int length() const;
    	void insert(int i, const T &x);
    	void remove(int i);
    	int search(const T &x) const;
    	T visit(int i) const;
    	void traverse() const;
};

基本上还是跟上面一样的说明，但是这次就不能再打太极了，必须解决，不过一个习惯就是不要放在类里面解决（除非真的很短）

析构函数，clear，length，visit，traverse函数的实现

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
//~seqlist的实现
template <class T>
seqlist<T>::~seqlist(){
    delete [] data;
}
//clear的实现
template <class T>
void seqlist<T>::clear(){
    curlength = 0;
    maxsize = 0;
}
//length的实现
template <class T>
int seqlist<T>::length()const{
    return curlength;
}
//visit的实现
template <class T>
T seqlist<T>::visit(int i)const{
    return data[i];
}
//traverse的实现
template <class T>
void seqlist<T>::traverse()const{
	for(int i = 0; i <= curlength; i++)
        	cout << data[i] << " ";
   	cout << endl;
}

上面是最简单的几个功能的实现，基本上所有学习过C++的读者都可以轻松自己编写，除了traverse函数的时间复杂度是O(n)，其他的时间复杂度都是O(1)，接下来几个比较能够体现顺序类列表的特点，我分开来列：

构造函数的实现

1
2
3
4
5
6
7
//构造函数的实现
template <class T>
seqlist<T>::seqlist(int startsize){
    data = new T [startsize];
    maxsize = startsize;
    currentlength = 0;
}

这个其实也非常简单（或许我应该把它列在上面的，算了，懒得动）

search的实现

1
2
3
4
5
6
7
//search的实现
template <class T>
int seqlist<T>::search(const T &x)const{
    int i;
    for(i = 0; i < curlength && data[i] != x; i++);
    return ((i == curlength)?-1:i);
}

其实讲真的，基本上所有人都能看得出来这块挺麻烦的，但是搜索就是这样， 除非储存下标，不然就是需要遍历，时间复杂度就是O(n)级别的。

doublespace和search函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//doublespace和search函数的实现
template <class T>
void seqlist<T>::doublespace(){
    T *tmp = data;
    maxsize *= 2;
    data = new T [maxsize];
    for(int i = 0; i < curlength; i++)
        data[i] = tmp[i];
    delete [] tmp;
}
template <class T>
void seqlist<T>::insert(int i,const T &x){
	if(curlength == maxsize)
		doublespace();
    for(int j = i; j < curlength; j++)
        data[j + 1] = data[j];
    data[i] = x;
    curlength++;
}

基本上十分明显了，很简单就是我要插入在第i的位置，那么我把自从第i往后的每一位都向后挪一个位置，再把第i位变成我要的x这样子就完成了，这里就是顺序表和链表最大的不同，不过两者基本上都是O(n)的时间复杂度，因为顺序表知道下标但是挪动需要花一定的时间，而链表是挪动不用花时间但是不知道下表（但是实际上可以解决）

remove函数的实现

1
2
3
4
5
6
7
//remove的实现
template <class T>
void seqlist<T>::remove(int i){
    for(int j = i; j < curlength; j++)
        data[j] = data[j + 1];
    curlength--;
}

顺序表就这么多内容了，基本上没有什么例外，确实比较简单，链表在move函数那边比较具有迷惑性，需要好好解释一下的我们接下来探讨

单链表

单链表类的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <class T>
class slinklist: public linearlist<T>{
    private:
    	struct node{
            T data;
            node *next;//这两个是链表的基本元素
            node(const T &x, node *n = NULL){data = x; next = n;}//这里面是node的构造函数
            node():next(NULL){}//这个是没有初始化的时候的构造函数，将next指针指向NULL是避免错误的一个非常好的做法
            ~node(){}
        };
    	node *head;//这个是头节点
    	int curlength;//这个是当下的长度
    	node *move(int i) const;
    	public:
    		slinklist();
    		void clear();
    		~slinklist(){clear();delete head;}//clear就是将所有除头节点以外的节点全部清除
    		int length() const {return curlength};
    		void insert(int i,const T &x);
    		void remove(int i);
    		int search(const T &x)
             T visit(int i) const;
    		void traverse() const;
};

这里里面的定义基本上都跟上面一样，不过这里需要注意的就是node作为结构体，也具有构造函数和析构函数，形式跟类差不多

move函数的实现

1
2
3
4
5
6
7
//move函数的实现
template<class T>
typename slinklist<T>::node *slinklist<T>::move(int i) const{//这个地方需要申明的就是typename是一个可有可无的量，其本质就是对编译器申明这里是一个变量名，可能有些不太先进的编译器没有办法识别出来
    node *p = head;
    while(i-- >= 0)	p = p -> next;//这里面i-- >= 0总共会循环i + 1次
    return p;
}

这里面为什么是i + 1次循环？而不是i我们的头节点并不是我们的第0个节点，我们要从头节点移动到第0个节点需要移动1次，第一个节点需要2次……以此类推，你要到第i个节点，就需要i + 1次，那既然如此，我们为什么不直接去除掉head节点，来考虑剩下来的问题？这个问题我们下文会考虑

构造函数的实现

1
2
3
4
5
6
//slinklist的实现
template<class T>
slinklist<T>::slinklist(){
	head = new node;
    curlength = 0;
}

非常简单，没有什么好讲的（所以你干嘛写它呢？）

clear函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
//clear函数的实现
template<class T>
void slinklist <T> ::clear(){
	node *p = head->next ,*q;
    head->next = NULL;
    while(p != NULL){
		q = p->next;
        delete p;
        p = q;//删除，然后移动到下一个节点
    }
    curlength = 0;
}

也是非常的简单，不多说了

insert和remove函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//insert函数的实现
template<class T>
void slinklist<T>::insert(int i, const T &x){
	node *pos;
    pos = move(i - 1);
    pos->next = new node(x, pos->next);//这里使用了我在定义里面写的node的构造函数
    curlength++;
}
//remove函数的实现
template<class T>
void slinklist<T>::remove(int i){
	node *pos, *delp;
    pos = move(i - 1);
    delp = pos->next;
    pos->next = delp->next;
    delete delp;
    curlength--;
}

终于来了点有意思的东西了，第一个问题：为什么move函数的参数是i - 1?而不是i呢？我们要去除第i个节点，自然就是要将i - 1和i + 1链接起来，所以实际上，我们将pos移到i - 1的位置是便于操作的，因为我们这边是单链表，你找你的下家容易，但是你去找上家比较的困难

另外再说，为什么我们需要将node后面写上x, pos->next的参数，可以参考我在定义里面写的node(const T &x, node *n = NULL){data = x; next = n;}我们将这里面的x变为一个新的节点的data然后将原来pos->next变作这个新节点的next，最后将post->next改为这个新节点的地址，如果我们不要求代码的美观度这么高，我们可以写得明显一些：

1
2
3
4
node *tmp = new node;
tmp->data = x;
tmp->next = pos->next;
pos->next = tmp;

上面这四行代码可以达到同样的效果

在remove函数的实现中，注意delp函数的使用，因为delp函数其实是记下来给用来释放空间的，不然会产生内存泄漏。

search，visit，traverse函数的实现

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
//search函数的实现
template<class T>
int slinklist<T>::search(const T &x)const{
	node *p = head->next;
    int i = 0;
    while(p != NULL && p->data != x){
		p = p->next;
        i++;
    }
    if(p == NULL)
        return -1;//如果p是到NULL的时候停下来的说明没有找到x，x不存在在顺序链表里
    else
        return i;
}
//visit函数的实现
template<class T>
T slinklist<T>::visit(int i)const{
	return move(i)->data;
}
//traverse函数的实现
template<class T>
void slinklist<T>::traverse()const{
	node *p = head->next;
    while(p != NULL){
        cout << p->data << " ";
		p = p->next;
    }
    cout << endl;
}

这三个函数还是十分简单的，基本上就是遍历了，没有什么太过困难的。

无头结点的函数实现

但是

你觉得，这就结束了吗？

不！

我们还要尝试无头结点的情况下面的单链表，判断为什么拥有头节点是一件更好的事情，我们来尝试一下无头结点情况下的insert和remove函数

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
//无头结点下的insert函数的实现
template<class T>
void slinklist<T>::insert(int i, const T &x){
	if(i == 0){
		p = head;
        head = new node(x,p);
    }
    else if(i > 0){
        p = move(i - 2);
        p->next = new node(x,p->next);//其实在i > 0的情况下其实差不多，没有什么太大的区别，就是只能移动i - 2位了
    }
    curlength++;
}
//无头结点下的remove函数的实现
template<class T>
void slinklist<T>::remove(int i){
	node *pos, *delp;
    if(i == 0){
        delp = head;
        head = delp->next;
    }
    else if(i > 0){
		p = move(i - 2);
        delp = p->next;
        p->next = delp->next;
    }
    delete delp;
    curlength--;
}

明显可以看出来复杂得多了，因为我们需要对于有i == 0的情况进行专门的判断，我建议有精力的读者可以自己用笔来画画图，来理解一下为什么这里面i == 0需要专门判断，笔者本来也想写一写然后贴图片上去的，但是作业还没有写完（悲），就不能继续写了

总结

数据结构知识整理
#链表 #数组 #更新中
线性表整理
http://example.com/2025/07/04/线性表整理/
作者
牧丛
发布于
2025年7月4日
许可协议