嵌入式培训之数据结构学习（二）顺序表与单向链表

目录

一、顺序表

（一）顺序表的基本操作

1、创建顺序表

2、销毁顺序表

3、遍历顺序表

4、尾插，在顺序表的最后插入元素

5、判断表是否满

6、判断表是否空

7、按指定位置插入元素

8、查找元素，根据名字

9、根据名字修改指定元素

10、根据名字删除指定元素

11、清空表，清空表中已有的元素

12、获得表中有效元素的个数

13、获得指定下标的元素本身

（二）顺序表优缺点

二、链表

（一）链表基础概念

（二）单向链表（重点）

（三）单向链表的基本操作

1、创建链表

2、判断链表是否为空

3、获取链表长度

4、头插，在链表的前面插入一个结点

5、遍历打印链表

6、根据名字查找链表中的结点

7、根据名字删除链表中的结点

---

一、顺序表

（一）顺序表的基本操作

1、创建顺序表

SeqList *CreateSeqList(int len)

{
    SeqList *sl = malloc(sizeof(SeqList));  // 分配顺序表结构体空间
    if (NULL == sl) {
        fprintf(stderr, "CreateSeqList malloc error\n");  // 分配失败报错
        return NULL;
    }
    sl->head = malloc(sizeof(DATATYPE) * len);  // 分配数据存储数组空间
    if (NULL == sl->head) {
        fprintf(stderr, "CreateSeqList malloc2 error\n");  // 数组分配失败报错
        return NULL;
    }
    sl->tlen = len;  // 存储总长度（最大容量）
    sl->clen = 0;    // 初始元素个数为0
    return sl;       // 返回顺序表指针
}

2、销毁顺序表

int DestroySeqList(SeqList *list)

{
        if(NULL == list)

        {
                return 1; // 空指针返回错误码1
        }
         //先检查顺序表指针是否为空
 
        free(list->head); // 释放数据存储区（动态分配的数组）
        free(list); // 释放顺序表结构体本身
        return 0; // 销毁成功，返回0
        //先释放数据区内存，再释放顺序表结构体内存，避免内存泄漏

}

3、遍历顺序表

int ShowSeqList(SeqList *list)

{
    int len = GetSizeSeqList(list);  // 获取当前元素个数
    int i = 0;
    for (i = 0; i < len; ++i) {
        // 打印每个元素的成员（DATATYPE包含name、sex、age、score）
        printf("%s %c %d %d\n", 
               list->head[i].name, 
               list->head[i].sex, 
               list->head[i].age, 
               list->head[i].score);
    }
    return 0;
}

4、尾插，在顺序表的最后插入元素

int InsertTailSeqList(SeqList *list, DATATYPE *data)

{
    if (IsFullSeqList(list)) {  // 检查是否已满
        fprintf(stderr, "seqlist full\n");
        return 1;
    }
    // 方式1：直接赋值 *data 到当前末尾位置
    // list->head[list->clen] = *data;
    
    // 方式2：使用memcpy复制数据（适用于结构体中有指针成员的情况，避免浅拷贝）
    memcpy(&list->head[list->clen], data, sizeof(DATATYPE));
    
    list->clen++;  // 元素个数+1
    return 0;       // 成功返回0
}

5、判断表是否满

int IsFullSeqList(SeqList *list)

{
    if (NULL == list) {
        fprintf(stderr, "IsFullSeqList parameter error\n");  // 空指针检查
        return 1;  // 返回非0表示错误或已满（此处逻辑为：错误按"满"处理，可能需优化）
    }
    return list->clen == list->tlen;  // 元素个数等于总长度时返回1（满），否则0
}

6、判断表是否空

int IsEmptySeqList(SeqList *list)

{
    // 正确写法：判断元素个数是否为0
    return 0 == list->clen;
    // return list->clen = 0;  // 会将clen置0并返回0，逻辑错误
}

7、按指定位置插入元素

int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)

{
    if (IsFullSeqList(list)) return 1;  // 判满
    int len = GetSizeSeqList(list);
    if (pos < 0 || pos > len) {         // 位置合法性检查（允许pos==len，即尾插）
        return 1;
    }
    // 从末尾开始，将[pos, len-1]的元素后移一位
    int i = 0;
    for (i = list->clen; i > pos; i--) {
        // 方式1：直接赋值
        // list->head[i] = list->head[i-1];
        
        // 方式2：使用memcpy复制结构体
        memcpy(&list->head[i], &list->head[i-1], sizeof(DATATYPE));
    }
    // 在pos位置插入新元素
    memcpy(&list->head[pos], data, sizeof(DATATYPE));
    list->clen++;  // 元素个数+1
    return 0;
}

