首页 > 代码库 > 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语言编程题