-2

所以我正在编写这个程序，将用户输入存储在链表上并将其反转，但我有点迷茫。是否可以为不返回任何值的循环类型提供循环不变量？例如，位于 main 内部的循环。

这是我用来在 main 中获取用户输入并将其存储在链表中的循环示例，当然代码上还有更多内容，但我只展示了相关的内容。

typedef struct node {
char x; // data
struct node* next; // link to next node
} Node;

int main(void){
char c = ' ';
Node* start = NULL; 
Node* temp; 
while(c!='.'){
    c=getchar();
    temp=(Node*)calloc(1, sizeof(Node));
    temp->x = c; 
    temp->next = start; 
    start = temp; 
}

是否有可能为此提出一个循环不变量？另外，程序正确性是什么意思，在我的情况下如何证明它？

谢谢！

4

2 回答 2

0

循环不变量是关于程序中变量之间关系的正式陈述，它在循环运行之前成立（建立不变量）并且在循环底部再次为真，每次通过循环（保持不变量)

假设这是你想要的。您显示的代码看起来不错，可以将节点添加到链表，因此关于正确性应该没问题。

char str[100];
int cnt = 0;
int n;
fgets(str,100,stdin);
if(strlen(str) < 99)
str[strlen(str) -1] = '\0';

n = strlen(str);
/* cnt <= n */
while(str[i] != '.')
{
   /* cnt <= n */
   // Do your stuff
   cnt++;
   /* cnt <= n */
}
/* cnt <= n */

循环不变量将是

cnt <= n
于 2015-01-21T06:36:34.397 回答
0

循环不变量是在循环的每次迭代之前和之后必须立即为真的条件

int main(void)
{
    char c = ' ';
    Node* start = NULL; 
    Node* temp = NULL; 

    while(c!='.'){
        /* temp = NULL before each iteration*/

        c=getchar();
        temp=(Node*)calloc(1, sizeof(Node));
        temp->x = c; 
        temp->next = start; 
        start = temp;

        temp = NULL;
        /* temp = NULL after each iteration*/
    }

So in this case temp is NULL before and after each iteration of the loop. 你可以用这个作为证明。

有关更多详细信息，请参阅http://en.wikipedia.org/wiki/Loop_invariant 和什么是循环不变量？

于 2015-01-21T06:37:32.517 回答