文档介绍：该【数据结构期末复习知识点(兼容版) 】是由【久阅文学】上传分享，文档一共【62】页，该文档可以免费在线阅读，需要了解更多关于【数据结构期末复习知识点(兼容版) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构期末复****知识点(兼容版)
《数据结构》期末复****br/>复****要点:
第一章
:数据、数据元素(基本单位)、数据项(最小单位)、算法及其特征等;
◎数据:所有能输入到计算机中并被计算机程序处理的符号总称。
◎数据元素:基本单位。
◎数据项:最小单位。
◎算法特征(5点):有穷性;确定性;可行性;输入;输出。
、存储结构(物理结构)及其类型;
◎逻辑结构有四种基本类型:集合、线性结构、树形结构和网状结构。
◎数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。
◎注:期中考题目
数据结构分为两大类,即为逻辑结构和存储结构。其中逻辑结果又分为线性结构和非线性结构,存储结构一共有四种(顺序、链接、索引、散列)。
:语句频度(执行次数)计算、时间和空间复杂度分析。
表示方法
◎语句频度:直接写次数。
◎时间复杂度:O(执行次数),如:O(n)。
◎空间复杂度:O(所需空间)
第二章
(数组)插入、删除、有序表合并算法及其移动次数计算;
12
13
21
24
28
30
42
77
数据元素
序号12345678
[0][1][2][3][4][5][6][7]
◎顺序表插入
算法思想:如果要在序号5前插入元素e,需要将序号5~8向后移动一个位置。
▲移动次数为4次,公式n-i+1
算法思想(以非递减为例):La和Lb非递减排列,La与Lb中元素逐个比较,较小的先插入Lc中。
▲注:非递减是指递增排序,但元素有可能相等,与之相对的有非递增排序。
▲移动次数为(+)
(有无头节点、单双、循环)插入(前、后)、删除(前、本身、后)的指针挂接、建立(
不带头节点)算法。
◎单链表
▲每个节点有数据域和指针域datanext
头a1a2a3a4a5a6
带头节点L→→→→→→→
P↑
a1a2a3a4a5a6
不带头节点L→→→→→→
P↑
单循环链表
●在P(a3)节点前插入S节点
(1)Q=P;//先让Q指向a3
(2)P=L;//P指向第一个节点(带头结点指向头结点,不带头结点指向a1)
(3)while(P->next!=Q)P=P->next;//找到a3的前驱a2,P指向a2
(4)S->next=P->next;//P->next为a3,让S->next等于a3
(5)P->next=S;//a2指针域指向节点S
●在P(a3)节点后插入S节点
(1)S-next=P->next;
(2)P->next=S;
●删除P(a3)前一个节点
(1)Q=P;
(2)P=L;
(3)while(P->next->next!=Q)P=P->next;//找到a1
(4)P->next=P->next->next;//让a1指针域指向a3,从而删除a2
●删除P(a3)节点
(1)Q=P;
(2)P=L;
(3)while(P->next!=Q)P=P->next;//找到a2
(4)P->next=P->next->next;//让a2指针域指向a4,从而删除a3
●删除P(a3)后一个节点
(1)P->next=P->next->next;//让a3指针域指向a5,从而删除a4
◎双链表
▲每个节点有前驱指针、数据域、后继指针priordatanext
双循环链表
头a1a2a3a4
●在P(a2)节点前插入S节点
▲技巧:先让S->prior和S->next与链表建立关系
注:步骤(4)必须在步骤(3)后面
(1)S->next=P;//先让S->next指向a2
(2)S->prior=P->prior;//S->prior指向a1
(3)P->prior->next=S;//再把a1->next指向S
(4)P->prior=S;//a2->prior指向S
●在P(a2)节点后插入S节点
注:步骤(4)必须在步骤(3)后面
(1)S->prior=P;
(2)S->next=P->next;
(3)P->next->prior=S;//a3->prior指向S
(4)P->next=S;
●删除P(a2)前一个节点a1
(1)Q=P->prior;//Q指向要被删除的a1;
(2)P->prior=P->prior->prior;//P->priro指向头
(3)P->prior->next=P;//头->next指向P
(4)free(Q);//释放a1的存储空间
●删除P(a2)节点
(1)P->next->prior=p->prior;
(2)P->prior->next=p->next;
(3)free(P);
●删除P(a2)后一个节点a3
(1)Q=P->next;
(2)P->next=P->next->next;//a2->next指向a4
(3)P->next->prior=P;//a4->prior=P
(4)free(Q);//释放a3存储空间
◎建立(不带头节点)单链表