一些简单的常用的数据算法

1.编写一个算法，利用栈将一个非负的十进制整数N转换为一个二进制整数。<xmlnamespaceprefix

="o"ns="urn:schemas-microsoft-com:office:office"/>基本思想：十进制整数N化为二进制整数的方法是，首先将N反复除以2,直到整数商为0,然后逆取余。因为“逆取余”正好符合“后进先出”原则，所以用栈保存运算过程中得到的各个余数。typedefintdatatype;〃顺序栈的类型定义

#definemaxsize1024typedefstruct

(datatypedata[maxsize];inttop;}seqstack;voidtran(seqstack*s,intn){s->top=-1;〃置空栈while(n!=0)〃当n不为0时反复"除基逆取余”{s->top++;s->data[s->top]=n%2;〃余数进栈n=n/2;//计算整数商}}设计算法，实现统计单链表中具有给定值x的所有元素的个数。基本思想：从左往右扫描带头结点的单向链表，每见到一个值为x的元素，都使计数器增1。

算法：//结点类型定义

typedefintdatatype;typedefstructnode

(datatypedata;structnode*next;}linklist;intcountx(linklist*head,datatypex)

{intn=0;head=head->next;//跳过头结点while(head!=NULL){if(head->data==x)n++;head=head->next;}returnn;}设计算法，实现在非递减有序的单链表中删除值相同的多于结点。基本思想：用指针变量head从左往右扫描带头结点的单向链表。对每个当前结点*head，都检查它与后继

结点的值是否相等：若相等，则删除后继结点，head不动；否则，移动head。算法：//结点类型定义

typedefintdatatype;typedefstructnode

(datatypedata;structnode*next;}linklist;voiddeletedyys(linklist*head)

{linklist*p;head=head->next;//指向第一个结点if(head!=NULL){p=head->next;while(p!=NULL)if(head->data==p->data){head->next=p->next;free(p);p=head->next;}else{head=p;p=head->next;}}}设记录的关键字集合K={23,9,39,5,68,12,62,48,33},给定的增量序列D={4,2,1},请写出对K按希尔排序时各趟排序结束时的结果。第一趟结果：23,9,39,5,33,12,62,48,68第二趟结果：23,5,33,9,39,12,62,48,68第三趟结果：5,9,12,25,33,39,48,62,68设一个字符串用一个带头结点的单链表存储。请设计一个算法，删除字符串中所有字符'a'。结点类型名为linkstring,,结点结构如下：datanext二叉树采用二叉链表存储，设计一个算法求一棵给定二叉树中没有左孩子的结点数。结点类型名为

Ibitref,结点结构如下：〔Ichilddatarchild设有两个字符的集合A,B，分别用带头结点的单链表表示。请设计一个算法，利用原有结点空间实现集

合A与B的并运算AUB。结点类型名为linkstri?g,结点结构如下：

datanextvoidmerge1(LinkList&A,LinkList&B,LinkList&C)//把链表A和B合并为C,A和B的元素间隔排列,且使用

原存储空间{

p=A->next;q=B->next;C=A;while(p&&q)

{s=p->next;p->next=q;//将B的元素插入

if(s){t=q->next;q->next=s;//如A非空，将A的元素插入}P=s；q=t；}//while}//merge1二叉树采用二叉链表存储。设计一个算法求一棵二叉树中data域值等于x的结点个数。要求：利用层

次遍历，或使用其它的非递归方法。结点类型名为bitree，结点结构如下：Ichilddatarchild采用深度优先的示例：voidcountl(bitreptrr,datatypex,int&k){if(!bitreptrr)return;if(bitreptrr->value==x){k++;}

countl((bitreptrr->left,x,k);countl((bitreptrr->right,x,k);}voidGetnum(BTNode*t,int*n,int*m)//n是叶子节点数，m是非叶子结点数//其中n,m的初值为零。非递归算法{BTNode*queue=newBTNode[50];//初始化一个队列BTNode*T=t;intrear=0,front=0;if(!T)return;//若树为空，则返回

queue[rear++]=T;while(rear!=front){T=queue[front++];if(T->Lchild||T->Rchild)//结点有左子树或右子树{(*m)++;if(T->Lchild)queue[rear++]=T->Lchild;if(T->Rchild)queue[rear++]=T->Rchild;}else(*n)++;}}试编写一个算法，按关键字由大到小遍历一棵二叉排序树。10.设计算法，对顺序存储的线性表(其中每个元素是一个正整数)，在T(n)=O(n),S(n)=O(1)内将所有奇

数放在所有偶数前。在链式存储的线性表中将值为x的结点与值为y的结点互换。无向图采用邻接矩阵或邻接表表示。请设计算法，对输入的一条边，检查图中是否存在该边。若不存

在，则插入此边，否则删除该边。往图中插入一个顶点(2)往图中插入一条边(3)删去图中某顶点(4)删去图中某条边用邻接矩阵表示算法设计#defineMaxVertexNum100//最大顶点数，应由用户定义typedefcharVertexType；〃顶点类型应由用户定义typedefintEdgeType；〃边上的权值类型应由用户定义typedefstruct(VextexTypevexs[MaxVertexNum]//顶点表EdeTypeedges[MaxVertexNum][MaxVertexNum];〃邻接矩阵，可看作边表intn，e；〃图中当前的顶点数和边数}MGragh；(1)往图中插入一个顶点voidAddVertexMGraph(MGraph*G,VertexTypex){//往无向图的邻接矩阵中插入顶点if(G->n>=MaxVertexNum)Error("顶点数太多”)；G->vexs[G->n]=x;//将新顶点输入顶点表G->n++；〃顶点数加1}往图中插入一条边voidAddedgeMGraph(MGraph*G,VertexTypex,VertexTypey){//往无向图的邻接矩阵中插入边(x,y)inti,j,k;i=-1;j=-1;for(k=0;k<G->n;k++)//查找X，Y的编号{if(g->vexs[k]===x)i=k;if(g->vexs[k]==y)j=k;}if(i==-1||j==-1)Error("结点不存在”)；else{//插入边(x,y)g->vex[i][j]=1;g->vex[j][i]=1;G->e++;//边数加1}}删去图中某顶点voidDeleteVertexMGraph(MGraph*G,VertexTypex){//无向图的邻接矩阵中删除顶点xinti,k,j;i=-1;for(k=0;k<G->n;k++)//查找X的编号if(g->vexs[k]=x)i=k;if(i==-1)Error(-结点不存在”)；else{〃删除顶点以及边k=0;/俅出与x结点相关联的边数kfor(j=0;j<G->n;j++)if(g->vexs[i][j]==0)k++;G->e=G->e-k;//设置新的边数for(k=i+1;k<G->n;k++)//在邻接矩阵中删除第i行for(j=0;j<G->n;j++)g->vexs[k-1][j]=g->vexs[k][j];for(k=i+1;k<G->n;k++)//在邻接矩阵中删除第i列for(j=0;j<G->n;j++)g->vexs[j][k-1]=g->vexs[j][k];G->n--;//总结点数-1}}删去图中某条边voidDeleteedgeMGraph(MGraph*G,VertexTypex,VertexTypey){//无向图的邻接矩阵中删除边(x,y)inti,j,k;i=-1;j=-1;for(k=0;k<G->n;k++)//查找X，Y的编号{if(g->vexs[k]=x)i=k;if(g->vexs[k]=y)j=k;}if(i==-1||j==-1)Error("结点不存在，elseif(g->vexs[i][j]!=1){//删除边(x,y)g->vex[i][j]=0;g->vex[j][i]=0;G->e--;//边数加1}}假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。解析：利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q,然后可删除结点*?。实现算法：vioddelepre(s)LinkNode*s;{LinkNode*p,*q;p=s;while(p->next=s){q=p;p=p->next;}q->next=s;free(p);}在值递增单链表中插入一个值为x的结点，仍递增intInsert_Linkx(LinkListH,ElemTypex){LNode*q=H,*s;*p=H->next;while(p!=NULL&&p->data<x)/*q->next&&q->next->data<x*/{q=p;p=p->next;}/*查找a结点*/s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/s->data=x;s->next=q->next;/*新结点插入*/q->next=s；returnOK;}/*Insert_Linkx*/二叉树的中序遍历的非递归算法。voidInorder2(BTNode*bt)while(p||top>-1){if(p){++top；s[top]=p；p=p->lchild；}else{p=s[top]；--top；printf(p->data；p=p->rchild；}/*利用栈实现前序遍历非递归算法*/{p=bt；top=-1；/*二叉树非空*//*根结点指针进栈*//*p移向左孩子*//*栈非空*//*双亲结点指针出栈*//*访问根结点，输出结点*/}/*p移向右孩子*/-/*Inorder2*/设二叉树以二叉链表形式存储，写出一个求叶子结点总个数的算法。voidLeaf_BiTree(BTNode*T)/*求树的深度及叶子结点个数*/{if(T){if(T->lchild==NULL&&T->rchild==NULL){printf("%c\n",T->data);count++;}Leaf_BiTree(T->lchild,j);Leaf_BiTree(T->rchild,j);}}/*Leaf_BiTree*/删除线性表a中第i个元素起的k个元素StatusDeleteK(SqList&a,inti,intk){if(i<1llk<0lli+k-1>a.length)returnINFEASIBLE;for(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;returnOK;}//DeleteK把x插入递增有序表va中StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1>va.listsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}//Insert_SqList判别表达式中三种括号是否匹配StatusAllBrackets_Test(char*str)//判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;〃必、须与当前栈顶括号匹配}}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test19、试写一算法写出用二叉链表表示给定二叉树的叶结点总数。求叶结点数问题#include<stdio.h>#include<malloc.h>typedefcharDatatype;//以下为二叉链表的结构定义typedefstructnode{Datatypedata;node*lchild;node*rchild;}BinTreeNode;typedefBinTreeNode*BinTree;

voidCreatBinTree(BinTree*T){//构造二叉链表。T是指向根的指针，故修改了*丁就修改了实参charch;if((ch=getchar())=='')*T=NULL;else{〃读入非空格*T=(BinTreeNode*)malloc(sizeof(BinTreeNode));//生成结点(*T)->data=ch;CreatBinTree(&(*T)->lchild);〃构造左子树CreatBinTree(&(*T)->rchild);〃构造右子树}

}

intGetLeaves(BinTreeroot)

{/俅叶结点总数staticintleaf=0;//此l用于记叶结点数，注意用静态变量

if(root){〃递归计算叶结点数if(!(root->lchild||root->rchild))leaf++;//如果该结点无左右孩子，则叶子数加1GetLeaves(root->lchild);//算左子数的叶结点数GetLeaves(root->rchild);//算右子树的叶结点数}returnleaf;//返回结果

}

voidmain(){〃以下为验证程序BinTreeroot;

CreatBinTree(&root);intleaves=GetLeaves(root);

printf("Totalleaves=%d”,leaves);

}以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为：voidinordercount(tnodetype*t)/*中序遍历二叉树，统计树中的结点数和叶子结点数*/{if(t!=NULL){inordercount(t->lch);/*中序遍历左子树*/printf("％c\n”,t->data);/*访问根结点*/countnode++;/*结点计数*/if((t->lch==N