欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

栈和线性表的简单应用-数制转换

程序员文章站 2022-06-03 15:22:11
栈结构具有后进先出的特点,是程序设计中的有用工具 我们先来看看进制转换的过程 如图: 可以看出 整数部分符合后进先出的特点,可以应用栈结构 小数部分先进先出,可以应用线性表 栈的头文件 sqstack.h 线性表的头文件 sqlist.h 源代码: 合理的使用数据结构可以使代码跟易读,易懂。栈的引入 ......

  栈结构具有后进先出的特点,是程序设计中的有用工具

我们先来看看进制转换的过程 如图:

栈和线性表的简单应用-数制转换

可以看出 整数部分符合后进先出的特点,可以应用栈结构

小数部分先进先出,可以应用线性表

   栈的头文件 sqstack.h 

 

 1 #pragma once
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #define stack_init_size 100//储存空间初始分配量
 5 #define stackincrement  10//存储空间分配增量
 6 #define ok 1
 7 #define error 0
 8 typedef int stacktype; //栈元素类型
 9 
10 typedef struct {
11     stacktype *base;   //在构造之前和销毁之后,base的值为null
12     stacktype *top;    //栈顶指针
13     int stacksize;     //当前已分配的存储空间,以元素为单位
14 }sqstack; //顺序栈
15 
16 //栈的初始化
17 int initstack(sqstack *p) {
18 
19 
20     p->base = (stacktype*)malloc(stack_init_size * sizeof(stacktype));
21     if (p->base == null)  return error;  //内存分配失败
22     p->top = p->base;     //栈顶与栈底相同表示一个空栈
23     p->stacksize = stack_init_size;
24     return ok;
25 
26 }
27 //判断栈是否为空
28 int emptystack(sqstack *p) {
29     //若为空栈 则返回ok,否则返回error
30     if (p->top == p->base) return ok;
31     else return error;
32 }
33 //顺序栈的压入
34 int push(sqstack *p, stacktype e) {
35     //插入元素e为新的栈顶元素
36     if ((p->top - p->base) >= p->stacksize)   //栈满,追加储存空间
37     {
38         p->base = (stacktype*)realloc(p->base, (p->stacksize + stackincrement) * sizeof(stacktype));
39         if (p->base == null)   return error;// 储存空间分配失败
40         p->top = p->base + p->stacksize;   
41         p->stacksize += stackincrement;
42     }
43     *(p->top) = e;
44     (p->top)++;
45     return ok;
46 }
47 // 顺序栈的弹出     
48 int pop(sqstack *p, stacktype *e) {
49     //若栈不空,则删除p的栈顶元素,用e返回其值
50     if (p->top == p->base) return error;
51     --(p->top);
52     *e = *(p->top);
53     return ok;
54 
55 
56 }
57 //顺序栈的销毁
58 int destroystack(sqstack *p) {
59     //释放栈底空间并置空
60     free(p->base);
61     p->base = null;
62     p->top = null;
63     p->stacksize = 0;
64 
65     return ok;
66 }

  线性表的头文件 sqlist.h

#pragma once
//顺序线性表
#include <stdio.h>
#include <stdlib.h>
#define list_init_size 100 //线性表储存空间的初始分配量
#define listincrement 10  //线性表储存空间的分配增量
#define ok 1
#define error 0
typedef double elemtype;
typedef struct {
    elemtype *elem;  //储存空间基地址
    int length;        //当前长度
    int listsize;   //当前分配的储存容量(以sizeof(elemtype))为单位
}sqlist;
//顺序表的初始化
void initlist(sqlist *l) {
    l->elem = (elemtype*)malloc(list_init_size);
    if (!l->elem)  //储存分配失败
        exit(-1);
    l->length = 0;    //空表长度为0
    l->listsize = list_init_size; //初始储存容量
}
//判断表是否为空
int emptylist(sqlist *l)
{
    if (l->length == 0)
    {
        return ok;
    }
    return error;
}
//尾插
int backinsert(sqlist *l,elemtype e) {
    elemtype *newbase, *p;
    if (l->length >= l->listsize)  //当前储存空间已满,增加分配
    {
        newbase = (elemtype*)realloc(l->elem, (l->listsize +
            listincrement) * sizeof(elemtype));
        if (!newbase)  exit(-1);
        l->elem = newbase;  //新基地址
        l->listsize += listincrement;  //增加储存容量
    }
    p = l->elem + l->length;  //p指向最后一个元素的后一个地址
    *p = e;       //插入e
    l->length++;  //表长加1
    return ok;

}
//打印表中元素
void printlist(sqlist *l)
{
    int i;
    if (emptylist(l)==ok)
    {
        printf("表为空!\n");
        exit(-1);
    }
    for (i = 0; i< l->length; i++)
    {
        printf("%d ",*( l->elem+i));
    }
    printf("\n");
}
//销毁表
int destorylist(sqlist *l) {
    
    free(l->elem);
    return ok;
}

  源代码:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 #include "sqstack.h" //引入顺序栈储存结构及其基本操作
 5 #include "sqlist.h"  //引入顺序表储存结构及其基本操作
 6 #define ok 1
 7 #define error 0
 8 
 9 //对于输入任意一个非负的十进制数,打印与其等值的n进制数
10 void conversion(int n) {
11     double x, decimal;
12     int integer;
13     scanf("%lf", &x);
14     integer =(int)floor(x);  //整数部分
15     decimal = x - integer; //小数部分
16     //处理整数部分
17     
18     stacktype *e;
19     sqstack *ps, s;
20         ps = &s;
21         e = (stacktype*)malloc(sizeof(stacktype));    //为指针e分配内存地址
22         initstack(ps);                               //初始化栈
23         while (integer)  //当integer不等于0
24         {
25             push(ps, integer % n);  //压入integer 除以n的余数
26             integer = integer / n;
27         }
28         while (emptystack(ps) != ok) //当栈不为空
29         {
30             pop(ps, e);  //弹出的栈顶元素,并让e指向其地址
31             printf("%d ", *e); // 输出e 每一个数码间用空格隔开
32         }
33         //处理小数部分
34         if (decimal) { //小数部分不为0 才处理
35             sqlist *l;
36             elemtype m;
37             l = (sqlist*)malloc(sizeof(sqlist)); //为指针l分配内存地址
38             initlist(l);                        //初始化顺序表
39             while (decimal)   //当decimal不为0
40             {
41                 m = (elemtype)floor(decimal*n);
42                 backinsert(l, m); //插入decimal*n的整数
43                 decimal = decimal * n - m;
44             }
45             printf(". ");
46             printlist(l);  //每一个数码之间用空格隔开
47         }
48 }
49 int main() {
50     int n;
51     printf("请输入目标进制:");
52     scanf("%d", &n);
53     printf("将十进制数n转换为%d进制数,请输入:n(>=0)=", n);
54     conversion(n);
55     return 0;
56 
57 }

   合理的使用数据结构可以使代码跟易读,易懂。栈的引入

简化了程序设计的问题,划分了不同的关注层次,逻辑思路清晰。