数据结构——线性表

简介: 1 线性表的特性是数据元素之间在逻辑结构上存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。 2 当线性表的长度n=0时,为一个空表。当n>0时,序列中必存在唯一的一个“第一个元素”,也必存在唯一的一个“最后一个元素”。除第一个元素外,每一个元素均有唯一的前驱;除最后一个元素外,

1 线性表的特性是数据元素之间在逻辑结构上存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。


2 当线性表的长度n=0时,为一个空表。当n>0时,序列中必存在唯一的一个“第一个元素”,也必存在唯一的一个“最后一个元素”。除第一个元素外,每一个元素均有唯一的前驱;除最后一个元素外,每一个元素均有唯一的后继。


3 线性表抽象类

文件List.h

#pragma once
template <class T>
class List
{
public:
	virtual bool IsEmpty() const = 0;
	virtual int Length() const = 0;
	virtual void Clear() = 0;
	virtual bool GetElem(T&, int) const = 0;
	virtual bool SetElem(const T&, int) = 0;
	virtual int LocateElem(const T&) const = 0;
	virtual int LocatePrior(const T&) const = 0;
	virtual int LocateNext(const T&) const = 0;
	virtual bool Insert(const T&, int) = 0;
	virtual bool Append(const T&) = 0;
	virtual bool Delete(T&, int) = 0;
	virtual void Traverse(void(*visit)(const T&)) const = 0; //遍历
};


4 顺序表

#pragma once
#include "List.h"
#include <windows.h>
template <class T>
class SqList :
	public List<T>
{
public:
	SqList(int m = 0);
	SqList(const SqList<T>&);
	~SqList();
	bool IsEmpty() const {return len <= 0;}
	int Length() const {return len;}
	void Clear(){len = 0;}
	bool GetElem(T&, int) const;
	bool SetElem(const T&, int);
	int LocateElem(const T&) const;
	int LocatePrior(const T&) const;
	int LocateNext(const T&) const;
	bool Insert(const T&, int);
	bool Append(const T&);
	bool Delete(T&, int);
	void Traverse(void (*visit)(const T&)) const;
	SqList<T>& operator=(const SqList<T>&);
private:
	int len;
	int size;
	T* elem;
	void CopyFrom(const SqList<T>&);
};

template<class T> 
SqList<T>::SqList(int m)
{
	len = 0;
	if (m == 0)
	{
		elem = NULL;
	}
	else
	{
		elem = new T[m];
	}
	size = m;
}

template<class T>
SqList<T>::SqList(const SqList<T>& r)
{
	len = 0;
	size = 0;
	elem = NULL;
	CopyFrom(r);
}

template<class T>
SqList<T>::~SqList()
{
	delete [] elem;
}

template<class T> 
bool SqList<T>::GetElem(T& e, int i) const
{
	if (len < 1 || i > len)
	{
		return false;
	}
	e = elem[i-1];
	return true;
}

template<class T>
bool SqList<T>::SetElem(const T& e, int i)
{
	if (len < 1 || i > len)
	{
		return false;
	}
	elem[i-1] = e;
	return true;
}

template<class T>
int SqList<T>::LocateElem(const T& e) const
{
	T* p = elem;
	int i = 1;
	while (i <= len && *p != e)
	{
		i++;
		p++;
	}
	if (i <= len)
	{
		return len;
	}
	return 0;
}

template<class T>
int SqList<T>::LocatePrior(const T& e) const
{
	int i = LocateElem(e);
	if (i > 1)
	{
		return i - 1;
	}
	return 0;
}

template<class T>
int SqList<T>::LocateNext(const T& e) const 
{
	int i = LocateElem(e);
	if (i >= 1 && i < len)
	{
		return i + 1;
	}
	return 0;
}

template<class T>
bool SqList<T>::Insert(const T& e, int i)
{
	if (i < 1 || i > len + 1)
	{
		return false;
	}
	if (len >= size)
	{
		T* newbase;
		newbase = new T[size+10];
		if (!newbase)
		{
			return false;
		}
		for(int j = 0; j < len; j++)
		{
			newbase[j] = elem[j];
		}
		delete [] elem;
		elem = newbase;
		size += 10;
	}

	T *p,*q;
	q = &elem[i-1];
	for (p = &elem[len-1]; p >= q; p--)
	{
		*(p+1) = *p;
	}
	*q = e;
	++len;
	return true;
}

