顺序表的基本运算的实现

代码

//
//// Created by Cyadhy on 2019/11/12.
//
#include<stdio.h>
#include<stdlib.h>

//顺序表的类型定义
#define MAXLEN 100  //存储空间总量
typedef int DataType;
typedef struct  //顺序表存储类型
{
    DataType data[MAXLEN]; //存放顺序表的数组
    int Length; //顺序表长度
} SeqList;
SeqList L;  //定义一个顺序表L


//顺序表初始化
void InitList(SeqList *L) {   //初始化顺序表L函数
    L->Length = 0;    //初始化顺序表为空
}

//顺序表建立
void CreateList(SeqList *L, int n) {   //建立顺序表并输入多个元素函数
    int i;
    printf("请输入%d个整数:", n);
    for (i = 0; i < n; i++)
        scanf("%d", &L->data[i]);
    L->Length = i;    //设线性表的长度为i
}


//查找操作

//1.按位置查找
int GetElem(SeqList *L, int i, DataType *x) {   //获取顺序表第i位中元素函数
    if (i < 1 || i > L->Length)  //当查找位置i不正确
        return 0;
    else {
        *x = L->data[i - 1];  //将顺序表第i个元素赋给指针x所指变量
        return 1;
    }
}

//2.按值查找
int Locate(SeqList *L, DataType x) {   //在顺序表中定位元素x函数
    int i = 0;
    while (i < L->Length && L->data[i] != x)
        i++;
    if (i >= L->Length)
        return 0;
    else
        return i + 1; //返回的是元素位置
}

//插入操作
int InsElem(SeqList *L, int i, DataType x) {   //在顺序表L中在第i位中插入新元素x函数
    int j;
    if (L->Length >= MAXLEN) {
        printf("顺序表已满");
        return -1;  //表满,不能插入
    }
    if (i < 1 || i > L->Length + 1)   //检查给定的插入位置正确性
    {
        printf("插入位置出错");
        return 0;
    }
    if (i == L->Length + 1)  //插入位置为表尾,则不需移动直接插入即可
    {
        L->data[i - 1] = x;
        L->Length++;
        return 1;
    }
    for (j = L->Length - 1; j >= i - 1; j--)     //插入位置为表尾,则插入点后各节点后移
        L->data[j + 1] = L->data[j];
        L->data[i - 1] = x;     //新元素插入
        L->Length++;    //顺序表长度增1
        return 1;   //插入成功,返回
}

//删除操作
int DelElem(SeqList *L, int i, DataType *x) {
    int j;
    if (L->Length == 0) {
        printf("顺序表为空");
        return 0;
    }
    if (i < 1 || i > L->Length) {
        printf("不存在第i个元素");
        return 0;
    }
    *x = L->data[i - 1];
    for (j = 1; j > L->Length; j++)
        L->data[j - 1] = L->data[j];
    L->Length--;
    return 1;
}

//输出元素操作
void DispList(SeqList *L) {
    int i;
    for (int i = 0; i < L->Length; i++) {
        printf("%d", L->data[i]);
    }
}

//显示菜单
void menu() {
    printf("\n                  顺序表各种操作                    ");
    printf("\n================================================== ");
    printf("\n                   1.---建立顺序表                  ");
    printf("\n                   2.---插入操作                    ");
    printf("\n                   3.---删除操作                    ");
    printf("\n                   4.---按位置查找元素               ");
    printf("\n                   5.---按元素值查找其在表中位置      ");
    printf("\n                   6.---求顺序表长度                 ");
    printf("\n                   0.---返回                        ");
    printf("\n=================================================== ");
    printf("\n 请输入菜单号(0-6):");
}

