/* ***********************************************
Author :mubaixu
Created Time :2015-12-08 20:45:05
File Name :线性表顺序存储操作
************************************************ */
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <malloc.h>
4 #include <windows.h>
5 #define TRUE 1
6 #define FALSE 0
7 #define OK 1
8 #define ERROR 0
9 #define INFEASIBLE -1
10 #define OVERFLOW -2
11 #define LIST_INIT_SIZE 100
12 #define LISTINCREMENT 10
13 #define status int
14 #define elemtype int
15 typedef struct {
16 elemtype *elem;
17
18 int lenght;
19 int listsize;
20 }sqlist;
21 status initlist(sqlist &l){//构造线性表
22 l.elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype));
23 if(!l.elem)
24 exit(OVERFLOW);
25 l.lenght=0;//运行过程中的动态长度
26 l.listsize=LISTINCREMENT;//初始化的静态长度。
27 return OK;
28 }
29
30 status listinsert(sqlist &l,int i,elemtype e){//在线性表第i个位置插入元素e
31 if(i<1||i>l.lenght+1)
32 return ERROR;
33 elemtype *p=NULL;
34 elemtype *q=NULL;
35 elemtype *newbase=NULL;
36
37 if(l.lenght>=l.listsize){
38 newbase=(elemtype *)realloc(l.elem,(LISTINCREMENT+LIST_INIT_SIZE)*sizeof(elemtype));
39 if(!newbase)
40 return OVERFLOW;
41 l.elem=newbase;
42 l.listsize+=LISTINCREMENT;
43 }
44
45 q=&(l.elem[i-1]);
46 for(p=&(l.elem[l.lenght-1]);p>=q;p--){
47 *(p+1)=*p;
48 }
49 *q=e;
50 ++l.lenght;
51 return OK;
52 }
53
54 status listdelete(sqlist &l,int i,elemtype &e){//删除线性表中的第i个元素， 并且返回删除的值为e
55
56 if(i<1||i>l.lenght)
57 return ERROR;
58
59 elemtype *p=NULL;
60 elemtype *q=NULL;
61 q=&(l.elem[i-1]);
62 e=*q;
63 p=l.elem+l.lenght-1;
64 for(++q;q<=p;q++){
65 *(q-1)=*q;
66 }
67 --l.lenght;
68 return OK;
69 }
70 void mergelist(sqlist la,sqlist lb,sqlist &lc){
71 elemtype *pa,*pb,*pc,*pb_last,*pa_last;
72 //将la和lb按非递减顺序排序后赋值于lc
73 //eg: la:3 5 8 11
74 // lb:2 6 8 9 11 15 20
75 // lc:2 3 5 6 8 8 9 11 11 15 20
76 pa=la.elem;
77 pb=lb.elem;
78 pc=lc.elem;
79 printf("------
");
80 lc.listsize=lc.lenght=la.lenght+lb.lenght;
81 pc=lc.elem=(elemtype *)malloc(lc.listsize*sizeof(elemtype));
82 pa_last=la.elem+la.lenght-1;
83 pb_last=lb.elem+lb.lenght-1;
84 // printf("--------->%d %d %d
",la.lenght,lb.lenght,lc.lenght);
85 while(pa<=pa_last&&pb<=pb_last){
86 if(*pa<=*pb){
87 *pc++=*pa++;
88 }
89 else
90 *pc++=*pb++;
91 }
92
93 while(pa<=pa_last)
94 *pc++=*pa++;
95 while(pb<=pb_last)
96 *pc++=*pb++;
97
98 }
99 status compare(elemtype x, elemtype y)
100 {
101 return x == y;
102 }
103 int locateelem(sqlist l,elemtype e,status(*compare)(elemtype,elemtype)){
104 //在线性表中查找元素e,如果查到了返回其位序，位序值从1开始
105 //如果没有查到返回0
106 elemtype i=1;
107 elemtype *p=l.elem;
108 while(i<=l.lenght&&!(*compare)(*p++,e))
109 ++i;
110 if(i<=l.lenght)
111 return i;
112 else
113 return 0;
114 }
115
116
117 void Union(sqlist &la,sqlist lb){
118 // 将所有在线性表lb中但是不在la中的元素插入到线性表la的后面
119 elemtype la_len,lb_len;
120 la_len=la.lenght;
121 lb_len=lb.lenght;
122 for(int i=1;i<=lb_len;i++){
123 elemtype tmp=lb.elem[i-1];
124
125 if(!locateelem(la,tmp,compare))
126 listinsert(la,++la_len,tmp);
127 }
128 la.lenght=la_len;
129 }
130
131 int main(){
132 //构造基本顺序表并按照逆序顺序输出主函数
133 freopen("in.txt","r",stdin);
134 freopen("out.txt","w",stdout);
135 sqlist l;
136 initlist(l);
137 elemtype e,i;
138 i=0;
139 while(~scanf("%d",&e)){
140 i++;
141 listinsert(l,i,e);
142 }
143 printf("%d
",l.lenght);
144 for( i=l.lenght-1;i>=0;i--)//逆序输出
145 printf("%d",l.elem[i]);
146 for( i=0;i<l.lenght;i++)//正序输出
147 printf("%d",l.elem[i]);
148 //删除元素
149 //如果想要删除第pos个元素
150 elemtype pos;
151 scanf("%d",&pos);
152 listdelete(l,pos,e);
153 printf("%d
",l.lenght);
154 for(i=0;i<l.lenght;i++)
155 printf("%d ",l.elem[i]);
156 puts("");
157 //查找某个元素是否在线性表l中
158 //如果在返回其相对位序，如果不在，返回值为0
159 elemtype x;
160 scanf("%d",&x);
161 elemtype ans=locateelem(l,x,compare);
162 printf("%d
",ans);
163 return 0;
164 }
165
166 int main(){
167 //分别输入两个线性表的序列，构造两个线性表
168 //后将两个表合并按顺序输出
169 // page20算法2.2实现 && page26算法2.7
170 freopen("in.txt","r",stdin);
171 freopen("out.txt","w",stdout);
172 sqlist l1,l2,l3;
173 initlist(l1),initlist(l2),initlist(l3);
174 elemtype e,i,cnt;
175 cnt=0;
176 elemtype n1,n2;
177 scanf("%d",&n1);
178 for( i=0;i<n1;i++){
179 scanf("%d",&e);
180 cnt++;
181 listinsert(l1,cnt,e);
182 }
183 scanf("%d",&n2);
184 cnt=0;
185 for( i=0;i<n2;i++){
186 scanf("%d",&e);
187 cnt++;
188 listinsert(l2,cnt,e);
189 }
190 //printf("--------->%d %d %d
",l1.lenght,l2.lenght,l3.lenght);
191 mergelist(l1,l2,l3);
192 printf("%d
",l3.lenght);//输出合并后的线性表长度
193 for( i=0;i<l3.lenght;i++){
194 printf("%d ",l3.elem[i]);//按顺序输出合并后的表的序列
195 }
196 puts("");
197 return 0;
198 }
199
200 int main(){
201 //构造两个线性表，将两个表合并至第一个表中，要求将第二个表中不在第一个表中的元素
202 //放置在第一个表中的后面
203 //page20 此主函数和Union函数相对应
204 freopen("in.txt","r",stdin);
205 freopen("out.txt","w",stdout);
206 sqlist l1,l2;
207 initlist(l1),initlist(l2);
208 elemtype e,i,cnt;
209 cnt=0;
210 elemtype n1,n2;
211 scanf("%d",&n1);
212 for( i=0;i<n1;i++){
213 scanf("%d",&e);
214 cnt++;
215 listinsert(l1,cnt,e);
216 }
217 scanf("%d",&n2);
218 cnt=0;
219 for( i=0;i<n2;i++){
220 scanf("%d",&e);
221 cnt++;
222 listinsert(l2,cnt,e);
223 }
224
225 Union(l1,l2);
226 printf("%d
",l1.lenght);
227 for(int i=0;i<l1.lenght;i++)
228 printf("%d ",l1.elem[i]);
229 puts("");
230 return 0;
231 }