源码分析单链表和顺序表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。顺序表是在计算机内存中以数组的形式保存的线性表，采用顺序存储结构的线性表简称为“ 顺序表”。单链表和顺序表尽管都是表，但是有着大不相同的数据结构。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。而线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。从整体考虑, 顺序表要预分配存储空间, 如果预先分配得过大, 将造成浪费, 若分配得过小, 又将发生上溢;单链表不需要预先分配空间, 只要内存内存空间没有耗尽, 单链表中的结点个数就没有限制。下面我们从源码进行分析：

1.顺序表的完整代码

#include <stdio.h>

// 定义一个结构体类型

typedef struct {

    char name[10];

    int age;

} DataType;

// 顺序表的结构体定义

// 线性表的大小, 也就是最多存储多少个数据元素

const int maxSize = 100;

typedef struct {

    // 所存放的数据类型为int, 最多存放100个元素的数组

    DataType data[maxSize];

    // 当前所存放的数据元素的个数

    int length;

} SeqList;

/**

 线性表的插入

 @param pList 类型为SeqList的结构体指针

 @param x 要插入的类型为DataType类型的数据元素

 @param i 要插入的位置

*/

void insertSeqList(SeqList * pList, DataType x, int i) {

    // 判断线性表是否已满

    if (pList->length == maxSize) {

        printf("表已满 \n");

        return;

    }

    // 检查插入位置是否合法

    if (i < 1 || i > (pList->length) + 1) {

        printf("插入位置不合法 \n");

        return;

    }

    // 进行插入操作

    // 从表的最后一个位置依次进行后移

    for (int j = pList->length; j >= i; j--) {

        pList->data[j] = pList->data[j-1];

    }

    // 后移完成之后, 对空出的位置进行赋值

    pList->data[i - 1] = x;

    // 表的长度加1

    pList->length++;

}

/**

 线性表的删除

 @param pList 类型为SeqList结构体的指针

 @param i 要删除的位置

 */

void deleteSeqList(SeqList * pList, int i) {

    // 检查删除位置是否合法

    if (i < 1 || i > pList -> length) {

        printf("删除位置不合法");

        return;

    }

    // 进行删除操作, 依次左移

    for (int j = i; j < pList->length; j++) {

        pList->data[j - 1] = pList->data[j];

    }

    // 表的长度减1

    pList->length--;

}

/**

 线性表的定位

 @param pList 类型为SeqList结构体的指针

 @param name 要查找的姓名

 @return 查找到的元素的位置

 */

int locateSeqList(SeqList * pList, char name[]) {

    int i = 0;

    // 在顺序表中查找值为name的结点

    while (i < pList->length && pList->data[i].name == name) {

        i++;

    }

    // 若找到值为name的结点, 则返回结点的序号

    if (i < pList->length) {

        return i + 1;

    } else { // 未找到值为name的结点, 返回0

        return 0;

    }

}

int main(int argc, const char * argv[]) {

    // insert code here...

    // 创建一个结构体实例, 并进行初始化

    DataType dt1 = {"alex", 18};

    DataType dt2 = {"kevin", 16};

    DataType dt3 = {"jack", 21};

    // 创建一个空的线性表

    SeqList list = {};

    // 创建一个指针指向这个线性表

    SeqList * pList = &list;

    printf("插入前表的长度: %d \n", list.length);

    // 插入操作

    insertSeqList(pList, dt1, 1);

    insertSeqList(pList, dt2, 1);

    insertSeqList(pList, dt3, 1);

    printf("插入后表的长度: %d \n", list.length);

    // 删除操作

    deleteSeqList(pList, 2);

    printf("插入后表的长度: %d \n", list.length);

    // 定位

    int loc = locateSeqList(pList, "alex");

    printf("alex在第%d位 \n", loc);

    return 0;

}

2.单链表的完整代码

#include <stdio.h>

#include <stdlib.h>

// 声明一个结构体类型

typedef struct {

    char name[12];

    int age;

} DataType;

// 声明一个单链表类型

typedef struct node {

    DataType data; // 数据域

    struct node * next; // 指针域

} Node, * LinkList;

/**

 初始化一个单链表

 @return 初始化好的单链表

 */

