数据结构：单链表的基本操作实现

谁借莪１个温暖的怀抱￠ 2022-12-21 04:56 239阅读 0赞

## 实验3、单链表的基本操作实现 ##

**（1）实验目的**  
通过该实验，深入理解链表的逻辑结构、物理结构等概念，掌握链表基本操作的编程实现，熟练掌握C语言中指针的操作。和实验3对比，掌握线性结构两种不同存储方式的区别。  
**（2）实验内容**  
编程实现链表下教材第二章定义的线性表的基本操作，最好用菜单形式对应各个操作，使其编程一个完整的小软件。注意，每个功能模块一定要考虑非法的情况，并作出相应的提示，例如：求前驱，要分别能够测试第一个元素的前驱、其他正常的元素的前驱、输入一个在表中不存在的元素求其前驱，这三种情况应给出相应的提示语和结果值；插入和删除时要考虑插入或删除的位置是否合法等。  
**（3）实验要求：**  
菜单项包括：  
1.初始化或重置链表  
2.销毁链表  
3.清空链表  
4.链表长度  
5.指定位置的元素值  
6.链表已存在元素的位序  
7.求输入元素的直接前驱  
8.求输入元素的直接后继  
9.在第i个位置插入一个元素  
10.删除第i个元素  
11.输出有的链表元素  
12.初始化并用头插法（或尾插法）输入元素  
13.实现单链表的逆序存放  
**要求：**  
所有的提示语和输出语句不允许出现在自定义的函数中，只能在main函数中出现提示语。  
注：销毁链表时需要循环释放每个结点所占用的空间。  
注：求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值。  
**效果图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]  
**代码如下**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    //--------------线性表的链式存储表示---------------
    typedef int status;     //status是函数的类型，其值是函数结果状态代码。
    typedef int Elem;     //自定
    /* data：数据域 *next：指针域 */
    typedef struct LNode{ 
    	Elem data;
    	struct LNode *next;
    }LNode, *Link; 
    //---------------基本操作的函数原型说明------------ 
    status InitList (Link &L);
           //初始化或重置链表L
    status DestroyList (Link &L);
           //销毁链表
    status ClearList(Link &L);
           //清空链表
    //status ListEmpty(Link L);
    status ListLength(Link L);
           //链表长度
    status GetElem(Link L,int i,Elem &e);
           //指定位置的元素值
    status LocateElem(Link L,Elem e,int &locate);
           //链表已存在元素的位序
    status PriorElem(Link L,Elem cur_e,Elem &pre_e);
           //求输入元素的直接前驱
    status NextElem (Link L,Elem cur_e,Elem &next_e);
           //求输入元素的直接后继
    status ListInsert(Link &L,int i,Elem e);
           //在第i个位置插入一个元素
    status ListDelete(Link &L,int i,Elem &e);
           //删除第i个元素
    status HeadInsert(Link &M);
           //头插 
    status Reorder(Link M,Link &N);
           //元素逆序存放 
           
    //---------------主函数---------------------------- 
    int main (){ 
    	int i = 0;
    	Elem e = 0,pre_e = 0,next_e = 0;
    	int locate = 0;
    	Link L = NULL;  //头节点 
    	Link N = NULL;
    	Link M = NULL;
    	
    	int choice = 0;
    	while (1){ 
    		//菜单
    		printf("\t\t\t 1---初始化一个链表\n");
    		printf("\t\t\t 2---销毁链表\n");
    		printf("\t\t\t 3---清空链表\n");
    		printf("\t\t\t 4---求链表长度\n");
    		printf("\t\t\t 5---获取指定位置的元素\n");
    		printf("\t\t\t 6---获取指定元素的位置\n");
    		printf("\t\t\t 7---求前驱\n");
    		printf("\t\t\t 8---求后继\n");
    		printf("\t\t\t 9---在指定位置插入元素\n");
    		printf("\t\t\t 10--删除指定位置元素\n");
    		printf("\t\t\t 11--输出所有元素\n");
    		printf("\t\t\t 12--初始化并用头插法插入元素\n");
    		printf("\t\t\t 13--实现单链表的逆序存放\n");	
    		printf("\t\t\t 退出，输入一个负数！");
    		printf("\n");
    		printf("\t\t----------------------------------------------\n");
    		printf("\n");
    		printf("请输入你需要的操作：\n");
    		//退出
    		scanf("%d",&choice);
    		if(choice<=0){ 
    			printf("已退出\n");
    			return 0;
    		} 
    		switch (choice){ 
    			case 1:
    				if(L){ 
    					printf("链表已存在，不可重复初始化！\n");
    				}else{ 
    					//初始化 
    					i = InitList(L);
    					if(i==1){ 
    						printf("初始化链表成功\n");
    					}else if(i==-2){ 
    						printf("分配空间失败\n");
    					} 
    				}
    				break;
    			case 2:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//销毁
    					i = DestroyList(L);
    					if(i==1){ 
    						printf("销毁链表成功\n");
    					} 
    				}
    				break;
    			case 3:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//清空
    					i = ClearList(L);
    					if(i==1){ 
    						printf("清空链表成功\n");
    					} 
    				}
    				break;
    			case 4:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					//求长度
    					i = ListLength(L);
    					printf("当前链表的长度为%d\n",i); 
    				}
    				break;
    			case 5:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else{ 
    					if(!L->next) { 
    						printf("该链表是空链表\n");
    					}else{ 
    						//求指定位置的元素 
    						printf("请输入你想查找的位置\n");
    					    scanf("%d",&locate);
    					    i = GetElem(L,locate,e);
    				    	if(i ==1){ 
    				    		printf("该位置的元素为%d\n",e);
    				    	}else{ 
    				    		printf("输入位置不合法\n");
    				    	}
    					}	
    				}
    				break;
    			case 6:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					//求链表已存在元素位序
    					printf("请输入你想要查找的元素\n");
    					scanf("%d",&e);
    					i = LocateElem(L,e,locate);
    					 if(i ==1){ 
    						printf("该元素的位置为%d\n",locate);
    					}else{ 
    						printf("链表没有该元素\n");
    					}
    				}
    				break;
    			case 7:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					//求前驱
    					printf("请输入你想查询的元素\n");
    					scanf("%d",&e);
    					i = PriorElem(L,e,pre_e);
    					if(i == 1){ 
    						printf("该元素的直接前驱为%d\n",pre_e); 
    					} else if(i == -2){ 
    						printf("第一个元素没有直接前驱\n");
    					}else{ 
    						printf("元素输入错误\n");
    					}
    				}
    				break;
    			case 8:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					//求后继
    					printf("请输入你想查询的元素\n");
    					scanf("%d",&e);
    					i = NextElem(L,e,next_e);
    					if(i == 1){ 
    						printf("该元素的直接后继为%d\n",next_e); 
    					} else if(i == -2){ 
    						printf("最后一个元素没有直接后继\n");
    					}else{ 
    						printf("元素输入错误\n");
    					}
    				}
    				break;
    			case 9:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else{ 
    					//在指定位置插入元素
    					while(1){ 
    						printf("请输入你想插入元素的位置：（输入0退出）");
    						scanf("%d",&locate);
    						if(locate < 0){ 
    							printf("输入位置不合法\n");
    							continue; 
    						}else if(locate == 0){ 
    							break;
    						}
    						printf("请输入你想插入的元素：");
    						scanf("%d",&e);
    						i = ListInsert(L,locate,e);
    						if( i == 1){ 
    						printf("插入成功\n"); 			
    						}else{ 
    							printf("输入位置不合法\n");
    						}
    					
    					} 
    				}
    				break;
    			case 10:
    				if(!L){ 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					//删除指定位置元素
    					printf("请输入你想删除元素的位置");
    					scanf("%d",&locate);
    					if(locate < 0){ 
    						printf("输入位置不合法\n");
    						continue;
    					}
    					i = ListDelete(L,locate,e);
    					if( i == 1){ 
    						printf("元素%d成功删除\n",e); 			
    					}else{ 
    						printf("输入位置不合法\n");
    					}
    				}
    				break;
    			case 11:
    				if(!L){ 
    					//输出所有元素 
    					printf("链表未完成初始化，请先进行初始化！\n");
    				}else if(!L->next){ 
    					printf("该链表是空链表\n");
    				}else{ 
    					N = L->next;
    					printf("该链表：【链头】->");
    					while(N){ 
    						printf("【%d】->",N->data);
    						N = N->next;
    					} 
    					printf("【链尾】\n");
    				}
    				break;
    			case 12:
    				//头插
    				i = ClearList(M); 
    				printf("使用头插法将{10,20,30,40,50}五个元素插入一个新的链表\n"); 
    				i = HeadInsert(M);
    				N = M;
    				printf("该链表：【链头】->");
    				while(N){ 
    					printf("【%d】->",N->data);
    					N = N->next;
    				} 
    				printf("【链尾】\n");
    				break;
    			case 13:
    				i = HeadInsert(M);
    				N = M;
    				printf("原链表顺序为：【链头】->");
    				while(N){ 
    					printf("【%d】->",N->data);
    					N = N->next;
    				} 
    				printf("【链尾】\n");
    				
    				i = DestroyList(N);
    				i = Reorder(M,N);
    				printf("逆序后的链表顺序为：【链头】->");
    				while(N){ 
    					printf("【%d】->",N->data);
    					N = N->next;
    				}
    				printf("【链尾】\n");				
    				break;
    			default:
    				printf("选择失败！请重新选择！\n");
    				break; 	 	 	 			
    		}
    		system("pause");   //请按任意键结束 
    		system("cls");     //清屏 
    	}
    	return 0;
    }
    
    //---------------基本操作的算法描述----------------
    status InitList (Link &L){ 
    	//初始化或重置链表L
    	L = (Link)malloc(sizeof(LNode));
    	if (!L){    //开辟空间失败 
    		return OVERFLOW;
    	}
    	L->next = NULL;
    	return OK;
    }
    
    status DestroyList (Link &L){ 
    	//销毁链表
    	Link p;
    	while(L){ 
    		p = L;
    		L = L->next;		
    		free(p);
    	} 
    	return OK;
    }
    
    status ClearList (Link &L){ 
    	//清空链表
    	Link p,q;
    	p = L->next;
    	while(p){ 
    		q = p;
    		p = p->next;
    		free(q);
    	} 
    	L->next = NULL; 
    	return OK;
    }
    
    status ListLength (Link L){ 
    	//求链表长度
    	int i = 0;
    	L = L->next;
    	while (L){ 
    		i++;
    		L = L->next;
    	} 
    	return i;
    }
    
    status GetElem(Link L,int i,Elem &e){ 
    	//求指定位置的元素 
    	if(i<0){ 
    		return ERROR;
    	} 
    	int numb = 0;
    	/* while(L){ L = L->next; numb++; if(numb == i){ break; } } */	
    	do{ 	
    		L = L->next;
    		if(!L){ 
    			return ERROR;
    		}
    		numb++; 
    	}while(numb != i);
    	e = L->data;
    	return OK;
    }
    
    status LocateElem (Link L,Elem e,int &locate){ 
    	//链表已存在元素的位序
    	int i = 0;
    	do{ 
    		L = L->next;
    		i++;
    		if(L->data == e){ 
    			locate = i;
    			return OK;
    		}
    	}while(L);
    	return ERROR;
    }
    
    status PriorElem(Link L,Elem cur_e,Elem &pre_e){ 
        //求输入元素的直接前驱
        L = L->next;
    	if(L->data == cur_e){ 
    		return OVERFLOW; 
    	} 
    	Link p;
    	while (L->next){ 
    		p = L->next;
    		if(p->data == cur_e){ 
    			pre_e = L->data;
    			return OK;
    		}
    		L = L->next;
    	}
    	return ERROR;
    } 
    
    status NextElem(Link L,Elem cur_e,Elem &next_e){ 
    	//求后继
    	L = L->next; 
    	Link p = L->next;
    	while (p){ 
    		if(L->data == cur_e){ 
    			next_e = p->data;
    			return OK;
    		}
    		L = L->next;
    		p = L->next;
    	}
    	if(!p && L->data == cur_e){ 
    		return OVERFLOW;
    	}
    	return ERROR;
    }
    
    status ListInsert(Link &L,int i,Elem e){ 
    	/*在第i个位置插入一个元素 插入后，原来该位置元素后移 i取值应合法 */
    	Link q = L;
    	int m = 0; 
    	do{ //通过遍历L来查找位置,且运用do-while循环可判短 
    		if(m == i-1){ 
    			//尾插 
    			Link p = (Link)malloc(sizeof(LNode));
    			p->data = e;
    			p->next = q->next;
    			q->next = p;
    			return OK;  
    		}
    		m++;
    		q = q->next;
    	}while(q); 
    	if(!q && m != i-1){ 
    		//i值不合法
    		return ERROR; 
    	}
    }
           
    status ListDelete(Link &L,int i,Elem &e){ 
    	/*删除第i个元素 删除后，原来该位置下一个元素前移 i取值应合法 */
    	Link q = L;
    	Link p ; 
    	int m = 1; 
    	do{ //通过遍历L来查找位置,且运用do-while循环可判断
    		p = q->next;
    		if(m == i){ 
    			e = p->data;
    			q->next = p->next;
    			free(p);
    			return OK;  
    		}
    		m++;
    		q = p;
    	}while(p->next); 
    	return ERROR; 
    }
        
    status HeadInsert(Link &M){ 
    	//头插 
    	int a[5] = { 10,20,30,40,50};
    	for(int i = 0; i < 5;i++){ 
    		Link q = (Link)malloc(sizeof(LNode));
    		q->data = a[i];
    		q->next = M ;
    		M = q;
    	}
    	
    	return OK;
    } 
           
    status Reorder(Link M,Link &N){ 
    	//元素逆序存放
    	 while(M){ 
    	 	Link p = (Link)malloc(sizeof(LNode));
    	 	p->data = M->data;
    	 	p->next = N;
    	 	N = p;
    	 	M = M->next;
    	 }
    	 return OK;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9a32aa90a8f74eecb2bebcfbbaca183d.png