C语言数据结构——线性表的链式存储结构

线性表的链式存储结构

1.基本概念

链式存储定义：为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息之外，还需要存储指示其直接后继的信息。

n个结点连接成一个链表，即为线性表(a1 a2 a3…an)的链式存储结构，因此此链表的每个结点中包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

组成部分
表头结点：链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
数据结点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息

2.设计与实现

首先先创造一个整体的框架，先自定一个header文件，然后把想要实现的方法写入，然后直接在主程序中导入此头文件
header.h

//
// Created by 2NaCl on 2019/2/20.
//

#ifndef CPRIMERPLUS_HEADER_H
#define CPRIMERPLUS_HEADER_H

typedef void LinkList;//声明一下线性表

typedef struct _tag_LinkListNode{
    struct LinkListNode *next;
}LinkListNode;

LinkListNode node1;

LinkList *LinkList_Create();//创建一张线性表

void LinkList_Destroy(LinkList *list);//销毁一张线性表

void LinkList_Clear(LinkList *list);//清空结点元素

int LinkList_Length(LinkList *list);//返回线性表的长度

int LinkList_Insert(LinkList *list,LinkList *node,int pos);//向SeqList链表pos的位置插入一个结点node

LinkListNode *LinkList_Get(LinkList *list , int pos);//获取pos位置元素

LinkListNode *LinkList_Delete(LinkList *list,int pos);//删除pos位置元素

#endif //CPRIMERPLUS_HEADER_H

然后我们编写测试程序，调用我们拟定好的实现方法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "header.h"

typedef struct Teacher{
    LinkListNode node;//老师是大结点，让大结点包含链表结点，形成链式存储结构
    int age;
    char name[30];
}Teacher;

int main(){
    int len = 0,ret = 0;
    LinkList *list = NULL;
    Teacher t1,t2,t3,t4,t5;
    t1.age=30;
    t2.age=31;
    t3.age=32;
    t4.age=33;
    t5.age=34;
    list = LinkList_Create();
    if (list == NULL) {
        return 0;
    }
    LinkList_Length(list);
    ret = LinkList_Insert(list, (LinkListNode *) (&t1), 0);
    ret = LinkList_Insert(list, (LinkListNode *) (&t2), 0);
    ret = LinkList_Insert(list, (LinkListNode *) (&t3), 0);
    ret = LinkList_Insert(list, (LinkListNode *) (&t4), 0);
    ret = LinkList_Insert(list, (LinkListNode *) (&t5), 0);

    for (int i = 0; i < LinkList_Length(list); ++i) {
        Teacher *teacher = (Teacher *) LinkList_Get(list, i);
        if (teacher==NULL) {
            printf("404");
        }
        printf("teacher->age:%d\n", teacher->age);
    }

    while (LinkList_Length(list) > 0) {
        Teacher *teacher = (Teacher *) LinkList_Delete(list, 0);
        if (teacher == NULL) {
            printf("404");
        }
        printf("teacher->age:%d\n", teacher->age);
    }

    LinkList_Destroy(list);


    system("pause");
}

最后把细节写好，本文采用的还是头插法，下面开始写具体实现方法的实现顺序
1.搭建链表框架
我们之前提到了，要在大的Teacher结点中，放入一个链表结点，然后连接所有的链表结点，实现链表，也就是说，这个链表框架的功能就是穿针引线，将内部的链表结构串联起来。

typedef struct _tag_LinkList{
    LinkListNode header;
    int length;
}tLinkList;

2.创建链表并且为其分配存储空间，和之前的顺序结构相差无几，也要在分配完链表的存储空间后使用到memset方法

LinkList *LinkList_Create(){
    tLinkList *ret = NULL;
    ret = (tLinkList *) malloc(sizeof(tLinkList));
    memset(ret, 0, sizeof(tLinkList));
    ret->length = 0;
    ret->header.next = NULL;
    return NULL;
}

3.然后是销毁链表，和顺序存储结构不相同的是，只需要一次free即可，free的就是链表内部的内存

void LinkList_Destroy(LinkList *list){
    if (list != NULL) {
        free(list);
        list = NULL;
    }
    return;
}

4.然后写clear方法，clear的目的是让链表回到初始值

void LinkList_Clear(LinkList *list){
    tLinkList *tLinkList1 = NULL;
    if (list == NULL) {
        return;
    }
    tLinkList1 = (tLinkList *) list;
    tLinkList1->header.next = NULL;
    tLinkList1->length = 0;
}

5.求链表长度

int LinkList_Length(LinkList *list){
    tLinkList *linkList1 = NULL;
    if (list == NULL) {
        return 0;
    }
    linkList1 = (tLinkList *) list;
    return linkList1->length;
}

6.链表的插入操作
其实道理很简单，指针指向谁，就把谁的地址赋给指针，主要注意辅助变量之间的关系就可以了。
画图说明：

现在想要让node结点插入到2和3中，就需要执行以下操作（因为链表是单向的，3号位置要保存在2号位置的next域中）：
(1).node->next = current2->next;
(2).current2 ->next = node;

int LinkList_Insert(LinkList *list,LinkListNode *node,int pos){
    int ret = 0;
    LinkListNode *current = NULL;
    tLinkList *tList = NULL;
    if (pos < 0 || node == NULL || list == NULL) {
        ret = 0;
        printf("Insert有错误");
        return 0;
    }
    tList = (tLinkList *) list;
    current = &(tList->header);

    for (int i = 0; i < pos && (current->next != NULL); ++i) {
        current = current->next;
    }
    //用node连接后续链表
    node->next = current->next;
    //让前面的链表使用到node
    current->next = node;

    tList->length ++ ;
    return 0;
}

7.获取链表中的结点

LinkListNode *LinkList_Get(LinkList *list, int pos) {
    int ret = 0;
    tLinkList *tList = NULL;
    LinkListNode *current = NULL;
    if (pos < 0 || list == NULL) {
        printf("get出错");
        return 0;
    }
    tList = (tLinkList *) list;
    current = &(tList->header);
    for (int i = 0; i < pos && (current->next != NULL); i++) {
        current = current->next;
    }
    return current->next;
}

8.删除列表中的某个结点

现在要让current2跳过current3，直接next就是current4
核心步骤：
先声明一个辅助指针ret，然后
ret = current2->next;
current2->next=ret ->next;

LinkListNode *LinkList_Delete(LinkList *list,int pos){
    int i = 0;
    LinkListNode *current = NULL;
    LinkListNode *ret = NULL;
    tLinkList *tlist = NULL;
    if (list == NULL || pos < 0) {
        int ret = 0;
        printf("Delete出错");
        return NULL;
    }

    tlist = (tLinkList *) list;
    current = (&tlist->header);
    for (int i = 0; i < pos && (current->next != NULL); i++) {
        current = current->next;
    }
    //缓存被删除的结点
    ret = current->next;
    current->next = ret->next;
    return ret;

}

3.优点和缺点

优点：
无需一次性定制链表的容量
插入和删除操作无需移动数据元素
缺点：
数据元素必须保存后继元素的位置信息
获取指定元素的数据操作需要顺序访问之前的元素。