线性表C代码实现

发布于 2021-09-26  452 次阅读


未完成版本

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 0
#define OVERFLOW -2
#define MAXSIZE 20
typedef int Status;
typedef char ElemType;
typedef struct {    
    ElemType *data;
    int length;
}SqList;
Status InitList_Sq(SqList &L);      //初始化线性表L 
void DestroyList(SqList &L);        //销毁线性表L
void ClearList(SqList &L);          //清空线性表L
int GetLength(SqList &L);           //求线性表L的长度
int IsEmpty(SqList &L);             //判断线性表L是否为空 
int GetElem(SqList &L,int i,ElemType &e);   //顺序表的取值 
int LocateElem(SqList &L,ElemType e);       //顺序表的查找 
Status ListInsert_Sq(SqList &L,int i,ElemType e);   //顺序表的插入 
Status ListDelete_Sq(SqList &L,int i);
int main(void)
{
    SqList Q;
    InitList_Sq(Q);
    ElemType c;
    scanf("%d",&Q.length);
    printf("length = %d\n",GetLength(Q));
    int i =0;
    int x = Q.length;
    while(x>0)
    {
    gets(Q.data);
    i++;
    x--;
    }
    if(GetElem(Q,3,c))
        printf("%c",c);

    return 0;
}
Status InitList_Sq(SqList &L)
{
    L.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));    //构造一个空的顺序表L
    if(!L.data) 
        exit(OVERFLOW);
    L.length = 0;
    return OK; 
}
void DestroyList(SqList &L)
{
    if(L.data)
        delete L.data;          //释放存储空间 
} 
int GetLength(SqList &L)        //获得线性表长度 
{
    return (L.length);
}
int IsEmpty(SqList &L)          //判断线性表是否为空 
{
    if(L.length ==0)
        return 1;
    else 
        return 0;
}
int GetElem(SqList &L,int i,ElemType &e)    //根据位置i取值 
{
    if(i<1||i>L.length)
        return ERROR;
    e = L.data[i-1];
    return OK;
}
int LocateElem(SqList &L,ElemType e)
{
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i] == e)
            return i+1;
    return 0; 
}
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
    int j;
    if(i<1||i>L.length+1)
        return ERROR;
    for(j=L.length-1;j>=i-1;j--)
        L.data[j+1] = L.data[j];
    L.data[i-1] = e;                //将新元素放入第i个位置
    L.length++;
    return OK; 
}
Status ListDelete_Sq(SqList &L,int i)
{
    int j;
    if((i<1)||(i>L.length))
        return ERROR;
    L.data[j-1] = L.data[j];
    L.length--;
    return OK;
}

改进后的版本

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define STARS   "**************************"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 0
#define OVERFLOW -2
#define MAXSIZE 20
#define QUIT 10

typedef int Status;
typedef char ElemType;
typedef struct {    
    ElemType *data;
    int length;
}SqList;
Status InitList_Sq(SqList &L);      //初始化线性表L 
void DestroyList(SqList &L);        //销毁线性表L
void ClearList(SqList &L);          //清空线性表L
int GetLength(SqList &L);           //求线性表L的长度
int IsEmpty(SqList &L);             //判断线性表L是否为空 
int GetElem(SqList &L,int i,ElemType e);    //顺序表的取值 
int LocateElem(SqList &L,ElemType e);       //顺序表的查找 
Status ListInsert_Sq(SqList &L,int i,ElemType e);   //顺序表的插入 
Status ListDelete_Sq(SqList &L,int i);
int menu(void);
char *s_gets(char *st,int n);

