【408学习】数据结构--顺序表

注：本文为博主学习408相关知识所撰写的学习笔记内容，如有雷同，纯属巧合。

一、线性表的定义和基本操作

1、线性表的定义

线性表：由n（n>=0）个数据特性相同的元素构成的有限序列。

2、线性表的特点

1.线性表是一种逻辑结构

2.表中元素的个数有限

3.表中数据元素类型相同

4.除第一个元素外，每个数据元素均只有一个前驱

5.除最后一个元素外，每个数据元素均只有一个后继

注：线性表-->逻辑结构

顺序表-->线性表的顺序存储

二、线性表的顺序表示

1、顺序表的定义

顺序表中，逻辑上相邻的数据元素物理位置也是相邻的。

注：位序与数组下标相差1

计算顺序表中的地址

Array[i] = Array[0] + 1 * L

L：数据元素所占地址长度

顺序表中任一数据元素都可随机存取

2、顺序表申请数组方式

①静态方式

数组空间大小锁死

//静态 #define MaxSize 50 //定义线性表的最大长度 typedef struct{ ElemType data[MaxSize]; //顺序表的元素 int length; //当前长度 }SqList; //顺序表的结构类型为SqList

②动态方式

数组空间没有规定上限，动态调整

//typedef struct{ ElemType *elem; //存储空间的基地址 int length; //当前长度 }SqList; //顺序表的结构类型为SqList

3、顺序表的基本操作

①初始化

//动态 Status InitList(SqLsit &L) { L.elem = (ElemType *) malloc(sizeof(ElemType) *InitSize); //为顺序表分配一个大小为InitSize的数组空间 if(!L.elem) exit (OVERFLOW);//存储分配失败 退出 return OK; }

②取值

//动态 Status GetElem (SqList L,int i,ElemType &e) { if(i < 1 || i > L.length) return error;//判断i的值是否合理 e = L.elem[i - 1]; //elem[i - 1]单元存储第i个数据元素 return OK; }

③按值查找

//动态 int LocateElem (SqList L,ElemType e) //在顺序表L中查找值为e的元素，返回其序号 { for(i = 0; i < L.length;i++) if(L.elem[i] == e) return i + 1; //查找成功 返回序号 return 0; //查找失败 }

④插入

Status ListInsert (SqList &L,int i,ElemType e) { if(i < 1 || (i > L.length 1)) return error; //如果i值不合法 返回error if(L.length == MAXSIZE) return error; //如果存储空间满 返回error for(j = L.length - 1; j >= i - 1;j--) L.elem[j + 1] = L.elem[j]; //插入位置后元素后移 L.elem[i - 1] = e; //将元素e放入第i个位置 L.length++; //表长+1 return OK; }

⑤删除

//动态 Status ListDelete (SqList &L, int i) { if((i < 1 || i > L.length)) return error; //如果i值不合法 返回error for(j = i; j <= L.length - 1; j++) L.elem[j - 1] = L.elem[j]; //删除元素之后的元素前移 L.length--; //表长-1 return OK; }

三、结构体

结构体，好比一个自定义的组，例如将结构体组成一个果篮，果篮里面有苹果、香蕉、雪梨等，如下图所示结构体，左边为常规结构体定义，右边结构体定义方式Fru = struct Fruit，给结构体起新名字，不能再用Fruit Apple。

注：ElemType泛指所有数据类型，只会在伪代码中出现的数据类型。

//-----------顺序表的存储结构----------- typedef struct{ ElemType *elem;//存储空间的基地址 int length;//当前长度 }SqList;//顺序表的结构类型为SqList