数据结构 第3讲 顺序表

数据结构 第3讲 顺序表

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

顺序表可以分配一段连续的存储空间Maxsize,用elem记录基地址,用length记录实际的元素个数,即顺序表的长度,

结构体的定义:

结构体定义后,如果要定义个顺序表L,就可以写:

SqList L;

1. 顺序表初始化

初始化是指给顺序表分配一个预定义大小的空间,用基地址elem记录这段空间的首地址,里面什么都没用,元素个数为0。前面我们已经预定义好了一个最大空间数Maxsize,那么就用new分配这么大的空间,分配成功会返回空间的首地址。假设顺序表里面需要存储整型数,那么就可以这样初始化:

boolInitList(SqList &L) //构造一个空的顺序表L
{   //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效
    //不加&内部改变,跳出函数后无效
    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间
    if(!L.elem) return false;      //存储分配失败
    L.length=0;                          //空表长度为0
    return true;
}

2. 顺序表创建

顺序表创建是向顺序表中输入数据,输入数据的类型要与类型定义中的类型一致。假设顺序表里面需要存储整型数,那么就可以这样创建:

boolCreateList(SqList &L) //创建一个顺序表L
{   //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效
    //不加&内部改变,跳出函数后无效
    int a,i=0;
   while(a!=-1)
   {
       cin>>a;
      if(L.length==Maxsize)
     {
          cout<<”顺序表已满!”
          return false;
     }
    L.elem[i++]=a;
      L.length++;
   }
    return true;
}

3. 顺序表取值

顺序表中的任何一个元素都可以立即找到,称为随机存取方式,例如我们我取第i个元素,只要i值是合理的(1≤i≤L.length),那么立即就可以找到该元素L.elem[i-1]:

bool GetElem(SqList L,int i,int &e)
{
    if (i<1||i>L.length) return false; 
      //判断i值是否合理,若不合理,返回false
    e=L.elem[i-1]; //第i-1的单元存储着第i个数据
   return true;
}

4. 顺序表查找

在顺序表中查找一个元素e,需要从第一个元素开始顺序查找,依次比较每一个元素值,如果相等,则返回元素位置(第几个元素),如果查找整个顺序表都没找到,则返回-1:

int LocateELem(SqList L,int e)
{
   for (i=0;i< L.length;i++)
       if (L.elem[i]==e) return i+1; //第几个元素,例如第5个元素,下标其实为4
  return -1;
}

时间复杂性分析:

最好情况:如果元素正好在第一个位置,一次比较成功;时间复杂度为O(1);

最坏情况:如果元素正好在最后一个位置,需要比较n次成功,时间复杂度为O(n);

平均情况:假设每个元素查找概率均等,在第一个位置需要比较1次,第二个位置需要比较2次,…,最后一个位置,需要比较n次,把n种情况加起来平均,平均时间复杂度也为O(n):

5. 顺序表插入

在顺序表中第i个位置之前插入一个元素e,需要从最后一个元素开始后移,…,直到把第i个元素也后移一位,然后把e放入第i个位置。

(1)判断插入位置i是否合法(1≤i≤L.length+1),可以在第n+1个元素之前插入。

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

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

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

(5)表长加1,插入成功返回true。

bool ListInsert_Sq(SqList &L,int i ,int e)
{
   if(i<1 || i>L.length+1) return false;     //i值不合法
   if(L.length==Maxsize) return false; //存储空间已满 
   for(j=L.length-1;j>=i-1;j--) 
      L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移,直到第i个元素后移
   L.elem[i-1]=e; //将新元素e放入第i个位置
   L.length++;             //表长增1
  return true;
}

时间复杂性分析:

假设每个位置插入的概率均等,可以在第一个位置之前插入,第二个位置之前插入,…,最后一个位置之前,第n+1个位置之前,一共有n+1种情况,每种情况移动元素的个数是n-i+1,把所有情况加起来平均,平均时间复杂度为O(n):