int main()
{
    SeqList L;
    DataType x;
    int n, i, loc;
    char ch1, ch2, a;
    ch1 = 'y';
    while (ch1 == 'y' || ch1 == 'Y') {
        menu();
        scanf("%c", &ch2);
        getchar();
        switch (ch2) {
            case '1':
                InitList(&L);
                printf("输入建立线性表的个数");
                scanf("%d", &n);
                CreateList(&L, n);
                printf("建立的线性表为:");
                DispList(&L);
                break;
            case '2':
                printf("输入要插入的位置:");
                scanf("%d", &i);
                printf("输入要插入的元素:");
                scanf("%d", &x);
                if (InsElem(&L, i, x)) {
                    printf("成功在第%d的位置上插入%d,插入后的线性表为:\n", i, x);
                    DispList(&L);
                } else
                    printf("输入插入的参数错误");
                break;
            case '3':
                printf("输入要删除的元素的位置:");
                scanf("%d", &i);
                if (DelElem(&L, i, &x)) {
                    printf("已成功在第%d的位置删除%d,删除后的线性表为:\n", i, x);
                    DispList(&L);
                } else
                    printf("\n输入删除的参数错误");
                break;
            case '4':
                printf("输入要查看表中元素位置(从1开始):");
                scanf("%d", &i);
                if (GetElem(&L, i, &x))
                    printf("当线性表第%d个元素值为:%d", i, x);
                else
                    printf("输入的位置错误");
                break;
            case '5':
                printf("输入要查找的元素值:");
                scanf("%d", &x);
                loc = Locate(&L, x);
                if (loc)
                    printf("查找元素值为%d的位置为:%d", x, loc);
                else
                    printf("该表中无此元素");
                break;
            case '6':
                printf("当前线性表的长度为:%d", L.Length);
                break;
            case '0':
                ch1 = 'n';
                break;
            default:
                printf("输入有误,请从o--6选择");
        }
        if (ch2 != '0') {
            printf("\n按回车继续,按任意键返回菜单");
            a = getchar();
            if (a != '\xA') {
                getchar();
                ch1 = 'n';
            }
        }
    }
}


栈子系统

代码

/**
Created by Clion && Cyadhy on 2019/11/27/10:11:55
**/
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef int DataType;
typedef struct stacknode
{
    DataType data;
    struct stacknode *next;
} LinkStack;

//初始化链栈函数
LinkStack *InitStack()
{
    LinkStack *S;
    S=NULL;
    return S;
}

//判断栈空函数
int EmptyStack(LinkStack *S)
{
    if(S==NULL)
        return 1;
    else
        return 0;
}

//进栈函数
LinkStack *Push(LinkStack *S, DataType x)
{
    LinkStack *p;
    p=(LinkStack *)malloc(sizeof(LinkStack));
    p->data=x;
    p->next=S;
    S=p;
    return S;
}

//出栈函数
LinkStack *Pop(LinkStack *S, DataType *x)
{
    LinkStack *p;
    if(EmptyStack(S))
    {
        printf("\t栈空,不能出栈");
        return NULL;
    }
    else
    {
        *x=S->data;
        p=S;
        S=S->next;
        free(p);
        return S;
    }
}

//获取栈顶元素函数
int GetTop(LinkStack *S, DataType *x)
{
    if(EmptyStack(S))
    {
        printf("栈空");
        return 0;
    }
    else
    {
        *x=S->data;
        return 1;
    }
}

void ShowStack(LinkStack *S)
{
    LinkStack *p=S;
    if(p==NULL)
        printf("\t栈空");
    else
    {
        printf("从栈顶元素起栈中各元素为:");
        while(p!=NULL)
        {
            printf("%d", p->data);
            p=p->next;
        }
    }
}

void D_B(LinkStack *S, DataType x)
{
    while(x)
    {
        S=Push(S, x%2);
        x/=2;
    }
    printf("转换后的二进制为");
    while(!EmptyStack(S))
    {
        S=Pop(S, &x);
        printf("%d", x);
    }
}

