数据结构算法设计基础总结.docx

数据结构算法设计基础总结.docx

《数据结构算法设计基础总结.docx》由会员分享，可在线阅读，更多相关《数据结构算法设计基础总结.docx（24页珍藏版）》请在冰点文库上搜索。

数据结构算法设计基础总结

算法设计总结

--------------------------线性表部分--------------------

A,B单链表，递增有序。

设计A并B，生成按非递减有序C。

Voidmerge（LNode*A,LNode*B,LNode*&C）

{

LNode*p=A->next;

LNode*q=B->nxet;

LNode*r;

C=A;

C->nxet=NULL;

free（b）;

r=C;

while（p!

=NULL&&q!

=NULL）

{

if（p->data<=q->data）

{

r->next=p;p=p->nxet;

r=r->next;

}

else

{

r->nxet=q;q=q->next;

r=r->next;

}

}

r->next=null;

if（p!

=NULl）r->next=p;

if（q!

=NULL）r->next=q;

}

归并成递增有序C

Voidmerge（LNode*A,LNode*B,LNode*&C）

{

LNode*p=A->next;

LNode*q=B->nxet;

LNode*s;

C=A;

C->nxet=NULL;

free（b）;

r=C;

while（p!

=NULL&&q!

=NULL）

{

if（p->data<=q->data）

{

s=p;p=p->next;

s->next=C->next;

C->next=s;

}

else

{

s=q;q=q->next;

s->next=C->next;

C->next=s;

}

}

while（p!

=NULl）

{

s=p;p=p->next;

s->next=C->next;

C->next=s;

}

while（q!

=NULl）

{

s=q;q=q->next;

s->next=C->next;

C->next=s;

}

}

查找链表C（带头）是否存在一个值为X的节点，是，则删除返回1，否则返回0。

intSearchAndDelete（LNode*C,intx）

{

LNode*p,*q;

p=C;

while（p->next!

=NULL）

{

if（p->next->data==x）

break;

p=p->next;

}

if（p->next==NULL）

return0;

else

{

q=p->next;

p->next=p->next->next;

free（q）;

return1;

}

}

设计一个A[]，下标1-m+n范围内，前m个元素递增有序，后n个也递增有序，设计算法，使得整个表有序。

voidInsert（intA[],intm,intn）

{

inti,j;

inttemp;

for（i=m+1;i<=m+n;++i）

{

temp=A[i];

for（j=i-1;j>=1&&temp

A[j+1]=A[j];

A[j+1]=temp;

}

}

求A-B（元素个数分别是m，n，带头），保存于A。

voidDifference（LNode*A,LNode*B）

{

LNode*p=A->next,*q=B->next;

LNode*pre=A;

LNode*r;

while（p!

=NULL&&q!

=NULL）

{

if（p->datadata）

{

pre=p;

p=p->next;

}

elseif（p->data>q-data）

q=q->next;

else

{

pre->next=p->next;

r=p;

p=p->next;

free（r）;

}

}

}

删除L中下标大于等于i小于等于j的所有元素，假定i，j合法。

voiddelete（Sqlist&L,inti,intj）

{

intk,l;

l=j-i+1;

for（k=j+1;k<=L.length;++k）

{

L.data[k-l]=L.data[K];

}

L.length-=l;

}

将A分成两个A和B，A中含奇数，B中偶数，保持原序。

{

LNode*p,*q,*r;

B=（LNode*）malloc（sizeof（LNode））;

B->next=NULL;

r=B;

p=A;

while（p->next!

=NULL）

{

if（p->next->data%2==0）

{

q=p->next;

p->next=q->next;

q->next=NULL;

r->next=q;

r=q;

}

elsep=p->next;

}

}

----------------堆栈部分--------------

栈部分简易算法

intstack[maxSize];inttop=-1;

pop

stack[++top]=x;

push

x=stack[top--];

小括号匹配，表达式已经存入exp[]（下标从1开始）.字符个数n。

intmatch（charexp[],intn）

{

charstack[maxSize];inttop=-1;

inti;

for（i=1;i<=n;++i）

{

if（exp[i]=='（'）

stack[++top]='（';

if（exp[i]=='）'）

{

if（top==-1）

return0;

else

--top;

}

}

if（top==-1）

return1;

else

return0;

}

