[数据结构与算法]数据结构与算法---线性表---链表(MOOC)

线性表

链表

• 通过指针把它的一串存储结点链接成一个链
• 存储结点有两个部分组成:
  — 数据域+指针域(后继地址)
  data next

分类(根据链接方式和指针多寡)

• 单链
• 双链
• 循环链表

单链表

简单的单链表

— 整个单链表:head
— 第一个结点:head
— 空表判断: head==NULL
— 当前结点a : curr

带头结点的单链表

• 整个单链表:head
• 第一个结点:head->next,head!=NULL
• 空表判断:head->next=NULL
• 当前结点a:fence->next(curr隐含)

单链表的结点类型

template<class T>
class Link {
public:
	T data;
	Link<T>* next;

	Link(const T info, const Link<T>* nextValue = NULL) {
		data = info;
		next = nextValue;
	}
	Link(const Link<T>* nextValue) {
		next = nextValue;
	}
};

单链表类定义

template<class T>
class LinkList :public List<T> {
private:
	Link<T>* head, * tail;					//单链表的头,尾指针
	Link<T>* setPos(const int k);			//第k个元素指针
public:
	LinkList(int s);						//构造函数
	~LinkList();							//析构函数
	bool IsEmpty();							//判断链表是否为空
	bool Clear();							//将链表存储的内容清除,成为空表
	int Length();							//返回此顺序表的的当前实际长度
	bool Append(const T value);				//表尾添加一个元素value,表的长度增1
	bool Insert(const int k, const T value);//位置k上插入一个元素
	bool Delete(const int k);				//删除位置k上的元素,表的长度减1
	bool GetValue(const int k, T& value);	//返回位置k的元素值
	bool GetPos(int& k, const T value);		//查找值为value的元素
};

查找单链表中第i个结点

//查找单链表中第i个结点
//查找返回值是找到的结点指针
template<class T>
Link<T>* LinkList<T>::setPos(int i) {
	int count = 0;
	if (i == -1) {
		return head;					//i为-1则定位到头结点
	}

	//循环定位,若i为0则定位到第一个结点
	Link<T>* k = head->next;
	while (k != NULL && count < i) {
		k = k->next;
		count++;
	}
	//指向第i结点,i=0,1,...,当链表中结点数小于i时返回NULL
	return k;
}

单链表的插入

• 创建新结点
• 新结点指向右边的结点
• 左边结点指向新结点

//单链表插入算法
//插入数据内容为value的新结点作为第i个结点
template<class T>
bool LinkList<T>::Insert(const int i, const T value) {
	Link<T>* p, * q;
	if ((p = setPos(i - 1)) == NULL) {
		//p是第i个结点的前驱
		cout << "非法插入点" << endl;
		return false;
	}
	q = new Link<T>(value, p->next);
	p->next = q;
	if (p == tail) {					//插入点在链尾,插入结点成为新的链尾
		tail = q;
	}
	return false;
}

单链表的删除

• 从链表中删除结点x
  — 用p指向元素x的结点的前驱结点
  — 删除元素为x的结点
  — 释放x占据的空间