main.c

数据压缩

#include<string.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define MAX 100
typedef struct message  // 定义消息结点
{
       char member;
       struct message * next;
}messagelist;
typedef struct messagecode //编码结果结点
{
       int no;
       int firstno;
       char code;
       struct messagecode * next;
}messagecodelist;
 
typedef struct stringnode //当前被编码的消息结点
{
       int no;
       char string[MAX];
       struct stringnode * next;
}stringnodelist; 

messagelist * createmessagelist(); //创建消息链表
messagecodelist* createmessagenodelist1(messagelist *head);//创建结果的第一结点
stringnodelist * createstringnodelist1(messagecodelist *head1);//创建当前编码的第一个结点
messagecodelist* createmessagenode(int a,int b,char c);//创建结果结点
stringnodelist * createstringnode(int a,char string[MAX]);//创建当前编码的结点
messagecodelist* insertmessagenodelist(messagecodelist *head1,messagecodelist *p);//插入结果结点
stringnodelist * insertstringnodelist(stringnodelist *head2,stringnodelist *p);//插入当前编码结点
int bijiao(char string1[MAX],char string2[MAX] );//比较两个数组是否相等
int jianyan(char string1[MAX],stringnodelist * head2);//检验当前消息是否被编过
void printmessage(messagelist *head);//输出消息
void printmessagecode(messagecodelist * head1,stringnodelist *head2);//输出编码结果  
int main()
{
       messagelist *head,*p;
       messagecodelist *head1,*p2,*p3;
       stringnodelist *head2,*p1,*m;
       int k,i,a,temp;
       char string[MAX];
       i=0;
       a=1;
       temp=0;
       head=createmessagelist();//创建消息链表,以‘？’结束字符串       
       head1=createmessagenodelist1(head);//创建结果的第一结点
       head2=createstringnodelist1(head1);//创建当前编码的第一个结点
       p=head->next->next;
       while(p!=NULL)
       {
              string[i]=p->member;
              string[++i]='?';
              k=jianyan(string, head2);
              if(k==0)
              {
                     p2=createmessagenode(++a,temp,p->member);
                     p1=createstringnode(a,string);
                     head1=insertmessagenodelist(head1,p2);
                     head2=insertstringnodelist(head2,p1);
                     i=0;
                     p=p->next;
                     temp=0;
              }
              else
              {
                     temp=k;
                     p=p->next;
              }
       }
       if(temp!=0)
       {
              p2=head1->next;
              while(p2!=NULL)
              {
                     if(p2->no!=temp)
                            p2=p2->next;
                     else
                     {
                            p3=createmessagenode(++a,p2->firstno,p2->code);
                            p1=createstringnode(a,string);
                            head1=insertmessagenodelist(head1,p3);
                            head2=insertstringnodelist(head2,p1);
                            break;
                     }     
              }
       }
       printmessagecode( head1,head2);//输出结果 
  system("PAUSE");	
  return(0);
}


messagelist * createmessagelist()
{
       char ch;
       messagelist *head,*r,*p;
       p=(messagelist *)malloc(sizeof(messagelist));
       head=p;
       p->next=NULL;
       r=p;
       printf("input message(end in' ?'):\n");
       ch=getchar();
       while(ch!='?')
       {
              p=(messagelist *)malloc(sizeof(messagelist));
              p->member=ch;
              p->next=NULL;
              r->next=p;
              r=r->next;
              ch=getchar();
       }
       return (head);
}
 
messagecodelist* createmessagenodelist1(messagelist *head)
{
       messagelist *q;
       messagecodelist *p,*head1,*r;
       p=(messagecodelist *)malloc(sizeof(messagecodelist));
       head1=p;
       p->next=NULL;
       r=p;
       if(head->next!=NULL)
       {
              q=head->next;
              p=(messagecodelist *)malloc(sizeof(messagecodelist));
              p->no=1;
              p->firstno=0;
              p->code=q->member;
              p->next=NULL;
              r->next=p;
              r=r->next;
       }
       return (head1);
}
 
stringnodelist * createstringnodelist1(messagecodelist *head1)
{
       messagecodelist *q;
       stringnodelist *p,*head2,*r;
       p=(stringnodelist *)malloc(sizeof(stringnodelist));
       head2=p;
       p->next=NULL;
       r=p;
       if(head1->next!=NULL)
       {
              q=head1->next;
              p=(stringnodelist *)malloc(sizeof(stringnodelist));
              p->no=1;
              p->string[0]=q->code;
              p->string[1]='?';
              p->next=NULL;
              r->next=p;
              r=r->next;
       }
       return (head2);
}
 
messagecodelist * insertmessagenodelist(messagecodelist *head1,messagecodelist *p)
{
       messagecodelist *r;
       r=head1;
       while(r->next!=NULL)
              r=r->next;              
       r->next=p;
       r=r->next;
       return (head1);
}
 
stringnodelist * insertstringnodelist(stringnodelist *head2,stringnodelist *p)
{
       stringnodelist *r;
       r=head2;
       while(r->next!=NULL)
              r=r->next;
       r->next=p;
       r=r->next;
       return (head2);
}
 
int bijiao(char string1[MAX],char string2[MAX] )
{
       int i;
       i=0;
       while(string1[i]!='?'&&string2[i]!='?')
       {
              if(string1[i]==string2[i])
                     i++;
              else
              {
                     return 0;
              }
       }
       if(string1[i]=='?'&&string2[i]=='?')
              return 1;
       else
              return 0;
}
 
int jianyan(char string1[MAX],stringnodelist * head2)
{
       stringnodelist *p;
       int k;
       p=head2->next;
       while(p!=NULL)
       {
              k=bijiao(string1,p->string);
                     if(k==1)
                            break;
                     else         
                            p=p->next;
       }
       if(p==NULL)
              return 0;
       else
              return (p->no);
}

void printmessage(messagelist *head)
{
       messagelist *p;
       p=head->next;
       while(p!=NULL)
       {
              printf("%c  ",p->member);
              p=p->next;
       }
       printf("\n");
}
 
void printmessagecode(messagecodelist * head1,stringnodelist *head2)
{
       messagecodelist *p;
       stringnodelist *q;
       p=head1->next;
       q=head2->next;
       while(p!=NULL&&q!=NULL)
       {
              int i=0;
              printf("(%d,%d,%c)  ",p->no,p->firstno,p->code);
              while(q->string[i]!='?')
              {
                     printf("%c",q->string[i]);
                     i++;
              }
              printf("\n");
              p=p->next;
              q=q->next;
       }
}

messagecodelist* createmessagenode(int a,int b,char c)
{
       messagecodelist *p;
       p=(messagecodelist *)malloc(sizeof(messagecodelist));
       p->no=a;
       p->firstno=b;
       p->code=c;
       p->next=NULL;
       return (p);
}

stringnodelist * createstringnode(int a,char string[20])
{
       stringnodelist *p;
       p=(stringnodelist *)malloc(sizeof(stringnodelist));
       p->no=a;
       strcpy(p->string,string);
       p->next=NULL;
       return (p);
}