Question

假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

Answer 1

问：假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

答：亲，您好，感谢您匀出宝贵的时间为我等待本题利用循环单链表的特点,通过 p 指针可循环找到其前驱结点 q 及 q 的前驱结点 r ,然后将其删除。 node *del(p) node *p {node *q, *r; q=p; while(q à next!=q) r=r à next; r à next=p; free(q); return(p); }

答：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关

问：已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，编写算法求出 A 和 B 的交集 C ，要求 C 同样以元素递增的单链表形式存储。

答：由于问题与问题补充不一致,问题是要求交集,是找A和B的相同元素,问题补充里是求并集,强调不是归并,我按并集写的,如果是交集再稍加修改就可以了.LinkList *LinkMag(LinkList *ha, LinkList *hb)//假设ha和hb是带头结点的链表{\x09Link *p, *q, *r,*hc,*aa;\x09hc->head = (Link*)malloc(sizeof(Link));\x09p = ha->next;\x09q = hb->next;\x09r = hc;\x09while(p!=NULL && q!=NULL)\x09{\x09aa = (Link*)malloc(sizeof(Link));\x09\x09if(p->datadata)//如果是交集的话,没有传递数据,只有指针移动,即只执行p=p->next;就可以了\x09\x09{\x09aa->data = p->data;\x09\x09\x09p = p->next;\x09\x09}\x09\x09else//如果是交集的话,还要判断等于的情况,只有等于的情况,才有传递数据,而大于的情况与小于情况类似,只有指针移动.\x09\x09{\x09aa->data = q->data;\x09\x09\x09q = q->next;\x09\x09}\x09\x09r->next = aa;\x09\x09r = aa;\x09}\x09while(p!=NULL)\x09{\x09aa = (Link*)malloc(sizeof(Link));\x09\x09aa->data = p->data;\x09\x09p = p->next;\x09\x09r->next = aa;\x09\x09r = aa;\x09\x09}\x09while(q!=NULL)\x09{\x09aa = (Link*)malloc(sizeof(Link));\x09\x09aa->data = q->data;\x09\x09q = q->next;\x09\x09r->next = aa;\x09\x09r = aa;\x09\x09}r->next=NULL;return hc;}

问：设有一个双向链表，每个结点中除有 prior 、 data 和 next 域外，还有一个访问频度 freq 域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次 Locata ( L , x ）运算后，令值为 x 的结点中的 freq 域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的 Locata ( L , x ）算法。

答：解:①n个顶点的连通图至少有n-1条边。②n个顶点的强连通图至少有n条边。7.7 DFS和BFS遍历采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小,应采用何种遍历?解:①DFS采用了栈;BFS采用了队列。②采用BFS。7.8画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。解:7.9按顺序输入顶点对:(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5),根据第7.2.2节中算法CreateALGraph画出相应的邻接表,并写出在该邻接表上,从顶点4开始搜索所得的DFS和BFS序列,及DFS和BFS生成树。解:依题意构造有向图:①邻接表②DFS和BFS序列DFS序列:4 5 3 1 6 2BFS序列:4 5 3 6 1 2③DFS和BFS生成树DFS生成树BFS生成树7.10什么样的图其最小生成树是唯一的?用Prim和Kruskal求最小生成数的时间各为多少?他们分别适合于哪个图?解:①具有n的结点,n-1条边的连通图其生成树是唯一的。