int main(void)
{
    int code;
    SqList Q;
    Q.length = 0;
    ElemType e;
    int j;
    while((code = menu())!=QUIT)
    {
        switch(code)
        {
            case 1:
            if (InitList_Sq(Q))
                printf("Init.. \n");
                printf("输入你你要添加的线性表长度L(0-20):\n");
                scanf("%d",&Q.length); 
                char a;
                a = getchar();
                putchar(a);
                printf("设置...完成! \n"
                "现在输入你要添加的各个元素:\n");
                int i;
                for(i = 0; i<Q.length;i++)
                {
                    s_gets(&Q.data[i],4);
                }
                break;
            case 2:
                DestroyList(Q);
                printf("...销毁线性表成功!\n");
                break;
            case 3:
                ClearList(Q);
                printf("...清空线性表成功!\n"); 
                break;
            case 4:
                printf("线性表长度为%d\n",Q.length);
                break; 
            case 5:
                if(IsEmpty(Q))
                    printf("..线性表为空\n");
                else
                    printf("..线性表非空\n"); 
                break;
            case 6:
                printf("你要检查:"); 
                scanf("%d",&i); 
                if(GetElem(Q,i,e))

                    printf("...检查成功\n");
                else
                    printf("...检查失败\n");
                break;
            case 7:
                ElemType text;
                printf("请输入你要查找的元素:\n");
                int d;
                a = getchar();
                putchar(a);
                if((scanf("%c",&text)) == 1 && (d = LocateElem(Q,text))>0)
                    printf("查找到该元素为第%d个元素.\n",d);
                else
                    printf("...未找到该元素%c",text);
                break;
            case 8:
                a = getchar();
                putchar(a);
                printf("输入你要插入的元素:\n");
                scanf("%c",&e);
                a = getchar();
                putchar(a);
                printf("输入你要插入的位置(1-list.length+1):\n");
                scanf("%d",&i); 
                ListInsert_Sq(Q,i,e);
                printf("插入后的各个元素是:\n");
                for(j =0;j<Q.length;j++)
                    {
                        printf("%c\n",Q.data[j]);
                    }
                break;
            case 9:
                a = getchar();
                putchar(a);
                printf("输入你要删除的位置(1-list.length):\n");
                scanf("%d",&i); 
                ListDelete_Sq(Q,i);
                printf("删除后的各个元素是:\n");
                for(j =0;j<Q.length;j++)
                    {
                        printf("%c\n",Q.data[j]);
                    }
                break;
            default:
                printf("Done!");
                break;
        }
    }
    return 0;
}
Status InitList_Sq(SqList &L)
{
    L.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));    //构造一个空的顺序表L
    if(!L.data) 
        exit(OVERFLOW);
    L.length = 0;
    return OK; 
}
void DestroyList(SqList &L)
{
    if(L.data)
     free(L.data);          //释放存储空间 
} 
void ClearList(SqList &L)   //清空线性表L
{
    L.length = 0;
}
int GetLength(SqList &L)        //获得线性表长度 
{
    return (L.length);
}
int IsEmpty(SqList &L)          //判断线性表是否为空 
{
    if(L.length == 0)
        return 1;
    else 
        return 0;
}
int GetElem(SqList &L,int i,ElemType e) //根据位置i取值 
{
    if(i<1 || i>L.length)
        return ERROR;
    else
        e = L.data[i-1];
        printf("你要检查线性表第%d个元素是%c\n",i,e);
    return OK;
}
int LocateElem(SqList &L,ElemType e)        //查找元素 
{
    int i;
    for(i=0;i<L.length;i++)
        {
            if(L.data[i] == e)
            {
                    return i+1;
            }
        }
                return 0; 

}
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
    int j;
    if(i<1||i>L.length+1)
        return ERROR;
    for(j=L.length-1;j>=i-1;j--)
        L.data[j+1] = L.data[j];
    L.data[i-1] = e;                //将新元素放入第i个位置
    L.length++;
    return OK; 
}
Status ListDelete_Sq(SqList &L,int i)
{
    int j;
    if((i<1)||(i>L.length))
        return ERROR;
    for(j=i;j<L.length+1;j++)
        L.data[j-1] = L.data[j];
    L.length--;
    return OK;
}
int menu(void)
{
    SqList A;
    int code;
    printf("\n%s%s\n",STARS,STARS);
    printf("请选择操作:\n1.初始化线性表L,并且插入各个元素\n"
    "2.销毁线性表L\n"
    "3.清空线性表L\n"
    "4.求线性表L的长度\n"
    "5.判断线性表L是否为空\n"
    "6.顺序表的取值\n"
    "7.顺序表的查找\n"
    "8.顺序表的插入\n"
    "9.顺序表的删除\n"
    "10:退出\n");
    printf("\n%s%s\n",STARS,STARS);
    int status2;
    while((status2 = scanf("%d",&code))!=1||(code<1||code>10))
    {
        if(status2!=1)
            scanf("%*s");         //处理非整数输入
        printf("Enter an integer from 1 to 9 or 'q',please.\n");

    }
    return code;
}
char *s_gets(char *st,int n)
{
    char *ret_val;
    char *find;

    ret_val = fgets(st,n,stdin);
    if(ret_val)
    {
        find = strchr(st,'\n');
        if(find)
            *find = '\0';
        else
            while(getchar()!='\n')
                continue;
    }
    return ret_val;
}

