数据结构和算法描述

/ 数据结构 / 1 条评论 / 716浏览

概念名词

名词说明
数据信息的载体且能被计算机所处理的符号集合
数据元素数据的基本单位
数据项构成数据元素的基本单位
数据对象性质相同的数据元素集合

场景化分析,将数据定义为学生数据,数据对象就是学生信息表,数据元素就是学生信息表中的一名学生,数据项就是学生的名字信息。

数据结构

数据在计算机中的组织方式,数据结构指相互之间存在一种或多种特定关系的数据元素的集合,较优的数据结构可以带来更高的运行和储存效率,数据之间的关系分为逻辑关系和物理关系(存储结构),逻辑结构是数据结构的抽象,物理结构是数据结构的实现。

1.逻辑结构

  1. 集合结构,元素之间除了同属于一个集合外无任何其他关系;
  2. 线性结构,结构中的数据元素之间存在一对一的线性关系;
  3. 树型结构,结构中的元素之间存在一对多的层次关系;
  4. 图状结构和网状结构,结构中元素存在多对多的任意关系;

2.存储结构

  1. 顺序结构,储存在一块地址连续的存储单位,常用于数组进行实现顺序存储;
  2. 链表结构,一组任意的存储单元进行存储数据,数据之间的逻辑关系通过指针进行表示,存储节点存在一个指针指向下一个节点地址,最后一个节点的指向null;
  3. 索引结构,储存节点信息的同时,另外建立索引表,索引表中的每一项成为一个索引项;
  4. 散列结构,通过节点的关键词,根据公式计算出节点所在的内存地址;

3.概念小结

算法设计分析

1.要求

  1. 正确性;
  2. 可读性;
  3. 健壮性;
  4. 高效性;

2.算法特性

  1. 有穷性,必须总是在优先步骤之后完成;
  2. 确定性,算法中每一条指令必须有确切的含义;
  3. 可行性,算法是可执行;
  4. 输入,一个算法有0个或者多个输入;
  5. 输出,一个算法必须有一个或者多个输出;

3.空间复杂度

程序算法在执行时所占用的内存,空间复杂度过高的算法可能会超出限制内存,导致程序异常终止。算法本身需要占据一些空间,而且算法需要使用辅助空间完成任务。

4.时间复杂度

程序算法在执行时所消耗的时间,时间复杂度过高的算法可能让有生之年都看不到运行结果,通常平均时间复杂度比较难以求解,所以一般仅考虑最坏时间复杂度。

5.分析小窍门

计算机做加减法的速度远快于乘除法,所以评判复杂度一般会看乘除法而忽略加减法,假设现在拥有两个时间复杂度T1,T2,对应两个函数f1,f2,则有一下结论:

  1. T1+T2的复杂度取决于两者中的较大值;
  2. T1*T2的复杂度取决于相乘;
  3. T(n)是关于n的k阶多项式,那么复杂度取决于n的k次方,忽略低次幂和最高次幂项数;
  4. for循环的时间复杂度是循环的次数和代码体中的代码复杂度;
  5. if-else结构复杂度取决于if判断的条件和两个分支的复杂度,总体复杂度取决于三者中的最大值;

线性表

1.线性表的定义和特点

线性表是相同性质的数据元素的有限序列,除了起点和终点,每一个元素都存在一个直接前驱和直接后驱,数据元素的个数n称为表长,存储空间分配不灵活,运算的空间复杂度相对较高。

2.线性线性表

逻辑上相邻的数据元素在物理介质上也是相邻的存储单元,内存中占用一块连续的地址空间,知道一个元素所在单元和单元大小,就可以推算出所有元素所在的存储单元,Loc(ai)= Loc(a1)- (i-1)L,其中L为一个元素所占单元长度。

查找操作

假设一个有n个数据元素的数组,有幸第一次匹配上则执行匹配判断一次,不幸最后判断匹配或者未查找到则匹配n次,如果匹配的元素在第3个位置则需要判断3次,如果匹配元素在第7个位置则需要判断7次,所以得出以下公式1*1/n + 2*1/n + ... n*1/n,经过简化得到,1/n*(1+2+3+...n),最后得出(n+1)/2的时间复杂度,所以匹配查找的时间复杂度是O=n,可以通过哨兵模式减少时间复杂度。

