Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

数据结构-栈（栈的C语言实现）_c语言实现修改栈的类型

作者：Cpp五条 | 2024-05-28 03:43:26

踩

c语言实现修改栈的类型

栈

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

一、顺序栈

顺序栈是栈的顺序实现。顺序栈是指利用顺序存储结构实现的栈。采用地址连续的存储空间（数组)依次存储栈中的数据元素，由于入栈和出栈运算都是在栈顶进行，而栈底位置是固定不变的，可以将栈底位置设置在数组空间的起始处；栈顶位置是随入栈和出栈操作而变化的，故需用一个整型变量top来记录当前栈顶元素在数组中的位置。

在顺序栈的操作中可能存在两种溢出。
上溢：

当top>=stacksize-1（stacksize为分配的栈的大小）时，表示系统作为栈用的存储控件已满。如果还有元素要求进栈，则栈溢出，即上溢，这时需要进行栈满处理。

下溢：

当top=-1时，表示系统作为栈用的存储区已空，栈中无任何元素。这时若还要做出栈运算，则发生下溢。

顺序栈的存储结构及宏定义

//定义栈处理的数据类型
typedef int StackElemType;

/*定义栈的最大长度*/
#define STACK_MAX_SIZE 100

/*顺序栈的结构*/
typedef struct stack
{
    //栈顶位置当top=-1表示空栈，top=stack_size-1表示栈满
    int top;
    StackElemType date[STACK_MAX_SIZE];
}Stack,*StackPtr;

//定义状态
typedef enum Status
{
    success, 
    fail, 
    overflow, /*上溢*/
    underflow/*下溢*/
}Status;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

顺序栈的初始化（Init）

