雅乐网

向量和列表都是逻辑上线性数据结构，在物理上向量是顺序存储，列表是链式存储。

向量（Vector）接口描述

概述

• 内部使用数组封装，支持随机访问
• 空间复杂度
  • 插入时，若容量不足会翻倍
  • 删除时，目前不会缩小占用内存

构造函数和析构函数

1. Vector(int c = DEFAULT_CAPACITY);
   • 构造一个Vector，容量为c
2. Vector(Vector &s);
   • 复制构造函数，包括_elem指向的内容也会拷贝
3. ~Vector();
   • 析构函数，会delete[] _elem

整体属性

• int size();
  • 返回Vector中元素个数
• int capacity();
  • 返回Vector的最大容量
• bool empty();
  • 判断是否为空。为空返回true
• bool disordered();
  • 是否非降序排列（true乱序 false有序）

元素操作

• T& operator;
  • 返回秩为r的元素的引用
  • 不检查数组越界
• T get(int r);
  • 返回秩为r的元素
  • 如果r超出范围，返回的是0
• T last();
  • 返回最后一个元素
  • 不检查数组越界
• bool put(int r, T e);
  • 将位置r处元素替换为e
  • 若r越界，返回false
• bool insert(int r, T e);
  • 在位置r处插入e 后面元素的后移
  • r的范围为0到size，越界返回false
  • 若容量不足，会按照2倍大小扩容
• bool push_back(T e);
  • 在最后面添加元素e
  • 若容量不足，会按照2倍大小扩容
• T remove(int r);
  • 删除秩为r的元素，并返回删除的元素
  • 如果r不符合范围，返回的是0

排序查找

• void sort(enum sort_method method = QUICK);
  • 按照非降排序
  • 需要使用<运算符进行比较
  • 参数指定排序方法 默认为快速排序
  • 可选方法：
  • 冒泡：BUBBLE
  • 快速排序（默认）：QUICK
  • 归并排序：MERGE
• int find(T e);
  • 查找e 返回下标
  • 若找不到 返回的是-1
• int search(T e);
  • 必须有序才能使用 返回不大于e的最大元素的位置
  • 返回值范围是-1到size-1

遍历

1. void travser(VST &visit);
   • 遍历元素，对每个元素执行visit()操作

向量C++实现

最新的代码见Github。vector.h是实现文件，vector.cpp是简单的演示。

yalewoo/cpp-data-structure · GitHub

下面的代码可能不会及时更新

vector.h

#ifndef MY_VECTOR_H
#define MY_VECTOR_H

#include <cstdlib>
using std::rand;

#define DEFAULT_CAPACITY 20

enum sort_method{
	BUBBLE, INSERT, QUICK, MERGE
};

template <typename T> class Vector{	
	
protected:
	int _size;	//当前元素个数
	int _capacity;	//最大容量
	T* _elem;	//存放向量元素

	void expand();	//扩容为原来的2倍
	void decrease();	//收缩容量为二分之一
	void copyFrom(T a[], int lo, int hi);	//把a数组[lo,hi)部分复制到_elem

	void bubbleSort();	//冒泡排序
	int partition(int lo, int hi);	//快速排序的划分
	void quicksort(int lo, int hi);	//快速排序
	void merge(int lo, int mid, int hi);
	void mergesort(int lo, int hi);

	void swap(T &a, T &b){T tmp = a; a = b; b = tmp;}
	
public:
	Vector(int c = DEFAULT_CAPACITY)
	{
		_size = 0;
		_capacity = c;
		_elem = new T[c];
	}
	Vector(Vector &s)
	{
		copyFrom(s._elem, 0, s._size);
	}
	~Vector() { if (_elem) delete[] _elem; }
	template <typename VST> void travser(VST &visit);	//遍历
	int size() {return _size;}	//返回当前元素总数
	int capacity() {return _capacity;}
	bool empty() {return !_size;}
	T get(int r);	//返回秩为r的元素
	T & operator[](int n) { return _elem[n]; }
	T last() { return _elem[_size-1]; }

	bool put(int r, T e);	//将位置r处元素替换为e
	bool insert(int r, T e);	//在位置r处插入e 后面的后移
	bool push_back(T e) { return insert(_size, e); }
	T remove(int r);	//删除秩为r的元素，并返回
	bool disordered();	//是否非降序排列（true乱序 false有序）

	void sort(enum sort_method method = QUICK);	//按照非降排序

	int find(T e);	//查找e 返回下标
	int search(T e);	//有序查找 返回不大于e的最大元素的位置
	int findInRange(T e, int lo, int hi);	//查找e 返回下标
	int searchInRange(T e, int lo, int hi);	//有序查找 返回不大于e的最大元素的位置

	int deduplicate();	//无序向量去重
	int uniquify();	//有序向量去重
};


