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

顺序表的基本操作（初始化，增，删，查，改等等）

article 2024/9/22 18:27:47

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
 顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。
 

  静态顺序表的定义

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define N 1000
typedef int SLdatatype;
typedef struct SedList
{
	int a[N];
	int sz;
}SL;

但静态顺序表是有缺陷的，如果N给小了不够用，N给大了浪费空间。所以不推荐用静态顺序表。

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

动态顺序表的定义

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLdatatype;
typedef struct SedList
{
	SLdatatype* a;//用指针指向动态开辟的数组
	int sz;//空间大小==有效数据个数
	int capacity;//容量
}SL;

动态顺序表的好处：当顺序表有效空间满了以后可以用capacity扩容空间继续存放有效数据。

顺序表的初始化

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLdatatype*)malloc(sizeof(SLdatatype)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->sz = 0;
	ps->capacity = 4;
}

我们在初始化的时候也可以直接把ps->a=NULL;ps->sz=0;ps->capacity=0; 但不推荐这样，最好在初始化的时候开辟一点空间，最重要的是记得用指针接受并在test.c文件&传值，要不然不能改变结构体的内容，因为不传值相当于的实参的临时拷贝，不会改变顺序表的内容。

顺序表的销毁

void SLDestroy(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->sz = 0;
}

因为在初始化的时候ps->a我们是用malloc在堆上开辟出来的，所以我们要自己free掉这个指针 ，再把指针置为NULL避免野指针的问题，也可以不置空因为free以后可能不会有人使用这个指针指向别的空间，但最好是置空一下。

 顺序表的尾插

void SLPushBack(SL* ps, SLdatatype x)
{
	ps->a[ps->sz] = x;
	ps->sz++;

}

尾插很简单只需找到尾部然后插入，再ps->sz++即可； 但如果上图插入一个数据以后sz空间就满了，再插入数据就越界了，所以我们在插入之前要检查空间，如果满了就要扩容，然后再插入空间才不会发生越界。

顺序表的检查并扩容

