单链表(程序员宝典)

//

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <conio.h>

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)
    {
        std::cout<<"please input the data: ";
        std::cin>>x;
        std::cout<<std::endl;
        if(x != 0)
        {
            s = (node *)malloc(sizeof(node));
            s->data = x;
            p->next = s;
            p = s;
        }
        else
            cycle = 0;
    }
    head = head->next;
    p->next = NULL;
    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);
    std::cout<<"Now, These "<<n<<" records are: "<<std::endl;
    p = head;
    if(p != NULL)
    {
        while(p != NULL)
        {
            std::cout<<p->data<<" -> ";
            p = p->next;
        }
        std::cout<<std::endl;
    }
}
//单链表删除结点
node* del(node *head, int num)
{
    node *p1,*p2;
    p1 = head;
    while(num != p1->data && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next;
    }
    if(num == p1->data)
    {
        if(p1 == head)
        {
            head = p1->next;
            free(p1);
        }
        else
        {
            p2->next = p1->next;
            free(p1);
        }
    }
    else
    {
        std::cout<<num<<" could not been found"<<std::endl;
    }
    return head;
}
//插入结点
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(p1 == head)
        {
            p0->next = p1;
            head = p0;
        }
        else
        {
            p0->next = p1;
            p2->next = p0;
        }
    }
    else
    {
        p1->next = p0;
        p0->next = NULL;
    }
    return head;
}
//单链表的排序
node *sort(node *head)
{
    node *p;
    int n, 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;
}


int _tmain(int argc, _TCHAR* argv[])
{
    node *head;
    head = create();
    print(head);
    //删除结点
    int num;
    std::cin>>num;
    head = del(head, num);
    print(head);    //打印删除后的单链表
    //插入结点
    std::cin>>num;
    head = insert(head, num);
    print(head);

    //单链表排序
    head = sort(head);
    print(head);
    return 0;
}