シングルチェーンテーブルの基本操作C++

   https://blog.csdn.net/tianzhaixing2013/article/details/22786001
#include <iostream>
#include <stdio.h>
#include <string>
#include <conio.h>

/**
* cstdio  stdio.h    C++          。
*stdio.h C          ， ：standard buffered input&output。
*               （        ）。
*/

/**
*conio Console Input/Output（       ）   ，                        ，
*                   ，  getch()()    。
*/

/**           k   
*                    k   ，        。
*                     k-1 ，         。
*    k   ，                   。      
*        k-1，               ，         
*     k   。
*/

using namespace std;

struct node
{
    int data;  //      
    node *next; //      
};

//      
node *creat()
{
    node *head, *p;  //head     
    head = new node;  //    ，    
    p = head;

    int x, cycle = 1;  //x         cycle     
    while (cycle)
    {
        cout << "Please input the data for single linker : ";
        cin >> x;   //2 4 5 0

        if (x != 0)
        {
            node *s = new node;
            s->data = x;  //s              x
            cout << "Input data : " << x << endl;

            p->next = s;
                //cout << p->data << endl;  //    、 2、4
                //cout <data << endl;  //2、4、5
            p = s;
                //cout << p->data << endl; //2、4、5
        }
        else
        {
            cycle = 0;
            cout << "Input done! " << endl;
        }
    } //  while，  while(cycle)，  cycle 0，    head = head->next;

    //cout << head->data << endl; //    
    head = head->next;
    //cout << head->data << endl;  //2  head        
    p->next = NULL;
    //cout << p->data << p->next << endl;  //5 00000000

    return head;
}

//      
int length(node *head)
{
    int n = 0;
    node *p = head;

    while (p != NULL)
    {
        p = p->next;
        n++;
    }

    return n;
}

//           
void PrintListFormHeadToTail(node *head)
{
    node *p = head;

    while (p != NULL)
    {
        cout << "Single Linker data is " << p->data << endl;
        p = p->next;
    }
}

//           
void PrintListFormTailToHead(node *pHead)
{

    if (pHead == NULL)
    {
        return;
    }
    else
    {
        PrintListFormTailToHead(pHead->next);
        cout << "Single Linker data is " <<pHead->data << endl;
    }
}

//      
node *insert(node *head, int num)
{
    node *p0, *p1, *p2;
    p1 = head;

    p2 = new node;
    p0 = new node; //     
    p0->data = num;//     

    while (p0->data > p1->data && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next;// p0,p1 p2  : p2->p1->p0
    }

    if (p0->data <= p1->data)
    {
        if (p1 == head)
        {//        p0 p1  : p0->p1->...
            head = p0;
            p0->next = p1;
        }
        else
        {//        p0,p1 p2  : p2-> p0 -> p1
            p2->next = p0;
            p0->next = p1;
        }
    }
    else
    {   //        p0,p1 p2  : p2->p1->p0->NULL
        p1->next = p0;
        p0->next = NULL;
    }
    return head;
}

//      
node *del(node *head, int num)
{
    node *p1, *p2;
    p2 = new node;
    p1 = head;

    while (num != p1->data && p1->next != NULL)
    {
        p2 = p1;
        p1 = p1->next;// p1 p2  : p2->p1        
    }

    if (num == p1->data)
    {
        if (p1 == head)//      
        {
            head = p1->next;
            delete p1;
        }
        else
        {
            p2->next = p1->next;
            delete p1;
        }
    }
    else
    {
        cout << num << " could not been found in the current single linker!" << endl;
    }
    return head;
}

//      
node *sort(node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    node *p = head;//    p      

    int n, temp;
    n = length(head);

    for (int j = 0; j < n; j++)
    {
        p = head;
        for (int i = j + 1; i < n; i++)
        {
            if (p->data > p->next->data)
            {
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            else
            {
                p = p->next;
            }
        }
    }

    return head;
}

//      
node *reverse(node *head)
{
    node *p1, *p2, *p3;

    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    p1 = head;
    p2 = head->next;

    while (p2)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    head->next = NULL;
    head = p1;
    cout << head->data << endl;

    return head;
}

//      k   
node *findKthToTail(node *head, int k)
{
    node *fast = head;
    node *slow = NULL;
    if (head == NULL || k <= 0){
        return NULL;
    }
    for (int i = 0; i < k - 1; i++){
        fast = fast->next;
    }
    slow = head;
    while (fast->next != NULL){
        slow = slow->next;
        fast = fast->next;
    }
    cout << "The " << k << "th to tail is " << slow->data << endl;
    return slow;
}

//        
node *SearchMid(node *head) //         ，       
{
    node *slow = head;
    while (head->next != NULL && head->next->next != NULL)
    {
        head = head->next->next;
        slow = slow->next;
    }
    cout << "The mid is " << slow->data << endl;
    return slow;
}


int main()
{
    cout << "***     ***" << endl;
    node *head = creat();
    cout << endl;

    cout << "***     ***" << endl;
    int n = length(head);   //        head     
    cout << "The length of input single linker is " << n << "." << endl;
    cout << endl;

    cout << "***          ***" << endl;
    PrintListFormHeadToTail(head);  //         head  
    cout << endl;

    cout << "***          ***" << endl;
    PrintListFormTailToHead(head);  //         head  
    cout << endl;

    cout << "****    ****" << endl;
    cout << "Please input the data for inserting operate : ";
    int inData;
    cin >> inData;
    head = insert(head, inData);   // head       
    PrintListFormHeadToTail(head);
    cout << endl;

    cout << "****    ****" << endl;
    cout << "Please input the data for deleting operate : ";
    int outData;
    cin >> outData;
    head = del(head, outData);  // head       
    PrintListFormHeadToTail(head);
    cout << endl;

    cout << "***     ***" << endl;
    head = sort(head);   //// head      
    PrintListFormHeadToTail(head);
    cout << endl;

    //       head      ,           head

    cout << "***     ***" << endl;
    head = reverse(head);
    PrintListFormHeadToTail(head);   // head    ，        rev，       head     
    cout << endl;


    cout << "***     k   ***" << endl;
    cout << "Please input the data for find Kth to tail : ";
    int findData;
    cin >> findData;
    node *Kth = findKthToTail(head, findData);    //     head        K   ，     Kth
    cout << endl;


    cout << "***        ***" << endl;
    node *mid = SearchMid(head);     //     head          ，     mid
    cout << endl;

    return 0;
}