青春的岁月

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

typedef struct node{
int num;
struct node* nex_ptr;
struct node* pre_ptr;
}NODE;

typedef struct list{
char pare;
int charnum;
int length;
NODE head,tail;
}LIST;

int initlist(LIST* list){
list->head.pre_ptr=NULL;list->head.nex_ptr=NULL;
list->tail.nex_ptr=NULL;
list->charnum=0;
list->length=0;
return 1;
}

int addnum(LIST* list,int num){
NODE* ptr=malloc(sizeof(NODE));
ptr->num=num;
if(list->head.nex_ptr==NULL){
list->head.nex_ptr=ptr;list->tail.pre_ptr=ptr;
ptr->pre_ptr=&(list->head);ptr->nex_ptr=&(list->tail);
}else{
ptr->pre_ptr=list->tail.pre_ptr;ptr->nex_ptr=&(list->tail);
list->tail.pre_ptr->nex_ptr=ptr;list->tail.pre_ptr=ptr;
}
return 1;
}

int createlist(LIST* list){
char c;
int cal=0,num=0;
int charnum=0,length=0;
scanf("%c",&c);
list->pare=c;
while(scanf("%c",&c) && c != '#'){
if( c != ',' ){
list->charnum++;
num *= 10;
num += c-'0' ;
}else{
addnum(list,num);
list->length++;
num = 0;
}

}
return 1;
}

int addlist(LIST* list1,LIST* list2,LIST* list3){
int num=0,flag=0;
NODE* ptr1=list1->tail.pre_ptr;
NODE* ptr2=list2->tail.pre_ptr;
NODE* ptr3=list3->tail.pre_ptr;
while( ptr2->pre_ptr != NULL ){
if( ptr1->num + ptr2->num + flag >= 10000 ){
num = ptr1->num + ptr2->num + flag -10000;
addnum(list3,num);
flag=1;
}else{
num = ptr1->num + ptr2->num + flag;
addnum(list3,num);
flag=0;
}
ptr1=ptr1->pre_ptr;
ptr2=ptr2->pre_ptr;
num=0;
}

while( ptr1->pre_ptr != NULL ){
if( ptr1->num + flag >= 10000 ){
num = ptr1->num + flag - 10000;
addnum(list3,num);
flag=1;
}else{
num = ptr1->num + flag;
addnum(list3,num);
flag=0;
}
ptr1=ptr1->pre_ptr;
num=0;
}

if(flag){
addnum(list3,flag);
}
return 1;
}

int sublist(LIST* list1,LIST* list2,LIST* list3){
int num,flag=0;
NODE* ptr1=list1->tail.pre_ptr;
NODE* ptr2=list2->tail.pre_ptr;
NODE* ptr3=list3->tail.pre_ptr;
while( ptr2->pre_ptr != NULL ){
if( ptr1->num + flag < ptr2->num ){
num=10000 + ptr1->num + flag - ptr2->num;
addnum(list3,num);
flag=-1;
}else{
num = ptr1->num + flag - ptr2->num;
addnum(list3,num);
flag=0;
}

ptr1=ptr1->pre_ptr;
ptr2=ptr2->pre_ptr;
num=0;
}

while( ptr1->pre_ptr != NULL ){
if( ptr1->num + flag < 0 ){
num=10000 + ptr1->num + flag;
addnum(list3,num);
flag = -1;
}else{
num=ptr1->num + flag;
addnum(list3,num);
flag = 0;
}
ptr1=ptr1->pre_ptr;
num=0;
}

return 1;
}

int bigthen(LIST* list1,LIST* list2){
NODE *ptr1=list1->head.nex_ptr,*ptr2=list2->head.nex_ptr;
if( list1->charnum > list2->charnum ) return 1;
if( list1->charnum == list2->charnum ){
while( ptr1->nex_ptr != NULL ){
if( ptr1->num > ptr2->num ) return 1;
if( ptr1->num < ptr2->num ) return 0;
ptr1=ptr1->nex_ptr;ptr2=ptr2->nex_ptr;
}
}
return 0;
}

