线性表(二)

在开始这篇文章之前,我先把程序当中用到的一些头文件以及预定义给出

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //线性表初始分配空间大小
typedef int ElemType //预定义ElemType为int类型标识符 
#define ERROR -1    //预定义ERROR的值为-1 
#define OK 1        //预定义OK的值为1

l 线性表的顺序存储表示

算法描述:

线性表中的数据元素我们一般用结构体来表示

代码实现:

/**************************/ 
/*线性表的数据元素类型定义*/ 
/**************************/
typedef struct     //结构定义 
{
    ElemType *elem;//存储空间的基地址 
    int length;    //当前长度(含几个元素)
}SqList;       //线性表顺序存储结构类型名

l 构造一个空线性表

算法描述:

(1)按给定的线性表存储空间进行分配

(2)令线性表长为0

代码实现:

/**************************************************/
/*  函数功能:构造一个空的线性表                 */
/*  函数参数:指向SqList型变量的引用变量L        */
/*  函数返回值:空                               */
/*  函数名:InitList()                           */ 
/*************************************************/
void InitList(SqList &L)
{
    L.elem = (ElemType*)malloc(MAXSIZE *sizeof(ElemType));//分配存储空间  
    L.length = 0;//初始化表长为0(没有元素)
}

l 销毁线性表

算法描述:

分配内存空间用的是C语言的malloc函数,销毁线性表就是释放所分配的内存空间,所以用delete函数,但是要先判断线性表是否存在

代码实现:

/*************************************************/
/*  函数功能:销毁线性表            */
/*  函数参数:SqList的引用变量L        */
/*  函数返回值:空               */
/*  函数名:DestroyList()           */ 
/*************************************************/
void DestroyList(SqList &L)
{
    if(L.elem)     //线性表存在 
    delete[] L.elem;//释放存储空间
}

l 清空线性表

算法描述:

只需要将线性表的长度置为0即可(先判断线性表是否存在)

代码实现:

/**************************************************/
/*  函数功能:清空线性表                          */
/*  函数参数:SqList的引用变量L                   */
/*  函数返回值:空                                */
/*  函数名:ClearList()                           */ 
/**************************************************/
void ClearList(SqList &L) 
{
    if(L.elem)       //线性表存在 
    L.length = 0;//将线性表的长度置为0
}

l 判断是否为空表

算法描述:

为空表就是线性表中没有数据元素,则length等于0

代码实现:

/**************************************************/
/*  函数功能:判断是否为空表                      */
/*  函数参数:SqList的引用变量L                   */
/*  函数返回值:int                               */
/*  函数名:EmptyList()                           */ 
/**************************************************/
int EmptyList(SqList &L)
{
    if(L.length == 0)//线性表长度为0,则是空表,返回1 
        return OK;      
    else 
        return ERROR; //不是空表,则返回-1 
}

l 求线性表的长度

算法描述:

长度就是length,直接返回length的值即可

代码实现:

/**************************************************/
/*  函数功能:求线性表的长度                      */
/*  函数参数:SqList的引用变量L                   */
/*  函数返回值:int                               */
/*  函数名:LengthList()                          */ 
/**************************************************/
int LengthList(SqList &L)
{
    return L.length;//返回线性表的长度(数据元素个数)
}

l 求线性表中某位置的数据元素值

算法描述:

用户传入位置值i,首先要进行判断,i是否合法,即不能小于1或者是大于线性表的长度,然后用一个变量来保存得到的值

代码实现:

/********************************************************/
/*  函数功能:获取线性表某位置的数据元素值              */
/*  函数参数:SqList的引用变量L,位置i,实参的引用变量e   */
/*  函数返回值:int                                     */
/*  函数名:GetElem()                                   */
/********************************************************/
int GetElem(SqList &L,int i,ElemType &e)
{
    if(i < 1 || i > L.length)//判断i的值是否合理
        return ERROR;        //不合理则返回ERROR
    e = L.elem[i-1];         //第i-1的单元存储着第i个数据
        return OK; 
}

l 查找线性表中值为e的元素

算法描述:

