营销型网站建设设计6,北京做网站比较好的公司,北京南站到北京站怎么走,快手流量推广免费网站一.线性结构
1.顺序线性表
1.1 线性结构是一种基本的数据结构#xff0c;具有单一前驱和后继的数据关系描述。 1.2 线性表的存储结构分为顺序存储和链式存储。 1.3 顺序线性表的元素间的逻辑关系无需占用额外的空间来存储。 1.4 一般地#xff0c;以LOC(a1a_1a1)表示线性…一.线性结构
1.顺序线性表
1.1 线性结构是一种基本的数据结构具有单一前驱和后继的数据关系描述。 1.2 线性表的存储结构分为顺序存储和链式存储。 1.3 顺序线性表的元素间的逻辑关系无需占用额外的空间来存储。 1.4 一般地以LOC(a1a_1a1)表示线性表中第一个元素的存储位置在顺序存储结构中第个元素aia_iai的存储位置为 LOC(ai)LOC(a1)(i−1)∗LLOC(a_i) LOC(a_1) (i-1)*L LOC(ai)LOC(a1)(i−1)∗LL表示表中每个元素所占用空间的字节数。
1.5 顺序线性表的优点是可以随机存储表中的元素缺点是插入和删除元素需要移动元素。
1.6插入删除操作需要移动元素个数的期望值 (1) 在长度为的线性表中插入元素时共有n1个插入位置在位置处插入元素需要移动个元素在位置处插入元素需要移动一个元素则可知在**位置处插入元素需要移动的元素个数为n1 - i,**假设在n1个位置插入元素的概率相等则概率为 n1\frac{}{n1} n1则插入元素的期望为 Einsert∑i1n1n1(n1−i)n2E_{insert} \displaystyle\sum_{i1}^{n1} \frac{}{n1}(n1 - i) \frac{n}{2} Einserti1∑n1n1(n1−i)2n
(2) 删除元素时有个元素可删除的元素删除第个元素需要移动的元素个数为n-i,则期望为 Edelete∑i1nn(n−i)n−12E_{delete} \displaystyle\sum_{i1}^{n} \frac{}{n}(n - i) \frac{n-1}{2} Edeletei1∑nn(n−i)2n−1
1.7 因此插入和删除的时间复杂度为(n)。
2.链式线性表
2.1 通过指针域来存储元素之间的逻辑关系若节点中只有一个指针域则称为线性链表具有插入和删除元素不需要移动元素的优点。 2.2 在单链表中在所指节点后面插入新节点
s-next p-next;
p-next s2.3 在单链表中删除所指节点的后继节点
q p-next;//记住需要删除的节点用于其释放内存
p-next p-next-next;
free(q);插入删除节点都需要从插入或删除的节点入手结合图中所示书写首尾衔接方便快速写出正确的代码。
2.4 在实际应用中为了简化对链表状态的判定和处理特别引入一个不存储数据元素的节点称之为头节点将其作为链表的第一个节点并令头指针指向该节点。
2.5 双向链表具有连个指针域分别指出当前元素的直接前驱和直接后继。循环链表在单链表的基础上令表尾节点的指针指向链表的第一个节点。注意区分两者的区别。
2.6 双向链表的删除和插入操作,front表示前驱next表示后继。
在节点之前插入节点
s-front p-front;
p-front-next s;
s-next p;
p-front s;删除节点
p-front-next p-next;
p-next-front p-front;
free(p);3. 栈和队列
3.1 在栈中进行插入和删除操作的一端称为栈顶。 3.2 栈的存储结构顺序存储和链式存储。采用顺序存储结构的栈称为顺序栈在这种存储方式下需要预新申请栈的存储空间。 3.3 栈的典型应用包括表达式求值括号匹配等其次将递归过程转换成非递归过程也需要利用栈来实现。
3.4 在对队列中允许插入元素的一端称为队尾(Rear),允许删除元素的一端称之为队头(Front)。顺序存储的队列可以通过求余运算来实现环状结构。 元素入队和元素出队列;
Q.rear (Q.rear 1) % MAXSIZE;// 采用下标加的方式表示入队和出队
Q.front (Q.front 1) % MAXSIZE;3.5 当头指针和为指针相等时表示队列为空当尾指针的下一个位置为头指针是表示队列满或者设置一个队列满的标志是区分队列的空与满。
3.6 链式队列采用给队列添加一个头节点并令头指针指向该节点。因此当头指针与位置的值相等且均指向头结点表示队列空。 3.7 队列主要用于需要排队的场合以及离散事件的计算机模拟等。
4.串的模式匹配
4.1 朴素的模式匹配算法基本思想是从主串的第一个字符与模式串的第一个字符比较若相等则逐一对字符串进行后续的比较否则从主串第二个字符与模式串的第一个字符重新比较直到匹配成功或则失败。
4.2 模式匹配的算法时间复杂度 (1) 假设主串和模式串长度分别为和下表从开始假设从主串的第个位置匹配成功且在前趟中都是模式串的第一个字符与主串匹配失败字符比较次数为而第1趟成功匹配字符的比较次数为,总的字符比较次数为 m(0in-m),若在n-m个位置上匹配成功的概率相同即 n−m1\frac{}{n-m1} n−m1 则匹配成功时字符的平均比较次数为 n−m1∑i0n−m(im)nm2\frac{}{n-m1} \displaystyle\sum_{i0}^{n-m} (im) \frac{nm}{2} n−m1i0∑n−m(im)2nm 因此在最好情况下匹配算法的时间复杂度为O(n)。
(2)假设最坏情况下每次匹配不成功都是模式串的最后一个字符不匹配则前趟中字符比较了×次第趟也比较了次则 ∑i0n−mm(i1)n−m112m(n−m2)\displaystyle\sum_{i0}^{n-m}\frac{m(i1)}{n-m1} \frac{1}{2}m(n-m2) i0∑n−mn−m1m(i1)21m(n−m2) 因此在最坏情况下匹配算法的时间复杂度为O(n×)。
5.矩阵的压缩存储
5.1 n阶对称矩阵aija_{ij}aijajia_{ji}aji,可将n2n^2n2个元素压缩存储到n(n1)2\frac{n(n1)}{2}2n(n1)个元素的存储空间。 采用行为主序存储下三角包括对角线中的元素在数组A中则A [k]与矩阵元素aija_{ij}aij之间的一一对应关系为 k{i(i−1)2ji jj(j−1)2i,i jk \begin{cases} \frac{i(i-1)}{2}j \text {i j} \\ \frac{j(j-1)}{2}i , \text{i j} \end{cases} k{2i(i−1)j2j(j−1)i,i ji j
