Xiao Xu

The so-called Pu-Yu is not refined, comparing itself to Pu-Yu is really an old face and no need, ha-ha. After learning C language, I have been idle for several years. Now I decide to learn data structure. I think of the teacher who said to do more exercises in the course of data structure before. It's a pity that so many youths have been lost by their happy waves. In order to be able to record the process of learning data structure, so I open this blog to urge myself not to be lazy again, but also hope to be able to get online Daniel's guidance, if I can help you, that is also an excellent thing. Okay, there's too much gossip. Get to the point.
Learning data structure is, of course, starting from the most basic data structure, which includes tables, queues and stacks. Summarize the table today.

Why not use arrays to implement tables

1. Before using arrays, the size of arrays should be specified in advance. When the size of tables can not be estimated beforehand, it is necessary to define a large array to prevent overflow, which may waste a lot of memory space.
2. When table is interpolated or deleted, all data after interpolation or deletion need to be shifted. The time cost is unavoidable, and the worst case is O(N).
3. If you use interpolation to create a list, it's obvious that time is expensive.
   In short, because insertion and deletion run so slowly and the size of tables must be known beforehand, simple arrays are generally not used to implement the data structure of tables.

linked list

To avoid the time-linearity overhead during insertion and deletion, we need to allow tables to be stored discontinuously, otherwise some or all of the tables need to be moved as a whole. Link list is a solution to the above problems. A linked list consists of a series of structures that do not need to be connected in memory. Each structure contains a table element and a pointer to the structure containing the successor elements of that element. We call this pointer Next pointer (a two-way linked list should have another forward pointer). Next in the last cell points to the null pointer NULL.

So much has been said before, of course, the most direct way is to add comments to the code.

header file

//Prototype of Defining Tables and Operating Functions in Header Files
#ifndef _List_H
struct Node;         //Structures that declare a table node unit
typedef int ElementType;      //Redefining the member type in the structure so that you can modify the location and change the data type as needed
typedef struct Node *PtrToNode;     //Redefining the pointer type pointing to the Node type to facilitate the subsequent type definition
typedef PtrToNode List;       //Equivalent to Node *List is generally used to point to the header position
typedef PtrToNode Position;      //Equivalent to Node*Position to point to the specified location in the table

List MakeEmpty(List L);      //Clear a linked list into empty lists
int IsEmpty(List L);      //Judging whether the table is empty
int IsLast(Position P,List L);       //Determine whether P points to the end of the list
Position Find(ElementType X,List L);      //Returns the location of element X in the list
void Delete(ElementType X,List L);       //Delete the X element from the list
Position FindPrevious(ElementType X,List L);        //Find the location of the previous unit of element X
void Insert(ElementType X,List L,Position P);      //Insert an element X behind the position P points to
void DeleteList(List L);      //Delete the linked list and recycle the deleted units, leaving an empty list.
//Position Header(List L);
//Position First(List L);
//Position Advance(Position P);
//ElementType Retrieve(Position P);
#endif // _List_H

source file

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "list.h"// Include the header file
struct Node
{
    ElementType Element;
    Position Next;    // Node *Next
}; //The structure of Node node is defined, including member elements and Next pointer to the next node.

After defining the data structure, we define the operation related to the data structure.
The complete source code is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "list.h"
struct Node
{
    ElementType Element;
    Position Next;
};
List MakeEmpty(List L)
{
    L->Next = NULL;
    return L;
}
int IsEmpty(List L)
{
    return L->Next == NULL;
}
int IsLast(Position P,List L)
{
    return P->Next == NULL;
}
Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while(P != NULL && P->Element != X)
        P = P->Next;
    return P;
}
Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while(P->Next != NULL && P->Next->Element != X)
        P = P->Next;
    return P;
}
void Delete(ElementType X, List L)
{
    Position P,TmpNode;
    P = FindPrevious(X,L);
    if(!IsLast(P,L))
    {
        TmpNode = P->Next;
        P->Next = TmpNode ->Next;
        free(TmpNode);
    }
    //P->Next = P->Next->Next;
    //free(P->Next);
}
void Insert(ElementType X, List L, Position P)
{
    Position TmpNode;
    TmpNode = malloc(sizeof(struct Node));
    TmpNode->Element = X;
    TmpNode->Next = P->Next;
    P->Next = TmpNode;
}
void DeleteList(List L)
{
    Position P,TmpNode;
    P = L->Next;
    L->Next = NULL;
    while(P->Next != NULL)
    {
        TmpNode = P->Next;
        free(P);
        P = TmpNode;
    }
}
int main()
{
    printf("Hello world!\n");
    List myList = malloc(sizeof(struct Node));
    myList = MakeEmpty(myList);
    Position p;
    p = myList;
    myList->Element = 0;
    int i;
    for(i = 1; i<5;i++)
    {
        Insert(i,myList,p);
        p = p->Next;
    }

    printf("list->element = %d\n",myList->Element);
    printf("List->Next->Element = %d\n",myList->Next->Element);
    p = Find(3,myList);
    printf("find 3 in myList = %d\n",p->Element);
    p = FindPrevious(3,myList);
    printf("previous element of 3 = %d\n",p->Element);
    Delete(2,myList);
    p = Find(2,myList);
    //printf("debug = %d\n",p->Element);
    if(p == NULL)
        printf("cant find element 2 in myList.\n");
    p = Find(4,myList);
    if(IsLast(p,myList))
        printf("position of element 4 is last of myList.\n");
    DeleteList(myList);
    if(IsEmpty(myList))
        printf("myList has been deleted!\n");

    return 0;
}

The final output is as follows:

Note**

It needs to be noted that when using linked list, we should first apply for a section of memory dynamically, otherwise the definition of myList may point to important data, which may cause unexpected problems!!!
The definition of function is very simple, there is not much need to explain, but when I write Delete function myself, there is a problem that the function does not work properly. Specially post the code for illustration:

void Delete(ElementType X, List L)
{
    Position P,TmpNode;
    P = FindPrevious(X,L);
    if(!IsLast(P,L))
    {
        TmpNode = P->Next;
        P->Next = TmpNode ->Next;
        free(TmpNode);
    }
    //P->Next = P->Next->Next;
    //free(P->Next);
}

Free (P - > Next) is used between visible and visible, which means that the program cannot work properly, but must be deleted through a transient TmpNode. What is the reason for this? In fact, it's good to develop a habit of drawing and understanding data structures from time to time.
As you can see from the figure, if you don't define an intermediate variable TmpNode, then execute free directly (P - > Next); you will delete the last unit of X element, and the linked list is broken, so the program will collapse. For this kind of low-level mistakes, I think it's only my new learning rookie who will encounter them, but I also hope that here I can teach myself a lesson, and give a hint to friends who may see this text. Learning data structure often draws pictures, which will avoid many problems.

Since you have just learned the data, you are entitled to take your own notes. There will inevitably be some mistakes in the process of summarizing. I also hope that you can point out that you are welcome to exchange information.^^

PS

The first editing blog of Zhenger Bajing, the typesetting itself feels too LOW, haha!