//把a[]的[lo, hi)复制到类中
template <typename T>
void Vector<T>::copyFrom(T a[], int lo, int hi)
{
	_capacity = 2 * (lo - hi);
	_elem = new T[_capacity];
	_size = 0;
	while (lo < hi)
	{
		_elem[_size++] = a[lo++];
	}
}

template <typename T>
template <typename VST>
void Vector<T>::travser(VST &visit)
{
	for (int i = 0; i < _size; ++i)
		visit(_elem[i]);
}

template <typename T>
bool Vector<T>::insert(int r, T e)
{
	if (r > _size || r < 0)
		return false;
	if (_size == _capacity)
		expand();

	int i = _size++;
	while (i > r)
	{
		_elem[i] = _elem[i-1];
		--i;
	}
	_elem[i] = e;
	return true;
}

//返回秩为r的元素
template <typename T>
T Vector<T>::get(int r)
{
	if (r >= 0 && r < _size)
		return _elem[r];
	else
		return 0;
}

//将位置r处元素替换为e
template <typename T>
bool Vector<T>::put(int r, T e)
{
	if (r < 0 || r >= _size)
		return false;
	
	_elem[r] = e;
	return true;
}


//删除秩为r的元素，并返回
template <typename T>
T Vector<T>::remove(int r)
{
	if (r < 0 || r >= _size)
		return 0;
	T tmp = _elem[r];
	int i;
	for (i = r; i < _size-1; ++i)
	{
		_elem[i] = _elem[i+1];
	}
	--_size;
	return tmp;
}

//是否非降序排列（true乱序 false有序）
template <typename T>
bool Vector<T>::disordered()
{
	for (int i = 0; i < _size-1; ++i)
	{
		if (_elem[i+1] < _elem[i])
			return true;
	}
	return false;
}