更改其中scanf()输入后回车的消除以及一些小BUG

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define STARS   "**************************"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 0
#define OVERFLOW -2
#define MAXSIZE 20
#define QUIT 10

typedef int Status;
typedef char ElemType;
typedef struct {    
    ElemType *data;
    int length;
}SqList;
Status InitList_Sq(SqList &L);      //初始化线性表L 
void DestroyList(SqList &L);        //销毁线性表L
void ClearList(SqList &L);          //清空线性表L
int GetLength(SqList &L);           //求线性表L的长度
int IsEmpty(SqList &L);             //判断线性表L是否为空 
int GetElem(SqList &L,int i,ElemType e);    //顺序表的取值 
int LocateElem(SqList &L,ElemType e);       //顺序表的查找 
Status ListInsert_Sq(SqList &L,int i,ElemType e);   //顺序表的插入 
Status ListDelete_Sq(SqList &L,int i);
int menu(void);
char *s_gets(char *st,int n);

int main(void)
{
    int code;
    SqList Q;
    Q.length = 0;
    ElemType e;
    int j;
    while((code = menu())!=QUIT)
    {
        switch(code)
        {
            case 1:
            if (InitList_Sq(Q))
                {printf("Init.. \n");
                printf("输入你你要添加的线性表长度L(0-20):\n");
                scanf("%d",&Q.length); 
                while(getchar()!='\n')
                    continue;
                printf("设置...完成! \n"
                "现在输入你要添加的各个元素:\n");
                int i;
                for(i = 0; i<Q.length;i++)
                {
                    s_gets(&Q.data[i],4);
                }
                }
                else
                {
                    printf("初始化失败!");
                 } 
                break;
            case 2:
                DestroyList(Q);
                printf("...销毁线性表成功!\n");
                break;
            case 3:
                ClearList(Q);
                printf("...清空线性表成功!\n"); 
                break;
            case 4:
                printf("线性表长度为%d\n",Q.length);
                break; 
            case 5:
                if(IsEmpty(Q))
                    printf("..线性表为空\n");
                else
                    printf("..线性表非空\n"); 
                break;
            case 6:
                printf("你要检查:"); 
                int i;
                scanf("%d",&i); 
                if(GetElem(Q,i,e))

                    printf("...检查成功\n");
                else
                    printf("...检查失败\n");
                break;
            case 7:
                ElemType text;
                printf("请输入你要查找的元素:\n");
                int d;
                char a;
                a = getchar();
                putchar(a);
                if((scanf("%c",&text)) == 1 && (d = LocateElem(Q,text))>0)
                    printf("查找到该元素为第%d个元素.\n",d);
                else
                    printf("...未找到该元素%c",text);
                break;
            case 8:
                while(getchar()!='\n')
                            continue;
                printf("输入你要插入的元素:\n");
                scanf("%c",&e);
                while(getchar()!='\n')
                            continue;
                printf("输入你要插入的位置(1-list.length+1):\n");
                scanf("%d",&i); 
                ListInsert_Sq(Q,i,e);
                printf("插入后的各个元素是:\n");
                for(j =0;j<Q.length;j++)
                    {
                        printf("%c\n",Q.data[j]);
                    }
                break;
            case 9:
                while(getchar()!='\n')
                    continue;
                printf("输入你要删除的位置(1-list.length):\n");
                scanf("%d",&i); 
                ListDelete_Sq(Q,i);
                printf("删除后的各个元素是:\n");
                for(j =0;j<Q.length;j++)
                    {
                        printf("%c\n",Q.data[j]);
                    }
                break;
            default:
                printf("Done!");
                break;
        }
    }
    return 0;
}
Status InitList_Sq(SqList &L)
{
    L.data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));    //构造一个空的顺序表L
    if(!L.data) 
        exit(OVERFLOW);
    L.length = 0;
    return OK; 
}
void DestroyList(SqList &L)
{
    if(L.data)
     free(L.data);          //释放存储空间 
} 
void ClearList(SqList &L)   //清空线性表L
{
    L.length = 0;
}
int GetLength(SqList &L)        //获得线性表长度 
{
    return (L.length);
}
int IsEmpty(SqList &L)          //判断线性表是否为空 
{
    if(L.length == 0)
        return 1;
    else 
        return 0;
}
int GetElem(SqList &L,int i,ElemType e) //根据位置i取值 
{
    if(i<1 || i>L.length)
        return ERROR;
    else
        e = L.data[i-1];
        printf("你要检查线性表第%d个元素是%c\n",i,e);
    return OK;
}
int LocateElem(SqList &L,ElemType e)        //查找元素 
{
    int i;
    for(i=0;i<L.length;i++)
        {
            if(L.data[i] == e)
            {
                    return i+1;
            }
        }
                return 0; 

}
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
    int j;
    if(i<1||i>L.length+1)
        return ERROR;
    for(j=L.length-1;j>=i-1;j--)
        L.data[j+1] = L.data[j];
    L.data[i-1] = e;                //将新元素放入第i个位置
    L.length++;
    return OK; 
}
Status ListDelete_Sq(SqList &L,int i)
{
    int j;
    if((i<1)||(i>L.length))
        return ERROR;
    for(j=i;j<L.length+1;j++)
        L.data[j-1] = L.data[j];
    L.length--;
    return OK;
}
int menu(void)
{
    SqList A;
    int code;
    printf("\n%s%s\n",STARS,STARS);
    printf("请选择操作:\n1.初始化线性表L,并且插入各个元素\n"
    "2.销毁线性表L\n"
    "3.清空线性表L\n"
    "4.求线性表L的长度\n"
    "5.判断线性表L是否为空\n"
    "6.顺序表的取值\n"
    "7.顺序表的查找\n"
    "8.顺序表的插入\n"
    "9.顺序表的删除\n"
    "10:退出\n");
    printf("\n%s%s\n",STARS,STARS);
    int status2;
    while((status2 = scanf("%d",&code))!=1||(code<1||code>10))
    {
        if(status2!=1)
            scanf("%*s");         //处理非整数输入
        printf("Enter an integer from 1 to 9 or 'q',please.\n");

    }
    return code;
}
char *s_gets(char *st,int n)
{
    char *ret_val;
    char *find;

    ret_val = fgets(st,n,stdin);
    if(ret_val)
    {
        find = strchr(st,'\n');
        if(find)
            *find = '\0';
        else
            while(getchar()!='\n')
                continue;
    }
    return ret_val;
}

擦肩而过的概率