数据结构学习(1)--- 线性表的定义与基本功能实现

    科技2022-07-17  107

    数据结构学习(1)--- 线性表的定义与基本功能实现

    本篇主要讲解一下线性表的基本概念和在顺序存储结构中一些基本功能的实现,使用的代码语言是C/C++

    一、线性表

    线性表是n个数据特性相同的元素组成的有限序列,线性表中的元素个数定义为线性表的长度,长度为0时称为空表。

    二、线性表的顺序表示方式

    1.基本知识

    1.1 概念:用一组地址连续的存储单元依次存储线性表的数据元素,这种存储结构的线性表称为顺序表。

    1.2 特点:逻辑上相邻的数据元素,其物理次序也是相邻的。

    所以只要确定好了存储线性表的起始位置,线性表中任一数据元素都可以随机存取,因此线性表的顺序存储结构是一种随机存取的存储结构。

    2.顺序存储结构的两种定义方式

    2.1 静态定义(下面的功能实现均采用静态定义)

    # define maxleng 100 typedef struct{ ElemType elem[maxleng]; int length; }SqList;

    2.2 动态定义

    # define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 # define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基地址 int length; int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList;

    3.顺序存储结构常见操作

    3.1 初始化

    int Init(SqList &l) { l.length = 0; return 1; //用来验证初始化成功 }

    3.2 插入

    int Insert(SqList &l,int i,int x) { if(l.length>=maxleng) return -1; //顺序表已满,无法插入 else if(i<=0 || i>l.length+1) return -1; //插入位置错误 else { if(i==1 || i==l.length+1) //不需要移动直接赋值 { l.elem[i-1] = x; l.length++; } else { for(int j=l.length-1;j>=i-1;j--) { l.elem[j+1] = l.elem[j]; } l.elem[i] = x; l.length++; } } return 1; //用来验证插入成功 }

    3.3 查找

    int Search(SqList &l,int x) { int i = 0; while(i<l.length && l.elem[i]!=x) i++; if(i>=l.length) return -1; //该元素不在顺序表中 else i+1; }

    3.4 删除

    int Delete(SqList &l,int i) { if(i<=0 || i>l.length+1) return -1; //删除位置不正确 for(int j=i;j<l.length;j++) { l.elem[j-1] = l.elem[j]; } l.length--; return 1; 用来验证删除成功 }

    3.5 显示

    void DisPlay(SqList l) { for(int i=0;i<l.length;i++) cout<<l.elem[i]<<" "; cout<<endl; }

    三、例子

    下面给大家一个综合的例子来直观感受顺序表的这些基本操作

    #include<iostream> #include<stdio.h> using namespace std; #define maxleng 100 //定义---静态 typedef struct{ int elem[maxleng]; int length; }SqList; /* int Init(SqList &l)---------------------初始化,详见上文 int Insert(SqList &l,int i,int x)-------插入,详见上文 int Search(SqList &l,int x)-------------查找,详见上文 int Delete(SqList &l,int i)-------------删除,详见上文 void DisPlay(SqList l)------------------显示,详见上文 */ int main() { SqList l; Init(l); Insert(l,1,1); Insert(l,2,2); Insert(l,3,3); Insert(l,4,4); //first display DisPlay(l); Search(l,3); Search(l,5); Insert(l,5,5); //second display DisPlay(l); Delete(l,2); //third display DisPlay(l); return 0; }

    输出结果如下

    first display :1,2,3,4 second display : 1,2,3,4,5 third display : 1,3,4,5
    Processed: 0.012, SQL: 8