6. 顺序表删除

在顺序表中删除第i个元素,需要把该元素暂存到变量e,然后从i+1个元素开始前移,…,直到把第n个元素也前移一位,然后把e放入第i个位置。

(1)判断插入位置i是否合法(1≤i≤L.length)。

(2)将欲删除的元素保留在e中。

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

(4)表长减1,删除成功返回true。

bool ListDelete_Sq(SqList &L,int i, int &e)
{
   if((i<1)||(i>L.length)) return false;     //i值不合法
  e=L.elem[i-1]; //将欲删除的元素保留在e中
  for (j=i;j<=L.length-1;j++) 
   L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 
  L.length--;      //表长减1
  return true;
}

时间复杂性分析:

假设删除每个元素的概率均等,一共有n种情况,每种情况移动元素的个数是n-i,把所有情况加起来平均,平均时间复杂度为O(n):

完整代码

#include <iostream>
using namespace std;
#define  Maxsize 100  //最大空间
typedef struct{
  int *elem;
  int length;       // 顺序表的长度
}SqList;
bool InitList(SqList &L) //构造一个空的顺序表L
{   //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效
//不加&内部改变,跳出函数后无效
    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间
    if(!L.elem) return false;      //存储分配失败
    L.length=0;                          //空表长度为0
    return true;
}
bool CreateList(SqList &L) //创建一个顺序表L
{   //L加&表示引用类型参数,函数内部的改变跳出函数仍然有效
//不加&内部改变,跳出函数后无效
    int a,i=0;
    cin>>a;
    while(a!=-1)
    {
     if(L.length==Maxsize)
     {
       cout<<"顺序表已满!";
       return false;
     }
     L.elem[i++]=a;
     L.length++;
     cin>>a;
   }
   return true;
}
bool GetElem(SqList L,int i,int &e)
{
  if (i<1||i>L.length) returnfalse;
   //判断i值是否合理,若不合理,返回false
  e=L.elem[i-1];   //第i-1的单元存储着第i个数据
  return true;
}
int LocateELem(SqList L,int x)
{
  for (int i=0;i<L.length;i++)
      if (L.elem[i]==x) return i+1;//第几个元素,例如第5个元素,下标其实为4
  return -1;
}
bool ListInsert_Sq(SqList &L,int i ,int e)
{
   if(i<1 || i>L.length+1)return false; //i值不合法
   if(L.length==Maxsize) returnfalse; //存储空间已满
   for(intj=L.length-1;j>=i-1;j--)
       L.elem[j+1]=L.elem[j];   //从最后一个元素开始后移,直到第i个元素后移
   L.elem[i-1]=e;              //将新元素e放入第i个位置
   L.length++;                      //表长增1
   return true;
}
bool ListDelete_Sq(SqList &L,int i,int &e)
{
   if((i<1)||(i>L.length))return false;  //i值不合法
   e=L.elem[i-1];   //将欲删除的元素保留在e中
   for (int j=i; j<=L.length-1; j++)
              L.elem[j-1] =L.elem[j]; //被删除元素之后的元素前移
   L.length--; //表长减1
   return true;
}
void print(SqList L)
{
   cout << "输出顺序表" <<endl;
   for(int j=0;j<=L.length-1;j++)
    cout<<L.elem[j]<<"  ";
   cout<<endl;
}
void DestroyList(SqList &L)
{
  if (L.elem) delete []L.elem;    //释放存储空间
}
int main()
{
    SqList myL;
    int i,e,x;
    cout << "1. 初始化\n";
       cout << "2. 创建\n";
       cout << "3. 取值\n";
       cout << "4. 查找\n";
       cout << "5. 插入\n";
       cout << "6. 删除\n";
       cout << "7. 输出\n";
       cout << "8. 销毁\n";
       cout << "0. 退出\n";
       int choose = -1;
       while (choose != 0)
       {
        cout << "请选择:";
              cin >> choose;
              switch (choose)
              {
                  case 1://初始化顺序表
                      cout << "顺序表初始化..." <<endl;
                      if(InitList(myL))
                    cout <<"顺序表初始化成功!" << endl;
                else
                    cout <<"顺序表初始化失败!" << endl;
                      break;
                   case 2://创建顺序表
                       cout << "顺序表创建..." <<endl;
                       cout << "输入整型数,输入-1结束" <<endl;
                       if(CreateList(myL))
                    cout <<"顺序表创建成功!" << endl;
                 else
                    cout <<"顺序表创建失败!" << endl;
                 break;
            case 3://取值
                cout << "输入整型数i,取第i个元素输出" <<endl;
                cin>>i;
                if(GetElem(myL,i,e))
                    cout <<"第i个元素是: " <<e<< endl;
                 else
                    cout <<"顺序表取值失败!" << endl;;
                cout << "第i个元素是: "<<e<< endl;
                break;
            case 4://查找
                cout << "请输入要查找的数x:";
                cin>>x;
               if(LocateELem(myL,x)==-1)
                    cout <<"查找失败!" << endl;
                else
                    cout <<"查找成功!" << endl;
                break;
            case 5://插入
                cout << "请输入要插入的位置和要插入的数据元素e:";
               cin>>i>>e;
               if(ListInsert_Sq(myL,i,e))
                    cout <<"插入成功!" << endl;
                else
                    cout <<"插入失败!" << endl;
                break;
             case 6://删除
                cout << "请输入要删除的位置i:";
                cin>>i;
               if(ListDelete_Sq(myL,i,e))
                    cout <<" 删除成功!" << endl;
                else
                    cout <<"删除失败!" << endl;
                break;
            case 7://输出
                print(myL);
                break;
            case 8://销毁
                cout << "顺序表销毁..."<<endl;
                DestroyList(myL);
                break;
        }
       }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从零开始的linux

python变量

python下变量是对一个数据的引用 >>> a=123 >>> id(a) 39435920L 四则小运算 #!/usr/bin/pythonnum1 = i...

29290
来自专栏marsggbo

c++学习笔记之封装篇(上)

一、类对象 假设我们由Tv这个类,定义如下 注意class结尾要加上分号 class Tv() { int width; int hei...

18660
来自专栏Java架构师进阶

Java 常见的 30 个误区与细节!

1、在Java中,没有goto语句。因为大量使用goto语句会降低程序的可读性和可维护性,所以Java语言取消了goto的使用。同时,为了避免程序员自行使用go...

9330
来自专栏Golang语言社区

Go语言中的Array、Slice、Map和Set使用详解

Array(数组) 内部机制 在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可以是结构类型,元...

34180
来自专栏CoXie带你学编程

详解Python 2.x 与 Python 3.x 的区别

如果你是刚接触 Python 的初学者,那你可能是直接学习 Python 3.x 版本。对于 Python 2.x 的版本是不会有所接触。官方也宣布在 2020...

25120
来自专栏猿人谷

【Objective-C】05-第一个OC的类

说明:这个Objective-C专题,是学习iOS开发的前奏,也为了让有面向对象语言开发经验的程序员,能够快速上手Objective-C。如果你还没有编程经验,...

228100
来自专栏我是攻城师

Java基础类String了解一下

当你路过一些商场或者地铁口的时候,有没有被千篇一律的"xx健身,了解一下" 所烦到。

23750
来自专栏一枝花算不算浪漫

[C#基础]基础知识一: 面向对象的基本知识.

439170
来自专栏思考的代码世界

Python基础学习04天

12840
来自专栏CVer

Python Numpy学习教程(一)Python篇

通知:这篇文章主要简单介绍Python的基本数据结构、容器、列表、字典、集合、元组、函数和类等知识点 Python Numpy学习教程 Author: ...

1.1K140

扫码关注云+社区

领取腾讯云代金券