link.c

单向链表的升序建立

/*reserved at LIU Jing    Named :assignment_0
2007-9-13   used for create a link form min to max
re create it from max to min and to count it
to insert and delet    and display it in a new file */
#include <stdio.h>
#include <stdlib.h>

/* to define the structure of the link*/
typedef struct node
{
    int data;  //to store the numbers
    struct node *next;  //to point the next one
}
link;

/*fuction insert received an arguments , point head
to tell where is the link and x to tell which number want to
 insert into the link*/
int insert ( link *head ,int x)
{
    link *q, *p;

    p = head;
    q = ( link* ) malloc ( sizeof ( link ) );
    //q is used to store x and his link
    q->data = x;
    q->next = NULL;//make sure the link will not point to a place we don't know
    while (p->next != NULL && p->next->data <= x)
    {
        p = p->next;
        //if the number is less than the x move to next position
    }
    //to insert the x
    q->next = p->next;
    p->next = q;
    p = q->next;
    return 1;
}

//fuction insert_2 has the same fuction as insert but use for max to min
int insert_2 ( link *head, int x)
{
    link *q, *p;

    p = head;
    q = ( link* ) malloc ( sizeof ( link ) );
    //q is used to store x and his link
    q->data = x;
    q->next = NULL;//make sure the link will not point to a place we don't know
    while (p->next != NULL && p->next->data >= x)
    {
        p = p->next;
        //if the number is less than the x move to next position
    }
    //to insert the x
    q->next = p->next;
    p->next = q;
    p = q->next;
    return 1;
}

/* fuction delete_x is to delete the first x in the link
it received one argument head which tell us where the link]
is in the memory, if delete x successfully return 1 */
int delete_x ( link* head)
{
    link *p, *q;
    int x;

    scanf("%d",&x);//get in the x
    p = head;
    //if head->next == null ,the link must be an empty one
    while (p->next != NULL )
    {
        if ( p->next->data != x)
        {
            p = p->next;//move to the next position
        }
        else//if find the x and delete it
        {
            q = p->next;
            p->next = q->next;
            free ( q );
            return 0;
        }
    }
    printf(" no such a int in the link ");
    return 1;
}

/*fuction create has one argument head to tell the position of the link
it opens a file( user gives )and create a link form min to max,returns
head to tell other parts where the link is*/
link* create ( link *head )
{
    char filename [255];
    FILE *fp;
    int x = 0;

    head = ( link* ) malloc ( sizeof ( link ));
    head->next = NULL;

    printf("enter the filename you want to open:");
    scanf( "%s", filename );//get a file name

    fp = fopen ( filename ,"r" );//open only read
    while ( fp == NULL )
    {
        printf("ERROR!!!\nEnter the filename you want to open:");
        //can open it may be the file not exsist
        scanf( "%s", filename );
        fp = fopen ( filename ,"r" );
    }

    while ( (fscanf( fp, "%d", &x )) != EOF)//file not end
    {
        insert( head, x);
    }
    fclose ( fp );//close the file
    printf("link created sucessfully\n");
    return head;
}

//to tell how to use the programme
void help()
{
    printf("press c to create a new link\n"
           "    @ unless you use fuction a first \n"
           "    @ the link is from min to max."
           "press e to end the program\n"
           "press i to insert a int into the link\n"
           "    @ then you should give a int x\n "
           "press d to delete a int x"
           "    @ you should give a int then\n"
           "press r to turn link max to min\n"
           "press l to count the length of the link\n"
           "press a to empty the link in order to re_establish one\n"
           "press p to display the link in the file\n\n");
}


/*fuction errors received none and return none just to tell the user
the key can't open any fuctions of the program*/
void errors ()
{
    printf( "sorry, bad comments.\n ");
    help();
}

/* fuction delete_all received head
and to empty the old link and to create a
new link still in the position of the old */
void delete_all ( link *head )
{
    link *p, *q;
    p = head->next;
    //free every  crunode
    while ( p != NULL )
    {
        q = p;
        p = p->next;
        free ( q );
    }
    printf("now it is an empty link\n");
}

/*fuction search received head to locate the position of link
and is to find out the first x in the link ,return none*/
void search( link* head )
{
    int x;
    int count = 1,mark = 0;
    link *p;

    scanf("%d",&x);//what to find

    p = head->next;
    while ( p != NULL  )
    {
        if ( p->data != x )
        {
            //move to the next if it's not the x
            p = p->next;
            count++;
        }
        else
        {
            printf("now the %d is in the %d th place\n",x,count);
            mark = 1;
            break;
        }
    }
    if ( mark == 0 )
        printf("can't find such a(an) %d\n",x);
    else;//do nothing
}


/*fuction display received head and return none
it establish a new file( user gives the filename )
to display the link in order */
void display ( link *head )
{
    link *p;
    char display_filename[255];
    FILE *fp;

    //get the file name wanted establish
    printf ("enter the display_filename: ");
    scanf( "%s", display_filename);

    fp = fopen ( display_filename, "w");
    // open stytle write
    p = head->next;

    //write every data into the file in order
    while ( p != NULL)
    {
        fprintf ( fp,"%d ", p->data );
        p = p->next;
    }
    printf("displayed in %s\n",display_filename);
    fclose ( fp );
}

/*fuction re_create received head and return none
it used to create the link again from max to min */
void re_create ( link *head )
{
    link *p,*q,*r;

    if ( head->next == NULL )
    {
        printf(" empty link\n");
        //there is no need to create an empty link again
    }
    p = head->next;
    q = p->next;
    r = q->next;
    p->next = NULL;

    while ( q->next != NULL )
    {
        /*move the third crunode to the position before the
        second crunode,then the forth before the third */
        head->next = q;
        q->next = p;
        p = q;
        q = r;
        if ( r->next != NULL )
        {
            r = r->next;
        }
        else;//do nothing
    }
    head->next = q;
    q->next = p;
    printf("link re_create successfully\n");
}

/*fuction count received head and return none
to tell the user how many ints in the link */
void count ( link *head)
{
    int length = 0;
    link *p;

    p = head;
    while ( p->next != NULL )
    {
        p = p->next;
        length++;
    }
    printf ("the link now is %d",length);
}

//to give back all space to the system
void end ( link *head )
{
    delete_all( head );
    free( head );
}

int main()
{
    link* head;
    char option;
    int x = 0;
    int label = 0;

    //point head is to tell where is the link


    printf ("welcome ! press c to create a new link\n");
    printf ("press h for help\n");
    scanf( "%c", &option);

    /*to let the user choose which fuction he want to use
    how to use the program can be seen in fuction help*/
    while ( option != 'e')
    {
        switch ( option)
        {
        case 'a' :
            delete_all ( head );
        case 'c' :
            head = create ( head );
            break;
        case 'i':
        {
            scanf("%d",&x);
            if ( label % 2 == 0)
            insert ( head ,x);
            else insert_2 ( head ,x);
            break;
        }
        break;
        case 'd' :
            delete_x ( head );
            break;
        case 's':
            search( head );
            break;
        case 'r' :
        {
            re_create ( head );
            label++;
            break;
        }
        case 'p':
            display ( head );
            break;
        case 'h':
            help();
            break;
        case 'l':
            count( head );
            break;
        default :
            errors();
            break;
        }
        scanf( "%c", &option);
        scanf( "%c", &option);
        //option = getchar();
        //option = getchar();
    }
    end( head );
    return 0;
}