摘要： 分析：那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图：然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作：p+(i/8)|(0x01<<(i%8)）当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：接 阅读全文

摘要： 【0/1背包问题】 在0/1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示选取物品i) 取得最大值。【输入文件】第一行一个数c，为背包容量。第二行一个数n，为物品数量第三行n个数，以空格间隔，为n个物品的重量第四行n个数，以空格间隔，为n个物品的价值【输出文件】能取得的最大价值。【分析】 初看这类问题，第一个想到的会是贪心，但是贪心法却无 阅读全文

摘要： 题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。分析：1.直接穷举。从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此方法与数组有序或者无序无关，时间复杂度为O(n)。View Code 1 #include <iostream.h> 2 3 bool Find2Num(int *data,int n,int sum,int &num1,int &num2) 4 { 5 if (NU 阅读全文

摘要： 方法一：从头扫描这个数组，每碰到一个正数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完 之后在数组的末尾有一个空位，这时把该正数放入这个空位。由于碰到一个正，需要移动O(n)个数字，因此总的时间复杂度是O(n２)，空间复杂度为O(1)。View Code 1 #include <iostream.h> 2 void fun1(int a[],int n) 3 { 4 if (n<1) 5 { 6 cout<<"input error!"<<endl; 7 return; 8 } 9 int num=0;10 .. 阅读全文

摘要： 1 #include <iostream.h> 2 3 struct BSTreeNode 4 { 5 int m_nValue; 6 struct BSTreeNode *m_pLeft; 7 struct BSTreeNode *m_pRight; 8 }; 9 10 void addBSTreeNode(BSTreeNode *&pCurrent,int value); //建立二叉排序树11 void inOrderBSTree(BSTreeNode *pBSTree); //中序遍历12 void convertToDoubleList(BSTreeNod... 阅读全文

摘要： Q1:查找一个整数数组中第二大的数View Code 1 const int MINNUMBER = -32767; 2 int find_sec_max(int data[],int count) 3 { 4 int maxnumber = data[0]; 5 int sec_max = MINNUMBER; 6 for(int i = 1;i < count; i++) 7 { 8 if(data[i] > maxnumber) 9 { 10 sec_max=maxnumber;11... 阅读全文

摘要： 目前以lib后缀的库有两种，一种为静态链接库(Static Libary，以下简称“静态库”)，另一种为动态连接库(DLL，以下简称“动态库”)的导入库(Import Libary，以下简称“导入库”）。 静态库是一个或者多个obj文件的打包，所以有人干脆把从obj文件生成lib的过程称为Archive，即合并到一起。比如你链接一个静态库，如果其中有错，它会准确的找到是哪个obj有错，即静态lib只是壳子。 动态库一般会有对应的导入库，方便程序静态载入动态链接库，否则你可能就需要自己LoadLibary调入DLL文件，然后再手工GetProcAddress获得对应函数了。有了导入库，你只需要链 阅读全文

摘要： Q：给出一个单向链表的头指针，输出该链表中倒数第K个节点的指针，链表的倒数第0个节点为链表的尾节点（尾节点的next成员为NULL） NODE* findnode(NODE *head,unsigned int k);思路：首先求出单向链表的长度为Len,然后从链表头指针开始遍历，一直遍历Len-1-K次就可以找到倒数第K个节点指针。 代码实现如下： 1 #include <iostream.h> 2 #include <assert.h> 3 4 typedef struct Node 5 { 6 int data; 7 struct Node *next; 8 }N 阅读全文

摘要： Q: 函数checkstr判断一字符串是不是对称的。其中msg为输入的字符串，对称返回0，不对称返回-1，实现该函数。int checkstr(const char *msg);代码实现如下： 1 #include <stdio.h> 2 #include <assert.h> 3 #include <string.h> 4 5 int checkstr(const char *msg) 6 { 7 int len=strlen(msg); 8 assert(msg!=NULL && len>1); 9 int low=0;10 int 阅读全文

摘要： 栈的操作主要有：入栈，出栈，返回栈顶元素，返回栈长度以及判断栈是否为空。 若用两个queue实现（可以定义成queue的数组queue q[2]），可以增加一个currentIndex来指向当前选中的queue。入栈操作可以直接把元素加到queue里，即 queue[currentIndex].push(element)，时间复杂度为O(1)，出栈操作要复杂一些，还是因为栈和队列元素的出入顺序不 同，处理方法是将size()-1个元素从q[currentIndex]转移到空闲队列q[(currentIndex + 1)%2]中，q[currentIndex]最后一个剩下的元素恰对应栈顶元素，. 阅读全文