c_cpp,Code片段,代码实例,代码示例,代码片段库

c_cpp 将str转换为double

将str转换为double

str2double.c

#include <math.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool
is_digit(char c){
    return c >= '0' && c <= '9';
}

int
find(char *seq, char c){
    if (seq == NULL) 
        return -1;
    size_t len = strlen(seq);
    for (int i = 0; i < len; i++) {
        if (seq[i] == c) 
            return i;
    }
    return -1;
}

double
str2double(char *seq){
    assert(seq != NULL);

    double result = 0.0;

    bool is_negtive = false;
    bool has_integer = true;
    bool has_fraction = true;

    int start_pos = 0;
    size_t len = strlen(seq);

    if (seq[0] == '-'){ // negtive
        is_negtive = true;
        start_pos = 1;
    }
    int dot_pos = find(seq,'.');
    if (dot_pos == -1) {
        has_fraction = false;
        dot_pos = len;
    } else if ((is_negtive && dot_pos == 1) || (!is_negtive && dot_pos == 0))
        has_integer = false;
       
    if (has_integer){ 
        for (int i = dot_pos - 1; i >= start_pos; i--) { //handle integer part
            if (!is_digit(seq[i])) {
                printf("Wrong Format Integer\n");
                exit(-1);
            }
            result += (seq[i] - '0') * pow(10, dot_pos -1 - i);
        }
    }
    if (has_fraction) { // handle fraction part
       for (int i = dot_pos + 1; i < len; i++) {
           if (!is_digit(seq[i])) {
               printf("Wrong Format Fraction\n");
               exit(-1);
           }
           result += (seq[i] - '0') * pow(10, dot_pos - i);
       }
    }
    if (is_negtive) {
        result = -result;
    }
    return result;
}


int main(int argc, const char *argv[]) {
    char *str1 = "-.123456";
    char *str2 = "12345.123";
    char *str3 = "-654321.321";
    char *str4 = "-000654321.321";
    char *str5 = "123a4.12";
    printf("%f\n",str2double(str1));
    printf("%f\n",str2double(str2));
    printf("%f\n",str2double(str3));
    printf("%f\n",str2double(str4));
    printf("%f\n",str2double(str5));
    return 0;
}

c_cpp 求数字Ñ中1的个数

求数字Ñ中1的个数

NumberOf1.c

int number_of_1(int n){
    int count = 0;
    unsigned int flag = 1;
    while(flag){
        if(n & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}

//另一种解法
//一个整数减去1之后再和原来的整数做与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0
int number_of_1(int n){
    int count = 0;
    while(n){
        count++;
        n = (n-1)&n;
    }
    return count;
}

c_cpp 将一句话里的单词进行倒置，标点符号不倒置。比如一句话：我来自北京。倒置后变成：beijing。来自我

将一句话里的单词进行倒置，标点符号不倒置。比如一句话：我来自北京。倒置后变成：beijing。来自我

sentence_reverse.c

//解析：解决该问题可以分为两步：第一步全盘置换该语句成：.gnijieb morf emoc i。第二步进行部分翻转，如果不是空格，则开始翻转单词。
#include <iostream>
using namespace std;
 
int main ()
{
    int i=0, j=0,begin, end;
    char str[] = "i come from beijing.";
    char temp;
    j = strlen(str) - 1;
    //第一步是进行全盘翻转
    while(j>i)
    {
        temp = str[i];
        str[i++] = str[j];
        str[j--]=temp;
    }
    //第二步进行部分翻转
    i=0;
    while(str[i])
    {
        if(str[i] != ' ')
        {
            begin = i;
            while(str[i] && str[i] != ' ')
                i++;     //找到str[i]为空格符
            i = i - 1;    	//空格符回退一个
            end = i;
        }
        while(end > begin) //部分翻转
        {
            temp = str[begin];
            str[begin++] = str[end];
            str[end--] = temp;
        }
        i++; 
    }
    cout << "string:" << str << endl;
}

c_cpp 串的匹配算法和KMP算法

串的匹配算法和KMP算法

string_match.c

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

int str_match(char* S,int len_s,char* T,int len_t){
    int i =0,j=0;
    while(i<len_s && j<len_t){
        if(S[i] == T[j]){
            ++i;
            ++j;
        }else{
            i = i - j + 1;
            j = 0;
        }
    }
    if(j > len_t -1)
        return i - len_t;
    else
        return 0;
}

c_cpp tuple_explode.cpp

tuple_explode.cpp

/*

La primera idea que se me vino a la mente para
http://channel9.msdn.com/Events/GoingNative/2013/The-Way-of-the-Exploding-Tuple

No recomendaria su uso, pero es otra forma de atacar al reto.

*/
#include <cstring>
#include <tuple>
#include <type_traits>
#include <iostream>

template <unsigned... Nums>
struct stat_seq { };

template <unsigned... Nums>
struct stat_seq_builder;

template <unsigned... Nums>
struct stat_seq_builder<0, Nums...> {
	typedef stat_seq<0, Nums...> type;
};

template <unsigned I, unsigned... Nums>
struct stat_seq_builder<I, Nums...>
	: stat_seq_builder<I - 1, I, Nums...> { };

template <typename Func, typename... Ts, unsigned... Nums>
auto explode_helper(Func&& f, const std::tuple<Ts...>& tup, stat_seq<Nums...>)
	-> typename std::result_of<Func (Ts...)>::type
{
	return f(std::get<Nums>(tup)...);
}

template <typename Func, typename... Ts>
auto explode(Func&& f, const std::tuple<Ts...>& tup)
	-> typename std::result_of<Func (Ts...)>::type
{
	return explode_helper(std::forward<Func>(f), tup,
			typename stat_seq_builder<sizeof...(Ts) - 1>::type());
}

int f(int a, double b, const char* c) {
	return a + (int)b + std::strlen(c);
}

int main() {
	auto t1 = std::make_tuple(1, 4.2, "hello");
	
	std::cout << explode(f, t1) << std::endl;
}

c_cpp 四皇后问题

四皇后问题

Trial.c

//============================================================================
// Name        : test.cpp
// Author      : will
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

#define n 4

int arr[n][n];

int isLegal(){
	int i,j,
		sum1 =0,	//列和
		sum2 =0,	//行和
		sum3 =0,        //斜行和
		sum4 =0;        //反斜行和
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			sum1 += arr[j][i];
			sum2 += arr[i][j];
			if(i==j)	sum3 += arr[i][j];
			if(i+j==n-1)	sum4 += arr[i][j];
		}
		if(sum1>1||sum2>1)
			return 0;
		sum1=0;
		sum2=0;
	}
	if(sum3>1||sum4>1)
		return 0;

	return 1;
}

