线性表的链式表示和C++实现

◦ 链表 ◦ 链表是由一系列叫做 结点 （ node ）的对象连 接起来的数据结构。一般来说，结点之间用 指针来连接。 ◦ 链表结点类 (linkNode) 由两部分组成： 存储元素值的 element 域； 存储结点指针的 next 域； ◦ 链表类由多个链表结点构成，不同于顺序表的 连续存储，这些链表结点离散分布在存储空间 中，通过链表结点的指针进行连接。 ◦ 链表类的数据元素包含链表的首尾结点以及当 前结点的指针，通过指针来访问链表中的所有 元素。

#include
#include"assert.h"
using namespace std;
const int  LIST_SIZE = 1000;//限定当前线性表的最大长度
class node//建立一个结点类
{
public:

	char n;//存入结点的数据元素
	node* next;//指向下一结点的指针
	node(node* nextval = NULL) { next = nextval; };//构造函数1
	node(const char& elem, node* nextval = NULL) 
	{
		n = elem;  next = nextval;
	}//构造函数2
	~node() {};//析构函数
};
class list {// 单链表类
private:
	node* head;// 头指针
	node* tail;// 尾指针
	node* curr;// 指向当前元素的指针
	int number;//统计个数
public:
	list(const int sz = LIST_SIZE); // 构造函数
	~list();// 析构函数
	void clear(); // 从表中清除所有元素
	void insert(const char&); // 在当前位置插入一个新元素
	char remove();// 删除并返回当前元素
	void setFirst(); // 置光标于第一个位置
	void next();// 移动光标到下一位置
	void prev();// 移动光标到前一位置
	void setPos(const int); // 置光标于指定位置
	void setValue(const char&); // 给当前位置的元素赋值
	int length() const;// 返回表的当前长度
	char currValue() const; // 返回当前元素的值
	bool isEmpty() const; // 如果表为空则返回TRUE
	bool isInList() const; // 如果光标在表内则返回TRUE
	bool find(const char&);//从当前位置开始寻找某个元素

};
list::list(const int sz )
{
	head = nullptr;
	tail = nullptr;
	number = 0;

}
list::~list() { // 析构函数
	while (head != NULL) { // 释放链表的所有节点占用的空间
		curr = head;
		head = head->next;
		delete curr;
	}
}
void list::clear() // 从表中清除所有元素
{
	while (head->next != NULL)//释放所有空间，保留表头
	{
		curr = head->next;
		head->next = curr->next;
		delete curr;
	}
	curr = head;
}
void list::setFirst() // 置光标于第一个位置
{
	curr = head;
}
void list::next()// 移动光标到下一位置
{
	if (curr != NULL)
		curr = curr->next;
}
void list::prev()// 移动光标到前一位置
{	
	node* temp = head;
	if (curr == NULL || curr == head)//当前指针为空或为头指针时
	{
		curr = NULL;
		return;
	}
	while ((temp != NULL) && (temp->next != curr))//遍历指针到当前光标前一位置且指针不为空
	{
		temp = temp->next;
	}
	curr = temp;
	return;
}

void list::setPos(const int pos) // 置光标于指定位置
{
    curr = head;
	for (int i = 0; (curr != NULL) && (i < pos); i++)
		curr = curr->next;
}
bool list::isInList() const // 如果光标在表内则返回TRUE
{
	if (curr != NULL && curr->next != NULL)
	{
		return true;
	}
	else return false;
}
void list::setValue(const char&elem) // 给当前位置的元素赋值
{
	assert(isInList());
	curr->n = elem;
}
int list::length() const// 返回表的当前长度
{
	return number;
}
char list::currValue() const // 返回当前元素的值
{
	assert(isInList());
	return curr->next->n;
}
bool list::isEmpty() const// 如果表为空则返回TRUE
{
	return head->next == NULL;
}
void list::insert(const char&elem) // 在当前位置（后面）插入一个新元素
{
	assert(curr != NULL);
	curr->next = new node (elem, curr->next);

}
char list::remove()// 删除并返回当前(后面)元素
{
	assert(isInList());
	char temp = curr->next->n;
	node* ltemp = curr-> next;
	curr-> next = ltemp-> next;//更新链接关系
	if (tail == ltemp) tail = curr;
	delete ltemp;//删除链表结点
	return temp;

}
bool list::find(const char&val)//从当前位置开始寻找某个元素
{
	while(isInList())
	if (curr-> next->n == val)
		return true;
	else curr = curr-> next;
	return false;

}

数据结构冲啊冲啊！！！！