一、线性表的主要操作

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;
        }
    }   
}