数据结构顺序表思想以及完整代码实现
2018-06-17 21:00:44来源:未知 阅读 ()
本文转载自趣学算法,方便个人学习参考使用 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 位的元素依次向后移动一个位置,空出第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
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- gcc/g++ 链接顺序注意事项 2020-04-20
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash