任意长度的大数加法（栈的应用）,数据结构与算法,技术交流,鱼C论坛

18577318294 发表于 2016-9-4 22:17:17

我来

一个厉害的名字 发表于 2016-9-8 10:49:14

{:10_254:}

lb2616 发表于 2016-9-10 14:00:44

学习

陶逗逗 发表于 2016-10-30 14:48:27

感觉很6

zzzz76 发表于 2016-10-31 22:24:02

写了三个while，感觉复杂度有些高，不知对不对

84561475 发表于 2017-3-16 09:57:55

我写的感觉好复杂用了三个stack

#include<iostream>

using namespace std;

const int STOCK_SIZE = 100;//定义栈的大小

template<class DataType>
class DSStack
{
public:
DSStack(DataType[], int);
DSStack();
~DSStack();
void Push(DataType data);
DataType Pop();
void Clear();
void Print();
DataType GetTopData();
private:
DataType elem;
DataType *top;
DataType *bottom;
int Count;
};

template<class DataType>
DSStack<DataType>::DSStack(DataType data[], int len)
{
bottom = elem;// 栈底初始指向
top = bottom; // 初始栈底与栈顶指针指向相同的位置
for (int i = 1; i <= len; i++)
{
elem = data;
Count++;
}
}

template<class DataType>
DSStack<DataType>::DSStack()
{
bottom = elem;// 栈底初始指向
top = bottom; // 初始栈底与栈顶指针指向相同的位置
Count = 0;
}

template<class DataType>
DSStack<DataType>::~DSStack()
{
}

template<class DataType>
void DSStack<DataType>::Push(DataType data)
{
if (Count > STOCK_SIZE) return;
Count++;
elem = data;
}

template<class DataType>
DataType DSStack<DataType>::Pop()
{
if (Count < 1)return -1;
DataType data;
data = elem;
Count--;
return data;
}

template<class DataType>
void DSStack<DataType>::Clear()
{
top = bottom;
Count = 0;
}

template<class DataType>
void DSStack<DataType>::Print()
{
cout << "栈的数据: " << endl;
for (int i = 1; i <= Count; i++)
{
cout << " " << elem << endl;
}
}

template<class DataType>
DataType DSStack<DataType>::GetTopData()
{
if (Count == 0) return -1;
return elem;
}

void main()
{
DSStack<char> *stack_addend = new DSStack<char>();
DSStack<char> *stack_augend = new DSStack<char>();
DSStack<int> *stack_retult = new DSStack<int>();

cout << "请输入加数以#结束" << endl;
char s = ' ';
cin >> s;
while (s != '#')
{
stack_addend->Push(s);
cin >> s;
}
stack_addend->Print();

cout << "请输入被加数以#结束" << endl;
s = ' ';
cin >> s;
while (s != '#')
{
stack_augend->Push(s);
cin >> s;
}
stack_augend->Print();
bool is_carry = false;// 是否进位
while ((stack_addend->GetTopData() != -1) || (stack_augend->GetTopData() != -1) || is_carry)
{

// 考虑到两个数的位数不一定相等，把没有的弄为0
if (stack_addend->GetTopData() == -1)
{
stack_addend->Pop();
stack_addend->Push(48);
}
if (stack_augend->GetTopData() == -1)
{
stack_augend->Pop();
stack_augend->Push(48);
}

char addend = stack_addend->Pop();
char augend = stack_augend->Pop();

int result = 0;
if (is_carry)
{
result = ((int)addend - 48) + ((int)augend - 48) + 1;
is_carry = false;
}
else
{
result = ((int)addend - 48) + ((int)augend - 48);
}

if (result >= 10) // 如果的出来的结果是两位数
{
int temp = result % 10;
stack_retult->Push(temp);
is_carry = true;
//stack_retult->Push(result / 10);
}
else
{
stack_retult->Push(result);
}

}

stack_retult->Print();
getchar();
getchar();
}

wangjia911 发表于 2017-6-1 02:31:53

学习

莱昂纳多 发表于 2017-7-20 21:57:14

