数据结构04-线性表(Linear List)


一、什么是线性表


1、线性表是最基本、最简单、也是最常用的一种数据结构。

2、线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。

3、我们说“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。

4、在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。因此我们平时到线性表就是指一般线性表。


5、顺序表优点:遍历和寻址速度很快

6、顺序表缺点:动一个元素就得动好多元素,效率不高

happysneaker.com



二、顺序表(Sequential List)


1、顺序表的实现:List.h、List.cpp、demo.cpp


List.h

#ifndef LIST_H
#define LIST_H

class List {

public:
	List(int size);
	~List();
	void ClearList(); // 清空表不等于释放表的内存
	bool ListEmpty();
	int ListLength();
	bool GetElem(int i, int *e);
	int LocateElem(int *e);
	bool PriorElem(int *currentElem, int *preElem);
	bool NextElem(int *currentElem, int *nextElem);
	void ListTraverse();
	bool ListInsert(int i, int *e);		// 在第i个位置上插入元素
	bool ListDelete(int i, int *e);


private:
	int *m_pList;
	int m_iSize;
	int m_iLength;

};


#endif



List.cpp

#include"stdafx.h"

#include<iostream>
using namespace std;

#include"List.h"

List::List(int size) {
	m_iSize = size;
	m_pList = new int[m_iSize];
	m_iLength = 0;
}

List::~List() {
	delete[]m_pList;
	m_pList = NULL;
}

void List::ClearList() {
	m_iLength = 0;
}

bool List::ListEmpty() {
	return m_iLength ==  0?true:false;
}

int List::ListLength() {
	return m_iLength;
}

bool List::GetElem(int i, int *e) {
	if (i < 0 || i >= m_iSize) {
		return false;
	}
	*e = m_pList[i];
	return true;
}

int List::LocateElem(int *e) {
	for (int i = 0; i < m_iLength; i++) {
		if (m_pList[i] == *e) {
			return i;
		}
	}
	return -1;
}

bool List::PriorElem(int *currentElem, int *preElem) {
	int temp = LocateElem(currentElem);
	if (temp == -1) {
		return false;
	}
	else {
		if (temp == 0) {
			return false;
		}
		else {
			*preElem = m_pList[temp - 1];
			return true;
		}
	}
}

bool List::NextElem(int *currentElem, int *nextElem) {
	int temp = LocateElem(currentElem);
	if (temp == -1) {
		return false;
	}
	else {
		if (temp == m_iLength-1) {
			return false;
		}
		else {
			*nextElem = m_pList[temp + 1];
			return true;
		}
	}
}


void List::ListTraverse() {
	for (int i = 0; i < m_iLength; i++) {
		cout << m_pList[i] << endl;
	}
}

bool List::ListInsert(int i, int *e) {
	
	if (i < 0 || i > m_iLength) {
		return false;
	}
	for (int k = m_iLength-1; k >=i ; k++) {
		m_pList[k+1] = m_pList[k];
	}

	m_pList[i] = *e;

	m_iLength++;

	return true;
}

bool List::ListDelete(int i, int *e) {

	if (i < 0 || i >= m_iLength) {
		return false;
	}

	*e = m_pList[i];

	for (int k = i + 1; k < m_iLength; k++) {
		m_pList[k - 1] = m_pList[k];
	}

	m_iLength--;

	return true;
}



demo.cpp

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

/*
*	线性表 -- 顺序表

	3 5 6 75 4 2 567 2

	前驱  后继

	顺序表的重要操作:

	bool InitList(List **list);			// 创建顺序表
	void DestroyList(List *list);		// 销毁顺序表
	void ClearList(List *list);			// 清空顺序表
	bool ListEmpty(List *list);			// 判断是否为空表
	int ListLength(List *list);			// 获取表长度
	bool GetElem(List *list,int i,Elem *e);		// 获取指定元素
	int LocateElem(List *list,Elem *e);			// 寻找第一个满足e的元素的位序
	bool PriorElem(List *list,Elem *currentElem,Elem *preElem); // 获取指定元素的前驱
	bool NextElem(List *list,Elem *currentElem,Elem *nextElem); // 获取指定元素的后继
	bool ListInsert(List *list,int i,Elem *e);		// 在第i个位置上插入元素
	bool ListDelete(List *list,int i,Elem *e);		// 在第i个位置上删除元素
	void ListTraverse(List *list);			// 遍历顺序表
*/


