当前位置： 首页 > article >正文

数据结构实战之线性表（三）

article 2025/1/31 15:34:44

目录

1.顺序表释放

2.顺序表增加空间

3.合并顺序表

4.线性表之链表实现

1.项目结构以及初始代码

2.初始化链表(不带头结点)

3.链表尾部插入数据并显示

4.链表头部插入数据

5.初始化链表（带头结点）

6.带头结点的链表头部插入数据并显示

7.带头结点的链表尾部插入数据

5.提供操作界面


1.顺序表释放

main.c

SeqList.h

SeqList.c

void destroy(SeqList* list)
{

    free(list->base);
    list->base = NULL;// 防止野指针
    list->capacity = 0;
    list->size = 0;
}

2.顺序表增加空间

SeqList.h

SeqList.c


int Inc(SeqList* list)
{
        ElemType* newbase = (ElemType*)realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));
        if (newbase == NULL)
        {
            printf("增配空间失败，内存不足.\n");
            return 0;// 返回0，表示假，增配空间失败
        }
    
        list->base = newbase;
        list->capacity += INC_SIZE;
    
        return 1;
}

应该在顺序表插入的函数中判断

3.合并顺序表

注释掉原来的main函数

重新写一个main函数

main.c

int main(int argc, char** argv)
{
    SeqList mylist;
    SeqList youlist;
    SeqList list;

        InitSeqList(&mylist);
        InitSeqList(&youlist);
    
        push_back(&mylist,1);
        push_back(&mylist,3);
        push_back(&mylist,5);
        push_back(&mylist,7);
        push_back(&mylist,9);
    
        push_back(&youlist,2);
        push_back(&youlist,4);
        push_back(&youlist,6);
        push_back(&youlist,8);
        push_back(&youlist,10);
    
        merge(&list,&mylist,&youlist);
    
        show_list(&list);

}

SeqList.h

SeqList.c

/*
将两个有序的顺序表合并为一个有序的顺序表
*/
void merge(SeqList* lt, SeqList* la, SeqList* lb)
{
// 初始化三个指针，分别用于遍历la、lb、lt三个顺序表
        int ia = 0;// ia 指向顺序表 la 的当前元素
        int ib = 0;// ib 指向顺序表 lb 的当前元素
        int ic = 0;// ic 指向合并后的顺序表 lt 的当前插入位置

         // 计算合并后顺序表 lt 的容量（容量等于 la 和 lb 的元素总数）
    lt->capacity = la->size + lb->size;
         // 为顺序表 lt 分配足够的空间，能够存储合并后的所有元素
    lt->base = (ElemType*)malloc(sizeof(ElemType) * lt->capacity);
         // 检查内存分配是否成功，如果分配失败则终止程序
        assert(lt->base != NULL);// 开辟失败了，就断言返回
    
        // 合并两个顺序表，当 la 和 lb 都还有未处理的元素时，执行比较与插入操作
        while (ia < la->size && ib < lb->size)
        {
             // 如果 la 当前元素小于 lb 当前元素，取出 la 当前元素放入 lt
            if (la->base[ia] < lb->base[ib])
            {
                      // 插入元素并移动指针 ia 和 ic
                lt->base[ic++] = la->base[ia++];
            }
            else// 否则取出 lb 当前元素放入 lt
            {
                lt->base[ic++] = lb->base[ib++];// 插入元素并移动指针 ib 和 ic
            }
        }
    // 如果 la 中还有未处理的元素，直接将其复制到 lt 中
        while (ia < la->size)
        {
                 // 依次插入剩余元素并移动指针
            lt->base[ic] = la->base[ia];
            ic++;
            ia++;
        }
    // 如果 lb 中还有未处理的元素，直接将其复制到 lt 中
        while (ib < lb->size)
        {
                 // 依次插入剩余元素并移动指针
            lt->base[ic] = lb->base[ib];
            ic++;
            ib++;
        }
        // 设置合并后顺序表 lt 的大小，等于 la 和 lb 的元素总数
    lt->size = la->size + lb->size;
}

4.线性表之链表实现

1.项目结构以及初始代码

在解决方案"dataStructure"新增一个项目"List"。并把项目"List"设置为启动项目。

项目"List"初始结构

List.h

#ifndef  __LIST_H__
#define  __LIST_H__

#define ElemType int

typedef struct ListNode
{
    ElemType data;
    struct ListNode* next;
}ListNode;

typedef ListNode* List;



#endif // ! __LIST_H__

List.c

#include <stdio.h>
#include <assert.h>
#include <malloc.h>

#include "List.h"

main.c

#include <stdio.h>
#include "List.h"


int main(int argc, char** argv)
{
    

     return 0;
}

2.初始化链表(不带头结点)

List.h

List.c

main.c

#include <stdio.h>
#include "List.h"


int main(int argc, char** argv)
{
    List mylist;
    InitList(&mylist);

    return 0;
}

3.链表尾部插入数据并显示

main.c

List.h

List.c

/// <summary>
/// 在链表尾插入节点
/// </summary>
/// <param name="head"></param>
void CreateList(List* head)
{
        *head = (ListNode*)malloc(sizeof(ListNode));
        assert(*head != NULL);
        (*head)->data = 1;
        (*head)->next = NULL;

    ListNode* p = *head;
        for (int i = 2; i <= 10; i++)
        {
            ListNode* s = (ListNode*)malloc(sizeof(ListNode));
            assert(s != NULL);
            s->data = i;
            s->next = NULL;
            
            p->next = s;
            p = s;
        }
}

void ShowList(List* head)
{
    ListNode* p = *head;
        while (p != NULL)
        {
            printf("%d-->", p->data);
            p = p->next;
        }

         printf("Null.\n");
}

4.链表头部插入数据