int calist(LIST* list1,LIST* list2,LIST* list3){
int flag=bigthen(list1,list2);
if( flag ){
if( list1->pare == '+' && list2->pare == '+' )
{ sublist(list1,list2,list3);list3->pare='+';}
else if( list1->pare == '+' && list2->pare == '-' )
{ addlist(list1,list2,list3);list3->pare='+';}
else if( list1->pare == '-' && list2->pare == '+' )
{ addlist(list1,list2,list3);list3->pare='-';}
else if( list1->pare == '-' && list2->pare == '-' )
{ sublist(list1,list2,list3);list3->pare = '-';}
}
else{
calist(list2,list1,list3);
if( list3->pare == '+' )
list3->pare = '-';
elselist3->pare = '+';
}
return 1;
}

int trav_list_bak(LIST* list){
NODE* ptr=list->tail.pre_ptr;
printf("%c",list->pare);
while(ptr->pre_ptr != NULL){
if( ptr->num >= 1000 )
printf("%d,",ptr->num);
else if( ptr->num >= 100 )
printf("0%d,",ptr->num);
else if( ptr->num >= 10 )
printf("00%d,",ptr->num);
else if( ptr->num >=0 )
printf("000%d,",ptr->num);
ptr=ptr->pre_ptr;
}
return 1;
}

int main(){
LIST list1,list2,list3;
initlist(&list1);initlist(&list2);initlist(&list3);
int i=1;
while(i){
printf("put num as formate +/-xxxx,xxxx,....,#+/-xxxx,xxxx,#\n");
createlist(&list1);
createlist(&list2);
printf("--------------------\n");
calist(&list1,&list2,&list3);
trav_list_bak(&list3);
printf("\ndo your want to continue,1 for yes,0 for no ?\n");
scanf("%d", &i);
printf("\n");
}
return 0;
}

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

typedef union value{
char alg;
int num;
}VAL;

typedef struct node{
int type;
VAL content;
struct node* pre_ptr;
struct node* nex_ptr;
}NODE;

typedef struct list{
int length;
NODE head,tail;
}LIST;

int initlist(LIST* list){
list->head.type=0;list->head.content.alg='(';
list->tail.type=0;list->tail.content.alg=')';
list->head.pre_ptr=NULL;
list->head.nex_ptr=NULL;
list->tail.nex_ptr=NULL;
list->length=0;
return 1;
}

int creatnode(LIST* list,NODE* val){
if( list->head.nex_ptr==NULL ){
val->pre_ptr=&(list->head);val->nex_ptr=&(list->tail);
list->head.nex_ptr=val;list->tail.pre_ptr=val;
}else{
val->pre_ptr=list->tail.pre_ptr;val->nex_ptr=&(list->tail);
list->tail.pre_ptr->nex_ptr=val;list->tail.pre_ptr=val;
}
list->length++;
return 1;
}


int createlist(LIST* list){
int flag=1;
char c;
NODE* ptr;
while(scanf("%c",&c) && c != '='){
if( c=='+' || c=='-' || c=='x' || c=='/' || c=='(' || c==')' ){
ptr=malloc(sizeof(NODE));
ptr->type=0;ptr->content.alg=c;
creatnode(list,ptr);
flag=1;
}else if( c>=48 && c<=57 ){
int bit=c-48;
if(flag){
ptr=malloc(sizeof(NODE));
ptr->type=1;ptr->content.num=bit;
creatnode(list,ptr);
flag=0;
}else{
list->tail.pre_ptr->content.num *= 10;
list->tail.pre_ptr->content.num += bit;
flag=0;
}
}
}
return 1;
}

