《数据结构》实验报告（二）——单链表存储结构及实现

逃离我推掉我的手 2022-11-20 02:57 150阅读 0赞

## 单链表存储结构及实现 ——学生信息管理 ##

**一、实验目的**  
(1) 掌握单链表的概念及实现方式。  
(2) 掌握单链表的存储结构及主要运算，如建立、查找、插入、删除等。  
**二、实验环境**  
Windows 10，Microsoft Visual C++ 2010 Express  
**三、实验内容**  
*1、内容描述*  
定义一个包含学生信息（学号，姓名，成绩）的链表，使其具有如下功能：  
(1) 根据指定学生个数，逐个输入学生信息；  
(2) 逐个显示学生表中所有学生的相关信息；  
(3) 根据姓名进行查找，返回此学生的学号和成绩；  
(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；  
(5) 给定一个学生信息，插入到表中指定的位置；  
(6) 删除指定位置的学生记录。  
*2、实现代码*

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    typedef struct{
        
        char no[20];   //学号
        char name[20]; //姓名
        int mark;     //成绩
    }student;
    typedef struct LNode{
        
         student data;       //数据域
         struct LNode *next;   //指针域
    }LNode,*LinkList;
    
    bool initlist(LinkList &L){
        
        int n;
    	LinkList p,s;
    	p=L;
    	printf("输入学生人数：");
    	scanf("%d",&n);
    	printf("输入学生信息，按“学号 姓名 成绩”输入\n");
    	for(int i=0;i<n;i++){
        
    		s=new LNode;
    		printf("输入第%d位学生信息：",i+1);
            scanf("%s %s %d",&s->data.no,&s->data.name,&s->data.mark);
    		s->next=NULL;
    		p->next=s;
    		p=s;
    	}
    	return true;
    }
    
    bool displist(LinkList L){
        
    	if(L->next==NULL){
        
    		printf("请建立学生信息表！");
    		return false;
    	}
    	LinkList p;
    	p=L;
    	while(p->next!=NULL){
        
    		p=p->next;
    		printf("学号：%s  姓名：%s  成绩：%d\n",p->data.no,p->data.name,p->data.mark);
    	}
    	return true;
    }
    
    bool deletelist(LinkList &L){
        
    	if(L==NULL){
        
    		printf("请建立学生信息表！\n");
    		return false;
    	}
    	int i,j=0;
    	LinkList p,q;
    	p=L;
    	printf("输入删除的位置序号：");
    	scanf("%d",&i);
    	while((p->next!=NULL)&&(j<i-1)){
        
    		p=p->next;++j;
    	}
    	if(!(p->next!=NULL)||(j>i-1)){
        
            printf("请输入正确的序号！");
    		return false;
    	}
    	q=p->next;
    	p->next=q->next;
    	delete q;
    	return true;
    }
    
    bool inserlist(LinkList &L){
        
    	if(L==NULL){
        
    		printf("请建立学生信息表！");
    		return false;
    	}
    	int i,j=0;
    	LinkList p;
    	p=L;
    	printf("输入插入的位置序号：");
    	scanf("%d",&i);
    	while(p&&(j<i-1)){
        
    		p=p->next;
    		j++;
    	}
    	if(!p||j>i-1){
        
            printf("请输入正确的序号！\n");
    		return false;
    	}
    	LinkList s;
    	s=new LNode;
    	printf("输入插入的学生信息，按“学号 姓名 成绩”输入\n");
    	scanf("%s %s %d",&s->data.no,&s->data.name,&s->data.mark);
    	s->next=p->next;
    	p->next=s;
    	return true;
    }
    
    bool seeklist(LinkList L){
        
    	int flag=0;
    	char na[20];
    	if(L->next==NULL){
        
    		printf("请建立学生信息表！");
    		return false;
    	}
    	LNode *p;
    	p=L;
    	printf("输入查找的姓名：");
    	scanf("%s",na);
    	while(p->next!=NULL){
        
    		p=p->next;
    		if(strcmp(p->data.name,na)==0){
        
    			flag=1;
    			printf("学号：%s  成绩：%d\n",p->data.no,p->data.mark);
    		}
    	}
    	if(!flag)
    		printf("未找到相关信息!\n");
    	return true;
    }
    
    bool seek2list(LinkList L){
        
    	int num;
    	if(L->next==NULL){
        
    		printf("请建立学生信息表！");
    		return false;
    	}
    	LNode *p;
    	p=L;
    	printf("输入查找的序号：");
    	scanf("%d",&num);
    	for(int i=0;p!=NULL&&i<num;i++){
        
    		p=p->next;
    	}
    	if(p==NULL){
        
    	    printf("请输入正确的序号！\n");
    		return false;
    	}
    	printf("学号：%s  姓名：%s  成绩：%d\n",p->data.no,p->data.name,p->data.mark);
    	return true;
    }
    
    void main(){
        
    	int choose=0;
    	LinkList L;
    	L=new LNode;
    	L->next=NULL;
    	printf("欢迎进入学生信息管理系统！\n"
    		 "1.建立\n"
    		 "2.显示\n"
    		 "3.按姓名查找\n"
    		 "4.按位置查找\n"
    		 "5.插入\n"
    		 "6.删除\n"
    		 "7.退出\n"
    		);
    	while (choose!=7)
    	 {
        
    		 printf("\n选择序号：");
    		 scanf("%d",&choose);
    		 switch(choose)
    		 {
        
    		 case 1:
    			 if(!initlist(L))
    				 printf("建立失败！\n");
    			 else printf("建立成功！\n");
    			 break;
    		 case 2:
    			 if(!displist(L))
    				 printf("显示失败！\n");
    			 else printf("显示成功！\n");
    			 break;
    		 case 3:
    			 if(!seeklist(L))
    				 printf("查找失败！\n");
    			 else printf("查找成功！\n");
    			 break;
    		 case 4:
    			 if(!seek2list(L))
    				 printf("查找失败！\n");
    			 else printf("查找成功！\n");
    			 break;
    		 case 5:
    			 if(!inserlist(L))
    				 printf("插入失败！\n");
    			 else printf("插入成功！\n");
    			 break;
    		 case 6:
    			if(!deletelist(L))
    				 printf("删除失败！\n");
    			 else printf("删除成功！\n");
    			break;
    		 }
    	 }
     }

**四、实验体会**  
通过本次实验，我掌握了定义线性表的链式存储类型，加深了对链式存储结构的理解，进一步巩固和理解了单链表的基本操作，例如建立、查找、插入和删除等等。同时，也体会到了链表在插入、删除操作中的优点及链表中添加头结点的优点：便于首元结点的处理以及空表和非空表的统一处理。