实验报告一 顺序表和链表
（1）实验内容
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
2．遍历单向链表。
3．把单向链表中元素逆置（不允许申请新的结点空间）。
4．在单向链表中删除所有的偶数元素结点。
5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。
6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。
7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。
8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
* 9．采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。
10．在主函数中设计一个简单的菜单，分别调试上述算法。
*11．综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）
1 1）顺序表实现基本操作 2 #include <iostream> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #define MaxSize 10 6 using namespace std; 7 typedef int Elemtype; 8 //抽象化元素类型，到时候可根据需要将int修改成其他的基本数据类型 9 typedef struct { 10 Elemtype data[MaxSize]; 11 int length; 12 }Sqlist; 13 //1.构造新的顺序表L 14 //这种创建方法在逻辑上是不对的，因为数组的长度已经规定，不能无限制地输入数据元素 15 Sqlist createSqlist(){ 16 Sqlist l;//length此时不为0，而是随机分配的一个数字 17 int x; 18 scanf ("%d",&x); 19 int i=0; 20 l.length=0; 21 while (x!=-999){ 22 l.data[i]=x; 23 l.length++; 24 i++; 25 scanf("%d",&x);//勿忘重新读入数据 26 } 27 return l; 28 } 29 void displaySqlist(Sqlist &l){//加不加引用的区别？？ 30 for (int i=0;i<l.length;i++){ 31 printf("%d ",l.data[i]); 32 } 33 printf("\n"); 34 } 35 //初始化顺序表 36 void InitSqlist(Sqlist &l){ 37 l.length=0; 38 } 39 //插入：在第i个元素之前 40 void InsertSqlist(Sqlist &l,int i,Elemtype e){ 41 //1.判断I的位置是否合理 42 if (i<1||i>l.length+1)//可以插在最后一个位置 43 printf("positon error"); 44 for (int j=l.length;j>i-1;j--){ 45 l.data[j]=l.data[j-1]; 46 } 47 l.data[i-1]=e; 48 l.length++; 49 } 50 51 void readitemSqlist(Sqlist &l){ 52 int x; 53 scanf ("%d",&x); 54 int i=0; 55 while (x!=-999&&l.length<=MaxSize){ 56 l.data[i]=x; 57 i++; 58 scanf ("%d",&x); 59 l.length++; 60 } 61 } 62 //有返回值的插入方法 63 int InsertSqlist2(Sqlist &l,int i,Elemtype e){ 64 //1.判断I的位置是否合理 65 if (i<1||i>l.length+1){ 66 printf("positon error"); 67 return 0; 68 } 69 70 for (int j=l.length;j>i-1;j--){ 71 l.data[j]=l.data[j-1]; 72 } 73 l.data[i-1]=e; 74 l.length++; 75 return 1; 76 } 77 int deleteSqlist (Sqlist &l,int i,Elemtype &e){ 78 //删除i之前的元素，回收到e中 79 if (i<1||i>l.length){ 80 printf("positon error"); 81 return 0; 82 } 83 e=l.data[i-1]; 84 for (int j=i-1;j<l.length-1;j++){ 85 l.data[j]=l.data[j+1]; 86 } 87 l.length--; 88 return 1; 89 } 90 int locateSqlist (Sqlist &l,Elemtype e){ 91 for (int i=0;i<l.length;i++){ 92 if (l.data[i]==e) 93 return i+1;//返回的是序号 94 } 95 printf("can not find it !"); 96 return 0; 97 //另一种做法 98 //int i=l.length; 99 //while (i>=0&&l.data[i]!=x) i--; 100 //return i+1; 101 //if (i==-1) 102 //return 0; 103 } 104 int main() 105 { 106 Sqlist l; 107 InitSqlist(l); 108 readitemSqlist(l); 109 displaySqlist(l); 110 Elemtype e=5; 111 int i=locateSqlist(l,e); 112 printf("%d",i); 113 114 } 115 2）单链表实现基本操作 116 #include <iostream> 117 #include <stdio.h> 118 #include <stdlib.h> 119 using namespace std; 120 121 122 typedef int Elemtype; 123 typedef struct node 124 { 125 Elemtype data; 126 struct node *next; 127 } node,*linklist; 128 linklist creatlinklist() 129 { 130 //尾插法建立单链表 131 linklist l,p,q; 132 l=(linklist)malloc(sizeof(node)); 133 p=l; 134 int x; 135 scanf("%d",&x); 136 while (x!=-999) 137 { 138 q=(linklist)malloc(sizeof(node)); 139 q->data=x; 140 p->next=q; 141 q->next=NULL; 142 p=q; 143 scanf("%d",&x); 144 } 145 return l; 146 } 147 void displaylinklist(linklist l) 148 { 149 linklist p=l->next; 150 while (p!=NULL) 151 { 152 printf("%d ",p->data); 153 p=p->next; 154 } 155 printf("\n"); 156 } 157 void nizhilinklist(linklist &l) 158 { 159 linklist p,q;//p指向后面结点，q指向当前结点 160 q=l; 161 p=l->next; 162 l->next=NULL;//解放头结点 163 while(p!=NULL) 164 { 165 q=p;//q指向即将头插法的结点 166 p=p->next;//保存后面的结点首地址； 167 q->next=l->next; 168 l-> next=q; 169 } 170 171 } 172 void deletelinklist(linklist &l) 173 { 174 linklist p=l; 175 //p指向待删除元素的前面的位置，必须要从L开始，不然第一个元素无法删除 176 while (p!=NULL) 177 { 178 if(p->next==NULL)//如果最后一个元素是奇数要特别对待 179 break; 180 if (p->next->data%2==0) 181 { 182 p->next=p->next->next; 183 } 184 p=p->next; 185 186 } 187 } 188 void insertlinklist(linklist &l) 189 { 190 Elemtype x; 191 scanf("%d",&x); 192 linklist p; 193 linklist q; 194 p=l; 195 while (p->next!=NULL&&p->next->data < x) 196 { 197 p=p->next; 198 } 199 if (p->next!=NULL){ 200 q=(linklist )malloc(sizeof(node)); 201 q->data=x; 202 q->next=p->next; 203 p->next=q; 204 } 205 if (p->next==NULL) 206 { 207 p->next=q; 208 q->next=NULL; 209 } 210 } 211 void mergelinklist(linklist &la,linklist &lb,linklist &lc){ 212 //假设la与lb为非递减有序单向链表 213 lc=la; 214 linklist pa=la->next,pb=lb->next,pc=lc; 215 lc->next=NULL; 216 while (pa!=NULL&&pb!=NULL){ 217 if (pa->data > pb->data){ 218 pc->next=pb; 219 pc=pb; 220 pb=pb->next; 221 } 222 if (pa->data <= pb->data){ 223 pc->next=pa; 224 pc=pa; 225 pa=pa->next; 226 } 227 228 } 229 if (pa!=NULL) 230 pc->next=pa; 231 if (pb!=NULL) 232 pc->next=pb; 233 free(lb); 234 //free(la)?? 235 //这里判断条件如果用==，那么while循环出来的一定都满足该条件，所以要用不等于 236 237 238 239 } 240 void mergenizhilinklist(linklist &la,linklist &lb,linklist &lc){ 241 mergelinklist(la,lb,lc); 242 nizhilinklist(lc); 243 } 244 linklist dividelinklist(linklist &l){ 245 linklist h=(linklist)malloc(sizeof(node)); 246 h->next=NULL; 247 linklist p=l,q=h; 248 while(p!=NULL){ 249 if(p->next==NULL) 250 break;//最后为偶数 251 if (p->next->data%2!=0){ 252 q->next=p->next; 253 q=p->next; 254 p->next=q->next; 255 p=p->next; 256 } 257 p=p->next; 258 } 259 q->next=NULL; 260 return h; 261 //这里或许可以用头插法建立？？ 262 263 } 264 //实现一元多项式 265 typedef struct { 266 float conf; 267 int expn; 268 }Elemtype; 269 270 typedef struct pnode{ 271 Elemtype data; 272 struct pnode *next; 273 }pnode,*linklist; 274 275 linklist creatPolylist(){ 276 linklist l=(linklist )malloc(sizeof(pnode)); 277 linklist p=l,q; 278 float con; 279 int exp; 280 scanf ("%f %d",&con,&exp); 281 282 while (exp!=-1){ 283 q=(linklist )malloc(sizeof(pnode)); 284 (q->data).conf=con; 285 (q->data).expn=exp; 286 p->next=q; 287 p=q; 288 scanf ("%f %d",&con,&exp); 289 } 290 p->next=NULL; 291 return l ; 292 } 293 void displayPoly(linklist &l){ 294 linklist p=l->next; 295 while (p!=NULL){ 296 printf("(%.2f %d)",((p->data).conf),((p->data).expn)); 297 p=p->next; 298 } 299 printf("\n"); 300 } 301 void addPoly(linklist &la,linklist &lb){ 302 linklist pa=la,pb=lb,qa,qb; 303 qa=pa->next; 304 qb=pb->next; 305 int sum; 306 while (qa!=NULL&&qb!=NULL){ 307 if (qa->data.expn < qb->data.expn){ 308 pa=qa; 309 qa=qa->next; 310 }else if(qa->data.expn = qb->data.expn){ 311 sum=qa->data.conf + qb->data.conf; 312 if (sum!=0){ 313 qa->data.conf=sum; 314 pa=qa; 315 qa=qa->next; 316 pb=qb->next; 317 free(qb); 318 qb=qb->next;//释放B链表中的重复系数结点，这样不占用任何多余空间。 319 }else { 320 pa=qa->next; 321 pb=qb->next; 322 free(qa); 323 free(qb); 324 qa=pa->next; 325 qb=pb->next;//两个结点都要释放 326 327 } 328 }else { 329 pa->next=qb; 330 qb->next=qa; 331 pa=qb; 332 qb=qb->next;//在la链表中插入B中的一个结点，仍旧保持Pa为Qa的前驱，qb后移 333 } 334 } 335 if(qb!=NULL) 336 qa->next=qb; 337 }