2.2线性表的顺序存储和基本运算的实现

数组

增加O(n)

删除O(n)

线性查找O(n)二分查找O(log2(n))

修改O(1)

插入O(n)

数据结构：

1 狭义：

数据结构是专门研究数据存储的问题

数据的存储包含两方面：个体的存储+个体关系的存储

2 广义：

数据结构既包含数据的存储也包含数据的操作

对存储数据的操作就是算法

算法：

1 狭义的算法与数据的存储方式密切相关。

2 广义的算法与数据的存储方式无关。

泛型：

利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。

数据的存储结构有几种

1 线性

1.1 连续存储【数组】

优点

存取速度很快

缺点

事先必须知道数组的长度

插入、删除元素很慢

空间通常是有限制

需要大块连续的内存块

1.2 离散存储【链表】

优点

空间没有限制

插入、删除元素很快

缺点

存取速度很慢

线性结构的应用-栈和队列

2 非线性

树

图

1 静态数组

2 动态数组

1 静态数组

  1 #define _CRT_SECURE_NO_WARNINGS
  2 
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 
  6 //作为静态数组，无法变长，一旦分配内存，就固定了，不可以增加
  7 //外部的内存可以访问，但是外部内存可能被使用，也可能没有被使用
  8 //没有使用的情况下，越界偶尔会成功，还是可能被再次回收利用
  9 //已经使用，必然失败
 10 //a[n]等价于*(a+n);从数组名首地址开始，往下寻址，取出内容，数组不会检测越界
 11 //偶尔会成功，偶然的成功比必然的失败更加可怕，数组不可以越界
 12 
 13 main1()
 14 {
 15     int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
 16 
 17     printf("%x
", a);
 18 
 19     system("pause");
 20 }
 21 
 22 //静态数组，不可以处理较大的数据
 23 
 24 main2()
 25 {
 26     int b[1024 * 014 * 10];//默认数组在栈上，最大只能使用1MB
 27 
 28     printf("%x
", b);
 29 
 30     system("pause");
 31 }
 32 
 33 main3()
 34 {
 35     int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
 36     int i, j;
 37     int length = sizeof(a) / sizeof(int);
 38 
 39     for (i = 0;i < length;i++)
 40     {
 41         printf("%d
", a[i]);
 42     }
 43 
 44     int num = 8;//要删除的元素
 45 
 46     if (num == a[9])//检测最后一个元素
 47     {
 48         length = length - 1;//删除一个元素，元素在末尾
 49     }
 50     else
 51     {
 52         for (i = 0;i < length - 1;i++)//检测最后一个之前
 53         {
 54             if (a[i] == num)
 55             {
 56                 for (j = i;j < length - 1;j++)//从删除的位置开始，到最后一个全部向前移动
 57                 {
 58                     a[j] = a[j + 1];//逐个向前移动赋值
 59                 }
 60                 length = length - 1;
 61                 break;
 62             }
 63         }
 64     }
 65 
 66     printf("尾部删除以后
");
 67     for (i = 0;i < length;i++)
 68     {
 69         printf("%d
", a[i]);
 70     }
 71 
 72     system("pause");
 73 
 74 }
 75 
 76 //查询方便
 77 main4()
 78 {
 79     int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
 80     int i;
 81     int flag = 0;
 82     int length = sizeof(a) / sizeof(int);
 83 
 84     for (i = 0;i < length;i++)//逐个访问数组每个元素
 85     {
 86         if (a[i] == 7)//查询
 87         {
 88             flag = 1;
 89             break;
 90         }
 91     }
 92 
 93     if (flag == 1)
 94     {
 95         printf("找到");
 96     }
 97 
 98     system("pause");
 99 }
100 
101 //修改方便
102 main()
103 {
104     int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
105     int i;
106     int flag = 0;
107     int length = sizeof(a) / sizeof(int);
108 
109     for (i = 0;i < length;i++)//逐个访问数组每个元素
110     {
111         if (a[i] == 7)//查询
112         {
113             flag = 1;
114             a[i] = 9;
115             break;
116         }
117     }
118 
119     for (i = 0;i < length;i++)
120     {
121         printf("%d
", a[i]);
122     }
123 
124     system("pause");
125 }

2 动态数组

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <stdbool.h>
  4 
  5 struct Arr
  6 {
  7     int *pBase;//存储的是数组第一个元素的地址
  8     int len;//数组所能容纳的最大元素的个数
  9     int cnt;//当前数组有效元素的个数
 10 };
 11 
 12 typedef struct Arr ARR;
 13 
 14 void init_arr(ARR *pArr, int length);//初始化
 15 bool append_arr(ARR *pArr, int val);//追加
 16 bool insert_arr(ARR *pArr, int pos, int val);//插入，pos值从1开始
 17 bool delete_arr(ARR *pArr, int pos, int * pVal);//删除元素
 18 int get();//暂无实现
 19 bool is_empty(ARR *pArr);//判断是否为空
 20 bool is_full(ARR *pArr);//判断是否已满
 21 void sort_arr(ARR *pArr);//排序
 22 void show_arr(ARR *pArr);//打印
 23 void inversion_arr(ARR *pArr);//逆序
 24 
 25 void main()
 26 {
 27     struct Arr arr;
 28     int val = 0;//保存删除以后的元素
 29     
 30     init_arr(&arr, 6);//初始化
 31     
 32     show_arr(&arr);//打印
 33 
 34     append_arr(&arr, 1);//追加
 35     append_arr(&arr, 2);
 36     append_arr(&arr, 3);
 37     append_arr(&arr, 4);
 38     append_arr(&arr, 5);
 39 
 40     insert_arr(&arr, 6, 99);//插入，pos值从1开始
 41 
 42     show_arr(&arr);//打印
 43 
 44     if (delete_arr(&arr, 1, &val))//删除元素
 45     {
 46         printf("删除成功
");
 47         printf("你所删除的元素是%d
", val);
 48     }
 49     else
 50     {
 51         printf("删除失败
");
 52     }
 53     
 54     show_arr(&arr);//打印
 55 
 56     inversion_arr(&arr);//逆序
 57     show_arr(&arr);//打印
 58 
 59     sort_arr(&arr);//排序
 60     show_arr(&arr);//打印
 61 
 62     system("pause");
 63 }
 64 
 65 void init_arr(ARR *pArr, int length)//初始化
 66 {
 67     pArr->pBase = (int *)malloc(sizeof(int) * length);
 68     if (pArr->pBase == NULL)
 69     {
 70         printf("内存分配失败
");
 71     }
 72     else
 73     {
 74         pArr->len = length;
 75         pArr->cnt = 0;
 76     }
 77 }
 78 
 79 bool append_arr(ARR * pArr, int val)//追加
 80 {
 81     if (is_full(pArr))//满了
 82     {
 83         return false;
 84     }
 85     else
 86     {
 87         pArr->pBase[pArr->cnt] = val;
 88         (pArr->cnt)++;
 89         return true;
 90     }
 91 }
 92 
 93 bool insert_arr(ARR * pArr, int pos, int val)//插入，pos值从1开始
 94 {
 95     int i;
 96     if (is_full(pArr))//满了
 97     {
 98         return false;
 99     }
100     if (pos<1 || pos>pArr->cnt + 1)
101     {
102         return false;
103     }
104     for (i = pArr->cnt - 1; i >= pos - 1; i--)
105     {
106         pArr->pBase[i + 1] = pArr->pBase[i];
107     }
108     pArr->pBase[pos - 1] = val;
109     pArr->cnt++;
110     return true;
111 }
112 
113 bool delete_arr(ARR * pArr, int pos, int * pVal)//删除元素
114 {
115     int i = 0;
116     if (is_empty(pArr))//空了
117     {
118         return false;
119     }
120     if (pos<1 || pos>pArr->cnt)
121     {
122         return false;
123     }
124 
125     *pVal = pArr->pBase[pos - 1];//保存将要删除的元素
126 
127     for (i = pos; i < pArr->cnt; i++)
128     {
129         pArr->pBase[i - 1] = pArr->pBase[i];
130     }
131     pArr->cnt--;
132     return true;
133 }
134 
135 bool is_empty(ARR * pArr)//判断是否为空
136 {
137     if (pArr->cnt == 0)
138     {
139         return true;
140     }
141     else
142     {
143         return false;
144     }
145 }
146 
147 bool is_full(ARR * pArr)//判断是否已满
148 {
149     if (pArr->len == pArr->cnt)
150     {
151         return true;
152     }
153     else
154     {
155         return false;
156     }
157 }
158 
159 void sort_arr(ARR * pArr)//排序
160 {
161     int i = 0, j = 0;
162     int t = 0;
163 
164     for (i = 0; i < pArr->cnt - 1; i++)//冒泡
165     {
166         for (j = 0; j < pArr->cnt - 1 - i; j++)
167         {
168             if (pArr->pBase[j]>pArr->pBase[j + 1])
169             {
170                 t = pArr->pBase[j];
171                 pArr->pBase[j] = pArr->pBase[j + 1];
172                 pArr->pBase[j + 1] = t;
173             }
174         }
175     }
176 }
177 
178 void show_arr(ARR *pArr)//打印
179 {
180     if (is_empty(pArr))
181     {
182         printf("数组为空
");
183     }
184     else
185     {
186         int i = 0;
187         for (i = 0; i < pArr->cnt; i++)
188         {
189             printf("%d ", pArr->pBase[i]);
190         }
191         printf("
");
192     }
193 }
194 
195 void inversion_arr(ARR *pArr)//逆序
196 {
197     int i = 0;
198     int j = pArr->cnt - 1;
199     int t = 0;
200     while (i < j)
201     {
202         t = pArr->pBase[i];
203         pArr->pBase[i] = pArr->pBase[j];
204         pArr->pBase[j] = t;
205         i++;
206         j--;
207     }
208 }

C++实现vector

  1 #include "myvector.h"
  2 
  3 template <class T>
  4 myvector<T>::myvector()
  5 {
  6     p = nullptr;
  7     n = realn = 0;
  8 }
  9 
 10 template <class T>
 11 myvector<T>::~myvector()
 12 {
 13     if (p != nullptr)
 14     {
 15         delete[]p;
 16         p = nullptr;
 17     }
 18 }
 19 
 20 template <class T>
 21 void myvector<T>::push_pack(T t)//最后面插入
 22 {
 23     if (p == nullptr)//如果原来为空表
 24     {
 25         p = new T;
 26         *p = t;
 27         realn = n = 1;
 28     }
 29     else
 30     {
 31         T *ptemp = new T[n + 1];
 32         for (int i = 0; i < n; i++)
 33         {
 34             *(ptemp + i) = *(p + i);
 35         }
 36         *(ptemp + n) = t;
 37         delete[]p;
 38         p = ptemp;
 39 
 40         n += 1;
 41         realn += 1;
 42     }
 43 }
 44 
 45 template <class T>
 46 T *myvector<T>::find(T t)//查找
 47 {
 48     for (int i = 0; i < realn; i++)
 49     {
 50         if (t == p[i])
 51         {
 52             return p + i;
 53         }
 54     };
 55     return nullptr;
 56 }
 57 
 58 template <class T>
 59 void myvector<T>::change(T *pos, T t)//修改
 60 {
 61     if (pos == nullptr)
 62     {
 63         return;
 64     }
 65     else
 66     {
 67         *pos = t;
 68     }
 69 }
 70 
 71 template <class T>
 72 void myvector<T>::del(T t)//删除
 73 {
 74     int pos = -1;
 75     for (int i = 0; i < realn; i++)
 76     {
 77         if (t == *(p + i))
 78         {
 79             pos = i;
 80             break;
 81         }
 82     }
 83     if (pos != -1)
 84     {
 85         if (pos == realn - 1)
 86         {
 87             realn -= 1;
 88         }
 89         else
 90         {
 91             for (int i = pos; i < realn - 1; i++)
 92             {
 93                 p[i] = p[i + 1];
 94             }
 95             realn -= 1;
 96         }
 97     }
 98 }
 99 
100 template <class T>
101 void myvector<T>::insert(T findt, T t)//在某个元素前插入,前插
102 {
103     if (n == realn)//如果标记内存长度==实际长度
104     {
105         int pos = -1;
106         for (int i = 0; i < realn; i++)
107         {
108             if (findt == *(p + i))
109             {
110                 pos = i;
111                 break;
112             }
113         }
114         if (pos != -1)//如果查找的元素存在
115         {
116             T *ptemp = new T[n + 1];
117             for (int i = 0; i < n; i++)
118             {
119                 *(ptemp + i) = *(p + i);
120             }
121             *(ptemp + n) = t;
122             delete[]p;
123             p = ptemp;
124 
125             n += 1;
126             realn += 1;
127         }
128 
129         for (int i = realn - 2; i >= pos; i--)
130         {
131             p[i + 1] = p[i];
132         }
133         p[pos] = t;
134     }
135     else
136     {
137         int pos = -1;
138         for (int i = 0; i < realn; i++)
139         {
140             if (findt == *(p + i))
141             {
142                 pos = i;
143                 break;
144             }
145         }
146 
147         if (pos != -1)
148         {
149             for (int i = realn - 2; i >= pos; i--)
150             {
151                 p[i + 1] = p[i];
152             }
153             p[pos] = t;
154 
155             realn += 1;
156         }
157     }
158 }
159 
160 template <class T>
161 void myvector<T>::show()//打印
162 {
163     if (p == nullptr)
164     {
165         return;
166     }
167     else
168     {
169         for (int i = 0; i < realn; i++)
170         {
171             std::cout << p[i] << " ";
172         }
173         std::cout << "
";
174     }
175 }