//将中缀表达式转换成后缀表达式
void trans(char *exp, char *postexp)
{
    struct
    {
        char data[MAXSIZE];
        int top;
    }op;
    int i=0;
    op.top=-1;
    while(*exp!='#')
    {
        switch(*exp)
        {
            case '(':
                op.top++;
                op.data[op.top]=*exp;
                exp++;
                break;

            case ')':
                while(op.data[op.top]!='(')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                }
                op.top--;
                exp++;
                break;

            case '+':
            case '-':
                while(op.top!=-1 && op.data[op.top]!='(')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                }
                op.top++;
                op.data[op.top]=*exp;
                exp++;
                break;

            case '*':
            case '/':
                while(op.data[op.top]=='*' || op.data[op.top]=='/')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                }
                op.top++;
                op.data[op.top]=*exp;
                exp++;
                break;

            case ' ':
                break;
            default:
                while(*exp>='0' && *exp<='9')
                {
                    postexp[i++]=*exp;
                    exp++;
                }
                postexp[i++]='#';
        }
    }
    while(op.top!=-1)
    {
        postexp[i++]=op.data[op.top];
        op.top--;
    }
    postexp[i]='\0';
}

//根据后缀表达式求值函数
float compvalue(char *postexp)
{
    struct
    {
        float data[MAXSIZE];
        int top;
    }st;
    float a, b, c, d;
    st.top=-1;
    while(*postexp!='\0')
    {
        switch(*postexp)
        {
            case '+':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b+a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '-':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b-a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '*':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b*a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '/':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                if(a!=0)
                {
                    c=b/a;
                    st.top++;
                    st.data[st.top]=c;
                }
                else
                    printf("\n\t除零错误!\n");
                break;
            default:
                d=0;
                while(*postexp>='0' && *postexp<='9')
                {
                    d=10*d+*postexp-'0';
                    postexp++;
                }
                st.top++;
                st.data[st.top]=d;
                break;
        }
        postexp++;
    }
    return st.data[st.top];
}

//显示菜单函数
void MenuStack()
{
    printf("\n    栈子系统   ");
    printf("\n===============");
    printf("\n    1.初始化栈 ");
    printf("\n    2.入栈操作 ");
    printf("\n    3.出栈操作 ");
    printf("\n    4.求栈顶元素");
    printf("\n    5.显示栈中元素");
    printf("\n    6.十 . 十二进制转换");
    printf("\n    7.表达式转换并求值");
    printf("\n    0.返回       ");
    printf("\n================");
    printf("\n请输入菜单号(0--7):");
}


main()
{
    int i, n, flag;
    LinkStack *S;
    DataType x;
    char ch1, ch2, a;
    char exp[MAXSIZE], postexp[MAXSIZE];
    ch1='y';
    while(ch1=='y' || ch1=='Y')
    {
        MenuStack();
        scanf("%c", &ch2);
        getchar();
        switch (ch2)
        {
            case '1':
                S=InitStack();
                printf("初始化完成");
                break;
            case '2':
                printf("请输入要入栈的元素个数:");
                scanf("%d", &n);
                printf("请输入%d个整数进行入栈:",n);
                for (int i = 0; i < n; i++)
                {
                    scanf("%d", &x);
                    S=Push(S, x);
                }
                printf("入栈成功");
                break;
            case '3':
                printf("请输入要出栈的元素个数:");
                scanf("%d", &n);
                printf("出栈的元素为:");
                for(i=0; i<n; i++)
                {
                    S=Pop(S, &x);
                    if(S!=NULL)
                        printf("%5d", x);
                }
                break;
            case '4':
                if(flag=GetTop(S, &x))
                    printf("当前栈顶元素值为: %d", x);
                break;
            case '5':
                ShowStack(S);
                break;
            case '6':
                S=InitStack();
                printf("请输入十进制正整数:");
                scanf("%d", &x);
                D_B(S, x);
                break;
            case '7':
                printf("请输入表达式(只有+ - * / 四种运算符),以 # 结束:");
                scanf("%s", &exp);
                trans(exp, postexp);
                printf("则该表达式的中缀表达式为: %s\n", exp);
                printf("转换之后的后缀表达式为(每个操数作用 # 分隔): %s\n", postexp);
                printf("表达式的值为: %0.2f\n", compvalue(postexp));
                break;
            case '0':
                ch1='n';
                break;
            default:
                printf("输入有误,请输入0--5进行选择!");
        }
        if(ch2!='0')
        {
            printf("\n按回车继续,按任意键返回主菜单!\n");
            a=getchar();
            if(a!='\xA')
            {
                getchar();
                ch1='n';
            }
        }
    }
}


