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

目录

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 当前元素放入 ltif (la->base[ia] < lb->base[ib]){// 插入元素并移动指针 ia 和 iclt->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 inttypedef 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 inttypedef 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语言的无限可能！一起站在科技的前沿，迈向更美好的未来🌟。