2-1 线性表之顺序表 及其C语言实现

2-1 线性表之顺序表

0、数据结构大致包含以下几种存储结构:

线性表:还可细分为顺序表、链表、栈和队列;

树结构:包括普通树,二叉树,线索二叉树等;

图存储结构

1、线性表

线性表,全名为线性存储结构。 是由n个相同类型的元素 所构成的 有限线性序列。

线性表主要的基本操作有以下几种:

①Initiate(L):初始化,设定一个空的线性表。

②Length(L):对给定的线性表,函数返回值为其数据元素的个数。

③Get(L,i):按给定的索引号,取出元素

④Locate(L,x):定位,对给定值x,若线性表中存在某个元素等于x,返回其索引号i;若存在多个元素等于x,返回最小的索引 i;若不存在,返回False

⑤Insert(L, i, x):插入,对给定的线性表,在第i个位置插入新元素x,(i要在长度范围内)

⑥Delete(L,i):删除,对给定的线性表,按照索引号i 删除对应元素,(i 要在长度范围内)

这几项是线性表应当满足的基本的操作。

线性表存储数据可细分为以下 2 种:

① 将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表)

数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表)

也就是说,线性表存储结构可细分为 顺序存储结构 和 链式存储结构。

逻辑上是顺序的,而真实的物理空间 一个是连续, 一个是分散。

1.1 顺序表

顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙。

使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,

顺序表还需要实时记录以下 2 项数据:

● 顺序表申请的存储容量

● 顺序表的长度,也就是表中存储数据元素的个数

# 正常状态下,顺序表申请的存储容量要大于顺序表的长度。

顺序表可以有两种实现方式:

静态顺序表 :一般使用数组来实现,

动态顺序表:一般使用动态申请的内存来实现,比如C语言中是malloc,C++中用new

①静态顺序表的程序实现:

头文件 sq_list_01.h

#ifndef SQ_LIST_01_H_
#define SQ_LIST_01_H_

#define MAX 10
typedef struct Sq_List_Static{
	int data[MAX];//创建一个数组来充当顺序表
	int length;//记录元素个数
}sq_list_;

//线性表主要的基本操作
void Init(sq_list_ *l);//初始化
int Len(sq_list_ *l);//求长度
int Get(sq_list_ *l, int i);//按索引返回元素
int Locate(sq_list_ *l, int x);//查找元素索引
void Insert(sq_list_ *l, int i, int x);//指定索引处插入元素
void Delete(sq_list_ *l, int i);//删除指定索引的元素

#endif // !SQ_LIST_01_H_

函数定义文件 sq_list_01.cpp

#include<iostream>
#include"sq_list_01.h"

/*初始化*/
void Init(sq_list_ *l) {
	l->length = 0;
}

/*返回长度*/
int Len(sq_list_ *l) {
	return l->length;
}

/*返回指定索引元素*/
int Get(sq_list_ *l, int i) {
	if (i >= 0 && i < l->length) {//索引应该大于0且小于表长
		return l->data[i];
	}
	else
		return NAN;
}

/*返回元素索引*/
int Locate(sq_list_ *l, int x) {
	//可以选用其他更好的查找方法,这里为了简便只用遍历方法
	for (int i = 0; i < l->length; i++)
		return x == l->data[i] ? i : -1;//三目运算符
	//如果x等于某个元素就返回其索引,如果没有这样的元素就返回-1,表示没有
}

/*按索引插入元素x*/
void Insert(sq_list_ *l,int i, int x) {
	//先判满,看顺序表是否还有空间能装得下新元素
	if (l->length >= MAX) {
		std::cout << "\nthe list is full!\n";
		return;
	}
	//然后判断选择插入的索引位置是否合理
	//已有元素的索引为0---length-1,所以插入元素的范围只能是 0---length,
	if (i<0 || i>l->length) {
		std::cout << "\ninvalid index: "<<i<<"! the index should be 0 - "<< l->length<<" \n";
	}
	//把i位置及其之后的元素都后移一位
	int j;
	for (j = l->length - 1; j > i; j--)
		l->data[j + 1] = l->data[j];
	l->data[i] = x;//在i位置赋值x
	l->length++;//更新表长
}

/*删除指定索引元素*/
void Delete(sq_list_ *l, int i) {
	//判空
	if (l->length<=0) {
		std::cout << "\the list is empty!\n";
		return;
	}
	if (i<0 || i>l->length - 1) {
		std::cout << "\ninvalid index: "<<i<<"! the index should be 0 - " << l->length-1 << " \n";
		return;
	}
	for (int j = i; j < l->length - 1; j++)
		l->data[j] = l->data[j + 1];

	l->length--;
}

主程序文件 use_01.cpp