int calpare(NODE* node){
int num;
NODE *ptr,*ptr_bak=node;
node=node->nex_ptr;

//printf("num:%d",node->content.num);
while( !( node->type == 0 && node->content.alg == ')' ) ){
if( node->type == 0 && (node->content.alg == 'x'||node->content.alg == '/') ){
if(node->content.alg == 'x'){
num=(node->pre_ptr->content.num) * (node->nex_ptr->content.num);
}
if(node->content.alg == '/'){
if( node->nex_ptr->content.num==0 ){printf("div can not be zero !");return 0;}
num=(node->pre_ptr->content.num) / (node->nex_ptr->content.num);
}
ptr=malloc(sizeof(NODE));
ptr->type=1;ptr->content.num=num;

ptr->pre_ptr=node->pre_ptr->pre_ptr;ptr->nex_ptr=node->nex_ptr->nex_ptr;
node->pre_ptr->pre_ptr->nex_ptr=ptr;node->nex_ptr->nex_ptr->pre_ptr=ptr;

free(node->pre_ptr);free(node->nex_ptr);
free(node);node=ptr;
}
node=node->nex_ptr;
}


node=ptr_bak->nex_ptr;
while( !( node->type == 0 && node->content.alg == ')' ) ){
if( node->type == 0 && (node->content.alg == '+'||node->content.alg == '-') ){
if(node->content.alg == '+'){
num=(node->pre_ptr->content.num) + (node->nex_ptr->content.num);
}
if(node->content.alg == '-'){
num=(node->pre_ptr->content.num) - (node->nex_ptr->content.num);
}
ptr=malloc(sizeof(NODE));
ptr->type=1;ptr->content.num=num;

ptr->pre_ptr=node->pre_ptr->pre_ptr;ptr->nex_ptr=node->nex_ptr->nex_ptr;
node->pre_ptr->pre_ptr->nex_ptr=ptr;node->nex_ptr->nex_ptr->pre_ptr=ptr;

free(node->pre_ptr);free(node->nex_ptr);
free(node);node=ptr;
}
node=node->nex_ptr;
}


return 1;
}

int rmpare(LIST* list){
NODE *ptr,*tmp;
ptr=&(list->tail);
while(ptr->pre_ptr!=NULL){
if( ptr->type == 0 && ptr->content.alg == '(' ) {calpare(ptr);}
ptr=ptr->pre_ptr;
}

ptr=list->head.nex_ptr;
while( ptr->nex_ptr != NULL ){
if( ptr->type==0 && ( ptr->content.alg=='(' || ptr->content.alg==')' ) ){
ptr->pre_ptr->nex_ptr=ptr->nex_ptr;ptr->nex_ptr->pre_ptr=ptr->pre_ptr;
tmp=ptr;ptr=ptr->nex_ptr;
free(tmp);
continue;
}
ptr=ptr->nex_ptr;
}
calpare(&(list->head));
printf("the result is %d\n",list->head.nex_ptr->content.num);
}

int travel_list(LIST* list){
NODE* ptr=list->head.nex_ptr;
printf("\n");
while(ptr->nex_ptr != NULL){
if(ptr->type){
printf("%d,%d",ptr->type,ptr->content.num);
}else{
printf("%d,%c",ptr->type,ptr->content.alg);
}
ptr=ptr->nex_ptr;
printf("\n");
}
printf("\n");
return 1;
}


int main(){
LIST list;
initlist(&list);
createlist(&list);
NODE* ptr;
ptr=&(list.tail);

rmpare(&list);
return 0;
}


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

typedef union numorchar{
int num;
char pare;
}NUMORCHAR;

typedef struct node{
int type;
NUMORCHAR content;
struct node* nex_ptr;
}NODE;

typedef struct stack{
NODE head;
NODE* tail;
}STACK;

int initstack(STACK* stack){
stack->head.type=0;
stack->head.content.pare='#';
stack->head.nex_ptr=NULL;
stack->tail=&(stack->head);
return 1;
}

int pushchar(STACK* stack,char c){
NODE* ptr=malloc(sizeof(NODE));
ptr->content.pare=c;
switch (c)
{
case '#'tr->type=0;
break;
case '+'tr->type=2;
break;
case '-'tr->type=2;
break;
case '*'tr->type=4;
break;
case '/'tr->type=4;
break;
case '('tr->type=8;
break;
case ')'tr->type=1;
break;
}
stack->tail->nex_ptr=ptr;
stack->tail=ptr;stack->tail->nex_ptr=NULL;
return 1;
}


int pushchar_in(STACK* stack,char c){
NODE* ptr=malloc(sizeof(NODE));
ptr->content.pare=c;
switch (c)
{
case '#'tr->type=0;
break;
case '+'tr->type=3;
break;
case '-'tr->type=3;
break;
case '*'tr->type=5;
break;
case '/'tr->type=5;
break;
case '('tr->type=1;
break;
case ')'tr->type=8;
break;
}
stack->tail->nex_ptr=ptr;
stack->tail=ptr;stack->tail->nex_ptr=NULL;
return 1;
}

