单链表的建立/测长/打印/删除/排序/逆序/寻找中间值

#include <stdio.h>
#include <stdlib.h>  //函数malloc需要的头文件

typedef struct student * PNode;

typedef struct student     //设计链表前最重要的是先想好数据结构
{
    int data;
    struct student *next;
}Node;

PNode create()
{
    PNode head,p;
    int x=0;
    char flag;
    head=(PNode)malloc(sizeof(Node));
    p=head;
    if(head==NULL)
        return NULL;
    printf("请输入节点的值:");
    scanf("%d",&x);
    while(1)
    {
        p->data=x;
        printf("是否继续添加链表:Y/N
");
        scanf(" %c",&flag);     //注意，在%c前面有个空格，是为了防止上一个语句的回车符，因为scanf会把回车符当做一个字符，而scanf只接收一个字符
        if('N'==flag)
            break;
        p->next=(PNode)malloc(sizeof(Node));   //为下一个节点申请地址
        p=p->next;
        printf("请输入节点的值:");
        scanf("%d",&x);
    }
　　 p->next=NULL;
    return head;
}

void print(PNode link)
{
    PNode head=link;
    if(head==NULL)
        return;
    while(head!=NULL)
    {
        printf("%d ",head->data);
        head=head->next;
    }
    printf("
");
}

int length(PNode link)
{
    int count=0;
    PNode head=link;
    while(head!=NULL)
    {
        ++count;
        head=head->next;
    }
    return count;
}

PNode del(PNode link,int num)  //删除分两种情况，一种是删除第一个节点，另外一种是删除中间节点。
{
        PNode head,p,temp;
        head=link;
        if(head->data==num)   //删除第一个节点
        {   
                head=head->next;
                return head;
        }   
        p=head;
        while(p->next!=NULL)
        {   
                if(p->next->data==num)          //删除第其他节点
                {   
                        temp=p->next->next;
                        free(p->next);
                        p->next=temp;
                        return head;
                }   
                p=p->next;
    
        }   
        printf("没有这样的节点");
        return link;
}


PNode sort(PNode link)
{
        PNode head=link;
        PNode p;
        int i,j,temp;
        int n=length(link);
        for(j=1;j<n;j++)
        {
                p=head; //每次都要从头比较
                for(i=1;i<=n-j;i++)  //每次都把最大的放到末尾
                {
                        if(p->data>p->next->data)
                        {
                                temp=p->data;
                                p->data=p->next->data;
                                p->next->data=temp;
                        }
                        p=p->next;
                }
        }
        return head;
}


PNode reverse(PNode link)
{
        if(link==NULL) return NULL;  //注意要判断是否为空
        PNode head=link;
        PNode p,p1,p2;  //用p1来反指向p，同时p2不改变，利用p2->next来使指针不断向前，如果p2->next=p1也重指向，就不能利用p2继续前
进了。
        p=head;           //利用1 3 5 7 9画图来写算法
        p1=p->next;
        if(p1==NULL) return p;  //如果不判断是否为空，那么如果p1为空，那么p2将会出现段错误
        p2=p1->next;
        p->next=NULL; //处理头结点
        p1->next=p;
        while(p2!=NULL)
        {
                p=p1;
                p1=p2;
                p2=p2->next;
                p1->next=p;
        }
        return p1;
}


int searchMid(PNode link)    //寻找中间值
{
        PNode mid,fast;//mid每次移动一个结点，fast每次移动两个结点
          mid=link;
        fast=link;
        if(mid->next==NULL)    //假设只有一个结点
                return mid->data;
        while(fast!=NULL)
        {
                mid=mid->next;
                fast=fast->next->next;
        }
        return mid->data;
}

int main(void)
{
        PNode link;
        int len;//链表长度
         int num;//要删除的值
         int mid;//链表的中间值
         link=create();//创建链表
         printf("打印刚创建的链表
");
        print(link);
        mid=searchMid(link);
        printf("中间值是%d
",mid);
        link=reverse(link);
        printf("打印反转后的链表
");
        print(link);
        link=sort(link);
        printf("排序好的链表
");
        print(link);
        printf("请输入要删除的链表的值：");
        scanf("%d",&num);
        link=del(link,num);
        printf("打印删除后链表的值
");
        print(link);
        len=length(link);
        printf("链表的长度为%d
",len);
        return 0;
}

 程序猿必读