MMORPG大型游戏设计与开发（服务器 游戏场景 事件）

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#include <inttypes.h>/**
* 归并排序算法实现复杂，因为二路归并算法需要的临时空间较大，所以常常用在外部
* 排序中。（其核心的思想为将两个或两个以上的元素有序序列合并为一个有序序列）
* 归并算法是一种稳定的排序算法。
*///将source数组中的元素复制到dest数组中，其中，length为长度，first是目标数组的起始位置
void copyarray(int32_t source[], int32_t dest[], int32_t length, int32_t first);
//归并排序
void mergesort(int32_t array[], int32_t left, int32_t right);
//合并两个子序列中的元素
void merge(int32_t array[], int32_t left, int32_t right);
//数组打印
void displayarray(int32_t array[], int32_t length);int32_t main(int32_t argc, char *argv[]) {
int32_t array[] = {, , , , , , , , };
int32_t length = sizeof(array) / sizeof(array[]);
printf("before sort: ");
displayarray(array, length);
mergesort(array, , length - );
printf("after sort: ");
displayarray(array, length);
return ;
}void copyarray(int32_t source[], int32_t dest[], int32_t length, int32_t first) {
int32_t i, j = first;
for (i = ; i < length; ++i) {
dest[j] = source[i];
++j;
}
}void mergesort(int32_t array[], int32_t left, int32_t right) {
int32_t i;
if (left < right) {
i = (left + right) / ;
mergesort(array, left, i);
mergesort(array, i + , right);
merge(array, left, right);
}
}void merge(int32_t array[], int32_t left, int32_t right) {
int32_t begin1, begin2, middle, k = , length;
int32_t *pointer = NULL;
begin1 = left;
middle = (left + right) / ;
begin2 = middle + ;
length = right - left + ;
pointer = (int32_t *)malloc(length * sizeof(int32_t));
if (NULL == pointer) return;
while (begin1 <= middle && begin2 <= right) {
if (array[begin1] < array[begin2]) {
pointer[k++] = array[begin1++];
} else {
pointer[k++] = array[begin2++];
}
}
while (begin1 <= middle) pointer[k++] = array[begin1++];
while (begin2 <= right) pointer[k++] = array[begin2++];
copyarray(pointer, array, length, left);
if (pointer != NULL) free(pointer);
pointer = NULL;
}void displayarray(int32_t array[], int32_t length) {
int32_t i;
for (i = ; i < length; ++i)
printf("%4d", array[i]);
printf("\n");
}

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#include <inttypes.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>/**
* 基数排序算法实现比较复杂，它是一种多关键字的排序算法，属于分类排序。因为基数
* 排序算法不需要过多比较，所以在数据较多的情况下，采用基数排序算法的效率要高于
* 其他的排序算法。
*/#define SIZEMAX 200 //待排序元素的最大个数
#define N 10 //待排序元素的实际个数
#define NUMBERKEY_MAX 6 //关键字项数的最大值
#define RADIX 10 //关键字基数，10表示十进制数字可以分为十组typedef struct listcell_struct {
int32_t key[NUMBERKEY_MAX]; //关键字
int32_t next;
} listcell_t; //静态链表的节点，存放待排序的元素typedef struct list_struct {
listcell_t data[SIZEMAX]; //存储元素,data[0]为头节点
int32_t keynumber; //每个元素的当前关键字个数
int32_t length; //静态链表的当前长度
} list_t; //静态链表，存放元素序列typedef int32_t addr[RADIX]; //指针数组的类型，用来指向每个链表的第一个节点和最后一个节点void displaylist(list_t L); //输出链表中的元素
void display_staticlist(list_t L); //以静态链表的形式输出元素
void initlist(list_t *list, int32_t dest[], int32_t length);
int32_t transchar(char _char); //将字符转换为数字
void distribute(listcell_t data[], int32_t i, addr f, addr r); //分配
void collect(listcell_t data[], addr f, addr r); //收集
void radixsort(list_t *L);int32_t main(int32_t argc, char *argv[]) {
int32_t array[N] = {, , , , , , , , , };
list_t L;
initlist(&L, array, N);
printf("need sort number is %d, key number is %d\n", L.length, L.keynumber);
printf("before sort static list: ");
display_staticlist(L);
printf("before sort list: \n");
displaylist(L);
radixsort(&L);
printf("after sort: \n");
displaylist(L);
return ;
}//按数组序号形式输出静态链表
void displaylist(list_t L) {
int32_t i, j;
printf("no key addr \n");
for (i = ; i <= L.length; ++i) {
printf("%2d ", i);
for (j = L.keynumber - ; j >= ; --j) {
printf("%c", L.data[i].key[j]);
}
printf(" %d\n", L.data[i].next);
}
}//按链表形式输出静态链表
void display_staticlist(list_t L) {
int32_t i = L.data[].next, j;
while (i) {
for (j = L.keynumber - ; j >= ; --j)
printf("%c", L.data[i].key[j]);
printf(" ");
i = L.data[i].next;
}
printf("\n");
}//初始化静态链表L
void initlist(list_t *L, int32_t array[], int32_t length) {
char _char1[NUMBERKEY_MAX] , _char2[NUMBERKEY_MAX];
int32_t i, j;
int32_t max = array[];
for (i = ; i < length; ++i) { //将最大的元素存入max
if (max < array[i]) max = array[i];
}
(*L).keynumber = (int32_t)(log10(max)) + ; //求字关键字的个数
(*L).length = length; //待排序个数
for (i = ; i <= length; ++i) {
//itoa(array[i - 1], _char1 , 10); //将整型转换为字符，并存入_char
sprintf(_char1, "%d", array[i - ]);
//如果_char的长度<max的位数，则在_char前补'0'
for (j = strlen(_char1); j < (*L).keynumber; ++j) {
strcpy(_char2, "");
strcat(_char2, _char1);
strcpy(_char1, _char2);
}
//将每个元素的个位数存入key，作为关键字
for (j = ; j < (*L).keynumber; ++j) {
(*L).data[i].key[j] = _char1[(*L).keynumber - - j];
}
}
for (i = ; i < (*L).length; ++i)
(*L).data[i].next = i + ;
(*L).data[(*L).length].next = ;
}int32_t transchar(char _char) {
return _char - '';
}//为data数组中的第i个关键字key[i]建立radix个子表，使同一子表中元素的key[i]相同
//f[0...radix - 1]和r[0...radix - 1]分别指向各个子表中第一个和最后一个元素
void distribute(listcell_t data[], int32_t i, addr f, addr r) {
int32_t j, p;
for (j = ; j < RADIX; ++j) f[j] = ; //初始化各个子表
for (p = data[].next; p; p = data[p].next) {
j = transchar(data[p].key[i]); //将关键字转换为数字
if (!f[j]) { //f[j]是空表，则f[j]指示第一个元素
f[j] = p;
} else {
data[r[j]].next = p;
}
r[j] = p; //将p所指的节点插入第j个子表中
}
}//收集，按key[i]将f[0...radix - 1]所指各子表依次连接成一个静态链表
void collect(listcell_t data[], addr f, addr r) {
int32_t i;
int32_t temp;
for (i = ; !f[i]; ++i); //找第一个非空子表，为求后续函数
data[].next = f[i];
temp = r[i]; //r[0].next 指向第一个非空子表中的第一个节点
while (i < RADIX - ) {
for (i = i + ; i < RADIX - && !f[i]; ++i); //查找下一个非空子表
if (f[i]) {
data[temp].next = f[i];
temp = r[i];
}
}
data[temp].next = ; //temp指向最后一个非空子表中的最后一个节点
}//基数排序，使得L成为按关键字非递减的静态链表，L.r[0]为头节点
void radixsort(list_t *L) {
int32_t i;
addr f, r;
//由低位到高位一次对各关键字进行分配和收集
for (i = ; i < (*L).keynumber; ++i) {
distribute((*L).data, i, f, r); //第i次分配
collect((*L).data, f, r); //第i次收集
printf("the %d times collect result: ", i + );
display_staticlist(*L);
}
}