Welcome to MDGSF's Blog!

This is my github blog

[C/C++] strncpy 库函数实现

2016-12-12

C/C++

C Strncpy

#include <stdio.h>
#include <string.h>

char * Mystrncpy(char * pcDest, char * pcSrc, size_t count)
{
    if(NULL == pcDest || NULL == pcSrc) {
        return NULL;
    }

    char * pcStart = pcDest;

    while (count && (*pcDest++ = *pcSrc++))
    {
        count--;
    }

    if(count != 0)
    {
        while (--count != 0)
        {
            *pcDest++ = '\0';
        }
    }

    return pcStart;
}

void vTest1()
{
    char acSrc[] = "hello world";
    char acDest[128] = {0};
    Mystrncpy(acDest, acSrc, sizeof(acDest));
    if(strcmp(acDest, acSrc) != 0)
    {
        printf("vTest1 failed\n");
    }

    printf("vTest1 pass\n");
}

void vTest2()
{
    char acSrc[] = "hello world";
    char acDest[128] = {0};
    char * pcDest = Mystrncpy(acDest, acSrc, sizeof(acDest));
    if(strcmp(pcDest, acSrc) != 0)
    {
        printf("vTest2 failed\n");
    }

    printf("vTest2 pass\n");
}

int main()
{
    vTest1();
    vTest2();
    return 0;
}

Read All

[C/C++] strcpy 库函数实现

2016-12-09

C/C++

C Strcpy

#include <stdio.h>
#include <assert.h>

//pcSrc 加上 const
//返回 pcDest,支持链式操作
char * MyStrcpy(char * pcDest, const char * pcSrc)
{
    //判断是否为NULL
    assert( (pcDest != NULL) && (pcSrc != NULL) );

    //判断是否重叠
    if(pcDest == pcSrc)
    {
        return pcDest;
    }

    char * pcAddr = pcDest;
    while ( *pcDest++ = *pcSrc++ )
    {
        ;
    }

    return pcAddr;
}

int main()
{
    printf("MyStrcpy\n");
    char ac[1024] = {0};
    MyStrcpy(ac, "Hello world");
    printf("ac = [%s]\n", ac);
    return 0;
}

Read All

[堆] topK--Maxheap

2016-12-09

mdgsf

Art

Question

在n个数中找出最小的k个数.

#include <stdio.h>

void vSwap(int & a, int & b)
{
    int t = a;
    a = b;
    b = t;
}

void MaxHeap(int heap[], int i, int len)
{
    if(NULL == heap || len <= 0)
    {
        return ;
    }

    int iLargeIndex = -1;
    int iLeft = i * 2;
    int iRight = i * 2 + 1;

    if(iLeft <= len && heap[iLeft] > heap[i])
    {
        iLargeIndex = iLeft;
    }
    else
    {
        iLargeIndex = i;
    }

    if(iRight <= len && heap[iRight] > heap[iLargeIndex])
    {
        iLargeIndex = iRight;
    }

    if(iLargeIndex != i)
    {
        vSwap(heap[i], heap[iLargeIndex]);
        MaxHeap(heap, iLargeIndex, len);
    }
}

void BuildHeap(int heap[], int len)
{
    if(NULL == heap || len <= 0)
    {
        return ;
    }

    int iIndex = len / 2;
    for (int i = iIndex; i>=1; i--)
    {
        MaxHeap(heap, i, len);
    }
}


int main()
{
    int n = 7;
    int k = 3;
    int ai[] = {0, 10, 12, 3, 4, 5, 6, 7};
    int iSize = 3;
    BuildHeap(ai, iSize);

    int i;
    for (i = 4; i <= 7; i++)
    {
        if(ai[i] < ai[1])
        {
            vSwap(ai[i], ai[1]);
            MaxHeap(ai, 1, k);
        }
    }

    for (i = 0; i <= 7; i++)
    {
        printf("%d ", ai[i]);
    }
    printf("\n");

    return 0;
}

Read All

[链表] 判断链表是否存在环

