标签为 "算法" 的存档

自制的Sqlcipher和OpenSSL framework的实战应用

  按照老传统首先得感谢一番,就把需要对我帮助过的部分参考给亮出来:

  1. sqlcipher配置 http://sqlcipher.net/ios-tutorial/
  2. sqlcipher API http://sqlcipher.net/sqlcipher-api/
  3. github上的sqlcipher https://github.com/sqlcipher/
  4. sqlcipher使用 http://jordy.easymorse.com/?p=970
  5. github上的sqlcipher测试 https://github.com/sqlcipher/SQLCipherSpeed
  6. 代替OpenSSL的官方代替库 Security.framework

阅读更多…

OpenSSL Framework for iOS 7(shell脚本)

  本文转自http://www.cppguru.com/12-openssl-framework-for-ios-7.html,看着是C++大牛,写了一个脚本编译iOS的framework,转一下,赞一个。
  Several OpenSSL build scripts can be found on the Internet. The distinctive feature of the following one is that it packs compiled libraries to XCode framework. The script has been polished to work with XCode 5.0.1 and targeted for i386 ARMv7 ARMv7s ARM64. You can download framework binaries or build OpenSSL yourself using the script.
阅读更多…

OpenSSL Framework for iOS 7(自制)

  对OpenSSL加密的研究,对于他的研究纯属于研究sqlite数据库加解密的副产品,因为sqlite加解密的一个开源库是基于OpenSSL的。
  打造framework就选用了 《ios static framework的制作笔记》 这个里面的工具,具体的操作转过去看看。
   阅读更多…

ios03_随机密码生成类

  最近做了一个密码生成器,就是能自动的生成密码,说一下自己设置的要求:
  1.密码总共可以选择包含大写字母、小写字母、数字和特殊字符四种字符。
  2.可以用户确定输入的位数
  3.保证当用户输入的密码位数小于用户选择的字符种类数时,密码的种类不能重复。如果用户选择4种字符类型,但是要求的位数是3位,那么输出的密码,字符的种类不能重复。
  遇到的重难点:
  1.要求3的实现,原来用的是switch,但是这是一个很错误的想法,switch的嵌套switch,写的很乱,最后想到了一种解决方法。用for循环+标记法来实现,OK!
  2.随机问题,原来我用的是C语言种的种子随机,结果发现,产生的密码是以秒为单位的,一秒之内的密码都一样,我就用了OC中的arc4random进行随机,也不需要种种子,比较爽!

  头文件如下:

#import <Foundation/Foundation.h>


@interface PWCreate : NSObject {

}

-(char)charAtIndex:(int)index;
-(unsigned int)randMaked;
-(char)upper;
-(char)lower;
-(char)number;
-(char)special;
-(NSString*)Creat:(int)switchSum:(int)count;
@end

实现代码:

#import "PWCreate.h"


@implementation PWCreate
-(unsigned int)randMaked
{
	return arc4random();
}
-(char)upper
{	
	return 65 + [self randMaked] % 26;
}
-(char)lower
{
	return 97+[self randMaked]%26;
}
-(char)number
{
	return 48+[self randMaked]%10;
}
-(char)special;
{
	char a[]="!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";
	return a[[self randMaked]%32];
}
-(char)charAtIndex:(int)index
{
	switch (index) {
		case 0:
			return [self upper];
			break;
		case 1:
			return [self lower];
			break;
		case 2:
			return [self number];
			break;
		case 3:
			return [self special];
			break;
	}
}
-(NSString*)Creat:(int)switchSum:(int)count
{
	int location,i,j; //记录随机的位置用
	BOOL flag[4]={0,0,0,0}; //标记位置是否用
	int switchSumFlaged=0;   //判断是否和switchSum一样
	BOOL flagAll = NO;   //是否每个选择过的值都有值
	char ch;
	NSMutableString* str=[[NSMutableString alloc] initWithCapacity:10];
	for(i=0,j=0;j<count;i++)
	{
		if (flagAll) {
			location=[self randMaked]%4;
			if((1<<location) & switchSum)
			{
				ch=[self charAtIndex:location];
				//printf("1.%c\n",ch);
				[str appendFormat:@"%c",ch];
				j++;
			}
		}
		else {
			location=[self randMaked]%4;
			if(((1<<location)&switchSum) && !flag[location])
			{
				flag[location]=YES;
				switchSumFlaged += (1<<location);
				if (switchSum == switchSumFlaged) {
					flagAll = YES;
				}
				ch=[self charAtIndex:location];
				//printf("2.%c\n",ch);
				[str appendFormat:@"%c",ch];
				j++;
			}
		}
	}
	NSString* s2=[NSString stringWithString:str];
	[str release];
	return s2;
}
@end

