西北工业大学数据结构noj_1-6题

/* noj6 */ #include <stdio.h> #include <stdlib.h> typedef struct Node { char data; struct Node *pre; struct Node *next; int freq; }ListNode,*LinkList; void ListInit(LinkList *L){ *L = (ListNode*)malloc(sizeof(ListNode)); (*L)->next = NULL; (*L)->pre = NULL; } void ListCreate(LinkList L,int data_num,char A[]){ ListNode *r = L; int i; char data; for(i=0;i<data_num;i++){ data = A[i]; ListNode *p; p = (ListNode*)malloc(sizeof(ListNode)); p->freq = 0; p->data = data; p->next = r->next; p->pre = r; r->next = p; r = r->next; } r->next = L; L->pre = r; } void ListPrint(LinkList L){ ListNode *r = L->next; while(r!=L){ printf("%c ",r->data); r = r->next; } //printf("\n"); } void ListPrintF(LinkList L){ ListNode *r = L->next; while(r!=L){ printf("%d ",r->freq); r = r->next; } printf("\n"); } void sort(LinkList L,int num){ ListNode *r = L->next; ListNode *t; int i,j; for(i=0;i<num;i++){ r = L->next; for(j=0;j<num;j++){ if(r->next==L) break; if(r->freq<r->next->freq){ t = r->next; r->next = t->next; t->next->pre = r; t->pre = r->pre; r->pre->next = t; r->pre = t; t->next = r; } r = r->next; } } } void option(LinkList L,char C[],int num_fang){ int i=0; ListNode *r = L->next; while(i<num_fang){ while(r!=L){ if(r->data != C[i]){ r = r->next; } else{ r->freq++; break; } } r = L->next; i++; } } int main(){ char A[1000]; char C[1000]; char B[1]; int num,fang_num,i; scanf("%d %d",&num,&fang_num); C[0] = getchar();//吸收回车键 for(i=0;i<num;i++){ A[i] = getchar(); B[0] = getchar(); } for(i=0;i<fang_num;i++){ C[i] = getchar(); B[0] = getchar(); } /* for(i=0;i<num;i++){ printf("%c ",A[i]); } printf("\n"); for(i=0;i<fang_num;i++){ printf("%c ",C[i]); } printf("\n-----------\n"); */ LinkList L1; ListInit(&L1); ListCreate(L1,num,A); option(L1,C,fang_num); sort(L1,num); ListPrint(L1); //ListPrintF(L1); return 0; }