是否知解? 1. 设L={a1,b1,a2,b2,...,an,bn}为一线性表, 编写一个算法, 将其拆分为两个线性表,使得: L1={a1,a2, ...,an},L2={bn,bn-1,...,b1}。 答案: 思想:循环扫描L表,使用尾插法建立L1表,用头插法建立L2表。 void sqlit(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; L1=L; r1=L1; L2=(LinkList *)malloc(sizeof(LinkList)); L2->next=NULL; while(p!=NULL) { q=p->next; r1->next=p; r1=p; p=q->next; q->next=L2->next; L2->next=q; } r1->next=NULL; } 2. 假设二叉树采用二叉链式存储结构,设计算法,计算一棵给定二叉树中值为k的结点总数。 答案: 思想:f(b,k)=0 当根为空 f(b,k)=1+f(b->lchild,k)+ f(b->rchild,k) 当b->data=k f(b,k)=f(b->lchild,k)+ f(b->rchild,k) 其他情况 typedef struct btreenode { ElemType data; //数据元素 struct btreenode *lchild; //指向结点 struct btreenode *rchild; //指向右孩子结点 } BTNode; int ValueNodes(BTNode *b,char k) //在根为b结点的二叉树中统计值为k的结点个数 { if(b==NULL) return 0; else if (b->data==k) return(1+ValueNodes(b->lchild,k)+ValueNodes(b->rchild,k)); else return(ValueNodes(b->lchild,k)+ValueNodes(b->rchild,k)); }