Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Single list summarizes the basic operation     - Linux Samba server-side structures and the use of the client (Server)

- MongoDB 3.0 New Features (Database)

- How to turn Java String into Date (Programming)

- Oracle 11g Export guide problem not an empty table (Database)

- To install and deploy Java applications under CentOS 6.5 (Linux)

- Talking about modern programming language syntax and standard library tightly bound phenomenon (Programming)

- Nine artifact control disk partition under Linux (Linux)

- Linux Operating System Security Management Experience (Linux)

- Ubuntu install image browser and manager Phototonic 1.6.17 (Linux)

- Linux crontab use (Linux)

- Seven kinds of NIC binding mode Detail (Linux)

- Camera-based face recognition OpenCV crawl and storage format (Python) (Linux)

- Linux program analysis tool: ldd and nm (Linux)

- Efficient running Linux virtual machine Six Tips (Linux)

- IOS interview questions Summary (Programming)

- Java eight new features 8 (Programming)

- Remote database using RMAN recovery test (RAC return to single-instance database) (Database)

- Four levels to deal with Linux server attacks (Linux)

- Turning off the interface eth0: error: Disconnect the device 'eth0' (Linux)

- MySQL optimization of the relevant Group By (Database)

 
         
  Single list summarizes the basic operation
     
  Add Date : 2018-11-21      
         
       
         
  List basic concepts:
List: the linear form of chain store.
Data field: storing data. That data.
Pointer Domain: storage location information of the next node. That is, the pointer to the next node.

Single list: each node node: a pointer to a data field + domain.
Head node:
1, the data fields can be stored linear table length and other public information.
2, the pointer field points to the first node (data field) position.
3, the first node of the list is not necessarily an essential element. But with the first node, prior to the first element node insert and delete elements, and other nodes on the agreement.
4, the head node and is easy to operate for the same establishment, the data field is generally meaningless, also store chain length.
Head pointer: pointer to the first node.
The last node: data field contains data; pointer field is empty, that is NULL.
If the linear table is empty, the head node pointer field is blank.
// Loop list: A single list of the terminal node pointer from the null pointer to point to the first node, the entire single-chain form a ring, end to end this short list of single circular list.
// Doubly linked list: each node in a single list, and then set a pointer to its predecessor node domain.

Single-chain basic operations are: create, outputs, measuring length, insert, delete, reverse position, ranking.

Singly linked list structure definition Code:

typedef struct Node {
    int data;
    struct Node * next;
} ListNode;
Creating a single-chain operations:

/ ** * Create a list /
ListNode * Create_list (int n) // Note that this function returns a pointer to Node pointer, n represents several nodes
{
    int elem, i;
    i = 1;
    ListNode * head, * current, * temp; / * current: a representative of the current node, the next node it is you're about to create; temp: on behalf of node you're about to create. * /
    head = new ListNode;
    head-> next = NULL;
    head-> data = n;
    current = head;

    while (i < = n) / * end interpolation: the new node on the tail * /
    {
        cout < < "please input elem:" < < endl;
        cin >> elem;

        temp = new ListNode;
        temp-> data = elem;
        temp-> next = NULL;
        current-> next = temp;
        current = temp;
        i ++;
    }

    return head;
}
Output operation:

/ ** * Output chain /
int Output_list (ListNode * head)
{
    ListNode * p;
    p = head-> next;
    if (p == NULL)
    {
        cout < < "The List is NULL" < < endl;
        return 0;
    }
    do {
        cout < < p-> data < < '';
        p = p-> next;
    } While (p = NULL!); // Here need to add ";"

    cout < < endl;

    return 0;
}
Measuring a linked list of nodes, namely length:

/ ** Measured length * /
int Length_test (ListNode * head)
{
    ListNode * p;
    int i = 0;
    p = head-> next;

    while (p! = NULL)
    {
        i ++;
        p = p-> next;
    }
    cout < < "The length of list is" < < i < < endl;
    return 0;
}
Insert node operation:

/ ** After the i-th node into a node, elem: that you want to insert data * /
ListNode * Insert_node (ListNode * head, int elem, int i)
{
    int j = 0;
    ListNode * p, * temp;
    temp = head-> next;
    / * Error writing
    while (NULL! = temp) find j after not out of the loop
    {
        j ++;
        if (j < = i)
            temp = temp-> next;
    }
    * /
    while (NULL! = temp)
    {
        j ++;
        if (j> = i) / ** pointer stop before the i-th node * /
            break;
        temp = temp-> next;
    }
    if (temp == NULL)
    {
        cout < < "There is no i" < < endl;
        return head;
    }
    p = new ListNode;
    p-> data = elem;
    p-> next = temp-> next;
    temp-> next = p;

    head-> data = head-> data + 1; / ** insert a node, the head node data saved plus a long list * /

    return head;
}
Delete operations:

