赞
踩
线性表:线性表是具有相同数据类型的n(n$>=$0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表示为
以下是几个概念
其他常用操作
Tips:
为什么要实现对数据结构的基本操作》
- 团队合作编程,你定义的数据结构要让别人能够很方便的使用(封装)
- 将常用的操作/运算封装成函数,避免重复工作,降低出错风险
顺序表:用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
#define MaxSize 10 //定义最大长度
typeof struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
上述代码中给各个数据元素分配连续的存储空间,大小位MaxSize*sizeof(ElemType)
代码实现
#include <stdio.h> #define MaxSize 10 //定义最大长度 typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 //基本操作——初始化一个顺序表 void InitList(SqList& L) { for (int i = 0; i < MaxSize; i++) L.data[i] = 0; //将所有数据元素设置位默认初始值 L.length = 0; //顺序表初始长度为0 } int main() { SqList L; //声明一个顺序表 InitList(L);//初始化顺序表 //……未完待续,后续操作 return 0; }
如果“数组”存满了怎么办?
可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的)
思考:如果刚开始就声明一个很大的内存空间呢?存在什么问题?
Key:动态申请和释放内存空间
C —— malloc、free函数
malloc函数返回一个指针,需要强制转型为你定义数据元素类型指针
eg:L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize)
表示要申请的一整片连续的内存空间
C++ —— new、delete关键字
#include <stdlib.h> #define InitSize 10 //默认的最大长度 typedef struct { int* data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度 }SeqList; void InitList(SeqList& L) { //用malloc函数申请一片连续的内存空间 L.data = (int*)malloc(InitSize * sizeof(int)); L.length = 0; L.MaxSize = InitSize; } //增加动态数组的长度 void IncreaseSize(SeqList& L, int len) { int* p = L.data; L.data = (int*)malloc((L.MaxSize + len) * sizeof(int)); for (int i = 0; i < L.length; i++) { L.data[i] = p[i]; //将数据复制到新区域 } L.MaxSize = L.MaxSize + len; //顺序表最大长度增加len free(p); //释放原来的内存空间 } int main() { SeqList L; //声明一个顺序表 InitList(L); //初始化顺序表 //……往顺序表中随便插入几个元素…… IncreaseSize(L, 5); return 0; }
顺序表的特点:
ListInsert(&L,i,e):插入操作。在表L中的第i个位置插入指定元素e。
#include <stdio.h> #define MaxSize 10 //定义最大长度 typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 //基本操作——初始化一个顺序表 void InitList(SqList& L) { for (int i = 0; i < MaxSize; i++) L.data[i] = 0; //将所有数据元素设置位默认初始值 L.length = 0; //顺序表初始长度为0 } //插入 bool ListInsert(SqList& L, int i, int e) { if (i<1 || i>L.length + 1) //判断i的范围是否有效 return false; if (L.length >= MaxSize) //当前存储空间已满,不能插入 return false; for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; //将第i个元素及之后的元素后移 } L.data[i - 1] = e; //在位置i出放入e L.length++; //长度加1 return true; } int main() { SqList L; //声明一个顺序表 InitList(L);//初始化顺序表 //……此处省略一些代码,插入几个元素 ListInsert(L, 3, 3); printf("data[2]=%d", L.data[2]); return 0; }
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
#include <stdio.h> #define MaxSize 10 //定义最大长度 typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 //基本操作——初始化一个顺序表 void InitList(SqList& L) { for (int i = 0; i < MaxSize; i++) L.data[i] = 0; //将所有数据元素设置位默认初始值 L.length = 0; //顺序表初始长度为0 } //插入 bool ListInsert(SqList& L, int i, int e) { if (i<1 || i>L.length + 1) //判断i的范围是否有效 return false; if (L.length >= MaxSize) //当前存储空间已满,不能插入 return false; for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; //将第i个元素及之后的元素后移 } L.data[i - 1] = e; //在位置i出放入e L.length++; //长度加1 return true; } //删除 bool ListDelete(SqList& L, int i, int& e) { if (i<1 || i>L.length) //判断i的范围是否有效 return false; e = L.data[i - 1]; //将被删除的元素赋值给e for (int j = i; j < L.length; j++) { L.data[j - 1] = L.data[j]; //将第i个位置后的元素前移 } L.length--; //线性表长度减1 return true; } int main() { SqList L; //声明一个顺序表 InitList(L);//初始化顺序表 //……此处省略一些代码,插入几个元素 ListInsert(L, 3, 3); int e = -1; //用变量e把删除的元素“带回来” if (ListDelete(L, 3, e)) printf("已删除第3个元素,删除元素为=%d\n", e); else printf("位序i不合法,删除失败\n"); return 0; }
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
注意:数组下标为i的元素值等于e,返回其位序i+1
#include <stdio.h> #define MaxSize 10 //定义最大长度 typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 //基本操作——初始化一个顺序表 void InitList(SqList& L) { for (int i = 0; i < MaxSize; i++) L.data[i] = 0; //将所有数据元素设置位默认初始值 L.length = 0; //顺序表初始长度为0 } //插入 bool ListInsert(SqList& L, int i, int e) { if (i<1 || i>L.length + 1) //判断i的范围是否有效 return false; if (L.length >= MaxSize) //当前存储空间已满,不能插入 return false; for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; //将第i个元素及之后的元素后移 } L.data[i - 1] = e; //在位置i出放入e L.length++; //长度加1 return true; } //删除 bool ListDelete(SqList& L, int i, int& e) { if (i<1 || i>L.length) //判断i的范围是否有效 return false; e = L.data[i - 1]; //将被删除的元素赋值给e for (int j = i; j < L.length; j++) { L.data[j - 1] = L.data[j]; //将第i个位置后的元素前移 } L.length--; //线性表长度减1 return true; } //在顺序表L中查找第一个元素值等于e的元素,并返回其位序 int LocateElem(SqList L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) return i + 1; } return 0; } int main() { SqList L; //声明一个顺序表 InitList(L);//初始化顺序表 //……此处省略一些代码,插入几个元素 ListInsert(L, 3, 3); int i = LocateElem(L, 3); printf("位序为%d", i); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。