实验目的：
1、掌握线性表的定义；
2、掌握线性表的基本操作，如建立、查找、插入和删除等。
实验内容：
定义一个包含学生信息（学号，姓名，成绩）的的顺序表和链表，使其具有如下功能：
(1) 根据指定学生个数，逐个输入学生信息；
(2) 逐个显示学生表中所有学生的相关信息；
(3) 根据姓名进行查找，返回此学生的学号和成绩；
(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；
(5) 给定一个学生信息，插入到表中指定的位置；
(6) 删除指定位置的学生记录；
(7) 统计表中学生个数。
顺序表
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status; // 定义函数返回值类型
typedef struct
{
char no[8]; // 8位学号
char name[20]; // 姓名
double price; // 成绩
}student;
typedef student ElemType;
typedef struct
{
ElemType* elem; // 存储空间的基地址
int length; // 当前长度
int listsize;//当前分配的存储空间
}SqList;
Status InitList_Sq(SqList* L) // 构造一个空的顺序表 L
{
L->elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
if (!L->elem) exit(OVERFLOW);//存储空间分配失败
L->length = 0;//空表长度为0
L->listsize = LIST_INIT_SIZE;//初始存储容量
return OK;
} // InitList_Sq
ElemType GetElem(SqList& L, int i) // 访问顺序表，找到 i位置，返回给 e
{
return L.elem[i];
}
int Search(SqList& L, char str[]) // 根据名字查找，返回该同学在顺序表中的编号
{
for (int i = 1; i <= L.length; i++)
{
if (strcmp(L.elem[i].name, str) == 0)
return i;
}
return 0;
}
Status ListInsert(SqList& L, int i, ElemType e) // 在 i位置插入某个学生的信息
{
if ((i < 1) || (i > L.length + 1)) return ERROR;
if (L.length == LIST_INIT_SIZE) return ERROR;
for (int j = L.length; j >= i; j--)
{
L.elem[j + 1] = L.elem[j];
}
L.elem[i] = e;
++L.length;
return OK;
}
Status ListDelete(SqList& L, int i) // 在顺序表中删除 i位置的学生信息
{
if ((i < 1) || (i > L.length)) return ERROR;
for (int j = i; j <= L.length; j++)
{
L.elem[j] = L.elem[j + 1];
}
--L.length;
return OK;
}
void Input(ElemType* e)
{
printf("姓名:"); scanf("%s", e->name);
printf("学号:"); scanf("%s", e->no);
printf("成绩:"); scanf("%lf", &e->price);
printf("输入完成\n\n");
}
void Output(ElemType* e)
{
printf("姓名:%-20s学号:%-10s成绩:%-10.2lf\n\n", e->name, e->no, e->price);
}
int main()
{
SqList L;
ElemType a, b, c, d;
puts("1. 开始输入学生信息");
puts("2. 显示所有学生信息");
puts("3. 输入姓名，查找该学生信息");
puts("4. 显示第几个学生信息");
puts("5. 在指定位置插入学生信息");
puts("6. 在指定位置删除学生信息");
puts("7. 统计学生个数");
puts("8. 退出");
InitList_Sq(&L);
int x, choose;
while (1)
{
puts("请选择:");
scanf("%d", &choose);
if (choose == 8) break;
switch (choose)
{
case 1:
printf("请输入要录入学生的人数（小于100）:");
scanf("%d", &x);
for (int i = 1; i <= x; i++)
{
printf("第%d个学生:\n", i);
Input(&L.elem[i]);
}
L.length = x;
puts("");
break;
case 2:
for (int i = 1; i <= x; i++)
{
a = GetElem(L, i);
Output(&a);
}
break;
case 3:
char s[20];
printf("请输入要查找的学生姓名:");
scanf("%s", s);
if (Search(L, s))
Output(&L.elem[Search(L, s)]);
else
puts("没有这个人！");
puts("");
break;
case 4:
printf("请输入要查询的学生的位置:");
int id1;
scanf("%d", &id1);
b = GetElem(L, id1);
Output(&b);
break;
case 5:
printf("请输入要插入的位置:");
int id2;
scanf("%d", &id2);
printf("请输入学生信息:\n");
Input(&c);
if (ListInsert(L, id2, c))
{
x++;
puts("插入成功");
puts("");
}
else
{
puts("插入失败");
puts("");
}
break;
case 6:
printf("请输入要删除的位置:");
int id3;
scanf("%d", &id3);
if (ListDelete(L, id3))
{
x--;
puts("删除成功");
puts("");
}
else
{
puts("删除失败");
puts("");
}
break;
case 7:
printf("已录入的学生个数为:%d\n\n", L.length);
break;
}
}
printf("\n\n请按任意键退出\n\n\n");
system("pause");
return 0;
}
链表的操作
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; // 定义函数返回值类型
typedef struct
{
char no[8]; //8位学号
char name[20]; //姓名
double price; //成绩
}student;
typedef student ElemType;
typedef struct LNode
{
ElemType data; // 数据域
struct LNode* next; //指针域
}LNode, * LinkList;
Status InitList(LinkList& L) //建立一个带头指针的链表
{
L = (struct LNode*)malloc(sizeof(struct LNode));
L->next = NULL;
return OK;
}
Status GetElem(LinkList L, int i, ElemType& e) // 访问链表，找到 i位置的数据域，返回给 e
{
LinkList p;
p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
++j;
}
if (!p || j > i) return ERROR;
e = p->data;
return OK;
}
Status Search(LNode L, char str[], LinkList& p) // 根据名字查找
{
p = L.next;
while (p)
{
if (strcmp(p->data.name, str) == 0)
return OK;
p = p->next;
}
return ERROR;
}
Status ListInsert(LinkList L, int i, ElemType e) // 在 i个位置插入某个学生的信息
{
LinkList p, s;
p = L;
int j = 0;
while (p && j < i - 1)
{
p = p->next;
++j;
}
if (!p || j > i - 1) return ERROR;
s = (struct LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete(LinkList p, int i) // 删除 i位置的学生信息
{
int j = 0;
while ((p->next) && (j < i - 1))
{
p = p->next;
++j;
}
if (!(p->next) || (j > i - 1)) return ERROR;
LinkList q;
q = p->next;
p->next = q->next;
delete q;
return OK;
}
void Input(ElemType* e)
{
printf("姓名:"); scanf("%s", e->name);
printf("学号:"); scanf("%s", e->no);
printf("成绩:"); scanf("%lf", &e->price);
printf("输入完成\n\n");
}
void Output(ElemType* e)
{
printf("姓名:%-20s学号:%-10s成绩:%-10.2lf\n\n", e->name, e->no, e->price);
}
int main()
{
LNode L;
LinkList p;
ElemType a, b, c, d;
puts("1. 开始输入学生信息");
puts("2. 显示所有学生信息");
puts("3. 输入姓名，查找该学生信息");
puts("4. 显示第几个学生信息");
puts("5. 在指定位置插入学生信息");
puts("6. 在指定位置删除学生信息");
puts("7. 统计学生个数");
puts("8. 退出");
InitList(p);
int x, choose = -1;
while (1)
{
puts("请选择:");
scanf("%d", &choose);
if (choose == 8) break;
switch (choose)
{
case 1:
printf("请输入要录入学生信息的人数:");
scanf("%d", &x);
for (int i = 1; i <= x; i++)
{
printf("第%d个学生:\n", i);
Input(&a);
ListInsert(&L, i, a);
}
break;
case 2:
for (int i = 1; i <= x; i++)
{
GetElem(&L, i, b);
Output(&b);
}
break;
case 3:
char s[20];
printf("请输入要查找的学生姓名:");
scanf("%s", s);
if (Search(L, s, p))
Output(&(p->data));
else
puts("没有这个人！");
puts("");
break;
case 4:
printf("请输入要查询的位置:");
int id1;
scanf("%d", &id1);
GetElem(&L, id1, c);
Output(&c);
break;
case 5:
printf("请输入要插入的位置:");
int id2;
scanf("%d", &id2);
printf("请输入学生信息:\n");
Input(&d);
if (ListInsert(&L, id2, d))
{
x++;
puts("插入成功");
puts("");
}
else
{
puts("插入失败");
puts("");
}
break;
case 6:
printf("请输入要删除的位置:");
int id3;
scanf("%d", &id3);
if (ListDelete(&L, id3))
{
x--;
puts("删除成功");
puts("");
}
else
{
puts("删除失败");
puts("");
}
break;
case 7:
printf("已录入的学生个数为:%d\n\n", x);
break;
}
}
printf("\n\n请按任意键退出\n\n\n");
system("pause");
return 0;
}