int pushint(STACK* stack,int n){
NODE* ptr=malloc(sizeof(NODE));
ptr->type=9;ptr->content.num=n;
stack->tail->nex_ptr=ptr;
stack->tail=ptr;stack->tail->nex_ptr=NULL;
return 1;
}

char popchar(STACK* stack){
NODE* ptr=&(stack->head);
while( ptr->nex_ptr != stack->tail ){ ptr=ptr->nex_ptr ;}
stack->tail=ptr;ptr=ptr->nex_ptr;
char c=ptr->content.pare;
free(ptr);stack->tail->nex_ptr=NULL;
return c;
}

int popint(STACK* stack){
NODE* ptr=&(stack->head);
while( ptr->nex_ptr != stack->tail ){ ptr=ptr->nex_ptr ;}
stack->tail=ptr;ptr=ptr->nex_ptr;
int n=ptr->content.num;
free(ptr);stack->tail->nex_ptr=NULL;
return n;
}

int createstack( STACK* stack){
char c;
int num,flag=1;
NODE* ptr;
while( scanf("%c",&c) ){
if( c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#' || c=='=' ){
if(!flag) pushint(stack,num);
if(c == '=') break;
pushchar(stack,c);flag=1;
}else if( c>=48 && c<=57 ){
int bit=c-48;
if( flag ){
num=bit;
}else{
num *= 10;
num +=bit;
}
flag=0;
}
}
return 1;
}

int fixpost(STACK* stack1,STACK* stack2,STACK* stack3){
NODE* ptr=stack1->head.nex_ptr;
while(1){
if( ptr->type == 9 ){
pushint(stack2,ptr->content.num);
}else{
if( ptr->type > stack3->tail->type){
pushchar_in(stack3,ptr->content.pare);
}else{
while( ptr->type <= stack3->tail->type ){
pushchar(stack2,popchar(stack3));
}
pushchar_in(stack3,ptr->content.pare);
}
}
if( ptr->nex_ptr == NULL ){
while( stack3->tail->content.pare != '#' ){
pushchar(stack2,popchar(stack3));
}
break;
}
ptr=ptr->nex_ptr;
}
return 1;
}

int cal(STACK* stack1,STACK* stack2){
NODE* ptr=stack1->head.nex_ptr;
int num,num1,num2;
while(1){
if(ptr->type == 9){
pushint(stack2,ptr->content.num);
}else{
switch (ptr->content.pare)
{
case '+':num1=popint(stack2);num2=popint(stack2);
num=num2+num1;pushint(stack2,num);break;
case '-':num1=popint(stack2);num2=popint(stack2);
num=num2-num1;pushint(stack2,num);break;
case '*':num1=popint(stack2);num2=popint(stack2);
num=num2*num1;pushint(stack2,num);break;
case '/':num1=popint(stack2);num2=popint(stack2);
num=num2/num1;pushint(stack2,num);break;
}
}
if(ptr->nex_ptr == NULL){
printf("the result is %d\n",stack2->head.nex_ptr->content.num);
break;
}
ptr=ptr->nex_ptr;
}
return 1;
}

int trav_stack(STACK* stack){
NODE* ptr=&(stack->head);
while(1){
if( ptr->type == 9 ){
printf("%d,%d\n",ptr->type,ptr->content.num);
}else{
printf("%d,%c\n",ptr->type,ptr->content.pare);
}
if( ptr->nex_ptr == NULL ) break;
ptr=ptr->nex_ptr;
}
return 1;
}

int main(){
int an=1;
STACK stack1,stack2,stack3,stack4;
initstack(&stack1);initstack(&stack2);initstack(&stack3);initstack(&stack4);
createstack(&stack1);
printf("----------------------\n");
fixpost(&stack1,&stack2,&stack3);
cal(&stack2,&stack4);
return 0;
}

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

typedef struct customer{
int arrive_time;
int need_service_time;
int waiting_time;
struct customer* nex_ptr;
}CUSTOMER;

//--------------------------------------------

typedef struct customer_queue{
int teller_service_customers;
int teller_service_time;
int teller_waiting_list_time;
int teller_waiting_time_all;
int teller_free_time;
CUSTOMER head;
CUSTOMER tail;
}CUSTOMER_QUEUE;

