数据结构的编程作业，使用哈希函数实现字典，并且支持插入，删除，查找功能。没有复杂的算法，但是写的过程中还是遇到一些问题。

1. 段错误

程序定义结构体：

struct hashTableEntry
{
    char key[LEN];
    char value[LEN];
};

然后在main()函数中定义 struct hashTableEntry hashTable[12255], 出现段错误，开始怀疑是不是C语言对数组所占的内存空间有限制，后来把hashTable变为全局变量，就没有问题。问超哥才知道堆空间和栈空间的区别，开始忏悔编译原理跟OS怎么学的……下面引用C语言教材关于C程序内存映像的介绍：

一个完成编译的C程序取得并使用4块在逻辑上不同且用于不同目的的内存区域。如上图所示，第一块区域存放程序代码，相邻的一块内存区域是存放全局变量和静态变量的静态存储区。相邻两块分别是“堆”和“栈”。栈用于保存程序的许多运行信息，如函数调用的返回地址，函数的形参，局部变量以及CPU的当前状态。堆是一个自由存储区，程序可以使用C的动态内存分配函数来使用它。

C程序中变量的内存分配方式有以下3种：

1. 从静态存储区分配。程序的全局变量和静态变量都是在静态存储区上分配，且在程序编译时就已经分配好了，在程序运行期间是存在的。只有在程序终止之前被操作系统回收。
2. 在栈上创建。在执行函数调用时，函数内的局部变量及形参都是在栈上创建的，该函数执行结束时，这些内存自动被释放掉。栈内存分配运算置于处理器的指令集中，效率很高，但是容量有限。
3. 从堆上分配。在程序运行期间，用动态内存分配函数来申请的内存都是从堆上分配的。动态内存的生存周期由程序员自己来决定，使用非常灵活，但也容易出现问题。有一点需要程序员时刻牢记：自己要负责在不使用这些内存的时候用free()将其释放，归还系统，以便以后利用，这时防止内存泄漏的必要手段。

2. sscanf() 的使用

以前只用过sprintf()，与printf()的使用方法相同，只是将打印的内容保存到字符串中。sscanf()与scnaf()同理，只是从字符串中按格式读取输入，而不是从终端中读取。基本用法见:http://baike.baidu.com/view/1364018.htm

C代码下载链接：https://github.com/jia1546/dictionary

最近听港大数据结构课，于是想动手实现一些最基本的算法。深度优先跟广度优先是最基本的遍历算法，实现的时候还是会有一些小的错误。

比如删除队列中的元素，出现段错误因为：

head -> next = head -> next -> next;

free(head -> next)

以及遍历链表时无法得到最后一个元素

while(tmp -> next != NULL)

都是一些细节没有处理好，以后写程序要注意了……

附上两个程序的图

BFS：

C语言程序可在GitHub下载：https://github.com/jia1546/BFS

DFS：

C语言程序可在GitHub下载：https://github.com/jia1546/DFS

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

int partition(int *array, int p, int r)
{
	int x, i, j;
	int tmp;
	x = array[r];
	i = p - 1;
	for(j=p; j<=r-1; j++)
	{
		if(array[j] <= x)
		{
			i++;
			tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
		}
	}
	tmp = array[r];
	array[r] = array[i+1];
	array[i+1] = tmp;
	return i+1;
}

void quickSort(int *array, int p, int r)
{
	int q;
	if(p < r)
	{
		q = partition(array, p, r);
		quickSort(array, p, q-1);
		quickSort(array, q+1, r);
	}
}

int main()
{
    int *array, n;
    int i;
    while(scanf("%d",&n) != EOF)
    {
    	array = (int*)malloc(sizeof(int)*n);
    	for(i=0; i<n; i++)
    		scanf("%d", array+i);
    		
    	quickSort(array, 0, n-1);
    	
    	for(i=0; i<n; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    }
	return 0;
}

虽然知道算法的基本原理，还是动手写写吧。

代码如下：

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

void MaxHeapfy(int *array, int i, int heapSize)
{
	int l, r ;
	int temp, largest;
	l = 2 * i;
	r = 2 * i + 1;
	if(l <= heapSize && array[l] > array[i])
		largest = l;
	else
		largest = i;
	if(r <= heapSize && array[r] > array[largest])
		largest = r;
	if(largest != i)
	{
		temp = array[i];
		array[i] = array[largest];
		array[largest] = temp;
		MaxHeapfy(array, largest, heapSize);
	}
}

void BuildMaxHeap(int* array, int n)
{
	int heapSize = n;
	int i;
	for(i=n/2; i>=1; i--)
		MaxHeapfy(array, i, heapSize);
}

void HeapSort(int *array, int n)
{
	int temp;
	int heapSize = n;
	int i;
	BuildMaxHeap(array, n);
	for(i=n; i>=2; i--)
	{
		temp = array[1];
		array[1] = array[i];
		array[i] = temp;
		heapSize--;
		MaxHeapfy(array, 1, heapSize);
	}
}

int main()
{
	int *array;
	int n;
	int i;
	
	while(scanf("%d",&n) != EOF)
	{
		array = (int*)malloc(sizeof(int)*(n+1));	//the index starts from 1
		for(i=1; i<=n; i++)
			scanf("%d",array+i);
		
		HeapSort(array, n);
		
		for(i=1; i<=n; i++)
			printf("%d ", array[i]);
		printf("\n");
	}	
	return 0;
}

PS：喜欢上Scribes Text Editor，虽然没有Vim, Emacs那般强大，但写写小程序够用了，之前试过很多编辑器，发现不是很简便，终于找到一个喜欢的了……