专栏首页huiC语言实现线性表的顺序表示

C语言实现线性表的顺序表示

文章目录
  • 线性表的常规操作
  • 定义顺序表结构体
  • 初始化顺序表
  • 顺序表的销毁
  • 清空顺序表
  • 顺序表判空
  • 求顺序表的长度
  • 顺序表的遍历
  • 顺序表的插入​(重点)
    • 算法实现
    • 表尾插入
    • 表中插入
  • 顺序表的删除​(重点)
  • 顺序表的查找​(重点)
    • 查找指定位置的顺序表元素
    • 查找顺序表指定元素的位置(第一个匹配成功的元素位置)
  • 源代码

线性表的常规操作

SeqList InitList();		// 初始化线性表
void DestroyList();		// 销毁线性表
void ClearList();		// 清空线性表
int ListEmpty();		// 判断线性表是否为空
int ListLength();		// 求线性表的长度
void Travel();			// 遍历线性表
int ListInsert();		// 向线性表插入元素
int ListDelete();		// 从线性表删除元素
int GetElem();			// 找到线性表指定位置的元素值
int LocateElem();		// 找到线性表指定元素值的位置

定义顺序表结构体

顺序表是有插入和删除操作的,所以顺序表的长度是变化的,而 C语言中的数组是定长 的,那么该如何用数组实现顺序表呢? 我们可以定义一个变量来表示顺序表的长度,当顺序表长度变化时,只需相应地更改该变量即可。

#include "stdio.h"
#include "malloc.h"

#define MAXSIZE 100		// 顺序表的最大存储量
#define TRUE  1
#define FALSE 0

typedef int ElemType;	// 顺序表存储元素的数据类型

// 定义顺序表结构体
typedef struct SeqList{
	ElemType elems[MAXSIZE];
	int len;			// 当前顺序表的长度
}*SeqList;

*SeqList 是结构体类型指针,这里指的就是顺序表的地址。

#define MAXSIZE 100 宏定义顺序表的最大存储量,更方便改顺序表的存储大小,耦合性低。

typedef int ElemType; 自定义顺序表元素类型的,看起来 ElemTypeint 是一样的,为什么不直接用 int,要用 ElemType

Because:

定义不同的数据类型名称是为了提高程序的 高内聚,低耦合 ,而且一旦你需要将数据类型变换其他类型比如使用char类型的了,

只要写:typedef char ElemType;一下子就全改了,如果没有定义的话就要一个个的把 int 改成 char,你不嫌麻烦么。

初始化顺序表

// 初始化顺序表
SeqList InitList(){
	SeqList list = (SeqList)malloc(sizeof(struct SeqList));		// 分配顺序表内存大小
	list -> len = 0;		// 顺序表的初始长度
	return list;
}

顺序表的销毁

有初始化操作肯定就会有销毁,销毁无用的资源是一个好习惯。 如果使用静态数组实现的顺序表,我们无需手动释放资源,因为程序结束后系统会自动释放内存;而如果使用动态内存分配实现的顺序表,就需要我们手动释放内存,实现如下:

#include "stdio.h"
#include "malloc.h"

#define MAXSIZE 100			// 顺序表的最大存储量
#define TRUE  1
#define FALSE 0

typedef int ElemType;		// 顺序表存储元素的数据类型

// 定义顺序表结构体
typedef struct SeqList{
	ElemType *elems;
	int len;				// 当前顺序表的长度
}*SeqList;

// 初始化顺序表
SeqList InitList(){
	SeqList list;
    list -> elems = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);		// 分配顺序表内存大小
	list -> len = 0;		// 顺序表的初始长度
	return list;
}

// 销毁顺序表
void DestroyList(SeqList list){
	if(list -> elems != NULL){
		free(list -> elems);	//释放动态数组内存
	}
	list -> elems = NULL;
	printf("释放动态数组内存\n");
}

int main(int argc, char const *argv[])
{
	SeqList list = InitList();
	printf("list -> len:%d\n", list -> len);
	DestroyList(list);
	printf("list -> elems地址:%p\n", list -> elems);
	return 0;
}

程序运行结果

list -> len:0
释放动态数组内存
list -> elems地址:00000000

请按任意键继续. . .

清空顺序表

// 清空顺序表
void ClearList(SeqList list){
	list -> len = 0;		// 将顺序表的长度置为 0
}

顺序表判空

// 顺序表判空
int ListEmpty(SeqList list){
	if(list == NULL) return FALSE;
	return list -> len == 0;
}

只需要判断顺序表的长度是否为0, 0则空反之有元素。

求顺序表的长度

// 获取顺序表的长度
int GetLen(SeqList list){
	return list -> len;
}

顺序表的遍历

// 遍历顺序表
void Travel(SeqList list){
	for(int i=0;i<list -> len;i++){
		printf("%d\t", list -> elems[i]);
	}
	printf("\n");
}

顺序表的插入​(重点)

顺序表的插入算法思想如下:

  1. 判断插入位置 pos 是否合法
  2. 判断顺序表的存储空间是否已满,若已满,返回 FALSE
  3. pos 位置之后的所有元素向后移动一位
  4. 将新元素插入到 pos 位置
  5. 顺序表长度len加1,此时插入成功,返回 TRUE

算法实现

