不知有晋

ADT Tree
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai,aj> | ai, aj∈D, i=1,2,…,n, j=1,2,…,n，其中每个元素只有一个前驱节点 ，可以有零个或多个后继节点，有且仅有一个元素（根节点）没有前驱节点 }
数据操作：
    (1) treeSeq * InitTree();                              //构造一个空的树t      
    (2) DestroyTree(treeSeq *t);                           //释放树t占用的内存空间      
    (3) Parent(treeSeq *t);                                //求t所指节点的双亲结点      
    (4) Sons(treeSeq *t);                                  //求t所指节点的子孙节点      
    ... ...
}

#define MaxSize 50
typedef int ElemType;

typedef struct
{
    ElemType date;
    int parent;
} PTree[MaxSize];

#define MaxSize 50
typedef struct node
{
    ElemType date;
    struct node *sone[MaxSize];
} TSonNode;

typedef int ElemType;
typedef struct tnode·
{
    ElemType date;      //节点的值
    struct tnode *hp;   //指向兄弟
    struct tnode *vp;   //指向孩子节点
}TSBNode;

#include <stdio.h>

int minSubArrayLen(int s, int* nums, int numsSize);

int main()
{
    int s = 3,numsSize = 2;
    int nums[2] = {1,1};
    int length = minSubArrayLen( s, &nums[0],  numsSize);
    printf("长度最小的子数组长度length=%d",length);
    return 0;
}

int minSubArrayLen(int s, int* nums, int numsSize)
{
    int length = numsSize;  

    for(int i=0;i<numsSize;i++)
    {    
        int sum = 0,tmpLength = 0,j;
        
        for(j=i;j<numsSize && sum<s;j++)
        {
            sum += nums[j];
            tmpLength++;
        }
        
        if(sum < s)
        {
            if(i == 0) return 0;   
            else break; 
        }

        if(tmpLength < length) length = tmpLength;
        printf("i=%d,j=%d,tmpLength=%d,sum=%d\n",i,j,tmpLength,sum);
    }

    return length;
}

#include <stdio.h>

int bf(char *s,char *t);

int main()
{
    char s[] = "[Done] exited with code=0 in 0.454 seconds";
    char t[] = "Done";
    int index = bf(&s[0],&t[0]);
    printf("index=%d\n",index);
    return 0;
}

int StrLength(char *s)
{
    int i = 0;
    while(*(s+i) != '\0')
        i++;
    
    return i;
}

//  Brute-Force算法 
int bf(char *s,char *t)
{
    int sLength = StrLength(s);
    int tLength = StrLength(t);
    if(sLength < tLength) return -1;
    int si = 0,ti = 0;
    while (si+tLength <= sLength)
    {
        int flag = 1;
        for(ti=0;ti<tLength;ti++)
            if(*(s+si+ti) != *(t+ti))
            {
                flag = 0;
                break;
            }

        if(flag)
            return si;
        else
        {
            ti = 0;
            si++;
        }
    }

    return -1;
}

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
typedef int bool;


typedef struct node
{
    char data;
    struct node *next;
} strLink;

strLink * StrAssign(char *s);
bool isPalindrome(char * s);
void DispStr(strLink * s);
bool isPalindrome(char * s);
char GetChar(char c);
void StrCopy(strLink *str,int length,char *s);
void DispArr(char *arr,int length);

int main()
{
    char s[] = "";
    if(isPalindrome(&s[0]))
    {
        printf("true\t");
    }else
    {
        printf("false\t");
    }
    
    return 0;
}

