南京工业大学数据结构作业答案作业2.docVIP

第二次作业 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 2 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 3. 已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a．在P结点后插入S结点的语句序列是-----------。 b．在P结点前插入S结点的语句序列是-----------。 c．删除P结点的直接后继结点的语句序列是----------。 d．删除P结点的直接前驱结点的语句序列是----------。 e．删除P结点的语句序列是------------。 (1)P-next=P-next-next; (10) P-prior-next=P; (2)P-prior=P-prior-prior; (11) P-next-prior =P; (3) P-next=S; (12)P-next-prior=S; (4) P-prior=S; (13) P-prior-next=S; (5)S-next=P; (14) P-next-prior=P-prior (6)S-prior=P; (15)Q=P-next; (7) S-next= P-next; (16)Q= P-prior; (8) S-prior= P-prior; (17)free(P); (9) P-prior-next=p-next; (18)free(Q); 4. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。 5.. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。 6. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。 1. 【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2 .【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点 head ? data link 头指针 首元结点 简而言之， 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！） 首元素结点是指链表中存储线性表中第一个数据元素a1的结点。 3. 已知P结点是双向链表的中间结点，试从下列提供的