int main()
{

	//	3 5 6 75 4 2 567 2
	int temp = 0;

	int e1 = 3;
	int e2 = 5;
	int e3 = 6;
	int e4 = 75;
	int e5 = 4;
	int e6 = 2;
	int e7 = 567;
	int e8 = 2;
	List *list1 = new List(10);

	list1->ListInsert(0,&e1);
	list1->ListInsert(1,&e2);
	list1->ListInsert(2,&e3);
	list1->ListInsert(3,&e4);
	list1->ListInsert(4,&e5);
	list1->ListInsert(5,&e6);
	list1->ListInsert(6,&e7);

	list1->ListDelete(0,&temp); // 取出第一个元素

	list1->ListTraverse();

	cout << "#取出的第一个元素为:" << temp << endl;

	delete list1;

	system("pause");
    return 0;
}


happysneaker.com

运行结果


2、但是顺序表不仅能够对int类型的数据进行操作,因此对其进行改造使其可以适应所有类型数据,新加Coordinate.h、Coordinate.cpp文件:


改动①:List.h

happysneaker.com

happysneaker.com


改动②:List.cpp

#include"stdafx.h"

#include<iostream>
using namespace std;

#include"List.h"

List::List(int size) {
	m_iSize = size;
	m_pList = new Coordinate[m_iSize];
	m_iLength = 0;
}

List::~List() {
	delete[]m_pList;
	m_pList = NULL;
}

void List::ClearList() {
	m_iLength = 0;
}

bool List::ListEmpty() {
	return m_iLength ==  0?true:false;
}

int List::ListLength() {
	return m_iLength;
}

bool List::GetElem(int i, Coordinate *e) {
	if (i < 0 || i >= m_iSize) {
		return false;
	}
	*e = m_pList[i];
	return true;
}

int List::LocateElem(Coordinate *e) {
	for (int i = 0; i < m_iLength; i++) {
		if (m_pList[i] == *e) {
			return i;
		}
	}
	return -1;
}

bool List::PriorElem(Coordinate *currentElem, Coordinate *preElem) {
	int temp = LocateElem(currentElem);
	if (temp == -1) {
		return false;
	}
	else {
		if (temp == 0) {
			return false;
		}
		else {
			*preElem = m_pList[temp - 1];
			return true;
		}
	}
}

bool List::NextElem(Coordinate *currentElem, Coordinate *nextElem) {
	int temp = LocateElem(currentElem);
	if (temp == -1) {
		return false;
	}
	else {
		if (temp == m_iLength-1) {
			return false;
		}
		else {
			*nextElem = m_pList[temp + 1];
			return true;
		}
	}
}


void List::ListTraverse() {
	for (int i = 0; i < m_iLength; i++) {
		cout << m_pList[i] << endl;
	}
}

bool List::ListInsert(int i, Coordinate *e) {
	
	if (i < 0 || i > m_iLength) {
		return false;
	}
	for (int k = m_iLength-1; k >=i ; k++) {
		m_pList[k+1] = m_pList[k];
	}

	m_pList[i] = *e;

	m_iLength++;

	return true;
}

bool List::ListDelete(int i, Coordinate *e) {

	if (i < 0 || i >= m_iLength) {
		return false;
	}

	*e = m_pList[i];

	for (int k = i + 1; k < m_iLength; k++) {
		m_pList[k - 1] = m_pList[k];
	}

	m_iLength--;

	return true;
}


改动三:Coordinate.h

happysneaker.com


改动④:Coordinate.cpp

#include"stdafx.h"
#include"Coordinate.h"
#include<iostream>
using namespace std;

Coordinate::Coordinate(int x, int y) {
	m_iX = x;
	m_iY = y;
}

void Coordinate::printCoordinate() {
	cout << "(" << m_iX << "," << m_iY << ")" << endl;
}

ostream &operator<<(ostream &out, Coordinate &coor) {
	out << "(" << coor.m_iX << "," << coor.m_iY << ")" <<endl;
	return out;
}

bool Coordinate::operator==(Coordinate &coor) {
	if (this->m_iX == coor.m_iX && this->m_iY == coor.m_iY) {
		return true;
	}
	return false;
}


改动5:demo.cpp

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