/**************************************
*函数名称：Statck_Init(StackPtr s)
*描   述：
*        初始化一个栈
*参   数：
*        StackPtr s 传入需要初始化的栈
*返回值 ：
*        success 成功
*        fail    失败
***************************************/
Status Stack_Init(StackPtr s)
{
    Status outcome = fail;
    StackPtr p = NULL;
    p = (StackPtr)malloc(STACK_MAX_SIZE*sizeof(StackElemType));
    if(p == NULL)
    {
        return outcome;/*空间未申请成功*/
    }
    s->top = -1; 
    outcome = success;
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

顺序栈的入栈操作（Push）

/***************************************************
*函数名称：Stack_Push(StackPtr s,StackElemType elem)
*描   述：
*        顺序栈入栈操作的实现
*参   数：
*        StackPtr s 传入栈
*        StackElemType elem 需要压栈的数据
*返回值 ：
*        success  成功
*        overflow 栈上溢出
****************************************************/
Status Stack_Push(StackPtr s, StackElemType elem)
{
    Status outcome = success;
    if(s->top == STACK_MAX_SIZE -1)
    {
        outcome = overflow;/*栈满，上溢*/
    }
	s -> top++;
    s -> date[s->top] = elem;
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

顺序栈的出栈操作（Pop）

/***************************************************
*函数名称：Stack_Pop(StackPtr s,StackElemType *elem)
*描   述：
*        顺序栈出栈操作的实现
*参   数:
*        StackPtr s 传入栈
*        StackElemType *elem 出栈的数据赋值给*elem
*返回值：
*        success  成功
*        underflow 栈下溢出
****************************************************/
Status Stack_Pop(StackPtr s,StackElemType *elem)
{
    Status outcome = success;
    if(s -> top == -1)
    {
        outcome = underflow;/*栈下溢*/
    }
    else
    {
        *elem = s->date[s->top];
        s -> top--;
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

清除栈（Clear）

/***************************************************
*函数名称：Stack_Clear(StackPtr s)
*描   述：
*        清除栈
*参   数:
*        StackPtr s 传入被清空的栈
*返回值：
*        无
****************************************************/
void Stack_Clear(StackPtr s)
{
    if(s)
    {
        s -> top = -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

判断栈是否为空（Empty）

/***************************************************
*函数名称：Stack_Empty(StackPtr s)
*描   述：
*        判断栈是否为空
*参   数:
*        StackPtr s 传入栈
*返回值：
*        1   空栈
*        0   不为空
****************************************************/
bool Stack_Empty(StackPtr s)
{
    return (s -> top == -1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、链栈

链栈是一种数据存储结构，可以通过单链表的方式来实现，使用链栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

链栈的宏定义及存储结构

#define bool int
/*链栈的大小*/
#define STACK_MAX_SIZE 20

/*定义待处理的数据类型*/
typedef int ElemType;

/*链栈结点的结构*/
typedef struct Stacknode {
    ElemType data;
    struct Stacknode *next;
}Stacknode,*PtrStacknode;

/*栈的类型*/
typedef struct{
    PtrStacknode top;
    int count;
}LinkStack;

/*定义状态*/
typedef enum Statuc{
    success,
    fail,
    error,
    full,
    empty
}Status;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

初始化链栈（Init）

/**************************************
*函数名称：Stack_Init(LinkStack *s)
*描   述：
*        初始化一个链栈
*参   数：
*        LinkStack *s 传入需要初始化的栈
*返回值 ：
*        success 成功
*        fail    失败
*  top       top-1
* -------    -------       -------    ------- 
  |   | |    |   | |  ~~~  |   | |    |   | | 
* -------    -------       -------    -------
*   \_________________  ___________________/
*                     \/ 
*  栈顶              count              栈尾
*注   意：栈顶为链表得第一个元素
***************************************/
Status Stack_Init(LinkStack *s)
{
    Status outcome = fail;
    s ->top = (PtrStacknode)malloc(sizeof(Stacknode));
    if(!s->top)
    {
        return outcome;/*空间申请失败*/
    }
    else
    {
        s ->top = NULL;
        s ->count = 0;
        outcome = success;
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

链栈的压栈操作（Push）

/**************************************
*函数名称：Stack_Push(LinkStack *Stack, ElemType *elem)
*描   述：
*        压栈操作
*参   数：
*        LinkStack *Stack 传入的栈
*        ElemType *elem   待压入的数据
*返回值 ：
*        success   成功
*        fail      失败
***************************************/
Status Stack_Push(LinkStack *Stack, ElemType *elem)
{
    Status outcome = success;
    PtrStacknode s = (PtrStacknode)malloc(sizeof(Stacknode));
    if(s != NULL)
    {
        s ->data = *elem;
        s ->next = Stack ->top;
        Stack ->top = s;
        Stack ->count++;
    }
    else
    {
        outcome = fail;/*压栈操作失败*/
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

链栈的出栈操作（Pop）

/**************************************
*函数名称：Stack_Pop(LinkStack *Stack,ElemType *elem)
*描   述：
*        出栈操作
*参   数：
*        LinkStack *Stack 传入的栈
*        ElemType *elem   出栈的数据保存到*elem
*返回值 ：
*        success   成功
*        empty     空栈无法弹出
***************************************/
Status Stack_Pop(LinkStack *Stack,ElemType *elem)
{
    Status outcome = success;
    if(Stack ->count != 0)
    {
        *elem = Stack ->top ->data;
        Stack ->top = Stack ->top ->next;
        Stack ->count--;
    }
    else
    {
        outcome = empty;/*空栈无法弹出*/
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

判断链栈是否为空（Empty）

/**************************************
*函数名称：Stack_Empty(LinkStack *s)
*描   述：
*        判断栈是否为空
*参   数：
*        LinkStack *s 传入的栈
*返回值 ：
*        1    空栈
*        0    非空
***************************************/
bool Stack_Empty(LinkStack *s)
{
    return (s ->count == 0);    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、两栈共享空间

用一个数组来存储两个栈，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度的n-1处。两个栈如果增加元素，就是两端点向中间延伸

存储结构及宏定义

#define bool int

/*存储空间分配*/
#define STACK_MAX_SIZE 20

#define STACK_ONE 1
#define STACK_TWO 2

/*栈中保存的数据类型*/
typedef int ElemType;

/*两栈共享空间结构*/
typedef struct stack{
    ElemType date[STACK_MAX_SIZE];
    int stack_top1;/*栈1栈顶指针*/
    int stack_top2;/*栈2栈顶指针*/
}DoubleStack,*PtrDoubleStack;

/*定义函数的返回状态*/
typedef enum Status{
    success,
    fail,
    error,
    full,
    empty
}Status;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

初始化一个共享空间的栈（Init）


/**************************************
*函数名称：Stack_Init(PtrDoubleStack s)
*描   述：
*        初始化一个共享空间的栈
*参   数：
*        PtrDoubleStack s 传入需要初始化的栈
*返回值 ：
*        success 成功
*        fail    失败
***************************************/
Status Stack_Init(PtrDoubleStack s)
{
    Status outcome = fail;
    s ->stack_top1 = -1;
    s -> stack_top2 = STACK_MAX_SIZE;
    outcome = success;
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

压栈操作（Push）

/***************************************************
*函数名称：Stack_Push(PtrDoubleStack s,ElemType e,int StackNumber)
*描   述：
*        压栈操作
*参   数:
*        PtrDoubleStack s  传入栈
*        ElemType e        带压入的数据
*        int StackNumber   压入哪个栈
*返回值：
*        fail    失败
*        full    满栈
*        success 成功
*        error   错误
*注  意：
*     top1                      top2
*     --------------  --------------
*     |  |  |  |  |    |  |  |  |  |
*     --------------  --------------
*       0  1  2  3       4  5  6  7  
****************************************************/
Status Stack_Push(PtrDoubleStack s, ElemType *e, int StackNumber)
{
    Status outcome = fail;
    if(s -> stack_top1 + 1 == s -> stack_top2)
    {
        outcome = full;/*栈已满，不能再压入新的数据*/
    }
    else
    {
        if(StackNumber == STACK_ONE)/*压入栈1*/
        {
            s -> date[++s -> stack_top1] = *e;
            outcome = success;
        }
        else if(StackNumber == STACK_TWO)/*压入栈2*/
        {
            s -> date[--s -> stack_top2] = *e;
            outcome = success;
        }
        else
        {
            outcome = error;/*出入的StackNumber错误*/
        }
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

出栈操作（Pop）


/**************************************
*函数名称：Stack_Pop(PtrDoubleStack s, ElemType *elem, int StackNumber)
*描   述：
*        出栈操作
*参   数：
*        PtrDoubleStack s 传入的栈
*        ElemType *elem   出栈的数据赋值给*elem
*        int StackNumber  确定出栈的栈
*返回值 ：
*        success 成功
*        fail    失败
*        error   错误
*        empty   空栈
***************************************/
Status Stack_Pop(PtrDoubleStack s, ElemType *elem, int StackNumber)
{
    Status outcome = error;
    if(s -> stack_top1 == -1 || s -> stack_top2 == STACK_MAX_SIZE)
    {
        outcome = empty;/*空栈无法继续弹出数据*/
    }
    else 
    {
        if(StackNumber == STACK_ONE)
        {
            *elem = s -> date[s -> stack_top1--];
            outcome = success;
        }
        else if(StackNumber == STACK_TWO)
        {
            *elem = s -> date[s -> stack_top2++];
            outcome = success;
        }
        else
        {
            outcome = error;/*出入的StackNumber错误*/
        }
    }
    return outcome;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

清空栈（Clear）

/**************************************
*函数名称：Stack_Clear(PtrDoubleStack s)
*描   述：
*        清空栈
*参   数：
*        PtrDoubleStack s 传入的栈
*返回值 ：
*        fail    失败
*        success 成功
***************************************/
Status Stack_Clear(PtrDoubleStack s)
{
    Status outcome = fail;
    if(s)
    {
        s ->stack_top1 = -1;
        s ->stack_top2 = STACK_MAX_SIZE;
        if(s ->stack_top1 == -1 && s ->stack_top2 == STACK_MAX_SIZE)
        {
            outcome = success;
        }
        else
        {
            outcome = fail;
        }   
    }
    return outcome;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

共享栈的数据长度（Length）

/**************************************
*函数名称：Stack_Length(PtrDoubleStack s)
*描   述：
*        共享栈的数据个数即栈的长度
*参   数：
*        PtrDoubleStack s 传入的栈
*返回值 ：
*        栈的长度
***************************************/
int Stack_Length(PtrDoubleStack s)
{
    return ((s -> stack_top1+1) + (STACK_MAX_SIZE -  s->stack_top2));
}
1
2
3
4
5
6
7
8
9
10
11
12
13

判断共享栈是否为空（Empty）

/**************************************
*函数名称：Stack_Empty(PtrDoubleStack s)
*描   述：
*        判断栈是否为空
*参   数：
*        PtrDoubleStack s 传入的栈
*返回值 ：
*        1    空栈
*        0    非空
***************************************/
bool Stack_Empty(PtrDoubleStack s)
{
    return (s ->stack_top1 == -1 && s ->stack_top2 == STACK_MAX_SIZE);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、利用栈实现进制转换

首先需要初始化栈以及压栈处理

    InitStack(&s);
    printf("请输入二进制数，输入字母q结束:");
    scanf("%c",&c);
    while (c != 'q')
    {
        PushStack(&s,c);
        scanf("%c",&c);
    }
    getchar();/*由于一般是\n结尾，需要将\n从输入的数据中剔除*/
    len = LengthStack(&s);
1
2
3
4
5
6
7
8
9
10

二进制转十进制

这里c-48是由于计算机保存数据为ASICII形式
ASICII

    for(i = 0; i< len; i++)
    {
        PopStack(&s,c);
        sum = sum+(c-48)*pow(2,i);
    }
1
2
3
4
5

二进制转八进制

/*2进制转8进制方法*/
    for(i =0; i< len; i++)
    {
        for(j =0;j < 3; j++)
        {
            PopStack(&s,c);
            sum = sum +(c-48)*pow(2,j);
        }
        if(s.top == s.base)
        {
            break;
        }
        PushStack(&s2,sum+48);
        sum = 0;
    }
    print("转换后的8进制数为：");
    while(s2.top != s2.base)
    {
        PopStack(&s2,c);
        printf("%c",c);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二进制转十六进制

/*2进制转16进制方法*/
    for(i =0; i< len;i++)
    {
        for(j =0; j<4;j++)
        {
            PopStack(&s,c);
            sum = sum+(c-48)*pow(2,j);
        }
        if(s.base == s.top)
        {
            break;
        }
        switch (sum)
        {
        case 10:
                sum = 'A';
            break;
        case 11:
                sum = 'B';
            break;
        case 12:
                sum = 'C';
            break;
        case 13:
                sum = 'D';
            break;
        case 14:
                sum = 'E';
            break;
        case 15:
                sum = 'F';
            break;
        default:
                sum += 48;
            break;
        }
            
        PushStack(&s2,sum);
        sum = 0;
        printf("转换后的16进制数为：0X");
        while (s2.base != s2.top)
        {
            PopStack(&s2,c);
            printf("%c",c);
        }
        printf("H\n");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/635472