线性表运算--顺序存储结构实现

 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_

  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 }