已知带头结点的线性链表L中的结点是按整数值递增排列的,试写一算法,将值为e的结点插入到表L中,使得L仍然递增有序。
时间: 2024-05-03 21:21:12 浏览: 7
算法思路:
1. 找到e应该插入的位置,即找到第一个大于等于e的结点p和p的前驱结点q。
2. 新建一个结点s,将e赋值给s的数据域。
3. 将s插入到p的前面,即将q的next指向s,将s的next指向p。
算法实现:
```
void insertNode(Node *L, int e) {
Node *p = L->next, *q = L;
while (p != NULL && p->data < e) {
q = p;
p = p->next;
}
Node *s = new Node();
s->data = e;
s->next = p;
q->next = s;
}
```
时间复杂度:O(n),其中n为链表的长度。需要遍历整个链表才能找到插入位置。
相关问题
已知带头结点的线性链表L中的结点是按整数值递增排列的,试写一c语言算法,将值为e的结点插入到表L中,使得L仍然递增有序。
```
void InsertNode(LinkList L, int e) {
LinkList p = L->next, prev = L;
while (p && p->data < e) {
prev = p;
p = p->next;
}
LinkList newNode = (LinkList)malloc(sizeof(Node));
newNode->data = e;
newNode->next = p;
prev->next = newNode;
}
```
算法思路:
从链表头结点开始遍历链表,找到第一个大于等于插入元素的结点位置,将新结点插入到该位置之前,即可保证链表仍然递增有序。
已知带头结点的动态单链表是按整数值递增进行排列,写一算法将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;
}