一般方法是从第一个元素开始,与e进行匹配,如果不相等,就往后继续匹配,如果相等了就返回该值的位置,这个遍历过程,通过循环来实现

图1 查找16

图2 查找50

代码实现:

/********************************************************/
/*  函数功能:查找线性表中值为e的元素                   */
/*  函数参数:SqList的引用变量L,变量e                   */
/*  函数返回值:int                                     */
/*  函数名:LocateElem()                                */ 
/********************************************************/
int LocateElem(SqList &L,ElemType &e)
{
    for(int i = 0;i < L.length;i++)//遍历整个线性表 
        if(L.elem[i] == e)         //如果与所找的值匹配 
            return i+1;            //返回位置 
    return 0;                      //线性表遍历结束都没找到,则返回0 
}

l 在线性表的第i个元素之前插入元素e

算法描述:

(1)判断插入位置i是否合法

(2)判断顺序表的存储空间是否已满

(3)将第n至第i位的元素依次向后移动一个位置,空出第i个位置

(4)将要插入的新元素e放入第i个位置

(5)表长+1,插入成功,返回OK

图3 插入99

分析:

插入的时候,是从最后一个元素开始向后移,插在第4个节点之前,移动了6-4+1次,那么插在第n个节点之前,移动n-i+1次

代码实现:

/********************************************************/
/*  函数功能:在线性表第i个元素之前插入元素e            */
/*  函数参数:SqList的引用变量L,位置i,变量e             */
/*  函数返回值:int                                     */
/*  函数名:InsertList()                                */ 
/********************************************************/
int InsertList(SqList &L,int i,ElemType e)
{
    if(i < 1 || i > L.length+1) //i值不合法 
        return ERROR;
    if(L.length == MAXSIZE)     //当前存储空间已满 
        return ERROR;
    for(int 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;
}

l 将线性表中第i个元素删除

算法描述:

(1)判断插入位置i是否合法

(2)将第i+1至第n位的元素依次向前移动一个位置

(3)表长-1,删除成功,返回OK

图4 删除第四个元素

分析:

删除的时候,是从第i+1个开始向前移,删除第4个节点,移动6-4次,删除第i个节点,移动n-i次

代码实现:

/********************************************************/
/*  函数功能:将线性表中第i个元素删除                   */
/*  函数参数:SqList的引用变量L,位置i                   */
/*  函数返回值:int                                     */
/*  函数名:DeleteList()                                */ 
/********************************************************/
int DeleteList(SqList &L,int i)
{
	if(i < 1 || i > L.length)   //i值不合法 
		return ERROR;
	for(int j = i;j < L.length;j++)
		L.elem[j-1] = L.elem[j];//被删除元素后面的元素前移
	L.length--;                 //表长-1
	return OK; 
}

总结一下:

(1)查找、插入、删除算法的平均时间复杂度为O(n)

(2)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系,即线性表的逻辑结构与存储结构一致

(3)在访问线性表时,可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为,访问每个元素所花时间相等

(4)这种存取元素的方法被称为随机存取法

顺序表的优点:

(1)存储密度大(结点本身所占存储量/结点结构所占存储量)

(2)可以随机存取表中任一元素

顺序表的缺点:

(1)在插入、删除某一元素时,需要移动大量元素

(2)经常浪费存储空间

(3)属于静态存储形式,数据元素的个数不能自右扩充

为了克服这一缺点,下一篇文章我就会讲到另一种数据结构——链表。我的博客地址http://www.mathor.top/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java思维导图

【一分钟知识】常用集合List、Map、Set

Collection和Collections的区别 Collection是一个接口,它是Set、List等容器的父接口; Collections是个一个工具类...

3496
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

822
来自专栏开发之途

Java集合框架源码解析之LinkedHashMap

1153
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

761
来自专栏Petrichor的专栏

leetcode: 100. Same Tree

1011
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

2797
来自专栏程序员互动联盟

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

36512
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

4286
来自专栏java工会

java集合详解

22710
来自专栏JavaNew

Java集合:整体结构

2826

扫码关注云+社区