char GetChar(char c)
{
    char res='\0';
    if((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') )
        res = c;
    
    if(c >= 'A' && c <= 'Z')
        res = c + 32;

    return res;
}

int StrLength(strLink *s)
{
    strLink * tmp = s->next;
    int i = 0;
    while(tmp != NULL)
    {
        i++;
        tmp = tmp->next;
    }
    return i;
}

strLink * StrAssign(char *s)
{
    strLink *tmp,*r,*p;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    r = tmp;
    int i = 0;
    while(s[i] != '\0')
    {
        char res;
        if((res = GetChar(s[i])) == '\0')
        {
            i++;
            continue;
        }

        p = (strLink *)malloc(sizeof(strLink));
        p->data = res;
        r->next = p;
        r = p;
        i++;
    }
    r->next = NULL;
    return tmp;
}

void DispStr(strLink *s)
{
    strLink *tmp = s->next;
    while(tmp != NULL)
    {
        printf("%c",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}
void DispArr(char *arr,int length)
{
    for(int i=0;i<length;i++)
    {
        printf("%c\t",*(arr+i));
    }
    printf("\n");
}

void StrCopy(strLink *str,int length,char *s)
{
    int i = 0;
    strLink * tmp = str->next;
    while(tmp != NULL)
    {
        *(s+i) = tmp->data;
        i++;
        tmp = tmp->next;
    }
}

bool isPalindrome(char * s)
{
    //  求出长度
    strLink *str;
    str = StrAssign(s);
    // DispStr(str);
    int length = StrLength(str);
    if(length <= 1) return true;
    char strArr[length];

    //  构造字符数组
    StrCopy(str,length,&strArr[0]);
    // DispArr(&strArr[0],length);

    //  验证
    int i=0,j=length-1;
    while(i < j)
    {
        if(strArr[i] != strArr[j])
            return false;
        i++;
        j--;
    }
    return true;
}

ADT String
{
数据对象：
	D = {ai | ai∈ElemType, i=1,2,…,n, n≧0 } //ElemType为类型标识符
数据关系：
	R = {<ai, ai+1> | ai, ai+1∈D, i=1,3,…,n-1 }
数据操作：
    (1) strSeq * InitStr();                                 //  初始化串
    (2) void StrAssign(strSeq *s,char cstr[]);              //  字符串常量cstr赋给串s
    (3) void DispStr(strSeq *s);                            //  输出串
    (4) strSeq * InsStr(strSeq *s,int i,strSeq *s1);        //  串插入
    (5) strSeq * StrCopy(strSeq *s);                        //  复制串s，返回新串
    (6) Bool StrEqual(strSeq *s,strSeq *t);                 //  串相等
    (7) int StrLength(strSeq *s);                           //  求串长
    (8) strSeq * Concat(strSeq *s,strSeq *t);               //  串连接
    (9) strSeq * SubStr(strSeq *s,int i,int j);             //  求子串
    (10) strSeq * DelStr(strSeq *s,int i,int j) ;            //  串删除
    (11) strSeq * RepStr(strSeq *s,int i,int j,strSeq *t);   //  串替换
}

#define MaxSize 100    
typedef struct
{   char data[MaxSize];         
    int length;                 
} strSeq;

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100          
#define true 1
#define false 0

typedef int Bool;
typedef struct
{   char data[MaxSize];         
    int length;                 
} strSeq;

strSeq * InitStr();                                 //  初始化串
void StrAssign(strSeq *s,char cstr[]);              //  字符串常量cstr赋给串s
void DispStr(strSeq *s);                            //  输出串
strSeq * InsStr(strSeq *s,int i,strSeq *s1);        //  串插入
strSeq * StrCopy(strSeq *s);                        //  复制串s，返回新串
Bool StrEqual(strSeq *s,strSeq *t);                 //  串相等
int StrLength(strSeq *s);                           //  求串长
strSeq * Concat(strSeq *s,strSeq *t);               //  串连接
strSeq * SubStr(strSeq *s,int i,int j);             //  求子串
strSeq * DelStr(strSeq *s,int i,int j) ;            //  串删去
strSeq * RepStr(strSeq *s,int i,int j,strSeq *t);   //  串替换


int main()
{
    strSeq *s,*s1,*s2,*s3,*s4,*s5;
    printf("串的基本运算如下:\n");
    printf("  (0)初始化串s:\n");
    s = InitStr();
    char cstr[] = "abcdefghijklmn";
    printf("  (1)字符串 %s 赋值给s\n",cstr);
    StrAssign(s,cstr);
    printf("  (2)输出串s:");
    DispStr(s);
    printf("  (0)初始化串s1:\n");
    s1 = InitStr();
    StrAssign(s1,"123");
    printf("  (2)输出串s1:");
    DispStr(s1);
    printf("  (3)串s的长度:%d\n",StrLength(s));
    printf("  (4)在串s的第9个字符位置插入串s1而产生串s2\n");
    s2 = InsStr(s,9,s1);
    printf("  (5)输出串s2:");
    DispStr(s2);
    printf("  (6)删除串s第2个字符开始的5个字符而产生串s2\n");
    s2 = DelStr(s,2,5);
    printf("  (7)输出串s2:");
    DispStr(s2);
    printf("  (8)将串s第2个字符开始的5个字符替换成串s1而产生串s2\n");
    s2 = RepStr(s,2,5,s1);
    printf("  (9)输出串s2:");
    DispStr(s2);
    printf("  (10)提取串s的第2个字符开始的10个字符而产生串s3\n");
    s3 = SubStr(s,2,10);
    printf("  (11)输出串s3:");
    DispStr(s3);
    printf("  (12)将串s1和串s2连接起来而产生串s4\n");
    s4 = Concat(s,s1);
    printf("  (13)输出串s4:");
    DispStr(s4);
    printf("  (14)复制串s返回s5\n");
    s5 = StrCopy(s);
    printf("  (15)输出串s5:");
    DispStr(s5);
    printf("  (16)比较串s和s5\n");
    if(StrEqual(s,s5))
        printf("  (17)串s和s5相等");
    else
        printf("  (17)串s和s5不相等");
    
    return 0;
}

strSeq * InitStr()
{
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    return tmp;
}

void StrAssign(strSeq *s,char cstr[])
{
    int i = 0;
    while (cstr[i] != '\0')
    {
        s->data[i] = cstr[i];
        i++;
    }
    s->length = i;
}

strSeq * InsStr(strSeq *s,int i,strSeq *s1)
{
    int j,k;
    strSeq *tmp  = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    i--;
    if(i < 0 || i > s->length)
        return tmp;
    if(s->length + s1->length > MaxSize)
        return tmp;

    for ( j = 0; j < i; j++)
        tmp->data[j] = s->data[j];
    for ( k = 0; k < s1->length; k++)
        tmp->data[j+k] = s1->data[k];    

    for ( j = i; j < s->length; j++)
        tmp->data[j+s1->length] = s->data[j];

    tmp->length = s->length + s1->length;
    return tmp;
}

void DispStr(strSeq *s)
{
    for (int i = 0; i < s->length; i++)
    {
        printf("%c ",s->data[i]);
    }
    printf("\n");
}


strSeq * Concat(strSeq *s,strSeq *t)
{
    int k,l;
    strSeq *tmp  = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    for(k=0;k<s->length;k++)
        tmp->data[k] = s->data[k];

    for(k=0;k<t->length;k++)
        tmp->data[s->length+k] = t->data[k];

    tmp->length = s->length + t->length;
    return tmp;
}


int StrLength(strSeq *s)
{
    return s->length;
}

strSeq * SubStr(strSeq *s,int i,int j)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    if(i+j-1 > s->length)
        return tmp;
    i--;
    for(k=i,l=0;l<j;l++,k++)
        tmp->data[l] = s->data[k];

    tmp->length = j;
    return tmp;
}

strSeq * RepStr(strSeq *s,int i,int j,strSeq *t)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    if(i+j-1 > s->length)
        return tmp;
    i--;
    for(k=0,l=0;k<i;k++,l++)
        tmp->data[l] = s->data[k];

    for(k=0;k<t->length;k++,l++)
        tmp->data[l] = t->data[k];

    for(k=i+j;k<s->length;k++,l++)
        tmp->data[l] = s->data[k];

    tmp->length = s->length-j+t->length;
    return tmp;
}

strSeq * DelStr(strSeq *s,int i,int j)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    //  元素数量不够，返回空
    if (i+j-1 > s->length)
        return tmp;
    i--;
    for ( k = 0,l = 0; k < i; k++,l++)
        tmp->data[l] = s->data[k];
    
    for ( k = i+j; k < s->length; k++,l++)
        tmp->data[l] = s->data[k];
    
    tmp->length = s->length-j;
    return tmp;
}

//  复制串s，返回新串
strSeq *StrCopy(strSeq *s)
{
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    for(int i=0;i<s->length;i++)
        tmp->data[i] = s->data[i];

    tmp->length = s->length;
    return tmp;
}

Bool StrEqual(strSeq *s,strSeq *t)
{
    if(s->length != t->length)
        return false;

    for(int i=0;i<s->length;i++)
        if(s->data[i] != t->data[i])
            return false;

    return true;
}

typedef struct node
{
    char data;
    struct node *next;
} strLink;  

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int Bool;
typedef struct node
{
    char data;
    struct node *next;
} strLink;

strLink * InitStr();                                    //初始化串
void StrAssign(strLink *s,char cstr[]);                 //字符串常量cstr赋给串s
void DispStr(strLink *s);                               //输出串
int StrLength(strLink *s);                              //求串长
strLink * InsStr(strLink *s,int i,strLink *t);          //串插入
strLink * DelStr(strLink *s,int i,int j);               //串删去
strLink * RepStr(strLink *s,int i,int j,strLink *t);    //串替换
strLink * SubStr(strLink *s,int i,int j);               //求子串
strLink * Concat(strLink *s,strLink *t);                //串连接
strLink * StrCopy(strLink *s);                          //复制串s，返回新串
Bool StrEqual(strLink *s,strLink *t);                   //判串相等

int main()
{
    strLink *s,*s1,*s2,*s3,*s4,*s5;
    printf("链串的基本运算如下:\n");
    printf("  (1)建立串s和串s1\n");
    s = InitStr();
    StrAssign(s,"abcdefghijklmn");
    printf("  (2)输出串s:");
    DispStr(s);
    s1 = InitStr();
    StrAssign(s1,"123");
    printf("  (2)输出串s1:");
    DispStr(s1);
    printf("  (3)串s的长度:%d\n",StrLength(s));
    printf("  (4)在串s的第9个字符位置插入串s1而产生串s2\n");
    s2 = InsStr(s,9,s1);
    printf("  (5)输出串s2:");
    DispStr(s2);
    printf("  (6)删除串s第2个字符开始的5个字符而产生串s2\n");
    s2=DelStr(s,2,5);
    printf("  (7)输出串s2:");
    DispStr(s2);
    printf("  (8)将串s第2个字符开始的5个字符替换成串s1而产生串s2\n");
    s2 = RepStr(s,2,5,s1);
    printf("  (9)输出串s2:");
    DispStr(s2);
    printf("  (10)提取串s的第2个字符开始的10个字符而产生串s3\n");
    s3 = SubStr(s,2,10);
    printf("  (11)输出串s3:");
    DispStr(s3);
    printf("  (12)将串s和串s1连接起来而产生串s4\n");
    s4 = Concat(s,s1);
    printf("  (13)输出串s4:");
    DispStr(s4);

    printf("  (14)复制串s返回s5\n");
    s5 = StrCopy(s);
    printf("  (15)输出串s5:");
    DispStr(s5);

    printf("  (16)比较串s和s5\n");
    if(StrEqual(s,s5))
        printf("  (17)串s和s5相等");
    else
        printf("  (17)串s和s5不相等");
    return 0;
}

strLink * InitStr()
{
    strLink *tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    return tmp;
}

void StrAssign(strLink *s,char cstr[])
{
    int i = 0;
    strLink *tmp,*p;
    p = s;
    while(cstr[i] != '\0')
    {
        tmp = (strLink *)malloc(sizeof(strLink));
        tmp->data = cstr[i];
        p->next = tmp;
        p = tmp;
        i++;
    }
    p->next = NULL;
}

void DispStr(strLink *s)
{
    strLink *tmp = s->next;
    while (tmp != NULL)
    {
        printf("%c ",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}

int StrLength(strLink *s)
{
    strLink *tmp = s->next;
    int i = 0;
    while (tmp != NULL)
    {
        i++;
        tmp = tmp->next;
    }
    return i;
}

strLink * InsStr(strLink *s,int i,strLink *t)
{
    strLink *tmp,*p1=s->next,*p2=t->next,*q,*r;
    int j;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    i--;    //  逻辑顺序转物理顺序
    if(i < 0 || i > StrLength(s))
        return tmp;

    r = tmp;
    for ( j = 0; j < i; j++)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }

    while(p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }
    for ( j = i; j < StrLength(s); j++)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }
    r->next = NULL;
    
    return tmp;  
}

strLink *DelStr(strLink *s,int i,int j)
{
    strLink *tmp,*r,*q,*p = s->next;
    int k=0;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i+j-1 > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
        k++;
    }

    while (k < i+j){
        p = p->next;
        k++;
    }
    
    while ( k < StrLength(s))
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;  
        k++;    
    }
    r->next = NULL;
    return tmp;
}


