LV03-03-数据结构-线性表-顺序表基础

发表于 分类于 ， ， 本文字数： 2.1k 阅读时长 ≈ 8 分钟

本文主要是数据结构——顺序表基础相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。

点击查看使用工具及版本
Windows windows11
Ubuntu Ubuntu16.04的64位版本
VMware® Workstation 16 Pro 16.2.3 build-19376536
SecureCRT Version 8.7.2 (x64 build 2214) - 正式版-2020年5月14日
开发板 正点原子 i.MX6ULL Linux阿尔法开发板
uboot NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)
linux内核 linux-4.15(NXP官方提供)
STM32开发板 正点原子战舰V3(STM32F103ZET6)
点击查看本文参考资料
参考方向 参考原文
------
点击查看相关文件下载
--- ---

一、顺序表基础

1.顺序表表示

若将线性表 L 中的各元素依次存储于计算机一片连续的存储空间。
$$
L = (a_0, a_1, …, a_{i-1},a_i,a_{i+1}, …,a_{n-1})
$$
设$Loc(a_i)$为$a_i$的地址，其中$p = Loc(a_0) $，每个元素占 m 个单元，那么就有$Loc(a_i) = p + i*m$。

image-20220929142924485

【注意】顺序表存储数据时，会提前申请一整块足够大小的物理空间，后边这块物理空间的大小是无法再变化的。其实，顺序表存储数据使用的就是数组。

2.顺序表特点

（1）逻辑上相邻的元素 $a_i$, $a_{i+1}$，其存储位置也是相邻的。

（2）对数据元素 $a_i$ 的存取为随机存取或按地址存取。

（3）存储密度高。

1
存储密度 D = 数据结构中元素所占存储空间 / 整个数据结构所占空间

【缺点】对顺序表进行插入和删除等运算的时间复杂度较差。

二、顺序表框架

1.存储结构表示

在 C 语言中，可以借助数组来描述线性表的顺序存储结构，不过我们需要加一个变量来指示目前顺序存储结构的线性表中当前数据的个数，存储结构可用下图表示：

image-20220929143204819

2.结构体定义

上边我们知道，构成一个顺序表，我们需要创建一个数组来存储数据，还需要一个变量来指示当前顺序表中数据的个数，所以就需要使用结构体来表示一个顺序表啦。使用顺序表存储数据时，需要使用的结构体至少需要两个成员，一个是存储数据用的数组，一个是代表顺序表中元素个数的变量。

image-20220929143409018

【说明】顺序表英文名称为 sequence list ，这里就用 seqlist 代表顺序表啦。

1
2
3
4
5
6
7
8
9
10
11
12
typedef int data_t;

#define N 128

struct __seqlist
{
    data_t data[N];
    int last;
};

typedef struct __seqlist seqlist; 
typedef struct __seqlist * seqlistlink;

该段程序定义了一个结构体数据类型 __seqlist，并对该结构体类型和该结构体类型指针进行了重命名。

【说明】该种方式是对方式一的简化，可以省略 sqlist 。

1
2
3
4
5
6
7
8
9
typedef int data_t;

#define N 128

typedef struct __seqlist
{
    data_t data[N];
    int last;
} _seqlist, *_seqlistlink;

该段程序定义了一个结构体数据类型 __seqlist，同时对该结构体类型和该结构体类型指针进行了重命名。

当我们为创建的结构体类型进行重命名之后，我们就可以简化结构体变量的定义了。

常规写法 等价写法
struct __seqlist L; _seqlist L;
struct __seqlist * p; _seqlistlink p;

3.框架实现

接下来我们需要搭建一个顺序表的实现框架，它一共需要三个文件： seqlist.c 、 seqlist.h 和 main.c 。

3.1 main.c

该文件主要是对顺序表进行调用和测试。

1
2
3
4
5
6
7
8
#include <stdio.h>
#include "seqlist.h"

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

