数据结构

数据结构

//链表初始化
linkList()
{
	first = new Node;
	first->next = nullptr;
}

//判空
Empty()
{
	if (first->next = nullptr)return1;
	else return 0;
}

//单链表的遍历
//1.工作指针p初始化
//2.重复执行下述 *** 作，直到指针p为空
//  2.1 输出节点p的数据域
//	2.2 工作指针p后移


PrintList()
{
	Node* p = first->next;		//工作指针p初始化
	while (p != nullptr)
	{
		cout << p->data << "t";
		p = p->next;
	}
	cout << endl;
}

//长度
Length()
{
	Node* p = first->next;
	int count = 0;
	while (p != nullptr)
	{
		count++;
		p = p->next;
	}
	return count++;
}

//按位查找
Get(int i)
{
	Node* p = first->next;
	int count = 1;
	while (p != nullptr && count < i)
	{
		p = p->next;
		count++;
	}
	if (p = nullptr)throw"查找位置错误";
	else return p->data;
}

//按值查找
Locate(int x)
{
	Node* p = first->next;
	int count = 1;
	while (p != nullptr)
	{
		if (p->data = x)return count;
		p = p->next;
		count++;
	}
	return 0;
}

//插入
//输入：单链表的头指针first，插入位置i，待插值x；
//输出：如果插入成功，返回新的单链表，否则返回出入失败信息
//	1.工作指针p初始化为指向头结点；
//	2.查找第i-1个结点并使工作指针p指向该结点
//	3.若查找不成功，说明插入位置不合理，返回插入失败信息
//	  否则，生成元素值为x的新结点s，将s插入到结点p之后
Insert(int i,int x)
{
	Node* p = first, * s = nullptr;  //工作指针p初始化
	int count = 0;
	while (p != nullptr && count < i - 1)	//查找第i-1个结点
	{
		p = p->next;						//工作指针p后移
		count++;
	}
	if (p == nullptr)throw"插入位置错误";	//没有找到第i-1个结点
	else {
		s = new Node; s->data = x;
		s->next = p->next; p->next = s;
	}
}

//删除
Delete(int i)
{
	Node* p = first; *q = nullptr;
	int x, int count = 0;
	while (p != nullptr && count < i - 1)
	{
		p = p->next;
		count++;
	}
	if (p == nullptr || p->next == nullptr)throw"删除位置错误";
	else {
		q = p->next; x = q->data;		//暂存被删结点
		p->next = q->next;				//摘链
		delete q;
		return x;
	}
}

//单链表的建立-头插法
linkList(int a[],int n)
{
	first = new Node; first->next = nullptr;
	for (int i = 0; i < n; i++)
	{
		Node* s = nullptr;
		s = new Node; s->data = a[i];
		s->next = first->next; first->next = s;
	}
}

//单链表的建立--尾插法
linkList(int a[],int n)
{
	first = new Node;		//生成头结点
	Node* r = first, * s = nullptr;			//尾指针初始化
	for (int i = 0; i < n; i++)
	{
		s = new Node; s->data = a[i];
		r->next = s; r = s;
	}
	r->next = nullptr;     //单链表建立完毕，将终端结点的指针域置空
}