【数据结构】-(一)

前端之家收集整理的这篇文章主要介绍了【数据结构】-(一)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

第一章 哈哈哈,当然是概论了

1、数据结构是计算机组织和存储数据的方式。

2、数据-数据元素-数据项(最小的标识单位)。

3、四种逻辑结构:集合、线性结构、树形结构、图结构。

4、数据存储结构:顺序存储方式、链式存储方式、索引存储方式、散列存储方式。

5、涉及到的运算:建立、查找、读取、插入、删除等。

6、具有线性结构的有:线性表、栈、队列。

7、算法分析:正确性、易读性、健壮性、时空性。

8、时间复杂度、空间复杂度(a 程序代码所占用的空间 b 输入数据所占用的空间 c 辅助变量所占用空间)。

9、算法复杂度排序优先级:O(1)< O(log2^n)< O(n)< O(nlog2^n)< O(n^2)< O(n^3)< O(n^k)< O(2^n)。


第二章 线线线性表

1、线性表是由n(n>=0)个数据元素组成的又穷序列,数据元素又称为结点。

2、一般采用数组来表示顺序表。

3、插入和删除元素的时候,分别依次向后或者向前移动数个元素,然后表长整体加一或者减一。

4、一个空单链表仅有一个头结点,它的指针域为NULL。

5、单链表插入结点的指针变化:p-> next = q-> next; q->next=q;


6、单链表上删除结点时指针变化:p = q->next; q->next = p->next;


7、建立表:第一种方法是每次插入时,都要经历查找最后一个插入点,比较费时间,在元素有n个的时候,计算量平均为:1/2n(n+1),时间复杂度为:O(n^2)。第二种方式为每次插入点后,声明一个指针指向尾结点。最后得到的顺序和插入顺序相同。第三种方式为每次都插入到头结点之后,最终得到的顺序和插入顺序相反。但是后两种的算法比第一种快,时间复杂度为O(n)。

8、循环链表:带头结点的循环链表,要找的尾结点可以从头指针head出发扫描所有的结点;没有头指针的,只有rear尾指针,这样的首结点表示为:rear->next->next,首位结点都能随便访问。

9、双向循环链表的对称性为:p=p->prior->next=p-next->prior

10、双循环链表中删除一个p结点:p->prior->next = p->next; p->next->prior = p->prior;


11、双循环链表中插入一个p结点:t->prior = p; t->next = p->next; p->next->prior = t; p->next = t;


12、线性表的顺序实现和链接实现时间空间上的复杂度的比较:


单链表 顺序表
按位置查找运算 需要对元素进行扫描,时间复杂度为O(n) 随机存取,时间复杂度为O(1)
定位运算 基本操作是比较时间复杂度为O(n) 基本操作是比较时间复杂度为O(n)

插入、删除运算
平均时间复杂度为O(n) 平均时间复杂度为O(n)
13、单链表的每个节点包括数据域与指针域,指针域需要占用额外空间。

14、顺序表需要预分配存储空间,单链表无需预先分配空间。

15、在表长为n的顺序表上做插入运算,平均要移动的结点数为n/2。

第三章队列数组 起来

1、栈和队列可以看做是特殊的线性表。特殊性表现在基本运算是线性运算的子集,是受限的线性表。

2、函数的嵌套调用和程序递归都是通过栈来实现的;操作系统中的进程调用、网络管理中的打印服务用队列来实现。

3、栈进出方式为,先进后出。允许进行插入和删除的一端称为栈顶,另一端称为栈底。不含有任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为栈顶元素。

4、出栈的时候要判断栈空。

5、栈的链接实现称为链栈。

6、链栈的每个结点空间都是动态分配产生的,链栈不用预先考虑容量的大小。

7、进栈操作算法中采用前插操作,新增结点始终插入到头结点之后。

8、出栈操作始终是栈顶结点出栈,即删除头结点之后的结点。


9、队列是有限个同类型数据元素的线性序列,是一种先进先出的线性表。。

10、排队的规则是不允许“插队”,新加入的成员只能排在队列尾,而且队列中全体成员只能按入队列的顺序离开队列(即先进先出)。

11、顺序存储实现的队列成为顺序队列,由一个一维数组及两个分别指示队列首和队列尾的变量组成,这个两个变量成为队列首指针和队列尾指针。

12、出队列判断队列是否为空。


13、对二维数组a[m][n],如果每个元素占k个存储单元,以行为主序为例,a[i][j]位置=起始地址+(n*i+j)*k(每个元素占k个存储单元)。

14、对称矩阵:矩阵元素Aij在数组M中的位置为k,k和(i,j)存在如下对应关系。当i>=j,k = 1/2(i+1)*i + j;当i<j,k = 1/2(j+1)*j +i;

15、三角矩阵:

上三角矩阵:前i行的元素个数总共有:i/2(2n-i+1);其中Aij与M[k]的位置关系为:当i<=j时:1/2[i(2n-i+1)]+j-i;当i>j时:1/2[n(n+1)];

下三角矩阵和对称矩阵的Aij和M[k]位置关系一致。

16、稀疏矩阵:将稀疏矩阵写成三元组表示法。


困了啊


原文链接:https://www.f2er.com/datastructure/382375.html

猜你在找的数据结构相关文章