线性表子系统

代码

/**
Created by Clion && Cyadhy on 2019/11/26/10:06:18
**/
//线性表子系统
#include<stdio.h>
#include<malloc.h>
typedef int DateType;   //定义DataType为int类型
typedef struct linknode     //单链表存储类型
{
    DateType data;      //定义结点的数据域
    struct linknode *next;  //定义结点的指针域
}LinkList;

//初始化链表
LinkList *InitList()
{
    LinkList *head;
    head=(LinkList *)malloc(sizeof(LinkList));  //动态分配一个结点空间
    head->next=NULL;
    return head;    //头指针L指针域为空,表示空链表
}

//头插法建立链表函数
void CreateListH(LinkList *head, int n)
{
    LinkList *s;
    int i;
    printf("请输入%d个整数:", n);
    for(i=0; i<n; i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList));     //生成新结点
        scanf("%d",&s->data);   //读入新结点的数据域
        s->next=head->next;     //将新结点的指针域存放头结点的指针域
        head->next=s;   //将新结点插入头结点之后
    }
    printf("建立线性表成功");
}

//尾插法建立链表函数
void CreateListL(LinkList *head, int n)
{
    LinkList *s, *last;
    int i;
    last=head;      //last始终指向尾结点,开始时指向头结点
    printf("请输入%d个整数", n);
    for(i=0; i<n; i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList));     //生成新结点
        scanf("%d", &s->data);      //读入新结点的数据域
        s->next=NULL;   //将新结点插入表尾
        last->next=s;   //将last指针指向表尾结点
        last=s;
    }
    printf("建立链表操作成功");
}

//求链表长度函数
int LengthList(LinkList *head)
{
    LinkList *p=head->next;
    int j=0;
    while(p!=NULL)  //当p不指向表尾时
    {
        p=p->next;
        j++;
    }
    return j;
}

//链表中建立查找值为x的元素位置
void Locate(LinkList *head, DateType x)
{
    int j=1;    //计数器
    LinkList *p;
    p=head->next;
    while(p!=NULL && p->data!=x)    //查找及定位
    {
        p=p->next;
        j++;
    }
    if(p!=NULL)
        printf("在表的第%d位找到值为%d的结点", j, x);
    else
        printf("未找到%d结点", x);
}

//链表中按位置查找元素
void SearchList(LinkList *head, int i)
{
    LinkList *p;
    int j=0;
    p=head;     //*p指向链表的头结点
    if(i>LengthList(head))
        printf("位置错误,链表中没有该位置");
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(j==i)    //判断与给定的序号是否相等
        printf("在第%d位置上插入的元素为%d",i, p->data);
}

//按位置插入元素函数
void InsList(LinkList *head, int i, DateType x)
{
    int j=0;
    LinkList *p, *s;
    p=head;
    while(p->next!=NULL && j<i-1)   //定位插入点
    {
        p=p->next;
        j++;
    }
    if(p!=NULL)     //*p不为空则将新结点插入到p后
    {
        s=(LinkList *)malloc(sizeof(LinkList));     //生成新节点s
        s->data=x;  //将数据x放入新节点的数据域
        s->next=p->next;    //将新节s点的指针域与p结点后面元素相连
        p->next=s;  //将p与新结点s链接
        printf("插入元素成功");
    }
    else
        printf("插入元素失败");
}