8、查找元素，根据名字

int FindSeqList(SeqList *list, char *name)

{
    int i = 0;
    int len = GetSizeSeqList(list);
    for (i = 0; i < len; ++i) {
        if (0 == strcmp(list->head[i].name, name)) {  // 字符串比较，相等时返回下标
            return i;
        }
    }
    return -1;  // 未找到返回-1
}

9、根据名字修改指定元素

int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)

{
//参数： old 为旧名称， newdata 为新数据指针
 
        if (IsEmptySeqList(list))

        {
            return 1; // 空表返回错误码1
        }
         //先检查顺序表是否为空
 
        int ret = FindSeqList(list, old);
        if (-1 == ret)

         {
            return 1; // 未找到旧元素，返回错误码1
          }
         //查找旧名称 old 的位置，未找到则返回错误
 
        memcpy(&list->head[ret], newdata, sizeof(DATATYPE));

        // 直接替换目标位置的数据

        return 0; // 修改成功，返回0
 }

10、根据名字删除指定元素

int DeleteSeqList(SeqList *list, char *name) //参数： list 为顺序表指针， name 为待删除元素的名称

{
        if (IsEmptySeqList(list)) {
        return 1; // 空表返回错误码1
}
 //先检查顺序表是否为空，空表无法删除元素，返回错误码

        int ret = FindSeqList(list, name);
        if (-1 == ret)

         {
            return 1; // 未找到目标元素，返回错误码1
         }
 //调用 FindSeqList 查找 name 的位置，返回下标 ret 
//若 ret=-1 ，说明元素不存在，返回错误码

         int i = 0;

         int len = GetSizeSeqList(list);

        // 获取当前元素总数
        //初始化循环变量 i ，获取顺序表当前长度
 
        for (i = ret; i < len - 1; ++i)

        {
            memcpy(&list->head[i], &list->head[i + 1], sizeof(DATATYPE));
        }
        //核心逻辑：从目标位置 ret 开始，将后续元素向前移动一位（覆盖删除）
        //memcpy 用于按数据类型大小批量复制内存，实现元素前移
 
        list->clen--; // 元素总数减1
        return 0; // 删除成功，返回0

}

11、清空表，清空表中已有的元素

int ClearSeqList(SeqList *list)

{ 
     list->clen = 0; // 直接将当前长度置0，不释放内存
     return 0; 
}
 //重置顺序表长度为0，逻辑清空（物理内存未释放)

12、获得表中有效元素的个数

int GetSizeSeqList(SeqList *list)

{ 
    return list->clen;  // 直接返回当前元素个数
}

13、获得指定下标的元素本身

DATATYPE *GetItemSeqList(SeqList *list, int ind)

{
    if (NULL == list) return NULL;  // 空指针检查
    int len = GetSizeSeqList(list);
    if (ind < 0 || ind > len) {     
        return NULL;
    }
    return &list->head[ind];  // 返回指定索引处的元素地址
}

（二）顺序表优缺点

1、优点：

（1）无需为表中的逻辑关系增加额外的存储空间；

（2）可以快速随机访问元素O(1)。

2、缺点：

（1）插入，删除元素需要移动元素o(n)；

（2）无法动态存储//链表可以动态存储，来一个输一个，大小不需要事先定，内存使用

率高，顺序表大小是事先定好的。

二、链表

（一）链表基础概念

1、作用：解决顺序存储的缺点，插入和删除，动态存储问题。

2、特点：线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，

                存储单元可以是连续的，也可以不连续；

                可以被存储在任意内存未被占用的位置上。

3、注：所以前面的顺序表只需要存储数据元素信息就可以了，但在链式结构中还需要

             一个元素存储下一个元素的地址。

4、为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，

      除了存储其本身的信息外，还需要存一个指示器直接后续的信息；

        把存储数据元素信息的域叫数据域，把存储直接后继位置的域叫指针域；

        这两部分信息组成数据元素ai的存储映像，叫结点(Node)。

（二）单向链表（重点）

单向链表的链式结构：

注：表头结构可要可不要

（三）单向链表的基本操作

1、创建链表

LinkList* CreateLinkList()

{
    LinkList* ll = malloc(sizeof(LinkList));  // 分配链表头结点内存
    if (NULL == ll) {                        // 检查内存分配失败
        fprintf(stderr, "CreateLinkList malloc");  // 错误输出
        return NULL;
    }
    ll->head = NULL;          // 初始化头指针为空
    ll->clen = 0;             // 初始化链表长度为0
    return ll;                // 返回链表头指针
}

