数据结构知识点总结

数据结构知识点总结绪论时间复杂度T（n）=O（f（n））通常用：常量阶O(1)线性阶O(n)平方阶O(n^2)对数阶O(logn)指数阶O(2^n)计算的复杂性：算法的计算量的大小算法的时间复杂度取决于问题的规模和待处理数据的初态。

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。

（1）有穷性（2）确定性（3）可行性（4）输入（5）输出从逻辑上可以把数据结构分为线性结构和非线性结构栈与数据的存储结构无关串是线性结构有序表属于逻辑结构连续存储设计时，存储单元的地址一定连续一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

它是计算机程序加工的“原料”。

二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。

四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。

在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。

根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合------------数据元素仅有同属一个关系的关系（2）线性结构----------结构中数据元素之间存在一个对一个的关系（3）树形结构------------结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-----------结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。

（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。

（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求------------------------------------------------------------------------------- 线性表：采用顺序存储，便于进行插入和删除的操作顺序表的优点：结构紧凑，存储空间利用率高，操作简单。

（存储密度大）缺点：它需要一块连续的存贮空间。

当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。

若某线性表最常用的操作是存取任一指定序号的元素和最后进行插入和删除运算，则利用顺序表的存储方式最节省时间；若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用仅有尾指针的单循环链表的存储方式最节省时间。

设一个链表最常用的操作是在末尾插入结点或删除尾结点，则利用带头结点的双循环链表的存储方式最节省时间。

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则利用带头结点的双循环链表的存储方式最节省时间。

链表的优点：在空间的合理利用上和插入、删除时不需要移动，是线性表的首选存储结构。

（不必事先估计存储空间、所需空间与线性长度成正比）缺点：求线性表的长度时不如顺序存储结构（不可随机访问任一元素）线性表在顺序存储时，查找第i个元素的时间同i的值无关；线性表在链式存储时，查找第i个元素的时间同i的值成正比。

对于顺序存储的线性表，访问结点的时间复杂度为O（1），插入和删除结点的时间复杂度为O（n）。

对于链式存储的线性表，访问第i个元素的时间复杂度为O（n）。

对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分为单链表和多重链表；根据指针的连接方式，链表又可分为动态链表和静态链表。

链表的头结点的作用：1.标识作用2.使操作统一3.其数据域可写入链表长度，或作监视哨。

静态链表中指针表示的是下一个元素地址静态链表能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

线性表是线性结构的基本形式线性表的逻辑结构线性表的定义线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，记为：(a1，a2，…a i-1，a i，a i+1，…a n)；其中：n为表长，n＝0 时称为空表。

表中相邻元素之间存在顺序关系：a i-1称为a i的直接前趋，a i+1称为a i的直接后继。

a1，…a n-1有且仅有一个直接后继；（非空线性表）a2，…a n有且仅有一个直接前趋。

（非空线性表）线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。

存储的特点：物理上的相邻实现了逻辑相邻的表示。

顺序存储能随机访问第i个元素：设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(a i)=Loc(a１)+(i-1)*d 1≤I≤n顺序表插入运算时间主要消耗：数据的移动。

一般情况下，在第i（1<=i<=n）个元素之前插入一个元素时，需将第n至第i （共n-i+1）个元素向后移动一个位置。

（在第i个位置上插入x ，从a i 到a n 都要向下移动一个位置，共需要移动n－i＋1个元素。

）一般情况下，删除第i（1<=i<=n）个元素时，需从第i+1至第n（共n-i）个元素向前移动一个位置i 的取值范围为：1≤i≤n+1（即有n＋1个位置可以插入）。

设在第i个位置上作插入的概率为P i：在等概率情况下：P i=1/ (n+1)这说明：在顺序表上做插入操作需移动表中一半的数据元素。

显然顺序表上插入时间复杂度为Ｏ(n)。

int SeqlistInsert(A[],n,i，x){if(i<1 || i>n) //检查插入位置的正确性{Printf(“参数非法”);return 0; //插入位置参数错，返回错误代码0 }else{for(k=n;k>=i;k--)A[k-1]<=A[k]; //结点移动A[i]<=x; //新元素插入n<=n+1; // n指向新的最后元素return n; //插入成功，返回成功代码}}线性表的删除运算是指将表中第i 个元素从线性表中去掉。

SeqlistDelete(A[],n,i){if(i<1 OR i>n) //检查空表及删除位置的合法性{Printf(“参数非法”);return 0; //不存在第i个元素，返回错误代码0}else{for(k=i+1;k<n;k++)A[k-1]<=A[k]; //数据元素向前移动n<=n -1; // n指向新的最后元素return n; //删除成功，返回成功代码 }删除算法的时间性能分析与插入运算相同，其时间主要消耗在了移动元素上。

计算数据移动的次数：某次删除数据的移动次数与具体位置有关。

求平均性能。

删除第i 个元素时，其后面的元素 a i+1～a n 都要向上移动一个位置，共移动了 n-i 个元素。

i 的取值范围为 ：1≤ i ≤ n （即有 n 个位置可以删除）。

设在第i 个位置上作删除的概率为P i ，平均移动数据元素的次数：在等概率情况下：P i =1/ n ，则平均移动数据元素的次数则为：这说明顺序表上作删除运算时大约需要移动表中一半的元素。

显然该算法的时间复杂度为Ｏ(n)。

线性表链式存储结构，不要求逻辑上相邻的两个数据元素物理上也相邻，因此不需要用地址连续的存储单元来实现。

链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素a i ，除了存放数据元素的自身的信息 a i 之外，还需要和a i 一起存放其后继a i+1 所在的存贮单元的地址，这两部分信息组成一个“结点”。

存放数据元素信息的称为数据域，存放其后继地址的称为指针域。

链表的表示：链表是由一个个结点构成的。

结点的申请：p=new LNode; 结点的释放：delete p ；在某结点后面插入新结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。

操作如下：①s->next=p->next;②p->next=s;注意：两个指针的操作顺序不能交换。

在某结点前面插入新结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p 的前面。

与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s。

设单链表头指针为L，操作如下：q=L;while (q->next!=p)q=q->next; //找*p的直接前驱s->next=q->next;q->next=s;删除结点：设p指向单链表中某结点，删除*p。

作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。

作业讲解：x<=A[i];while(A[j]>=x and i<j){j<=j-1;if(A[j]<x){A[i]<=A[j];i<=i+1;}while(A[i]<x and x<j)i<=i+1;if(A[i]>=x){A[j] <=A[i];j<=j-1;}插入a1：*p=a1; 改为：p->date=a1;指针p指向对象date=a1，该对象是一个结构体，指向结构体里a1那部分删除a1并把存储空间解放：free（p）；二、链表的构造q<=NULL;for(j=n;i>=1;i--){p<=(NODE*)malloc(sizeof(NODE));p->date<=an; 将an替换为ai 注：i此处为n-1 p->next<=NULL;把指针设为空指针，替换为qq<=p;}考虑链表的头指针当ai未插入时：算法：CreatLinkList(n) 构造链表，n为节点{q<=NULL;for(i=n;i>=1;i--){p<=(NODE*)malloc(sizeof(NODE));scanf(ai);p->date<=ai;p->next<=q;q<=p;}return(p);}注：此时p、q一样∵已被赋值给对方作业4：倒过来。