void print(){
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			printf("%d ",arr[i][j]);
		}
		printf("\n");
	}
	printf("----------\n");
}

void Trial(int i){
	int j;
	if(i>=n)
		print();
	else{
		for(j=0;j<n;j++){
			arr[i][j] = 1;
			if(isLegal())
				Trial(i+1);
			arr[i][j] = 0;
		}
	}
}

int main(void)
{
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			arr[i][j] = 0;
		}
	}
	Trial(0);
	return EXIT_SUCCESS;
}

c_cpp 递增排序的数组（元素不重复），旋转一定长度后，求数组中最小的数。如{1,2,3,4,5,6}，旋转后{4,5,6,1,2， 3}，旋转后的数组最小值为1

递增排序的数组（元素不重复），旋转一定长度后，求数组中最小的数。如{1,2,3,4,5,6}，旋转后{4,5,6,1,2， 3}，旋转后的数组最小值为1

findMin.c

//============================================================================
// Name        : test.cpp
// Author      : will
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

/*
 * left指向前面递增数组的元素，right指向后面递增数组的元素
 */
int findMin(int arr[],int n){
  	if(arr == NULL || n <= 0){
		return -1;
	}
	int left = 0;
	int right = n-1;
	int mid = left;		//mid初始化为0，如果数组有序，直接返回arr[0]
	while(arr[left] >= arr[right]){
		mid = (left+right)/2;
		if(right-left == 1){
			mid = right;
			break;
		}
		if(arr[mid] >= arr[left]){
			left = mid;
		}else if(arr[mid] <= arr[right]){
			right = mid;
		}
	}
	return arr[mid];
}



/*
 * 如果遇到{0,1,1,1,1}这样数组，旋转之后的数组{1,0,1,1,1}，
 * 中间的判断中会出现left，right，mid位置的元素都一样，
 * 这时候无法判断出来mid元素位于前面的递增数组还是位于后面的递增数组，这时候，只能顺序查找
 */
int findMin(int arr[],int n){
	if(arr == NULL || n <= 0){
		return -1;
	}
	int left = 0;
	int right = n-1;
	int mid = left;		//mid初始化为0，如果数组有序，直接返回arr[0]
	while(arr[left] >= arr[right]){
		mid = (left+right)/2;
		if(right-left == 1){
			mid = right;
			break;
		}
		//如果left，right，mid三个元素的值相同，就判断不了当前的递增关系，因此只能顺序查找
		if(arr[mid]==arr[left] && arr[mid]==arr[right]){
			int result = arr[left],i;
			for(i=left+1;left<=right;i++){
				if(result > arr[i])
					result = arr[i];
			}
			return result;
		}
		if(arr[mid] >= arr[left]){
			left = mid;
		}else if(arr[mid] <= arr[right]){
			right = mid;
		}
	}
	return arr[mid];
}

