已知单链表结点数据结构如下,编写算法判断一个单链表中各结点的值是否由小到大排列。如果是,返回1,不是则返回0。 typedef struct Node { ElemType data; struct Node *next; } LinkNode,*LinkList;
时间: 2023-05-21 09:07:18 浏览: 124
下面是判断单链表中各结点的值是否由小到大排列的算法,可以返回1或0:
int is_ordered(LinkList L) {
if (L == NULL || L->next == NULL) { // 空表或只有一个结点的情况
return 1;
}
LinkNode *p = L;
int min = p->data;
while (p != NULL) {
if (p->data < min) {
return 0;
}
min = p->data;
p = p->next;
}
return 1;
}
注意:该算法不能处理有相同值的结点的情况。如果要处理这种情况,可以在比较相邻两个结点的值时,使用 <= 而非 <。
相关问题
已知带头结点单链表L中存储一组整数,编写算法删除表中所有值大于x的结点。
以下是删除表中所有值大于x的结点的算法:
```
void deleteNodesGreaterThanX(ListNode* head, int x) {
ListNode* current = head->next;
ListNode* previous = head;
while (current != nullptr) {
if (current->val > x) {
previous->next = current->next;
delete current;
current = previous->next;
} else {
previous = current;
current = current->next;
}
}
}
```
其中,ListNode 是单链表的结点类型,head 是头结点,val 是结点存储的整数值。
已知带头结点的动态单链表是按整数值递增进行排列,写一算法将x插入
这个动态单链表中,使得插入后仍然保持递增顺序。
算法如下:
1. 创建一个新的节点,将x赋值给它的数据域。
2. 从头结点开始遍历链表,找到第一个比x大的节点。
3. 将新节点插入到该节点的前面。
4. 如果找不到比x大的节点,说明x是最大的,将新节点插入到链表的末尾。
代码如下:
void insert(Node* head, int x) {
Node* p = head;
while (p->next != NULL && p->next->data < x) {
p = p->next;
}
Node* new_node = new Node;
new_node->data = x;
new_node->next = p->next;
p->next = new_node;
}