2022数据结构知识点汇总.docxVIP

Jichenxu’sDataStructureNotes`第一章绪论

1.数据结构定义：存在一种或者多种特定的关系数据元素的集合。2.数据逻辑结构的分类：线性结构：线性表，栈，队，串，数组等；非线性结构：树，图3.两类物理存储方式及特点

顺序存储结构：(特点)借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系链式存储结构：(特点)借助指示元素存储地址的指针表示数据元素之间的逻辑关系4.时间复杂度的计算

时间复杂度按数量级递增罗列挨次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

P.S算法中的语句执行次数称为语句频度或者时间频度。记为T(n),与时间复杂度要区分。

第二章线性表

1．线性表的定义：线性表是由n≥0个数据元素组成的有限序列。2.挪移元素个数的计算3.顺序表插入和删除算法时间复杂度计算

插入：平均挪移结点次数为n/2；平均时间复杂度均为O(n)。

删除：平均挪移结点次数为(n-1)/2；平均时间复杂度均为O(n)

4.非空循环单链表的特点

表中最后一个结点的指针域指向头结点，整个链表形成一个环。

5.单链表的插入与删除操作

·头插法：s-next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。·尾插法：head=rear=null；if(head=null)head=s；elser-next=s；r=s；平均时间复杂度均为O(n)·插入运算：p=GetNode(L，i-1)；s-next=p-next；p-next=s；平均时间复杂度均为O(n)·删除运算：p=GetNode(L，i-1)；r=p-next；p-next=r-next；free(r)；平均时间复杂度均为O(n)

6.双向链表的插入操作

后插：s-priou=p;s-next=p-next;p-next-priou=s;p-next=s;

前插：q-rlink=p；q-llink=p-llink；p-llink-rlink=q;p-llink=q;

7.单链表中查找某元素的平均比较次数

从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较n个结点

第三章栈和队列

1.栈和队列的逻辑特性

栈：限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈的操作特性：后进先出(LIFO)。

队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入(也称入队、进队)的一端称为队尾，允许删除(也称出队)的一端称为队头。

队列的操作特性：先进先出(FIFO,LILO)

2.顺序栈的出栈、入栈

typedefintSElemType;if(s-top==MAXSIZE-1)

typedefstruct{returnERROR;

SElemTypedata[MAXSIZE];s-top++;

inttop;s-data[s-top]=e;

}SqStack;returnOK;}

//初始化//出栈

StatusInitStack(SqStack*s){StatusPop(SqStack*s,SElemType*e){

s-top=-1;if(s-top==-1){

returnOK;}returnERROR