LinkList initiateLinkList() {

    // 头指针

    LinkList head;

    // 动态创建一个结点, 也就是头结点, 然后让头指针指向这个结点

    head = malloc(sizeof(Node));

    // 头结点的指针域为NULL

    head->next = NULL;

    // 返回这个单链表

    return head;

}

/**

 求表的长度

 @param list 单链表

 @return 表的长度

 */

int LengthLinkList(LinkList list) {

    // 用于计数

    int j = 0;

    // p指向头指针

    LinkList p = list;

    // 当下一个结点不为空时, 计数加1, p指向下一个结点

    while (p->next != NULL) {

        j++;

        p = p->next;

    }

    // 返回表的长度

    return j;

}

/**

 读表元素

 @param list 单链表

 @param i 要读取的位置

 @return 如果有返回读取到的元素, 没有则返回NULL

 */

LinkList getLinkList(LinkList list, int i) {

    // 用于计数

    int j = 1;

    // p指向首结点

    LinkList p = list->next;

    while (j < i && p != NULL) {

        j++;

        p = p->next;

    }

    // 如果j等于i, 则p指向的结点为要找的结点

    if (j == i) {

        return p;

    } else { // 否则没有要找的结点

        return NULL;

    }

}

/**

 插入

 @param list 单链表

 @param x 要插入的数据元素

 @param i 要插入的位置

 */

void insertLinkList(LinkList list, DataType x, int i) {

    LinkList s, p;

    if (i == 1) {

        p = list;

    } else {

        // 找到第 i-1 个数据元素结点

        p = getLinkList(list, i - 1);

    }

    if (p == NULL) {

        // 如果不存在, 返回错误信息

        printf("找不到插入的位置");

    } else{

        // 生成新结点并初始化

        s = malloc(sizeof(Node));

        s->data = x;

        // 新结点的指针域指向第i个元素

        s->next = p->next;

        // 第 i-1 个结点的指针域指向新结点

        p->next = s;

    }

}

/**

 删除

 @param list 单链表

 @param i 要删除结点的位置

 */

void deleteLinkList(LinkList list, int i) {

    LinkList p;

    // 找到待删结点的直接前驱

    if (i == 1) {

        p = list;

    } else {

        p = getLinkList(list, i-1);

    }

    // 若直接前驱存在, 且待删结点存在

    if (p != NULL && p->next != NULL) {

        // q指向待删结点

        LinkList q = p->next;

        // 移出待删结点

        p->next = q->next;

        // 释放已经移出的结点

        free(q);

    } else {

        printf("要不到要删除的结点");

    }

}

/**

 定位

 @param list 单链表

 @param name 要查找的结点的名字

 @return 如果查找到了, 则返回结点的位置, 如果没有, 则返回0

 */

int locateLinkList(LinkList list, char name[]) {

    int j = 0;

    // p指向首结点

    LinkList p = list->next;

    // 查找结点

    while (p != NULL && !(strcmp(p->data.name, name) == 0)) {

        j++;

        p = p->next;

    }

    // 如果有则返回序号, 没有返回0

    if (p != NULL) {

        return j + 1;

    } else {

        return 0;

    }

}

int main(int argc, const char * argv[]) {

    // insert code here...

    Node list = {};

    LinkList pList = &list;

    DataType dt1 = {"jack", 18};

    DataType dt2 = {"kevin", 20};

    // 插入元素

    insertLinkList(pList, dt1, 1);

    insertLinkList(pList, dt2, 1);

    // 读表元素

    LinkList p = getLinkList(pList, 2);

    printf("%s \n", p->data.name);

    // 删除元素

//    deleteLinkList(pList, 2);

//    deleteLinkList(pList, 1);

    // 读表长

    int length = LengthLinkList(pList);

    printf("表的长度为: %d \n", length);

    // 定位

    int loc = locateLinkList(pList, "kevin");

    printf("在第%d位 \n", loc);

    return 0;

}

本文我们从源码分析了顺序表和单链表的不同，以及顺序表和单链表两者数据结构和存储结构的不同点，尽管都和线性表有一定关系，但是还是要区别对待，避免混淆概念。在本站数据结构和算法教程中，对每种常见的数据结构都有着非常透彻的讲解，欢迎小伙伴们一起学习探讨学习数据结构过程中遇到的问题，实现共同进步！