树1(AVL树)

  采用中序遍历二叉树,得到的也是一个有序的数列。
  完全按照伪码写出来后,就是不能运行,不知是自己加的遍历函数有问题还是插入实现上有问题。
  搞了半天,是没有解决一个问题,就是插入时,树里面的元素个数,如果没有的话,还得初始化一个树。
  14:10记录,下午时发现,原因是我插入时使用的是指针,结果呢?返回的时候,指针的值就变成了0,应该使用引用或双重指针,一个对结点的指针的引用,只有这样,才能改变树上的结点。现在出现的问题是这个树会自动的缩小,估计是昨天自己添的一个先左后右的平衡处理算法错了,才会导致现在的状况。
  15:20记录,其实挺喜欢VC6.0,强大的调试工具,断点分析的确能帮助新手很多忙。

#include &lt;iostream&gt;
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;
#define LH 1
#define EH 0
#define RH -1
#define true 1
#define false 0
using namespace std;

typedef struct BSTNode
{
int data;
int bf; //结点的平衡因子
struct BSTNode *lchild,*rchild;//左右孩子
}BSTNode,*BSTree;

void R_Rotate(BSTree &amp;p)//右旋
{
BSTree lc=p-&gt;lchild; //lc指向的*p的左子树根结点
p-&gt;lchild=lc-&gt;rchild; //lc的右子树挂接为*p的左子树
lc-&gt;rchild=p; //
p=lc; //p指向新的结点
}
void L_Rotate(BSTree &amp;p)//左旋
{
BSTree rc=p-&gt;rchild;
p-&gt;rchild=rc-&gt;lchild;
rc-&gt;lchild=p;
p=rc;
}
//对以指针T所指结点为根的二叉树做左平衡旋转处理,结束时,指针T指向新的根结点
void leftBalance(BSTree &amp;T)
{
BSTree lc =T-&gt;lchild,rd; //lc指向*T的左子树根结点
switch(lc-&gt;bf) //检查*T的左子树的平衡度,并作相应平衡处理
{
case LH: //新结点插入在*T的左孩子的左子树上,做单右旋处理
T-&gt;bf=lc-&gt;bf=EH;
R_Rotate(T);
break;
case RH: //新结点插入在*T的左子树的右子树上,要作双旋处理
rd = lc-&gt;rchild; //rd指向*T的左子树的右子树根上
switch(rd-&gt;bf) //修改*T以及左孩子的平衡因子
{
case LH:
T-&gt;bf=RH;
lc-&gt;bf=EH;
break;
case EH:
T-&gt;bf=lc-&gt;bf=EH;
break;
case RH:
T-&gt;bf=EH;
lc-&gt;bf=LH;
break;
}//switch(rd-&gt;bf)
rd-&gt;bf=EH;
L_Rotate(T-&gt;lchild); //d对*T的左子树作为左平衡处理
R_Rotate(T); //对*T右旋处理
}//switch(lc-&gt;bf)
}
void rightBalance(BSTree &amp;T)
{
BSTree rc =T-&gt;rchild,ld; //rc指向*T的右子树根结点
switch(rc-&gt;bf) //检查*T的右子树的平衡度,并作相应平衡处理
{
case RH: //新结点插入在*T的左孩子的右子树上,做单左旋处理
T-&gt;bf=rc-&gt;bf=EH;
L_Rotate(T);
break;
case LH: //新结点插入在*T的右子树的左子树上,要作双旋处理
ld = rc-&gt;lchild; //rd指向*T的右子树的左子树根上
switch(ld-&gt;bf) //修改*T以及右孩子的平衡因子
{
case LH:
T-&gt;bf=EH;
rc-&gt;bf=RH;
break;
case EH:
T-&gt;bf=rc-&gt;bf=EH;
break;
case RH:
T-&gt;bf=LH;
rc-&gt;bf=EH;
break;
}//switch(rd-&gt;bf)
ld-&gt;bf=EH;
R_Rotate(T-&gt;rchild); //d对*T的右子树作为右平衡处理
L_Rotate(T); //对*T左旋处理
}//switch(lc-&gt;bf)
}
/*如果在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个数据元素,为e的新结点,并返回1,否则返回0。如果因插入而使二叉排序树失去平衡,则作平衡旋转处理,变量taller反映T是否长高*/
int insertAVL(BSTree &amp;T,int e,int taller)
{
if(T == NULL) /*插入新结点,树“长高”,置taller为true*/
{
T=(BSTree)malloc(sizeof(BSTNode));
T-&gt;data=e;
T-&gt;lchild=T-&gt;rchild=NULL;
T-&gt;bf=EH;
taller=true;
}
else
{
if(e == T-&gt;data) /*如果树中已经存在和e有相同关键字的结点,则返回不再插入*/
{
taller=false;
return 0;
}
if(e &lt; T-&gt;data) /*如果小于,在*T的左子树进行搜索*/
{
if(!insertAVL(T-&gt;lchild,e,taller))/*未插入*/
return 0;
if(taller)/*以插入到*T的左子树且左子树长高*/
{
switch(T-&gt;bf)/*检查*T的平衡度*/
{
case LH:/*原本左子树比右子树高,需要作左平衡处理*/
leftBalance(T);
taller=false;
break;
case EH:/*原本一样高,现在左子树长高了*/
T-&gt;bf=LH;
taller=true;
break;
case RH:/*原本右子树高,现在一样高*/
T-&gt;bf=EH;
taller=false;
break;
}//switch(T-&gt;bf)
}
}
else
{
if(!insertAVL(T-&gt;rchild,e,taller))
return 0;
if(taller)
{
switch(T-&gt;bf)
{
case LH:
T-&gt;bf=EH;
taller=false;
break;
case EH:
T-&gt;bf=RH;
taller=true;
break;
case RH:
rightBalance(T);
taller=false;
break;
}//switch(T-&gt;bf)
}
}
}
return 1;
}
void midTraverse(BSTree T)
{
if(T != NULL)
{
if(T-&gt;lchild != NULL)
midTraverse(T-&gt;lchild);
printf("%d ",T-&gt;data);
if(T-&gt;rchild != NULL)
midTraverse(T-&gt;rchild);
}
else
return;
}
int main(void)
{
int i,t,a[10]={83,19,65,47,86,29,82,94,12,55};
BSTree tree=NULL;
srand(time(0));
for(i=0;i&lt;10;i++)
{
t=rand()%100;
printf("插入:%d\n",t);
insertAVL(tree,t,true);
midTraverse(tree);
printf("\n");
}
midTraverse(tree);
printf("\n");
return 0;
}

