#
Unix進(jìn)程間通信主要分為（1）消息傳遞 （2）同步 （3）共享內(nèi)存 （4）遠(yuǎn)程調(diào)用
（1）消息傳遞主要有管道，F(xiàn)IFO，消息隊(duì)列
（2）同步主要有互斥鎖與條件變量，讀寫鎖，記錄鎖，信號(hào)量
（3）共享內(nèi)存
（4）遠(yuǎn)程調(diào)用
參考 unix網(wǎng)絡(luò)編程
客戶/服務(wù)器程序設(shè)計(jì)范式有
（1）迭代服務(wù)器（無進(jìn)程控制)
（2）并發(fā)服務(wù)器，每個(gè)客戶請(qǐng)求fork 一個(gè)子進(jìn)程
（3）預(yù)先派生子進(jìn)程，每個(gè)子進(jìn)程無保護(hù)地調(diào)用accept
（4）預(yù)先派生子進(jìn)程，使用文件上鎖保護(hù)accept
（5）預(yù)先派生子進(jìn)程，使用線程互斥鎖保護(hù)accept（共享內(nèi)存)
（6）預(yù)先派生子進(jìn)程，父進(jìn)程向子進(jìn)程傳遞套接口描述字
（7）并發(fā)服務(wù)器，每個(gè)客戶請(qǐng)求創(chuàng)建一個(gè)線程
（8）預(yù)先創(chuàng)建線程服務(wù)器，使用互斥鎖上鎖保護(hù)accept
（9）預(yù)先創(chuàng)建線程服務(wù)器，由主線程調(diào)用accept.
測試用例 客戶創(chuàng)建5個(gè)進(jìn)程，每個(gè)發(fā)起500個(gè)連接，每個(gè)連接寫四個(gè)字節(jié)數(shù)據(jù)
總的用戶時(shí)間（秒） 總的系統(tǒng)時(shí)間（秒）
（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
最長公共子序列實(shí)現(xiàn)
參考算法導(dǎo)論第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;
}
}
}
/*輸出矩陣結(jié)果*/
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);
}
矩陣鏈乘法實(shí)現(xiàn)（算法導(dǎo)論 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);
}
動(dòng)態(tài)規(guī)劃是通過組合子問題的解而解決整個(gè)問題。
動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)可以分為4個(gè)步驟
（1）描述最優(yōu)解的結(jié)構(gòu)
（2）遞歸定義最優(yōu)解的值
（3）按自底向上的方式計(jì)算最優(yōu)解的值
（4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解
裝配線調(diào)度實(shí)現(xiàn)(算法導(dǎo)論192頁)
參考算法導(dǎo)論 第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);
}
/*紅黑樹設(shè)計(jì)與實(shí)現(xiàn)
*參考算法導(dǎo)論
*http://www.shnenglu.com/converse/archive/2008/11/10/66530.html
插入時(shí)有三種情況（這里只考慮z的父節(jié)點(diǎn)是z的祖父節(jié)點(diǎn)的左孩子，z的父節(jié)點(diǎn)是z的祖父節(jié)點(diǎn)的右孩子對(duì)稱也一樣）
（1） z的叔叔y是紅色的（改變顏色,提升x）
（2） z的叔叔y是黑色的，而且z是右孩子（左旋）
（3） z的叔叔y是黑色的，而且z是左孩子（右旋加改變顏色）
刪除時(shí)有四種情況（這里只考慮z是z的父節(jié)點(diǎn)的左孩子，z是z的父節(jié)點(diǎn)的右孩子對(duì)稱也一樣）
（1）x的兄弟w是紅色的（左旋加改變顏色）
（2）x的兄弟w是黑色的，而且w的兩個(gè)孩子都是黑色的（改變顏色，提升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;
/*定義結(jié)構(gòu)體*/
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);
}
}
/*中序打印節(jié)點(diǎn)用于測試*/
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);
}
}
/*先序打印節(jié)點(diǎn)用于測試*/
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);
}
}
/*創(chuàng)建節(jié)點(diǎn)*/
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;
}
/*查找節(jié)點(diǎn)，若找到則返回該節(jié)點(diǎn)，若沒找到返回NULL并且將父節(jié)點(diǎn)保存到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;
}
/*查找節(jié)點(diǎn)*/
rb_node_t * rb_search(int key,rb_node_t *root)
{
return rb_search_auxiliary(key,root,NULL);
}
/*插入節(jié)點(diǎn)后進(jìn)行調(diào)整，使其滿足紅黑樹性質(zhì)*/
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;
}
/*紅黑樹插入節(jié)點(diǎn)*/
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;
}
/*刪除黑節(jié)點(diǎn)后進(jìn)行調(diào)整，使其滿足紅黑樹性質(zhì)*/
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("當(dāng)前樹中節(jié)點(diǎn)\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>
/*結(jié)構(gòu)體節(jié)點(diǎn)*/
typedef struct _node{
int key;
struct _node *left;
struct _node *right;
struct _node *parent;
}node;
/*插入節(jié)點(diǎn)*/
void insert(node *root,node *toInsert)
{
node *p,*q;
p=root;
q=NULL;
if(toInsert==NULL || root==NULL)
{
return;
}
while(p!=NULL)
{
q=p;/*記錄父節(jié)點(diǎn)*/
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;
}
/*遞歸中序遍歷根節(jié)點(diǎn)*/
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);
}
}
/*查找返回節(jié)點(diǎn)關(guān)鍵字為key的節(jié)點(diǎn)*/
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;
}
/*找節(jié)點(diǎn)后續(xù)*/
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;
}
/*刪除節(jié)點(diǎn)*/
void delete(node *root,node *toDelete)
{
node *p,*q;
int key;
if(root==NULL || toDelete==NULL)
return ;
p=toDelete->parent;
/*第一種情況，要?jiǎng)h除的節(jié)點(diǎn)的左右子樹都為空*/
if(toDelete->left ==NULL && toDelete->right ==NULL)
{
if(p==NULL)/*要?jiǎng)h除的是根節(jié)點(diǎn)*/
{
free(toDelete);
return;
}
if(p->left==toDelete)
{
p->left=NULL;
}else
p->right=NULL;
free(toDelete);
}
/*第二種情況，要?jiǎng)h除的左子樹為空，右子樹不為空*/
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);
}
/* 第三種情況，要?jiǎng)h除的右子樹為空，左子樹不為空*/
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);
}
/* 第四種情況，要?jiǎng)h除的左右子樹都不為空*/
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;
/*創(chuàng)建頭節(jié)點(diǎn)*/
if((root=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
root->key=a[0];
/*插入節(jié)點(diǎn)*/
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);
/*查找關(guān)鍵字節(jié)點(diǎn)及其前驅(qū)*/
x=search(root,6);
y=successor(x);
if(y!=NULL)
printf("節(jié)點(diǎn) 6 后驅(qū) %d\n",y->key);
x=search(root,3);
y=successor(x);
if(y!=NULL)
printf("節(jié)點(diǎn) 3 后驅(qū) %d\n",y->key);
x=search(root,13);
y=successor(x);
if(y!=NULL)
printf("節(jié)點(diǎn) 13 后驅(qū) %d\n",y->key);
x=search(root,23);
y=successor(x);
if(y!=NULL)
printf("節(jié)點(diǎn) 23 后驅(qū) %d\n",y->key);
/*刪除節(jié)點(diǎn)*/
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");
}
/*快速排序算法實(shí)現(xiàn)，快序排序算法最壞復(fù)雜度為O(n^2),平均復(fù)雜度為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);
}
/*堆排序 實(shí)現(xiàn)，算法復(fù)雜度O(nlgn)*/
#include<stdio.h>
#include<stdlib.h>
/*假設(shè)節(jié)點(diǎn)i的左右子樹都是最大堆，操作使節(jié)點(diǎn)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 下飛鴿傳書設(shè)計(jì)實(shí)現(xiàn)
1.系統(tǒng)功能
根據(jù)飛鴿傳書協(xié)議在 linux 下實(shí)現(xiàn)飛鴿傳輸程序,并且與 windows 下飛鴿兼容。具體功能模塊包括用戶上線,下線,刷新查看在線用戶,收發(fā)消息,傳送文件/文件夾功能模塊。
2.具體實(shí)現(xiàn)
2.1 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)
/*命令的結(jié)構(gòu)*/
typedef struct _command
{
int version;/*命令的版本*/
int seq;/*包編號(hào)*/
char
srcName[100];/*發(fā)送者姓名*/
char
srcHost[100];/*發(fā)送者主機(jī)名*/
int flag;/*命令*/
char
addtion[100];/*附加字段*/
}command;
/*在線用戶信息*/
typedef struct _userInfo
{
char
name[MAXLINE]; /*姓名*/
char
host[MAXLINE]; /*主機(jī)名*/
char
group[MAXLINE]; /*所在的組名*/
struct
sockaddr_in addr; /*地址信息*/
struct
_userInfo next; /*鏈表中下一個(gè)*/
}userInfo;
/*在線用戶列表*/
typedef struct _uList
{
userInfo
*userListHead; /*鏈表頭*/
userInfo
userListTail; /*鏈表尾*/
}uList;
/*消息隊(duì)列*/
typedef struct _mesList
{
command
*mesHead;
command
*mesTail;
}mesList;
2.2 程序主要結(jié)構(gòu)
本程序主要采用多線程結(jié)構(gòu),分為 receive(接收消息), process(處理收到的消息), sendData(發(fā)送文件) 三個(gè)子線程。線程間通信互斥鎖與 Posix 信號(hào)量進(jìn)行通信。
2.3 函數(shù)接口
(1) /*從文件描述符fd中讀取count個(gè)字符存入buf中*/
ssize_t
readn(int fd,void *buf,size_t count)；
(2) /*將buf所指向的存儲(chǔ)區(qū)中的len個(gè)字符吸入文件描述符fd中*/
ssize_t
writen(int fd,char *buf,int len);
(3) /*用于字符串轉(zhuǎn)換,網(wǎng)絡(luò)傳輸中用gb2312編碼，linux下gtk用utf-8編碼，需要進(jìn)行轉(zhuǎn)換*/
int
code_convert(char *from_charset,char *to_charset,char *inbuf,int inlen,char
*outbuf,int outlen);
(4) /*在用戶鏈表中加入新用戶信息，加入成功返回1，否則返回0,使用userInfoMutex進(jìn)行線程間通信控制*/
int
pushBack(uList *list,userInfo user);
(5) /*在用戶鏈表中刪除指定地址信息的用戶，刪除成功后返回1，否則返回0，使用userInfoMutex進(jìn)行線程間控制*/
int
delUser(uList *list, struct sockaddr_in addr);
(6) /*判斷該用戶是否已經(jīng)存在，已經(jīng)存在則返回1，否則返回0,使用userInfoMutex進(jìn)行線程間控制*/
int isExist(uList *list,struct sockaddr_in addr);
(7)清空用戶鏈表，釋放空間，用于用戶退出和用戶刷新時(shí)釋放空間,使用userInfoMutex進(jìn)行線程間控制*/
int destroyList(uList *list);
(8)/*創(chuàng)建命令字,com為要返回的命令字,flag 為消息標(biāo)志,addtion 為附加標(biāo)志*/
void createCmd(command & com,int flag,char
addtion[])
(9)/*發(fā)送消息，com為要發(fā)送的消息，servaddr為要發(fā)送的地址，attach為文件附件信息*/
void sendCmd(command com, struct sockaddr_in
servaddr,char attach[]);
(10) /*把收到的消息加入到消息隊(duì)列中*/
void addMes(mesList *mHead,command cmd);
(11) /*把消息隊(duì)列中頭部的節(jié)點(diǎn)消息提取出來用于處理*/
int delMes(mesList *mHead,command *cmd);
(12)/*初始化操作，飛鴿登錄時(shí)初始化消息鏈表，用戶鏈表，信號(hào)量，套接字信息*/
void init();
(13)/*登錄操作,發(fā)送用戶上線消息*/
void login();
(14)/*解析收到的消息命令，提取各個(gè)字段*/
int
analysisCmd(command *cmd,char *buf);
(15) /*接收消息線程處理函數(shù),將收到的消息加入消息隊(duì)列中，通過信號(hào)量waitNoFull和waitNoEmpty和消息處理線程進(jìn)行通信。消息隊(duì)列用mesMutex與其他線程進(jìn)行通信，保證消息隊(duì)列的正確性*/
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) /*保存收到的單個(gè)文件,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來設(shè)置互斥性*/
void saveFile();
(24)/*收到單個(gè)文件*/
void receiveSignalFile(char *recvFileName);
(25)/*收到單個(gè)目錄*/
void receiveDir(char *recvDirName);
(26)/*接收文件*/
void receiveFile(command cmd);
(27)/*信號(hào)處理線程,從消息隊(duì)列中取出消息進(jìn)行處理*/
void *process(void *arg);
(28)/*發(fā)送消息*/
int sendMes();
(29) /*將文件名進(jìn)行轉(zhuǎn)換*/
char *transName(char *fileName);
(30)/*發(fā)送文件*/
void sendFile();
(31)/*發(fā)送文件夾*/
void sendDir();
(32)/*用戶點(diǎn)擊刷新,刷新在線用戶*/
void refresh();
(33) /*用戶退出*/
void quit();
(34)/*傳輸文件夾數(shù)據(jù)，遞歸函數(shù)*/
void transferDir(int fd,char *dir);
(35)/*監(jiān)聽TCP套接口，發(fā)送文件與文件夾線程*/
void *sendData(void *arg);
(36)/*創(chuàng)建菜單*/
static void create_popup_menu(GtkWidget
*menu,GtkWidget *view);
(37)/*右擊選中treeview,顯示傳送文件與文件夾菜單*/
static gboolean showTreeView(GtkWidget
*eventBox,GdkEventButton *event,GtkWidget *menu);
(38)/*選擇要發(fā)送的文件 */
static void selectFile();
(39)/*選擇要發(fā)送的文件夾*/
static void selectDir();
(40)/*選擇要保存的文件名或文件夾名*/
static void selectSaveFile();
3.總結(jié)
實(shí)現(xiàn)了linux下飛鴿傳書的基本功能，并且能與window下飛鴿進(jìn)行通信，傳文件。熟悉了linux下網(wǎng)絡(luò)編程，多線程編程及線程間通信（主要用到信號(hào)量與互斥鎖）。但加密解密那塊沒有完成，程序結(jié)構(gòu)不是很好，界面做得太差。有空應(yīng)該看看設(shè)計(jì)模式.
界面截圖（界面比較垃圾)：
附：
飛鴿協(xié)議： http://bbs.chinaunix.net/viewthread.php?tid=1015775