啊师傅

yeahbijin 发表于 2017-8-25 15:21:26

嗜睡的小哥 发表于 2017-8-25 21:27:53

{:10_256:}看看

生炒牛肉饭42 发表于 2017-9-18 08:03:19

谢谢小甲鱼老师啊啊啊啊啊啊

xiaocangshu886 发表于 2017-9-26 09:58:21

Elevenx 发表于 2017-9-26 16:44:38

对答案

aiblue 发表于 2017-10-15 22:32:59

学习学习。

ljxll326 发表于 2017-12-23 12:00:05

崔文浩 发表于 2017-12-30 11:15:20

就能

圣狄雅哥 发表于 2018-2-3 09:29:18

{:5_91:}

圣狄雅哥 发表于 2018-2-3 10:57:28

carry是char型的，但赋值时carry = 0，可以将整形数据赋值给字符型吗

圣狄雅哥 发表于 2018-2-3 10:58:25

谁参照它编一个减法器、乘法器

圣狄雅哥 发表于 2018-2-3 14:55:49

本帖最后由圣狄雅哥于 2018-2-3 14:59 编辑

//实现输入任意长度字符串的整数减法
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;

typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}sqstack;

void Initstack(sqstack *s)
{
s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!s->base)
{
   exit(0);
}
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}

void push(sqstack*s,ElemType e)
{
if(s->top-s->base>=s->stacksize)
{
   s->base=(ElemType*)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(ElemType));
   if(!s->base)
   {
         exit(0);
   }
   s->top=s->base+s->stacksize;
   s->stacksize+=STACKINCREMENT;
}
*(s->top++)=e;
}

void pop(sqstack*s,ElemType*e)
{
if(s->top==s->base)
{
   return;
}
*e=*(--s->top);
}

int stacklen(sqstack *s)
{
return (s->top-s->base);
}

void SUBTRACTION(sqstack*s1,sqstack*s2,sqstack*s3)
{
char a,b,c;
char carry=0;
while(stacklen(s1)!=0&&stacklen(s2)!=0)
{
   pop(s1,&a);
   pop(s2,&b);
   c=(a-48)-(b-48)-carry+48;
   if(c<'0')
   {
         c=c+'9'-47;
         carry=1;
   }
   else
   {
         carry=0;
   }
   push(s3,c);
}
if(stacklen(s1)!=0)
{
   while(stacklen(s1)!=0)
   {
         pop(s1,&a);
         c=a-carry;
         if(c<'0')
      {
         c=c+'9'-47;
         carry=1;
      }
      else
      {
         carry=0;
      }
   push(s3,c);
   }
}
else if(stacklen(s2)!=0)
{
   while(stacklen(s2)!=0)
   {
         pop(s2,&b);
         c='0'-carry-b;
         carry=1;
         c=c+'9'-47;
   push(s3,c);
   }
}
if(carry==1)
{
   while(stacklen(s3)!=0)
   {
         pop(s3,&b);
         push(s2,b);
   }
   carry=0;
   while(stacklen(s2)!=0)
   {
         pop(s2,&b);
         c='9'-b+49-carry;
         push(s3,c);
         carry=1;
   }
   push(s3,'-');
}
}

int main()
{
char e;
sqstack s1, s2, s3;

Initstack(&s1);
Initstack(&s2);
Initstack(&s3);

printf("请输入第一串任意整数，输入＃表示结束：");
scanf("%c", &e);
while( e != '#' )
{
   push(&s1, e);
   scanf("%c", &e);
}
getchar();    // 回收回车符

printf("\n请输入第二串任意整数，输入＃表示结束：");
scanf("%c", &e);
while( e != '#' )
{
   push(&s2, e);
   scanf("%c", &e);
}
getchar();    // 回收回车符

SUBTRACTION(&s1, &s2, &s3);

printf("\n两者的差是：");
while(stacklen(&s3) != 0)
{
   pop(&s3, &e);
   printf("%c", e);
}

return 0;
}

页: 1 2 3 4 [5] 6

鱼C论坛's Archiver