数据结构知识点 - 图文

复习要点： 第一章

1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等； ◎数据：所有能输入到计算机中并被计算机程序处理的符号总称。 ◎数据元素：基本单位。 ◎数据项：最小单位。 ◎算法特征（5点）：有穷性；确定性；可行性；输入；输出。 2.逻辑结构、存储结构（物理结构）及其类型；

◎逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。 ◎数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。 ◎注：期中考题目

数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结构又分为 线性结构和非线性结构 ，存储结构一共有四种（顺序、链接、索引、散列）。

3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。 表示方法

◎语句频度：直接写次数。

◎时间复杂度：O(执行次数),如：O(n)。 ◎空间复杂度：O(所需空间) 第二章

1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；

12 13 21 24 28 30 42 77 数据元素 序号 1 2 3 4 5 6 7 8 表示 L.elem[0] [1] [2] [3] [4] [5] [6] [7] ◎顺序表插入

算法思想：如果要在序号5前插入元素e，需要将序号5～8向后移动一个位置。 ▲移动次数为4次，公式n-i+1

◎顺序表删除

算法思想：如果要删除序号5元素，需要将6～8依次向前移动一位 ▲移动次数为3次，公式n-i

◎有序表合并

LA = (3,5,8,11)

LB = (2,6,8,9,11,15,20)

则LC = (2,3,5,6,8,8,9,11,11,15,20) 算法思想（以非递减为例）：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。

▲注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。 ▲移动次数为（La.length + Lb.length）

2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。

◎单链表

▲每个节点有数据域和指针域 data next

头 a1 a2 a3 a4 a5 a6 带头节点L→

→

→

→

→

→

→

P↑

a1 a2 a3 a4 a5 a6 不带头节点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

◎双链表

▲每个节点有前驱指针、数据域、后继指针 prior data next

双循环链表 头 a1 a2 a3 a4 ●在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存储空间