数据结构复习（二）

线性表的定义：
是具有相同类型的n个元素的有限序列，其中n为表长，n=0时，为空表。
注意：A.元素个数有限 B.都是单个数据元素，元素类型相同 C.占有相同的存储空间 D.并且按顺序排列 E.元素具有抽象性。

九种基本操作：
//使用引用是因为在函数内部操作是作用于一个局部变量上的，只有引用才能实现正确的引用。
InitList（&L）：创建一个空的线性表；
DestoryList（&L):销毁线性表，并且释放他所占有的空间；
LocateElem（L，e）：按值查找，e为关键字；
GetElem（l，i）：按位置查找，获得第i个元素的位置；
ListIsert（&L,i，e）在线性表i位置前插入元素e；
ListDelete（&L，i，&e）：删除表中第i个元素，并且返回第 i个元素的值；
PrintList（L):输出操作，按照前后顺序输出；
Empty（L）：判断是否为空，为空返回true，否则返回false；
Length（L):返回线性表的表长。

顺序表：地址相连且顺序存放，
sizeof（计算元素存储空间大小）
数组静态分配
数据结构复习（二）
数组动态分配：

在c和c++中动态分配语句的区别：
molloc函数：申请无类型空间
具体见：https://blog.csdn.net/qq_42160112/article/details/102711456
静态分配时存储空间是固定的，会产生溢出错误，而动态分配空间是动态分配的，如果溢出，会产生新的存储空间，将原来的空间转移到新空间上，所以不用但心溢出问题。

顺序表的插入，删除和查找操作（i对应的是顺序表的下标）
插入：
时间复杂度分析：
最好：在表尾插入，一次成功，为O(1);
平均：插入概率为1/n+1，移动n-i+1次，则O（n）；
最坏：插入到第一个数前面，插入概率为1/n+1，移动n次；则O（n）；
数据结构复习（二）

删除：
时间复杂度分析：
最好：在表尾删除，一次成功，O（1）；
平均：删除每个元素的概率为1/n，移动n-i个元素，O(n)
最坏：删除第一个元素，删除概率为1/n；移动n个元素，O（n）；
数据结构复习（二）

按值查找：
时间复杂度分析：
最好：第一个就找到，O(1);
平均：找到每一个元素的概率为1/n，查找i次O(n）；
最坏：最后一个才找到，找到每一个元素的概率为1/n，查找n次，O(n);
数据结构复习（二）
单链表的定义
线性表的链式存储又称为单链表，通过指针实现
结点：data next
头节点不存放数据，head->next为null时，单链表为空
插入操作统一

单链表的基本操作：
头插法建立单链表：
s->next=p->next;
p->next=s;
时间复杂度分析：
最好：O(1),插入一个
最坏：O(n）插入n个
关键：需要初始化新建链表和插入的结点
数据结构复习（二）

尾插法插入结点：尾结点指针指为空时，代表链表末端
r->next=s;
r->s;
时间复杂度分析：
最好：O(1),插入一个
最坏：O(n）插入n个
关键：与头插法不同之处在于，头插法先更改插入结点的next指针指向下一个结点，再更改上一个结点的next指针指向新插入的结点（因为链表断开后无法再找到后续结点，先连后断），而尾插法，最后一个结点后不再有结点，可以直接更改指针指向，再修改尾指针指向新的尾结点。结点全部插入后，将最后一个结点的指针指向NULL
数据结构复习（二）

按序号查找
时间复杂度分析：
最好：O(1)
最坏：O(n）

按值查找
时间复杂度分析：
最好：O(1)
最坏：O(n）

插入结点：（知道第 i好元素位置，在该元素前后插入结点）
关键：不知道前一个结点的位置，需要通过按序号查找到前一个结点的位置，再进行插入操作：
p=GetElem（L,i-1),s->next=p->next;p->next=s;
前插法和后插法的区别：O(N)和O(1)
可以用后插法实现前插法；先插入，再交换。

删除结点：
需要先用一个元素来保存后一个结点的位置,J交换第 i号和第i+1号数据元素，再删除结点
q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);

求表长：不包括头结点
数据结构复习（二）

体现单链表实现插入元素的统一。
左边，带有头节点，可以通过while循环来判断是否为空表，右边不带头节点，在判断过程中可能会出现错误，因为他没有next指针。

**特殊链表：
双链表：**在单链表中，我们插入节点时，需要按序查找出前一个结点的位置，再插入，引入双链表，增加一个前驱结点，保存前一个节点的位置。
数据结构复习（二）
插入操作：
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;

时间复杂度：O(1)
数据结构复习（二）

删除操作：
p->next=q->next;
q->next->prior=p;
free(q);
时间复杂度： O(1)
数据结构复习（二）
循环单链表链表：
只知道尾指针不知道头指针
仅设尾指针会使执行效率更高，在哪个位置插入或者删除都是一样的
判空：
L->next=L;

循环双链表：
只知道尾指针不知道头指针
仅设尾指针会使执行效率更高，在哪个位置插入或者删除都是一样的
判空：L->next=L;L->prior=L;
数据结构复习（二）
**静态链表：**通过数组实现，不常用

顺序表vs链表：
存取方式：顺序表可以实现顺序存取和随机存取，单链表只能实现顺序存取
逻辑结构：顺序表逻辑和物理相邻，通过相邻表示逻辑关系；单链表物理不一定相邻，通过指针表示逻辑关系。
基本操作：略
内存空间存储，规模难以估计，选择单链表；存储密度大，采用顺序表。效率：进行频繁删除插入操作时，单链表；按序号访问，顺序表；基于数组实现，顺序表，基于指针，采用单链表。

三个常用操作：最值，逆置，归并

数据结构复习（二）

相关推荐