大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(二）:線性結(jié)構(gòu)
一沟启、 線性表
1. 什么是線性表
- 線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列勋拟。
- 表中元素個(gè)數(shù)成為線性表的長(zhǎng)度草慧。
- 長(zhǎng)度為0時(shí)，成為空表。
- 表的起始位置稱表頭舱禽，結(jié)束位置稱表尾。
2. 線性表的抽象數(shù)據(jù)類型描述
- 類型名稱：線性表(list)
- 數(shù)據(jù)對(duì)象集: 線性表是
個(gè)元素構(gòu)成的有序序列(
)
- 操作集:線性表
,整數(shù)i表示位置恩沽，元素
- 主要操作有:
操作 含義 SeqList() 無參數(shù)構(gòu)造方法 SeqList(DataType a[], int n) 有參數(shù)構(gòu)造方法 ~SeqList() {} 析構(gòu)函數(shù) int Length() 獲取長(zhǎng)度 DataType Find(int i) 查找值 int Locate(DataType x) 查找位置 void Insert(int DataType x) 插入元素 DataType Delete(int i) 刪除元素 void PrintList() 遍歷線性表
3. 線性表存儲(chǔ)方式
3.1 順序存儲(chǔ)
-
利用數(shù)組的連續(xù)存儲(chǔ)空間誊稚，順序存放線性表的各元素。
- 優(yōu)點(diǎn)：
| 序號(hào) | 優(yōu)點(diǎn) |
|---|---|
| 1 | 隨機(jī)訪問特性，查找O(1)時(shí)間里伯，存儲(chǔ)密度高城瞎。 |
| 2 | 邏輯上相鄰的元素，物理上也相鄰疾瓮。 |
| 3 | 無須為表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間脖镀。 |
- 缺點(diǎn):
| 序號(hào) | 缺點(diǎn) |
|---|---|
| 1 | 插入和刪除需移動(dòng)大量元素。 |
| 2 | 當(dāng)線性表長(zhǎng)度變化較大時(shí)狼电，難以確定存儲(chǔ)空間的容量蜒灰。 |
| 3 | 造成存儲(chǔ)空間的“碎片”。 |
- 代碼實(shí)現(xiàn)：
#ifndef SEQLIST_H
#define SEQLIST_H
const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
SeqList() { length = 0; } //無參數(shù)構(gòu)造方法
SeqList(DataType a[], int n); //有參數(shù)構(gòu)造方法
~SeqList() {}; //析構(gòu)函數(shù)
int Length() { return length; } //獲取長(zhǎng)度
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)
{
//有參數(shù)構(gòu)造方法
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 鏈?zhǔn)酱鎯?chǔ)
- 不要求邏輯上相鄰的兩個(gè)元素物理上也相鄰肩碟。
- 通過"鏈"建立起數(shù)據(jù)元素之間的邏輯關(guān)系强窖。
- 插入刪除不需要移動(dòng)數(shù)據(jù)元素，只需要修改“鏈”削祈。
- 優(yōu)點(diǎn)：
| 序號(hào) | 優(yōu)點(diǎn) |
|---|---|
| 1 | 插入翅溺、刪除不需移動(dòng)其他元素，只需改變指針髓抑。 |
| 2 | 鏈表各個(gè)節(jié)點(diǎn)在內(nèi)存中空間不要求連續(xù)未巫，空間利用率高。 |
- 缺點(diǎn):
| 序號(hào) | 缺點(diǎn) |
|---|---|
| 1 | 查找需要遍歷操作启昧，比較麻煩叙凡。 |
- 代碼實(shí)現(xiàn):
#ifndef SEQCHAIN_H
#define SEQCHAIN_H
template<class DataType>
struct Node
{
//存儲(chǔ)結(jié)構(gòu)
DataType data; //數(shù)據(jù)
Node<DataType>* next; //下一個(gè)節(jié)點(diǎn)的地址
};
template<class DataType>
class SeqList
{
public:
SeqList(); //無參數(shù)構(gòu)造方法
SeqList(DataType a[], int n); //有參數(shù)構(gòu)造方法
~SeqList(); //析構(gòu)函數(shù)
int Length(); //獲取長(zhǎng)度
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()
{
//無參數(shù)構(gòu)造方法
first = new Node<DataType>;
first->next = nullptr;
}
template<class DataType>
SeqList<DataType>::SeqList(DataType a[], int n)
{
//有參數(shù)構(gòu)造方法
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()
{
//析構(gòu)函數(shù)
while (first != nullptr)
{
Node<DataType>* q = first;
first = first->next;
delete q;
}
}
template<class DataType>
int SeqList<DataType>::Length()
{
//獲取長(zhǎng)度
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 廣義表
- 是線性表的推廣。
-
在線性表中密末，元素是基本的原元素握爷，而在廣義表中，元素不僅可以是元素严里，也可以是另一個(gè)廣義表新啼。
- 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：
enum elem_tag
{
DATA, LIST
};
class GLnode
{
private:
elem_tag Tag; // 0:元素節(jié)點(diǎn) 1:子表
union
{
char data; // 元素節(jié)點(diǎn)的值域
struct // 表節(jié)點(diǎn)
{
GLnode* hp;
GLnode* tp;
}ptr;
};
};
4.2 多重鏈表
-
鏈表中的節(jié)點(diǎn)可能同時(shí)隸屬于多個(gè)鏈。
- 多重鏈表中節(jié)點(diǎn)的指針域會(huì)有多個(gè), 但包含兩個(gè)指針域的鏈表并不一定是多重鏈表刹碾。
- 經(jīng)常用于樹燥撞、圖等復(fù)雜數(shù)據(jù)結(jié)構(gòu)。
- 以實(shí)現(xiàn)雙鏈表存儲(chǔ)方法結(jié)構(gòu)為例：
template<class DataType>
struct Node
{
DataType data;
Node<DataType>* prior, * next;
};
參考資料
本文作者：大師兄(superkmi)
