数据结构顺序表及链表实验

向右看齐 2022-09-26 03:31 171阅读 0赞

实验目的 ：

1 、掌握线性表的定义；

2 、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的 顺序表和链表，使其具有如下功能：

(1) 根据指定学生个数，逐个输入学生信息；

(2) 逐个显示学生表中所有学生的相关信息；

(3) 根据姓名进行查找，返回此学生的学号和成绩；

(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；

(5) 给定一个学生信息，插入到表中指定的位置；

(6) 删除指定位置的学生记录；

(7) 统计表中学生个数。

参考信息 ：

**Definition of structure student ：**

typedef struct \{

char no\[8\]; //8 位学号

char name\[20\]; // 姓名

int price; // 成绩

\}Student;

**Definition of sequential list:**

typedef struct \{

Student \*elem; // 指向数据元素的基地址

int length; // 线性表的当前长度

\}SqList  ；

**Definition of linked list ：**

typedef struct LNode\{

Student data; // 数据域

struct LNode \*next; // 指针域

\}LNode,\*LinkList;

实验要求 ：

(1) 程序要添加适当的注释，程序的书写要采用 缩进格式  。

(2) 程序要具在一定的 健壮性，即当输入数据非法时， 程序也能适当地做出反应，如 插入删除时指定的位置不对  等等。

(3) 程序要做到 界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表 根据姓名进行查找的算法和插入算法的流程图 。

(5) 上传源程序到Saike网络教学平台。顺序表的源程序保存为 SqList.c  ，链表的源程序保存为 LinkList.c 。

链表实现：

//链表实现
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    typedef struct {
    	char name[20];	//姓名
    	char nu[8];		//8位学号
    	int price;		//成绩
    } Student;
    typedef struct LNode {
    	Student data;			//数据域
    	struct LNode *next;		//指针域
    } LNode,*LinkList;
    LNode L;
    LinkList q;
    void Input() {
    	printf(" 请输入要录入的学生信息（包括姓名(cstring)，学号（cstring），成绩（int)）个数：");
    	int num,k=0;
    	LinkList p;
    	scanf("%d",&num);
    	while(num--) {
    		p=(LNode *)malloc(sizeof(LNode));
    		printf("请输入第%d个学生的信息：",++k);
    		scanf("%s%s%d",p->data.name,p->data.nu,&p->data.price);
    		p->next=NULL;
    		q=&L;
    		while(q->next!=NULL) {
    			q=q->next;
    			//	printf("---\n");
    		}
    		q->next=p;
    	}
    	printf("录入完毕\n");
    }
    void Output() {
    	q=L.next;
    	printf("姓名	学号	成绩\n");
    	while(q->next!=NULL) {
    		printf("%s	%s	%d\n",q->data.name,q->data.nu,q->data.price);
    		q=q->next;
    	}
    	printf("%s	%s	%d\n",q->data.name,q->data.nu,q->data.price);
    }
    void search() {
    	printf("请输入学生姓名(输入-1结束查询)：");
    	char c[20];
    	int flag=0;
    	q=L.next;
    	while(scanf("%s",c)&&c[0]!='-') {
    		flag=0;
    		while(q->next!=NULL) {
    			if(strcmp(c,q->data.name)==0) {
    				printf("姓名：%s	学号：%s	成绩：%d\n",q->data.name,q->data.nu,q->data.price);
    				flag=1;
    				break;
    			}
    			q=q->next;
    		}
    		if(q->next==NULL&&strcmp(c,q->data.name)==0) {
    			printf("姓名：%s	学号：%s	成绩：%d\n",q->data.name,q->data.nu,q->data.price);
    			flag=1;
    		}
    		if(!flag)
    			printf("不存在该学生的信息\n");
    		printf("请输入学生姓名(输入-1结束查询)：");
    	}
    	printf("查询结束\n");
    }
    void find() {
    	printf("输入要查找第几个学生的信息:");
    	int k,step=0,cnt=0;
    	scanf("%d",&k);
    	q=L.next;
    	while(q->next!=NULL) {
    		step++;
    		if(step==k) {
    			printf("姓名：%s	学号：%s	成绩：%d\n",q->data.name,q->data.nu,q->data.price);
    			cnt=1;
    			break;
    		}
    		q=q->next;
    	}
    	if(step==k-1) {
    		printf("姓名：%s	学号：%s	成绩：%d\n",q->data.name,q->data.nu,q->data.price);
    		cnt=1;
    	}
    	if(!cnt)
    		printf("不存在此学生信息\n");
    }
    void insert() {
    	LinkList p;
    	p=(LNode *)malloc(sizeof(LNode));
    	printf("请输入要插入的学生信息：");
    	scanf("%s%s%d",p->data.name,p->data.nu,&p->data.price);
    	int k,step=0,cnt=0;
    	printf("请输入要插入的第几个位置：");
    	scanf("%d",&k);
    	q=L.next;
    	while(q->next!=NULL) {
    		step++;
    		if(step==k-1) {
    			cnt=1;
    			break;
    		}
    		q=q->next;
    	}
    	if(step==k-1) {
    		p->next=q->next;
    		q->next=p;
    	}
    	if(step==k-2) {
    		p->next=NULL;
    		q->next=p;
    		cnt=1;
    	}
    	if(!cnt) {
    		printf("位置输入过大\n");
    	}
    	printf("插入完毕\n");
    }
    void cutout() {
    	int k,step=0,cnt=0;
    	LinkList p;
    	printf("请输入要删除第几个学生信息：");
    	scanf("%d",&k);
    	q=L.next;
    	while(q->next!=NULL) {
    		step++;
    		if(step==k-1) {
    			cnt=1;
    			break;
    		}
    		q=q->next;
    	}
    	if(step==k-1) {
    		p=q->next;
    		q->next=p->next;
    		free(p);
    	}
    	if(!cnt)
    		printf("位置输入过大\n");
    	printf("删除完毕\n");
    }
    void statistics() {
    	int step=0;
    	q=L.next;
    	while(q->next!=NULL) {
    		step++;
    		q=q->next;
    	}
    	printf("统计表中的学生个数是%d\n",step+1);
    }
    void began() {
    	printf("学生成绩管理系统：\n");
    	printf("********************************************************************************\n");
    	printf("			1.输入学生信息\n");
    	printf("			2.显示学生表中的学生相关信息\n");
    	printf("			3.根据姓名查找学生学号和成绩\n");
    	printf("			4.得到指定位置相应的学生信息\n");
    	printf("			5.插入学生信息\n");
    	printf("			6.删除指定位置的学生记录\n");
    	printf("			7.统计表中的学生个数\n");
    	printf("			8.安全退出\n\n");
    	printf("********************************************************************************\n");
    	printf("请输入要实现的功能编号^.^:");
    }
    int main() {
    	began();
    	int x;
    	while(scanf("%d",&x)&&x!=8) {
    		switch(x) {
    			case 1: {
    				Input();
    				break;
    			}
    			case 2: {
    				Output();
    				break;
    			}
    			case 3: {
    				search();
    				break;
    			}
    			case 4: {
    				find();
    				break;
    			}
    			case 5: {
    				insert();
    				break;
    			}
    			case 6: {
    				cutout();
    				break;
    			}
    			case 7: {
    				statistics();
    				break;
    			}
    		}
    		system("pause");
    		system("cls");
    		began();
    	}
    	printf("安全退出\n");
    	return 0;
    }

顺序表实现：

#include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<malloc.h>
    #include<algorithm>
    using namespace std;
    const int N = 105;
    typedef struct {
    	char name[20];	//姓名
    	char nu[8];		//8位学号
    	int price;		//成绩
    } Student;
    typedef struct {
    	Student *elem;
    	int length;
    } SqList;
    SqList L;
    void build() {
    	L.elem=(Student *)(malloc(sizeof(Student)*N));	//建立线性表
    	L.length=0;
    	if(!L.elem)
    		printf("建立顺序表失败\n");
    }
    void Input() {						//输入
    	int y,k,p=0;
    	printf("请输入要读入的学生信息（包括姓名(cstring)，学号（cstring），成绩（int)） 数目：");
    	scanf("%d",&y);
    	for(int i=0; i<y; i++) {
    		if(i>=100) {
    			printf("内存超限\n");
    			return ;
    		}
    		printf("请输入第%d个学生信息：",++p);
    		scanf("%s%s%d",L.elem[i].name,L.elem[i].nu,&L.elem[i].price);
    		L.length++;
    	}
    	printf("建立学生成绩表完成\n");
    }
    void Output() {						//输出
    	printf("姓名	学号	成绩\n");
    	for(int i=0; i<L.length; i++) {
    		printf("%s	%s	%d\n",L.elem[i].name,L.elem[i].nu,L.elem[i].price);
    	}
    	//printf("按回车键继续\n");
    }
    void search() {				//按姓名查找
    	printf("输入要查找的学生姓名:");
    	char tem[20];
    	scanf("%s",tem);
    	for(int i=0; i<L.length; i++) {
    		if(!strcmp(L.elem[i].name,tem)) {
    			printf("姓名：%s	学号：%s	成绩：%d\n",L.elem[i].name,L.elem[i].nu,L.elem[i].price);
    			return ;
    		}
    	}
    	printf("没有此学生信息\n");
    }
    void find() {			//按位置查找
    	printf("输入要查找第几个学生的信息：");
    	int temp;
    	scanf("%d",&temp);
    	printf("姓名：%s	学号：%s	成绩：%d\n",L.elem[temp-1].name,L.elem[temp-1].nu,L.elem[temp-1].price);
    }
    void insert() {				//插入
    	int num,p=0;
    	Student e;
    	printf("输入你想插入的学生数量：");
    	scanf("%d",&num);
    	if(L.length+num>=100) {
    		printf("存储不够，插入失败\n");
    		return ;
    	}
    	while(num--) {
    		int s;
    		printf("输入要插入的第%d个学生的姓名、学号、成绩：",++p);
    		scanf("%s%s%d",e.name,e.nu,&e.price);
    		printf("输入要插入第几个位置：");
    		scanf("%d",&s);
    		for(int i=L.length; i>s-1; i--) {
    			L.elem[i]=L.elem[i-1];
    		}
    		L.elem[s-1]=e;
    		L.length++;
    	}
    	printf("插入成功\n");
    }
    void cutout() {					//删除
    	int num;
    	printf("输入共删除几个学生信息：");
    	scanf("%d",&num);
    	while(num--) {
    		int s;
    		printf("输入删除第几个学生信息：");
    		scanf("%d",&s);
    		if(s>=L.length) {
    			printf("没有此学生的信息\n");
    			continue;
    		}
    		for(int i=s-1; i<L.length-1; i++) {
    			L.elem[i]=L.elem[i+1];
    		}
    		L.length--;
    	}
    	printf("删除完毕\n");
    }
    void statistics() {				//表中的学生信息个数
    	printf("表中的学生信息个数是:%d\n",L.length);
    }
    void began() {
    	printf("学生成绩管理系统：\n"); 
    	printf("********************************************************************************\n");
    	printf("			1.输入学生信息\n");
    	printf("			2.显示学生表中的学生相关信息\n");
    	printf("			3.根据姓名查找学生学号和成绩\n");
    	printf("			4.得到指定位置相应的学生信息\n");
    	printf("			5.插入学生信息\n");
    	printf("			6.删除指定位置的学生记录\n");
    	printf("			7.统计表中的学生个数\n");
    	printf("			8.安全退出\n\n");
    	printf("********************************************************************************\n");
    	printf("请输入要实现的功能编号^.^:");
    }
    int main() {
    	began();
    	build();
    	int x;
    	while(scanf("%d",&x)&&x!=8) {
    		switch(x) {
    			case 1: {
    				Input();
    				break;
    			}
    			case 2: {
    				Output();
    				break;
    			}
    			case 3: {
    				search();
    				break;
    			}
    			case 4: {
    				find();
    				break;
    			}
    			case 5: {
    				insert();
    				break;
    			}
    			case 6: {
    				cutout();
    				break;
    			}
    			case 7: {
    				statistics();
    				break;
    			}
    		}
    		system("pause");
    		system("cls");
    		began();
    	}
    	printf("退出成功\n");
    	return 0;
    }