第二章线性表

文章目录

前言
一、线性表
- 1. 含义
- 2. 表示
- 3. 特点
- 4. 基本操作
二、线性表的顺序表示
- 1.顺序表的定义
- 2.顺序表的基本操作
- 3.顺序表优缺点
三、线性表的链式表示
- 1.单链式表的定义
- 1.链式表的定义
总结

前言

主要介绍线性表

一、线性表 1. 含义

由n（n>=0)个相同类型的元素组成的有序集合。

2. 表示

L=（a₁,a₂, ,a_i-1,a_i,a_i+1, , a_n)

3. 特点

表中元素是有限的；
表中元素的数组类型都相同也即每一个元素占用相同大小的空间；
表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后顺序。

4. 基本操作

初始化表；求表长；按值查找；按位查找；插入操作；删除操作；输出操作；判空操作；销毁操作。

二、线性表的顺序表示 1.顺序表的定义

A. 顺序表定义：
线性表的顺序存储称为顺序表。
B. 实现方法：
B.1 静态分配：

//伪代码，只是代码中的重要部分，不可执行
#define MaxSize 50//定义线性表长度
typedef int ElemType;//重定义int型为ElemType
typedef struct {
	ElemType data[MaxSize];//定义顺序表元素
	int length;//定义顺序表当前长度
}SqList;//定顺序表型变量SqList

B.2 动态分配：

//伪代码，只是代码中的重要部分，不可执行
#define InitSize 100//定义线性表长度
typedef int ElemType;//重定义int型为ElemType
typedef struct {
	ElemType *data;//指示动态分配数组的指针
	int MaxSize ，length;//数组的最大容量与当前长度
}SqList;//定顺序表型变量SqList
//C的初试动态分配语句：
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
//C++的初试动态分配语句：
L.data=new ElemType[InitSize];

2.顺序表的基本操作

A. 插入操作
A. 1 核心代码

//伪代码，只是代码中的重要部分，不可执行
if (i<1 || i>L.length + 1)//判断插入的位置是否合法
    return false;
if (L.length>MaxSize)//判断插入的位置是否超出存储空间
	return false;
for (int j = L.length; j >= i; j--)//移动顺序表中的元素，依次向后移动
	L.data[j] = L.data[j - 1];
L.data[i-1] = e;//数组下标从0开始，插入第一个位置，访问的下标为0
L.length++;

A. 2实战代码

#include
#include

//1.静态分配（结构体声明）
#define MaxSize 50
typedef int ElemType;//顺序表中元素的类型
typedef struct {
	ElemType data[MaxSize];//定义数组用来存储元素
	int length;//当前顺序表中元素个数
}Sqlist;

//2.表中插入元素
bool ListInsert(Sqlist& L, int i, ElemType e)
{
	//插入不合理的处理
	if (i<1 || i>L.length + 1)//判断插入的位置是否合法
		return false;
	if (L.length>MaxSize)//判断插入的位置是否超出存储空间
		return false;
	for (int j = L.length; j >= i; j--)//移动顺序表中的元素，依次向后移动
		L.data[j] = L.data[j - 1];
	L.data[i-1] = e;//数组下标从0开始，插入第一个位置，访问的下标为0
	L.length++;
	return true;
}

//3.输出表
void PrintList(Sqlist L)
{
	for (int i = 0; i < L.length; i++)
		printf("L.data[%d]=%dn",i, L.data[i]);
}

//4.主函数
int main()
{
	Sqlist L;//定义顺序表
	bool ret;//查看返回值，True或False
	//手动在顺序表中赋值
	L.data[0] = 1;
	L.data[1] = 2;
	L.data[2] = 3;
	L.length = 3;//一共三个元素
	ret = ListInsert(L, 2, 60);//往第二个位置插入60
	if (ret)
	{
		printf("插入成功n");
		PrintList(L);//输出表
	}
	else {
		printf("插入失败n");
	}
	return 0;
}

B. 删除操作
B. 1 核心代码

//伪代码，只是代码中的重要部分，不可执行
if (i<1 || i>L.length + 1)//判断插入的位置是否合法
    return false;