c_cpp 根据二叉树的前序和中序求后序

根据二叉树的前序和中序求后序

createTreeByPreorderAndInorder.c

//============================================================================
// Name        : test.cpp
// Author      : will
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

typedef struct BinaryTreeNode_{
  int value;
	BinaryTreeNode_* left;
	BinaryTreeNode_* right;
}BinaryTreeNode;

BinaryTreeNode* create(int* pre_start,int* pre_end,int* in_start,int* in_end){
	int root_value = pre_start[0];
	BinaryTreeNode* root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	root->value = root_value;
	root->left = root->right = NULL;

	//root只有left的时候
	if(pre_start == pre_end){
		if(in_start == in_end && *pre_start == *in_start){
			return root;
		}else{
			printf("input is invalid");
			return NULL;
		}
	}

	//求得中序中root的位置
	int* in_root = in_start;
	while(in_root <= in_end && *in_root != root_value){
		++in_root;
	}

	//root只有left的时候
	if(in_root == in_end && *in_root != root_value){
		printf("input is invalid");
		return NULL;
	}

	int left_len = in_root - in_start;

	if(left_len > 0){
		root->left = create(pre_start+1,pre_start+left_len,in_start,in_root-1);
	}
	if(left_len < pre_end - pre_start){
		root->right = create(pre_start+left_len+1,pre_end,in_root+1,in_end);
	}

	return root;
}

BinaryTreeNode* createTree(int* preorder,int* inorder,int len){
	if(preorder == NULL || inorder ==NULL || len <= 0){
		return NULL;
	}
	return create(preorder,preorder+len-1,inorder,inorder+len-1);
}

void postOrder(BinaryTreeNode* root){
	if(root){
		if(root->left){
			postOrder(root->left);
		}
		if(root->right){
			postOrder(root->right);
		}
		printf("%d ",root->value);
	}
}

int main(void)
{
	int a[] = {1,2,4,7,3,5,6,8};
	int b[] = {4,7,2,1,5,3,8,6};

	BinaryTreeNode* root = createTree(a,b,8);
	postOrder(root);
	return EXIT_SUCCESS;
}

c_cpp 单链表的快速排序

单链表的快速排序

linklist_sort.c

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

typedef struct ListNode* List;

struct ListNode
{
    int key;
    List     next;
};

void QuickSort( List head, List tail )
{
  if ( head->next == tail || head->next->next == tail )
		return;

	List mid = head->next;
	List p = head;
	List q = mid;
	int pivot = mid->key;
	List t = mid->next;

	while ( t != tail )
	{
		if ( t->key < pivot )
			p = p->next = t;
		else
			q = q->next = t;
		t = t->next;
	}
	p->next = mid;
	q->next = tail;

	QuickSort( head, mid );
	QuickSort( mid, tail );
}
void print_list(List head) {
    struct ListNode *p;
    for (p = head; p != NULL; p = p->next) {
        printf("%d ", p->key);
    }
    printf("\n");
}

int main(void) {
    List head;
    struct ListNode* p;
    int i = 0;
    /**
    * 初始化链表
    */
    head = (List)malloc(sizeof(struct ListNode));
    head->next = NULL;
    head->key = 0;
    srand((unsigned)time(NULL));
    for (i = 1; i < 11; ++i) {
        p = (struct ListNode*)malloc(sizeof(struct ListNode));
        p->key = rand() % 100 + 1;
        p->next = head->next;
        head->next = p;
    }

    print_list(head);
    printf("---------------------------------\n");
    QuickSort(head,NULL);
    print_list(head);
    return 0;
}

c_cpp 堆排序

堆排序

heap_sort.c

void swap( int arr[], int x, int y){
      int tmp = arr[x];
      arr[x] = arr[y];
      arr[y] = tmp;
}

//该操作主要用于维持堆的基本性质。
//假定以RIGHT(t)和LEFT(t)为根的子树都已经是堆，然后调整以t为根的子树，使之成为堆。
void heapify( int arr[], int size, int t){
      int left = 2*(t+1)-1;
      int right = 2*(t+1);

      //find max element
      int max = t;
      if(left < size){
            max = arr[left] > arr[max] ? left : max;
      }
      if(right < size){
            max = arr[right] > arr[max] ? right : max;
      }

      //调整后，重新维持堆
      if(max != t){
            swap(arr,t,max);
            heapify(arr,size,max);
      }
}

/**
 * 该操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），
 * 然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。
 */
void buildHeap( int arr[], int size){
      for(int i = size/2-1;i>=0;i--){
            heapify(arr,size,i);
      }
}

void heap_sort(int arr[],int size){
    buildHeap(arr,size);
    for(int i=size-1;i>0;i--){
        swap(arr,0,i);
        size--;
        heapify(arr,size,0);
    }
}