int init_customer_queue(CUSTOMER_QUEUE* queue){
queue->teller_service_time=0;
queue->teller_waiting_list_time=0;
queue->teller_service_customers=0;
queue->teller_waiting_time_all=0;
queue->head.nex_ptr=&(queue->tail);
queue->head.arrive_time=0;queue->head.waiting_time=0;
queue->tail.arrive_time=1001;queue->tail.waiting_time=0;
queue->tail.nex_ptr=NULL;
return 1;
}

int customer_queue_in(CUSTOMER_QUEUE* queue,CUSTOMER* customer){
if(queue->head.nex_ptr == &(queue->tail)){
queue->head.nex_ptr=customer;
customer->nex_ptr=&(queue->tail);
}else{
customer->nex_ptr=queue->head.nex_ptr;
queue->head.nex_ptr=customer;
}
return 1;
}

int customer_queue_out(CUSTOMER_QUEUE* queue){
CUSTOMER* ptr=&(queue->head);
if( ptr->nex_ptr == &(queue->tail)){
return 0;
}else{
while(ptr->nex_ptr->nex_ptr != &(queue->tail) ) ptr=ptr->nex_ptr;
ptr->nex_ptr=&(queue->tail);
}
return 1;
}

CUSTOMER_QUEUE* least_waiting_time(CUSTOMER_QUEUE* queue1,CUSTOMER_QUEUE* queue2,
CUSTOMER_QUEUE* queue3,CUSTOMER_QUEUE* queue4){
CUSTOMER_QUEUE* ptr=queue1;
if( ptr->teller_waiting_list_time > queue2->teller_waiting_list_time ) ptr=queue2;
if( ptr->teller_waiting_list_time > queue3->teller_waiting_list_time ) ptr=queue3;
if( ptr->teller_waiting_list_time > queue4->teller_waiting_list_time ) ptr=queue4;
return ptr;
}

int max_waiting_list_time(CUSTOMER_QUEUE* queue1,CUSTOMER_QUEUE* queue2,
CUSTOMER_QUEUE* queue3,CUSTOMER_QUEUE* queue4){
int waiting_list_time=queue1->teller_waiting_list_time;
if( queue2->teller_waiting_list_time > waiting_list_time ) waiting_list_time=queue2->teller_waiting_list_time;
if( queue3->teller_waiting_list_time > waiting_list_time ) waiting_list_time=queue3->teller_waiting_list_time;
if( queue4->teller_waiting_list_time > waiting_list_time ) waiting_list_time=queue4->teller_waiting_list_time;
return waiting_list_time;
}
//--------------------------------------------

typedef struct customer_list{
CUSTOMER head;
CUSTOMER tail;
}CUSTOMER_LIST;

int create_customer_list(CUSTOMER_LIST* customer_list){
int arrivetime,needservicetime;
srand((unsigned)time(NULL));
CUSTOMER *ptr1,*ptr2;
customer_list->head.nex_ptr=&(customer_list->tail);customer_list->tail.nex_ptr=NULL;
customer_list->head.arrive_time=0;customer_list->tail.arrive_time=1001;
int i=1;
while(i <= 100){
arrivetime=rand()%100+1;needservicetime=(rand()%3+1)*5;
ptr1=malloc(sizeof(CUSTOMER));
ptr1->arrive_time=arrivetime;ptr1->need_service_time=needservicetime;
ptr1->waiting_time=0;
ptr2=&(customer_list->head);
while(ptr1->arrive_time > ptr2->nex_ptr->arrive_time)ptr2=ptr2->nex_ptr;
ptr1->nex_ptr=ptr2->nex_ptr;ptr2->nex_ptr=ptr1;
i++;
}
return 1;
}

CUSTOMER* pop_customer_list(CUSTOMER_LIST* customer_list){
CUSTOMER* ptr;
if(customer_list->head.nex_ptr == &(customer_list->tail)){
return &(customer_list->tail);
}else{
ptr=customer_list->head.nex_ptr;
customer_list->head.nex_ptr=ptr->nex_ptr;
return ptr;
}
}

//--------------------------------------------