找最大值和最小值的问题

  如何在n个元素中找找到最大值和最小值?首先我想到的是,每一个元素与当前的最大值和最小值进行比较,而这样做和独立的求最大值和最小值没有什么区别。有一种方法:就是成对的处理元素,先将一对输入元素互相比较,然后把较小者与当前最小值比较,把较大者于当前最大值比较,因此每个元素需要3次比较。这样比较次数至多是3(n/2)。
#include<stdio.h>
int main()
{
int a[]={5,47,95,9,1,2,68,66,1,86,415,22,621,8,3,5,58};
int i,max=a[0],min=a[0];
for(i=1;i<=17-2;i+=2)
{
if(a[i]<a[i+1])
{
if(maxa[i])min=a[i];
}
else
{
if(maxa[i+1])min=a[i+1];
}
}
printf(“Max=%d,Min=%d\n”,max,min);
return 0;
}

排序7(小结)

  到目前为止,了解的排序算法有:
  直接插入递归归并堆排序快速排序希尔排序、还有简单的两种冒泡排序和选择排序,太简单了,就没有写上实现代码。还有计数排序,基数排序,桶排序,(这三种都是以线性时间排序,非比较排序)一共看了10种排序的排序方法。
  有人说现在系统里头有各种函数,供大家调用,而且效率还有各个方面的都是很好的,没有必要自己写算法。这让我想起了,小时候为什么要背乘法口诀,每个人直接发个计算器不就行了,而且一会儿就学会了,还能算各种加减乘除。路要一步一步的走,才能走的稳!
  这些天把自己见到的一些排序算法整理总结了一下,想学会跑,得先走稳,脚踏实地,切忌好高骛远。
  主要参考书:①电子版的《算法导论(中文第二版)》
        ②清华大学出版社的严蔚敏《数据结构》