template<class T>
bool SqList<T>::Append(const T& e)
{
	if (len >= size)
	{
		T* newbase;
		newbase = new T[size+10];
		for (int j = 0; j < len; j++)
		{
			newbase[j] = elem[j];
		}
		delete [] elem;
		elem = newbase;
		size += 10;
	}
	elem[len++] = e;
	return true;
}

template<class T>
bool SqList<T>::Delete(T& e, int i)
{
	if (i < 1 || i > len)
	{
		return false;
	}
	T *p,*q;
	p = &elem[i-1];
	e = *p;
	q = elem + len -1;
	for (++p; p <= q; ++p)
	{
		*(p-1) = *p;
	}
	--len;
	return true;
}

template<class T>
void SqList<T>::Traverse(void (*visit)(const T& e)) const
{
	T* p= elem;
	for (int i = 0; i < len; i++)
	{
		visit(*p++);
	}
}

template<class T>
SqList<T>& SqList<T>::operator=(const SqList<T>& r)
{
	Clear();
	CopyFrom(r);
	return *this;
}

template<class T>
void SqList<T>::CopyFrom(const SqList<T>& r)
{
	T* p = r.elem;
	for (int i = 0; i < r.len; i++)
	{
		Append(*p++);
	}
}


5 链表

若线性表在链式存储映像下,结点之间是通过唯一的一个后继结点指针域形成链接的,则存储结构被称为单链表。单链表的结点结构如下:

//LinkNode.h
template<class T>
struct LinkNode
{
	T data;
	LinkNode<T>* next;
};
单链表类模板:
//LinkList.h
#ifndef _LINKLIST_
#define _LINKLIST_
#include "List.h"
#include "LinkNode.h"

template<class T>
class LinkList: public List<T>
{
public:
	LinkList();
	LinkList(const LinkList<T>&);
	~LinkList();
	bool IsEmpty() const {return len <= 0;}
	int Length() const {return len;}
	void Clear();
	bool GetElem(T&, int) const;
	bool SetElem(const T&, int);
	int LocateElem(const T&) const;
	int LocatePrior(const T&) const;
	int LocateNext(const T&) const;
	bool Insert(const T&, int);
	bool Append(const T&);
	bool Delete(T&, int);
	void Traverse(void (*visit)(const T&)) const;
	LinkList<T>& operator=(const LinkList<T>&);
private:
	int len;
	LinkNode<T>* head;
	LinkNode<T>* tail;
	void CopyFrom(const LinkList<T>&);
};

template<class T>
LinkList<T>::LinkList()
{
	len = 0;
	head = tail = new LinkNode<T>;
	head->next = NULL;
}

template<class T>
LinkList<T>::LinkList(const LinkList<T>& r)
{
	CopyFrom(r);
}

//释放单链表中包括头节点在内的所有表节点
template<class T>
LinkList<T>::~LinkList()
{
	Clear();
	delete head;
}

//释放单链表中所有的数据节点
template<class T>
void LinkList<T>::Clear()
{
	LinkNode<T> *p = head->next, *q;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	tail = head;
	head->next = NULL;
	len = 0;
}

template<class T>
bool LinkList<T>::GetElem(T& e, int i) const
{
	if (i < 1 || i > len)
	{
		return false;
	}
	LinkNode<T>* p = head->next;
	int k = 1;
	while (k < i)
	{
		p = p->next;
		k++;
	}
	e = p->data;
	return true;
}

template<class T>
bool LinkList<T>::SetElem(const T& e, int i)
{
	if (i < 1 || i > len)
	{
		return false;
	}
	LinkNode<T>* p = head->next;
	int k = 1;
	while (k < i)
	{
		p = p->next;
		k++;
	}
	p->data = e;
	return true;
}