int out_queue(CUSTOMER_QUEUE* queue1,int timeout){
int i=10;
CUSTOMER* ptr;
if( queue1->teller_waiting_list_time == timeout ){
queue1->teller_waiting_list_time = 0;
queue1->teller_service_time += timeout;
while( customer_queue_out(queue1) ) ;
}else if( queue1->teller_waiting_list_time < timeout ){
queue1->teller_service_time += queue1->teller_waiting_list_time;
queue1->teller_waiting_list_time = 0;
while( customer_queue_out(queue1) ) ;
}else if( queue1->teller_waiting_list_time > timeout ){
queue1->teller_service_time += timeout;
queue1->teller_waiting_list_time -= timeout;
while(1){
ptr=&(queue1->head);
while(ptr->nex_ptr != &(queue1->tail) ) ptr=ptr->nex_ptr;
if( timeout >= ptr->need_service_time ){
timeout=timeout - ptr->need_service_time;
customer_queue_out(queue1);
}else{
ptr->need_service_time -= timeout; break;
}

}
}

return 1;
}

int out(CUSTOMER_QUEUE* queue1,CUSTOMER_QUEUE* queue2,
CUSTOMER_QUEUE* queue3,CUSTOMER_QUEUE* queue4,int timeout){
out_queue(queue1,timeout);out_queue(queue2,timeout);
out_queue(queue3,timeout);out_queue(queue4,timeout);
return 1;
}

int in(CUSTOMER_QUEUE* queue1,CUSTOMER_QUEUE* queue2,
CUSTOMER_QUEUE* queue3,CUSTOMER_QUEUE* queue4,CUSTOMER* customer){
CUSTOMER_QUEUE* ptr=least_waiting_time(queue1,queue2,queue3,queue4);
customer->waiting_time = ptr->teller_waiting_list_time;
ptr->teller_waiting_list_time += customer->need_service_time;
ptr->teller_service_customers++;ptr->teller_waiting_time_all += customer->waiting_time;
customer_queue_in(ptr,customer);
return 1;
}

int run(CUSTOMER_LIST* customer_list,CUSTOMER_QUEUE* queue1,CUSTOMER_QUEUE* queue2,
CUSTOMER_QUEUE* queue3,CUSTOMER_QUEUE* queue4){
int waiting_list_time;
CUSTOMER* ptr;
int time=0,timeout;
while(1){
ptr=pop_customer_list(customer_list);
if( ptr == &(customer_list->tail) ) break;
timeout=ptr->arrive_time-time;
out(queue1,queue2,queue3,queue4,timeout);
in(queue1,queue2,queue3,queue4,ptr);
time=ptr->arrive_time;
}
waiting_list_time=max_waiting_list_time(queue1,queue2,queue3,queue4);
out(queue1,queue2,queue3,queue4,waiting_list_time);
int time_all=100+waiting_list_time;

queue1->teller_free_time = time_all - queue1->teller_service_time;
queue2->teller_free_time = time_all - queue2->teller_service_time;
queue3->teller_free_time = time_all - queue3->teller_service_time;
queue4->teller_free_time = time_all - queue4->teller_service_time;

printf("queue1 service_time:%d,service_customer:%d,customer_avag_waitime:%d,queue_free_time:%d,customer_avar_waitime:%d\n",queue1->teller_service_time,queue1->teller_service_customers,queue1->teller_waiting_time_all,queue1->teller_free_time,(queue1->teller_waiting_time_all)/(queue1->teller_service_time));
printf("queue2 service_time:%d,service_customer:%d,customer_avag_waitime:%d,queue_free_time:%d,customer_avar_waitime:%d\n",queue2->teller_service_time,queue2->teller_service_customers,queue2->teller_waiting_time_all,queue2->teller_free_time,(queue2->teller_waiting_time_all)/(queue2->teller_service_time));
printf("queue3 service_time:%d,service_customer:%d,customer_avag_waitime:%d,queue_free_time:%d,customer_avar_waitime:%d\n",queue3->teller_service_time,queue3->teller_service_customers,queue3->teller_waiting_time_all,queue3->teller_free_time,(queue3->teller_waiting_time_all)/(queue3->teller_service_time));
printf("queue4 service_time:%d,service_customer:%d,customer_avag_waitime:%d,queue_free_time:%d,customer_avar_waitime:%d\n",queue4->teller_service_time,queue4->teller_service_customers,queue4->teller_waiting_time_all,queue4->teller_free_time,(queue4->teller_waiting_time_all)/(queue4->teller_service_time));
return 1;
}

