数据结构算法整理

1第四章串串的动态存储方式采用链式存储结构和堆存储结构两种形式//串的动态存储结构——块链存储类型定义#defineCHUNKSIZE用户定义的结点大小;typedefstructchunk----------结点结构{charch[CHUNKSIZE];structchunk*next;}chunktypedefstruct{chunk*head,*tail;---------尾指针指示链表中的最后一个结点intlength;--------串的长度}//串的动态存储结构——堆结构charstore[maxsize];typedefstructstring{intlength,*stadr;/*length域指示串序列的长度stadr域指示串序列的store中的起始地址*/};//串基本操作的实现——串的模式匹配（求子串位置）intIndex_bf(strtps,t);{/*Brute-Force算法思想求模式串t在主串s中的定位函数*/i=1;j=1;/*指针初始化*/while((i=s.curlen)&&(j=t.curlen)){if(s.ch[i]==t.ch[j]){i+1;j=j+1;}/*继续比较后继字符*/else{i=i-j+2;j=1;};/*指针后退重新开始匹配*/if(jt.curlen)returni-t.curlen;elsereturn0;};/*Index_bf*///串的简单应用——统计字母出现频率letter_Frequency(strtptext){/*统计给定文本text中每个字母出现的频率*/charalph[]='abcdefghijklmnopqrstuvwxyz';intfreq[26];total=0;n=len(text);2for(i=0;i26;i++)freq[i]=0;/*freq为数组*/for(i=0;in;i++){ch=SubStr(text,i,1);j=Index(alph,ch);if(j0){freq[j]=freq[j]+1;total=total+1;};}for(i=0;i26;i++){freq[i]=freq[i]/total;printf(‘%f’,freq[i]);}};/*Letter_Frequency*/第五章数组//稀疏矩阵的三元组表示法：#defineMAX10typedefstruct{inti,j;elemtypev;}node;typedefstruct{intmu,nu,tu;nodedata[MAX];}mat;//稀疏矩阵的转置运算的实现mat*zzjz(mat*a){intam.bn.col;mat*b;/*转置后的矩阵b*/b=(mat*)malloc(sizeof(mat));b.nu=a.mu;b.mu=a.nu;b.tu=a.tu;/*a,b矩阵行、列交换*/bn=0;for(col=1;col=a.nu;col++)/*按a的列序转置*/for(am=1;am=a.tu;am++)/*扫描整个三元组表*/if(a.data[am].j==col)/*列号为col是转置*/{b.data[bn].i=a.data[am].j;b.data[bn].j=a.data[am].i;b.data[bn].v=a.data[am].v;bn++;/*b.data中的结点序号加1*/}returnb;/*返回转置矩阵的指针*/3}//十字链表的结点类型定义如下：typedefstructnode{inti,j,v;structnode*down,*right;}szjd;//十字链表的建立表示法szlbcreate(szjd*m[],szjd*n[],int*hs,int*ls){intx,y,z,ms,ns;intk=0;szjd*p,*q,*s;ms=ns=0;scanf(“%d,%d”,&ms,&ns);for(k=0;kms;i++)m[k]=NULL;for(;kns;)n[k]=NULL;*hs=ms;*ls=ns;for(;;){scanf(%d,%d,%d”,&x,&y,&z);if(x==0||y==0)break;if((xms)||(yns))continue;s=(szjd*)malloc(sizeof(szjd));s-i=x;s-j=y;s-v=z;s-right=s-down=NULL;q=NULL;p=m[x-1];while((p!=NULL)&&(yp-j)){q=p;p=p-right;}if(p==NULL){if(q==NULL)m[x-1]=s;elseq-right=s;}elseif(y==p-j){p-v=z;free(s);continue;}else{s-right=p;q-right=s;}q=NULL;p=n[y-1];while((p!=NULL)&&(xp-i)){q=p;p=p-down;}4if(p==NULL)if(q==NULL)n[y-1]=s;elseq-down=s;else{s-down=p;q-down=s;}}}第六章树//二叉链表的类型定义：structbnodept{elemtypedata;structbnodept*lchild,*rchild}typedefstructbnodept*bitreptr;//遍历的递归算法的类型定义structbnodept{datatypedata;structbnodept*lchild,*rchild}//先根遍历的递归算法voidpreorder(bitreptrt)//按先根次序遍历二叉树T,T的每个根结点有三个域:lchild,data,rchild{if(t!=NULL)//为非空二叉树{visite(t-data);//访问根结点preorder(t-lchild);//先根遍历左子树preorder(t-rchild);//先根遍历右子树}}//voidpreorder(JD*bt){if(bt!=NULL){printf(%d\t,bt-data);preorder(bt-lchild);preorder(bt-rchild);}}//中根遍历的递归算法5voidinorder(bitreptrt)//按中根次序遍历二叉树t,t的每个结点有三个域:lchild,data,rchild{if(t!=NULL){inorder(t-lchild);visite(t-data);inorder(t-rchild);}}//后根遍历的递归算法voidpostorder(bitreptrt)//按后根次序遍历二叉树t,t的每个结点有三个域:lchild,data,rchild{if(t!=NULL){postorder(t-lchild);postorder(t-rchild);visite(t-data);}}//先根序遍历的非递归算法voidpreorder(bitreptrt){bitreptrstack[MAX+1];//顺序栈inttop=0;//栈顶指针do{while(t!=NULL){visite(t-data);//访问根结点if(top==MAX)//栈已满{printf(“stackfull”);return;//不能再遍历下去}stack[++top]=t;//根指针进栈t=t-lchild;//移向左子树}if(top!=0)//栈中还有根指针{t=stack[top--];//取出根指针t=t-rchild;//移向右子树}}while(top!=0||t!=NULL);//栈非空或为非空子树}//中根序遍历的非递归算法voidinorder(JD*bt){inti=0;JD*p,*s[M];p=bt;6do{while(p!=NULL){s[i++]=p;p=p-lchild;}if(i0){p=s[--i];printf(%d\t,p-data);p=p-rchild;}}while(i0||p!=NULL);}//二叉树中以值为x的结点为根的子树深度intGet_Sub_Depth(bitreptrT,datatypex)//求二叉树中以值为x的结点为根的子树深度{if(T-data==x){printf(%d\n,Get_Depth(T));//找到了值为x的结点,求其深度exit1;}else{if(T-lchild)Get_Sub_Depth(T-lchild,x);if(T-rchild)Get_Sub_Depth(T-rchild,x);//在左右子树中继续寻找}}//Get_Sub_Depth//intGet_Depth(bitreptrT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;}}//Get_Depth//在二叉树中求指定结点的层数。intpreorder(bitreptrroot,datatypech)//在二叉树root中求值为ch的结点所在的层数{intlev,m,n;if(root==NULL)lev=0;//空树7elseif(root-data==ch)lev=1;//ch所在结点为根结点else{m=preorder(root-lchild,ch);//在左子树中查找ch所在结点n=preorder(root-rchild,ch);//在右子树中查找ch所在结点if(m==0&&n==0)lev=0;//在左右子树中查找失败elselev=((mn)?m:n)+1;//在左子树或右子树中查找成功时,层数加1}return(lev);}//按先序序列建立二叉树的二叉链表。bitreptrcrt_bt_pre()//按先序序列建立二叉树的二叉链表。函数的返回值指向根结点{charch;bitreptrbt;ch=getchar();//从键盘上输入一个字符if(ch=='')return(NULL);//空格作为结束标志else{bt=(bitreptr)malloc(sizeof(structbnodept));//产生新结点bt-data=ch;bt-lchild=crt_bt_pre();bt-rchild=crt_bt_pre();return(bt);}}//求二叉树的叶子数intcountleaf(bitreptrroot)//先根遍历根指针为root的二叉树以计算其叶子数{inti;if(root==NULL)i=0;elseif((root-lchild==NULL)&&(root-rchild==NULL))i=1;elsei=count2(root-lchild)+count2(root-rchild);return(i);}//二叉树中根序线索化Typedefenum{link,thread}pointertag;//枚举值link和thread分别为0，18Typedefstructnode{Datatypedata;Pointertagltag,rtag;//左右标志Structnode*lchild,*rchild;}binthrnode;typedefbinthrnode*binthrtree;binthrnode*pre=NULL;//全局变量voidinorderthreading(binthrtreep)//将二叉树p中序线索化{if(p)//p非空时，当前访问结点是*p{inorderthreading(p-lchild);//左子树线索化//以下直至右子树线索化之前相当于遍历算法中访问结点的操作p-ltag=(p-lchild)?link:thread;//左指针非空时左标