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

注本文为博主学习408相关知识所撰写的学习笔记内容如有雷同纯属巧合。一、线性表的定义和基本操作1、线性表的定义线性表由nn0个数据特性相同的元素构成的有限序列。2、线性表的特点1.线性表是一种逻辑结构2.表中元素的个数有限3.表中数据元素类型相同4.除第一个元素外每个数据元素均只有一个前驱5.除最后一个元素外每个数据元素均只有一个后继注线性表--逻辑结构顺序表--线性表的顺序存储二、线性表的顺序表示1、顺序表的定义顺序表中逻辑上相邻的数据元素物理位置也是相邻的。注位序与数组下标相差1计算顺序表中的地址Array[i] Array[0] 1 * LL数据元素所占地址长度顺序表中任一数据元素都可随机存取2、顺序表申请数组方式①静态方式数组空间大小锁死//静态 #define MaxSize 50 //定义线性表的最大长度 typedef struct{ ElemType data[MaxSize]; //顺序表的元素 int length; //当前长度 }SqList; //顺序表的结构类型为SqList②动态方式数组空间没有规定上限动态调整//typedef struct{ ElemType *elem; //存储空间的基地址 int length; //当前长度 }SqList; //顺序表的结构类型为SqList3、顺序表的基本操作①初始化//动态 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