//按位置删除链表中元素函数
void DelList(LinkList *head, int i)
{
    int j=0;
    DateType x;
    LinkList *p=head, *s;
    while(p->next!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p->next!=NULL && j==i-1)
    {
        s=p->next;  //q为要删除的结点
        x=s->data;  //将要删除的数据放入指针x中
        p->next=s->next;    //将p结点的指针域q结点后面元素相连
        free(s);
        printf("删除第%d位上的元素%d成功",i, x);
    }
    else
    printf("删除结点位置错误,删除失败");
}

//显示输出链表函数
void DispList(LinkList *head)
{
    LinkList *p;
    p=head->next;
    while(p!=NULL)
    {
        printf("%5d", p->data);
        p=p->next;
    }
}

//显示菜单子函数
void MenuLine()
{
    printf("\n    线性表子系统");
    printf("\n=================");
    printf("\n   1.建立      ");
    printf("\n   2.插入      ");
    printf("\n   3.删除      ");
    printf("\n   4.按位置查找 ");
    printf("\n   5.按元素查找 ");
    printf("\n   6.求表长     ");
    printf("\n   0.返回       ");
    printf("\n===============\n");
    printf("请输入菜单号(0--6):");
}

main()
{
    LinkList *head;
    DateType x;
    int i, n;
    char ch1, ch2, a;
    ch1='y';
    while(ch1=='y' || ch1=='Y')
    {
        MenuLine();
        scanf("%c", &ch2);
        getchar();
        switch (ch2)
        {
            case '1':
                head=InitList();
                printf("请输入要建立的线性表的长度:");
                scanf("%d", &n);
                CreateListL(head, n);
                printf("建立后的线性表为:\n");
                DispList(head);
                break;
            case '2':
                printf("请输入要插入的元素位置:");
                scanf("%d", &i);
                getchar();
                printf("请输入要插入的元素值:");
                scanf("%d", &x);
                InsList(head, i, x);
                printf("插入元素%d后的线性表为:\n",x);
                DispList(head);
                break;
            case '3':
                printf("请输入要删除的元素位置");
                scanf("%d", i);
                DelList(head,i);
                printf("删除第%d位的元素后的线性表为:\n", i);
                DispList(head);
                break;
            case '4':
                printf("请输入查找的元素位置(大于等于1的整数)");
                scanf("%d", &i);
                SearchList(head, i);
                break;
            case '5':
                printf("请输入查找的整数:");
                scanf("%d", &x);
                Locate(head, x);
                break;
            case '6':
                printf("该线性表长度为%d!", LengthList(head));
                break;
            case '0':
                ch1='n';
                break;
            default:
                printf("输入有误,请从0--9进行选择");
        }
        if(ch2!='0')
        {
            printf("\n按回车继续,按任意键返回主菜单!");
            a=getchar();
            if(a!='\xA')
            {
                getchar();
                ch1='n';
            }
        }
    }
}


队列子系统

代码

/**
Created by Clion && Cyadhy on 2019/11/27/21:03:01
**/
//队列子系统
#include <stdio.h>
#include <malloc.h>
typedef int DataType;   //定义DataType为int类型
typedef struct qnode    //链队列存储类型
{
    DataType data;      //定义结点数据域
    struct qnode *next;     //定义结点指针域
}LinkListQ;
typedef  struct
{
    LinkListQ *front, *rear;    //定义队列对头指针和对尾指针
}LinkQueue;     //链队列的指针类型

//初始化链队列函数
LinkQueue *InitQueue()
{
    LinkQueue *Q;
    LinkListQ *p;
    Q=(LinkQueue *)malloc(sizeof(LinkQueue));   //建立链队列头指针所指结点
    p=(LinkListQ *)malloc(sizeof(LinkListQ));   //建立链队列的头结点
    Q->front=p;     //Q指针所指的front指针指向p
    Q->rear=p;      //Q指针所指的rear指针指向p
    return Q;
}

//判断队空函数
int EmptyQueue(LinkQueue *Q)    //链队为空
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}

