首页 > 代码库 > 线性表运算--顺序存储结构实现
线性表运算--顺序存储结构实现
对于线性表我们应掌握如下要点：
1、 掌握线性表的结构特点：顺序存储和链式存储。
2、 掌握线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度等运算在顺序存储结构和链式存储结构上的实现。
顺序存储具有随机访问的特点，而链式存储具有顺序访问的特点。
对于不同的应用我们应当选择不同的结构。
顺序结构实现源代码如下：
1 HList.h //线性表头文件定义 2 //数据结构头文件在定义， 3 //链表的头文件 4 #ifndef _HLIST_H_ 5 #define _HLIST_H_ 6 //#define M_error -1 7 #include"stdlib.h" 8 #define Length_Size 100 9 #define add_Length 10 10 typedef int Element; 11 struct Link 12 { 13 Element *p; //链表表示的物理线形表 14 Element leg ; //线形表的当前长度 15 Element list_size; //线形表分配的数据的长度 16 17 }; 18 //定义一个函数指针类型P_ptr 19 //用于compare();比较函数的调用 20 typedef bool (*P_ptr)(Element &a,Element &b); 21 22 //定义一个函数指针类型P_Vs 23 typedef bool (*P_Vs)(Element &a,Element &b); 24 25 //初始化一个线形表 26 //成功返回ture 失败返回false; 27 bool InitList(Link &L); 28 29 //销毁一个线形表 30 //显形表不存在提示错误 31 //销毁成功返回true,销毁失败返回false; 32 void DestroyList(Link &L); 33 34 //线形表不存在提示错误 35 //线形表存在清空 36 //清空成功返回ture,清空失败返回false; 37 bool ClearList(Link &L); 38 39 //线形表是否为空 40 //线形表存在不为空返回ture,线形表存在为空返回false 41 bool IsLink_Empty(Link &L); 42 43 //线形表存在，返回线形表数据元素的长度 44 45 int Get_Link_Length(Link &L); 46 47 //用e获得线形表中第i个元素 48 //前提线形表已经存在 49 //获得成功返回ture;获得非法，提示错误 50 bool Get_element(Link &L,int i,Element &e); 51 52 //线形表存在，e在线形表中第一个满足compare() 53 //条件的元素，若不满足，则提示错误，若不存在则提示 54 int Get_Compare(Link &L,Element &e,P_ptr p); 55 56 //获得前驱 57 //前提L存在，若cur是线形表中的元素，且cur不是第一元素，则返回 58 //cur的前面一个元素，若找不到则返回错误， 59 //若找到用pre_e返回，返回 ture 60 bool Get_Prior_Elm(Link &L,Element &cur,Element &pre_e); 61 62 //获得后继， 63 //前提L存在，若 cur是线形表中的元素，且cur不是第一元素，则返回 64 //cur的后面一个元素，若找不到则返回错误， 65 //若找到用next_e返回，返回为ture 66 bool Get_Next_Elm(Link &L,Element &cur,Element &next_e); 67 68 //链表存在， 69 //在链表的第i个元素前插入一个元素e。 70 //插入范围从i=1,到从末尾插入 71 //插入成功返回ture,失败返回错误提示 72 bool List_Insert(Link &L,int i,Element &e); 73 74 //链表存在，将链表中的第i个指定元素删除， 75 //删除成功返回ture,删除不合法或者错误返回false; 76 bool List_Delete(Link &L,int i); 77 78 //线形表存在，依次对线形表的每个元素调用vist(); 79 //vist(),操作失败则返回false,操作成功返回ture; 80 bool ListTraverse(Link &L,P_Vs visit,Element &e); 81 82 //compare()函数的声明 83 bool Compare(Element &a,Element &b); 84 85 86 //输出打印线性表中的所有值 87 void Print_Link(Link &L); 88 89 bool visit(Element &a,Element &b); 90 91 #endif //_HLIST_H_
HList.cpp
1 HList.cpp //线性表实现文件 2 3 //数据结构在定义实现文件 4 //数据结构头文件在定义， 5 #include<iostream> 6 #include"HList.h" 7 //初始化一个线形表，首选默认调用 8 //成功返回ture 失败返回false; 1 9 bool InitList(Link &L) 10 { 11 L.p = (Element*)malloc(Length_Size*sizeof(Element)); //分配100个元素的存储空间 12 if(!L.p) 13 { 14 std::cout<<"内存空间分配失败"<<std::endl; 15 return false; 16 17 } 18 else 19 { 20 L.list_size = Length_Size; //初始分配量 21 L.leg = 0; //当前线形表内容长度 22 int i = 0; 23 for(;i<6;i++) 24 { 25 L.p[i] = i+1; 26 27 } 28 L.leg = 6; 29 return true; 30 } 31 32 } 33 34 35 //销毁一个线形表 最后自动调用 36 //销毁成功返回true,销毁失败返回false; 2 37 void DestroyList(Link &L) 38 { 39 L.list_size = 0; 40 L.leg = 0; 41 free(L.p); 42 } 43 44 //线形表存在清空 45 //清空成功返回ture,清空失败返回false; 3 46 bool ClearList(Link &L) 47 { 48 if (L.leg>0) 49 { 50 L.leg = 0; 51 return true; 52 53 } 54 else if(0==L.leg) 55 { 56 return true; 57 } 58 else 59 { 60 return false; 61 } 62 } 63 //线形表是否为空 64 //线形表存在不为空返回ture,线形表存在为空返回false 4 65 bool IsLink_Empty(Link &L) 66 { 67 if(0 == L.leg && L.p!=NULL ) 68 { 69 return true; 70 } 71 else 72 { 73 return false; 74 75 } 76 } 77 78 //线形表存在，返回线形表数据元素的长度 5 79 int Get_Link_Length(Link &L) 80 { 81 if (L.p!=NULL) 82 { 83 return L.leg; 84 } 85 else 86 { 87 return -2; 88 } 89 } 90 91 //用e获得线形表中第i个元素 92 //获得成功返回ture;获得非法，提示错误 6 93 bool Get_element(Link &L,int i,Element &e) 94 { 95 if(L.p!=NULL &&L.leg!=0 && 0<i &&i<=L.leg) 96 { 97 e = L.p[i-1]; 98 return true; 99 } 100 else if (L.leg == 0) 101 { 102 std::cout<<"线性表为空"<<std::endl; 103 return false; 104 } 105 else if(i<1||i>L.leg) 106 { 107 std::cout<<"i值不合法"<<std::endl; 108 return false; 109 } 110 else 111 { 112 return false; 113 } 114 115 } 116 117 //b为比较元素e 118 //a为线性表元素 119 bool Compare(Element &a,Element &b) 120 { 121 if (a>b) 122 { 123 return true; 124 } 125 else 126 { 127 return false; 128 } 129 } 130 131 //线形表存在，e在线形表中第一个满足compare() 132 //条件的元素，若不满足，则提示错误，若不存在则提示 133 int Get_Compare(Link &L,Element &e,P_ptr p) 134 { 135 int i=0; 136 if(0 == L.leg) 137 { 138 return -1; 139 } 140 else 141 { 142 for(;i<L.leg;i++) 143 { 144 if(p(L.p[i],e)) 145 { 146 return i+1; 147 } 148 } 149 return -2; 150 } 151 } 152 //获得前驱 153 bool Get_Prior_Elm(Link &L,Element &cur,Element &pre_e) 154 { 155 int i = 1; 156 if(0 ==L.leg) 157 { 158 std::cout<<"线性表为空，无法完成操作"<<std::endl; 159 return false; 160 } 161 else if (L.p[0] == cur) 162 { 163 std::cout<<"cur为线性表中第一个元素，没有前驱"<<std::endl; 164 return false; 165 } 166 else 167 { 168 for(;i<=L.leg;i++) 169 { 170 if(L.p[i]==cur) 171 { 172 pre_e = L.p[i-1]; 173 return true; 174 } 175 176 } 177 std::cout<<"输入元素不存在"<<std::endl; 178 return false; 179 } 180 181 } 182 183 //获得后继， 184 bool Get_Next_Elm(Link &L,Element &cur,Element &next_e) 185 { 186 int i = 0; 187 if(0 ==L.leg) 188 { 189 std::cout<<"线性表为空，无法完成操作"<<std::endl; 190 return false; 191 } 192 else if (L.p[L.leg-1] == cur) 193 { 194 std::cout<<"cur为线性表中最后一个元素，没有后继"<<std::endl; 195 return false; 196 } 197 else 198 { 199 for(;i<L.leg-1;i++) 200 { 201 if(L.p[i]==cur) 202 { 203 next_e = L.p[i+1]; 204 return true; 205 } 206 } 207 std::cout<<"输入元素不存在"<<std::endl; 208 return false; 209 } 210 } 211 212 213 214 bool List_Insert(Link &L,int i,Element &e) 215 { 216 int j=L.leg; 217 Element* new_p; 218 if(i<1&&i>L.leg+1) 219 { 220 std::cout<<"i值不合法"<<std::endl; 221 return false; 222 223 } 224 if(L.leg ==L.list_size)//内存不足，分配空间 225 { 226 new_p = (Element*)realloc(L.p,(L.list_size+add_Length)*sizeof(Element)); 227 if(!new_p) 228 { 229 std::cout<<"内存扩展失败"<<std::endl; 230 return false; 231 } 232 L.p = new_p; 233 } 234 for(;j>=i;j--) 235 { 236 L.p[j]=L.p[j-1]; 237 } 238 239 L.p[i-1] = e; 240 L.leg++; 241 242 return true; 243 } 244 245 246 bool List_Delete(Link &L,int i) 247 { 248 if(0==L.leg) 249 { 250 std::cout<<"线性表为空，无法执行删除操作"<<std::endl; 251 return false; 252 } 253 else 254 { 255 int j = i; 256 if(1<=i&&i<=L.leg) 257 { 258 while(j<L.leg) 259 { 260 L.p[j-1] = L.p[j]; 261 j++; 262 } 263 L.leg--; 264 return true; 265 } 266 else if (i<1||i>L.leg) 267 { 268 std::cout<<"i值输入不合法"<<std::endl; 269 return false; 270 } 271 else 272 { 273 return false; 274 } 275 } 276 } 277 278 bool visit(Element &a,Element &b) 279 { 280 if(a<=b) 281 { 282 return false; 283 } 284 else 285 { 286 return true; 287 } 288 } 289 //测试，；依次对元素调用visit函数 290 //有一个不满足则返回false 291 bool ListTraverse(Link &L,P_Vs visit,Element &e) 292 { 293 if(0==L.leg) 294 { 295 std::cout<<"线性表为空"<<std::endl; 296 return false; 297 } 298 else 299 { 300 while(L.leg>=1) 301 { 302 if(!visit(L.p[L.leg-1],e)) 303 { 304 return false; 305 } 306 L.leg--; 307 } 308 } 309 return true; 310 311 } 312 313 314 void Print_Link(Link &L) 315 { 316 int i = 1; 317 for(;i<=L.leg;i++) 318 { 319 std::cout<<L.p[i-1]<<" "; 320 } 321 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。