插入操作

插入时需要考虑插入的位置(1~n+1),存在几个情况插入方法,头插法,尾插法,中间插法,同样要对非法异常的插入位置进行提醒。如果尾插法速度最快;如果中间插法则需要将插入位置空出再进行插入;如果是头插法则需要后移全部元素。

插入位置为1时需要移动n次,插入位置为n+1时需要移动0次,插入位置为n时需要移动1次,不难发现,插入位置和移动次数之和等于n+1,因为每个位置插入的概率1/n+1,所以得出以下公式并求出时间复杂度O(n),n趋于无穷大则可以忽略掉常数分母。

删除操作

传入一个i,对第i个节点删除,i(1~n)的位置必须是合法参数,如果头删法则需要将后面所有元素向左移动一个位置覆盖掉删除的位置元素;如果是尾删法则直接长度减一,如果是中心删除则需要将后面元素左移覆盖掉删除位置的元素。

![](/Users/huasenjio/Library/Application Support/typora-user-images/image-20201110203603172.png)

删除位置为1时需要移动n-1次,删除位置为2时需要移动n-2次,删除位置为n时需要移动n-n次,不难发现,移动次数等于元素个数和删除位置之差,因为每一个元素都有1/n被删除的概率,所以得出以下公式,得出时间复杂度O(n),当n趋于无穷大时,常数项可以忽略。

总结

  1. 优点,存储密度大(节点本身存储量/节点结所存储量=1),可以取得表中的任意元素;
  2. 缺点,删除元素时耗时过大,浪费存储空间,属于静态存储形式不可以自由扩充

3.链式线性表

节点在存储介质中是可以在任意位置,逻辑上相邻的数据元素物理上不相邻,节点包括数据项和地址项,数据项指数据元素信息,地址项指向下一个节点的地址(最后节点指向null)。 单链表由头指针唯一确定,所以单链表可以使用头指针进行命名。

链式线性表分类

  1. 单链表,节点组成数据域 指针域,指针域指向后一个节点的位置;
  2. 双链表,节点组成指针域1 数据域 指针域2,指针域1指向前一个节点的地址,指针域2指向后一个节点地址;
  3. 循环链表,头尾相连的链表;

链式线性表概念

头指针/头结点/首元结点

表现定义

单链表存储结构和数据表示

初始化单链表

生成一个存在指针域和数据域的头结点,将头结点的指针域赋值为null值,同样判断也是可以通过头指针判断是否单链表为空。

单链表销毁

借助一个指针p指向第一个元素,L头指针向后一个位置,L=L->next,再删除p指针所指向的节点,利用while循环一次进行,直到L指向null则循环结束。

清空单链表

依次释放所有节点,仅保留头结点和头指针,并且将头指针的指针域赋值成为null值。

单链表表长

设置指针p指向首元节点,从首元节点开始,指针p后移p=p->next,使用一个变量进行计数,直到p的值为null,最后输出表长。

p = L-> next; // p指向首元节点
count = 0;  // 计数器
while(p) {
  count++;
  p = p-> next;// 将p指向下一个节点
}
return count; // 返回表长

取值

一个带头节点的单链表 ,建立p指针首元结点开始,往下遍历且设置计数器,当计数值等于索取元素的序号时,输出p对应的data域。如果当为null且计数器未和索取需要匹配则说明不存在该序号元素,进行报错反馈。

按值查找

一个带头结点的单链表, 建立指针p指向首元节点,往下遍历的同时判断节点的data域与给定词匹配,匹配则输出,如果p为null仍然未匹配则说明未找到。

插入

一个带头结点的单链表,建立p指向插入位置的前一个节点,建立一个s指针指向新节点,将新节点的指针域指向原先该位置的节点,s->next = p->next,p所指节点的指针域指向新元素,p->next = s,完成按给定位置插入新元素。