将10进制转化为二进制

intBaseTrans（intN）

{

inti,result=0;

intstack[maxSize];inttop=-1;

while（N!

=0）

{

i=N%2;

N=N/2;

stack[++top]=i;

}

while（top=-1）

{

i=stack[top--];

result=i+10*result;

}

returnresult;

}

---------------数组部分------------

建立三元组

voidcreaterimat（floatA[][maxSize],intm,intn,floatB[][3]）

{

intk=i;

for（inti=0;i

{

for（intj=0;j

{

B[k][0]=A[i][j];

B[k][1]=i;

B[k][2]=j;

++k;

}

B[0][0]=k-1;

B[0][1]=m;

B[0][2]=n

}

}

-------------树部分------------

表达式求值

intcomp（BTNode*p）

{

intA,B;

if（p!

=NULL）

{

if（p->lchild!

=NULL&&p->rchlid!

=NULL）

{

A=comp（p->lchild）;

B=comp（p->rchild）;

returnop（A,B,P->data）;

}

elsereturnp->data-'0';

}

elsereturn0;

}

先序遍历中第k个节点的值，假设k不大于总共节点数

intn=0;

voidtrave（BTNode*p,intk）

{

if（p）

{

++n;

if（k==n）

{

cout<data<

return;

}

trave（p->lchild,k）;

trave（p->rchild,k）;

}

}

中序遍历建立线索二叉树

voidInThread（TBTNode*p,TBTNode*pre）

{

if（p）

{

InThread（p->lchilde,pre）;

if（p->lchilde=NULL）

{

p->lchild=pre;

p->ltag=1;

}

if（pre!

=NULL&&pre->rchild==NULL）

{

pre->rchlid=p;

pre->rtag=1;

}

pre=p;

InThread（p->rchild,pr）;

}

}

voidcreatInThread（TBTNode*root）

{

TBTNode*pre=NULL;

if（root!

=NULL）

{

InTheard（root,pre）;

pre->rchild=NULL;

pre->rtag=1;

}

}

求中序线索后继节点

TBTNode*Next{TBTNode*p}

{

if（p->rtag==0）

{

p=p->rchild;

while（p->ltag==0）

p=p->lchild;

returnp;

}

else

returnp->rchild;

}

求中序线索最后一个结点

TBTNode*Next{TBTNode*p}

{

if（p->rtag==0）

{

p=p->rchild;

while（p->rtag==0）

p=p->rchild;

returnp;

}

else

returnp->rchild;

}

求中序线索前驱节点

TBTNode*Next{TBTNode*p}

{

if（p->ltag==0）

{

p=p->lchild;

while（p->ltag==0）

p=p->lchild;

returnp;

}

else

returnp->lchild;

}

返回公共祖先

charancestor（char,tree[],inti,intj）

{

intp=i,q=j;

while（p!

=q）

{

if（p>q）

p=p/2;

else

q=q/2;

}

returntree[p];

}

计算叶子节点数目

intcount（BTNode*p）

{

intn1,n2;

if（p==NULL）

return0;

elseif（p->lchild==NULL&&p->rchlid==NULL）

return1;

else

{

n1=count（p->lchild）;

n2=count（p->rchild）;

returnn1+n2;

}

}

求二叉树采用二叉链表存储，求b中值为x的节点层号。

intL

voidleno（BTNode*p,charx）

{

if（p）

{

if（p->data==x）

{

cout<

}

++L;

leno（p->lchild,x）;

leno（p->rhcild,x）;

--L;

}

}

———————————图部分——————————

链接矩阵定义

typedefstruct

{

intedge[maxSize][maxSize];

intn,e;

intvex[maxSize];

}MGraph;

链接表定义

typedefstructArcNode

{

intadjvex;

struct*nextarc;

}ArcNode;

typedefstructVNode

{

intdata;

ArcNode*firstarc;

}VNode;

typedefstruct

{

ArcNodeadjlist[maxSize];

intn,e;

}AGraph;

深度优先遍历

intVisit[maxSize];

voidDFS（Graph*g,intv）

