用C语言假有一个带有头结点的单链表,请设计算法判断该链表中的结点是否成等差关系,即假设个元素依次为a1,a2,a3....,判断ai+1-ai=ai-ai-1是否成立,其中i满足2小于等于i小于等于n+
时间: 2024-05-11 16:14:28 浏览: 16
算法思路:
1. 定义一个指针p指向链表的第一个结点,再定义一个指针q指向链表的第二个结点。
2. 依次遍历链表中的每个结点,判断ai 1-ai=ai-ai-1是否成立。若成立,则继续遍历;若不成立,则该链表不是等差数列,返回false。
3. 若遍历完整个链表,都满足ai 1-ai=ai-ai-1成立,则该链表为等差数列,返回true。
C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { // 定义单链表结点类型
int data;
struct Node* next;
} Node;
bool isArithmeticSequence(Node* head) {
Node* p = head->next;
Node* q = p->next;
int diff = q->data - p->data; // 计算公差
while (q != NULL) {
if (q->data - p->data != diff) {
return false; // 不是等差数列,返回false
}
p = q;
q = q->next;
}
return true; // 是等差数列,返回true
}
int main() {
// 创建带有头结点的单链表
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
Node* tail = head;
int n, num;
printf("请输入链表长度:");
scanf("%d", &n);
printf("请输入链表中的元素:");
for (int i = 1; i <= n; i++) {
scanf("%d", &num);
Node* node = (Node*)malloc(sizeof(Node));
node->data = num;
node->next = NULL;
tail->next = node;
tail = node;
}
// 判断链表是否为等差数列
if (isArithmeticSequence(head)) {
printf("该链表是等差数列。\n");
} else {
printf("该链表不是等差数列。\n");
}
// 释放链表内存
Node* p = head;
while (p != NULL) {
Node* q = p->next;
free(p);
p = q;
}
return 0;
}
```