数据结构复习(1)

记录数据结构复习中的不清楚的点，自用，参考的原文链接https://blog.csdn.net/m0_37568814/article/details/81288756）

1. 数据结构三要素

2. 线性表

线性表有两种存储结构：顺序存储结构和链式存储结构

（１）定义

顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。通常用数组来描述数据结构中的顺序存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。

（２）运算

数据结构的基本运算：修改、插入、删除、查找、排序。从这５类入手，分别对顺序存储结构和链式存储结构进行关键代码的总结。

• 线性表的顺序表示和实现（顺序存储结构）

ａ．修改：通过数组的下标便可访问某个特定元素并修改。
时间复杂度O(1)

ｂ．插入:在线性表的第i个位置前插入一个元素
实现步骤：
①将第n至第i 位的元素逐一向后移动一个位置；
②将要插入的元素写到第i个位置；
③表长加1。

注意：事先应判断: 插入位置i 是否合法?表是否已满?
应当符合条件： 1≤i≤n+1  或  i=[1, n+1]

核心语句：

for (j=n; j>=i; j--)
a[j+1]=a[ j ]; 
a[ i ]=x;   
n++;

插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

ｃ．删除：删除线性表的第i个位置上的元素
实现步骤：
①将第i+1 至第n 位的元素向前移动一个位置；
②表长减1。

注意：事先需要判断，删除位置i 是否合法?
应当符合条件：1≤i≤n  或  i=[1, n]

核心语句：

for ( j=i+1; j<=n; j++ )
a[j-1]=a[j]; 
n--;

顺序表删除一元素的时间效率为:T(n)=(n-1)/2 ≈O(n)
顺序表插入、删除算法的平均空间复杂度为O(1)

• 线性表的链式表示和实现（链式存储结构）
  一个数据元素称为一个结点 ，包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。
  由于链表的每个结点中只包含一个指针域，故线性链表又称为单链表。

ａ．单链表的修改(或读取）
思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，return p;
然后才能：p->data=new_value，把新值赋给该结点的指针

ｂ．单链表的插入和删除
插入

删除

ｃ．双向链表的插入与删除

双向链表与单链表的区别在于：单链表只有一个指向下一结点的指针，也就是只能next
双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点，顾名思义，单链表只能单向读取。
因此在插入和删除操作中，双向链表还会涉及到对指向前一结点的指针的操作。

插入




删除

d.循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。