2008秋-计算机软件基础- 实验二 参考源程序

实验二 参考源程序
/* Author : Eman Lee,
计算机软件基础 教材 P79, ex4

设有一头为head的带头结点的单链表，其数据域为整形数据且递增有序。

试写一算法，将元素插入链表适当的位置，以保持链表的有序性。
*/

#include<stdio.h>

#include<stdlib.h>


typedef int DataType;
struct nodetype//Define node 定义节点
{

 DataType data;//Data field
 struct nodetype * next;//Pointer field which point to the next node
};


typedef struct nodetype NodeType;//Give struct nodetype a new name NodeType


NodeType * InitialLinkList()//Initialize a Linked List,and return the head pointer
{

 NodeType * head;

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

 return head;

}

void CreateLinkListInRear(NodeType * head, DataType numbers[], int LengthOfNumbers)

{//Insert new node in the rear of link list.
    int i;

    NodeType * temp,* rear;

    rear=head;

    for(i=0;i<LengthOfNumbers;i++)

    {

        temp=(NodeType *)malloc(sizeof(NodeType));

        temp->data=numbers[i];

        temp->next=NULL;

        rear->next=temp;

        rear=temp;

    }

}

void CreateLinkListInHead(NodeType * head, DataType numbers[], int LengthOfNumbers)

{//Insert new node in the front of link list.
    int i;

    NodeType * temp,*front;

    //front=head;
    for(i=0;i<LengthOfNumbers;i++)

    {

        temp=(NodeType *)malloc(sizeof(NodeType));

        temp->data=numbers[i];

        temp->next=head->next;

        head->next=temp;

        //rear=temp;
    }

}


NodeType * SearchInLinkList(NodeType * head, DataType x)

{//Search x in link list.
    NodeType * p=head->next;

    while(p!=NULL)

    {

    if(p->data==x)

        return p;

    else

        p=p->next;

    }

    return NULL;

}

void InsertNumberIntoLinkList(NodeType * head,DataType key,DataType x)

{

 //Insert x after key in the linked list.

    //Need two pointers if insert x before key.
    NodeType * location,*temp;

 if((location=SearchInLinkList(head,key))!=NULL)

    {

        temp=(NodeType *)malloc(sizeof(NodeType));

        temp->data=x;

        temp->next=location->next;

        location->next=temp;

        printf("\n链表中插入元素%d",x);

    }

 else

     printf("\nNot Found, Insert failed!\n");

}

void DeleteNumberFromLinkList(NodeType * head,DataType x)

{

 //Delete x in the linked list.

 //need two pointers

    //todo
}

void PrintIntegerLinkList(NodeType * head)

{//Show nodes on the screen.
    NodeType *temp;

    temp=head->next;

    printf("\n显示所有元素:");

    while(temp!=NULL)

    {

        printf("%d ",temp->data);

        temp=temp->next;

    }

    printf("\n");

}

int InsertIntoSortedList(NodeType * head, int x)

{

 NodeType * f,*r,*temp;

 f=head;

 r=head->next;

 while(r!=NULL)

  {

    if(r->data>=x)

    {

      temp=(NodeType *)malloc(sizeof(NodeType));

      temp->data=x;

      temp->next=r;

      f->next=temp;

      printf("\n链表中插入元素%d",x);

      return 1;

    }

    else

    {

     f=r;

     r=r->next;

    }

  }

  temp=(NodeType *)malloc(sizeof(NodeType));

  temp->data=x;

  temp->next=NULL;

  f->next=temp;

  printf("\n链表中插入元素%d",x);

  return 1;

  

}

void main()

{

 NodeType *head,*head2;

 //DataType x[5]={1,2,3,4,5};
 DataType y[5]={8,7,6,5,4};

 //head=InitialLinkList();
 head2=InitialLinkList();

 CreateLinkListInHead(head2,y,5);

 //CreateLinkListInRear(head,x,5);
 PrintIntegerLinkList(head2);

 //PrintIntegerLinkList(head);
 if(SearchInLinkList(head2,88)!=NULL)

     printf("\nFound 88\n");

 else

     printf("\nSearch 88,Not Found\n");

 //InsertNumberIntoLinkList(head2,7,33);

 //PrintIntegerLinkList(head2);


 InsertIntoSortedList(head2,0);

 PrintIntegerLinkList(head2);


 InsertIntoSortedList(head2,6);

 PrintIntegerLinkList(head2);


 InsertIntoSortedList(head2,9);

 PrintIntegerLinkList(head2);

}