1 #include//c++ universal header file, you don’t need to write this other header file
2 using namespace std;//Use the namespace, you don’t care
3
4 #define List_Init_Size 100
5 #define List_Inrement 10
6 #define pr printf
7
8 struct List{
9 int *elem;//The base address of the table
10 int length;//Current table length
11 int listsize;//Current table capacity
12 };
13
14 //Initialize the linear table
15 bool InitList(List &L)
16 {
17 L.elem = (int *)< span style="color: #0000ff;">malloc(List_Init_Size*sizeof(int ));
18 if(L.elem == NULL) exit(-1); //If memory allocation fails, exit the program
19
20 L.length = 0;
21 L.listsize = 100;
22 return 1;
23 }
24
25 //Linear table insert element
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 //Need to be clear, the subscript starts from 0,
34 //This function is implemented to insert an element before the i-th element, so the validity of the insertion position must be judged
35 //In addition to inserting behind the last element, all other elements need to be moved back
36
37 if(L.length >= L.listsize)
38 {
39 //The capacity of the table is not enough, because the inserted element will add an element so there is an equal sign.
40 //Increase capacity
41 int *newbase = (int *)realloc(L.elem,(List_Init_Size + List_Inrement)*sizeof(int));
42 //The realloc function is used to reallocate a piece of memory of size size for ptr. It seems very simple.
43 //Various errors occur during use.
44 //The function form is:
45 //void * realloc (void * ptr, size_t new_size );
46
47 if(newbase == NULL)
48 {
49 //means that the reallocation of memory failed
50 puts("Sorry Baby! Reassigning memory failed!");
51 exit(-1);//Exit the program
52 }
53 L.elem = newbase;
54 L.listsize += List_Inrement;
55 }
56
57 int *q = L.elem + (i-1);//Get the i Element address
58
59 //The back element of the i-th moves backward
60 for(int *p = L.elem + (L.length-1); p >= q; p--)
61 *(p+1) = *p;
62
63 *q = e;
64 ++L.length;//< span style="color: #008000;">Add an element, plus one for the length
65 return 1;
66 }
67
68 //Linear table delete element
69 bool List_Delete(List &L,int i,int &e)
70 {
71 //First determine whether the location is legal
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;//This is to move the element behind the I forward, where p is the position of the i+1 element
81 for(p; p <= q; p++)
82 *(p-1) = *< span style="color: #000000;">p;
83 --L.length;//< span style="color: #008000;">Delete an element, reduce the length by one
84 return 1;
85 }
86
87 //Get the current number of elements in the linear table
88 int getListLength(List &L)
89 {
90 return L.length;
91 }
92
93 //Get linear table elements
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 //Traverse the linear table
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 << " < span style="color: #800000;">";
120 puts("");
121 }
122
123 //Get the position of the first element that satisfies a certain comparison relationship to be searched, and I will judge it to be greater than, less than, or equal to.
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 //Destroy the linear table and clear the heap memory. Prevent memory leaks
169 void List_Destroed(List &L)
170 {
171 int *p;
172 //Can only be destroyed from the back
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 }
1 #include//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 }
