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

《南京工业大学 数据结构 作业答案 作业2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二次作业1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？2.描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a．在P结点后插入S结点的语句序列是-----------。b．在P结点前插入S结点的语句序列是-----------。c．删除P结点的直接后继结点的语句序列是----------。d．删除P结点的直接前驱结点的语句序列是----------。e．删除P结点的语句序列是----

2、--------。(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->prio

3、r;(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）把所有结点按照其值从小到大的

4、顺序链接起来。6.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间

5、关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数

6、据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headàdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表

7、标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a．在P结点后插入S结点的语句序列是-----------。b．在P结点前插入S结点的语句序列是-----------。c．删除P结点的直接后继结点的语句序列是----------。d．删除P结点的直接前驱结点的语句序列是----------。e．删除P结点的语句序列是------------。(1)P->next=P->next->next;(10)

8、P->prior->next=P;(2)P->prior=P->prior->prior;(11)P->next->prior=P;(3)P->next=S;(12)P->nex