堆和栈
数据结构中的堆栈：
堆：树状结构，是一种优先队列，先进先出
栈：桶状结构，先进后出
操作系统中的堆栈：
都是指内存空间
- 申请方式
堆是由程序员自己申请并指明大小，在c中malloc函数 如p1 = (char *)malloc(10);
栈由系统自动分配，如声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 - 申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会 遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内 存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大 小，系统会自动的将多余的那部分重新放入空闲链表中。 - 申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结 构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有的说是1M，总之是 一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。 - 申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
进程线程与栈、堆的关系
一般一个进程有一个运行时堆(heap)，【动态大小】，这个堆为本进程中所有线程共享；线程拥有各自独立的（/私有的）栈(stack)，大小一般是1M/2M(不同系统不一样)【固定大小】
区
1.栈区(stack)：由系统的编译器自动的释放，主要用来存放方法中的参数，一些临时的局部变量等，并且方法中的参数一般在操作完后，会由编译器自动的释放掉。
2.堆区(heap):由程序员决定，在Java中，如果程序员不释放的话，一般会由垃圾回收机制自动的清理掉。此区域主要用来存放我们经常创建的对象、动态的申请的临时空间等。
3.数据区(data seg):也称全局区或者静态区，根据名称我们就应该知道用来存放一些全局的东西，比如我们经常用到的静态变量、全局变量等都会存放到数据区，此区域上的东西都被全局所共享。比如我们可以采取类名.的方式就可以访问到方法，这就是所谓的静态方法，存放到数据区的。
4.代码区：存放程序编译后可以执行代码的地方。比如执行代码时写的While语句、if条件语句等，都会存放到此。
进程间堆不能相互访问
保护模式下进程的内存空间是分离的，进程分配的堆只能进程内访问
不过16位实模式下（纯DOS），全局只有一个地址空间，进程之间可以相互窃取对方信息
如果用new和malloc分配的堆空间在不同进程中是不可以共享的
不过用globalAlloc申请的内存可以在进程中共享，比如剪切板就是用的他们
堆的大小：堆的大小实际上（运行时）动态变化的，但有理论最大值，（取决于内存或虚拟内存？）
链表倒序
void reverse(list_node *head)
{
if(NULL == head || NULL == head->next )
{
return;
}
list_node pre = head;
list_node c = head->next;
list_node n = NULL;
while (NULL != c)
{
n = c.next;
c.next = pre;
pre = c;
c = n;
}
head.next = NULL;
return pre;
}
冒泡排序
//（从小到大）
void bubbleSort(int a[], int n)
{
if (n < 2) {
return;
}
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
选择排序
//（从小到大）
void selectSort(int *a, int n)
{
if (n < 2) {
return;
}
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
插入排序
//（从小到大）
void insertSort(int *a, int n)
{
if (n < 2) {
return;
}
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while (j >= 0 && temp < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
快速排序
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，递归调用，以达到整个序列有序。
void quickSort(int a[], int left, int right)
{
if (left >= right) {
return;
}
int i = left, j = right, key = a[left], temp = 0;
while (i < j) {
while (i < j && a[j] >= key) {
j--;
}
while (i < j && a[i] <= key) {
i++;
}
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[left] = a[i];
a[i] = key;
quickSort(a, left, i - 1);
quickSort(a, i + 1, right);
}
字符串排序
void stringSort()
{
NSString *string = @"kassf骄傲覅微积分违法IQ多看看我经济法基督教扩大加肥加大djfoeIJOFIJODSJIFOI13243423";
NSLog(@"%@", string);
NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i < string.length; i++) {
[array addObject:[string substringWithRange:NSMakeRange(i, 1)]];
}
//NSLog(@"%@", array);
[array sortUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
NSString *string1 = (NSString *)obj1;
NSString *string2 = (NSString *)obj2;
NSInteger ascll1 = [string1 characterAtIndex:0];
NSInteger ascll2 = [string2 characterAtIndex:0];
//return [string1 compare:string2 options:NSBackwardsSearch];
//return [string1 compare:string2];
if (ascll1 > ascll2) {
return NSOrderedDescending;
}
else if (ascll1 == ascll2) {
return NSOrderedSame;
}
else {
return NSOrderedAscending;
}
}];
// NSInteger count = array.count;
// for (NSInteger i = 0; i < count; i++) {
// for (NSInteger j = 0; j < count - 1 - i; j++) {
// NSString *string1 = array[j];
// NSString *string2 = array[j+1];
// NSInteger character1 = [string1 characterAtIndex:0];
// NSInteger character2 = [string2 characterAtIndex:0];
// if (character1 > character2) {
// [array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
// }
// }
// }
NSString *newString = [array componentsJoinedByString:[NSString string]];
NSLog(@"newString: %@", newString);
}
查找最大值和最小值
//(两两一组比较，3n/2次)
BOOL search(int a[], int n, int *max, int *min)
{
if (n < 1) {
return NO;
}
*max = a[0];
*min = a[0];
//int i = (n % 2 == 0 ? 0 : 1);
int i = 1;
while (i + 1 < n) {
if (a[i] > a[i+1]) {
if (*max < a[i]) {
*max = a[i];
}
if (*min > a[i+1]) {
*min = a[i+1];
}
}
else {
if (*max < a[i+1]) {
*max = a[i+1];
}
if (*min > a[i]) {
*min = a[i];
}
}
i += 2;
}
//最后一个数如果没比较的话，单独比较
if (i < n) {
int last = a[n - 1];
if (*max < last) {
*max = last;
}
else if (*min > last) {
*min = last;
}
}
return YES;
}
分治法查找
void divideSearch(int a[], int left, int right, int *max, int *min)
{
if (left > right) {
return;
}
if (right - left > 1) {
int leftMax, leftMin, rightMax, rightMin;
int mid = (right + left) / 2;
divideSearch(a, left, mid, &leftMax, &leftMin);
divideSearch(a, mid + 1, right, &rightMax, &rightMin);
*max = (leftMax > rightMax ? leftMax : rightMax);
*min = (leftMin < rightMin ? leftMin : rightMin);
return;
}
if (a[left] > a[right]) {
*max = a[left];
*min = a[right];
}
else {
*max = a[right];
*min = a[left];
}
}
二分查找
//（在有序的数组中查找指定数字的位置）
int findKeyNum(int *a, int count, int keyNumber)
{
int max = count - 1, min = 0, mid;
while (max >= min) {
mid = (max + min) / 2;
if (keyNumber > a[mid]) {
min = mid + 1;
}
else if (keyNumber < a[mid]) {
max = mid - 1;
}
else {
return mid + 1; //返回第几个
}
}
return -1;
}
交换两个数
void exchageNum(int *num1, int *num2)
{
// //加法
// *num1 = *num1 + *num2;
// *num2 = *num1 - *num2;
// *num1 = *num1 - *num2;
//异或（相同为0，不同为1. 可以理解为不进位加法）
*num1 = *num1 ^ *num2;
*num2 = *num1 ^ *num2;
*num1 = *num1 ^ *num2;
}
最大公约数
void maxDivisor(unsigned int a, unsigned int b)
{
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
//遍历法
unsigned int min = MIN(a, b);
unsigned int maxDivisor = 1;
for (unsigned int i = min; i > 1; i--) {
if (a % i == 0 && b % i == 0) {
maxDivisor = i;
break;
}
}
// //辗转相除法（欧几里得算法）
// uint r, maxDivisor;
// while (a % b != 0) {
// r = a % b;
// a = b;
// b = r;
// }
// maxDivisor = b;
CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent();
NSLog(@"TimeCount：%.9f", endTime - startTime);
NSLog(@"maxDivisor is %d", maxDivisor);
}
树
typedef struct BTNode *Tree;
//二叉树结构体
struct BTNode {
int data;
struct BTNode *left, *right;
};
//创建二叉树
Tree creatTree()
{
int input;
scanf("%d", &input);
if (input == 0) {
return NULL;
}
Tree node = malloc(sizeof(Tree));
node->data = input;
node->left = creatTree();
node->right = creatTree();
return node;
}
//遍历二叉树
void traverseTree(Tree node)
{
if (node == NULL) {
return;
}
printf("%d ", node->data);
traverseTree(node->left);
traverseTree(node->right);
}
void treeTest()
{
Tree tree = creatTree();
traverseTree(tree);
free(tree);
}
网友评论