//在有序数组中找出某个数字的位置
#include<stdio.h>
int binarySearch(int a[] , int length,int object)
{
int head=0,mid=0;
int tail = length -1;
while(head<tail)
{
mid = (head+tail)/2;
if ( a[mid] > object)
tail = mid -1;
else if(a[mid]<object)
head = mid +1;
else
return mid;
}
return -1;
}
int main()
{
int array[] ={ 1,2,3 ,4 ,5, 6,7,8,9,10};
int result=binarySearch(array,sizeof(array),6);
printf("%d",result);
return 0;
}
//找出有序数组中出现某数字的次数
#include<stdio.h>
int count =0;
void binarySearch(int a[] , int head,int tail,int object)
{
if(head<=tail)
{
int mid = (head+tail)/2;
if (a[mid] == object)
{
count++;
binarySearch(a,head,mid-1,object);
binarySearch(a,mid+1,tail,object);
}
else if( a[mid] < object)
{
binarySearch(a,mid+1,tail,object);
}
else
{
binarySearch(a,head, mid-1,object);
}
}
}
int main()
{
int array[] ={ 1,2,2 ,2 ,2, 2,2,2,9,10};
binarySearch(array,0,sizeof(array)/4-1,2);
printf("%d",count);
return 0;
}
//求数组中最大子数组和
#include <stdio.h>
int MaxSum(int a[] ,int length)
{
int nStart = 0,nSum=0,i;
for(i=0; i < length; i++)
{
nStart = ( nStart+a[i] ) > a[i]? ( nStart+a[i] ) : a[i];
nSum = nStart>nSum? nStart:nSum;
}
return nSum;
}
int main()
{
int array[]={ 7,-9,8,7,-5,9,10,-20,9,-30,20,49,-50,-60};
int sum= MaxSum(array,sizeof(array)/4);
printf("%d",sum);
}
//求最长公共子序列
#include <stdio.h>
int MaxLength(char a[], char b[],int **c,int **back,int m,int n)
{
int i,j;
for (i=0;i<m;i++)
for(j=0;j<n;j++)
back[i][j] = 0;
for (i=0;i<m;i++) c[i][0] = 0;
for (j=0;j<n;j++) c[0][j] = 0;
for (i=1; i<m;i++)
for (j=1;j<n;j++)
{
if ( a[i]==b[j] )
{
c[i][j] = c[i-1][j-1] +1;
back[i][j] = 1;
}
else if( c[i-1][j] >= c[i][j-1] )
{
c[i][j] =c[i-1][j];
back[i][j] =2;
}
else
{
c[i][j] = c[i][j-1];
back[i][j] = 3;
}
}
return c[m -1][n -1];
}
void LCS(int i,int j, char *a, int **back)
{
if(i ==0 || j==0)
return;
if (back[i][j] == 1)
{
LCS(i-1,j-1,a,back);
printf("%c",a[i]);
}
else if(back[i][j] == 2)
{
LCS(i-1,j,a,back);
}
else
{
LCS(i,j-1,a,back);
}
}
int main()
{
char A[]="ACDWDYEZYXZXXABDYBZZ";
char B[] ="BYBZACDZYAXXXYZZ";
int **C = new int*[sizeof(A)];
for (int i=0;i<sizeof(A);i++)
C[i] = new int[sizeof(B)];
int **Back = new int*[sizeof(A)];
for(int i=0;i<sizeof(A);i++)
Back[i] =new int[sizeof(B)];
int length = MaxLength(A,B,C,Back,sizeof(A),sizeof(B));
printf("Max Common Length: %d\n",length);
printf("Common String: ");
LCS(sizeof(A)-1,sizeof(B)-1,A,Back);
printf("\nLength Array\n");
for(int i=0;i<sizeof(A);i++)
{
for(int j=0;j<sizeof(B);j++)
printf("%d ",C[i][j]);
printf("\n");
}
printf("TraceBack Array\n");
for(int i=0;i<sizeof(A);i++)
{
for(int j=0;j<sizeof(B);j++)
printf("%d ",Back[i][j]);
printf("\n");
}
}
//约瑟夫环
#include<stdio.h>
#include <stdlib.h>
typedef struct Node
{
int num;
struct Node *next;
}LinkList;
LinkList *create(int n)
{
LinkList *p,*q,*head;
p = (struct Node*)malloc(sizeof(Node));
p->num=1;
head =p;
q = p;
for(int i=2;i<=n;i++)
{
p= (struct Node*)malloc(sizeof(Node));
p->num =i;
q->next =p;
q=p;
}
p->next = head;
return head;
}
void Jonse(LinkList *&head,int m)
{
LinkList *p,*q,*s;
p=head;
while(p->next != p)
{
for(int i=1;i<m;i++)
{
q=p;
p=p->next;
}
printf("%d ",p->num);
s=p;
q->next=p->next;
p = p->next;
free(s);
}
printf("%3d",p->num);
}
void main()
{
LinkList *head;
int m,n;
printf("Enter the number of List: ");
scanf("%d",&m);
printf("\nEnter the internal of List: ");
scanf("%d",&n);
head = create(n);
Jonse(head,m);
}
//链表的倒置
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int num;
struct Node *next;
}LinkList;
LinkList *create(int n)
{
LinkList *p,*q,*head;
p = (struct Node*)malloc(sizeof(Node));
p->num=1;
head =p;
q = p;
for(int i=2;i<=n;i++)
{
p = (struct Node*)malloc(sizeof(Node));
p->num = i;
q->next =p;
q = p;
}
p->next = NULL;
return head;
}
void reverse(LinkList *&head)
{
LinkList *p,*q;
p = head->next;
q = p ->next;
head->next = NULL;
while( q != NULL)
{
p->next = head;
head =p;
p =q;
q = q->next;
}
p->next =head;
head =p;
}
void List(LinkList *head)
{
while(head != NULL)
{
printf("%3d",head->num);
head = head->next;
}
}
void main()
{
LinkList *head;
int n;
printf("Enter the length of the List: ");
scanf("%d",&n);
head = create(n);
printf("Before reverse : ");
List(head);
reverse(head);
printf("\nAfter reverse: ");
List(head);
}
//指针，字符串的理解
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main()
{
char *s =(char*)malloc(12); //这里需要为字符串指针申请内存空间
const char *sas= "we are the world\0";
printf("The length of string: %d\n",strlen(sas));
char *dd[] = { "we","are" ,"the","world","to be better","innocence","somebody","yesterday is history, tomorrow is mystery,but today is gift"};
char cc[10][10]={"we","are" ,"the","world","be better","innocence","somebody","yesterday"};
char (*CC)[10] =cc; //数组指针出场
printf("数组指针隆重出场: %s %s\n", CC,CC[0],CC[1]);
scanf("%s",s);
printf("%s",s);
printf("\n%s",sas);
for(int i=0;i<sizeof(dd)/4;i++) //指针数组，可以用sizeof求出数组的长度，指针的字节是4，所以需要除以4
{
printf("\n%s",dd[i]);
if(i==7)
{
printf("\n");
for(int j=0; j<20; j++) //这里不能使用sizeof(dd[7])，来获取长度，这里只能获取指针的长度
printf("%c",dd[i][j]);
}
}
for(int i=0; i<sizeof(cc);i++)
{
for(int j=0; j<sizeof(cc[10]);j++)
printf("%c",cc[i][j]);
printf("\n");
}
}
//字符串的快速排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int Partition(char **quicksort,int left,int right)
{
char *random = quicksort[left];
int l = left, r = right+1;
while (true)
{
while( (strcmp(quicksort[++l] , random)<0 ) && l<r) ;
while( strcmp(quicksort[--r],random) > 0 ) ;
if( l >= r)
break;
char temp[20]={};
strcpy(temp,quicksort[l]);
strcpy(quicksort[l],quicksort[r]);
strcpy(quicksort[r],quicksort[l]);
}
strcpy(quicksort[left],quicksort[r]);
strcpy(quicksort[r],random);
return r;
}
void QuickSort(char **quicksort ,int left,int right)
{
if(left < right)
{
int part = Partition(quicksort,left,right);
QuickSort(quicksort,left, part-1);
QuickSort(quicksort,part+1,right);
}
}
void main()
{
char *quicksort[ ] = {"me","he","who","she","what","new"};
QuickSort(quicksort, 0,sizeof(quicksort)/4-1);
for(int i=0;i<sizeof(quicksort)/4; i++)
printf("%s ",quicksort[i]);
}
//快速排序
#include <stdio.h>
#include <stdlib.h>
int Partition(int *sort,int left,int right)
{
int x=sort[left];
int l=left, r=right+1;
while(true)
{
while( sort[++l] < x && l < r) ;
while( sort[--r] > x ) ;
if( l >=r)
break;
int temp = sort[l];
sort[l] = sort[r];
sort[r] = temp;
}
sort[left] = sort[r];
sort[r] = x;
return r;
}
void QuickSort(int *sort,int left,int right)
{
if(left<right)
{
int part = Partition(sort,left,right);
QuickSort(sort,left,part-1);
QuickSort(sort,part+1,right);
}
}
void main()
{
int sort[] = {8,3,9,31,32,32,32,33,78,7,10,11,12};
QuickSort(sort, 0,sizeof(sort)/4-1);
for(int i=0;i<sizeof(sort)/4; i++)
printf("%d ",sort[i]);
}
#include <iostream>
using namespace std;
typedef struct Node
{
int num;
struct Node *next;
}LinkList;
typedef struct LinkQueue
{
LinkList *head, *tail;
}queue;
void insert(queue *Q, int m)
{
LinkList *p;
p = (Node*)malloc(sizeof(Node));
p->num = m;
p->next = NULL;
if(Q->tail == NULL)
{
Q->tail = p;
Q->head =p;
}
else
{
Q->tail->next =p;
Q->tail =p;
}
}
void del(queue *Q)
{
LinkList *p; int x;
if( Q->head == NULL)
{
cout<<"The Queue is Empty"<<endl;
}
else
{
x = Q->head->num;
cout<<x <<endl;
p = Q->head;
if (Q->head == Q->tail)
{
Q->head = NULL;
Q->tail = NULL;
}
else
{
Q->head = Q->head->next;
}
free(p);
}
}
void main()
{
queue *Q =(LinkQueue*)malloc(sizeof(LinkQueue));
Q->head = NULL;
Q->tail = NULL;
for(int i = 0 ; i <=10; i++)
insert(Q,i);
for(int i= 0; i <= 10; i++)
del(Q);
}
// 用链表实现的栈
#include <iostream>
#include <stdio.h>
#include <array>
#include <vector>
#include <list>
#include <map>
#include <hash_map>
#include <queue>
using namespace std;
typedef struct Node{
int num;
struct Node *next;
}LinkList;
typedef struct Stack{
LinkList *bottom, *top;
}stack;
void push(stack *S, int num)
{
LinkList *p;
p = (Node *)malloc(sizeof(Node));
p->num =num;
if(S->bottom == NULL)
{
S->bottom =p;
S->top =p;
p->next = NULL;
}
else
{
p->next = S->top;
S->top = p;
}
}
int pop(stack *S)
{
LinkList *p; int x;
if(S->bottom == NULL)
{
cout<< "The Stack is Empty"<<endl;
}
else
{
x = S->top->num;
cout<< x<<" ";
p = S->top;
if( S->top == S->bottom)
{
S->top = NULL;
S->bottom =NULL;
}
else
{
S->top = S->top->next;
}
free(p);
}
return x;
}
void main()
{
stack *S = (Stack *)malloc(sizeof(Stack));
S->bottom = NULL; S->top = NULL;
for(int i=0;i<=10;i++)
push(S,i);
for(int i=0;i<=10;i++)
pop(S);
}
//使用栈实现四则运算
#include<iostream>
#include <stack>
using namespace std;
void main()
{
stack<int> s_num;
stack<char> s_oper;
char *express =new char[100];
cout<<"Enter the expression:"<<endl;
cin>>express;
int sum=0, number1,number2;
int len = strlen(express);
for(int i=0;i < len; i++)
{
if(express[i] >= '0' && express[i] <='9')
sum = sum*10+(express[i] - '0');
else
{
if(express[i] ==' ')
continue;
s_num.push(sum);
sum=0;
if(express[i] =='=')
{
while(!s_oper.empty())
{
number1 = s_num.top();
s_num.pop();
number2 = s_num.top();
s_num.pop();
switch(s_oper.top())
{
case '+':
s_num.push(number2+number1);
break;
case '-':
s_num.push(number2-number1);
break;
case '*':
s_num.push(number2*number1);
break;
case '/':
s_num.push(number2/number1);
break;
default:
break;
}
s_oper.pop();
}
}
if(!s_oper.empty())
{
if(s_oper.top() =='*' || s_oper.top() == '/')
{
number1 = s_num.top();
s_num.pop();
number2 = s_num.top();
s_num.pop();
if(s_oper.top() =='*')
s_num.push(number2*number1);
else
s_num.push(number2/number1);
s_oper.pop();
}
}
switch(express[i])
{
case '+':
if(s_oper.empty())
s_oper.push('+');
else
{
number1 = s_num.top();
s_num.pop();
number2 = s_num.top();
s_num.pop();
if(s_oper.top() == '+')
s_num.push(number2+number1);
else
s_num.push(number2-number1);
s_oper.pop();
s_oper.push('+');
}
break;
case '-':
if(s_oper.empty())
s_oper.push('-');
else
{
number1 = s_num.top();
s_num.pop();
number2 = s_num.top();
s_num.pop();
if(s_oper.top() == '+')
s_num.push(number2+number1);
else
s_num.push(number2-number1);
s_oper.pop();
s_oper.push('-');
}
break;
case '*':
s_oper.push('*');
break;
case '/':
s_oper.push('/');
break;
default:
break;
}
}
}
cout<<"Sum is : "<< s_num.top()<<endl;
}
//两个栈实现队列的功能
#include <iostream>
#include <stack>
using namespace std;
template <class T>
struct Queue
{
void push(T &t)
{
s1.push(t);
}
T front()
{
if(s2.empty())
{
if(s1.size() == 0) throw;
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
void pop()
{
if(s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
if(!s2.empty())
s2.pop();
}
stack<T> s1;
stack<T> s2;
};
int main()
{
Queue<int> Q;
int i;
for ( i=0; i<10; ++i)
Q.push(i);
for(i=0;i<10;++i)
{
cout<< Q.front()<<endl;
Q.pop();
}
return 0;
}
//整数转换为字符串 itoa函数
#include <iostream>
using namespace std;
void main()
{
int m,i=0;
char temp[10], str[10];
cin>> m;
while(m != 0)
{
temp[i++] = m%10+'0';
m = m/10;
}
temp[i] ='\0';
str[i] ='\0';
int j=0;
while(temp[j] != '\0')
{
str[--i] = temp[j++];
}
for(i=0;i<=j;i++)
cout<<str[i];
}
//字符串转换为整数 atoi函数
#include <iostream>
using namespace std;
void main()
{
char *str=new char[10];
cin>>str;
int num=0;
int len = strlen(str);
for(int i=0;i<len;i++)
num = num*10 + (str[i] -'0');
cout<<num;
}
//字符串复制
#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;
char * strcpy(char *dest, const char *source)
{
assert((dest != NULL )&&(source != NULL));
char *address = dest;
while( *source != '\0')
*dest++ = *source++;
*dest ='\0';
return address;
}
void main()
{
char *source = "We are the World";
char *dest = new char[20];
char *address=strcpy(dest,source);
cout<<address<<endl;
}
//循环右移字符串n位
#include <iostream>
using namespace std;
void LoopMove(char *str,int steps)
{
int n= strlen(str) - steps;
char temp[100];
strcpy(temp, str+n);
strcpy(temp+steps,str);
*(temp+strlen(str)) = '\0';
strcpy(str,temp);
}
void LoopMove(char *str,int steps)
{
int n = strlen(str) - steps;
char temp[100];
memcpy(temp,str+n,steps);
memcpy(temp+steps,str,n);
memcpy(str,temp,n+steps);
}
void main()
{
char str[30]; //char *str = "I live in Guangzhou",str[i] ='m'; 默认指针指向常量，不可修改
int i;
for(i=0;i<9;i++)
str[i] =i+'0';
str[i]='\0';
LoopMove(str,4);
cout<<str<<endl;
}
//map结构记录字母或单词出现的次数, 还没实现根据value来排序。
#include <iostream>
#include <map>
#include <string.h>
using namespace std;
void main()
{
map<char,int> m ;
map<char,int>::iterator m_iter;
char *str = "Yesterday is history,tomorrow is mystery,but today is gift";
while(*str != '\0')
{
if(m[*str] >= 1)
m[*str]++;
else
m[*str] = 1;
str++;
}
for(m_iter = m.begin(); m_iter !=m.end(); m_iter++)
cout<<m_iter->first <<" :" <<m_iter->second <<" ";
map<string,int> word_map;
map<string,int>::iterator word_iter;
string bb[10]={"Yesterday","is","history","tomorrow","is","mystery","but","today", "is","gift"};
for (int i=0;i<10;i++)
{
if(word_map[bb[i] ] >=1)
word_map[ bb[i] ] ++;
else
word_map[bb[i]] = 1;
}
for(word_iter = word_map.begin(); word_iter !=word_map.end(); word_iter++)
cout << word_iter->first.c_str() <<" :" <<word_iter->second <<" ";
}
//qsort函数字符串的快速排序
#include <iostream>
using namespace std;
int comp( const void *A, const void *B)
{
return strcmp((char*)A, (char*)B);
}
int comp_num(const void *A, const void *B)
{
if(*((int*)A) >= *((int*)B) ) return 1;
else return -1;
}
void main()
{
const int row= 5;
const int col = 10;
char a[row][col] = { "hzhida", "is", "a ","diligent","man"};
qsort(a,row,sizeof(a[0]),comp);
for(int i=0;i<row;i++)
cout<<a[i] <<"\t";
int A[col] ={100,55,20,30,50,60,70,90,67,10};
qsort(A,sizeof(A)/sizeof(int),sizeof(int),comp_num);
for(int i=0;i<col;i++)
cout<<A[i] <<"\t";
}
//String 类
#include <iostream>
using namespace std;
class String
{
public:
String(const char* str = NULL); //普通构造函数
String(const String &other); //拷贝构造函数
~String(void); //析构函数
String & operator =(const String &other); // 赋值函数
void print();
private:
char *m_data;
};
String::String(const char *str )
{
if (str == NULL)
{
m_data = new char[1];
*m_data = '\0';
}
else
{
m_data = new char[strlen(str)+1];
strcpy(m_data, str);
}
}
String::~String(void)
{
delete m_data;
}
String::String(const String &other)
{
m_data = new char[strlen(other.m_data)+1];
strcpy(m_data, other.m_data);
}
String &String::operator=(const String &other)
{
if(this == &other)
return *this;
delete [] m_data;
m_data = new char[strlen(other.m_data) +1];
strcpy(m_data,other.m_data);
return *this;
}
void String::print()
{
cout<<m_data<<endl;
}
void main()
{
const char *m="long ago, in ancient China, the peakcock rule over the goldmen city";
String M(m); //普通构造函数
M.print();
String Z(M); //拷贝构造函数
Z.print();
String Y = M; //赋值函数
Y.print();
}
汉诺塔问题
#include <iostream>
using namespace std;
void TowerHanoi(int n,char x, char y, char z)
{
if(n)
{
TowerHanoi(n-1, x, z, y);
cout<< "Move top disk from: "<< char(x) <<" to: "<<char(y)<<endl;
TowerHanoi(n-1, z, y, x);
}
}
void main()
{
int n=0;
cout <<"input the level of tower: ";
cin>>n;
TowerHanoi(n, 'A','B','C');
}
#include <iostream>
using namespace std;
void TransferString(const char *pInputStr, long lInputLen,char *pOutputStr)
{
int i;
for(i=0; i<lInputLen;i++)
{
if( pInputStr[i] > 'A' && pInputStr[i] < 'V')
{
pOutputStr[i] = pInputStr[i] + (char)37;
}
else if(pInputStr[i] >= 'V' && pInputStr[i] <= 'Z')
{
pOutputStr[i] = pInputStr[i] + (char)11;
}
else
pOutputStr[i] = pInputStr[i];
}
pOutputStr[i] ='\0';
}
void main()
{
char *aa="Axs3mWss";
char *bb = new char[20];
TransferString(aa,strlen(aa),bb);
cout<<bb<<endl;
}
#include <iostream>
using namespace std;
void main()
{
char *aa = new char[100];
char *bb = new char[100];
cin>>aa;
int i;
for( i=0; i<strlen(aa); i++)
bb[strlen(aa) - i -1] = aa[i];
for(i=0; i<strlen(aa); i++)
{
if(aa[i] == bb[i])
continue;
else
{
cout<<"NO"<<endl;
break;
}
}
if( i == strlen(aa) )
cout<< "YES"<<endl;
}
#include <iostream>
using namespace std;
void main()
{
char *aa = new char[100];
cin>>aa;
int i;
for(i=0; i<strlen(aa)/2;i++)
{
if(aa[i] == (aa[strlen(aa) -i-1]))
continue;
else
{
cout<<"NO"<<endl;
break;
}
}
if( i == strlen(aa)/2)
cout<<"YES"<<endl;
}
View Code
