#
Unix进程间通信主要分为（1）消息传递 （2）同步 （3）共享内存 （4）远程调用
（1）消息传递主要有管道，FIFO，消息队列
（2）同步主要有互斥锁与条件变量，读写锁，记录锁，信号量
（3）共享内存
（4）远程调用
参考 unix网络编程
客户/服务器程序设计范式有
（1）迭代服务器（无进程控制)
（2）并发服务器，每个客户请求fork 一个子进程
（3）预先派生子进程，每个子进程无保护地调用accept
（4）预先派生子进程，使用文件上锁保护accept
（5）预先派生子进程，使用线程互斥锁保护accept（共享内存)
（6）预先派生子进程，父进程向子进程传递套接口描述字
（7）并发服务器，每个客户请求创建一个线程
（8）预先创建线程服务器，使用互斥锁上锁保护accept
（9）预先创建线程服务器，由主线程调用accept.
测试用例 客户创建5个进程，每个发起500个连接，每个连接写四个字节数据
总的用户时间（秒） 总的系统时间（秒）
（1） 0.012 0.16001
（2） 0.008 0.256016
（3） 0.016 0.268016
（4） 0.020001 0.380023
（5） 0.012 0.308019
（6） 0.068003 0.464029
（7） 0.024001 0.224014
（8） 0.012 0.280017
（9） 0.0160001 0.268016
最长公共子序列实现
参考算法导论第208页
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void LCS(char *p,char *q)
{
int lenP,lenQ;
int *s,*t;
lenP=strlen(p);
lenQ=strlen(q);
int i,j;
if((s=(int*)malloc(sizeof(int)*(lenP+1)*(lenQ+1)))==NULL)
{
perror("malloc error");
exit(1);
}
if((t=(int*)malloc(sizeof(int)*(lenP+1)*(lenQ+1)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<(lenP+1);i++)
s[i]=0;
for(i=0;i<(lenQ+1);i++)
s[i*(lenP+1)]=0;
for(i=1;i<(lenQ+1);i++)
{
for(j=1;j<(lenP+1);j++)
{
if(q[i-1]==p[j-1])
{
s[i*(lenP+1)+j]=s[(i-1)*(lenP+1)+j-1]+1;
t[i*(lenP+1)+j]=3;
}else if(s[(i-1)*(lenP+1)+j]<s[i*(lenP+1)+j-1]){
s[i*(lenP+1)+j]=s[i*(lenP+1)+j-1];
t[i*(lenP+1)+j]=1;
}else{
s[i*(lenP+1)+j]=s[(i-1)*(lenP+1)+j];
t[i*(lenP+1)+j]=2;
}
}
}
/*输出矩阵结果*/
printf("output the result:\n");
for(i=0;i<(lenQ+1);i++)
{
for(j=0;j<(lenP+1);j++)
{
printf("%d ",s[i*(lenP+1)+j]);
}
printf("\n");
}
printf("output the result 箭头 1表示向左，2表示向上，3表示斜向上:\n");
for(i=0;i<(lenQ+1);i++)
{
for(j=0;j<(lenP+1);j++)
{
printf("%d ",t[i*(lenP+1)+j]);
}
printf("\n");
}
i=lenQ;
j=lenP;
/*倒序输出LCS*/
printf("倒序输出LCS\n");
while(i>1 || j>1)
{
if(t[i*(lenP+1)+j]==3)
{
printf("%c ",p[j-1]);
i--;
j--;
}else if(t[i*(lenP+1)+j]==2)
{
i--;
}else
j--;
}
printf("\n");
}
int main()
{
char *p="BDCABA";
char *q="ABCBDAB";
LCS(p,q);
}
矩阵链乘法实现（算法导论 P197）
#include<stdio.h>
#include<stdlib.h>
#define MAX 65536
void printMatrix(int *s,int len,int i,int j)
{
if(i==j)
printf("A%d",i+1);
else{
printf("(");
printMatrix(s,len,i,s[i*len+j]);
printMatrix(s,len,s[i*len+j]+1,j);
printf(")");
}
}
void matrixOrder(int p[][2],int len)
{
int *m,*s;
int i,j,k;
if((m=malloc(len*len*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
if((s=malloc(len*len*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<len;i++)
m[i*len+i]=0;
for(i=1;i<len;i++)
{
for(j=0;j+i<len;j++)
{
m[j*len+j+i]=MAX;
for(k=j;k<j+i;k++)
{
if((p[j][0]*p[k][1]*p[i+j][1]+m[j*len+k]+m[(k+1)*len+i+j])<m[j*len+j+i])
{
m[j*len+j+i]=p[j][0]*p[k][1]*p[i+j][1]+m[j*len+k]+m[(k+1)*len+i+j];
s[j*len+j+i]=k;
}
}
}
}
printf("##### then matrix m\n");
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
printf("%d ",m[i*len+j]);
}
printf("\n");
}
printf("##### the matrix s\n");
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
printf("%d ",s[i*len+j]);
}
printf("\n");
}
printMatrix(s,len,0,5);
printf("\n");
}
int main()
{
int p[6][2]={{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};
matrixOrder(p,6);
}
动态规划是通过组合子问题的解而解决整个问题。
动态规划算法设计可以分为4个步骤
（1）描述最优解的结构
（2）递归定义最优解的值
（3）按自底向上的方式计算最优解的值
（4）由计算出的结果构造一个最优解
装配线调度实现(算法导论192页)
参考算法导论 第15章
#include<stdio.h>
#include<stdlib.h>
int schedule(int a[][6],int t[][5],int e[],int x[])
{
int f[2][6];
int l[2][5];
int totalMin;
int lastL;
int i,k;
f[0][0]=e[0]+a[0][0];
f[1][0]=e[1]+a[1][0];
for(i=1;i<6;i++)
{
if(f[0][i-1]<(f[1][i-1]+t[1][i-1]))
{
f[0][i]=f[0][i-1]+a[0][i];
l[0][i-1]=1;
}else{
f[0][i]=f[1][i-1]+t[1][i-1]+a[0][i];
l[0][i-1]=2;
}
if(f[1][i-1]<(f[0][i-1]+t[0][i-1]))
{
f[1][i]=f[1][i-1]+a[1][i];
l[1][i-1]=2;
}else{
f[1][i]=f[0][i-1]+t[0][i-1]+a[1][i];
l[1][i-1]=1;
}
}
for(i=0;i<2;i++)
{
for(k=0;k<6;k++)
{
printf("%d ",f[i][k]);
}
printf("\n");
}
if((x[0]+f[0][5])<(x[1]+f[1][5]))
{
totalMin=x[0]+f[0][5];
lastL=1;
}else{
totalMin=x[1]+f[1][5];
lastL=2;
}
printf("totalMin=%d\n",totalMin);
if(lastL==1)
{
printf("S (1,6) ");
k=0;
}else{
printf("S (2,6) ");
k=1;
}
for(i=4;i>=0;i--)
{
if(l[k][i]==1)
{
printf("S (1, %d) ",i+1);
k=0;
}else{
printf("S (2, %d) ",i+1);
k=1;
}
}
printf("\n");
}
int main()
{
int a[2][6]={{7,9,3,4,8,4},{8,5,6,4,5,7}};
int t[2][5]={{2,3,1,3,4},{2,1,2,2,1}};
int e[2]={2,4};
int x[2]={3,2};
schedule(a,t,e,x);
}
/*红黑树设计与实现
*参考算法导论
*http://www.cppblog.com/converse/archive/2008/11/10/66530.html
插入时有三种情况（这里只考虑z的父节点是z的祖父节点的左孩子，z的父节点是z的祖父节点的右孩子对称也一样）
（1） z的叔叔y是红色的（改变颜色,提升x）
（2） z的叔叔y是黑色的，而且z是右孩子（左旋）
（3） z的叔叔y是黑色的，而且z是左孩子（右旋加改变颜色）
删除时有四种情况（这里只考虑z是z的父节点的左孩子，z是z的父节点的右孩子对称也一样）
（1）x的兄弟w是红色的（左旋加改变颜色）
（2）x的兄弟w是黑色的，而且w的两个孩子都是黑色的（改变颜色，提升x)
（3）x的兄弟w是黑色的，w的左孩子是红色的，右孩子是黑色的(改变颜色加右旋)
（4）x的兄弟w是黑色的，而且w的右孩子是红色的（改变颜色加左旋）
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*定义颜色枚举类型*/
typedef enum color_t
{
RED=0,
BLACK=1
}color_t;
/*定义结构体*/
typedef struct rb_node_t
{
int key;
color_t color;
struct rb_node_t *left,*right,*parent;
}rb_node_t;
/* 测试是否为红黑树*/
int isRedBlackTree(rb_node_t *root,int count)
{
if(root==NULL)
{
printf("黑高度为 %d\n",count);
if(count!=12)/*通过测试该测试用例黑高度为12，不具有普遍性*/
{
printf("not a redblack tree\n");
exit(1);
}
}else{
if(root->color==BLACK)
{
count++;
}
else{
if((root->left!=NULL &&root->left->color==RED)||
(root->right!=NULL && root->right->color==RED))
{
printf("child color RED\n");
}
}
isRedBlackTree(root->left,count);
isRedBlackTree(root->right,count);
}
}
/*中序打印节点用于测试*/
void midPrint(rb_node_t *root)
{
if(root!=NULL)
{
midPrint(root->left);
printf("%d ",root->key);
if(root->color==RED)
printf("RED ");
else
printf("BLACK ");
midPrint(root->right);
}
}
/*先序打印节点用于测试*/
void prePrint(rb_node_t *root)
{
if(root!=NULL)
{
printf("%d ",root->key);
if(root->color==RED)
printf("RED ");
else
printf("BLACK ");
prePrint(root->left);
prePrint(root->right);
}
}
/*创建节点*/
rb_node_t * createNode(int key)
{
rb_node_t *newNode;
if((newNode=malloc(sizeof(rb_node_t)))==NULL)
{
printf("malloc error");
return NULL;
}
newNode->color=RED;
newNode->left=NULL;
newNode->right=NULL;
newNode->key=key;
newNode->parent=NULL;
return newNode;
}
/*左旋*/
rb_node_t * leftRotate(rb_node_t *root,rb_node_t *node)
{
rb_node_t *right;
right=node->right;
if(node->right=right->left)
{
right->left->parent=node;
}
right->left=node;
if(right->parent=node->parent)
{
if(node->parent->left==node)
node->parent->left=right;
else
node->parent->right=right;
}else
root=right;
node->parent=right;
return root;
}
/*右旋*/
rb_node_t *rightRotate(rb_node_t *root,rb_node_t *node)
{
rb_node_t *left;
left=node->left;
if(node->left=left->right)
left->right->parent=node;
left->right=node;
if(left->parent=node->parent)
{
if(node->parent->left==node)
node->parent->left=left;
else
node->parent->right=left;
}else
root=left;
node->parent=left;
return root;
}
/*查找节点，若找到则返回该节点，若没找到返回NULL并且将父节点保存到save中*/
rb_node_t * rb_search_auxiliary(int key,rb_node_t *root,rb_node_t **save)
{
rb_node_t *node,*parent;
node=root;
parent=NULL;
while(node)
{
parent=node;
if(node->key<key)
node=node->right;
else if(node->key>key)
node=node->left;
else
return node;
}
if(save)
*save=parent;
return NULL;
}
/*查找节点*/
rb_node_t * rb_search(int key,rb_node_t *root)
{
return rb_search_auxiliary(key,root,NULL);
}
/*插入节点后进行调整，使其满足红黑树性质*/
rb_node_t * rb_insert_reblance(rb_node_t *root,rb_node_t *node)
{
rb_node_t *parent,*uncle,*grandParent,*temp;
while((parent=node->parent)&&(parent->color==RED))
{
grandParent=parent->parent;
if(parent==grandParent->left)
{
uncle=grandParent->right;
if(uncle!=NULL && uncle->color==RED)
{
parent->color=BLACK;
uncle->color=BLACK;
grandParent->color=RED;
node=grandParent;
}else{
if(node==parent->right)
{
root=leftRotate(root,parent);
temp=parent;
parent=node;
node=temp;
}
//printf("##########\n");
//print(root);
//printf("\n");
parent->color=BLACK;
grandParent->color=RED;
root=rightRotate(root,grandParent);
//printf("##########\n");
// print(root);
// printf("\n");
}
}else{
uncle=grandParent->left;
if(uncle!=NULL && uncle->color==RED)
{
parent->color=BLACK;
uncle->color=BLACK;
grandParent->color=RED;
node=grandParent;
}else{
if(node==parent->left)
{
root=rightRotate(root,parent);
temp=parent;
parent=node;
node=temp;
}
parent->color=BLACK;
grandParent->color=RED;
root=leftRotate(root,grandParent);
}
}
}
root->color=BLACK;
return root;
}
/*红黑树插入节点*/
rb_node_t * rb_insert(rb_node_t *root,int key)
{
rb_node_t *parent,*newNode;
newNode=createNode(key);
if(rb_search_auxiliary(key,root,&parent)!=NULL)
{
printf("already exixt\n");
return root;
}
if(parent==NULL)
{
root=newNode;
}else{
newNode->parent=parent;
if(parent->key<key)
parent->right=newNode;
else
parent->left=newNode;
}
// print(root);
// printf("\n");
root=rb_insert_reblance(root,newNode);
return root;
}
/*删除黑节点后进行调整，使其满足红黑树性质*/
rb_node_t *rb_delete_reblance(rb_node_t *root,rb_node_t *node,rb_node_t *parent)
{
rb_node_t *brother;
while((node==NULL ||node->color==BLACK)&&((node!=root)))
{
if(node==parent->left)
{
brother=parent->right;
if(brother->color==RED)
{
brother->color=BLACK;
parent->color=RED;
root=leftRotate(root,parent);
brother=parent->right;
}
if((!brother->left || brother->left->color==BLACK)&&
(!brother->right || brother->right->color==BLACK))
{
brother->color=RED;
node=parent;
parent=parent->parent;
}else{
if(!brother->right || brother->right->color==BLACK)
{
brother->color=RED;
brother->left->color=BLACK;
root=rightRotate(root,brother);
brother=parent->right;
}
brother->color=parent->color;
parent->color=BLACK;
brother->right->color=BLACK;
root=leftRotate(root,parent);
node=root;
}
}else{
brother=parent->left;
if(brother->color==RED)
{
brother->color=BLACK;
parent->color=RED;
root=rightRotate(root,parent);
brother=parent->left;
}
if((!brother->left ||brother->left->color==BLACK) &&
(!brother->right ||brother->right->color==BLACK))
{
brother->color=RED;
node=parent;
parent=parent->parent;
}else {
if(!brother->left || brother->left->color==BLACK)
{
brother->color=RED;
brother->right->color=BLACK;
root=leftRotate(root,brother);
brother=parent->left;
}
brother->color=parent->color;
parent->color=BLACK;
brother->left->color=BLACK;
root=rightRotate(root,parent);
node=root;
}
}
}
node->color=BLACK;
return root;
}
rb_node_t *rb_delete(rb_node_t *root,int key)
{
rb_node_t *node,*old,*child,*parent;
color_t color;
child=NULL;
if((node=rb_search(key,root))==NULL)
{
printf("not find the node\n");
return root;
}
old=node;
if(node->left!=NULL && node->right!=NULL)
{
node=node->right;
while(node->left!=NULL)
{
node=node->left;
}
child=node->right;
parent=node->parent;
if(child)
child->parent=parent;
if(parent->left==node)
parent->left=child;
else
parent->right=child;
if(node->parent==old)
{
parent=node;
}
color=node->color;
node->left=old->left;
node->right=old->right;
node->color=old->color;
node->parent=old->parent;
if(old->parent)
{
if(old->parent->left==old)
old->parent->left=node;
else
old->parent->right=node;
}else
root=node;
old->left->parent=node;
if(old->right)
old->right->parent=node;
free(old);
}else{
parent=node->parent;
if(node->left!=NULL)
child=node->left;
else
child=node->right;
if(child)
child->parent=parent;
if(parent)
{
if(parent->left==node)
parent->left=child;
else
parent->right=child;
}else
root=child;
color=node->color;
free(node);
}
if(color==BLACK)
rb_delete_reblance(root,child,parent);
return root;
}
int main()
{
int i,count=900000;
int key;
rb_node_t *root=NULL,*node=NULL;
srand(time(NULL));
int num=0;
for(i=1;i<count;++i)
{
key=rand()%count;
if(root=rb_insert(root,key))
{
printf("[i=%d] insert key %d,success!\n",i,key);
}else{
printf("[i=%d] insert key %d error!\n",i,key);
exit(1);
}
// printf("当前树中节点\n");
// midPrint(root);
// printf("\n");
if((node=rb_search(key,root)))
{
printf("[i=%d] search key %d success!\n",i,key);
}else{
printf("[i=%d] search key %d error!\n",i,key);
exit(1);
}
if(!(i%10))
{
// prePrint(root);
if((root=rb_delete(root,key)))
{
printf("[i=%d] delete key %d success\n",i,key);
}else
{
printf("[i=%d] erase key %d error\n",i,key);
exit(1);
}
}
}
/*printf("#########线序遍历\n");
prePrint(root);
printf("\n");
printf("$$$$$$$$$中序遍历\n");
midPrint(root);
printf("\n");
*/
printf("the root color %d\n",root->color);
isRedBlackTree(root,0);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*结构体节点*/
typedef struct _node{
int key;
struct _node *left;
struct _node *right;
struct _node *parent;
}node;
/*插入节点*/
void insert(node *root,node *toInsert)
{
node *p,*q;
p=root;
q=NULL;
if(toInsert==NULL || root==NULL)
{
return;
}
while(p!=NULL)
{
q=p;/*记录父节点*/
if(toInsert->key<p->key)
{
p=p->left;
}else{
p=p->right;
}
}
if(toInsert->key<q->key)
{
q->left=toInsert;
}else{
q->right=toInsert;
}
toInsert->parent=q;
toInsert->left=NULL;
toInsert->right=NULL;
}
/*递归中序遍历根节点*/
void middleSearch(node *root)
{
if(root!=NULL)
{
middleSearch(root->left);
printf("%d\t",root->key);
middleSearch(root->right);
}
}
/*先序遍历*/
void preSearch(node *root)
{
if(root!=NULL)
{
printf("%d\t",root->key);
preSearch(root->left);
preSearch(root->right);
}
}
/*查找返回节点关键字为key的节点*/
node* search(node *root,int key)
{
node *p=root;
while(p!=NULL)
{
if(key<p->key)
{
p=p->left;
}else if(key>p->key)
{
p=p->right;
}else
break;
}
return p;
}
/*查找二叉树最小值*/
node *minimun(node *root)
{
node *p=root;
if(p==NULL)
return p;
while(p->left!=NULL)
p=p->left;
printf("min %d\n",p->key);
return p;
}
/*查找二叉树最大值*/
node *maximun(node *root)
{
node *p=root;
if(p==NULL)
return;
while(p->right!=NULL)
p=p->right;
printf("max %d\n",p->key);
return p;
}
/*找节点后续*/
node* successor(node *x)
{
node *p;
if(NULL==x)
return x;
if(x->right!=NULL)
return minimun(x->right);
p=x->parent;
while(p!=NULL && p->right==x)
{
x=p;
p=p->parent;
}
return p;
}
/*删除节点*/
void delete(node *root,node *toDelete)
{
node *p,*q;
int key;
if(root==NULL || toDelete==NULL)
return ;
p=toDelete->parent;
/*第一种情况，要删除的节点的左右子树都为空*/
if(toDelete->left ==NULL && toDelete->right ==NULL)
{
if(p==NULL)/*要删除的是根节点*/
{
free(toDelete);
return;
}
if(p->left==toDelete)
{
p->left=NULL;
}else
p->right=NULL;
free(toDelete);
}
/*第二种情况，要删除的左子树为空，右子树不为空*/
else if(toDelete->left==NULL)
{
if(p==NULL)
{
q=root->right;
root->key=q->key;
root->left=q->left;
root->right=q->right;
free(q);
return;
}
else if(p->left==toDelete)
{
p->left=toDelete->right;
}else
p->right=toDelete->right;
toDelete->right->parent=p;
free(toDelete);
}
/* 第三种情况，要删除的右子树为空，左子树不为空*/
else if(toDelete->right==NULL)
{
if(p==NULL)
{
q=root->left;
root->key=q->key;
root->left=q->left;
root->right=q->right;
root->parent=NULL;
free(q);
return;
}
else if(p->left==toDelete)
{
p->left=toDelete->left;
}else
p->right=toDelete->right;
toDelete->parent=p;
free(toDelete);
}
/* 第四种情况，要删除的左右子树都不为空*/
else{
q=successor(toDelete);
key=q->key;
delete(root,q);
toDelete->key=key;
}
}
int main()
{
node *root;
int a[12]={15,5,3,12,10,13,6,7,16,20,18,23};
node *toInsert;
node *x,*y;
int i;
/*创建头节点*/
if((root=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
root->key=a[0];
/*插入节点*/
for(i=1;i<12;i++)
{
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=a[i];
insert(root,toInsert);
}
/*中序遍历*/
middleSearch(root);
printf("\n");
/*先序遍历*/
preSearch(root);
printf("\n");
/*最大值*/
maximun(root);
/*最小值*/
minimun(root);
/*查找关键字节点及其前驱*/
x=search(root,6);
y=successor(x);
if(y!=NULL)
printf("节点 6 后驱 %d\n",y->key);
x=search(root,3);
y=successor(x);
if(y!=NULL)
printf("节点 3 后驱 %d\n",y->key);
x=search(root,13);
y=successor(x);
if(y!=NULL)
printf("节点 13 后驱 %d\n",y->key);
x=search(root,23);
y=successor(x);
if(y!=NULL)
printf("节点 23 后驱 %d\n",y->key);
/*删除节点*/
printf("before delete the node\n");
x=search(root,13);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=13;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,16);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=16;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,5);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=5;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,15);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,16);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,18);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,20);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,23);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
}
/*快速排序算法实现，快序排序算法最坏复杂度为O(n^2),平均复杂度为O(nlgn),而且该比例因子比较少*/
#include<stdio.h>
#include<stdlib.h>
void print(int A[],int len)
{
int i;
for(i=0;i<len;i++)
{
printf("%d ",A[i]);
}
printf("\n");
}
int quickPart(int A[],int begin,int end)
{
int key,i,j,temp;
key=A[end-1];
i=begin-1;
for(j=begin;j<end-1;j++)
{
if(A[j]<key)
{
i++;
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
i++;
temp=A[i];
A[i]=key;
A[end-1]=temp;
return (i);
}
void quickSort(int A[],int begin,int end)
{
int q;
if(end>begin)
{
q=quickPart(A,begin,end);
quickSort(A,begin,q);
quickSort(A,q+1,end);
}
}
int main()
{
int A[8]={2,8,7,1,3,5,6,4};
quickSort(A,0,8);
printf("after sort\n");
print(A,8);
}
/*堆排序 实现，算法复杂度O(nlgn)*/
#include<stdio.h>
#include<stdlib.h>
/*假设节点i的左右子树都是最大堆，操作使节点i的子树变成最大堆*/
void maxHeap(int A[],int len,int i)
{
int l,r,large,temp;
l=2*i;
r=2*i+1;
large=i;
if(l<len)
{
if(A[l]>A[i])
{
large=l;
}
}
if(r<len)
{
if(A[r]>A[large])
{
large=r;
}
}
if(large!=i)
{
temp=A[large];
A[large]=A[i];
A[i]=temp;
maxHeap(A,len,large);
}
}
/*建立大根堆*/
void buildMaxHeap(int A[],int len)
{
int i;
for(i=len/2-1;i>=0;i--)
maxHeap(A,len,i);
}
/*堆排序*/
void maxHeapSort(int A[],int len)
{
int i,temp;
buildMaxHeap(A,len);
printf("建立大跟堆\n");
for(i=0;i<len;i++)
printf("%d ",A[i]);
printf("\n");
for(i=len;i>1;i--)
{
temp=A[0];
A[0]=A[i-1];
A[i-1]=temp;
printf("%d ",A[i-1]);
buildMaxHeap(A,i-1);
}
printf("\n");
}
/*测试堆排序*/
int main()
{
int i;
int A[11]={4,1,3,2,16,9,10,14,8,7,6};
maxHeapSort(A,11);
for(i=0;i<11;i++)
{
printf("%d ",A[i]);
}
printf("\n");
}
Linux 下飞鸽传书设计实现
1.系统功能
根据飞鸽传书协议在 linux 下实现飞鸽传输程序,并且与 windows 下飞鸽兼容。具体功能模块包括用户上线,下线,刷新查看在线用户,收发消息,传送文件/文件夹功能模块。
2.具体实现
2.1 关键数据结构
/*命令的结构*/
typedef struct _command
{
int version;/*命令的版本*/
int seq;/*包编号*/
char
srcName[100];/*发送者姓名*/
char
srcHost[100];/*发送者主机名*/
int flag;/*命令*/
char
addtion[100];/*附加字段*/
}command;
/*在线用户信息*/
typedef struct _userInfo
{
char
name[MAXLINE]; /*姓名*/
char
host[MAXLINE]; /*主机名*/
char
group[MAXLINE]; /*所在的组名*/
struct
sockaddr_in addr; /*地址信息*/
struct
_userInfo next; /*链表中下一个*/
}userInfo;
/*在线用户列表*/
typedef struct _uList
{
userInfo
*userListHead; /*链表头*/
userInfo
userListTail; /*链表尾*/
}uList;
/*消息队列*/
typedef struct _mesList
{
command
*mesHead;
command
*mesTail;
}mesList;
2.2 程序主要结构
本程序主要采用多线程结构,分为 receive(接收消息), process(处理收到的消息), sendData(发送文件) 三个子线程。线程间通信互斥锁与 Posix 信号量进行通信。
2.3 函数接口
(1) /*从文件描述符fd中读取count个字符存入buf中*/
ssize_t
readn(int fd,void *buf,size_t count)；
(2) /*将buf所指向的存储区中的len个字符吸入文件描述符fd中*/
ssize_t
writen(int fd,char *buf,int len);
(3) /*用于字符串转换,网络传输中用gb2312编码，linux下gtk用utf-8编码，需要进行转换*/
int
code_convert(char *from_charset,char *to_charset,char *inbuf,int inlen,char
*outbuf,int outlen);
(4) /*在用户链表中加入新用户信息，加入成功返回1，否则返回0,使用userInfoMutex进行线程间通信控制*/
int
pushBack(uList *list,userInfo user);
(5) /*在用户链表中删除指定地址信息的用户，删除成功后返回1，否则返回0，使用userInfoMutex进行线程间控制*/
int
delUser(uList *list, struct sockaddr_in addr);
(6) /*判断该用户是否已经存在，已经存在则返回1，否则返回0,使用userInfoMutex进行线程间控制*/
int isExist(uList *list,struct sockaddr_in addr);
(7)清空用户链表，释放空间，用于用户退出和用户刷新时释放空间,使用userInfoMutex进行线程间控制*/
int destroyList(uList *list);
(8)/*创建命令字,com为要返回的命令字,flag 为消息标志,addtion 为附加标志*/
void createCmd(command & com,int flag,char
addtion[])
(9)/*发送消息，com为要发送的消息，servaddr为要发送的地址，attach为文件附件信息*/
void sendCmd(command com, struct sockaddr_in
servaddr,char attach[]);
(10) /*把收到的消息加入到消息队列中*/
void addMes(mesList *mHead,command cmd);
(11) /*把消息队列中头部的节点消息提取出来用于处理*/
int delMes(mesList *mHead,command *cmd);
(12)/*初始化操作，飞鸽登录时初始化消息链表，用户链表，信号量，套接字信息*/
void init();
(13)/*登录操作,发送用户上线消息*/
void login();
(14)/*解析收到的消息命令，提取各个字段*/
int
analysisCmd(command *cmd,char *buf);
(15) /*接收消息线程处理函数,将收到的消息加入消息队列中，通过信号量waitNoFull和waitNoEmpty和消息处理线程进行通信。消息队列用mesMutex与其他线程进行通信，保证消息队列的正确性*/
void
*receive(void *arg);
(16)/*gtk界面中显示在线用户信息*/
void showUser(uList *list);
(17)/*在gtk界面中显示消息*/
void showMessage(char *message);
(18)/*显示收到的信息*/
void showRecvMessage(char *host,char *message);
(19)/*分析文件的信息，提取有用的字段*/
void fileAnalysis(char *recv,int *fNum,char *fName,int
*fSize,int *fTime,int *fType);
(20) /*保存收到的单个文件,saveName为保存的文件名*/
void saveSignalFile(char *saveName);
(21)/*分析目录附件，获得目录文件的文件名，文件大小，文件类型*/
void getDirInfo(char *recv,char *fName,int *fSize,int
*fType);
(22) /*保存目录,saveName为要保存的目录*/
void saveDir(char *saveName);
(23)/*保存文件,recvType=1为保存文件，recvType=2为保存的目录,使用fileMutex来设置互斥性*/
void saveFile();
(24)/*收到单个文件*/
void receiveSignalFile(char *recvFileName);
(25)/*收到单个目录*/
void receiveDir(char *recvDirName);
(26)/*接收文件*/
void receiveFile(command cmd);
(27)/*信号处理线程,从消息队列中取出消息进行处理*/
void *process(void *arg);
(28)/*发送消息*/
int sendMes();
(29) /*将文件名进行转换*/
char *transName(char *fileName);
(30)/*发送文件*/
void sendFile();
(31)/*发送文件夹*/
void sendDir();
(32)/*用户点击刷新,刷新在线用户*/
void refresh();
(33) /*用户退出*/
void quit();
(34)/*传输文件夹数据，递归函数*/
void transferDir(int fd,char *dir);
(35)/*监听TCP套接口，发送文件与文件夹线程*/
void *sendData(void *arg);
(36)/*创建菜单*/
static void create_popup_menu(GtkWidget
*menu,GtkWidget *view);
(37)/*右击选中treeview,显示传送文件与文件夹菜单*/
static gboolean showTreeView(GtkWidget
*eventBox,GdkEventButton *event,GtkWidget *menu);
(38)/*选择要发送的文件 */
static void selectFile();
(39)/*选择要发送的文件夹*/
static void selectDir();
(40)/*选择要保存的文件名或文件夹名*/
static void selectSaveFile();
3.总结
实现了linux下飞鸽传书的基本功能，并且能与window下飞鸽进行通信，传文件。熟悉了linux下网络编程，多线程编程及线程间通信（主要用到信号量与互斥锁）。但加密解密那块没有完成，程序结构不是很好，界面做得太差。有空应该看看设计模式.
界面截图（界面比较垃圾)：
附：
飞鸽协议： http://bbs.chinaunix.net/viewthread.php?tid=1015775