线性表(二)

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

#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 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(89) 正则表达式 (中) / 计算机程序的思维逻辑

上节介绍了正则表达式的语法,本节介绍相关的Java API。 正则表达式相关的类位于包java.util.regex下,有两个主要的类,一个是Pattern,另...

1887
来自专栏Golang语言社区

Golang语言社区--Go语言基础第三节常量

大家好,我是彬哥;今天继续我们的基础课程的讲解,本篇给大家讲解的是关于Go语言常量的知识。那么在编程语言中何为常量?常量解释如下:

46522
来自专栏Micro_awake web

javascript(二):数据类型&数值

第一部分:数据类型 javascript数据类型通常来说是6种(ES6新增第七种Symbol类型) number:数值 string:字符串 boolean:布...

1835
来自专栏IT可乐

JAVA 用数组实现 ArrayList

  我们知道 ArrayList 是一个集合,它能存放各种不同类型的数据,而且其容量是自动增长的。那么它是怎么实现的呢?   其实 ArrayList 的底层是...

2158
来自专栏乐百川的学习频道

C++学习笔记 基本数据类型

由于考研的编程题很多都需要使用C++语言来写,所以虽然我不太喜欢C++这门语言,那么还是得来看看。 算术类型 需要提前说明,C++语言属于比较低级的语言,所以没...

1658
来自专栏趣学算法

数据结构 第3讲 顺序表

顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以插入、删除时需要移动大量元素。

893
来自专栏青枫的专栏

java基础学习_基础语法(上)03_day04总结

============================================================================= ==...

561
来自专栏noteless

JavaSE之Long 详解 Long的方法简介以及用法

java.lang.Long.valueOf(String, int)是借助于parseLong进行转换

1262
来自专栏鸿的学习笔记

线性表之顺序存储结构

线性表的数据对象集合为{a1,a2,...an},每个元素的数据类型均为DataType。

622
来自专栏武培轩的专栏

剑指Offer-左旋转字符串

package String; /** * 左旋转字符串 * 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令...

2863

扫码关注云+社区