数据结构看书笔记_线性表_顺序存储结构

#define MAXSIZE 20 //存储空间的初始分配量 typedef int ElemType; //ElemType是线性表中元素的类型 typedef struct { ElemType data[MAXSIZE]; //数据存储结构元素,最大空间为MAXSIZE int length; //线性表当前长度 }SqList;

这里可以发现顺序存储结构需要三个属性:

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

数据元素和存放它的数组下标之间存在对应关系.如下图

数据结构看书笔记_线性表_顺序存储结构

用数组存储顺序意味着要分配固定长度的数组空间,由于线性表中可以进行插入和删除操作,于是分配的数组空间是要大于等于当前线性表的长度

存储器中的每个存储单元都有自己的编号,这个编号称为地址,之间有如下关系(LOC表示获得存储位置的函数)

LOC(ai+1) = LOC(ai) + c

LOC(ai) = LOC(a1) + (i-1)*c

通过这个公式可以随意算出线性表中任意位置的地址,而且都是相同的时间,无论在线性表中存入还是取出数据,从时间复杂度来说就是O[1], 对于这种时间复杂度是O[1]的存储结构称为随机存取结构

顺序存储结构的插入与删除

对于线性表的顺序存储结构来说,如果要实现GetElem操作,只需将其第i个位置元素值返回,也就是下标是i-1的值返回就可:

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /* Status是函数的类型,其值是函数结果状态的代码 */ /* 初始条件: 顺序线性表L已存在，１<=i<=Length */ /* 操作结果: 用e返回L中第i个数据元素的值 */ Status GetElem(SqList L, int i, ELemType *e) { if(L.length == 0 || i<1 || i>L.length) return ERROR; *e = L.data[i-1]; return OK; }

插入操作

ListInsert

思路:

由于需要对线性表进行操作,所以需要进行指针操作
如果插入位置不合理,输出异常
如果线性表当前长度大于等于数组长度,输出异常,或者动态增加容量
从最后一个元素开始遍历到第i个位置,分别将他们都向后移动一个位置
将要插入的元素填入位置i中
表长+1

代码在后面

删除操作

ListDeldte

思路:

如果删除位置不合理,输出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素的位置,分别将他们都向前移动一个位置
表长+1

平均操作次数:(n-1)/2 插入和删除时间复杂度: O[n]

存,读时间复杂度:O[1]

由此可见顺序线性表比较适合元素个数不怎么变化,而更多是存取数据的应用

顺序存储结构的优点和缺点

优点:

1. 无须为表示表中之间的罗技关系而增加额外的存储空间

2. 可以快速得存取表中任一位置的元素

缺点

1. 插入和删除操作需要移动大量的数据

2. 当线性表长度变化较大时候,难以缺点存储空间的容量

代码

main.c

/* main.c */
#include <stdio.h>
#include "List.h"

int main()
{
	ElemType a,b,c;
	int g,i,d;
	SqList L = {{1,2,3,4,5,6},6};
	
	ScanList(L);
	/* 查询一个线性表单元 */
	printf("Get_number: ");
	scanf("%d", &g);
	GetELem(L, g, &a);
	printf("Get_Elem : %d\n",a);
	/* 插入一个线性表单元 */ 
	printf("Insert_number:");
	scanf("%d", &i);
	printf("Insert_data:");
	scanf("%d", &b);
	ListInsert(&L, i, b);
	ScanList(L);
	/* 删除一个线性表单元 */
	printf("Delete_number:");
	scanf("%d", &d);
	ListDelete(&L, i, &c);
	ScanList(L);
	printf("delete data: %d\n", c);
	return 0;
 }

List.c

/* List.c */
#include <stdio.h>
#include "List.h"

/* 从线性表Ｌ中取出第ｉ个元素，并用e返回 */
Status GetELem(SqList L, int i, ElemType *e)
{
	if(L.length==0 || i<1 ||i>L.length)
		return ERROR;
	*e = L.data[i-1];
	return OK;
}

/* 遍历一个线性表L */
void ScanList(SqList L) 
{
	int i;
	for(i=0; i<L.length; i++)
		printf("%d\n",L.data[i]);
}
/* 从线性表L中第i个位置之前插入数据元素e */
Status ListInsert(SqList *L, int i, ElemType e) 
{
	int k;
	if(L->length == MAXSIZE) return ERROR;
	if(i<1 || i>L->length+1) return ERROR;
	if(i<=L->length)
	{
		for(k=L->length-1; k>=i-1; k--)
			L->data[k+1] = L->data[k];
	}
	L->data[i-1] = e;
	L->length++;
	return OK; 
}
/* 从线性表L中第i个位置删除数据元素,用e返回其值 */
Status ListDelete(SqList *L, int i, ElemType *e) 
{
	int k;
	if(L->length == 0) return ERROR;
	if(i<1 || i>L->length+1) return ERROR;
	*e = L->data[i-1];
	if(i<=L->length)
	{
		for(k=i; k<=L->length; k++)
			L->data[k-1] = L->data[k];
	}
	L->length--;
	return OK; 
}

List.h

#ifndef _LIST_H_
#define _LIST_H

#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0

typedef int Status;
typedef int ElemType; 
typedef struct
{
	ElemType data[MAXSIZE];
	int length;
}SqList, *pSqList;

Status GetELem(SqList L, int i, ElemType *e);
void ScanList(SqList L);
Status ListInsert(SqList *L, int i, ElemType e);
Status ListDelete(SqList *L, int i, ElemType *e);


#endif

输出结果如下:

数据结构看书笔记_线性表_顺序存储结构

数据结构看书笔记_线性表_顺序存储结构

线性表的定义

线性表抽象数据结构定义

线性表的顺序存储结构

顺序存储结构的插入与删除

插入操作

删除操作

顺序存储结构的优点和缺点

代码

main.c

List.c

List.h