//冒泡排序
template <typename T>
void Vector<T>::bubbleSort()
{
	int i, j, temp;
	
	for (i = _size-1; i > 0; --i)
	{
		int flag = 0;
		for (j = 0; j < i; ++j)
		{
			if (_elem[j+1] < _elem[j])
			{
				temp = _elem[j];
				_elem[j] = _elem[j+1];
				_elem[j+1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
			return;
	}
}


//按照非降排序
template <typename T>
void Vector<T>::sort(enum sort_method method)
{
	switch (method)
	{
	case BUBBLE:
		bubbleSort();
		break;
	case INSERT:
		break;
	case QUICK:
		quicksort(0, _size);
		break;
	case MERGE:
		mergesort(0, _size);
		break;
	default:
		break;
	}
}

//无序时查找
template <typename T>
int Vector<T>::findInRange(T e, int lo, int hi)
{
	for (int i = lo; i < hi; ++i)
	{
		if (_elem[i] == e)
			return i;
	}
	return -1;
}

//有序查找 返回不大于e的最大元素的位置
template <typename T>
int Vector<T>::searchInRange(T e, int lo, int hi)
{
	while (lo < hi)
	{
		int mid = lo + (hi - lo) / 2;
		if (e < _elem[mid])
		{
			hi = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return lo-1;
}

template <typename T>
int Vector<T>::search(T e)
{
	return searchInRange(e, 0, _size);
}

template <typename T>
int Vector<T>::find(T e)
{
	return findInRange(e, 0, _size);
}

//无序向量去重 返回重复个数
template <typename T>
int Vector<T>::deduplicate()
{
	int oldsize = _size;
	for (int i = 0; i < _size; ++i)
	{
		if (findInRange(_elem[i], 0, i) >= 0)
			remove(i);
	}
	return oldsize - _size;
}

//有序向量去重
template <typename T>
int Vector<T>::uniquify()
{
	int oldsize = _size;
	int i = _size - 2;
	while (i >= 0)
	{
		if (_elem[i] == _elem[i+1])
			remove(i+1);

		--i;
	}
	return oldsize - _size;
}

//快速排序的划分
template <typename T>
int Vector<T>::partition(int lo, int hi)
{
	int r = rand() % (hi - lo + 1) + lo;
	int x = _elem[r];
	_elem[r] = _elem[lo];

	while (lo < hi)
	{
		while (hi > lo && !(_elem[hi] < x))
			--hi;
		_elem[lo] = _elem[hi];


		while (lo < hi && !(x < _elem[lo]))
			++lo;
		_elem[hi] = _elem[lo];

	}
	_elem[lo] = x;
	return lo;
}
//快速排序
template <typename T>
void Vector<T>::quicksort(int lo, int hi)
{
	if (hi - lo < 2) return;
	int mid = partition(lo, hi - 1);
	quicksort(lo, mid);
	quicksort(mid+1, hi);
}

template <typename T>
void Vector<T>::merge(int lo, int mid, int hi)
{
	T * L = new int[mid-lo];

	int i;
	int lenL = mid - lo;

	for (i = lo; i < mid; ++i)
		L[i-lo] = _elem[i];

	i = 0;
	int j = mid;
	int k = lo;
	while (i < lenL && j < hi)
	{
		if (!(_elem[j] < L[i]))
			_elem[k++] = L[i++];
		else
			_elem[k++] = _elem[j++];
	}
	while (i < lenL)
		_elem[k++] = L[i++];

	delete[] L;
}
template <typename T>
void Vector<T>::mergesort(int lo, int hi)
{
	if (hi - lo < 2) return;
	int mid = lo + (hi - lo) / 2;
	mergesort(lo, mid);
	mergesort(mid, hi);
	merge(lo, mid, hi);
}

template <typename T>
void Vector<T>::expand()
{
	_capacity *= 2;
	T *old = _elem;
	_elem = new T[_capacity];
	for (int i = 0; i < _size; ++i)
	{
		_elem[i] = old[i];
	}
	delete[] old;
}
template <typename T>
void Vector<T>::decrease()
{
	_capacity /= 2;
	T *old = _elem;
	_elem = new T[_capacity];
	for (int i = 0; i < _size; ++i)
	{
		_elem[i] = old[i];
	}
	delete[] old;
}

#endif

 vector.cpp

#include <iostream>
#include "Vector.h"

using namespace std;

template <typename T>
class MyPrint
{
public:
	void operator()(T e)
	{
		cout << e << " ";
	}
};

int main()
{
	Vector<int> a(5);
	a.insert(0, 2);
	a.insert(0, 6);
	a.insert(0, 7);
	// cout << a.capacity() << endl;
	a.insert(0, 4);
	a.insert(0, 4);
	a.insert(0, 5);
	a.insert(0, 9);
	a.insert(0, 9);
	a.insert(0, 5);
	a.insert(0, 5);
	a.insert(0, 9);
	a.insert(0, 9);
	a.insert(0, 5);
	// cout << a.capacity() << endl;

	MyPrint<int> visit;

	// a.travser(visit);
	a.sort();
	a.travser(visit);

	cout << endl;
	cout << a.search(1) << endl;
	cout << a.search(2) << endl;
	cout << a.search(3) << endl;
	//cout << "uniquify " << a.uniquify() << endl;
	//cout << "deduplicate " << a.deduplicate() << endl;
	
	//cout << a.search(7, 0, a.size());
	//cout << a.search(8, 0, a.size());


	return 0;
}

列表（List）接口

概述

• 使用链表实现
• 一个初始的List包含了哨兵头结点和尾结点

构造函数和析构函数

• List()
  • 大小初始化为0，头结点和尾结点互相指向
• ~List()
  • 释放链表中所有结点的内存

整体属性

• int size();
  • 返回元素个数
• bool empty();
  • 判断列表是否为空
• bool disordered();
  • 如果不是有序的，返回true

元素操作

• Posi(T) first();
  • 返回第一个元素的位置
  • 若列表为空 返回的是尾结点的位置
• Posi(T) last();
  • 返回最后一个元素的位置
  • 若列表为空，返回的是头结点的位置
• Posi(T) insertAsFirst(T e);
  • 把e插入到列表的头部
  • 返回新插入结点的位置
• Posi(T) insertAsLast(T e);
  • 把e插入到列表的尾部
  • 返回新插入结点的位置
• Posi(T) insertAfter(Posi(T) p, T e);
  • 把e插入到p指向结点的后面
  • 不检查p是否有效
• Posi(T) insertBefore(Posi(T) p, T e);
  • 把e插入到p指向结点的前面
  • 不检查p是否有效
• T remove(Posi(T) p);
  • 删除p指向的结点
  • 不检查p是否有效

排序查找

• void sort();
  • 按照非降顺序进行插入排序
• Posi(T) find(T e);
  • 查找元素e，返回第一个e的结点指针
  • 找不到时，返回NULL
• Posi(T) search(T e);
  • 有序列表查找，返回不大于e的最后一个元素结点位置

遍历

• void travser(VST &visit);
  • 遍历，对结点中每个元素执行visit()

C++实现

最新的代码见Github。list.h是实现文件，list.cpp是简单的演示。

yalewoo/cpp-data-structure · GitHub

下面的代码可能不会及时更新

list.h

#ifndef MY_LIST_H
#define MY_LIST_H

#include <iostream>
#define Posi(T) ListNode<T>*


template <typename T> struct ListNode
{
	T data;
	Posi(T) pred;
	Posi(T) next;
	ListNode() = default;
	ListNode(T e, Posi(T) p = NULL, Posi(T) n = NULL) : data(e), pred(p), next(n) { }
	Posi(T) insertPred(T e);
	Posi(T) insertNext(T e);
};
template <typename T> class List
{
protected:
	int _size;
	ListNode<T> head;
	ListNode<T> tail;
public:
	List();
	~List();
	int size() {return _size; }
	bool empty() {return !_size; }
	Posi(T) first() {return head.next;}
	Posi(T) last() {return tail.pred;}
	Posi(T) insertAsFirst(T e);
	Posi(T) insertAsLast(T e);
	template <typename VST> void travser(VST &visit);	//遍历
	Posi(T) insertAfter(Posi(T) p, T e);
	Posi(T) insertBefore(Posi(T) p, T e);
	T remove(Posi(T) p);
	bool disordered();
	void sort();
	Posi(T) find(T e);
	Posi(T) search(T e);
};

template <typename T>
List<T>::~List()
{
	Posi(T) x = head.next;
	Posi(T) x1 = x;
	while (x != &tail)
	{
		x1 = x;
		x = x->next;
		delete x1;
	}
}
template <typename T>
Posi(T) ListNode<T>::insertPred(T e)
{
	Posi(T) x = new ListNode(e, this->pred, this);
	this->pred->next = x;
	this->pred = x;
	return x;
}
template <typename T>
Posi(T) ListNode<T>::insertNext(T e)
{
	Posi(T) x = new ListNode(e, this, this->next);
	this->next->pred = x;
	this->next = x;
	return x;
}


template <typename T>
List<T>::List()
{
	_size = 0;

	head.next = &tail;
	tail.pred = &head;

	head.pred = NULL;
	tail.next = NULL;
}

template <typename T>
Posi(T) List<T>::insertAsFirst(T e)
{
	Posi(T) x = new ListNode<T> (e, &head, head.next);
	head.next->pred = x;
	head.next = x;
	++_size;
	return x;
}
template <typename T>
Posi(T) List<T>::insertAsLast(T e)
{
	Posi(T) x = new ListNode<T> (e, tail.pred, &tail);
	tail.pred->next = x;
	tail.pred = x;
	++_size;
	return x;
}

template <typename T>
template <typename VST>
void List<T>::travser(VST &visit)
{
	Posi(T) x = head.next;
	while (x != &tail)
	{
		visit(x->data);
		x = x->next;
	}
}

template <typename T>
Posi(T) List<T>::insertAfter(Posi(T) p, T e)
{
	Posi(T) x = new ListNode<T> (e, p, p->next);
	p->next = x;
	x->next->pred = x;
	++_size;
	return x;
}
template <typename T>
Posi(T) List<T>::insertBefore(Posi(T) p, T e)
{
	Posi(T) x = new ListNode<T> (e, p->pred, p);
	p->pred = x;
	x->pred->next = x;
	++_size;
	return x;
}

template <typename T>
T List<T>::remove(Posi(T) p)
{
	T tmp = p->data;
	p->pred->next = p->next;
	p->next->pred = p->pred;
	delete p;
	--_size;
	return tmp;
}

template <typename T>
bool List<T>::disordered()
{
	Posi(T) p = head.next;
	T e = p->data;
	while (p != &tail)
	{
		if (p->data < e)
			return true;
		e = p->data;
		p = p->next;
	}
	return false;
}

template <typename T>
void List<T>::sort()
{
	Posi(T) i = head.next;
	Posi(T) j = i;
	while (i != &tail)
	{
		for (j = head.next; j != i && j->data <= i->data; j = j->next)
			;
		Posi(T) newi = i->next;
		j->insertPred(i->data);
		remove(i);
		i = newi;
	}
}

template <typename T>
Posi(T) List<T>::find(T e)
{
	Posi(T) x = head.next;
	while (x != &tail)
	{
		if (x->data == e)
			return x;
		x = x->next;
	}
	return 0;
}

//return the largest x which is not bigger than e
//so we can use List.insertAfter(List.search(e), e) to insert e in a sorted list
template <typename T>
Posi(T) List<T>::search(T e)
{
	Posi(T) x = head.next;
	while (x != &tail && x->data <= e)
	{
		x = x->next;
	}
	return x->pred;
}

#endif

list.cpp

#include <iostream>
#include "List.h"

using namespace std;

template <typename T>
class MyPrint
{
public:
	void operator()(T e)
	{
		cout << e << " ";
	}
};

int main()
{
	List<int> l;
	l.insertAsFirst(5);
	Posi(int) p = l.insertAsFirst(4);
	l.insertAsFirst(3);
	l.insertAsFirst(8);
	l.insertAsFirst(22);
	l.insertBefore(l.insertAsFirst(2), 9);

	MyPrint<int> visit;
	l.travser(visit);
	l.remove(p);
	cout << endl;
	l.travser(visit);
	cout << endl;

	//cout << l.disordered();
	l.sort();
	l.insertAfter(l.search(7), 7);
	l.travser(visit);


	return 0;
}