"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“
前言
接着前面的线性表记录，本篇主要记录一下线性表的顺序表示相关的内容。这个上周我也基本学完啦，回顾整理一下。
顺序表示
定义：
线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
逻辑上相邻，物理上也相邻
需要注意：强调的必须连续顺序存储，如果存储中中间有空缺的就不是一个线性表顺序存储结构了。
特点：
- 以物理位置相邻表示逻辑关系；（一一对应的关系）
- 任一元素均可随机存取。（优点）
线性表的顺序储存表示
地址连续、依次存取、随机存取、类型相同------可用数组来表示。
问题：线性表长度可变，数组的长度不可动态定义。
如下：
需要知道数组长度实际上也是可以动态变化的，可以实现的，但是会影响执行的效率各种，上面就默认说数组长度不可变，我们平时用其实也不去动态定义数组的长度。
定义的模板
为了解决不能直接使用数组来表示，数组不能动态分配长度的问题，下面就引入了这种定义。
我理解的是：先定义一个大小长度不可变的数组空间，然后线性表又在这个空间内进行任意分配，就是线性表的可变长度是在这个数组范围内的可变。
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
typedef int ElemType;//定义数据元素的类型为int型 （根据实际情况定义）
typedef struct{
ElemType date[LIST_INIT_SIZE];//数组存储数据元素，最大存储长度为100
int length;//当前长度
}SqList;
需要明确几点：
- 数组的长度是存放线性表的储存空间的长度大小，一般被定义后不可变。
- 线性表的长度是线性表中数据元素的个数，可随线性表的删除、插入等操作变化。
- 任意时刻，线性表的长度 <= 数组的长度
C语言补充
数组定义
- 第一种静态分配空间
typedef struct{
ElemType data[MaxSize];//定义数组
int length;
}SqList;//顺序表类型
- 第二种动态分配空间
typedef struct{
ElemType *data;//定义数组的基地址
int length;
}SqList;//顺序表类型
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType) * MaxSize);//动态分配数组空间
解释：
-
①malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址。
原型：extern void *malloc(unsigned int num_bytes);
用法：#include <alloc.h>
功能：分配长度为num_bytes字节的内存块
说明：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。
当内存不再使用时，应使用free()函数将内存块释放。 -
②sizeof(x)运算，计算变量x的长度。
-
③free(p)函数，释放指针p所指变量的存储空间，即彻底删除一个变量。
线性表的顺序存储表示
存储结构分两部分：数据元素+线性表长度
#define MAXSIZE 100
typedef struct{
ElemType *elem;
int length;
}SqList;//定义顺序表类型
SqList L;//定义变量L，L是SqList这种类型的，L是个顺序表
//就像
int a;//定义变量a，a是int型
基本操作实现
下面我给出完整的基本所有操作。
使用的编译器平台为：visual C++ 2010
使用的语言： C语言
需要注意的点：
1、需要注意形参变化是否会导致实参的变化，如果都变，一般使用指针，使他改变。
2、程序逻辑上需要考虑一些非法特殊情况。
3、测试代码的合理性
#include"stdio.h"
#include <stdlib.h> // malloc, free, rand, system
#define MAXSIZE 100
#define OK 1
#define FALSE 0
typedef int ElemType;
typedef struct
{
ElemType *elem;//表的数据
int length; //表长
}SqList;//定义顺序表类型
SqList List;//定义变量L，L是SqList这种类型的，L是个顺序表
//构造一个空的顺序表L
unsigned char InitList_Sq(SqList *L)
{
//L->elem = new ElemType[MAXSIZE];//C++中为顺序表分配空间
L->elem =(ElemType*)malloc(sizeof(ElemType) * MAXSIZE);//为顺序表分配空间
if(!L->elem)
{
return FALSE;//存储分配失败
}
L->length = 0;//空表长度为0
return OK;
}
//销毁线性表
void DestroyList(SqList *L)
{
if(!L->elem)
{
//delete L->elem;//C++中释放存储空间
free(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 FALSE;
}
*e = L.elem[i - 1];//第i-1的单元存储着第i个数据
return OK;
}
//线性表L的输入
void InputList(SqList *L, int n)
{
int i, data;
for(i = 0; i < n; i++)
{
printf("请输入第%d个数据元素：", i + 1);
scanf("%d", &data);
L->elem[i] = data;
L->length++;
}
}
//线性表L的输出
void OutputList(SqList L)
{
int i;
for(i = 0; i < L.length; i++)
{
printf("%d ", L.elem[i]);
}
printf("\n");
}
void main()
{
SqList L;//定义变量L，L是SqList这种类型的，L是个顺序表
int choice, ans, n, i;
ElemType e;
printf("线性表的顺序表示和实现3(菜单)：\n");
printf("1、线性表的初始化 2、线性表的输入\n");
printf("3、线性表的长度 4、线性表是否为空\n");
printf("5、线性表的输出 6、线性表的取值\n");
printf("7、线性表的清空 8、线性表的销毁\n");
while(1)
{
printf("请输入菜单序号：\n");
scanf("%d", &choice);
switch(choice){
case 1:
InitList_Sq(&L);
break;
case 2:
printf("请输入数据元素的个数：\n");
scanf("%d", &n);
InputList(&L, n);
break;
case 3:
ans = GetLength(L);
printf("线性表的长度是：%d\n", ans);
break;
case 4:
ans = IsEmpty(L);
if(ans)
{
printf("线性表为空\n");
}
else
{
printf("线性表不为空\n");
}
break;
case 5:
OutputList(L);
break;
case 6:
printf("请输入取值位置：\n");
scanf("%d", &i);
ans = GetElem(L, i, &e);
if(ans)
{
printf("数据元素是：%d\n", e);
}
else
{
printf("取值失败\n");
}
break;
case 7:
ClearList(&L);
printf("线性表已清空\n");
break;
case 8:
DestroyList(&L);
printf("线性表已销毁\n");
break;
}
}
}
运行如下：
参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
《大话数据结构》.程杰
欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
网友评论