链表基本操作的程序实现

原帖及讨论：

#include
#include

typedef struct List_Node{
    int info;
    struct List_Node *next;
  }node;//结点结构体

/******************************/
/* 尾插法建立带头结点的单链表 */
/******************************/
node* Creat_Node()
{
    node *head,*pre,*p;
    int x;
    head=(node*)malloc(sizeof(node));;
    head->next=NULL;
    pre=head;
    printf("输入各结点的值,以0结束:");
    while(EOF!=(scanf("%d",&x))&&x!=0)
    {
        p=(node*)malloc(sizeof(node));
        p->info=x;
        p->next=pre->next;
        pre->next=p;
        pre=pre->next;
    }
    return head;
}

/******************************/
/* 头插法建立带头结点的单链表 */
/******************************/
node* Build_Node()
{
    node *head,*p;
    int x;
    head=(node*)malloc(sizeof(node));;
    head->next=NULL;
    printf("输入各结点的值,以0结束:");
    while(EOF!=(scanf("%d",&x))&&x!=0)
    {
        p=(node*)malloc(sizeof(node));
        p->info=x;
        p->next=head->next;
        head->next=p;
    }
    return head;
}

/******************************/
/*         打印单链表         */
/******************************/

void Print_Node(node *head)
{
    node *p=head->next;
    printf("输出该链表:");
    while(p)
    {
        printf("%-5d--->",p->info);
        p=p->next;
    }
    if(p==NULL)
    {
        printf("^\n\n\n");
    }
}

 

#include"Head_Node.h"

int Count_Node(node *head)
{
    node *p=head->next;
    int num=0;
    while(p!=NULL)
    {
        num++;
        p=p->next;
    }
    return num;
}

int main()
{
    node *head;
    head=Creat_Node();
    Print_Node(head);
    printf("结点个数为:%d\n",Count_Node(head));
    return 0;
}

 

#include"head_node.h"

/**********************************/
/*         删除重复               */
/**********************************/

