顺序表——动态分配和静态分配

静态分配

数组采用静态分配时，数组的大小和空间事先已经固定，一旦空间占满，再新加入数据就会溢出，导致程序崩溃。

1 //顺序表——静态分配 
 2 #include <stdio.h>
 3 #define MaxSize 10        //定义顺序表的最大长度 
 4 
 5 //定义
 6 typedef struct{
 7     int data[MaxSize];        //使用数组存放数据元素 
 8     int length;                //顺序表当前的长度 
 9 }SqList;
10 
11 //初始化——1、将顺序表的所有数据元素初始化为0；2、将顺序表的初始长度设为0 
12 void InitList(SqList &L){        //参数为SqList类型，需要& 
13     for(int i=0;i<MaxSize;i++){
14         L.data[i]=0;        //将顺序表的所有数据元素初始化为0
15     }
16     L.length=0;        //将顺序表的初始长度设为0
17 }
18 
19 //插入 ——在位置i插入元素e 
20 bool ListInsert(SqList &L,int i,int e){
21     if(i<1||i>L.length+1)
22         return false;
23     if(i>=MaxSize)
24         return false;
25     for(int j=L.length;j>=i;j--){
26         L.data[j]=L.data[j-1];        //最好时间复杂度为O(1),最坏和平均为O(n)
27     } 
28     L.data[i-1]=e;
29     L.length++;        //插入后表的长度+1 
30     return true;
31 } 
32 
33 //删除——删除第i个元素 
34 bool ListDelete(SqList &L,int i){
35     if(i<1||i>L.length)
36         return false;
37     for(int j=i;j<L.length;j++){
38         L.data[j-1]=L.data[j];        //最好时间复杂度为O(1),最坏和平均为O(n) 
39     } 
40     L.length--;
41     return true;
42 } 
43 
44 //查找——按值查找
45 int LocateElem(SqList L,int e){
46     for(int i=0;i<L.length;i++){
47         if(L.data[i]==e)
48             printf("该元素为第%d个元素",i+1);
49     }
50     return 0;
51 } 
52 int main(){
53     SqList L;            //定义 
54     InitList(L);        //初始化，此处不需要& 
55     ListInsert(L,1,5);    //在位置1插入元素5
56     ListInsert(L,2,6);    //在位置2插入元素6
57     for(int i=0;i<L.length;i++){
58         printf("插入后的顺序表第%d个元素为：%d\n",i,L.data[i]);
59     }
60     ListDelete(L,2);    //删除第2个元素 
61     for(int i=0;i<L.length;i++){
62         printf("删除后的顺序表为：%d\n",L.data[i]);
63     }
64     LocateElem(L,5);
65     return 0;
66 }

动态分配

数组采用动态分配时，空间在程序执行过程中可以通过动态存储分配语句分配，不需要一次性为线性表划分所有的空间。

1 //顺序表——动态分配
 2 #include <stdio.h>    
 3 #include <stdlib.h>        //使用malloc、free的头文件 
 4 #define InitSize 10        //默认最大长度 
 5 
 6 //定义
 7 typedef struct{
 8     int *data;        //指示动态数组的指针
 9     int MaxSize;    //顺序表的最大容量 
10     int length;     //顺序表的当前长度 
11 }SeqList;
12 
13 //初始化——使用malloc函数动态申请内存
14 void InitList(SeqList &L){
15     L.data=(int *)malloc(InitSize*sizeof(int));        //使用malloc函数动态申请内存
16     L.length=0;        //当前长度设为0 
17     L.MaxSize=InitSize;        //默认最大长度 
18 } 
19 
20 //动态增加数组长度
21 void IncreaseList(SeqList &L,int len){
22     int *p=L.data;        //将数组中的数据暂时存放到指针p
23     L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));        //重新申请内存
24     for(int i=0;i<L.length;i++){
25         L.data[i]=p[i];        //复制数据 
26     } 
27     L.MaxSize=L.MaxSize+len;
28     free(p); 
29 } 
30 
31 //插入
32 bool ListInsert(SeqList &L,int i,int e){
33     if(i<1||i>L.length+1)
34         return false;
35     if(i>=L.MaxSize)
36         return false;
37     for(int j=L.length;j>=i;j--){
38         L.data[j]=L.data[j-1];
39     }
40     L.data[i-1]=e;
41     L.length++;
42     return true;
43 } 
44 
45 //删除
46 bool ListDelete(SeqList &L,int i){
47     if(i<1||i>L.length)
48         return false;
49     for(int j=i;j<L.length;j++){
50         L.data[j-1]=L.data[j];
51     }
52     L.length--;
53     return true;
54 } 
55 
56 //按值查找
57 void LocateElem(SeqList L,int e){
58     for(int i=0;i<L.length;i++){
59         if(L.data[i]==e)
60             printf("元素%d是第%d个元素",e,i+1);
61     }
62 } 
63 int main(){
64     SeqList L;
65     InitList(L);
66 //    IncreaseList(L,10);    //动态增加数组长度
67     ListInsert(L,1,5);    //在位置1插入元素5
68     ListInsert(L,2,6);    //在位置2插入元素6
69     for(int i=0;i<L.length;i++){
70         printf("插入后的顺序表第%d个元素为：%d\n",i,L.data[i]);
71     }
72     ListDelete(L,2);    //删除第2个元素 
73     for(int i=0;i<L.length;i++){
74         printf("删除后的顺序表为：%d\n",L.data[i]);
75     }
76     LocateElem(L,5);
77     return 0;
78 }