{

ArcNode*p;

visit（v）;

Visit[v]=1;

p=g.adjlist[v].firstarc;

while（p）

{

if（visit[p.adjvex]==））

DFS[g,p.adjvex];

p=p->nextarc;

}

}

广度遍历

voidBFS（AGraph*g,intv,intvisit[maxSize]）

{

ArcNode*p;

intque[maxSize],intfront=0,intrear=0;

intj;

Visit（v）;

visit[v]=1;

rear=（rear+1）%maxSize;

que[rear]=v;

while（rear!

=front）

{

front=（front+1）%maxSize;

j=que[front];

p=g->adjlist[j].firstarc;

while（p）

{

if（visit[p->adjvex]==0）

{

Visit（p->adjvex）;

visit[p->adjvex]=1;

rear=（rear+1）%maxSize;

que[rear]=p->adjvex;

}

p=p->nextarc;

}

}

}

从i进行遍历，判断i到j是否有路径。

intDFSTrave（AGraphg,inti）

{

intk;

for（k=1;k<=g->n;++k）

visit[k]=0;

DFS（g,i）;

if（visit[j]==1）

return1;

else

return0;

}

图的连接表表示转化为链接矩阵表示

voidMGraphToAGraph（MGraph&g1,AGraphg2）

{

ArcNode*p;

inti,j;

for（i=1;i<=g1.n;++i）

for（j=1;j<=g1.n;++j）

g1.edges[i][j]=0;

for（i=1;i<=g2.n;++i）

{

p=g2.adjlist[i].firstarc;

while（p）

{

g1.edges[i][p->adjvex]=1;

p=p->nextarc;

}

}

}

求点k的入度。

intcount（AGraph*g,intk）

{

ArcNode*p;

inti,sum=0;

for（i=1;i<=g.n;++i）

{

p=g.adjlist[i].firstarc;

whilde（p）

{

if（p->adjvex==k）

{

++sum;

break;

}

p=p->nextarc;

}

}

returnsum;

}

----------排序--------------

直接插入

voidInsertSort（intR[],intn）

{

inti,j;

inttemp;

for（i=2;i<=n;++i）

{

j=i-i;

temp=R[i];

while（j>=1&&temp

{

R[j+1]=R[j];

--j;

}

R[j+1]=temp;

}

}

冒泡

voidBubbleSort（intR[];intn）

{

inti,j,flag;

inttemp;

for（i=n;i>2;--i）

{

flag=0;

for（j=2;j

{

if（R[j-1]>R[j]）

{

temp=R[j];

R[j]=R[j-1];

R[j-1]=temp;

flag=1;

}

if（flag=0）

return;

}

}

}

快排

voidQuickSort（intR[],intl,intr）

{

inttemp;

inti=l,intj=r;

if（l

{

temp=R[l];

while（i!

=j）

{

while（j>i&&R[j]>temp）--j;

if（i

{

R[i]=R[j];

++i;

}

while（j>i&&R[i]

if（i

{

R[j]=[i];

--j;

}

}

R[i]=temp;

QuickSort（R,l,i-1）;

QuickSort（R,i+1,r）;

}

}

将所有负值关键字放在所有非负关键字之前，下标1-n。

（类似快排）

voidSort（intR[],intn）

{

inti=1,j=n;

inttemp;

while（i

{

while（i

temp=R[i];

while（i=0）--j;

R[i++]=R[j];

R[j--]=temp;

}

}

简单选择排序

voidSelectSort（intR[],intn）

{

inti,j,k;

inttemp;

for（i=1;i<=n;++i）

{

k=i;

for（j=i+1;j<=n;++j）

{

if（R[k]>R[j]）

k=j;

}

temp=R[i];

R[i]=R[k];

R[k]=temp;

}

}

设计一个计数排序算法

voidcountSort（intA[],intB[],intn）

{

inti,j,count;

for（i=0;i<=n-1;++i）

{

count=0;

for（j=0;i<=n-1;++j）

if（A[j]

++count;

B[count]=A[i];

}

}

---------查找--------------

折半查找

intBsearch（intR[],intlow,inthigh,intk）

{

intmid;

while（low<=high）

{

mid=（low+high）/2;

if（R[mid]==k）

returnmid;

elseif（R[mid]>k）

high=mid-1;

else

low=mid+1;

}

return0;

}