一、线性表的主要操作
1）初始化——给线性表相关参数赋初值；
2）求长处——求线性表的元素个数；
3）取元素——取给定位置的元素值；
4）定位——查找给定元素值的位置；
5）插入——在指定位置插入给定的值；
6）删除——删除指定位置的值或给定的值；
7）遍历——从头到尾扫描线性表，做指定的操作；
二、存储结构讨论
优点：
（1）方法简单，各种高级语言中都有数组，容易实现。
（2）存储空间使用紧凑。
（3）顺序表具有按元素序号随机访问的特点。
缺点：
（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率较低。
（2）预先分配空间需按最大空间分配，估计过大，可能会导致顺序表后部大量闲置；预先分配过小。又会造成溢出。
（3）表容量难以扩充。
三、代码实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 6
#define MAXSIZE 5
//定义datatype
typedef struct
{
int sno;
char sname[LEN];
int grade;
} datatype;
//比较datatype，返回0表示相等
int compare(datatype *x,datatype *y)
{
return x->sno-y->sno;
}
//打印datatype
void printDatatype(datatype *x)
{
printf("%d\t%s\t%d\n",x->sno,x->sname,x->grade);
}
//定义顺序表
typedef struct
{
datatype data[MAXSIZE];
int last;
}SeqList;
/*******************线性表的基本操作**************************/
//初始化
SeqList *Init_SeqList()//返回一个结构指针
{
SeqList *L=(SeqList *)malloc(sizeof(SeqList));
if(L)
{
L->last=-1;
}
return L;
}
//销毁
void Destroy_SeqList(SeqList **L)
{
if((*L)!=NULL)
{
free((*L));
(*L)=NULL;
}
}
//求表长
int Length_SeqList(SeqList *L)
{
return L->last+1;
}
//判断是否为空
int isEmpty_SeqList(SeqList *L)
{
if(L->last==-1)
return 1;
}
//查找(按值) 有问题
int Locate_SeqList(SeqList *L,datatype x)
{
int i;
for(i=-1;i<L->last;i++)
{
if(compare(&x,&L->data[i])==0) //没问题，将两个结构传入compare函数中
return i;
}
return -2; //返回查找失败
}
//插入
int Insert_SeqList(SeqList *L,int i,datatype x)
{
int j;
if(L->last==MAXSIZE-1)
printf("表的容量已满！");
if(i<1||i>L->last+2)
printf("所插入的位置不正确");
for(j=L->last;j>=i-1;j--)
L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->last++; //每次操作完毕后都要将last指向最后一个元素
return 1;
}
//删除
int Delete_SeqList(SeqList *L,int i)
{
int ret;
datatype stu;
stu.sno=i;
ret=Locate_SeqList(L,stu);
if(ret!=-2)
{
int j;
free(&(L->data[ret]));
for(j=ret;j<=L->last;j++)
L->data[j]=L->data[j+1];
L->last--;
return 1; //删除成功
}
return 0; //删除失败
}
//更新
int Update_SeqList(SeqList *L,int i,int score)
{
int ret;
datatype stu;
stu.sno=i;
ret=Locate_SeqList(L,stu);
if(ret!=-2)
{
L->data[ret].grade=score;
return 1;
}
else
return 0;
}
/*******************程序的功能函数**************************/
//打印
void Print(SeqList *L)
{
int i;
if(isEmpty_SeqList(L)!=1)
{
printf("学生信息如下：\n");
for(i=-1;i<L->last;i++)
{
printDatatype(&(L->data[i+1]));
}
printf("请输入回车键返回主菜单。");
}
else
printf("暂无信息，请先插入学生再试！");
}
//查找
void Search(SeqList *L)
{
if((isEmpty_SeqList)!=1)
{
datatype x;
int no;
printf("请输入学生的学号：");
scanf("%d",&x.sno);
no=Locate_SeqList(L,x);
if(no==-2)
printf("查找失败！");
else
printDatatype(&L->data[no]);
}
else
printf("查找失败！");
}
//插入
void Insert(SeqList *L)
{
int in,ret;
datatype stu;
printf("请输入要插入学生的学号：");
scanf("%d",&stu.sno);
printf("请输入要插入学生的姓名：");
scanf("%s",stu.sname);
printf("请输入要插入学生的成绩：");
scanf("%d",&stu.grade);
printf("请输入要插入的位置0~%d：",(L->last)+2);
scanf("%d",&in);
ret=Insert_SeqList(L,in,stu);
if(ret==1)
printf("插入成功，输入回车返回主菜单");
else
printf("插入失败！");
}
//删除
void Delete(SeqList *L)
{
if(isEmpty_SeqList(L)!=1)
{
int num,ret;
printf("请输入要删除的学生的学号：");
scanf("%d",&num);
ret=Delete_SeqList(L,num);
if(ret)
printf("删除成功，请输入回车键返回主菜单！");
else
printf("删除失败！");
}
else
printf("本表已空，删除无效！");
}
//更新
void Update(SeqList *L)
{
if(isEmpty_SeqList(L)!=1)
{
int num,score,ret;
printf("请输入要更新学生的学号：");
scanf("%d",&num);
printf("请输入要更新学生的成绩：");
scanf("%d",&score);
ret=Update_SeqList(L,num,score);
if(ret)
printf("更新成功，请输入回车键返回主菜单！");
else
printf("更新失败！");
}
else
printf("本表已空，更新失败！");
}
/*******************main函数**************************/
void printChoice()
{
printf("\n");
printf("\t进行功能选择：\n");
printf("\t1.打印表格\n");
printf("\t2.查找学生\n");
printf("\t3.插入学生\n");
printf("\t4.删除学生\n");
printf("\t5.更新成绩\n");
printf("\t6.退出程序\n");
}
int main()
{
SeqList *L=Init_SeqList();
if(!L)
{
printf("空间分配失败！");
return 0;
}
int choice=-1;
while(1)
{
printChoice();
scanf("%d",&choice);
switch(choice)
{
case 1:
Print(L);
break;
case 2:
Search(L);
break;
case 3:
Insert(L);
break;
case 4:
Delete(L);
break;
case 5:
Update(L);
break;
case 6:
Destroy_SeqList(&L);
break;
default:
printf("输入错误！");
break;
}
}
}