void Delete_Repeat_Node(node *head)
{
    node *p,*pre,*s;
    pre=head->next;
    p=pre->next;
    while(p)
    {
        s=p->next;
        while(s&&s->info!=p->info)
        {
            s=s->next;
        }
        if(s)
        {
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
}

int main()
{
    node *head;
    head=Creat_Node();
    Print_Node(head);
    Delete_Repeat_Node(head);
    Print_Node(head);
    return 0;
}

 

#include"Head_Node.h"
/************************************/
/*           在Y前插入X             */
/************************************/
void Before_y_Insert_x(node* head,int y,int x)
{
    node *pre,*p,*s;
    pre=head;
    p=pre->next;
    while(p&&p->info!=y)
    {
        pre=p;
        p=p->next;
    }
    if(p==NULL)
    {
        printf("error!%d不在该链表中\n",y);
    }
    else
    {
        s=(node*)malloc(sizeof(node));
        s->info=x;
        s->next=p;
        pre->next=s;
    }
}

int main()
{
    node *head;
    int x,y;
    head=Creat_Node();
    printf("在y前插入x，输入y,x:");
    scanf("%d%d",&y,&x);
    Print_Node(head);
    Before_y_Insert_x(head,y,x);
    Print_Node(head);
    return 0;
}

#include"Head_Node.h"

/************************************/
/*         判断链表是否有序         */
/************************************/
int Is_Sort(node *head)
{
    node *p,*pre;
    int flag;
    pre=head->next;
    p=pre->next;
    flag=pre->info>p->info?1:0;
    while(p)
    {
        pre=p;
        p=p->next;
        if(p)
        {
            if(flag!=pre->info>p->info?1:0)
            {
                return 0;
            }
        }
    }
    return 1;
}

int main()
{
    node *head;
    int flag;
    head=Creat_Node();
    Print_Node(head);
    flag=Is_Sort(head);
    if(flag==1)
    {
        printf("该链表有序!\n");
    }
    else
    {
        printf("该链表无序!\n");
    }
    return 0;
}

 

#include"Head_Node.h"
/************************************/
/*          链表反序                */
/************************************/
void convert_Node(node *head)
{
    node *pre,*p=head->next;
    head->next=NULL;
    while(p)
    {
        pre=p;
        p=p->next;
        pre->next=NULL;
        pre->next=head->next;
        head->next=pre;
    }
}
        
  list   *list_reverse(list   *head)  
  {  
  list   *p,*q,*r;  
  p=head;  
  q=p->next;  
  while(q!=null)  
  {  
  r=q->next;  
  q->next=p;  
  p=q;  
  q=r;  
  }   
        
    
int main()
{
    node *head;
    head=Creat_Node();
    Print_Node(head);
    convert_Node(head);
    Print_Node(head);
    return 0;
}

#include"Head_Node.h"

/************************************/
/*     将奇偶数按原相对顺序分开     */
/************************************/

node *Divide_Node(node *head1)
{
    node *head2,*pre,*p,*s;
    p=head1->next;
    pre=head1;
    head2=(node*)malloc(sizeof(node));
    head2->next=NULL;
    s=head2;
    while(p)
    {
        if(p->info%2)
        {
            pre->next=p->next;
            p->next=s->next;
            s->next=p;
            s=p;
            p=pre->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
    return head2;
}

int main()
{
    node *head,*head2;
    head=Creat_Node();
    Print_Node(head);
    head2=Divide_Node(head);
    printf("打印偶数链表\n");
    Print_Node(head);
    printf("打印奇数链表\n");
    Print_Node(head2);
    return 0;
}

 

#include"Head_Node.h"

/*******************************/
/*删除所有大于x而不大于Y的结点 */
/*******************************/

void Delete_X_y(node *head,int x,int y)
{
    node *pre=head,*p=head->next;
    if(x>=y)
    {
        printf("不符合条件!\n");
        return ;
    }
    while(p)
    {
        if(p->info>x&&p->info<=y)
        {
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
}

int main()
{
    node *head;
    int x,y;
    head=Creat_Node();
    printf("输出x,y的值:");
    scanf("%d%d",&x,&y);
    Print_Node(head);
    Delete_X_y(head,x,y);
    Print_Node(head);
    return 0;
}

#include"Head_Node.h"
/****************************************************/
/*                 直接插入排序                     */
/****************************************************/

void Insert_Sort(node *head)
{
    node *p,*pre,*s,*r;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        pre=p->next;
        r=head;
        s=head->next;
        while(s&&s->infoinfo)
        {
            r=s;
            s=s->next;
        }
        p->next=r->next;
        r->next=p;
        p=pre;
    }
}
        

        
int main()
{
    node *head;
    head=Creat_Node();
    Print_Node(head);
    Insert_Sort(head);
    Print_Node(head);
    return 0;
}

 

#include"head_node.h"
node* merge_two_List(node *head1,node *head2)
{
    node *head,*s,*p,*r;
    p=head1->next;
    s=head2->next;
    head=(node*)malloc(sizeof(node));
    head->next=NULL;
    r=head->next;
    while(s&&p)
    {
        if(p->infoinfo)
        {
            head1->next=p->next;
            p->next=NULL;
            r->next=p;
            r=r->next;
            p=head1->next;
        }
        else
        {
            head2->next=s->next;
            s->next=NULL;
            r->next=s;
            r=r->next;
            s=head2->next;
        }
    }
    while(s)
    {
        head2->next=s->next;
        s->next=NULL;
        r->next=s;
        r=r->next;
        s=head2->next;
    }
    while(p)
    {
        head1->next=p->next;
        p->next=NULL;
        r->next=p;
        r=r->next;
        p=head1->next;
    }
    //free(head1);
    //free(head2);
    return head;
}

int main()
{
    node *head,*head1,*head2;
    head1=Creat_Node();
    head2=Creat_Node();
    head=merge_two_List(head1,head2);
    Print_Node(head);
    return 0;
}