向顺序表插入元素的时候需要移动大量的数据

链表采用动态存储分配，

可以根据需要申请内存单元

#include "stdafx.h"
#include "stdlib.h"
#include "string.h"
typedef struct{
    char key[15];
    char name[20];
    int age;
}DATA;
 
typedef struct Node{
    DATA data;
    struct Node * next;
 
}ChainListType;
//  添加到节点的尾部
    ChainListType * ChainListAddEnd(ChainListType * head,DATA data){
        //head 为链表的头指针,data为节点保存的数据
        ChainListType *node, *h;
        //因为需要动态分配内存 所以需要引入 stdlib.h 头文件
        if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))){
            printf("为保存的节点数据申请内存失败");
            return NULL;
        }
        node->data = data;
        node->next = NULL;
        if (head == NULL){
            head = node;
            return head;
        }
        h = head;
        while (h->next!=NULL)
            h = h->next;
            h->next = node;
            return head;
}
        //添加节点到首部
    ChainListType * ChainListAddFirst(ChainListType *head,DATA data){
        ChainListType * node, *h;
        if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))){
            printf("为保存的节点数据申请内存失败");
            return NULL;
        }
        node->data = data;
        node->next = head;     //指向头指针所指节点
        head = node;          //头指针指向新增节点
        return head;
 
    }
    //按照关键字查找节点
    ChainListType * ChainListFind(ChainListType * head,char *key){
        ChainListType *h;
        h = head;
        while (h)
        {
            if (strcmp(h->data.key, key) == 0){      //若节点的关键字与传入关键字相同
                return h;                          //  返回该节点指针
                h = h->next;                       //  处理下一个节点
            }
        }
    }
    //插入节点到链表
    ChainListType * ChainListInsert(ChainListType *head,char *findkey,DATA data){
        ChainListType * node, *node1;
        if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))){
            printf("为保存的节点数据申请内存失败");
            return 0;
        }
        node->data = data;
        node1 = ChainListFind(head, findkey);
        if (node1){
            node->next = node1->next;
            node1->next = node;
        }
        else{
            free(node);
            printf("未找到插入位置\n");
         
        }
        return head;
    }
    //删除节点
    int ChainListDelete(ChainListType *head, char *key){
        ChainListType *node, *h;
        node = h = head;
        while (h){
            if (strcmp(h->data.key, key) == 0){
                node->next = h->next;
                free(h);
                return 1;
            }
            else{
                node = h;
                h = h->next;
            }
        }
        return 0;
    }
    void ChainListAll(ChainListType *head){
        ChainListType *h;
        DATA data;
        h = head;
        printf("链表所有的数据如下\n");
        while (h)
        {
            data = h->data;
            printf("%s%s%d\n", data.key, data.name, data.age);
            h = h->next;
        }
    }
    //统计链表的长度
    int ChainListLength(ChainListType * head){
        ChainListType *h;
        int i = 0;
        h = head;
        while (h){
            i++;
            h = h->next;
        }
        return i;
    }

int main(){
    ChainListType *node, *head = NULL;
    DATA data;
    char key[15], findkey[15];
    printf("输入链表中的数据.包括关键字,姓名,年龄,关键字输入0\n");
    do{
        fflush(stdin);
        scanf("%s", data.key);
        if (strcmp(data.key, "0") == 0) break; //若输入0，则退出
        scanf("%s%d", data.name, &data.age);
        head = ChainListAddEnd(head, data);
    } while (1);
    ChainListAll(head);
     
    printf("在链表中查找,请输入关键字\n");
    fflush(stdin);      //  清空输入缓冲区
    scanf("%s", key);
    node = ChainListFind(head, key);
    if (node){
        data = node->data;
        printf("关键字%s对应的节点数据(%s,%s,%d)\n",key,data.key,data.name,data.age);
    }
    else{
        printf("在链表中未找到关键字为%s的节点\n", key);
    }
 
    printf("在链表中删除节点,输入要删除的关键字\n");
    fflush(stdin);
    scanf("%s", key);
    ChainListDelete(head, key);
    ChainListAll(head);
    //getch();
    system("pause");
}