欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构顺序表思想以及完整代码实现

程序员文章站 2022-03-15 12:16:35
本文转载自趣学算法,方便个人学习参考使用 http://blog.csdn.net/rainchxy/article/details/77946835 数据结构 第3讲 顺序表 顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以 ......

本文转载自趣学算法,方便个人学习参考使用 http://blog.csdn.net/rainchxy/article/details/77946835

数据结构 第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个位置。

(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):

数据结构顺序表思想以及完整代码实现

 

完整代码

  1 #include <iostream>
  2 using namespace std;
  3 #define Maxsize 100//最大空间
  4 typedef struct{
  5     int *elem;
  6     int length;//顺序表长度 
  7 }SqList;
  8 
  9 bool InitList(SqList &L) //构造一个空的顺序表L
 10 {//L加&表示引用类型参数,函数内部的改变跳出函数依然有效
 11 //不加&表示内部改变,跳出函数后无效
 12     L.elem=new int[Maxsize];//为顺序表分配Maxsize 个空间
 13     if(!L.elem) return false;//存储分配失败
 14     L.length=0;
 15     return true; 
 16  } 
 17  
 18  bool CreateList(SqList &L)//创建一个顺序表L
 19  {
 20      int a,i=0;
 21      cin>>a;
 22      while(a!=-1){
 23          if(L.length==Maxsize){
 24              cout<<"顺序表已满! ";
 25              return false;
 26          }
 27          L.elem[i++]=a;
 28          L.length++;
 29          cin>>a;
 30      }
 31      return true;
 32   } 
 33   
 34   bool GetElem(SqList L,int i,int &e){
 35       if(i<1||i>L.length) return false;
 36       //判断i值是否合理,若不合理,返回false
 37       e=L.elem[i-1];//第i-1的单元存储着第i个数据
 38       return true; 
 39   }
 40   
 41   int LocateElem(SqList L,int x){
 42       for(int i=0;i<L.length;i++)
 43           if(L.elem[i]==x) return i+1;//第几个元素,例如第五个元素,下标其实为4
 44           return -1;
 45     }
 46     
 47 bool ListInsert_Sq(SqList &L,int i,int e)
 48 {
 49     if(i<1||i>L.length+1) return false;//i值不合法
 50     if(L.length == Maxsize) return false;//存储空间已满
 51     for(int j=L.length-1;j>=i-1;j--)
 52         L.elem[j+1]=L.elem[j];//从最后一个元素开始后移,直到第i个元素后移
 53     L.elem[i-1]=e;//将新元素e放入第i个位置
 54     L.length++;//表长加1
 55     return true;         
 56 }    
 57 
 58 bool ListDelete_Sq(SqList &L,int i,int &e)
 59 {
 60     if((i<1)||(i>L.length)) return false;//i值不合法
 61     e=L.elem[i-1];//将欲删除的元素保留在e中
 62     for(int j=i;j<=L.length-1;j++)
 63         L.elem[j-1]=L.elem[j];//被删除元素之后的元素后移 
 64     L.length--;//表长减少1
 65     return true; 
 66 }
 67 
 68 void print(SqList L)
 69 {
 70     cout<<"输出顺序表"<<endl;
 71     for(int j=0;j<=L.length-1;j++)
 72         cout<<L.elem[j]<<" ";
 73         cout<<endl;
 74 }
 75 
 76 void DestroyList(SqList &L){
 77     if(L.elem) delete []L.elem;//释放存储空间 
 78 }
 79 
 80 int main()
 81 {
 82     SqList myL;
 83     int i,e,x;
 84     cout<<"1.初始化\n";
 85     cout<<"2.创建\n";
 86     cout<<"3.取值\n";
 87     cout<<"4.查找\n";
 88     cout<<"5.插入\n";
 89     cout<<"6.删除\n";
 90     cout<<"7.输出\n";
 91     cout<<"8.销毁\n";
 92     cout<<"0.退出\n";
 93     
 94     int choose = -1;
 95     while(choose != 0){
 96         cout<<"请选择:";
 97         cin>>choose;
 98         switch(choose){
 99             case 1://初始化顺序表
100             cout<<"顺序表初始化·····"<<endl;
101             if(InitList(myL))
102             cout<<"顺序表初始化成功!"<<endl;
103             else
104                 cout<<"顺序表初始化失败!"<<endl;
105                 break;
106             case 2://创建顺序表
107             cout<<"顺序表创建····"<<endl;
108             cout<<"输入整型数,输入-1结束"<<endl;
109             if(CreateList(myL))
110                 cout<<"顺序表创建成功!"<<endl;
111             else
112                 cout<<"顺序表创建失败!"<<endl;
113                 break;
114             case 3://取值
115                 cout<<"输入整型数i,取第i个元素输出"<<endl;
116                 cin>>i;
117                 if(GetElem(myL,i,e))
118                     cout<<"第i个元素是:"<<e<<endl;
119                     else
120                         cout<<"顺序表取值失败!"<<endl;; 
121                     cout<<"第i个元素是:"<<e<<endl;
122                     break;
123             case 4://查找
124                 cout<<"请输入要查找的数x:";
125                 cin>>x;
126                 if(LocateElem(myL,x)==-1)
127                     cout<<"查找失败!"<<endl;
128                 else 
129                     cout<<"查找成功!"<<endl;
130                     break;
131             case 5://插入
132                 cout<<"请输入要插入的位置和要插入的数据元素e:";
133                 cin>>i>>e;
134                 if(ListInsert_Sq(myL,i,e))
135                     cout<<"插入成功!"<<endl;
136                 else 
137                     cout<<"插入失败!"<<endl;
138                     break;
139             case 6://删除
140                 cout<<"请输入要删除的位置i:";
141                 cin>>i;
142                 if(ListDelete_Sq(myL,i,e))
143                     cout<<"删除成功!"<<endl;
144                 else
145                     cout<<"删除失败!"<<endl;
146                 break;
147             case 7://输出
148                 print(myL);
149                 break;
150             case 8://销毁
151                  cout<<"顺序表销毁·····"<<endl;
152                  DestroyList(myL);
153                  break; 
154         }
155     }
156 return 0;
157 }
158