文档介绍：算法与数据结构均移动多少个结点? 具体的移动次数取决于哪两个因素? 答: 在等概率情况下,顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均移动(n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。i 越接近 n 则所需移动的结点数越少。已知由单链表表示的线性表中,含有三类字符的数据元素(如: 字母字符、数字字符和其它字符) ,试编写算法构造三个以循环链表表示的线性表, 使每个表中只含同一类的字符, 且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。解: 要解决这样的问题, 只要新建三个头结点, 然后在原来的单链表中依次查询, 找到一类字符结点时, 就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下: // 设已建立三个带头结点的空循环链表 A,B,C 且A、B、C 分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) { ListNode *p=L->next, *q; while (p){ if( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') { q=p->next; p=p->next;// 指向下一结点 q->next=A->next;// 将字母结点链到 A 表中 A->next=q;A=q; } else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next; p=p->next;// 指向下一结点 q->next=B->next;// 将数字结点链到 B 表中 B->next=q;B=q; } else { // 分出其他字符结点 q=p->next; p=p->next;// 指向下一结点 q->next=C->next;// 将其他结点链到 C 表中 C->next=q;C=q; }} }// 结束设有一个双链表, 每个结点中除有 prior 、 data 和 next 三个域外,还有一个访问频度域 freq ,在链表被起用之前,其值均初始化为零。每当在链表进行一次 LocateNode(L,x) 运算时,令元素值为 x 的结点中 freq 域的值加 1 ,并调整表中结点的次序,使其按访问频度的递减序排列, 以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。解: LocateNode 运算的基本思想就是在双向链表中查找值为 x 的结点, 具体方法与单链表中查找一样。找到结点*p 后给 freq 域的值加 1。由于原来比*p 结点查找频度高的结点都排它前面, 所以, 接下去要顺着前趋指针找到第一个频度小于或等于*p 结点频度的结点*q 后,将*p 结点从原来的位置删除,并插入到*q 后就可以了。算法如下: // 双向链表的存储结构 typedef struct dlistnode{ DataType data; struct dlistnode *prior,*next; int freq; }DListNode; typedef DListNode *DLinkList; void LocateNode( LinkList L, DataType x) { ListNode *p, *q; p=L->next; // 带有头结点 while( p&&p->data!=x ) p=p->next; if (!p) ERROR("x is not in L");// 双链表中无值为 x 的结点 else { p->freq++;//freq 加1 q=p->prior;// 以q 为扫描指针寻找第一个频度大于或等于*p 频度的结点 while(q!=L&&q->freq<p->freq) q=q->prior; if (q->next!=p)// 若*q 结点和*p 结点不为直接前趋直接后继关系, // 则将*p 结点链到*q 结点后{p->prior->next=p->next;// 将*p 从原来位置摘下 p->next->prior=p->prior; q->next->prior=p;// 将*p 插入*q 之后。 p->next=q->next; q->next=p; p->prior=q; } }} 设将整数 1,2,3,4 依次进栈, 但只要出栈时栈非空, 则可将出栈操作按任何次序夹入其中,请回答下述问题: (1) 若入、出栈次序为 Push(1), Pop(),Push(2),Push(