3.2 seqlist.c

这个文件主要是对顺序表各种操作的实现文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "seqlist.h"

/**
 * @Function   : seqlist_create
 * @brief      : 创建一个顺序表
 * @param arg  : none
 * @return     : seqlistlink 类型，返回创建的顺序表首地址
 * @Description: 
 */
_seqlistlink seqlist_create(void)
{
    return NULL;
}

/* 测试函数实现 */
void test_seqlist_create(void) 
{
	_seqlistlink L;
	L = seqlist_create();
}

3.3 seqlist.h

这个文件主要是顺序表结构体定义和相关函数的声明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

/* 头文件 */
#include <stdio.h>

typedef int data_t;

#define N 128

typedef struct __seqlist
{
    data_t data[N];
    int last;
} _seqlist, *_seqlistlink;

/* 函数声明 */

_seqlistlink seqlist_create(void);

void test_seqlist_create(void);

#endif

3.4 Makefile

这个文件主要是用于编译程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
##============================================================================#
# Copyright © hk. 2022-2025. All rights reserved.
# File name  : Makefile
# Author     : qidaink
# Date       : 2022-09-29
# Version    : 
# Description: 
# Others     : 
# Log        : 
##============================================================================#
##

TARGET          := main
#============================================================================#
## 工具设置
# 设置交叉编译器名称
CROSS_COMPILE   :=
# 设置交叉编译器
CC              := $(CROSS_COMPILE)gcc
# 编译选项
CFLAGS          += -g -Wall
#============================================================================#
## 目录路径设置
# 头文件路径设置(.h)
INCDIRS 		:= .

# 源文件路径设置(.S .C)
SRCDIRS			:= .

# 生成的中间 .o 文件的位置
OBJDIRS         := .
#============================================================================#
# 生成编译器的 -I dir_path 参数 
INCLUDE			:= $(patsubst %, -I %, $(INCDIRS))

# 获取所有的 .C 文件名称(包含路径)
CFILES			:= $(foreach dir, $(SRCDIRS), $(wildcard $(dir)/*.c))

# 获取所有的 .C 文件名称(不包含路径)
CFILENDIR		:= $(notdir  $(CFILES))

# 指定所有的 .C 生成的 .o 文件名(包含将要存放的路径)
COBJS			:= $(patsubst %, $(OBJDIRS)/%, $(CFILENDIR:.c=.o))

# 将所有要生成的 .o 文件合并到一个变量中(都包含路径)
OBJS			:= $(COBJS)

# 设置源文件路径
VPATH			:= $(SRCDIRS)

#============================================================================#			
# 生成目标文件	   
$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) $^ -o $(TARGET)

# 隐含规则推导相关中间文件
$(COBJS) : $(OBJDIRS)/%.o : %.c
	$(CC) $(CFLAGS) -c $(INCLUDE) $<  -o $@ 
	
#============================================================================#	
.PHONY: clean clean_o
# 删除所有编译链接生成的文件命令
clean: clean_o
	@rm -vf $(TARGET)

# 删除所有的 .o 文件命令
clean_o:
	@rm -vf $(COBJS)

printf:
	@echo "CFLAGS    = $(CFLAGS)"
	@echo "INCDIRS   = $(INCDIRS)"
	@echo "SRCDIRS   = $(SRCDIRS)"
	@echo "INCLUDE   = $(INCLUDE)"
	@echo "CFILES    = $(CFILES)"
	@echo "CFILENDIR = $(CFILENDIR)"
	@echo "COBJS     = $(COBJS)"
	@echo "OBJS      = $(OBJS)"
	@echo "VPATH     = $(VPATH)"

3.5编译测试

框架创建完毕后，可以在命令行输入以下命令进行测试，观察是否有报错，保证没有错误以便于后边相关操作的实现。

1
2
make          # 编译程序
./main        # 执行可执行程序

上边的程序中由于功能还没实现，所以可能会有警告。