数据结构2-线性表-顺序表

线性表

线性表包括：

顺序表
单链表
双向链表
循环链表
双向循环链表

线性表的定义和特点

定义：由n(n≥O)个数据特性相同的元素构成的有限序列称为线性表。
特点：

线性表中元素的个数n(n≥O)定义为线性表的长度，n=0时称为空表。
将非空的线性表(n>0)记作(a1，a2，a3，…，an)
这里的数据元素ai(1≤i≤n)只是个抽象的符号，其具体含义在不同情况下可以不同。
在非空的线性表，有且仅有一个开始结点a1,它没有直接前趋，而仅有一个直接后继a2;
有且仅有一个终端结点an,它没有直接后继，而仅有一个直接前趋an-1;
其余的内部结点ai,(2

基本操作

InitList(&L) 构造一个空的线性表L
DestroyList(&L) 销毁线性表L 线性表存在
ClearList(&L) 将线性表置空线性表存在
ListEmpty(&L) 判断线性表是否为空，是空返回TRUE 线性表存在
ListLength(L) 返回线性表元素个数线性表存在
GetElem(L,i,&e) 用e返回线性表L中的第i个元素线性表存在，i大于1，小于L长度
LocateElem(L,e,compare()) 返回线性表L中,第一个与e满足compare()数据元素的位序，不存在则返回0 线性表存在，compare()为数据元素判定函数
PriorElem(L,cur_e,&pre_e) 若cur是L的数据元素，且不是第一个，用pre返回他的前驱，否则操作失败，pre无意义线性表存在
NextElem(L,cur_e,&next_e) 若cur是L的数据元素，且不是第一个，用next返回他的后继，否则操作失败，next无意义线性表存在
ListInsert(&L,i,e) 在L的第i个位置之前插入e，L长度加一线性表L已存在，i大于1，小于长度加一
ListDelete(&L,i,&e) 删除线性表中第i个元素，用e返回其值，L的长度减一线性表存在，i大于1，小于长度
ListTraverse(&L,visited()) 线性表遍历线性表存在

顺序表（数组）

顺序存储结构:逻辑上相邻的数据元素存储在物理上相邻的存储单元中，占用一片连续的存储空间

线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址
计算地址只算一次与处理数据的规模无关数量级是O(1)这种运算叫随机存取。

描述顺序存储结构需要三个属性：

存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length。

特点：

任一元素均可随机存取
依次存放
随机存取
类型相同
线性表长度可变（删除） Vector ,用一变量表示顺序表的长度属性

线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址

//SqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

#define MAXSIZE 100
//typedef  int  ElemType;

typedef struct
{
	ElemType *elem;//动态分配内存
	//ElemType elem[MAXSIZE];//静态分配内存
	int length;
}SqList;

//动态创建SqList


//顺序表L的初始化
Status InitList_Sq(SqList &L);

//销毁顺序表L
void DestroyList(SqList &L);

//清空线性表L
void ClearList(SqList &L);

//求线性表L的长度
int GetLength(SqList L);

//判断线性表L是否为空
int IsEmpty(SqList L);

//顺序表的取值（根据位置i获取相应位置数据元素的内容
int GetElem(SqList L, int i, ElemType &e);

//顺序表的查找
int LocateELem(SqList L, ElemType e);

//在线性表L中第i个位置插入新元素e
Status Listlnsert_Sq(SqList &L, int i, ElemType e);

//删除线性表L中第个位置元素，用e返回
Status ListDelete_Sq(SqList &L, int i, ElemType e);

//输出顺序表
Status ListShow_Sq(SqList L);

//Sqlist.cpp
#include "SqList.h"

//顺序表L的初始化
Status InitList_Sq(SqList &L)
{
	//构造一个空的顺序表
	L.elem = new ElemType[MAXSIZE];//为顺序表分配空间
	if (!L.elem)
		exit(OVERFLOW);
	//存储分配失败
	L.length = 0;
	//空表长度为0
	return OK;
}

//销毁顺序表L
void DestroyList(SqList &L)
{
	if (L.elem)
		delete L.elem;//释放存储空间
}

//清空线性表L
void ClearList(SqList &L)
{
	L.length = 0;
	//将线性表的长度置为0
}

//求线性表L的长度
int GetLength(SqList L)
{
	return(L.length);
}

//判断线性表L是否为空
int IsEmpty(SqList L)
{
	if (L.length == 0)
		return 1;
	else
		return 0;
}

//顺序表的取值（根据位置i获取相应位置数据元素的内容
int GetElem(SqList L, int i, ElemType &e)
{
	if (i<1 || i>L.length)//判断i值是否合理，若不合理，返回ERROR
		return ERROR;
	e = L.elem[i - 1];//第i-1的单元存储着第1个数据
	return OK;
}

//顺序表的查找

int LocateELem(SqList L, ElemType e)
{
	//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e)
			return i + 1;//查找成功，返回序号
	}
	return FALSE;//查找失败，返回0
}

