由n
个数据元素(节点)组成的有序序列, 数据元素之间具有线性关系.
基本操作
- 初始化
- 取值
- 插入
- 查找
- 删除
int Length() const;
bool Empty() const;
void Clear();
void Traverse(void (*visit)(const ElemType &)); //依次对线性表的每个元素调用函数(*visit)
bool GetElem(int pos, ElemType &e) const;
bool SetElem(int pos, const ElemType &e);
bool Delete(int pos, ElenType &e);
bool Insert(int pos, const ElemType &e);
顺序表
- 在内存中地址连续
顺序表的实现:
//
// Created by Mars Luke on 2023/9/28.
//
#include <iostream>
using namespace std;
#define DEFAULT_SIZE 10
template<typename ElemType>
class SqList{
private:
int count; //线性表元素个数
int maxsize; //线性表的元素个数最大值
ElemType * elems; //元素存储空间
public:
SqList(int size = DEFAULT_SIZE); //构造函数模版
virtual ~SqList(); //祈构函数模版
int Length() const; //求线性表长度
bool Empty() const; //判断线性表是否为空
void Clear(); //清楚线性表
void Traverse(void (*visit)(const ElemType &)) const; //遍历线性表
bool GetElem(int pos, ElemType &e); // 获取线性表指定位置元素
bool SetElem(int pos, ElemType &e); // 设置指定位置线性表元素
bool Delete(int pos, ElemType &e); // 删除指定位置线性表元素
bool Insert(int pos, ElemType &e); // 指定位置插入元素
void print(void ) const;
};
template<typename ElemType>
SqList<ElemType>::SqList(int size) {
maxsize = size;
elems = new ElemType[maxsize];
count = 0;
}
template<typename ElemType>
SqList<ElemType>::~SqList() {
delete []elems;
}
template<typename ElemType>
int SqList<ElemType>::Length() const {
return count;
}
template<typename ElemType>
bool SqList<ElemType>::Empty() const {
return count==0;
}
template<typename ElemType>
void SqList<ElemType>::Clear() {
count = 0;
}
template<typename ElemType>
void SqList<ElemType>::Traverse(void (*visit)(const ElemType &)) const {
for (int i=0;i<Length();i++){
(*visit)(elems[i]);
}
}
template<typename ElemType>
bool SqList<ElemType>::GetElem(int pos, ElemType &e) {
if (pos <= 0 || pos > count) return false;
else{
e = elems[pos-1];
return true;
}
}
template<typename ElemType>
bool SqList<ElemType>::SetElem(int pos, ElemType &e) {
if (pos < 1 || pos > Length()){
return false;
} else {
elems[pos - 1] = e;
return true;
}
}
template<typename ElemType>
bool SqList<ElemType>::Delete(int pos, ElemType &e) {
if (pos < 1 || pos > Length()){
return false;
} else {
e = elems[pos-1];
for (int i=pos;i<Length();i++){
elems[i-1] = elems[i];
}
count--;
return true;
}
}
template<typename ElemType>
bool SqList<ElemType>::Insert(int pos, ElemType &e) {
if (pos < 1 || pos > Length()+1){
return false;
} else {
for (int i=Length();i>=pos;i--){
elems[i] = elems[i-1];
}
elems[pos-1] = e;
count++;
return true;
}
}
template<typename ElemType>
void SqList<ElemType>::print() const {
for (int i=0;i<count;i++){
cout<<elems[i]<<" ";
}
cout<<endl;
}
int main(){
int size = 5;
SqList<int> list(10);
cout<<list.Empty()<<endl;
for(int i=0;i<=size;i++){
list.Insert(1,i);
list.print();
}
for(int i=0;i<=size;i++){
int temp;
list.GetElem(i+1,temp);
cout<<temp<<" ";
}
int temp;
list.Delete(4,temp);
cout<<endl;
list.print();
list.Clear();
cout<<list.Empty();
return 0;
}
算法复杂度分析
- 删除插入移动数据花费时间长
- 插入平均移动次数为
n/2
, 删除平均移动次数(n-1)/2
- 插入平均移动次数为
- 平均时间复杂度为
O(n)
顺序表特点
- 线性表的逻辑结构与存储结构一致。
- 访问线性表时,可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为,访问每个元素所花时间相等。
称为随机存取法
优点:
- 存储密度大(结点本身所占存储量/结点结构所占存储量)
- 可以随机存取表中任一元素
缺点:
- 在插入、删除某一元素时,需要移动大量元素
- 属于静态存储形式,数据元素的个数不能自由扩充
链表
- 位置任意
- 逻辑上相邻的数据元素在物理上不一定相邻
线性表的链式存储表示称为非顺序映像或链式映像
特点
- 用任意存储空间单元来存放线性表的数据元素;
- 在存放元素本身的信息外,还存放该数据元素直接后继 (前驱)的存储地址。
节点
由数据和指针构成
template<class elemetype>
struct node{
int data;
node<elemtype>* next;
}
单向链表
- 头节点为空,尾节点为空
节点只有一个指针域的链表
单链表方法
- 创建
- 查找
- 修改
- 删除
- 插入
- 遍历
易混点
链表节点与链表节点指针
node<typename elemtype>* nodeptr; // 节点指针,可作为node->next,同时也是一个节点
node->next; //指针
node->next = nodeptr; // 对当前节点进行操作
nodeptr = node->next; //将当前节点的后继赋值给nodeptr
双向链表
节点有两个指针域的链表
循环链表
首尾相接的链表
标签:const,线性表,int,ElemType,pos,SqList From: https://www.cnblogs.com/0x000001/p/17774990.html