void SLCheckcapacity(SL* ps)
{
	if (ps->sz == ps->capacity)
	{
		SLdatatype* tmp = (SLdatatype*)realloc(ps->a, sizeof(SLdatatype)*ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

顺序表的正确尾插

void SLPushBack(SL* ps, SLdatatype x)
{
	SLCheckcapacity(ps);
	ps->a[ps->sz] = x;
	ps->sz++;

}

增加检查函数以后想插入几个就插入几个，不会发生越界问题。 

顺序表的打印

void SLprint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");

}

顺序表的打印就没啥说的，遍历一遍打印即可。

顺序表的头插

void SLPushFront(SL* ps, SLdatatype x)
{
	SLCheckcapacity(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->sz++;


}

 

头插如果我们从前往后挪会覆盖数据，所以我们要从后往前挪动数据。 

一定要记得end位置是ps->sz-1,而不是ps->sz;然后挪动即可。

顺序表的尾删

void SLPopBack(SL* ps)
{
	ps->a[ps->sz];
	ps->sz--;

}

千万不要写成ps->a[ps->sz-1]=0;然后ps->sz--;尾删的时候初始化成0没有意义，因为如果它本身的值就是0你改成0有什么意义，所以直接把空间ps->sz--即可。 但这个代码存在一定的问题，因为一直尾删ps->sz--如果一直--下去，它会出现越界，会出现ps->sz=-1的位置存放有效数据，相当于越界，当一直尾删到ps->sz==0的位置再减减ps->sz==-1，然后再进行尾插的时候就会出现越界，

ps->a[ps->sz]=x，就会变成ps->a[-1]=有效数据，就会越界所以我们要断言一下。

void SLPopBack(SL* ps)
{
	//暴力的检查
	assert(ps->sz > 0);
	//温柔的检查
	//if (ps->sz == 0)
	//{
	//	printf("链表为空，不能删除！");
	//	return;
	//}
	ps->a[ps->sz];
	ps->sz--;

}

两种方式都可以检查，但推荐使用断言，断言会直接报错并且告诉你在第几行出问题。 

顺序表的头删

void SLPopFront(SL* ps)
{
第一种方法
	assert(ps->sz > 0);
	int start = 0;
	while (start < ps->sz-1)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}
	ps->sz--;
 

第二种方法
assert(ps->sz > 0);
     int start = 1;
	while (start < ps->sz)
	{
		ps->a[start-1] = ps->a[start];
		start++;
	}
	ps->sz--;


}

头删也要断言一下防止越界。注意这里的条件是ps->sz-1,不是ps->sz,如果你start是指向第一个位置可以写成ps->sz。

顺序表的插入


void SLInsert(SL* ps, int pos, SLdatatype x)
{
   assert(0 <= pos && pos <= ps->sz);
	SLCheckcapacity(ps);
	int end = ps->sz - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->sz++;
}

只要插入数据就要检查空间大小，然后pos位置要插入就要挪动数据，从后往前挪，大于pos的位置，然后把pos的位置插入要插入的有效数据，再把空间ps->sz++即可。 还有断言pos，因为在我们插入数据的时候，可能会超过size本身的容量就插入，比如有4个空间，别人在空间以外20的位置插入了30，就会发生越界行为，所以我们要断言一下0<=pos&&pos<=ps->size即可。

 当我们把Insert函数写完以后可以复用在头插和尾插函数当中。

void SLPushBack(SL* ps, SLdatatype x)
{
	//SLCheckcapacity(ps);
	//ps->a[ps->sz] = x;
	//ps->sz++;
	SLInsert(ps, ps->sz, x);

}

void SLPushFront(SL* ps, SLdatatype x)
{
	/*SLCheckcapacity(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->sz++;*/
	SLInsert(ps, 0, x);


}

简直妙妙米奇屋！

顺序表的删除

void SLErase(SL* ps, int pos)
{
	assert(0 <= pos && pos < ps->sz);
	//assert(ps->sz > 0);
	int start = pos+1;
	while (start <ps->sz)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->sz--;


}

第二句断言可有可无，因为在第一句断言就已经判断了 pos大于0，sz就一定不为空。最重要的是pos<ps->sz，不是<=ps->sz,要不然会越界。

写完Erase函数也能复用头删和尾删。

void SLPopBack(SL* ps)
{
	//暴力的检查
	//assert(ps->sz > 0);
	温柔的检查
	if (ps->sz == 0)
	{
		printf("链表为空，不能删除！");
		return;
	}
	//ps->a[ps->sz];
	//ps->sz--;
	SLErase(ps, ps->sz - 1);

}

void SLPopFront(SL* ps)
{
	//assert(ps->sz > 0);
	/*int start = 0;
	while (start < ps->sz-1)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}
	ps->sz--;*/

	/*int start = 1;
	while (start < ps->sz)
	{
		ps->a[start-1] = ps->a[start];
		start++;
	}
	ps->sz--;*/
	SLErase(ps, 0);

}

 香死了！

顺序表的查找下标返回下标

int SLFind(SL* ps, SLdatatype x)
{
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;

}

 顺序表的修改

void SLModify(SL* ps, int pos, SLdatatype x)
{
	assert(0 <= pos && pos < ps->sz);
	ps->a[pos] = x;
}

顺序表完整代码展示

头文件

SedList.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLdatatype;
typedef struct SedList
{
	SLdatatype* a;//用指针指向动态开辟的数组
	int sz;//空间大小==有效数据个数
	int capacity;//容量
}SL;


void SLInit(SL* ps);//初始化
void SLprint(SL* ps);//打印
void SLDestroy(SL* ps);//销毁


void SLPushBack(SL* ps, SLdatatype x);//尾插
void SLPushFront(SL* ps, SLdatatype x);//头插
void SLPopBack(SL* ps);//尾删
void SLPopFront(SL* ps);//头删

void SLInsert(SL* ps, int pos, SLdatatype x);//插入
void SLErase(SL* ps, int pos);//删除

int SLFind(SL* ps, SLdatatype x);//找到下标返回下标
void SLModify(SL* ps,int pos,SLdatatype x);//修改

 SedList.c

#include"SedList.h"
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLdatatype*)malloc(sizeof(SLdatatype)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->sz = 0;
	ps->capacity = 4;
}

void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->sz = 0;


}
void SLprint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");

}
void SLCheckcapacity(SL* ps)
{
	assert(ps);
	if (ps->sz == ps->capacity)
	{
		SLdatatype* tmp = (SLdatatype*)realloc(ps->a, sizeof(SLdatatype)*ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
void SLPushBack(SL* ps, SLdatatype x)
{
	assert(ps);
	//SLCheckcapacity(ps);
	//ps->a[ps->sz] = x;
	//ps->sz++;
	SLInsert(ps, ps->sz, x);

}
void SLPushFront(SL* ps, SLdatatype x)
{
	assert(ps);
	/*SLCheckcapacity(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->sz++;*/
	SLInsert(ps, 0, x);


}
void SLPopBack(SL* ps)
{
	assert(ps);
	//暴力的检查
	//assert(ps->sz > 0);
	温柔的检查
	if (ps->sz == 0)
	{
		printf("链表为空，不能删除！");
		return;
	}
	//ps->a[ps->sz];
	//ps->sz--;
	SLErase(ps, ps->sz - 1);

}
void SLPopFront(SL* ps)
{
	assert(ps);
	/*assert(ps->sz > 0);*/
	/*int start = 0;
	while (start < ps->sz-1)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}
	ps->sz--;*/

	/*int start = 1;
	while (start < ps->sz)
	{
		ps->a[start-1] = ps->a[start];
		start++;
	}
	ps->sz--;*/
	SLErase(ps, 0);

}


void SLInsert(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	assert(0 <= pos && pos <= ps->sz);
	SLCheckcapacity(ps);
	int end = ps->sz - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->sz++;
}
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(0 <= pos && pos < ps->sz);
	assert(ps->sz > 0);
	int start = pos+1;
	while (start <ps->sz)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->sz--;


}

int SLFind(SL* ps, SLdatatype x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;

}
void SLModify(SL* ps, int pos, SLdatatype x)
{
	assert(ps);
	assert(0 <= pos && pos < ps->sz);
	ps->a[pos] = x;
}

test.c

#include"SedList.h"
void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLprint(&s);
	SLDestroy(&s);

}
void test2()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLprint(&s);
	SLDestroy(&s);

}
void test3()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPopBack(&s);
	SLprint(&s);
	SLDestroy(&s);

}
void test4()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLPopFront(&s);
	SLprint(&s);
	SLDestroy(&s);

}
void test5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLInsert(&s, 2, 30);
	SLprint(&s);


}
void test6()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	int pos = SLFind(&s, 5);
	if (pos)
	{
		SLErase(&s, pos);
	}
	SLprint(&s);

	SLDestroy(&s);

}
void test7()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	int pos = SLFind(&s, 5);
	if (pos)
	{
		SLErase(&s, pos);
	}
	SLprint(&s);
	SLDestroy(&s);

}
void test8()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	int pos = SLFind(&s, 5);
	if (pos)
	{
		SLModify(&s, pos,30);
	}
	SLprint(&s);
	SLDestroy(&s);

}
int main()
{
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	test7();
	test8();

}


