线性表
设计一个时间复杂度为O(N)的算法，实现将数组A[n]中所有元素循环左移k个位置
分析：把数组ab转换成数组ba，先把a置逆，再把b置逆，最后将a,b置逆。
Void converse(char a[],int n,int k)
{
Reverse(a,0,k-1);
Reverse(a,k,n-1);
Reverse(a,0,n-1);
}
Void reverse(char A[],int from,int to)
{
For(i=0;i<(to-from+1)/2;i++)
{
A[from+i]<->A[to-i]
}
}
设计算法实现单链表就地置逆
分析：即将每个结点的指针由指向该结点的后继改为指向该结点的前驱。在扫描过程中设置三个指针。
Void reverse(node *first)
{
P=first->next; pre=NULL; //如果针对循环链表，则只需要把NULL改为头指针first即可
While(p!=NULL)
{
R=p->next;
p->next=pre;
pre=p;
p=r;
}
First->next=pre;
}
栈和队列
设计递归算法求解在n元集合A={1,2…n}中选取k个元素的所有组合。
分析：第一次选择有包括1与不包括1两种情况，包括1在后续中选k-1个，不包括1在后续中选k个。
Void comb(int I,int n,int k)
{
If(n-i+1<=k)
{
For(i=1;i<=k;i++)
Printf(B[i]);
Printf(“/n”);
}
Else
{
B[i]=A[i];
Comb(i+1,n,k-1);
Comb(i+1,n,k);
}
}
树与二叉树
已知深度为h的二叉树采用顺序存储结构已存放于数组B[1….2^h-1]中，编写递归算法产生该二叉树的二叉链表结构。
分析：可以采用一个队列，先将二叉树的根结点即数组的第一个元素建立对应的二叉链表的根结点，并入队列，然后对队列中的元素依次进行出队并考查该结点。
Void seqtobi(binode *T, elemtype BT[], int n)
{
Len=2^h-1;
T=(binode *)malloc(sizeof(binode));
T->data=BT[1];
Front=0;rear=0;
Tq.ptr=T; tq.num=1;Q[++rear]=tq;
While(front!=rear)
{
Tq=Q[++front];p=tq.ptr;i=tq.num;
If(BT[2*i]==0||2*i>len) p->lchild=NULL; //左子树为空时
Else
{
p->lchild=(binode*)malloc(sizeof(binode));
p->lchild->data=BT[2*i];
tq.ptr=p->lchild;tq.num=2*i;Q[++rear]=tq; //左孩子及其编号入队
}
If(BT[2*i+1]==0||2*i+1>len) p->lchild=NULL; //右子树为空时
Else
{
p->rchild=(binode*)malloc(sizeof(binode));
p->rchild->data=BT[2*i+1];
tq.ptr=p->rchild;tq.num=2*i+1;Q[++rear]=tq; //右孩子及其编号入队
}
}
}
一棵二叉树以二叉链表存储，求二叉树第k层上叶子结点的个数
分析：设置last记载当前访问结点所在的层次，将last指向该层地最右结点，当last结点处理完则遍历进入下一层。
Int leaflevel(binode *T,int k)
{
If(T==NULL) return 0 ;
Leaf=0 ;
Front=0 ;rear=0 ;
Last=1 ;level=1 ;//last是二叉树同层最右结点的指针
Q[++rear]=T ;
While(front<rear)
{
P=Q[++rear] ;
If(level==k&& !p->lchild&& !p->rchild) leaf++; //统计叶子结点个数
If(p->lchild)Q[++rear]=p->lchild; //左孩子入队
If(p->rchild)Q[++rear]=p->rchild;//右孩子入队
If(front==last) //正在处理的结点是该层最右结点
{
Level++;
Last=rear;
}
If(level>k) return leaf; //层数大于k无需继续处理
}
}
中序线索链表的构造
Void inthrbitree(thrnode *root)
{
If(root==NULL) return;
Inthrbitree(root->lchild);
If(!root->lchild) //对root左指针进行处理
{
Root->ltag=1;
Root->lchild=pre;
}
If(!root->rchild) root->rtag=1;//对root的右指针进行处理
If(pre->rtag==1) pre->rchild=root;//设置pre的后继线索
Pre=root;
Inthrbitree(root->rchild);
}
求最近公共祖先,p,q分别为指向该二叉树中任意两个结点的指针，找到p,q最近公共祖先r
Binode *ancestor(binode *root,binode *p,binode *q,binode *r)
{
Top=0;bt=root;
While(bt!=NULL||top>0)
{
While(bt!=NULL)//沿左分支向下
{
Top++;s[top].ptr=bt;s[top].flag=1;
Bt=bt->lchild;
}
While(top!=0&&s[top].flag==2)
{
If(s[top].ptr==p)
{
For(i=1;i<=top;i++) //将栈s的结点拷贝到栈t中
T[i]=s[i];
Top1=top;
}
If(s[top].ptr==q) //访问到结点q
{
For(i=top;i>0;i–)
{
For(j=top1;j>0;j–)
{
If(t[j].ptr==s[i].ptr)//找到最近的公共祖先
Return s[i].ptr;
}
}
}
Top–;
}
If(top!=0) //准备沿右分支遍历
{
S[top].flag=2;bt=s[top].ptr->rchild;
}
}
Return NULL;
}
图
深度优先遍历算法
Void dfs(mgraph G,int v)
{
Printf(G.vertex[v]);visited[v]=1;
For(j=0;j<G.vertexNum;j++)
If(G.arc[v][j]==1&&visited[j]==0) dfs(G,j);
}
广度优先遍历算法
Void bfs(mgraph G,int v)
{
Front=rear=-1;
Printf(G.vertex[v]); visited[v]=1;Q[++rear]=v; //被访问顶点入队
While(front!=rear)
{
V=Q[++front];
For(j=0;j<G.vertexNum;j++)
{
If(G.arc[v][j]==1&&visited[j]==0)
{
Printf(G.vertex[j]);visited[j]=1;Q[++rear]=j;
}
}
}
}
Prim算法
Void prim(mgraph G)
{
For(i=1;i<G.vertexNum;i++)
{
Lowcost[i]=G.arc[0][i];
Adjvex[i]=0;
}
Lowcost[0]=0;
For(i=1;i<G.vertexNum;i++)
{
K=minedge(lowcost,G.vertexNum); //在lowcost中寻找最短边的顶点x
Printf(k,adjvex[k],lowcost[k]); //输出加入到TE中的边
Lowcost[k]=0; //将顶点K加入集合U中
For(j=1;j<G.vertexNum;j++)
{
If(G.arc[k][j]<lowcost[j])
{
Lowcost[j]=G.arc[k][j];
Adjvex[j]=k;
}
}
}
}
Dijkstra算法
Dist[i]:表示当前找到的从源点v到终点vi的最短路径长度
Path[i]:表示当前找到的从源点v到终点vi的最短路径
S[n]:存放源点和已经生成的终点，初态为只有一个源点v
Void dijkstra(Mgraph G,int v)
{
For(i=0;i<G..vertexNum;i++) //初始化dist[n],path[n]
{
Dist[i]=G.arc[v][i];
If(dist[i]!=∞) path[i]=G.vertex[v]+G.vertex[i];
Else path[i]=””;
}
S[0]=G.vertex[v]; //初始化集合s
Dist[v]=0; //标记顶点v的源点
Num=1;
While(num<G.vertexNum)
{
For(k=0,i=1;i<G.vertexNum;i++)
{
If((dist[i]<dist[k])&&dist[i]!=0) k=I;
}
Printf(dist[k],path[k]);
S[num++]=G.vertex[k]; //将新生成的终点vk加入集合S
Dist[k]=0; //置顶点vk为已生成终点标记
For(i=0;i<G.vertexNum;i++)
If(dist[i]>dist[k]+G.arc[k][i])
{
Dist[i]=dist[k]+G.arc[k][i];
Path[i]=path[k]+G.vertex[i];
}
}
}
查找
二叉排序树的删除算法
Void deletebst(binode *p,binode *f)
{
If(!p->lchild&&!p->rchild) //p为叶子结点
{
f->lchild=NULL;delete p;
}
Else if(!p->rchild) //p只有左子树
{
f->lchild=p->lchild;delete p;
}
Else if(!p->lchild) //p只有右子树
{
f->lchild=p->rchild;delete p;
}
Else //p左右子树均不为空
{
Par=p; s=p->rchild;
While(s->lchild!=NULL)
{
Par=s;s=s->lchild;
}
p->data=s->data;
if(par==p)
par->rchild=s->rchild;
else
par->lchild=s->rchild;
delete s;
}
}
排序
快速排序的一次划分
Int partition(int r[],int first,int end)
{
I=first;j=end;
While(i<j)
{
While(i<j&&r[i]<=r[j]) j–; //右侧扫描
If(i<j)
{
R[i]<->r[j];i++;
}
While(i<j&&r[i]<=r[j]) i++;//左侧扫描
If(i<j)
{
R[j]<->r[i]; j–;
}
}
Return I;
}
Void quicksort(int r[],int first,int end)
{
If(first<end)
{
Pivot=partition(r,first,end);//一次划分，pivot为轴的最终位置
Quicksort(r,first,pivot-1); //对左侧进行划分
Quicksort(r,pivot+1,end);//对右侧进行划分
}
}
堆调整算法,m为堆中最后一个结点的编号，k为当前要筛选结点的编号
Void shift(int r[],int k,int m)
{
I=k;j=2*I; //i为要筛选的结点，j为i的左孩子
While(j<m)
{
If(j<m&&r[j]<r[j+1]) j++; //比较i的左右孩子，j为较大者
If(r[i]>r[j]) break; //根结点大于较大者
Else
{
R[i]<->r[j]; //将根结点与结点j交换
I=j;j=2*I; //被筛选结点位于原来j结点位置
}
}
}