补充重点:
1.每个存储结点都包含两部分:数据域和指针域(链域)
2.在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。
3.在链表中设置头结点有什么好处?
头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放
表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首
元结点进行统一处理,编程更方便。
4.如何表示空表?
(1)无头结点时,当头指针的值为空时表示空表;
(2)有头结点时,当头结点的指针域为空时表示空表。
5.链表的数据元素有两个域,不再是简单数据类型,编程时该如何表示?
因每个结点至少有两个分量,且数据类型通常不一致,所以要采用结构数据类型。
6.sizeof(x)—— 计算变量 x 的长度(字节数);
malloc(m) — 开辟 m 字节长度的地址空间,并返回这段空间的首地址;
free(p) —— 释放指针 p 所指变量的存储空间,即彻底删除一个变量。
7.链表的运算效率分析:
(1)查找
因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为 O(n)。
(2) 插入和删除
因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为 O(1)。
但是,如果要在单链表中进行前插或删除操作,因为要从头查找前驱结点,所耗时间复杂
度将是 O(n)。
例:在 n 个结点的单链表中要删除已知结点*P,需找到它的前驱结点的地址,其时间复杂
度为 O(n)
8. 顺序存储和链式存储的区别和优缺点?
顺序存储时,逻辑上相邻的数据元素,其物理存放地址也相邻。顺序存储的优点是存储
密度大,存储空间利用率高;缺点是插入或删除元素时不方便。
链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,
另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便,使用
灵活。缺点是存储密度小,存储空间利用率低。
◆ 顺序表适宜于做查找这样的静态操作;
◆ 链表宜于做插入、删除这样的动态操作。
◆ 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;
◆ 若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。
9. 判断:“数组的处理比其它复杂的结构要简单”,对吗?
答:对的。因为——
① 数组中各元素具有统一的类型;
② 数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不
再改变。
③数组的基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的
操作。
10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别
表示该元素的 行下标 、列下标 和 元素值 。