线性表的顺序表示和实现

  1 #include<bits/stdc++.h>//c++万能头文件，写了这个其他头文件不用写 
  2 using namespace std;//使用名字空间，你不用管 
  3 
  4 #define List_Init_Size 100
  5 #define List_Inrement 10
  6 #define pr printf
  7 
  8 struct List{
  9     int *elem;//表的基地址 
 10     int length;//当前表长 
 11     int listsize;//当前表的容量 
 12 };
 13 
 14 //初始化线性表 
 15 bool InitList(List &L)
 16 {
 17     L.elem = (int *)malloc(List_Init_Size*sizeof(int));
 18     if(L.elem == NULL) exit(-1); //如果分配内存失败，就退出程序
 19     
 20     L.length = 0;
 21     L.listsize = 100; 
 22     return 1;
 23 } 
 24 
 25 //线性表插入元素 
 26 bool ListInsert(List &L,int i,int e)
 27 {
 28     if(i < 1 || i > L.length + 1) 
 29     {
 30         puts("Oh! Baby! The insertion position is invalid. Please re-enter the insertion position!");
 31         return 0;
 32     } 
 33     //需要清楚，下标是从0开始，
 34     //该函数实现的是在第i个元素前面插入一个元素，所有必须判断插入位置的合法性 
 35     //除了插在最后的元素后面外其他都需要把后面的元素往后移动
 36     
 37     if(L.length >= L.listsize)
 38     {
 39         //表的容量不够，因为插入的会增加一个元素所以有等号 。
 40         //增加容量
 41         int *newbase = (int *)realloc(L.elem,(List_Init_Size + List_Inrement)*sizeof(int));
 42         //realloc函数用来为ptr重新分配大小为size的一块内存，看似很简单，
 43         //在使用过程中却会发生各种错误。
 44         //函数形式为：
 45         //void * realloc ( void * ptr, size_t new_size ); 
 46         
 47         if(newbase == NULL)
 48         {
 49             //意味着重新分配内存失败
 50             puts("Sorry Baby! Reassigning memory failed!");
 51             exit(-1);//退出程序 
 52         }
 53         L.elem = newbase;
 54         L.listsize += List_Inrement;
 55     } 
 56     
 57     int *q = L.elem + (i-1);//获取第i个元素的地址 
 58     
 59     //第i的后面元素往后移动 
 60     for(int *p = L.elem + (L.length-1); p >= q; p--) 
 61     *(p+1) = *p;
 62     
 63     *q = e;
 64     ++L.length;//添加一个元素，长度加一 
 65     return 1;
 66 }
 67 
 68 //线性表删除元素 
 69 bool List_Delete(List &L,int i,int &e)
 70 {
 71     //先判断位置是否合法
 72     if(i < 1 || i > L.length) 
 73     {
 74         puts("Oh baby! The deletion location is illegal, please re-enter!");
 75         return 0;
 76     }
 77     int *q = L.elem + (L.length - 1);
 78     int *p = L.elem + (i-1); 
 79     e = *p;
 80     ++p;//这里是为了把第I后面的元素往前移动，此时的p为第i+1个元素的位置 
 81     for(p; p <= q; p++)
 82     *(p-1) = *p;
 83     --L.length;//删除一个元素，长度减一
 84     return 1; 
 85 } 
 86 
 87 //获取线性表当前的元素个数
 88 int getListLength(List &L)
 89 {
 90     return L.length;
 91 } 
 92 
 93 //获取线性表元素 
 94 bool getElem(List &L,int q,int &e)
 95 {
 96     if(q < 1 || q > L.length)
 97     {
 98         puts("Oh! Baby! The  position is invalid. Please re-enter the position!");
 99         return 0;
100     }
101     int *p = L.elem;
102     for(p ;p <= L.elem + (L.length - 1);p++)
103     {
104         if(p == (L.elem + (q - 1)));
105         {
106             e = *p;
107             break;
108         }
109     }
110     return 1;
111 }
112 
113 //遍历线性表 
114 void List_Traver(List &L)
115 {
116     puts("Let‘s do it! Traver! Traver_List!"); 
117     int *p = L.elem;
118     for(p; p <= L.elem + (L.length - 1); p++)
119     cout << *p << " ";
120     puts("");
121 }
122  
123 //获取要查找的第一个满足某个比较关系的元素位置,我就判断大于，小于，等于吧 
124 int LocateElem(List &L,int e,string s)
125 {
126     int *p = L.elem;
127     int len = L.length;
128     int now = 1;
129        if(s == ">")
130     {
131            for(p ;p <= L.elem + (len - 1);p++)
132            {
133                if(*p > e)
134                {
135                    return  now;
136             }
137             now++;
138         }
139         puts("Oh baby! Sorry, there is no such number!");
140         return 0;
141     } 
142     else if(s == "<")
143     {
144         for(p ;p <= L.elem + (len - 1);p++)
145            {
146                if(*p < e)
147                {
148                    return  now;
149             }
150             now++;
151         }
152         puts("Oh baby! Sorry, there is no such number!");
153         return 0;
154     }
155     else{
156         for(p ;p <= L.elem + (len - 1);p++)
157            {
158                if(*p == e)
159                {
160                    return  now;
161             }
162             now++;
163         }
164         puts("Oh baby! Sorry, there is no such number!");
165         return 0;
166     }
167 } 
168 //销毁线性表,清除堆内存。防止内存泄露 
169 void List_Destroed(List &L)
170 {
171     int *p;
172     //只能从后面销毁 
173     for(p = L.elem + (L.length - 1); p >= L.elem; p--)
174     {
175         free(p); 
176     }
177 }
178 
179 
180 int main()
181 {
182     List L;
183     int ok = InitList(L);
184     if(ok)
185     {
186         puts("Oh Yes! Linear table created successfully!");
187         cout << "base address = " << L.elem << endl;
188         cout << "L.length =  " << L.length << endl;
189         cout << "L.listsize = "<< L.listsize << endl;
190     } 
191     
192     for(int i = 1;i <= 10;i++)
193     {
194         if(ListInsert(L,i,i))
195         {
196             puts("GO");
197         }
198         else {
199             puts("Something Wrong!");
200             exit(-1);
201         }
202     }
203     
204     puts("Check the creation of a linear table");
205     cout << "base address = " << L.elem << endl;
206     cout << "L.length =  " << L.length << endl;
207     cout << "L.listsize = "<< L.listsize << endl;
208     
209     List_Traver(L);
210     
211     int pos = LocateElem(L,5,"<");
212     if(pos) {
213         cout << pos << endl;
214     }
215     
216     pos = LocateElem(L,5,"=");
217     if(pos) {
218         cout << pos << endl;
219     }
220     
221     pos = LocateElem(L,5,">");
222     if(pos) {
223         cout << pos << endl;
224     }
225     
226     cout << "sizeof(L) = " << sizeof(L) << endl;
227     List_Destroed(L);//销毁 
228     cout << "sizeof(L) = " << sizeof(L) << endl;//检查是否销毁成功，如果成功，
229     //下面的语句就不执行 ，因为销毁之后不可用了。 
230     List_Traver(L); 
231     return 0;
232 }