单链表

1. 编程实现一个单链表的建立/测长/打印。

#include<iostream>
using namespace std;

//单链表结构体
typedef struct student
{
    int data;
    struct student *next;
}node;

//建立单链表
node *create()
{
    node *head,*p,*s;
    int x,cycle=1;
    head=(node*)malloc(sizeof(node)); //建立头节点
    p=head;
    while(cycle)
    {
        printf("\nPlease input the data:");
        scanf("%d",&x);
        if(x!=0)
        {
            s=(node*)malloc(sizeof(node));//每次新建一个节点
            s->data=x;
            printf("\n%d",s->data);
            p->next=s;
            p=s;
        }
        else
        {
            cycle=0;
        }
    }
    head=head->next;
    p->next=NULL;
    printf("\n yyy %d",head->data);
    return (head);
}

//单链表测长
int length(node *head)
{
    int n=0;
    node *p;
    p=head;
    while(p!=NULL)
    {
        p=p->next;
        n++;
    }
    return (n);
}

//单链表打印
void print(node *head)
{
    node *p;
    int n;
    n=length(head);
    printf("\nNow,These %d records are :\n",n);
    p=head;
    if(head!=NULL)
        p=p->next;
    while(p!=NULL)
    {
        printf("\n uuu %d ",p->data);
        p=p->next;
    }
}

2.编程实现单链表删除节点。

//单链表删除节点
node *remove(node *head ,int num)
{
    node *p1,*p2;
    p1=head;
    while(num!=p1->data && p1->next!=NULL)//查找data为num的节点
    {
        p2=p1;
        p1=p1->next;
    }
    if(num==p1->data) //如果存在num节点，则删除
    {
        if(p1==head)
        {
            head=p1->next;
            free(p1);
        }
        else
        {
            p2->next=p1->next;
        }
    }
    else
    {
        printf("\n%d could not been found",num);
    }
    return (head);
}

3.编写程序实现单链表的插入。

//单链表插入节点
node *insert(node *head,int num)
{
    node *p0,*p1,*p2;
    p1=head;
    p0=(node *)malloc(sizeof(node));
    p0->data=num;
    while(p0->data > p1->data && p1->next!=NULL)
    {
        p2==p1;
        p1=p1->next;
    }
    if(p0->data<=p1->data)
    {
        if(head==p1)
        {
            p0->next=p1;
            head=p0;
        }
        else
        {
            p2->next=p0;
            p0->next=p1;
        }
    }
    else
    {
        p1->next=p0;
        p0->next=NULL;
    }
    return (head);
}

4.编程实现单链表的排序。

//单链表排序
node *sort(node *head)
{
    node *p,*p2,*p3;
    int n;
    int temp;
    n=length(head);
    if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点
        return head;
    p=head;
    for(int j=1;j<n;++j)
    {
        p=head;
        for(int i=0;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);
}

5.编写实现单链表的逆置。

//单链表逆置
node *reverse(node *head)
{
    node *p1,*p2,*p3;
    if(head==NULL || head->next==NULL)
        return head;
    p1=head;
    p2=p1->next;
    while(p2)
    {
        p3=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p3;
    }
    head->next=NULL;
    head=p1;
    return head;
}