http://www.kler.cn/news/17662.html

相关文章：

  • 【c语言】字符串匹配(搜索) | API仿真
  • Nginx快速入门
  • I.MX6Q-SDB开发板移植ubuntu
  • MySQL5.7和MySQL8.0的区别是什么
  • 华为OD机试 - 优选核酸检测点（Python）
  • 操作系统(2.7)--进程
  • DAY 55 mysql数据库管理
  • 计算机专业还有前途吗？从业9年的程序员告诉你优缺点
  • MySQL知识学习04（MySQL事务隔离级别详解）
  • Elasticsearch --- 数据同步、集群
  • APP渗透—MobSF安全评估、frida、r0capture抓包
  • 倒排索引(Inverted Index)
  • Unity——Mirror学习（01）
  • c#笔记-运算符
  • 网卡丢失导致集群异常
  • Linux日志文件处理
  • 程序员找工作难吗？我用亲身经历来告诉大家
  • 基于哈希表的用户管理系统
  • 操作系统——存储管理方式
  • Python机器学习入门 -- 支持向量机学习笔记
  • 基于改进的离散PSO算法的FJSP的研究（Python代码实现）
  • 优秀的B树（B-Tree）文章索引
  • C++类的静态成员详解：成员函数非静态成员函数的非法调用
  • Java 版 spring cloud 工程系统管理 +二次开发 工程项目管理系统源码
  • axios使用笔记
  • 【五一创作】网络协议与攻击模拟-01-wireshark使用-捕获过滤器
  • 【学习笔记】「JOISC 2022 Day1」错误拼写
  • git 撤销add/commit，以及更换源命令
  • Unity VFX -- （4）创建burst粒子效果
  • 图片损坏修复软件,分享好用靠谱的软件