# 斯坦福编程范式 CS107_7

# 使用栈来操纵字符串

接着上节课的栈的结构体

	typedef struct{
	void *elems;
	int elemSize; // 泛型中并不知道类型占用字节的大小，所以需要指定
	int loglength;
	int alloclength;

	}stack;

	void StackNew(stack *s,int elemSize);
	void StackDispose(stack *s);
	void StackPush(stack s,void elemAddr);
	void StackPop(stack s,void elemAddr);

以下是 main 函数内容

	int main(){
	const char* friends[] = {"Al","Bob","Carl"};
	stack stringStack;
	StackNew(&stringStack,sizeof(char*));
	for(int i = 0; i < 3; i++){
	char *copy = strdup(friends[i]); // 调用 strdup 会使用 malloc 函数，这和后面我们使用 free 函数是呼应的
	StackPush(&stringStack,&copy);
	}
	char *name;
	for(int i = 0;i < 3;i++){
	StackPop(&stringStack,&name);
	printf("%s\n",name);
	free(name);
	}
	StackDispose(&stringStack);
	}

在上述例子中，如何构造 StackDispose 使其能够完全的将栈中的特殊元素，诸如指针元素中指针所指的内容传递给 free 函数释放动态申请的内存较为难以实现，下面进行实现。

在结构体中新增加了一个 void 函数。

	typedef struct{
	void *elems;
	int elemSize; // 泛型中并不知道类型占用字节的大小，所以需要指定
	int loglength;
	int alloclength;
	void (freefn)(void );
	}stack;

	void StackNew(stack *s,int elemSize);
	void StackDispose(stack *s);
	void StackPush(stack s,void elemAddr);
	void StackPop(stack s,void elemAddr);

	void StackNew(stack s,int elemSize,void (freefn)(void *));
	void StackDispose(stack *s){
	if(s->freefn != NULL){
	for(int i = 0;i < loglength,i++){
	s->freefn((char)s->elems + is->elemSize);
	}
	}
	}

s->freefn != NULL 表示栈中有复杂的结构，如 char* 或者套用了另一个结构体之类的，因而需要我们调用自己的函数手动进行清楚空间。

还是假设栈是字符串栈。

	stack stringStack;
	StackNew(&stringStack,sizeof(char*),StringFree);

	----------------
	void StringFree(void *elem){
	free((char *)elem);
	}

实现一个 rotate 函数，将一个数组的前几项内容整体全部复制并挪到数组的尾部，其余部分往前移动。

调用 memcpy 函数时，地址是不能重叠的。memmove 函数与 memcpy 类似，只不过效率更低，对重叠元素进行处理，并进行数组移动。尽可能多用 memcpy 少用 memmove

	void rotate(void front,void middle,void *end){
	int frontSize = (char)middle - (char)front;
	int backSize = (char)end - (char)middle;
	char buffer[frontSize];
	memcpy(buffer,front,frontSize);
	memmove(front,middle,backSize); // 这里只能用 memmove 不能用 memcpy
	memcpy((char*)end-frontSize,buffer,frontSize);
	}

	void Qsort(void base,int size,int elemSize,int (cmpfn)(void ,void )){

	}

函数栈就不多说了，主函数高地址，每当调用新的函数时，就会入栈，从高地址到低地址，函数返回就会出栈。

这里的堆栈指的不是一种优先队列数据结构，只是一块任意的字节。汇编代码一般都会在堆的低地址部分，由硬件进行管理；在汇编代码上方是由软件的堆内存管理器管理的，如 malloc、realloc、free 函数，是由软件管理的。

堆内存是一个很大的线性的字节数组。当我们执行以下代码时：

void *a = malloc(40);

malloc 函数会从堆的开始地址开始查找，找到第一块适合请求大小的空闲内存，并将这块内存标记为已占用，并返回内存的开始地址。继续执行下面的代码：

void *b = malloc(60);

函数发现开始的一段内存块已经被占用了，它会快速的到达这块内存块的尾部，从空闲位置进行内存分配，和上一步的步骤类似。如果再执行以下代码：

free(a);

free 函数会抹掉这段内存的被占用状态，释放内存。再执行如下命令：

void *c = malloc(44);

函数会查看第一段内存块，发现这是一段 40 字节大小的空内存块，由于小于 44 字节，所以会直接跳到下一段空闲的足够大的内存块。之后执行如下代码：

void *d = malloc(20);

这一次第一段的 40 字节内存块就足够大了，函数会将这块切下来并记录下是 20 字节大，然后再次返回这个指针。

以上只是粗略的进行讲述堆栈的内存分配过程，实际上是有一个数据结构用来管理着整个堆栈，它使用了很多 void * 来进行内存管理，名字是空闲记录的链表，它始终记录着第一个空闲记录的地址，能够方便的找出哪一部分能够满足下一个 malloc 的需求