ツリー検索、一致文字列、クイックソート
4025 ワード
: , ,40 ,C
, , , n 。 : , ,ascii 。
#include
#include
#include
#define SIZE 100
struct TreeNode{
char *str;
struct TreeNode *left, *right;
};
struct help{
int num;
struct TreeNode *node;
};
struct help pall[SIZE]={};;
int inde =0;
int com(struct help *p1,struct help *p2){
if(p1->num < p2->num){
return 1;
}
if(p1->num == p2->num){
if(strlen(p1->node->str) node->str))
{
return 1;
}
if(strlen(p1->node->str) == strlen(p2->node->str)){
if(strcmp(p1->node->str,p2->node->str) <0){
return 1;
}
}
}
return 0;
}
struct TreeNode * qsort1(struct help *p, int n ,int k)
{
struct help h = p[0];
int i=0,j=n-1,index=0;
if(nstr);
}*/
return (p+i)->node;
}else if(i >(k-1)){
/*int j=0;for( j=0;jstr);
}
printf("--------- pre");*/
return qsort1(p,i,k);
}else{
/*int j=0;for( j=0;jstr);
}
printf("--------- back");*/
return qsort1(p+i+1,n-i-1,k-i-1);
}
}
void inorder(struct TreeNode *node, char *substr)
{
int *next = (int *)malloc(sizeof(int)*(strlen(substr)+1));
if(node == NULL){
return ;
}
inorder(node->left,substr);
int num =findSubNum(node->str,substr,next);
if(num>0){struct help h = {num,node};
pall[inde++] = h;}
//printf("%s %d
",node->str,num);
inorder(node->right,substr);
}
void getnext(char *str, int next[])
{
next[0] = next[1] = 0;
int length = strlen(str);
int i =0,j=0 ;
for( i = 1; i < length ; i++){
while(j>0&&(*(str+i)) != (*(str+j)))
j = next[j];
if((*(str+i)) == (*(str+j))) j++;
next[i+1] = j;
}
}
int findSubNum(char *str, char *substr,int next[])
{
getnext(substr,next);
int length = strlen(substr);
int i=0,j=0,num=0;
for(i = 0; i< strlen(str); i++)
{
while(j>0&&((*(str+i))!=(*(substr+j))))
j=next[j];
if((*(str+i))==(*(substr+j)) ) j++;
if(j == length){
num++;
j = next[j];
}
}
return num;
}
struct TreeNode *findNode(struct TreeNode *node, char *substr,int n){
inorder(node,substr);
/*printf("find node num %d
",inde);
int i=0;
for( i=0;istr);
}*/
qsort1(pall,inde,n);
}
int main()
{
struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1);
struct TreeNode *left = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1);
struct TreeNode *right = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1);
struct TreeNode *leftright = (struct TreeNode*)malloc(sizeof(struct TreeNode)*1);
root->left=left;
root->right =right;
left->left=NULL;
left->right=NULL;
right->left=NULL;
right->right=NULL;
left->right = leftright;
left->left = NULL;
leftright->right =NULL;
leftright->left =NULL;
leftright->str="abedf";
root->str="abced";
left->str="cbcab";
right->str="babefbaad";
char *substr = "ab";
/*struct help p1 = {2,root};
struct help p2 = {2,left};
struct help p3 = {3,right};
//printf("%d",com(&p1,&p2));
p[0]=p1;p[1]=p2;p[2]=p3;*/
printf("%s",findNode(root,substr,4)->str);
//printf("%s",s1.str);
return 0;
//inorder(root,substr);
}