//在线性表L中第i个位置插入新元素e

Status Listlnsert_Sq(SqList &L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1 ) 
		return ERROR;
	if (L.length == MAXSIZE)
		return ERROR;
	for (int j = L.length - 1; j >= i-1 ; --j)
	{
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i-1] = e;
	L.length++;
	return OK;
}

//删除线性表L中第个位置元素，用e返回

Status ListDelete_Sq(SqList &L, int i, ElemType e)
{
	if (i < 1 || i > L.length)
		return ERROR;
	e = L.elem[i - 1];
	for (int j = i; j <= L.length - 1; ++j)
	{
		L.elem[j - 1] = L.elem[j];
	}
	L.length--;
	return OK;
}

Status ListShow_Sq(SqList L)
{
	if (L.length > 0)
	{
		for (int i = 0; i < L.length ; i++)
		{
			printf("%c  ", L.elem[i]);
		}
		printf("n");
		return OK;
	}
	else
	{
		return ERROR;
	}
	
}
	
void test01()  
{ 
	//初始化顺序表
	SqList L;
	ElemType elem;
	Status isinit = InitList_Sq(L);
	if (isinit)
	{
		Listlnsert_Sq(L,1,'a');
		Listlnsert_Sq(L, 2, 'b');
		Listlnsert_Sq(L, 3, 'c');
		Listlnsert_Sq(L, 4, 'd');
		Listlnsert_Sq(L, 5, 'e');
	}
	
	ListShow_Sq(L);
	printf("顺序表的长度为%dn", GetLength(L));
	if (!IsEmpty(L))
	{
		int i = 5;
		if (GetElem(L, i, elem))
		{
			printf("L[%d]值为%cn", i,elem);
		}
	}

	ListDelete_Sq(L, 1, elem);
	printf("删除1后L 为");
	ListShow_Sq(L);

	printf("在1插入a L为");
	Listlnsert_Sq(L, 1, 'a');
	ListShow_Sq(L);

	ListDelete_Sq(L, 2, elem);
	printf("删除2后L 为");
	ListShow_Sq(L);

	ListDelete_Sq(L, 3, elem);
	printf("删除3后L 为");
	ListShow_Sq(L);

	printf("在2插入V L为");
	Listlnsert_Sq(L, 2, 'V');
	ListShow_Sq(L);

		
	int n = LocateELem(L, 'c');
	printf("c的位置是%dn", n);



	printf("清空Ln");
	ClearList(L);
	ListShow_Sq(L);

	DestroyList(L);

}

int main()
{
	test01();//测试代码
	system("pause");
	return EXIT_SUCCESS;
	
}

单链表算法的时间复杂度分析

查找

查找算法的基本操作:将记录的关键字同给定值进行比较(L.elem==e)

在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。

查找第一个元素仅需比较一次；而查找表中最后一个记录时，则需比较n次。一般情况下C,等于
假设每个元素的查找概率相等，即P1=1/n

顺序表按值查找算法的平均时间复杂度为O(n)。

2.插入
插入的基本操作是移动元素。

插入位置在最后在线性表的最后添加一个元素不需要移动直接添加
插入位置在最前在原线性表的第1个元素之前插入一个新的元素，线性表的所有元素都要移动移动次数最多
则插入一个元素时移动元素的平均值为：表长的一半

顺序表插入算法的平均时间复杂度为O(n)。

3.删除

删除的基本操作是移动元素。

删除位置为最后一个元素时元素不需要移动

删除位置为第一个元素时，线性表的所有元素都要移动移动次数最多为 n-1

删除一个元素时英东元素的平均值为

顺序表删除元素的时间复杂度为O(n)

顺序表小结：

查找、插入、删除的平均算法复杂度为O(n)

空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)

顺序表的优缺点：

优点
- 存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系，而增加额外的存储空间
- 可以随机存取表中任意位置的元素
缺点
- 插入、删除某一元素需移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量，数据元素的个数不能自由扩充(存储空间不灵活)

数据结构2-线性表-顺序表

Java相关栏目本月热门文章