2016-12-09

mdgsf

Art

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

typedef struct _SLinkNode {
    int val;
    struct _SLinkNode * next;
}SLinkNode, *PSLinkNode;

PSLinkNode NewNode(int val)
{
    PSLinkNode newnode = (PSLinkNode)malloc(sizeof(SLinkNode));
    newnode->val = val;
    newnode->next = NULL;
    return newnode;
}

PSLinkNode createList(int ai[], int num)
{
    PSLinkNode head = NULL;
    PSLinkNode tail = NULL;
    for (int i = 0; i < num; i++)
    {
        PSLinkNode newnode = NewNode(ai[i]);
        if(head == NULL)
        {
            head = newnode;
            tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
    }
    return head;
}

void ShowList(PSLinkNode head)
{
    while(head != NULL)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

bool bExistsLoop(PSLinkNode head)
{
    PSLinkNode fast = head;
    PSLinkNode slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            break;
        }
    }

    return (fast == NULL || fast->next == NULL) ? false : true;
}

PSLinkNode FindLoopPort(PSLinkNode head)
{
    PSLinkNode fast = head;
    PSLinkNode slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            break;
        }
    }

    if (fast == NULL || fast->next == NULL)
    {
        return NULL;
    }

    slow = head;
    while (slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

int main()
{
    int ai[] = {1, 2, 3, 4, 5, 6, 7, 8};
    PSLinkNode list = createList(ai, 8);
    ShowList(list);

    PSLinkNode pCur = list;
    while (pCur->next != NULL)
    {
        pCur = pCur->next;
    }
    pCur->next = list->next;

    printf("%d\n", bExistsLoop(list));

    PSLinkNode pLoopPort = FindLoopPort(list);
    printf("%d\n", pLoopPort->val);

    return 0;
}

Read All

[基础] atoi

2016-12-07

mdgsf

Art

«编程之法» 学习

#include <stdio.h>
#include <ctype.h>
#include <string.h>

int StrToInt(const char * s)
{
    static const int MAX_INT = (int)((unsigned)~0>>1);
    static const int MIN_INT = -(int)((unsigned)~0>>1) - 1;

    if(NULL == s || strlen(s) <= 0)
    {
        return 0;
    }

    while (isspace(*s))
    {
        s++;
    }

    int iSign = 1;
    if(*s == '+' || *s == '-')
    {
        if(*s == '-')
        {
            iSign = -1;
        }
        s++;
    }

    unsigned int n = 0;
    while (isdigit(*s))
    {
        int c = *s - '0';
        if(iSign > 0 && (n > MAX_INT/10 || (n == MAX_INT/10 && c > MAX_INT % 10)))
        {
            return MAX_INT;
        }
        else if(iSign < 0 && (n > (unsigned)MAX_INT/10 || (n == (unsigned)MAX_INT/10 && c > (unsigned)MAX_INT % 10)))
        {
            return MIN_INT;
        }

        n = n * 10 + c;
        s++;
    }

    return (iSign > 0) ? n : -n;
}

void vTest(const char * pcCaseName, const char * s, int iExpectResult)
{
    int iRet = StrToInt(s);
    if(iRet == iExpectResult)
    {
        printf("%s: pass\n", pcCaseName);
    }
    else
    {
        printf("%s: failed\n", pcCaseName);
        printf("iRet = %d, iExpectResult = %d\n", iRet, iExpectResult);
    }
}

void vTest1()
{
    vTest("vTest1", "123", 123);
}

void vTest2()
{
    vTest("vTest2", "-123", -123);
}

void vTest3()
{
    vTest("vTest3", " 0123", 123);
}

void vTest4()
{
    vTest("vTest4", " -0123", -123);
}

void vTest5()
{
    vTest("vTest5", "  2147483647 ", 2147483647);
}

void vTest6()
{
    vTest("vTest6", "2147483648", 2147483647);
}

void vTest7()
{
    vTest("vTest7", "2147483646", 2147483646);
}

void vTest8()
{
    vTest("vTest8", "-2147483648", -2147483648);
}

void vTest9()
{
    vTest("vTest9", "-2147483649", -2147483648);
}

void vTest10()
{
    vTest("vTest10", "", 0);
}

void vTest11()
{
    vTest("vTest11", NULL, 0);
}

void vTest12()
{
    vTest("vTest12", "123abc", 123);
}

int main()
{
    vTest1();
    vTest2();
    vTest3();
    vTest4();
    vTest5();
    vTest6();
    vTest7();
    vTest8();
    vTest9();
    vTest10();
    vTest11();
    vTest12();
    return 0;
}

Read All

[链表] 判断一个链表是不是回文串

2016-12-07

mdgsf

Art

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

typedef struct _SLinkNode {
    int val;
    struct _SLinkNode * next;
}SLinkNode, *PSLinkNode;

PSLinkNode NewNode(int val)
{
    PSLinkNode newnode = (PSLinkNode)malloc(sizeof(SLinkNode));
    newnode->val = val;
    newnode->next = NULL;
    return newnode;
}

PSLinkNode createList(int ai[], int num)
{
    PSLinkNode head = NULL;
    PSLinkNode tail = NULL;
    for (int i = 0; i < num; i++)
    {
        PSLinkNode newnode = NewNode(ai[i]);
        if(head == NULL)
        {
            head = newnode;
            tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
    }
    return head;
}

void ShowList(PSLinkNode head)
{
    while(head != NULL)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

PSLinkNode getMiddle(PSLinkNode head)
{
    if(NULL == head)
    {
        return NULL;
    }

    PSLinkNode fast = head;
    PSLinkNode slow = head;
    while (fast->next != NULL && fast->next->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

PSLinkNode reverseList(PSLinkNode head)
{
    if(NULL == head || head->next == NULL)
    {
        return head;
    }

    PSLinkNode p3 = head;
    PSLinkNode p2 = head->next;
    PSLinkNode p1 = head->next->next;

    p3->next = NULL;
    p2->next = p3;
    while (p1 != NULL)
    {
        p3 = p2;
        p2 = p1;
        p1 = p1->next;

        p2->next = p3;
    }

    return p2;
}

bool bIsPalindrome(PSLinkNode head)
{
    if(NULL == head || head->next == NULL)
    {
        return true;
    }

    PSLinkNode middle = getMiddle(head);

    PSLinkNode right = reverseList(middle->next);

    while (right != NULL)
    {
        if(right->val != head->val)
        {
            return false;
        }

        right = right->next;
        head = head->next;
    }
    return true;
}

void vTest(const char * pcCaseName, int ai[], int num, bool bExpectResult)
{
    PSLinkNode list = createList(ai, num);
    ShowList(list);
    bool bRet = bIsPalindrome(list);
    if(bRet == bExpectResult)
    {
        printf("%s: pass\n", pcCaseName);
    }
    else
    {
        printf("%s: failed\n", pcCaseName);
    }
}

void vTest1()
{
    int ai[] = {1, 2, 3, 2, 1};
    int num = sizeof ai / sizeof ai[0];
    vTest("vTest1", ai, num, true);
}

void vTest2()
{
    int ai[] = {1, 2, 3, 4, 1};
    int num = sizeof ai / sizeof ai[0];
    vTest("vTest2", ai, num, false);
}

void vTest3()
{
    int ai[] = {1, 2, 2, 1};
    int num = sizeof ai / sizeof ai[0];
    vTest("vTest3", ai, num, true);
}

void vTest4()
{
    int ai[] = {1};
    int num = sizeof ai / sizeof ai[0];
    vTest("vTest4", ai, num, true);
}

void vTest5()
{
    int ai[] = {1, 2};
    int num = sizeof ai / sizeof ai[0];
    vTest("vTest5", ai, num, false);
}

int main()
{
    vTest1();
    vTest2();
    vTest3();
    vTest4();
    vTest5();
    return 0;
}

Read All

72/97