数据结构常考算法大全

2021年1月25日发(作者：surveillance)
数据结构常考算法大全

HL
是单链表的头指针，试写出删除头结点的算法
。

ElemTypeDeleFront(LNode * & HL)

{

if (HL==NULL){

cerr<<
空表


exit(1);

}

LNode* p=HL;

HL=HL->next;

ElemType

temp=p->data;

delete p;

return temp;

}



统计出单链表
HL
中结点的值等于给定值
X
的结点
数。

intCountX(LNode* HL,ElemType x)

{

int i=0; LNode* p=HL;//i
为计数器







while(p!=NULL)









{ if (P->data==x) i++;











p=p->next;










}//while,
出循环时
i
中的值即为
x
结点个数








return i;




}//CountX



写算法，
将一个结点类型为
Lnode
的单链表按逆序链
接，
即若原单链表中存储元素 的次序为
a1
，
……an
-1
，
an
，则逆序链接 后变为
, an
，
an-1
，
……a1
。

Void

contrary (Lnode * & H
L)

{

Lnode *P=HL;

HL=NULL;

While (p!=null)




{



Lnode*q=p;







P=p
→
next;







q
→
next=HL;







HL=q;





}

}

34
．阅读下列函数
arrange()

int arrange(int a[],int 1,int h,int x)


{//1
和
h
分别为数据区的下界和上界

inti,j,t
；






i=1
；
j=h
；







while(i










while(i=x)j--
；










while(i=x)i++
；










if(i












{

t=a[j]
；
a[j]=a[i]
；
a[i]=t；
}







}










if(a[i]
；










else

return i
－
1
；







}

（
1
）写出该函数的功能；

（
2< br>）
写一个调用上述函数实现下列功能的算法：
对一整型数组
b[n]
中 的元素进行重新排列，
将所有负数均调整到数组的低下标
端，将所有正数均调整到数组的高下标 端，若有零值，则置
于两者之间，并返回数组中零元素的个数。

五、算法设计题（本题共
10
分）




34
．（
1
）该函数的功能是：调整整数数组
a[]
中的元素并返 回
分界值
i
，使所有＜
x
的元素均落在
a[1..i]上，使所有≥
x
的元素均落在
a[i
＋
1..h]
上。

（
2
）
int f(int b[],int n)





或
int f(int b[],int n)















{






















{

intp,q
；
intp,q
；




p=arrange(b,0,n
－
1,0)
；




p=arrange(b,0,n
－
1,1)
；




q= arrange(b,p+1,n
－
1,1)
；

q= arrange(b,0,p,0)
；




return q
－
p
；













return p
－
q
；




}
























}

设计判断单链表中结点是否关于中心对称算法
。

typedefstruct {int s[100]; int top;} sqstack;

intlklistsymmetry(lklist *head)

{

sqstack stack;

= -1; lklist *p;



for(p=head;p!=0;p=p->next) {++;
stack.s[]=p->data;}



for(p=head;p!=0;p=p->next) if (p->data==stack.s[])
=-1; else return(0);



return(1);

}

设计在链式存储结构上建立一棵二叉树的算法
。

typedef char datatype;

typedefstruct node {datatype data; struct node *lchild,*rchild;}
bitree;

void createbitree(bitree *&bt)

{



char ch; scanf(



if(ch=='#') {bt=0; return;}

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch;

createbitree(bt->lchild); createbitree(bt->rchild);

}

设计判断一棵二叉树是否是二叉排序树的算法。

intminnum=-32768,flag=1;

typedefstruct node{int key; struct node *lchild,*rchild;}bitree;

void inorder(bitree *bt)

{



if (bt!=0)



{inorder(bt->lchild); if(minnum>bt->key)flag=0;
minnum=bt->key; inorder(bt->rchild);}

}





设有一组初始记录关键字序列（
K1
，
K2
，
… ，
Kn
）
，
要求设计一个算法能够在
O(n)
的时间复杂度 内将线
性表划分成两部分，
其中左半部分的每个关键字均小
于
Ki
， 右半部分的每个关键字均大于等于
Ki
。

void quickpass(int r[], int s,int t)
{

int i=s, j=t, x=r[s];

while(iwhile (ix) j=j-1; if (i



while (i
}

r[i]=x;
}
设有两个集合
A
和集合
B
， 要求设计生成集合
C=A
∩
B
的算法，其中集合
A
、
B
和
C
用链式存储结构表
示。

typedefstruct node {int data; struct node *next;}lklist;

void intersection(lklist *ha,lklist *hb,lklist *&hc)

{

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{

for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}

}

}

设计在单链表中删除值相同的多余结点的算法。

typedefintdatatype;

typedefstruct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head)

{

lklist *p,*q,*s;




for(p=head;p!=0;p=p->next)




{






for(q=p->next,s=q;q!=0; )






if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}






else {s=q,q=q->next;}




}

}

设计一个求结点
x
在二叉树中的双亲结点算法。

typedefstruct node {datatype data; struct node *lchild,*rchild;} bitree;

bitree *q[20]; int r=0,f=0,flag=0;

void preorder(bitree *bt, char x)

{



if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x);
preorder(bt->rchild,x); }

}

void parent(bitree *bt,char x)

{

int i;




preorder(bt,x);




for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break;




if (flag==0) printf(




else if (i<=r) printf(

}



设单链表中有仅三类字符的数据 元素
(
大写字母、数
字和其它字符
)
，要求利用原单链表中结点空间 设计
出三个单链表的算法，使每个单链表只包含同类字
符。

typedef char datatype;

typedefstruct node {datatype data; struct node *next;}lklist;

void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)

{

lklist *p; ha=0,hb=0,hc=0;




for(p=head;p!=0;p=head)




{





head=p->next; p->next=0;





if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}





else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else
{p->next=hc; hc=p;}




}

}

计在链式存储结构上交换二叉树中所有结点左
右子树的算法。

typedefstruct node {int data; struct node *lchild,*rchild;} bitree;

void swapbitree(bitree *bt)

{

bitree *p;




if(bt==0) return;