/*
*	线性表 -- 顺序表

	3 5 6 75 4 2 567 2

	前驱  后继

	顺序表的重要操作:

	bool InitList(List **list);			// 创建顺序表
	void DestroyList(List *list);		// 销毁顺序表
	void ClearList(List *list);			// 清空顺序表
	bool ListEmpty(List *list);			// 判断是否为空表
	int ListLength(List *list);			// 获取表长度
	bool GetElem(List *list,int i,Elem *e);		// 获取指定元素
	int LocateElem(List *list,Elem *e);			// 寻找第一个满足e的元素的位序
	bool PriorElem(List *list,Elem *currentElem,Elem *preElem); // 获取指定元素的前驱
	bool NextElem(List *list,Elem *currentElem,Elem *nextElem); // 获取指定元素的后继
	bool ListInsert(List *list,int i,Elem *e);		// 在第i个位置上插入元素
	bool ListDelete(List *list,int i,Elem *e);		// 在第i个位置上删除元素
	void ListTraverse(List *list);			// 遍历顺序表
*/


int main()
{

	//	3 5 6 75 4 2 567 2
	int temp = 0;

	Coordinate e1(3,5);
	Coordinate e2 (5,6);
	Coordinate e3(6,75);
	//Coordinate e4 = 75;
	//Coordinate e5 = 4;
	//Coordinate e6 = 2;
	//Coordinate e7 = 567;
	//Coordinate e8 = 2;
	List *list1 = new List(10);

	list1->ListInsert(0,&e1);
	list1->ListInsert(1,&e2);
	list1->ListInsert(2,&e3);
	//list1->ListInsert(3,&e4);
	//list1->ListInsert(4,&e5);
	//list1->ListInsert(5,&e6);
	//list1->ListInsert(6,&e7);

	//list1->ListDelete(0,&temp); // 取出第一个元素

	list1->ListTraverse();

	cout << "#取出的第一个元素为:" << temp << endl;

	delete list1;

	system("pause");
    return 0;
}

happysneaker.com

result


三、链表(Linked List)


1、链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于顺序表,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间是O(1)。


2、使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表双向链表以及循环链表。如下所示:


happysneaker.com

单链表


happysneaker.com

循环链表


happysneaker.com

双向链表


happysneaker.com

静态链表



这里以单链表为例进行实现:

五个文件:List.h、List.cpp、demo.cpp、Node.h、Node.cpp


List.h

#ifndef LIST_H
#define LIST_H

#include"Node.h"
class List {

public:
	List();
	~List();
	void ClearList(); // 清空表不等于释放表的内存
	bool ListEmpty();
	int ListLength();
	bool GetElem(int i, Node *pNode);
	int LocateElem(Node *pNode);
	bool PriorElem(Node *pCurrentNode, Node *pPreNode);
	bool NextElem(Node *pCurrentNode, Node *pNextpNode);
	void ListTraverse();
	bool ListInsert(int i, Node *pNode);		// 在第i个位置上插入结点
	bool ListDelete(int i, Node *pNode);
	bool ListInsertHead(Node *pNode);  // 从头插入结点
	bool ListInsertTail(Node *pNode);  // 从尾插入结点


private:
	Node *m_pList;

	int m_iLength;

};


#endif


List.cpp

#include"stdafx.h"

#include<iostream>
using namespace std;

#include"List.h"

List::List() {
	m_pList = new Node;
	m_pList->data = 0;
	m_pList->next = NULL;
	m_iLength = 0;
}

bool List::ListEmpty() {
	if (m_iLength == 0) {
		return true;
	}
	else {
		return false;
	}
}

int List::ListLength() {
	return m_iLength;
}

void List::ClearList() {
	Node *currentNode = m_pList -> next;
	while (currentNode != NULL) {
	
		Node *temp = currentNode->next;
		delete currentNode;
		currentNode = temp;
	}
	m_pList->next = NULL;
}

List::~List() {
	ClearList();
	delete m_pList;
	m_pList = NULL;
}

bool List::ListInsertHead(Node *pNode) {
	Node *temp = m_pList->next;
	Node *newNode = new Node;
	if (newNode == NULL) {
		return false;
	}
	newNode->data = pNode->data;
	m_pList->next = newNode;
	newNode->next = temp;  //链表就连起来了
	m_iLength++;
	return true;
}

bool List::ListInsertTail(Node *pNode) {
	Node *currentNode = m_pList;
	while (currentNode->next != NULL) {
		currentNode = currentNode->next;
	}
	Node *newNode = new Node;
	if (newNode == NULL) {
		return false;
	}
	newNode->data = pNode->data;
	newNode->next = NULL;
	currentNode->next = newNode;
	m_iLength++;
	return true;
}

bool List::ListInsert(int i, Node *pNode) {
	if (i<0 || i > m_iLength) {
		return false;
	}
	Node *currentNode = m_pList;
	for (int k = 0; k < i; k++) {
		currentNode = currentNode->next;
	}
	Node *newNode = new Node;
	if (newNode == NULL) {
		return false;
	}
	newNode->data = pNode->data;
	newNode->next = currentNode->next;
	currentNode->next = newNode;
	return true;

}