#include<iostream>
#include"sq_list_01.h"

using std::cin;
using std::cout;
using std::endl;

int main() {

	sq_list_ list_0;

	Init(&list_0);
	cout << "\nthe length of list: " << Len(&list_0) << endl;
	
	/*这里故意将插入元素的次数设置为多于MAX,看是否能顺利运行*/
	for (int i = 0; i < MAX + 1; i++) {
		Insert(&list_0, i, i*i);
		for (int j = 0; j < list_0.length; j++) {
			cout << Get(&list_0, j) << "   ";
		}
		cout << endl;
	}
	cout << "\nthe length of list: " << Len(&list_0) << endl;

	

	for (int k = list_0.length; k >=0; k--) {
		Delete(&list_0, k);
		for (int j = 0; j < list_0.length; j++) {
			cout << Get(&list_0, j) << "   ";
		}
		cout << endl;
	}

	cin.get();
	return 0;
}

②动态顺序表的实现

头文件sq_list_02.h

#ifndef SQ_LIST_02_H_
#define SQ_LIST_02_H_

#define MAX 10

typedef struct Sq_List_Dynamic {

	int * head;//动态内存块的地址
	int length;//顺序表的元素个数
	int ListSize = MAX;//顺序表的容量

}list;

void Init(list *l);
int Len(list *l);
int Get(list *l, int i);
int Locate(list *l, int x);

void Insert(list *l, int i, int x);
void Delete(list *l, int i);

void Destroy(list *l);
#endif

函数定义文件: sq_list_02.cpp

#include<iostream>
#include"sq_list_02.h"

using std::cin;
using std::cout;
using std::endl;


void Init(list *l) {
	l->head = (int*)malloc( l->ListSize * sizeof(int) );//动态开辟内存,并返回地址给head
	l->length = 0;
}

int Len(list *l) {
	return l->length;
}

int Get(list *l, int i) {
	//作为顺序表依然从0开始计数,所以合理范围是 0 --- length-1
	if (i >= 0 && i < l->length)
		return l->head[i];
	else
		return NAN;
}

int Locate(list *l, int x) {

	for (int i = 0; i < l->length; i++)
		return x == l->head[i] ? i : -1;//三木运算符
	//如果x等于某个数就返回索引i,否则返回-1表示没有这个数
}

void Insert(list *l, int i, int x) {
	//判断插入位置是否合理
	if (i<0 || i>l->length) {
		cout << "\ninvalid index: " << i << " ! the valid index should be in range of 0---" << l->length - 1 << endl;
		return;
	}

	//判断顺序是否已经满了,这里和静态顺序表有个区别
	if (l->length >= l->ListSize) {
		//在动态顺序表已满的时候,可以再用realloc函数给它紧接着原来的内存又开辟新的内存!
		//我下面这行代码就又多开辟了一个内存,允许在表满的情况下,继续在尾部多插入一个元素
		l->head = (int *)realloc( l->head,(l->ListSize + 1) * sizeof (int));
		l->ListSize++;//别忘了把顺序表的总容量的数值也增1,
	}

	//接下来的操作和静态顺序表一样,将i位置及其之后的元素右移,然后将新元素赋值给i位置
	for (int j = l->length - 1; j >= i; j--)
		l->head[j + 1] = l->head[j];

	l->head[i] = x;
	l->length++;
}
void Delete(list *l, int i) {
	if (i<0 || i>l->length - 1) {
		cout << "\invalid index: " << i << " ! the valid index should be in range of 0---" << l->length - 1 << endl;
		return;
	}

	for (int j = i; j < l->length - 1; j++) {
		l->head[j] = l->head[j + 1];
		l->length--;
	}
}

/*对于开辟的动态内存,要记得手动释放,否则造成内存泄漏*/
void Destroy(list *l) {
	free(l->head);
}

主函数文件 use.cpp

#include<iostream>
#include"sq_list_02.h"

using std::cin;
using std::cout;
using std::endl;

int main() {

	list L;
	Init(&L);
	cout << "\nThe length of the list is " << Len(&L) << endl;

	for (int i = 0; i < MAX + 2; i++) {
		Insert(&L, i, i * 10);
		for (int j = 0; j < L.length; j++) {
			cout << Get(&L, j) << "  ";
		}
		cout << endl;
	}

	for (int i = L.length; i >=0; i--) {
		Delete(&L, i);

		for (int j = 0; j < L.length; j++) {
			cout << Get(&L, j) << "  ";
		}
		cout << endl;
	}


	cin.get();
    //对于动态开辟的内存,一定要记得手动给释放掉!!!
	Destroy(&L);
	return 0;
}

如有错误 还望不吝指出,谢谢。

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券