//入队函数
int InQueue(LinkQueue *Q, DataType x)
{
    LinkListQ *p;
    p=(LinkListQ *)malloc(sizeof(LinkListQ));   //生成新节点
    p->data=x;      //将x存入新结点的数据域
    p->next=NULL;
    Q->rear->next=p;    //将新结点插入链队之后
    Q->rear=p;  //队尾指针指向队尾元素
}

//出队函数
int DeQueue(LinkQueue *Q, DataType *x)
{
    LinkListQ *p;
    if(EmptyQueue(Q))   //调用EmptyQueue(Q),判断队列是否为空
    {
        printf("队空,不能出队元素!");
        return 0;
    }
    else    //队不为空
    {
        p=Q->front->next;   //p指向对头元素
        *x=p->data;     //对头元素取出赋给x
        Q->front->next=p->next;     //对头指针的指针域存放新对头元素的地址
        if(p->next==NULL)   // 队列中只含有一个元素出队
            Q->rear=Q->front;   //出队后队尾指针指向队头指针,此时队空
        free(p);    //释放原队头结点空间
        return 1;
    }
}

//获取对头元素函数
int GetFront(LinkQueue *Q, DataType *x)
{
    if(EmptyQueue(Q))   //调用判空函数EmptyQueue(Q),判断队列是否为空
    {
        printf("对空,无对头元素");
        return 0;
    }
    else    //队列不为空
    {
        *x=Q->front->next->data;    //队头元素赋给变量x
        return 1;
    }
}

//显示队中元素
void ShowQueue(LinkQueue *Q)
{
    LinkListQ *p=Q->front->next;
    if(p==NULL)
        printf("队列为空,无元素");
    else
    {
        printf("从队列元素起栈中各元素为:");
        while(p!=NULL)
        {
            printf("%5d", p->data);
            p=p->next;
        }
    }
}

//显示菜单子函数
void MenuQueue()
{
    printf("\n         队列子系统");
    printf("\n===================");
    printf("\n     1.初始化队列  ");
    printf("\n     2.入队操作    ");
    printf("\n     3.出队操作    ");
    printf("\n     4.求对头元素  ");
    printf("\n     5.显示队中所有元素");
    printf("\n     0.返回        ");
    printf("\n==================");
    printf("\n请输入菜单号(0--5):");
}

int main()
{
    int i, n, flag;
    LinkQueue *Q;
    DataType  x;
    char ch1, ch2, a;
    ch1='y';
    while(ch1=='y' || ch1=='Y')
    {
        MenuQueue();
        scanf("%c", &ch2);
        getchar();
        switch(ch2)
        {
            case '1':
                Q=InitQueue();
                printf("队列初始化完成!");
                break;
            case '2':
                printf("请输入要入队的元素个数为:");
                scanf("%d", &n);
                printf("请输入%d个整数进行入队:", n);
                for(i=0; i<n; i++)
                {
                    scanf("%d", &x);
                    InQueue(Q, x);
                }
                printf("入队操作完成");
                break;
            case '3':
                printf("请输入要出队的元素个数:");
                scanf("%d", &n);
                printf("出队的元素顺序为:");
                for(i=0; i<n; i++)
                {
                    flag=DeQueue(Q, &x);
                    printf("%5d", x);
                }
                if(flag==1)
                    printf("\n出栈操作成功");
                else
                    printf("出栈操作失败");
                break;
            case '4':
                if(flag=GetFront(Q, &x))
                    printf("当前队头元素值为: %d", x);
                break;
            case '5':
                ShowQueue(Q);
                break;
            case '0':
                ch1='n';
                break;
            default:
                printf("输入有误,请从0--4进行选择!");
        }
        if(ch2!='0')
        {
            printf("\n按回车键继续,按任意键返回主菜单!");
            a=getchar();
            if(a!='\xA')
            {
                getchar();
                ch1='n';
            }
        }
    }
}


Last modification:March 16th, 2020 at 02:45 am
如果觉得我的文章对你有用,请随意赞赏或点击页内广告。