//--------------------------------------------
int main(){
CUSTOMER_QUEUE queue1,queue2,queue3,queue4;
init_customer_queue(&queue1);init_customer_queue(&queue2);
init_customer_queue(&queue3);init_customer_queue(&queue4);

CUSTOMER_LIST customer_list;
create_customer_list(&customer_list);

CUSTOMER *ptr=customer_list.head.nex_ptr;
while(ptr->nex_ptr != NULL){
printf("arrive_time:%d,need_service_time:%d\n",ptr->arrive_time,ptr->need_service_time);
ptr=ptr->nex_ptr;
}
//-------------------------------
run(&customer_list,&queue1,&queue2,&queue3,&queue4);
return 0;
}

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

typedef struct edgenode{
char from;
char to;
int cost;
struct edgenode* nex_ptr;
}EDGENODE;

typedef struct nodelist{
int node_num;
EDGENODE head;
EDGENODE tail;
}NODELIST;

int initnodelist(NODELIST* list){
list->node_num=0;
list->head.cost=-1;list->tail.cost=-1;
list->head.nex_ptr=&(list->tail);
list->tail.nex_ptr=NULL;
}

int createlist(NODELIST* list){
EDGENODE *ptr,*ptr_list;
EDGENODE *ptr_num;
int flag1,flag2;
char tmp;
printf("edgenode from:to:cost:,input as format a\\tb\\tc\\n,end with '#':\n");
while(1){
flag1=1;flag2=1;
ptr=malloc(sizeof(EDGENODE));
scanf("%c",&(ptr->from));
if(ptr->from == '#') break;
scanf("%c",&tmp);
scanf("%c",&(ptr->to));
scanf("%c",&tmp);
scanf("%d",&(ptr->cost));
scanf("%c",&tmp);

if(list->head.nex_ptr == &(list->tail)){
list->head.nex_ptr=ptr;ptr->nex_ptr=&(list->tail);
list->node_num += 2;
}else{
ptr_list=&(list->head);
ptr_num=list->head.nex_ptr;
while(1){
if( ptr_num->from == ptr->from || ptr_num->to == ptr->from ) flag1=0;
if( ptr_num->from == ptr->to || ptr_num->to == ptr->to ) flag2=0;
if( ptr_num->nex_ptr == &(list->tail) ) break;
ptr_num=ptr_num->nex_ptr;
}
list->node_num += (flag1+flag2);

while(1){
if( ptr_list->nex_ptr->cost >= ptr->cost ){
ptr->nex_ptr=ptr_list->nex_ptr;
ptr_list->nex_ptr=ptr;break;
}
if( ptr_list->nex_ptr == &(list->tail) ){
ptr->nex_ptr=&(list->tail);
ptr_list->nex_ptr=ptr;
break;
}
ptr_list=ptr_list->nex_ptr;
}
}
}
return 1;
}

EDGENODE* poplist(NODELIST* list){
EDGENODE* ptr;
if( list->head.nex_ptr == &(list->tail) ){
return &(list->tail);
}else{
ptr=list->head.nex_ptr;
list->head.nex_ptr=list->head.nex_ptr->nex_ptr;
return ptr;
}
}

//-------------------------------------------------------------------------
typedef struct node{
char c;
struct node* nex_node;
}NODE;

typedef struct union_node{
NODE* head;
NODE* tail;
struct union_node* nex_union_node;
}UNION_NODE;

typedef struct union_list{
//int node_num;
UNION_NODE head;
UNION_NODE tail;
}UNION_LIST;

int initunion_list(UNION_LIST* list){
//list->node_num=0;
list->head.nex_union_node=&(list->tail);
list->tail.nex_union_node=NULL;
return 1;
}

UNION_NODE* find(UNION_LIST* list,char find_c){
UNION_NODE* ptr_union_node=list->head.nex_union_node;
NODE* ptr_node;
while( ptr_union_node->nex_union_node != NULL ){
ptr_node=ptr_union_node->head;
while(1){
if( ptr_node->c == find_c ){
return ptr_union_node;
}
if( ptr_node == ptr_union_node->tail ) break;
ptr_node=ptr_node->nex_node;
}
ptr_union_node=ptr_union_node->nex_union_node;
}
return NULL;
}

