#
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.shnenglu.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