首页 > 代码库 > C语言编程题

C语言编程题

1、递归

汉诺塔是由三根杆子A,B,C组成的。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。
要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?

void MoveHanoi(int iCnt, char* pSrc, char* pMid, char* pDest){    if (iCnt == 1)    {        printf(" %s->%s\n", pSrc, pDest);    //当iCnt只有1个的时候直接从src移动到dest        }    else    {        MoveHanoi(iCnt - 1, pSrc, pDest, pMid);            //将src上iCnt-1个通过dest移动到mid        printf(" %s->%s\n", pSrc, pDest);//将src上最后一个移动到dest        MoveHanoi(iCnt - 1, pMid, pSrc, pDest);            //将mid上iCnt-1个通过src移动到dest    }}

有一对刚出生的小兔子,两个月后会生一对小兔子,以后每个月又要生一对小兔子。在没有死亡的情况下,问第n个月后总共有多少对兔子?
实际上每个月兔子的对数是一个斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55……

unsigned RabitBirth(unsigned uMounths){    if (uMounths <= 1)        return 1;    else        return RabitBirth(uMounths - 1) + RabitBirth(uMounths - 2);}

//判断一个数组是否为递增

bool JudgeIncre(int ary[], unsigned uSize)//uSize>=2{    if (uSize == 2)    {        return ary[1] > ary[0];    }    else    {        if (ary[uSize - 1] >= ary[uSize - 2])            return JudgeIncre(ary, uSize - 1);        else            return false;    }}

2、排序

快速排序,思想:分区 + 对分好的区进行递归操作
分区就是从数组中取出一个数,然后以这个数为轴心,将所有小于这个数的数放到其左边,将所有大于这个数的数放到其右边.
对这个数组分区完成之后再分别对左边、右边区域进行分区,递归结束后排序完成.

void swap(int *a, int *b){    int  tmp = *a;    *a = *b;    *b = tmp;}//对ary进行分区:以ary[0]为轴心数,将比轴心数小的和大的分别放到其左右两侧,返回轴心数左边数字个数int partition(int *ary, int iLen){    const int iPivotPos = 0;//以ary[0]为轴心数    int iPivotNum = ary[iPivotPos];//轴心数    int iLeftLen = 0;//保存比轴心数小的数字个数    swap(&ary[iPivotPos], &ary[iLen - 1]);//将轴心数放置最右侧    //将所有的数与轴心数对比,如果比轴心数小的话就往左边顺序排放    for (int i = 0; i < iLen-1; i++)    {        if (ary[i] < iPivotNum)        {            if(ary[i] != ary[iLeftLen])                swap(&ary[i], &ary[iLeftLen]);            iLeftLen++;        }    }    //将轴心数从最右侧放置轴心位置    if(iLeftLen != iLen - 1)        swap(&ary[iLeftLen], &ary[iLen - 1]);    return iLeftLen;}void quick_sort(int *ary, int iLen){    //个数为0或1终止递归    if (iLen == 1 || iLen == 0)        return;    //对ary进行分区:将比ary[0]小的和大的分别放到其两侧    int iLeftLen = partition(ary, iLen);    //对两侧的区域再进行分区    quick_sort(ary, iLeftLen);    iLeftLen++;//加上轴心数    if (iLeftLen != iLen)        quick_sort(&ary[iLeftLen], iLen - iLeftLen);}

冒泡法排序:将十个数里边最大(小)的放到右边(两两比较,将大(小)的换到右边),.......,将两个数里边最大(小)的放到右边(两两比较,将大(小)的换到右边)

void bubble_sort(int* ary, int iLen, bool bIncreaseOrder = true){    for (int i = 0; i < iLen - 1; i++)    {        for (int j = 0; j < iLen- 1 - i; j++)        {            if (bIncreaseOrder)            {                if (ary[j] > ary[j + 1])                    swap(&ary[j], &ary[j + 1]);            }            else            {                if (ary[j] < ary[j + 1])                    swap(&ary[j], &ary[j + 1]);            }        }    }}

选择法排序:将十个数里边最小(大)的放到左边(遍历右边9个数获得最小(大)数的索引,将找到的最小(最大)数换到第一个数),.......,将两个数里边最小(大)的放到左边(遍历右边1个数获得最小(大)数的索引,将找到的最小(最大)数换到第九个数)

void select_sort(int* ary, int iLen, bool bIncreaseOrder = true){    for (int i = 0; i < iLen - 1; i++)    {        int iLargeIndex = i;        for (int j = i+1; j < iLen; j++)        {            if (bIncreaseOrder)            {                if (ary[j] < ary[iLargeIndex])                    iLargeIndex = j;            }            else            {                if (ary[j] > ary[iLargeIndex])                    iLargeIndex = j;            }        }        if (iLargeIndex != i)            swap(&ary[i], &ary[iLargeIndex]);    }}

3、字符串处理

实现字符串处理strstr():
对pStr逐字与pSubStr比较,eg:
A B C D E F
C D
pStr中第一个就不同,跳过第一个不再考虑

A B C D E F
C D
pStr中第二个也不同,跳过第二个不再考虑

A B C D E F
C D
pStr中有相同的,进行处理

char* MyStrstr(char* pStr, char* pSubStr){    //assert(pStr && pSubStr);    char*pStrAdvance = pStr;    while (*pStrAdvance)    {        char* p = pStrAdvance, *q = pSubStr;        while (*p && *q)        {            if (*p == *q)            {                p++;                q++;            }            else                break;        }        if (!*q)            return pStrAdvance;        pStrAdvance++;    }    return NULL;}

4、链表问题

//链表节点结构typedef struct node{    int iIndex;    struct node* pNext;}Node, *NodePtr;//创建链表NodePtr CreateList(unsigned iLen){    NodePtr pHeadNode = NULL, pLastNode = NULL;    for (unsigned i = 0; i < iLen; i++)    {        NodePtr pNode = new Node;        pNode->iIndex = i;        if (pLastNode)            pLastNode->pNext = pNode;        else            pHeadNode = pNode;                    pLastNode = pNode;    }    pLastNode->pNext = NULL;    return pHeadNode;}//输出链表void PrintList(NodePtr pHeadNode){    NodePtr pNode = pHeadNode;    do     {        cout << pNode->iIndex << ", ";        pNode = pNode->pNext;    } while (pNode);    cout << endl;}//链表逆序:定义三个节点指针分别指向前三个节点,第二个节点的pNext重新指向第一个节点,三个节点指针再往后移动,如此往复NodePtr TurnList(NodePtr pHeadNode){    if (pHeadNode->pNext)    {        NodePtr pLastNode = pHeadNode;        NodePtr pNode = pLastNode->pNext;        NodePtr pNextNode = pNode->pNext;        while (pNextNode)        {            pNode->pNext = pLastNode;            pLastNode = pNode;            pNode = pNextNode;            pNextNode = pNextNode->pNext;        }        pNode->pNext = pLastNode;        pHeadNode->pNext = NULL;        return pNode;    }    else        return pHeadNode;}//链表排序:利用选择排序法思想void SelectSortList(NodePtr pHeadNode){    NodePtr pNode = pHeadNode;    while (pNode->pNext)    {        NodePtr pNodeMin = pNode;        NodePtr pNodeNext = pNode->pNext;        while (pNodeNext)        {            if (pNodeNext->iIndex < pNodeMin->iIndex)                pNodeMin = pNodeNext;            pNodeNext = pNodeNext->pNext;        }        if (pNodeMin != pNode)            swap(&pNode->iIndex, &pNodeMin->iIndex);        pNode = pNode->pNext;    }}//合并两个有序链表为一个NodePtr UnionList(NodePtr pHeadNode1, NodePtr pHeadNode2){    NodePtr pHeadNode = new Node;//新的链表添加一个头结点    NodePtr pNode1 = pHeadNode1, pNode2 = pHeadNode2, pNode = pHeadNode;    while (pNode1 && pNode2)    {        if (pNode1->iIndex <= pNode2->iIndex)        {            pNode->pNext = pNode1;            pNode = pNode->pNext;            pNode1 = pNode1->pNext;        }        else        {            pNode->pNext = pNode2;            pNode = pNode->pNext;            pNode2 = pNode2->pNext;        }    }    pNode->pNext = pNode1 ? pNode1 : pNode2;//插入剩余段    NodePtr pReturnNode = pHeadNode->pNext;    delete pHeadNode;//删除新链表的头结点    return pReturnNode;}

 

C语言编程题