大师兄的数据结构学习笔记(二）:线性结构
一、 线性表
1. 什么是线性表
- 表中元素个数成为线性表的长度。
- 长度为0时，成为空表。
- 表的起始位置称表头，结束位置称表尾。
2. 线性表的抽象数据类型描述
- 类型名称：线性表(list)
- 数据对象集: 线性表是
)
个元素构成的有序序列()
- 操作集:线性表
,整数i表示位置，元素 
- 主要操作有:
| 操作 |
含义 |
| SeqList() |
无参数构造方法 |
| SeqList(DataType a[], int n) |
有参数构造方法 |
| ~SeqList() {} |
析构函数 |
| int Length() |
获取长度 |
| DataType Find(int i) |
查找值 |
| int Locate(DataType x) |
查找位置 |
| void Insert(int DataType x) |
插入元素 |
| DataType Delete(int i) |
删除元素 |
| void PrintList() |
遍历线性表 |
3. 线性表存储方式
3.1 顺序存储
-
利用数组的连续存储空间，顺序存放线性表的各元素。
- 优点：
| 序号 |
优点 |
| 1 |
随机访问特性，查找O(1)时间，存储密度高。 |
| 2 |
逻辑上相邻的元素，物理上也相邻。 |
| 3 |
无须为表中元素之间的逻辑关系而增加额外的存储空间。 |
| 序号 |
缺点 |
| 1 |
插入和删除需移动大量元素。 |
| 2 |
当线性表长度变化较大时，难以确定存储空间的容量。 |
| 3 |
造成存储空间的“碎片”。 |
#ifndef SEQLIST_H
#define SEQLIST_H
const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
SeqList() { length = 0; } //无参数构造方法
SeqList(DataType a[], int n); //有参数构造方法
~SeqList() {}; //析构函数
int Length() { return length; } //获取长度
DataType Find(int i); //查找值
int Locate(DataType x); //查找位置
void Insert(int i, DataType x); //插入元素
DataType Delete(int i); //删除元素
void PrintList(); //遍历线性表
private:
DataType data[MaxSize];
int length;
};
#endif
#include "seqlist.h"
#include <iostream>
using namespace std;
template <class DataType>
SeqList<DataType>::SeqList(DataType a[], int n)
{
//有参数构造方法
if (n > MaxSize) throw "Parameter Over MaxSize";
for (int i = 0; i < n; i++)
data[i] = a[i];
length = n;
}
template <class DataType>
DataType SeqList<DataType>::Find(int i)
{
//按位查找
if (i<1 && i>length) throw "Location Over Size";
else return data[i - 1];
}
template <class DataType>
int SeqList<DataType>::Locate(DataType x)
{
//按值查找
for (int i = 0; i < length; i++)
if (data[i] == x) return i + 1;
return 0;
}
template <class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
//插入元素
if (length >= MaxSize) throw "Overflow";
if (i<1 || i>length + 1) throw "Location";
for (int j = length + 1; j > i; j--)
data[j] = data[j - 1];
data[i - 1] = x;
length++;
}
template <class DataType>
DataType SeqList<DataType>::Delete(int i)
{
//删除元素
int x;
if (length == 0) throw "Underflow";
if (i<1 || i>length) throw "Location";
x = data[i - 1];
for (int j = i; j < length; j++)
data[j - 1] = data[j];
length--;
return x;
}
template <class DataType>
void SeqList<DataType>::PrintList()
{
//遍历线性表
for (int i = 0; i < length; i++)
cout << data[i] << endl;
}
3.2 链式存储
- 不要求逻辑上相邻的两个元素物理上也相邻。
- 通过"链"建立起数据元素之间的逻辑关系。
- 插入删除不需要移动数据元素，只需要修改“链”。
- 优点：
| 序号 |
优点 |
| 1 |
插入、删除不需移动其他元素，只需改变指针。 |
| 2 |
链表各个节点在内存中空间不要求连续，空间利用率高。 |
#ifndef SEQCHAIN_H
#define SEQCHAIN_H
template<class DataType>
struct Node
{
//存储结构
DataType data; //数据
Node<DataType>* next; //下一个节点的地址
};
template<class DataType>
class SeqList
{
public:
SeqList(); //无参数构造方法
SeqList(DataType a[], int n); //有参数构造方法
~SeqList(); //析构函数
int Length(); //获取长度
DataType Find(int i); //查找值
int Locate(DataType x); //查找位置
void Insert(int i, DataType x); //插入元素
DataType Delete(int i); //删除元素
void PrintList(); //遍历线性表
private:
Node<DataType>* first;
};
#endif
#include "seqlist.h"
#include <iostream>
using namespace std;
template<class DataType>
SeqList<DataType>::SeqList()
{
//无参数构造方法
first = new Node<DataType>;
first->next = nullptr;
}
template<class DataType>
SeqList<DataType>::SeqList(DataType a[], int n)
{
//有参数构造方法
first = new Node<DataType>;
first->next = nullptr;
for (int i = 0; i < n; i++)
{
Node<DataType>* s = new Node<DataType>;
s->data = a[i];
s->next = first->next;
first->next = s;
}
}
template<class DataType>
SeqList<DataType>::~SeqList()
{
//析构函数
while (first != nullptr)
{
Node<DataType>* q = first;
first = first->next;
delete q;
}
}
template<class DataType>
int SeqList<DataType>::Length()
{
//获取长度
Node<DataType>* p = first->next;
int count = 0;
while(p != nullptr)
{
p = p->next;
count++;
}
return count;
}
template<class DataType>
DataType SeqList<DataType>::Find(int i)
{
//查找值
Node<DataType>* p = first->next;
int count = 1;
while (p != nullptr && count < i)
{
p = p->next;
count++;
}
if (p == nullptr) throw "Location";
else return p->data;
}
template<class DataType>
int SeqList<DataType>::Locate(DataType x)
{
//查找位置
Node<DataType>* p = first->next;
int count = 1;
while (p != nullptr)
{
if (p->data == x) return count;
count++;
}
return 0;
}
template<class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
//插入元素
Node<DataType>* p = first;
int count = 0;
while (p != nullptr && count < i - 1)
{
p = p->next;
count++;
}
if (p == nullptr) throw "Location";
else {
Node<DataType>* s = new Node<DataType>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template<class DataType>
DataType SeqList<DataType>::Delete(int i)
{
//删除元素
Node<DataType>* p = first;
int count = 0;
while (p != nullptr && count < i - 1)
{
p = p->next;
count++;
}
if (p == nullptr || p->next == nullptr) throw "Location";
else {
Node<DataType>* q = p->next;
int x = q->data;
p->next = q->next;
return x;
}
}
template<class DataType>
void SeqList<DataType>::PrintList()
{
//遍历线性表
Node<DataType>* p = first->next;
while (p != nullptr)
{
cout << p->data << endl;
p = p->next;
}
}
4. 其他线性表
4.1 广义表
enum elem_tag
{
DATA, LIST
};
class GLnode
{
private:
elem_tag Tag; // 0:元素节点 1:子表
union
{
char data; // 元素节点的值域
struct // 表节点
{
GLnode* hp;
GLnode* tp;
}ptr;
};
};
4.2 多重链表
-
链表中的节点可能同时隶属于多个链。
- 多重链表中节点的指针域会有多个, 但包含两个指针域的链表并不一定是多重链表。
- 经常用于树、图等复杂数据结构。
- 以实现双链表存储方法结构为例：
template<class DataType>
struct Node
{
DataType data;
Node<DataType>* prior, * next;
};
参考资料
本文作者：大师兄(superkmi)
网友评论