/*
 * 指定位置在顺序表插入元素
 * pos 逻辑下标 (1, 2, 3, ...)
 * elem 要插入顺序表的元素
*/
int ListInsert(SeqList list, int pos, ElemType elem){
	// 判断插入位置是否合理
	if(pos <= 0 || pos > list -> len + 1){
		return FALSE;
	}

	// 判断顺序表是否已满
	if(list -> len == MAXSIZE){
		return FALSE;
	}

	// 元素后移
	for(int i=list -> len;i>= pos;i--){
		// 1 [2] 3 4 5
		list -> elems[i] = list -> elems[i-1];
	}

	// 元素插入
	list -> elems[pos - 1] = elem;
	list -> len ++;	// 记得更新顺序表长度
	return TRUE;
}

注意:元素后移是从顺序表最后一个元素开始移动

表尾插入

假设顺序表容量为6,MAXSIZE = 6

顺序表的长度为4,len = 4

在顺序表第5个位置插入元素5,pos = 5elem = 5

由于len < pos		--> 	4 <  5
所以for循环条件不满足
    
直接插入elems[pos - 1] = elem;	--> 	elems[4] = 5

表中插入

假设顺序表容量为6,MAXSIZE = 6

顺序表的长度为4,len = 4

在顺序表第2个位置插入元素5,pos = 2elem = 5

从顺序表最后一个元素开始移动后

移动过程

 1、elems[4] = elems[4 - 1];  -->	elems[4] = elems[3]
 2、elems[3] = elems[3 - 1];  --> 	elems[3] = elems[2]
 3、elems[2] = elems[2 - 1];  --> 	elems[2] = elems[1]

元素插入后

elems[pos - 1] = elem;	--> 	elems[1] = 5

顺序表的删除​(重点)

顺序表的删除算法思想如下:

  1. 判断删除位置 pos 是否合法
  2. 先把要删除元素的值保存起来
  3. pos 位置之后的所有元素向前移动一位
  4. 顺序表长度len减1,此时删除成功,返回 TRUE
/*
 * 指定位置在顺序表删除元素
 * pos 逻辑下标 (1, 2, 3, ...)
 * val 用来保存删除元素的值
*/
int ListDelete(SeqList list, int pos, ElemType *val){
	// 判断删除位置是否合法
	if(pos <= 0 || pos > list -> len){
		return FALSE;
	}

	*val = list -> elems[pos - 1];	// 先保存要删除元素的值

	// 元素前移
	for(int i=pos - 1;i<list -> len;i++){
		list -> elems[i] = list -> elems[i + 1];
	}

	list -> len --;	// 记得更新顺序表长度
	return FALSE;
}

假设顺序表容量为6,MAXSIZE = 6

顺序表的长度为4,len = 5

删除顺序表第2个位置的元素,pos = 2

元素向前移动过程

1、elems[1] = elems[1 + 1];	--> elems[1] = elems[2];
2、elems[2] = elems[2 + 1];	--> elems[2] = elems[3];
3、elems[3] = elems[3 + 1];	--> elems[3] = elems[4];

顺序表的查找​(重点)

查找指定位置的顺序表元素

/*
 * 查找指定位置的顺序表元素
 * pos 逻辑下标 (1, 2, 3, ...)查找的位置
 * val 用来保存元素的值
*/
int GetElem(SeqList list, int pos, ElemType *val){
	// 判断位置是否合理
	if(pos <= 0 || pos > list -> len){
		return FALSE;
	}
	*val = list -> elems[pos - 1];
	return TRUE;
}

查找顺序表指定元素的位置(第一个匹配成功的元素位置)

/*
 * 查找顺序表指定元素的位置(第一个匹配成功的元素位置)
 * elem 要查找的元素
 * pos 逻辑下标 (1, 2, 3, ...)用来保存元素的位置
*/			
int LocateElem(SeqList list, ElemType elem, int *pos){
	for(int i=0;i<list -> len;i++){
		if(list -> elems[i] == elem){	// 判断元素是否相等
			*pos = i + 1;				// 通过指针把逻辑下标返回
			return TRUE;
		}
	}
	return FALSE; 	// 没找到返回FAlSE
}	

源代码

源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C语言实现顺序栈

    源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构

    忆想不到的晖
  • Python环境安装教程

    通常我们将Python和Java语言归为解释型语言,而对于C/C++则归为编译型语言。

    忆想不到的晖
  • C语言实现顺序队列

    顺序队列和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个 “指针” front 和 rear...

    忆想不到的晖
  • 洛谷P4344 [SHOI2015]脑洞治疗仪(ODT)

    attack
  • 找球号(一)

    在某一国度里流行着一种游戏。游戏规则为:在一堆球中,每个球上都有一个整数编号i(0<=i<=100000000),编号可重复,现在说一个随机整数k(0<=k<=...

    书童小二
  • POJ-3641:Pseudoprime numbers(快速幂)

    Fermat's theorem states that for any prime number p and for any integer a > 1, a...

    ACM算法日常
  • 树链剖分简单分析及模板(杂谈)

    这几天学习了一下树链剖分,顺便写一下我的理解、 早上看了一下别人的讲解,云里雾里,终于算是搞懂了、 树链剖分是解决在树上进行插点问线,插线问点等一系列树上的问题...

    Angel_Kitty
  • 指针*和引用&的区别使用

    首先,&不是地址运算符,而是类型标识符的一种,就像*也不是指针运算符一样。 本篇偏向于&运算符。

    看、未来
  • OpenCV3.3 深度学习模块-对象检测演示

    OpenCV3.3 深度学习模块-对象检测演示 一:概述 OpenCV3.3 DNN模块功能十分强大,可以基于已经训练好的模型数据,实现对图像的分类与图像中的对...

    OpenCV学堂
  • 求两个等长有序数组的中位数的logN算法 分治法

    http://blog.csdn.net/yangliuy/article/details/7194199

    bear_fish

扫码关注云+社区

领取腾讯云代金券