2、判断链表是否为空

int IsEmptyLinkList(LinkList* ll)

{ 
    return 0 == ll->clen;  // 直接通过长度判断空链表
}

3、获取链表长度

int GetSizeLinkList(LinkList* ll)

{
    return ll->clen;  // 直接返回链表长度
}

4、头插，在链表的前面插入一个结点

（1）图解

第一种情况（第一个放进去）

第二种情况（放在第二个）

第一步：

第二步：

（2）算法实现

int InsertHeadLinkList(LinkList* ll, DATATYPE* data)

{
    LinkNode* newnode = malloc(sizeof(LinkNode));  // 分配新结点内存
    if (NULL == newnode) {                         // 检查内存分配失败
        fprintf(stderr, "InsertHeadLinkList malloc");
        return 1;
    }
    memcpy(&newnode->data, data, sizeof(DATATYPE));  // 复制数据到新结点
    newnode->next = NULL;                            // 新结点初始next为空

    if (IsEmptyLinkList(ll)) {                       // 若链表为空
        ll->head = newnode;                          // 新结点作为头结点
    } else {                                         // 若链表非空
        newnode->next = ll->head;                    // 新结点指向原头结点
        ll->head = newnode;                          // 新结点成为头结点
    }
    ll->clen++;                                      // 链表长度+1
    return 0;                                        // 成功返回0
}

5、遍历打印链表

（1）图解

定义临时指针tmp

循环tmp = tmp->next

（2）算法实现

int ShowLinkList(LinkList* ll)

{
    int len = GetSizeLinkList(ll);       // 获取链表长度
    LinkNode* tmp = ll->head;            // 临时指针指向头结点
    int i = 0;

    for (i = 0; i < len; ++i) {          // 循环遍历每个结点
        // 打印节点数据（假设DATATYPE包含name、sex、age、score字段）
        printf("%s %c %d %d\n", 
               tmp->data.name, 
               tmp->data.sex, 
               tmp->data.age, 
               tmp->data.score);
        tmp = tmp->next;                 // 移动临时指针到下一个结点
    }
    return 0;
}

6、根据名字查找链表中的结点

