清华大学《数据结构与算法》(5)

中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。 typedef struct node { int data;

struct node *next; } lklist;

void del( lklist rear, int &x);

{ lklist p,q;

q=rear-> next; //q为头结点

if (__rear-> next== rear ________) printf( “it is empty!\\n” ); else {

p=q->next;

x=p->data;

___q->next=p->next______________ ; //删除首元结点 if (_q->next==q__________) rear=q; //空，或rear== p free(p) ; }; };

2、堆分配存储方式下，串连接函数。 typedef struct { char * ch； int len； } HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ { int i; char *temp; f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］; for ( ;ilen + t.len;i++) temp［i］=t.ch［i-s->len］; s->len+=t.len; fr s->ch=temp; return(1); }

3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体

Void InsertRear(LNode*& HL,const ElemType& item) {

LNode* newptr; newptr=new LNode;

If (_____!newprt ______) {

cerr<<\exit(1); }

_______newptr->data_______=item; newptr->next=NULL; if (HL==NULL)

HL=____newptr_____; else{

LNode* P=HL;

While (P->next!=NULL) __p=p->next___; p->next=newptr; }

} 4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) {

LinkList Lc,p,pre; pre=L;

p= (1) ; p=L->next

Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {

pre->next=p->next;

(2) ; p->next=Lc->next Lc->next=p; p=pre->next; } else {

pre=p;

(3) ; p=p->next }

return Lc; }

5、已知图的邻接链表的顶点表结点结构为

边表结点EdgeNode的结构为

下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算

法。

int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 {

adjvex vertex firstedge next int dgree, j;

EdgeNode *p;

degree= (1) ; 0 for(j=0;jn;j++) {

p=G->adjlist［j］. firstedge; while ( (2) ) p {

if( (3) ) p->adjvex==i {

degree++; break; }

p=p->next; } }

return degree; }

六 简单应用题

1、已知一个非空二叉树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A

试将这样二叉树构造出来;若已知先根和后根的遍历结果，能否构造这棵二叉树，为什么? (基本方法：先由后根序列确定根结点，再到中序序列中分割该二叉树)

2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。

3、画出由下面的二叉树转换成的森林。

4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：

A 1 2 3 PATH 1 2 3

A(0) 1 2 (0) A(1) 3 1 2 (1) A(2) 3 1 2 (2) A(3) 3 1 2 (3) 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。(教材P149)

weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

5 29 7 8 14 23 3 11 -- -- -- -- -- -- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0

weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Lchild Rchild -- 0 0 0

6、考虑右图：

(1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分)

(3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)

答案如下：

七 编写算法题

1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x)

2、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）

由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。

int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材

{int maxdepth=0;

for(i=1;i<=t.n;i++)

{temp=0; f=i;

while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲

if(temp>maxdepth) maxdepth=temp; //最大深度更新 }

return(maxdepth);//返回树的深度 } //结束Depth