数据结构——线性表

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;
	}
}

转载：http://blog.csdn.net/foreverling/article/details/43085481

时间： 2024-10-31 19:52:18

数据结构——线性表的相关文章

（C语言版）数据结构线性表从键盘输入元素实现相关功能，不报错，但执行意外终止

问题描述 (C语言版)数据结构线性表从键盘输入元素实现相关功能,不报错,但执行意外终止 #include #include #define MaxSize 50 typedef char ElemType; typedef struct{//struct结构体 ElemType data[MaxSize]; int length; }SqList; void InitList(SqList &L)//初始化线性表的方法,&是取地址符号,是定义指针符号,如int *b=&a:*a=4

C++数据结构线性表的存储

问题描述 C++数据结构线性表的存储 输入姓名和地址信息,原样输出,例如 input liming beijing output liming beijing 求C++代码 我是新手,求大神罩

大话数据结构五：线性表的链式存储结构（双向链表）

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱. 2. 单链表和双向链表比较: 单链表:总是要从头到尾找结点,只能正遍历,不能反遍历. 双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间. 3. Java实现双向链表: // 双向链表 public class DoubleLi

数据结构C语言实现之线性表

#include <stdio.h>#include <stdlib.h>typedef int elemType; /************************************************************************//* 以下是关于线性表顺序存储操作的16种算法 *//************************************************************************/struct Lis

大话数据结构之三：线性表

1.定义: 线性表表示0个或者多个数据元素的有限序列 线性表的特性有: 除第一个元素外,每一个元素均有一个直接前驱 出最后一个元素外,每一个元素均有一个直接后继 2.线性表抽象数据类型 ADT List  Data          /*线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType.其中,除第一个元素a1外,   每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素.   数据元素直接是一对一的关系.*/  Op

算法速成（八）线性表之链表

一:线性表的简单回顾 上一篇跟大家聊过"线性表"顺序存储,通过实验,大家也知 道,如果我每次向 顺序表的头部插入元素,都会引起痉挛,效率比较低下,第二点我们用顺序 存储时,容 易受到长度的限制,反之就会造成空间资源的浪费. 二:链表 对于 顺序表存在的若干问题,链表都给出了相应的解决方案. 1. 概念:其实链表的"每个节点" 都包含一个"数据域"和"指针域". "数据域"中包含当前的数据. "指针

编程c语言-数据结构中构建线性表

问题描述 数据结构中构建线性表 为什么是取地址符,求普及 解决方案 因为你需要在函数内创建和返回这个表.而status这个返回值被用来返回状态. 用引用修饰参数,将参数当作返回值,这是一种常见的技巧. 解决方案二: 返回地址的引用,方便对返回的表作其他操作. 解决方案三: 有些编译器 没有bool 类型, 就用宏定义了 status 类型 表示 bool类型,不是取地址把? 应该是c++中的引用把? 如果取地址,下面的应该L->elem, 你看的是严蔚敏的数据结构? 解决方案四: 简单来说就是你

php线性表顺序存储实现代码(增删查改)_php技巧

复制代码 代码如下: <?php /* *文件名:linearList.php * 功能:数据结构线性表的顺序存储实现 * author:黎锦焕 * @copyright:www.drw1314.com */ class linearList { private $arr; private $length; const MAXSIZE=100; /* *构造函数,判断空表还是飞空表,并且进行实例化 * @param array $arr 输入的数组 * @param int $n 输入数组的长度

顺序存储线性表-数据结构顺序表的操作（c++）

问题描述 数据结构顺序表的操作(c++) 求解答谢谢 解决方案 贴出代码而不是截图.发了帖子你难道自己不看下.这么小的字根本看不清. 解决方案二: 什么是线性表?定义:由n(n>=0)个数据类型相同的数据元素组成的有限序列.特点是:在数据元素的非空有限集合中,除第一个元素无直接前驱,最后一个元素无直接后继外,集合中其余每个元素均有唯一的直接前驱和直接后继.什么是顺序表,在这里回答一下.顺序表就是线性表的顺序存储,其特点是:物理顺序与逻辑顺序是相同的,关系线性化,结点顺序存.线性表顺序存储的表示?