main.c

List.h

List.c

void InsertTopList(List* head)
{
    *head = (ListNode*)malloc(sizeof(ListNode));
    assert(*head != NULL);

    (*head)->data = 1;
    (*head)->next = NULL;

    for (int i = 2; i <= 10; i++)
    {
        ListNode* s = (ListNode*)malloc(sizeof(ListNode));
        assert(s!= NULL);
        s->data = i;
        s->next = *head;

        *head = s;// head指向新的节点，也就是这个新的结点成为头结点
    }
}

5.初始化链表（带头结点）

main.c

List.h

List.c

void InitListWithHead(List* head)
{
        *head = (ListNode*)malloc(sizeof(ListNode));
        assert(*head != NULL);
        (*head)->next = NULL;
}

6.带头结点的链表头部插入数据并显示

main.c

List.h

List.c

// 在带头结点的链表头部插入数据
void CreateListTopWithHead(List* head)
{
        for (int i = 1; i <= 10; i++)
        {
            ListNode* s = (ListNode*)malloc(sizeof(ListNode));
            s->data = i;
            s->next = (*head)->next;
            (*head)->next = s;
        }
}



void ShowListWithHead(List* head)
{
    ListNode* p = (*head)->next;
        while (p != NULL)
        {
            printf("%d-->", p->data);
            p = p->next;
        }

         printf("Null.\n");
}

main.c

List.h

List.c

// 在带头结点的链表尾部插入数据
void InsertTailListWithHead(List* head)
{
    ListNode* p = *head;
        for (int i = 1; i <= 10; i++)
        {
            p = p->next = (ListNode*)malloc(sizeof(ListNode));
            assert(p != NULL);
            p->data = i;
            p->next = NULL;
        }
}

链表结构如下

8.1.项目初始结构

main.c

#include <stdio.h>
#include "SList.h"

int main(int argc, char** argv)
{
        
    
        return 0;
}

SList.h

#ifndef __SLIST_H__
#define __SLIST_H__
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define ElemType int

typedef struct Node
{
    ElemType data;
    struct Node* next;
}Node,*PNode;


typedef struct List
{
     PNode first;
     PNode last;
     size_t size;// 节点个数大小
}List;


void InitList(List* list);


#endif // !__SLIST_H__

SList.c

#include "SList.h"

void InitList(List* list)
{
    list->first = list->last = (Node*)malloc(sizeof(Node));
    assert(list->first != NULL);
    list->first->next = NULL;
    list->size = 0;
}

5.提供操作界面

main.c

#include <stdio.h>
#include "SList.h"

int main(int argc, char** argv)
{
    List mylist;
    InitList(&mylist);

    int select = 1;
    while (select)
    {
    printf("*******************************************\n");
    printf("* [1] push_back          [2] push_front   *\n");
    printf("* [3] show_list          [4] pop_back     *\n");
    printf("* [5] pop_front          [6] insert_val   *\n");
    printf("* [7] find                 [8] length       *\n");
    printf("* [9] delete_val         [10] sort        *\n");
    printf("* [11] reverse             [12] clear       *\n");
    printf("* [13] destroy             [0] quit_system  *\n");
    printf("*******************************************\n");
    
    printf("请选择:>");
    scanf("%d", &select);
    switch (select)
    {
        case 1:
        {
            break;
        }
        default:
        {
            printf("输入的命令错误，请重新输入.\n");
            break;
        }
    }
    }

     return 0;
}

8.3.单链表尾部插入元素并显示单链表

  1. 尾部插入元素

main.c

SList.h

SList.c

void push_back(List* list, ElemType x)
{
    Node* s = (Node*)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    
    list->last->next = s;
    list->last = s;
    
    list->size++;
}
  1. 显示单链表元素

void show_list(List* list)
{
    Node* p = list->first->next;
    while (p != NULL)
    {
        printf("%d--->", p->data);
        p = p->next;
    }
    printf("NULL.\n");
}

🔔 如果你对C语言数据库 和其他先进技术感兴趣，请别忘了点赞👍、收藏⭐️，并关注我们！ 我们将持续为大家带来更多精彩内容，探索嵌入式C语言的无限可能！一起站在科技的前沿，迈向更美好的未来🌟。


http://www.kler.cn/a/526085.html

相关文章：

  • INCOSE需求编写指南-附录 D: 交叉引用矩阵
  • 【Linux】线程互斥与同步
  • VLLM性能调优
  • 百度热力图数据获取，原理，处理及论文应用5
  • 白嫖DeepSeek：一分钟完成本地部署AI
  • NLP模型大对比：Transformer ＞ RNN ＞ n-gram
  • 多目标优化策略之一：非支配排序
  • 前端axios拦截器
  • 短链接项目02---依赖的添加和postman测试
  • .Net / C# 繁体中文 与 简体中文 互相转换, 支持地方特色词汇
  • 【Unity3D】实现横版2D游戏——攀爬绳索（简易版）
  • 力扣【416. 分割等和子集】详细Java题解（背包问题）
  • C++中常用的排序方法之——冒泡排序
  • 《智能家居“孤岛危机”：设备孤立如何拖垮系统优化后腿》
  • 索引02之正确建立和使用索引
  • 572. 另一棵树的子树
  • 1.文件 标准IO库
  • JxBrowser 8.2.2 版本发布啦！
  • momask-codes 部署踩坑笔记
  • 列表（列表是什么）
  • 【Qt】信号和槽简介
  • vue相关的页面和js编写
  • Fork/Join框架_任务分解与并行执行
  • 智慧园区管理平台实现智能整合提升企业运营模式与管理效率
  • 记录一次Sqoop从MySQL导入数据到Hive问题的排查经过
  • 使用Swiper构建运营推荐位