UNION_NODE* creat_union_node(UNION_LIST* list){
UNION_NODE* ptr=malloc(sizeof(UNION_NODE));
ptr->nex_union_node=list->head.nex_union_node;
list->head.nex_union_node=ptr;
ptr->head=NULL; ptr->tail=NULL;
return ptr;
}

int del_union_node(UNION_LIST* list){
UNION_NODE* ptr_union_node=&(list->head);
UNION_NODE* tmp;
while( ptr_union_node->nex_union_node != NULL ){
if( ptr_union_node->nex_union_node->head == NULL ){
tmp=ptr_union_node->nex_union_node;
ptr_union_node->nex_union_node=tmp->nex_union_node;
free(tmp);
}
ptr_union_node=ptr_union_node->nex_union_node;
}
return 1;
}

int unite_union_node(UNION_LIST* list,UNION_NODE* union_node1,UNION_NODE* union_node2){
if( union_node1->head == NULL || union_node2->head == NULL ) return 0;
NODE* ptr=union_node2->head;
union_node1->tail->nex_node=ptr;
union_node1->tail=union_node2->tail;
union_node2->head=NULL;
del_union_node(list);
return 1;
}

int creat_node(UNION_NODE* ptr,char c){
NODE* node_ptr=malloc(sizeof(NODE));
node_ptr->c=c;
if( ptr->head == NULL ){
ptr->head=node_ptr;
ptr->tail=node_ptr;
}else{
ptr->tail->nex_node=node_ptr;
ptr->tail=node_ptr;
node_ptr->nex_node=NULL;
}
return 1;
}

int add_two_char(UNION_LIST* list,char from,char to){
UNION_NODE *ptr1,*ptr2;
UNION_NODE* new_ptr;
ptr1=find(list,from);ptr2=find(list,to);
if( ptr1 != NULL && ptr2 != NULL ){
if( ptr1==ptr2 ){
return 0;
}else{
unite_union_node(list,ptr1,ptr2);
}
}else if( ptr1 != NULL && ptr2 == NULL ){
creat_node(ptr1,to);//list->node_num++;
}else if( ptr1 == NULL && ptr2 != NULL ){
creat_node(ptr2,from);//list->node_num++;
}else if( ptr1 == NULL && ptr2 ==NULL ){
new_ptr=creat_union_node(list);
creat_node(new_ptr,from);creat_node(new_ptr,to);
//list->node_num += 2;
}

return 1;
}

int trav_union_list(UNION_LIST* list){
UNION_NODE* ptr_union_node=list->head.nex_union_node;
NODE* ptr_node;
//printf("there is %d nodes\n",list->node_num);
while( ptr_union_node->nex_union_node != NULL ){
ptr_node=ptr_union_node->head;
printf("line:");
while(1){
printf("%c",ptr_node->c);
if( ptr_node == ptr_union_node->tail ) break;
ptr_node=ptr_node->nex_node;
}
printf("\n");
ptr_union_node=ptr_union_node->nex_union_node;
}
return 1;

}

//-------------------------------------------------------------------------

int run(NODELIST* nodelist,UNION_LIST* union_list){
int cost=0;
int line=0;
EDGENODE* ptr;
printf("smallest tree:\n");
while( (ptr=poplist(nodelist)) != &(nodelist->tail) && line < nodelist->node_num-1 ){
if( add_two_char(union_list,ptr->from,ptr->to) == 0 ) continue;
else{
printf("%c,%c,%d\n",ptr->from,ptr->to,ptr->cost);
cost += ptr->cost;
line++;
}
}
if( line < nodelist->node_num-1 ) printf("is not a smallest tree\n");
else printf("that is the smallest tree,the smallest cost is %d\n",cost);
return 1;
}


//-------------------------------------------------------------------------

int main(){
EDGENODE* ptr;

UNION_LIST union_list;
initunion_list(&union_list);

NODELIST list;
initnodelist(&list);
createlist(&list);

//printf("the node_num:");
//scanf("%d",&(union_list.node_num));
run(&list,&union_list);
return 0;
}