题目如下,解法可能不是最好的 若有更好解法 请赐教
初学算法~望多多指教啊~~
解法:
1
2
3 #include <iostream>
4 #include <windows.h>
5
6 #define MAXINPUT 15
7
8 using namespace std ;
9
10 struct stack {
11 int *data ;
12 stack *next ;
13 } ;
14
15
16
17 stack *push(stack *top , int *data ) //压栈
18 {
19 stack *tem = new stack ;
20
21 tem->data = data ;
22
23 tem->next = top ;
24
25 return tem ;
26 }
27
28 stack *pop(stack *top , int **data) //出栈
29 {
30 if( top == NULL)
31 return top ;
32 stack *tem ;
33
34 tem = top ;
35
36 *(data) = tem->data ;
37
38 top = top->next ;
39
40 delete tem ;
41
42 return top ;
43 }
44
45 void stackprint(stack *top) //打印栈内容
46 {
47 while(1)
48 {
49
50 if( top == NULL )
51 break ;
52
53 cout<<*(top->data)<<" " ;
54
55 top = top->next ;
56
57 }
58
59 cout<<endl ;
60 }
61
62
63
64 int sum = 0 , input[MAXINPUT] = {0} ;
65
66 int main(void)
67 {
68 int count = 0 , T = 0 ;
69
70 cout<<"请输入T值"<<endl ;
71 cin>>T ;
72
73 cout<<"请输入w数组数目"<<endl ;
74 cin>>count ;
75
76 if( count > MAXINPUT )
77 {
78 cout<<"输入溢出"<<endl ;
79 return 1 ;
80 }
81
82 for( int i = 0 ; i < count ; i++ )
83 {
84 cout<<"请输入w["<<i<<"]值"<<endl ;
85 cin>>input[i] ;
86 }
87
88 cout<<endl<<"Loading
"<<endl ;
89
90
91
92 stack *top = NULL ; //初始化栈
93
94 int i = 0 , *temdata = input , *popdata = input , *enddata = &input[count] ;
95
96 /*
97 栈的非递归调用,
98 先压栈数据,然后依次遍历剩余的数据,满足条件打印,小于预期值就压栈
99 接着遍历剩余数据,遍历这个层次的数据完了就出栈,然后指针+1(指向下一个数据),继续遍历剩余数据
100 */
101
102 while(1)
103 {
104 sum += *temdata ;
105
106 top = push(top , temdata) ;
107
108 if( sum == T )
109 {
110 stackprint(top) ;
111 top = pop(top,&popdata) ;
112 sum -= *popdata ;
113 top = pop(top , &popdata ) ;
114 sum -= *popdata ;
115 temdata = ++popdata ;
116
117 }
118 else if (sum > T )
119 {
120 top = pop(top,&popdata) ;
121 sum -= *popdata ;
122 temdata = ++popdata ;
123 }
124 else if( sum<T )
125 {
126 temdata = ++popdata ;
127 }
128
129 if( (temdata-1) == enddata )
130 {
131 top = pop(top,&popdata) ;
132 sum -= *popdata ;
133 top = pop(top,&popdata) ;
134 sum -= *popdata ;
135
136 temdata = ++popdata ;
137 }
138
139 if( top == NULL && popdata == enddata)
140 break ;
141
142 }
143
144
145
146
147 system("pause") ;
148
149 return 1;
150
151 }
152
153
154