前言

最近在看《数据结构与算法分析——C语言描述》，看到第三章表、栈、队列。这一章看完略显吃力，书中的代码倒还懂，但只说了几个主要的插入，删除方法，而自己看完后想自己运行一遍，而mac上只有Visual Studio Code来编写。
结果图：

结果.png

自己也按照书中的方法定义

struct Node
{
    int id;
    int score;
    struct Node * next; 
} ;

struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List scan_list(); //链表的输入
void print_list(List l); //链表的打印

//测试一个表是否为空表
int IsEmpty(List l);
//测试当前位置是否为链表的末尾
int IsLast(List  l);
//查找
Position  Find(int data, List l);
//查找元素的前一个
Position FindPrevious (int data,List l);
//插入一个元素
void Insert (int data,List l,Position P);
//删除指定元素
void Delete(int data,List L);

创建链表

想着自己手动输入创建一个链表，首先创建一个表头，后面再一个个元素的指向。定义了打印方法,测试空表的方法。

struct Node *scan_list()
{
    int id;
    List list_temp = NULL;
    List list_head = NULL;
    list_temp = list_head;
    cout<<"请输入id和score:"<<endl;
    while(cin >>id){
        List list_body = new Node();
        list_body->id = id;
        cin >> list_body->score;
        list_body->next = NULL;

        if (list_head == NULL ) {
            list_head = list_body; 
        }else
        {
            list_temp->next = list_body;
        }
        list_temp = list_body;
        
        
    }
    return list_head;
    
}

void print_list(List l)
{
    // Node * list_temp = list_head;
    List list_temp ;
    list_temp = l;
    cout << "打印所有元素===" <<endl;
    while( list_temp != NULL ){
        cout << "id:"<<list_temp->id <<"\t" <<"score:"<<list_temp->score <<endl;
        list_temp = list_temp->next;
    }
    cout << "======end===="<<endl;
    
}

//测试当前位置是否为链表的末尾
int IsLast(List l)
{
    return l->next == NULL;
}

查找

这里只查找第一次出现的data，这里并没有把所有的包含data都查找出来。

//查找
Position Find(int data,List l)
{
    List temp ;
    temp = l;
    while(temp != NULL && temp->id != data){
        temp = temp->next;
    }
     cout << "id:"<<temp->id <<"\t" <<"score:"<<temp->score <<endl;
    return temp;
    
}

插入

把元素插入到位置P处

//插入一个元素
void Insert (int data,List l,Position P)
{
    Position tempCell;
    tempCell = new Node();
    tempCell->id =data;
    tempCell->next = P->next;
    P->next = tempCell;
}

删除

先查出要删除元素的前一个数，再改变指向

//删除指定元素
void Delete(int data,List L)
{
    Position P,tempCell;
    P = FindPrevious(data,L);
    if (!IsLast(P)) {
        tempCell = P->next;
        P->next = tempCell->next;
        free(tempCell);
    }
    
}
//查找元素的前一个
Position FindPrevious (int data,List l)
{
    Position P;
    P = l;
    while(P->next != NULL && P->next->id != data){
        P = P->next;
    }
    cout << "查找过元素的前一个 id:"<<P->id <<"\t" <<"score:"<<P->score <<endl;
    return P;
    
}

测试

int main(int argc, char const *argv[])
{
    /* code */
    List temp = scan_list();
    int check = IsEmpty(temp);
    cout <<"检测是否是xx空表"<<check<<endl;
    print_list(temp);

    cout <<"查找元素id =5 \n"<<endl;
    List result = Find(5,temp);
    FindPrevious(5,temp);

    cout <<"插入元素id = 99 \n"<<endl;
    Insert(99,temp,result);
    print_list(temp);

    cout <<"删除元素id = 99 \n"<<endl;
    Delete(99,temp);
    print_list(temp);

    return 0;
}