del=L.date[i-1];//将被删除的元素赋给del
for (int j = i; j 
B. 2 实战代码 
#include
#include


//1.1静态分配（结构体声明）
#define MaxSize 50
typedef int ElemType;//顺序表中元素的类型
typedef struct {
	ElemType data[MaxSize];//定义数组用来存储元素
	int length;//当前顺序表中元素个数
}Sqlist;


//2.输出表
void PrintList(Sqlist L)
{
	for (int i = 0; i < L.length; i++)
		printf("L.data[%d]=%dn", i, L.data[i]);
}
//4.1表中删除元素
bool ListDelete(Sqlist& L, int i, ElemType e)
{
	//插入不合理的处理
	if (i<1 || i>L.length + 1)//判断删除的位置是否合法
		return false;
	if (L.length ==0)//顺序表中没有元素，无需删除
		return false;
	e = L.data[i - 1];//获取顺序表中要删除的元素赋值给e
	for (int j =i; j< L.length; j++)
		L.data[j-1] = L.data[j];
	L.length--;
	return true;

}
int main()//
{
	//1.3顺序表赋值
	Sqlist L;//定义顺序表
	//手动在顺序表中赋值
	L.data[0] = 1;
	L.data[1] = 2;
	L.data[2] = 3;
	L.length = 3;//一共三个元素
	//4.2删除操作部分
	bool ret_delete;//查看返回值，True或False
	ElemType del=NULL;
	ret_delete = ListDelete(L, 2, del);//删除第二个位置的元素
	if (ret_delete)
	{
		printf("删除成功n");
		printf("删除元素为%dn",del);
		PrintList(L);
	}
	else {
		printf("删除失败n");
	}
	return 0;
}
 
C. 查询操作
 C. 1 核心代码 
//伪代码，只是代码中的重要部分，不可执行
for (int i = 0; i < L.length; i++)
		if (L.data[i]==e)
			return i+1;//数组从0开始，顺序表从1开始
 
B. 2 实战代码 
#include
#include
//1.1静态分配（结构体声明）
#define MaxSize 50
typedef int ElemType;//顺序表中元素的类型
typedef struct {
	ElemType data[MaxSize];//定义数组用来存储元素
	int length;//当前顺序表中元素个数
}Sqlist;


//2.输出表
void PrintList(Sqlist L)
{
	for (int i = 0; i < L.length; i++)
		printf("L.data[%d]=%dn", i, L.data[i]);
}
//5.1按值查询
int LocateElem(Sqlist& L,ElemType e)
{
	
	for (int i = 0; i < L.length; i++)
		if (L.data[i]==e)
			return i+1;//数组从0开始，顺序表从1开始
	return 0;
}
int main()//
{
	//1.3顺序表赋值
	Sqlist L;//定义顺序表
	//手动在顺序表中赋值
	L.data[0] = 1;
	L.data[1] = 2;
	L.data[2] = 3;
	L.length = 3;//一共三个元素
	//5.2 查询操作部分
	bool ret_search;//查看返回值，True或False
	ret_search = LocateElem(L,2);//删除第二个位置的元素
	if (ret_search)
	{
		printf("查询成功n");
		printf("元素位置为%dn", ret_search);//bool与int型可以相互转换
	}
	else {
		printf("查询失败n");
	}
	return 0;
}
 
F. 修改操作 
在这里插入代码片
 
3.顺序表优缺点 
A. 优点：
 可以随机存取（根据表头元素地址和元素序号）表中任意一个元素；
 存储密度高，每个节点只存储数据元素。
 B. 缺点：
 插入与删除操作需要移动大量的元素；
 线性表变化较大时，难以确定存储空间的容量；
 存储分配需要一整段连续的存储空间，不够灵活。 
三、线性表的链式表示 
1.单链式表的定义 
A. 定义：线性表的链式表存储为单链表
  
B. 核心代码 
typedef struct LNode//单链表结构点类型
{
ElemType data;//数字域
stryct LNode *next;//指针域
}LNode,*LinkList;
 
data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())
 
该处使用的url网络请求的数据。 
1.链式表的定义 
 
总结 
提示：这里对文章进行总结：
 例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

第二章 线性表

C/C++/C#相关栏目本月热门文章

第二章线性表