数据结构的基本技能

2.链式结构

链表的增删改查

#include<iostream>
#include<string.h>
using namespace std;

typedef struct Student_Information
{
    char key[10];
    char name[20];
    int age;
}Data;

typedef struct Node
{
    Data val;
    Node* next;
    Node(Data x):val(x),next(nullptr){}  //构造函数
}CLType;

/**追加节点**/
CLType *CLAddEnd(CLType *head,Data data)
{
    CLType *node=new CLType(data);       //新节点
    CLType *cur;
    if(head==nullptr) {
            head=node;
            return head;
    }
    else{
        cur=head;
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        cur->next=node;
        return head;
    }
}

/**头插法**/
CLType *CLAddFirst(CLType *head,Data data)
{
    CLType *node=nullptr;               //默认构造函数（空节点）
    node->val=data;
    node->next=head;
    head=node;
    return head;
}

/**查找节点**/
CLType *CLFindNode(CLType *head,char* key)
{
    CLType *cur;
    cur=head;
    while(cur){
        if(strcmp(cur->val.key,key)==0){
            return cur;
        }
        cur=cur->next;
    }
    return nullptr;
}

/**某一位置插入节点**/
CLType *CLInsertNode(CLType *head, char* findkey,Data data)
{
    CLType *node=new CLType(data);       //新节点
    CLType *findnode=CLFindNode(head,findkey);
    if(findnode){
        node->next=findnode->next;
        findnode->next=node;
    }
    else{
        cout<<"未找到正确的插入位置！"<<endl;
        delete node;
    }
    return head;
}

int CLDeleteNode(CLType *head,char* key)
{
    CLType *cur=head;
    CLType *pre=head;
    if(strcmp(cur->val.key,key)==0)  /**删除头部节点**/
    {
        pre=cur->next;
        delete cur;
        return 1;
    }
    while(cur){                      /**删除非头部节点**/
        if(strcmp(cur->val.key,key)==0){
            pre->next=cur->next;
            delete cur;
            return 1;
        }
        pre=cur;
        cur=cur->next;
    }
    return 0;
}

int CLLength(CLType *head)
{
    CLType *cur=head;
    int len=0;
    while(cur)
    {
        len++;
        cur=cur->next;
    }
    return len;
}

void CLAllNode(CLType *head)
{
    CLType *cur=head;
    Data data;
    cout<<"当前共有节点个数为："<<CLLength(head)<<endl;
    while(cur)
    {
        data=cur->val;
        cout<<"节点数据为："<<data.key<<" "<<data.name<<" "<<data.age<<endl;
        cur=cur->next;
    }
}

int main()
{
    CLType *node,*head=nullptr;
    Data data;
    char key[10],findkey[20];

    cout<<"链表测试！先输入链表中的数据，格式为：关键字 名字 年龄: "<<endl;;
    do{
        cin>>data.key;
        if(strcmp(data.key,"0")==0) break;
        else{
            cin>>data.name>>data.age;
            head=CLAddEnd(head,data);
        }
    }while(1);
    CLAllNode(head);    //显示所有节点

    cout<<"开始插入节点，输入关键字（插入的位置）: ";
    cin>>findkey;
    cout<<"先输入要插入的数据，格式为：关键字 名字 年龄: ";
    cin>>data.key>>data.name>>data.age;
    CLInsertNode(head, findkey,data);
    CLAllNode(head);

    cout<<"开始删除节点，输入关键字: ";
    cin>>key;
    CLDeleteNode(head,key);
    CLAllNode(head);

    cout<<"开始查找节点，输入关键字: ";
    cin>>key;
    node=CLFindNode(head,key);
    if(node)
    {
        data=node->val;
        cout<<"节点数据为："<<data.key<<" "<<data.name<<" "<<data.age<<endl;
    }
    else{
        cout<<"未找到该节点！"<<endl;
    }
}