template<class T>
int LinkList<T>::LocateElem(const T& e) const
{
	int i = 1;
	LinkNode<T>* p = head->next;
	while (p && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (p)
	{
		return i;
	}
	return 0;
}

template<class T>
int LinkList<T>::LocatePrior(const T& e) const
{
	int i = LocateElem(e);
	if (i > 1)
	{
		return i - 1;
	}
	return 0;
}

template<class T>
int LinkList<T>::LocateNext(const T& e) const
{
	int i = LocateElem(e);
	if (i >= 1 && i < len)
	{
		return i + 1;
	}
	return 0;
}

template<class T>
bool LinkList<T>::Insert(const T& e, int i)
{
	LinkNode<T> *p,*q;
	int k = 1;
	if (i < 1 || i > len + 1)
	{
		return false;
	}

	q = new LinkNode<T>;
	q->data = e;
	p = head;
	while (k < i)
	{
		p = p->next;
		k++;
	}

	q->next = p->next;
	p->next = q;

	if (i == len + 1)
	{
		tail = q;
	}
	++len;
	return true;
}

template<class T>
bool LinkList<T>::Append(const T& e)
{
	LinkNode<T>* p = new LinkNode<T>;
	p->data = e;
	tail->next = p;
	tail = p;
	tail->next = NULL;
	++len;
	return true;
}

template<class T>
bool LinkList<T>::Delete(T& e, int i)
{
	if (i < 1 || i > len)
	{
		return false;
	}
	LinkNode<T> *p,*q;
	p = head;
	int k = 1;
	while (k < i)
	{
		p = p->next;
		k++
	}
	q = p->next;
	p->next = q->next;
	if (q == tail)
	{
		tail = p;
	}
	e = q->data;
	delete q;
	--len;
	return true;
}

template<class T>
void LinkList<T>::Traverse(void (*visit)(const T& e)) const
{
	LinkNode<T> *p = head->next;
	while (p)
	{
		visit(p->data);
		p = p->next;
	}
}

template<class T>
LinkList<T>& LinkList<T>::operator=(const LinkList<T>& r)
{
	Clear();
	delete head;
	CopyFrom(r);
	return *this;
}

template<class T>
void LinkList<T>::CopyFrom(const LinkList<T>& r)
{
	len = 0;
	head = tail = new LinkNode<T>;
	head->next = NULL;
	LinkNode<T> *p = r.head->next;
	while(p)
	{
		Append(p->data);
		p = p->next;
	}
}

#endif


6 顺序表和链表比较

  顺序表 链表
存值、取值操作 O(1) O(n)
插入、删除操作 O(n) O(n)
链表的插入删除操作只需修改指针,而无须移动数据元素,故操作效率较顺序表优;此外,单链表结构理论上不存在溢出问题(顺序表存在空间溢出或空间浪费问题)。因此,顺序表适宜做存储、取值等静态操作,而单链表结构适宜做插入、删除等动态操作。


7 其他形式的链表

循环单链表:最后一个结点的后继指针不为空,而是指向链表的头结点。其优点是:只要知道表中任一节点的地址,就可搜寻到所有其他节点。此外,许多操作只对链表的两端处理(如队列),在循环单链表中只需设置一个尾元结点指针,既能方便地对链表的尾部进行操作,又能方便的对链表的头部进行操作。

双向循环链表:对表中任一已知结点取后继结点或前驱结点的操作,其时间复杂度均为O(1);只要知道表中任一结点的地址,即可向后、也可向前搜寻到表中所有其他结点。双向链表中结点的结构描述如下:

template<class T>
struct Dulinknode
{
	T data;
	Dulinknode<T>* next;
	Dulinknode<T>* prior;
};
静态链表:常用于不支持指针的高级语言或用于数据对象中的元素个数是限定的情况。静态链表定义如下:
#define MAXSIZE 256
template<class T>
struct SNode
{
	T data;
	int next;
}SLinkList[MAXSIZE];

8 线性表的应用

8.1 两个有序表的合并

#include <iostream>
#include "SqList.h"
#include "List.h"
using namespace std;

void Create(List<int>*, int, char);
void MergeList(List<int>*, List<int>*, List<int>*);
void print(const int&);

void main(int argc, char* argv[])
{
	int n,m;
	cout<<"请输入有序表A的长度:"<<endl;
	cin>>n;
	cout<<"请输入有序表B的长度:"<<endl;
	cin>>m;
	SqList<int> la(n),lb(m),lc(n+m);
	Create(&la,n,'A');
	Create(&lb,m,'B');
	MergeList(&la,&lb,&lc);
	cout<<"合并后的有序表C为:"<<endl;
	lc.Traverse(print);
	system("pause");
}    

void Create(List<int>* lx, int k, char c)
{
	int e;
	if(k > 0)
	{
		cout<<"请按非递减次序输入"<<k<<"个"<<c<<"表中的数据元素:"<<endl;
		for (int i = 0; i < k; i++)
		{
			cin>>e;
			lx->Append(e);
		}
	}
}

void MergeList(List<int>* la, List<int>*lb, List<int>*lc)
{
	int i = 1, j = 1;
	int lena = la->Length();
	int lenb = lb->Length();
	int ea,eb;
	while (i <= lena && j <= lenb)
	{
		la->GetElem(ea,i);
		lb->GetElem(eb,j);
		if (ea <= eb)
		{
			lc->Append(ea);
			i++;
		}
		else
		{
			lc->Append(eb);
			j++;
		}
	}
	while (i <= lena)
	{
		la->GetElem(ea,i);
		lc->Append(ea);
		i++;
	}
	while (j <= lenb)
	{
		lb->GetElem(eb,j);
		lc->Append(eb);
		j++;
	}
}

void print(const int& c)
{
	cout<<c<<" ";
}

8.2 集合运算

#include <iostream>
#include "SqList.h"
#include "LinkList.h"
#include "List.h"
using namespace std;

void Difference(LinkList<char>&, LinkList<char>&);
void Create(LinkList<char>&, const int&);
void print(const char&);
void main(int argc, char* argv[])
{
	int n,m;
	cout<<"请输入集合A中元素的个数:"<<endl;
	cin>>n;
	cout<<"请输入集合B中元素的个数:"<<endl;
	cin>>m;

	LinkList<char> la,lb;
	cout<<"请输入"<<n<<"个元素至集合A:"<<endl;
	Create(la,n);
	cout<<"请输入"<<m<<"个元素至集合A:"<<endl;
	Create(lb,m);

	Difference(la,lb);
	cout<<"运算后的集合A是:"<<endl;
	la.Traverse(print);
	system("pause");
}    

void Difference(LinkList<char>& la, LinkList<char>& lb)
{
	int lenb = lb.Length();
	for (int i = 1; i <= lenb; i++)
	{
		char eb;
		lb.GetElem(eb,i);
		int k = la.LocateElem(eb);
		if (k)
		{
			la.Delete(eb,i);
		}
		else
		{			
			la.Append(eb);
		}
	}
}

void Create(LinkList<char>& la, const int& k)
{
	char e;
	for (int i = 0; i < k; i++)
	{
		cin>>e;
		la.Append(e);
	}
}

void print(const char& c)
{
	cout<<c<<" ";
}

8.3 一元多项式相加

Polynomial.h

#pragma once
#include <iostream>
#include "LinkList.h"
using namespace std;

//定义单项式类
class Monomial
{
public:
	int coef;
	int exp;
	friend bool operator!=(const Monomial&, const Monomial&);
};

bool operator!=(const Monomial& m1, const Monomial& m2)
{
	return m1.coef != m2.coef || m1.exp != m2.exp;
}

//定义多项式类
class Polynomial : public LinkList<Monomial>
{
public:
	Polynomial();
	Polynomial(const Polynomial&);
	void AppendMonomial(const Monomial&);
	friend Polynomial operator+(const Polynomial&, const Polynomial&);
	friend Polynomial operator-(const Polynomial&, const Polynomial&);
	friend Polynomial operator*(const Polynomial&, const Polynomial&);
};

Polynomial::Polynomial()
{
}

Polynomial::Polynomial(const Polynomial& r) : LinkList<Monomial>(r)
{
}

void Polynomial::AppendMonomial(const Monomial& m)
{
	Append(m);
}

Polynomial operator+(const Polynomial &pa, const Polynomial &pb)
{
	Polynomial pc;
	Monomial ma,mb,mc;
	int i = 1, j = 1;
	int lena = pa.Length();
	int lenb = pb.Length();
	while (i <= lena && j <= lenb)
	{
		pa.GetElem(ma,i);
		pb.GetElem(mb,j);
		if (ma.exp < mb.exp)
		{
			pc.AppendMonomial(ma);
			i++;
		}
		else if (ma.exp > mb.exp)
		{
			pc.AppendMonomial(mb);
			j++;
		}
		else
		{
			mc.coef = ma.coef + mb.coef;
			if (mc.coef!=0)
			{
				mc.exp = ma.exp;
				pc.AppendMonomial(mc);
			}
			i++;
			j++;
		}
	}
	while(i <= lena)
	{
		pa.GetElem(ma,i);
		pc.AppendMonomial(ma);
		i++;
	}
	while (j <= lenb)
	{
		pb.GetElem(mb,j);
		pc.AppendMonomial(mb);
		j++;
	}
	return pc;
}
main.cpp
#include <iostream>
#include "LinkList.h"
#include "List.h"
#include "Polynomial.h"
using namespace std;

void Create(Polynomial&);
void print(const Monomial&);
void main(int argc, char* argv[])
{
	Polynomial pa,pb;
	cout<<"请输入一元多项式A"<<endl;
	Create(pa);
	cout<<"一元多项式为:"<<endl;
	pa.Traverse(print);
	cout<<endl<<endl;
	cout<<"请输入一元多项式B"<<endl;
	Create(pb);
	cout<<"一元多项式为:"<<endl;
	pb.Traverse(print);
	cout<<endl<<endl;
	Polynomial pc;
	pc = pa + pb;
	cout<<"两个多项式相加的结果为:"<<endl;
	pc.Traverse(print);
	cout<<endl<<endl;
	system("pause");
}    

void Create(Polynomial& p)
{
	Monomial m;
	int n;
	cout<<"请输入多项式的项数:";
	cin>>n;
	cout<<"逐项输入"<<n<<"项的一元多项式,每一项格式为:\"系数 指数\":"<<endl;
	for (int i = 0; i < n; i++)
	{
		cin>>m.coef>>m.exp;
		p.AppendMonomial(m);
	}
}

void print(const Monomial& m)
{
	if (m.coef > 0)
	{
		cout<<"+"<<m.coef<<"x^"<<m.exp;
	}
	else
	{
		cout<<m.coef<<"x^"<<m.exp;
	}
}

相关实践学习
部署高可用架构
本场景主要介绍如何使用云服务器ECS、负载均衡SLB、云数据库RDS和数据传输服务产品来部署多可用区高可用架构。
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
目录
相关文章
|
19天前
|
存储
【数据结构】什么是线性表?
【数据结构】什么是线性表?
11 2
|
6月前
|
存储 人工智能 算法
数据结构(二)—— 线性表(详细知识总结)
【考纲内容】 (一)线性表的定义和基本操作 (二)线性表的实现
|
9月前
|
存储 人工智能 Java
数据结构——线性表
数据结构——线性表
69 0
|
9月前
|
存储 前端开发
数据结构-线性表(二)
数据结构-线性表(二)
|
9月前
|
存储 机器学习/深度学习 C语言
数据结构-线性表(一)
数据结构-线性表(一)
|
10月前
|
算法 Python
数据结构|线性表的一二三事
数据结构|线性表的一二三事
48 0
|
存储 人工智能 Java
数据结构-线性表
数据结构-线性表
103 0
数据结构-线性表
#数据结构# C2线性表-1
#数据结构# C2线性表-1
124 1
|
存储 人工智能 索引
数据结构之线性表
1.什么是线性表 线性表是n个相同数据类型元素的有限序列,通常记作(a0,a1,…an-1) (1)相同数据类型元素:都是具有相同属性的元素 比如都是数字,都是字符,也可以都是具有复杂结构的数据元素(如学生、商品等) (2)有限: 线性表中数据元素的个数n定义为线性表的长度,n是一个有限值 ①当n=0时线性表为空表 ②在非空的线性表每个数据元素在线性表中都有唯一确定的序号 ③在一个具有n &gt; 0个数据元素的线性表中,数据元素序号的范围是[0,n-1]
数据结构之线性表