数据结构复习资料--覆盖所有知识点(4)

2. 设有一带头结点的单链表，编写一个算法将链表颠倒过来。

void invert(LinkList &La){

/*逆置单链表*/

LinkList r,p=La->next; /*p为工作指针*/ La->next=NULL; while(p!=NULL){ }

}/*结束invert函数*/

3. 已知L为带头结点的单链表，设计一个算法计算数据域为x的结点个数。

int count(LinkList La,ElemType x){ //计数x出现的次数

LinkList p=La->next; //p为工作指针 int n=0; while(p){

if(p->data ==x) n++; p=p->next ;

r=p->next; /*暂存p的后继*/ p->next=La->next; La->next=p; p=r;

}return n;}

4. 设L为有序顺序表，试编写一个算法删除L中的重复元素。要求不要另开辟数据存储空间。

例如：L=（1，1，2，4，4，9，9，9），执行算法后L=（1，2，4，9）

int delduplicate(int a[],int n){ int i,j,k,count; i=0;

while (i

16

n=n-count;i++; }

return n;}

假设一个人算术表达式包含圆括弧，编写一个判别表达式中括弧是否正确匹配的算法。

Status AllBrackets_Test(char *str)// 判别表达式中三种括号是否匹配 {

InitStack(s); for(p=str;*p;p++) {

if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') {

if(StackEmpty(s)) return ERROR; pop(s,c);

if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR;

if(*p=='}'&&c!='{') return ERROR; // 必须与当前栈顶括号匹配 } }//for

if(!StackEmpty(s)) return ERROR; return OK;

5. 17

}//AllBrackets_Test

6. 设二叉树采用二叉链表法存储，试编写一个求二叉树深度的算法。 int Depth (BiTree &T ){ // 返回二叉树的深度 int depthval,depthLeft,depthRight; if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);

}

return depthval;}

7. 编写算法,求二叉树中度为2结点个数。

void Countdu2 (BiTree &T, int &count){ //统计二叉树中度为2结点的个数 if ( T ) {

if ((T->lchild)&& (T->rchild))

count++; // 对度为2的结点计数 Countdu2( T->lchild, count); Countdu2( T->rchild, count); } // if } // Countdu2

8. 编写算法,求二叉树中叶结点的个数。

void CountLeaf (BiTree &T, int &count){ if ( T ) {//统计叶子节点个数 if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if} // CountLeaf

18