数据结构、算法、线性表总结

hanyujianke 2020-03-28

一.数据结构

数据结构、算法、线性表总结

1.概念

1.数据类型和抽象数据类型是不同的概念。

2.逻辑结构分为线性结构(一对一)、树形结构(一对多)、图形结构(多对多)。

3.时间复杂度(T(n)=O(f(n));空间复杂度(占用的内存空间)。

4.算法

1.BF算法:时间复杂度最坏为O(n*m)。

2.kmp算法:时间复杂度最坏为O(n+m)。

二.线性表

数据结构、算法、线性表总结

1.概念

1.顺序表结点的存储地址计算公式:Loc(ai)=Loc(a1)+(i-1)*C。

2.操作主要是查找用顺序表,进行插入、删除操作的适合用链表。

3.存储密度=(结点数据本身所占的存储量)/(整个结点结构所占的存储总量)。

4.栈

1.栈又称为先进后出表(LIFO表)

2.基本操作:initstack(s),构造一个空栈;stackempty(s),判断栈是否为空;stackfull(s),判断栈是否为满;push(s,x),进栈;pop (s),退栈;stacktop(s),取栈顶元素。

5.队列

1.队列又称为先进先出线性表(FIFO表)。

2.基本操作:initqueue(q),构造一个空队列;queueempty(q),判断队列是否为空;queuefull(q),判断队列是否为满;enqueue(q,x),入队;dequeue(q),出队;queuefront(q),返回队头元素。

6.串

1.链串中的一个节点可存储一至多个字符。

2.基本操作: StrCompare( S, T),对串进行比较;Concat( &T, S1, S2),连接两个串组成一个新串;SubString( &Sub, S, pos, len),求子串;StrInsert( &S, pos , T),串插入;StrDelete( &S, pos , len),串删除 。

三.疑难问题及解决方案

疑难问题:next和nextval不太理解
解决发案:在网上找了一篇博文,通过博文加强理解
链接:https://www.cnblogs.com/SYJ-521/p/7074702.html

相关推荐