【从零开始的嵌入式生活】数据结构3——线性表及链表(1)

简介: 【从零开始的嵌入式生活】数据结构3——线性表及链表(1)

前言

最近回到了学校,导致啥也不想干呢,本来打算去实习的,offer拿到了,我还去了两天,封校了,你说这整的,继续写文章把。。。。

主要内容为:



三连即可提高学习效率0.0


🧑🏻作者简介:一个学嵌入式的年轻人

✨联系方式:2201891280(QQ)

📔源码地址:https://gitee.com/xingleigao/study_qianrushi

⏳全文大约阅读时间: 120min


文章目录

前言

线性表的链式存储结构

结点的类型描述

链表基础算法

1.建立单链表

2.尾插法插入元素

3,遍历算法

4.链表查找

5.链表插入

6.链表的删除

7.链表释放

链表应用举例

1.单链表H倒置

2.链表求两个相连结点最大值

3.有序链表的合并

写在最后

线性表的链式存储结构

将线性表L = (a0,a1,…,an-1)中各元素分布在存储器的不同存储块,成为结点。通过地址或指针建立元素之间的联系。

结点的data域存放数据元素ai,而next是一个指针,指向ai的直接后记ai所在结点。

一般使用中都会使用带头结点的链表如下图:


结点的类型描述

定义:


typedef struct node{
  data_t data;
  struct node *next;
}listnode, *linklist;


声明:


listnode A;
linklist p = &A;


一般情况是在堆上申请内存,所以更常见的写法入下:


p = (linklist)malloc(sizeof(listnode));


数据的访问:


p->data;
A.data;
A.next;

链表基础算法

1.建立单链表

依次读入表L = (a0,a1,…,an-1)中每个元素ai(假设为整型),若ai!=结束符(-1),则为ai创建一个结点,然后插入表尾,最后返回链表的头节点指针H。

示例代码


linklist list_create(){
  linklist H;
  H = (linklist)malloc(sizeof(listnode));
  if ( H == NULL){
  printf("malloc failed\n")
  return H;
  }
  H->data = 0;//一定要赋值 防止内存泄漏
  H->next = NULL;
  return NULL;  
}


2.尾插法插入元素

相关的代码


int list_tail_insert(linklist H, data_t value){
       linklist p;
       linklist q;
       if(H == NULL){
               printf("H is NULL\n");
               return -1;
       }
       //1 new node p
       if((p = malloc(sizeof(listnode))) == NULL){
               printf("malloc failed\n");
               return -1;
       }
       p->data = value;
       p->next = NULL;
       //2 find tail
       q = H;
       while(q->next)  q = q->next;
       //3 insert
       q->next = p;
       return 0;
}

3,遍历算法


int list_show(linklist H){
       linklist p;
       if ( H == NULL){
               printf("H is NULL\n");
               return -1;
       }
       p = H;
       while ( p->next != NULL){
               printf("%d ",p->next->data);
               p = p->next;
       }
       puts("");
       return 0;
}

4.链表查找


linklist list_get(linklist H, int pos){
       linklist p;
       int i;
       if (H == NULL){
               puts("H is NULL");
               return NULL;
       }
       if (pos < -1){
               puts("pos is invalid");
              return NULL;
       }
       if (pos == -1){
               return H;
       }
       p = H;
       i = -1;
       while(i < pos){
               p = p->next;
               if (p == NULL){
                       puts("pos is invalid");
                       return NULL;
               }
               i++;
       }
       return p;
}

5.链表插入


int list_insert(linklist H, data_t value, int pos){
       linklist p, q;
       if(H == NULL){
               puts("H is NULL");
               return -1;
       }
       //1 locate node pos-1
       p = list_get(H, pos - 1);
       if (p == NULL){
               return -1;
       }
       //2 new node q
       if ((q = (linklist)malloc(sizeof(listnode))) == NULL){
               puts("malloc failed");
               return -1;
       }
       q->data = value;
       //3 q->p
       q->next = p->next;
       p->next = q;
       return 0;
}


相关文章
|
4天前
【数据结构OJ题】环形链表
力扣题目——环形链表
14 3
【数据结构OJ题】环形链表
|
4天前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
12 1
【数据结构OJ题】复制带随机指针的链表
|
4天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
9 1
【数据结构OJ题】环形链表II
|
4天前
【数据结构OJ题】相交链表
力扣题目——相交链表
14 1
【数据结构OJ题】相交链表
|
4天前
|
存储 C语言
数据结构:循环链表
【7月更文挑战第21天】
15 2
|
11天前
【数据结构OJ题】链表分割
牛客题目——链表分割
12 0
【数据结构OJ题】链表分割
|
28天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
4天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
9 1
【数据结构】栈和队列
|
4天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
10 0
【数据结构OJ题】用栈实现队列
|
4天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
15 0
【数据结构OJ题】用队列实现栈