部分习题参考答案数据结构 李春葆.ppt

2.3 设计一个算法，将一个带头结点的数据域依次为a1，a2，…，an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为an，…，最后一个结点的数据域为a1。;2.4 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。;bool LocateNode(DLinkList *h,ElemType x) { DLinkList *p=h-next,*q; while (p!=NULL p-data!=x) p=p-next; //找data域值为x的节点*p if (p==NULL) //未找到的情况 return false; else //找到的情况 { p-freq++; //频度增1 q=p-prior; //*q为p前驱节点 while (q!=h q-freqp-freq) { p-prior=q-prior;p-prior-next=p;//交换*p和*q的位置 q-next=p-next; if (q-next!=NULL) //*p不为最后一个节点时 q-next-prior=q; p-next=q;q-prior=p; q=p-prior; //q重指向*p的前趋节点 } return true; } };2.5 设ha=(a1,a2,…,an)和hb=(b1,b2, …,bm) 是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表hc的算法。;2.6 设非空线性表ha和hb都用带头节点的循环双链表表示。设计一个算法Insert(ha,hb,i)。其功能是：i=0时，将线性表hb插入到线性表ha的最前面；当i0时，将线性表hb插入到线性表ha中第i个节点的后面；当i大于等于线性表ha的长度时，将线性表hb插入到线性表ha的最后面。;if (i==0) //将hb的所有数据结点插入到ha的头结点和第1个数据结点之间 { p=hb-prior; //p指向hb的最后一个结点/ p-next=ha-next; //将*p链到ha的第1个数据结点前面 ha-next-prior=p; ha-next=hb-next; hb-next-prior=ha; //将ha头结点与hb的第1个数据结点链起来 } else if (ilena) //将hb插入到ha中间 { p=ha-next; while (ji) //在ha中查找第i个结点*p { p=p-next; j++; } q=p-next; //q指向*p结点的后继结点/ p-next=hb-next; //hb-prior指向hb的最后一个结点 hb-next-prior=p; hb-prior-next=q; q-prior=hb-prior; }; else //将hb链到ha之后 { ha-prior-next=hb-next; //ha-prior指向ha的最后一个结点 hb-next-prior=ha-prior; hb-prior-next=ha; ha-prior=hb-prior; } free(hb); //释放hb头结点 } ;练习题3 　习题3.1、3.2、3.3、3.4和3.6。;3.2 假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。 （1）下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO （2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）。;（2）本题使用一个链栈来判断操作序列是否合法，其中A为存放操作序列的字符数组，n为该数组的元素个数（这里的ElemType类型设定为char）。对应的算