bool List::ListDelete(int i, Node *pNode) {
	if (i < 0 || i >= m_iLength) {
		return false;
	}
	Node *currentNode = m_pList;
	Node *currentNodeBefore = NULL;
	for (int k = 0; k <= i;k++) {
		currentNodeBefore = currentNode;
		currentNode = currentNode->next;	
	}

	currentNodeBefore->next = currentNode->next;
	pNode->data = currentNode->data;
	delete currentNode;
	currentNode = NULL;
	m_iLength--;
	return true;
}

bool List::GetElem(int i, Node *pNode) {
	if (i < 0 || i >= m_iLength) {
		return false;
	}

	Node *currentNode = m_pList;
	Node *currentNodeBefore = NULL;
	for (int k = 0; k <= i; k++) {
		currentNodeBefore = currentNode;
		currentNode = currentNode->next;
	}
	pNode->data = currentNode->data;
	return true;
}

int List::LocateElem(Node *pNode) {
	Node *currentNode = m_pList;
	int count = 0;
	while (currentNode->next != NULL) {
		currentNode = currentNode->next;
		if(currentNode->data == pNode->data){
			return count;
		}
		count++;
	}
	return -1;
}

bool List::PriorElem(Node *pCurrentNode, Node *pPreNode) {
	Node *currentNode = m_pList;
	Node *tempNode = NULL;
	while (currentNode->next != NULL) {
		tempNode = currentNode;
		currentNode = currentNode->next;
		if (currentNode->data == pCurrentNode->data) {
			if (tempNode == m_pList) {
				return false;
			}
			pPreNode->data = tempNode->data;
			return true;
		}
	}
	return false;
}


bool List::NextElem(Node *pCurrentNode, Node *pNextpNode) {
	Node *currentNode = m_pList;

	while (currentNode->next != NULL) {
		currentNode = currentNode->next;
		if (currentNode->data == pCurrentNode->data) {
			if (currentNode->next == NULL) {
				return false;
			}
			pNextpNode->data = currentNode->next->data;
			return true;
		}
	}
	return false;
}

void List::ListTraverse() {
	Node *currentNode = m_pList;
	while (currentNode->next != NULL) {
		currentNode = currentNode->next;
		currentNode->printNode();
	}
}


demo.cpp

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

/*
*	线性表 -- 单链表

	bool InitList(List **list);			// 创建顺序表
	void DestroyList(List *list);		// 销毁顺序表
	void ClearList(List *list);			// 清空顺序表
	bool ListEmpty(List *list);			// 判断是否为空表
	int ListLength(List *list);			// 获取表长度
	bool GetElem(List *list,int i,Elem *e);		// 获取指定元素
	int LocateElem(List *list,Elem *e);			// 寻找第一个满足e的元素的位序
	bool PriorElem(List *list,Elem *currentElem,Elem *preElem); // 获取指定元素的前驱
	bool NextElem(List *list,Elem *currentElem,Elem *nextElem); // 获取指定元素的后继
	bool ListInsert(List *list,int i,Elem *e);		// 在第i个位置上插入元素
	bool ListDelete(List *list,int i,Elem *e);		// 在第i个位置上删除元素
	void ListTraverse(List *list);			// 遍历顺序表
*/


int main()
{
	Node node1;
	Node node2;
	Node node3;
	Node node4;
	node1.data = 3;
	node2.data = 7;
	node3.data = 5;
	node4.data = 9;

	Node node5;
	node5.data = 65;

	List *pList = new List();

	pList->ListInsertHead(&node1);
	pList->ListInsertHead(&node2);
	pList->ListInsertHead(&node3);
	pList->ListInsertHead(&node4);

	cout << endl;

	pList->ListInsertTail(&node1);
	pList->ListInsertTail(&node2);
	pList->ListInsertTail(&node3);
	pList->ListInsertTail(&node4);


	pList->ListInsert(0,&node5);

	pList->ListTraverse();

	delete pList;
	pList = NULL;

	system("pause");
    return 0;
}


Node.h

#ifndef NODE_H
#define NODE_H


class Node {

public:
	int data;
	Node *next;
	void printNode();
};


#endif


Node.cpp

#include"stdafx.h"
#include"Node.h"
#include<iostream>
using namespace std;


void Node::printNode() {
	cout << data << endl;
}

happysneaker.com

运行结果



※ 链表的应用:通讯录(姓名、电话)

我写的总是出错,可以参考视频:https://www.imooc.com/video/12009



Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论