strLink *RepStr(strLink *s,int i,int j,strLink *t)
{
    strLink *tmp,*r,*q,*p1=s->next,*p2=t->next;
    int k = 0;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i+j-1 > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
        k++;
    }

    while (p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }

    while (k < i+j)
    {
        p1 = p1->next;
        k++;
    }

    while ( k < StrLength(s))
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;  
        k++;    
    }
    r->next = NULL;

    return tmp;   
}

strLink * SubStr(strLink *s,int i,int j)
{
    int k = 0;
    strLink *tmp,*p = s->next,*r,*q;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i-1+j > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        p = p->next;
        k++;
    }

    while (k < i+j)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
        k++;
    }
    r->next = NULL;
    return tmp; 
}

strLink * Concat(strLink *s,strLink *t)
{
    strLink *tmp,*r,*q,*p1 =s->next,*p2=t->next;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    r = tmp;
    while (p1 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }

    while (p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }
    r->next = NULL;
    return tmp;
}

//   复制串s，返回新串
strLink * StrCopy(strLink *s)
{
    strLink *tmp,*r,*q,*p1=s->next;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    r = tmp;
    while (p1 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }
    
    return tmp;
}

//  串相等
Bool StrEqual(strLink *s,strLink *t)
{
    strLink *p1=s->next,*p2=t->next;
    if(StrLength(s) != StrLength(t))
        return false;

    while (p1 != NULL)
    {
        if(p1->data != p2->data)
            return false;

        p1=p1->next;
        p2=p2->next;
    }
    return true;
}

#include <stdio.h>
#include <stdlib.h>

void bubble(int* arr, int arrSize);
int findBestValue(int* arr, int arrSize, int target);

int main()
{
    int arr[] = {4,9,3};
    int n = 3,target = 10;
    int value = findBestValue(&arr[0],n,target);
    printf("value=%d",value);
    return 0;
}
//  排序
void bubble(int* arr, int arrSize)
{
    for(int i=0;i<arrSize-1;i++)
    {
        int flag = 1;
        for(int j=arrSize-1;j>i;j--)
        {
            if(arr[j] < arr[j-1])
            {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = 0;
            }
        }
        if(flag == 1) break;
    }
}

int findBestValue(int* arr, int arrSize, int target)
{
    bubble(&arr[0],arrSize);
    int i,sum=0;

    for(i=0;i<arrSize;i++)
    {
        if(sum + arr[i]*(arrSize-i) > target) break;
        sum += arr[i];
    }

    if(i == arrSize) return arr[arrSize-1];

    int value = (target-sum)/(arrSize-i);
    double value_1 = (double)(target-sum)/(arrSize-i);
    if(value_1 - value > 0.5)
        return value+1;
    else
        return value;
}