数据结构（2）

---

1. 线性表的顺序表示

 1. 线性表是具有相同数据类型的 $n$ 个数据元素的有限序列，其中 $n$ 为表长。

 2. 线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理地址上也相邻。

 3. 顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

 4. (1) 顺序表插入算法的平均时间复杂度为 $O(n)$。 (2) 顺序表删除算法的平均时间复杂度为 $O(n)$。 (3) 顺序表按值查找算法的平均时间复杂度为 $O(n)$。 (4) 顺序表按序号查找的时间复杂度为 $O(1)$。

#include<iostream>
using namespace std;
#define InitSize 10  //表的初始长度定义 

typedef struct{
int length;
int Maxsize;
int *data;
}SqList; 

void InitList(SqList &L)//初始化顺序表
{
L.data = new int[InitSize];
L.length = 0;
L.Maxsize = InitSize;
}

void WriteList(SqList &L)//把元素放入顺序表
{
cout<<"请输入你要创建的顺序表的长度：";
cin>>L.length;
cout<<"请输入你要放入顺序表里的元素：";
for (int i = 0; i < L.length; i++)
cin>>L.data[i];
}

bool PrintList(SqList &L)//打印顺序表
{
if (!L.data)
return false;
cout<<"顺序表里的元素有：";
for (int i = 0; i < L.length; i++)
cout<<L.data[i];
return true;
}
 
int main(){
    SqList L;
InitList(L);
WriteList(L);
PrintList(L);
return 0;
} 

2. 线性表的链式表示

 1. 线性表的链式存储又称单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。
 为建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还需要存放一个指向其后继的指针。

 2. 单链表结点结构如下图所示，其中 $data$ 为数据域，存放数据元素；$next$ 为指针域，存放其后继结点的地址。由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构。

 4. 头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点；而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

 3. 双链表结点中有两个指针 $prior$ 和 $next$，分别指向其直接前躯和直接后继。

原文地址：https://blog.csdn.net/m0_62881487/article/details/140572099

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！