DATATYPE* FindLinkList(LinkList* ll, char* name)
 {
 //参数：-  ll ：指向链表头节点的指针；
              -  name ：待查找的目标姓名（字符串）；
              - 返回值：若找到匹配节点，返回该节点的  DATATYPE  数据指针；否则     返回  NULL 。
 
        //初始化临时指针
        LinkNode* tmp = ll->head;
         //作用：创建临时指针  tmp ，指向链表的头节点，用于遍历链表。
 
        //循环遍历链表
         while (tmp) 
        {
        //条件： tmp  不为空时继续循环（即未遍历到链表末尾）。
        // 逻辑：从头部开始逐个访问节点，直到  tmp  为  NULL （遍历结束）。
 
        //字符串匹配检查
        if (0 == strcmp(tmp->data.name, name)) 
        {
            return &tmp->data;
        }
        //strcmp  函数：比较两个字符串（ tmp->data.name  和  name ）。
        //若相等，返回  0 ，进入条件分支。
        //若不等，返回非零值，跳过分支。
        //返回数据指针：若匹配成功，返回当前节点数据域的地址  &tmp->data （类型为  DATATYPE* ）。
 
        //移动临时指针
         tmp = tmp->next;
         //作用：将  tmp  指向下一个结点，继续遍历。
 
        //遍历结束，返回空指针
         return NULL;
} 

7、根据名字删除链表中的结点

（1）图解：

情况一：不是头删

定义tmp指向头结点

tmp指向待删结点的前一个

情况二头删：

（2）算法实现：

int DeleteLinkList(LinkList* ll, char* name)
{
         //参数：
         ll ：链表头指针（指向  LinkList  结构体，包含头结点                  head  和                  长度  clen ）。
         name ：待删除结点的姓名（字符串）。
         返回值：成功删除返回  0 ，失败（链表为空或未找到结点）返回                                           1 。

        //初始化临时指针

        LinkNode* tmp = ll->head;

        //作用：创建临时指针  tmp ，指向链表头结点，用于遍历和定位结点。
 
        //检查链表是否为空

        if (IsEmptyLinkList(ll))

        {

                return 1;//空链表无法删除，直接返回错误

        }

        //处理头结点匹配的情况

        if (0 == strcmp(tmp->data.name, name))

        {

                    ll->head = ll->head->next; // 头结点后移一位
                    free(tmp);                // 释放原头结点内存
                    ll->clen--;               // 链表长度减1
                    return 0;                 // 返回成功

        }

        // 条件：若头结点的  name  与目标  name  相等（ strcmp  返回  0 ）。
         //操作：将头指针  ll->head  指向原头结点的下一个结点;
                         用  free  释放原头结点的内存（避免内存泄漏）;
                         链表长度  clen  减  1 ;
                         返回  0  表示删除成功.

         //遍历查找后续结点

          while (tmp->next)

          {

        //循环条件： tmp->next  不为空（即当前结点后还有结点，未到链表末尾);
         目的：从第二个结点开始，逐个检查后续结点是否匹配目标姓名;
         检查当前结点的下一个结点是否匹配.

                if (0 == strcmp(tmp->next->data.name, name))

                {

                //当前结点的下一个结点（ tmp->next ）的 name  与目标 name  相等

                            LinkNode* tmp2 = tmp->next; // 记录待删除结点
                            tmp->next = tmp->next->next; // 跳过待删除结点，连接前后结点
                            free(tmp2);                  // 释放待删除结点内存
                            ll->clen--;                  // 链表长度减1
                            return 0;                    // 返回成功

                }

                tmp = tmp->next;//将 tmp  指向下一个结点，继续向后遍历链表

        }

        return 1;//未找到目标结点，返回删除失败

}

8、指定位置插入

（1）图解

（2）算法实现

int InsertPosLinkList(LinkList* ll, DATATYPE* data, int pos) // 定义按位置插入函数，参数为链表指针、数据指针和位置pos
{
        int len = GetSizeLinkList(ll); // 获取链表当前长度
        if(pos<0 || pos>len) // 检查插入位置是否越界（pos不能小于0或大于长度）
        {
                return 1; // 越界返回错误码1
        }
        if(0==pos) // 位置为0时（头节点位置）
        {
                return InsertHeadLinkList(ll, data); // 调用头插法插入
        }
        else if(pos == len) // 位置为链表长度时（尾部位置）
        {
                return InsertTailLinkList(ll, data); // 调用尾插法插入
        }
        else
        {
                LinkNode* newnode = malloc(sizeof(LinkNode)); // 申请新节点内存
                if (NULL == newnode) // 检查内存申请是否失败
                {
                        fprintf(stderr, "InsertPosLinkList malloc"); // 输出错误信息
                        return 1; // 返回错误码1
                }
                memcpy(&newnode->data, data, sizeof(DATATYPE)); // 复制数据到新节点数据域
                newnode->next = NULL; // 初始化新节点next指针（后续会修改）
                int i = 0 ; // 循环计数器
                LinkNode* tmp = ll->head; // 临时指针指向头节点
                for(i = 0 ;i<pos-1;++i) // 循环移动tmp到插入位置的前一个节点（pos-1次）
                {
                        tmp = tmp->next; // 移动tmp指针
                }
                newnode->next = tmp->next; // 新节点的next指向原位置节点（tmp的下一个节点）
                tmp->next = newnode; // 前一个节点的next指向新节点
                ll->clen++; // 链表长度加1
        }
        return 0; // 插入成功返回0
}

9、尾插

int InsertTailLinkList(LinkList* ll, DATATYPE* data) // 定义尾插法函数，参数为链  表指针和数据指针
{
        if (IsEmptyLinkList(ll)) // 检查链表是否为空
        {
                return InsertHeadLinkList(ll, data); // 若为空，调用头插法插入第一个节点
        }
        else
        {
                LinkNode* newnode = malloc(sizeof(LinkNode)); // 申请新节点内存
                if (NULL == newnode) // 检查内存申请是否失败
                {
                        fprintf(stderr, "InsertTailLinkList malloc"); // 向标准错误输出错误信息
                        return 1; // 返回错误码1
                }
                memcpy(&newnode->data, data, sizeof(DATATYPE)); // 复制数据到新节点的数据域
                newnode->next = NULL; // 新节点的next指针置空（作为尾节点）
                LinkNode* tmp = ll->head; // 临时指针指向头节点
                while(tmp->next) // 循环找到当前尾节点（tmp的next不为空时继续移动）
                {
                        tmp = tmp->next; // 移动tmp到下一个节点
                }
                tmp->next = newnode; // 尾节点的next指向新节点
                ll->clen++; // 链表长度加1
        }
        return 0; // 插入成功返回0
}