排序6(线性时间排序)

  今天看了《算法导论》第八章,这一章介绍了三种排序的思路:计数排序,基数排序,还有桶排序。
  计数排序,就是用一个辅助数组记录每一个数的出现次数。然后,把数挨着放进去,排序。这不是一个排序算法,因为元素之间没有存在比较。计数排序比较稳定,常作为基数排序的一个子过程。
  基数排序,一种老式穿卡机上的算法,就是在多位数中,排序从低位到高位排序,这让我想起对年月日进行排序,用这种方法绝对不错。先对日,再对月,最后对年进行排序。
  桶排序,就是在一个小范围内的输入,不能太大,就是存储有点类似于hash吧!不过hash是随机的,这个是按顺序存储的。形象上,就是摆一排顺序的桶,然后把数据按一定顺序落在桶中。整个桶排序算法就以线性期望时间运行。
  好了,以上三种算法都是以线性时间排序。都是用一些非比较的一些操作来确定排序的顺序。到目前为止,已经有了7种比较排序的方法,这三种还见的不太多(可能见识的少吧!)。觉得有用的还是基数排序的进行排日期的那种思维,这中思路还是值得借鉴的。

排序5(希尔排序)

  今天看了希尔排序,是在直接插入排序上的一种改进,缩小增量的排序。在时间效率上有了较大的改进。
  希尔排序就是用一个递减的序列对数据进行排序。增量序列的取法:没有除了1之外的公因子,而且最后一个元素是1。

#include<stdio.h>
void shellInsert(int *a,int k)
{
int i,j;
for(i=k+1;i<=10;i++)
{
if(a[i]0 && a[0]<a[j];j-=k)
a[j+k]=a[j];
a[j+k]=a[0];
}
}
return;
}
void shellSort(int *a,int *zeng,int t)
{
int k;
for(k=0;k<t;k++)
shellInsert(a,zeng[k]);
return;
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
int zeng[3]={5,3,1};
shellSort(a,zeng,3);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

排序4(快速排序–冒泡的改进)

  今天看了《算法导论》的第七章快速排序。
  首先选择一个记录(通常选择第一个)最为枢轴(pivot)(自己理解为用作比较的关键字)。
  其次,开始进行排序,先进行一趟排序,然后进行递归式的排序。
  在一趟排序的时候,还有两种思维的方法:①(注释的partition)直接把比pivot小的移动在低位,把比pivot大的移动在高位,最后了,把pivot放进去。②设立三个指向东西的i,j,p。p是记录低位,不动。j是遍历,i记录低位段的最高位,最后了,再把pivot查到地位段和高位段的中间。
  继续进化:
  当对一个随机的输入数组应用快速排序时,要想在每一层上都有同样的划分是不太可能的。这样每一次的pivot都是第一个元素的话,就会使某些划分比较对称,另一些很不对称。一个好的解决方法:把pivot随机化,这样我们就在期望平均的情况下,对输入数组进行划分能够比较的对称。
  随机化版本的快速排序是对足够大的输入的理想选择。

#include<stdio.h>
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
return;
}
int partition(int * a,int p ,int r)
{
int x=a[r],i=p-1,j;
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(&a[i],&a[j]);
}
}
swap(&a[i+1],&a[r]);
return i+1;
}
/*int partition(int * a,int low ,int high)
{
int pivot;
a[0]=a[low];
pivot=a[low];
while(low<high)
{
while(low= pivot )
–high;
a[low]=a[high];
while(low ++low;
a[high]=a[low];
}
a[low]=a[0];
return low;
}*/
void quickSort(int *a,int low,int high)
{
int pivot;
if(low<high)
{
pivot=partition(a,low,high);
quickSort(a,low,pivot-1);
quickSort(a,pivot+1,high);
}
return;
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
quickSort(a,1,10);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}