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

第二次作业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datalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。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);解答：a.（12）（7）（3）（6）3必须在12和7的后面，其余的顺序可变b.（13）（8）（4）（5）同上c.（15）（1）（11）（18）不可变d.（16）（2）（10）（18）不可变e.（9）（14）（17）4.编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。注：统计结点个数是【省统考样题】的要求，也是教材P604-6计算链表长度的要求，编程又简单，很容易作为考题。解：编写C程序如下(已上机通过)：全局变量及函数提前说明：---------------------------------#includestdio.h#includestdlib.htypedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p,*q,*r,*head;intm=sizeof(test);voidmain()/*第一步，从键盘输入整数，不断添加到链表*/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999){printf(/ninputaninteger[stopby'-9999']:);scanf(%d,&i);p-data=i;/*inputdataissaved*/p-link=(test*)malloc(m);/*m=sizeof(test));*/q=p;p=p-link;}q-link=NULL;/*原先用p-link=NULL似乎太晚！*/p=head;i=0;/*统计链表结点的个数并打印出来*/while(p-link!=NULL){printf(%d,p-data);p=p-link;i++;}printf(\nnodenumber=%d\n,i-1);/*结点的个数不包括-9999*/}5.定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head-next;//p指向待插入的结点，初始时指向第一个结点while(p!=NULL){s=head;//s指向q结点的前趋结点q=head-prior;//q指向由prior域构成的链表中待比较的结点while((q!=NULL)&&(p-dataq-data))//查找插入结点p的合适的插入位置{s=q;q=q-prior;}s-prior=p;p-prior=q;//结点p插入到结点s和结点q之间p=p-next;}}6.算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head-next;while((p!=NULL)&&(p-data=min)){q=p;p=p-next;}while((p!=NULL)&&(p-datamax))p=p-next;q-next=p;}}