/ ** Remove the i-th node * /
ListNode * Delete_node (ListNode * head, int i)
{
    int j = 0;
    ListNode * temp, * pre_temp;
    temp = head-> next;

    while (NULL! = temp)
    {
        j ++;
        if (j> = i)
            break;
        pre_temp = temp; / ** saved before the node * /
        temp = temp-> next;
    }
    if (temp == NULL)
    {
        cout < < "There is no i" < < endl;
        return head;
    }
    pre_temp-> next = temp-> next;
    / ** Here can not be written temp = temp-> next; because below delete temp; following nodes will delete * /

    delete temp;

    head-> data - = 1; / ** delete a node, the head node data saved Save a long list * /

    return head;
}
Retrograde operations:

/ ** Set against the single list, the first node of a node after a disconnect, use head interpolation inserted after the first node * /
ListNode * Reverse_list (ListNode * head)
{
    if (NULL == head)
        return head;
    if (NULL == head-> next)
        return head;
    if (NULL == head-> next-> next)
        return head;
    / ** To achieve the reverse position, in addition to the head node requires at least two data nodes * /

    ListNode * curr, * temp;
    curr = head-> next; / ** curr to save that string after disconnection * /
    head-> next = NULL; / ** head node and the node back off * /

    while (NULL! = curr)
    {
        / ** Temp played the role of a temporary substitute curr * /; temp = curr-> next
        curr-> next = head-> next; / ** * head interpolation /
        head-> next = curr;
        curr = temp; / ** temp function will return curr * /
    }
    return head;
}
Single list sorting (using the bubble sort method): This sorting algorithm, only exchange data without switching node

void Swap_data (int & a, int & b) / ** this must be added a reference character, or exchange no effect * /
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
ListNode * Sort_list (ListNode * head)
{
    int i, len;
    ListNode * p;
    len = head-> data;
    p = head-> next;
    if (NULL == p)
        cout < < "list is null" < < endl;
    for (i = 1; i < = len; i ++)
    {
        while (NULL! = p-> next)
        {
            if (p-> data> p-> next-> data)
                Swap_data (p-> data, p-> next-> data);
            p = p-> next;
        }
        p = head-> next;
    }
    return head;
}
A special function: used to find the single chain intermediate nodes do not know the total number of nodes in the case

/ ** I do not know the total number of nodes, can be obtained only once traverse intermediate node * /
/ ** This function has a problem, only an odd number of nodes solved when the node is even, there will be p-> next-> next meaningless case, the program error * /
/ * The principle is: to find two pointers, one at a time to go one step further each take two steps, take two steps when a pointer to the end, just go step pointer at the intermediate node * /
void Search_mid (ListNode * head)
{
    ListNode * p_1, * q_2;
    ListNode * mid;
    p_1 = head-> next;
    q_2 = head-> next;
    while (NULL! = q_2-> next)
    {
        p_1 = p_1-> next;
        q_2 = q_2-> next-> next;
        mid = p_1;
    }
    cout < < "intermediate values:" < < mid-> data < < endl;
}
Test main function:

int main ()
{
    ListNode * p;
    int a = 3;
    int b = 4;
    p = Create_list (5);
    cout < < "The list is:" < < endl;
    Output_list (p);
    Length_test (p);

    p = Insert_node (p, 6,5);
    cout < < "after the insertion node:" < < endl;
    Output_list (p);
    cout < < "New length:" < < p-> data < < endl;

    p = Delete_node (p, 3);
    cout < < "to remove a node after:" < < endl;
    Output_list (p);

    p = Reverse_list (p);
    cout < < "Retrograde after:" < < endl;
    Output_list (p);

    p = Sort_list (p);
    cout < < "sorted (small to large):" < < endl;
    Output_list (p);

    cout < < "original ab:" < < a < < b < < endl;
    Swap_data (a, b);
    cout < < "Following the exchange:" < < a < < b < < endl;

    Search_mid (p);

    return 0;
}
     
         
       
         
  More:      
 
- Hadoop - Task Scheduling System Comparison (Server)
- Ubuntu program using the Sound Recorder (Linux)
- Ten to improve the efficiency of the Linux bash tricks (Linux)
- SUSE Linux network configuration and firewall configuration (Linux)
- Golang use Oracle database on Ubuntu 14.04 (Linux)
- Shutdown - an advanced shutdown artifact (Linux)
- RedHat6.4 installation tutorial --- Minimal Edition (Linux)
- Why did not Oracle privileges can also log in with sysdba (Database)
- Make command Detailed Tutorial (Programming)
- JavaScript event handling Detailed (Programming)
- Json data with double backslashes to a single backslash Json data processing (Programming)
- How to disable IPv6 in the CentOS 7 (Linux)
- Using Maven to download Spring (Linux)
- Linux basic introductory tutorial ---- Software Installation under Linux (Linux)
- Ubuntu GCC, G ++ and fortran Version Switch (Linux)
- Linux kernel log --dmesg (Linux)
- Python 2.7.9 Installation on Linux CentOS 6.6 (Linux)
- Cross server / client backup command: rsync use (Server)
- Shell Common Command Summary (Programming)
- Fatal NI connect error 12170 error in Alert Log (Database)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.