void push_tail(struct LinkList* list, struct Node* temp) { temp->pro = list->head; temp->next = list->tail; list->tail->pro = temp; list->head->next = temp; list->head = temp; }这是双向链表的头插法还是尾插法
时间: 2024-03-18 13:43:21 浏览: 103
这是双向链表的尾插法。在这个函数中,我们将新节点temp插入到链表的尾部,即temp成为新的尾节点。具体来说,我们将temp的前驱指针pro指向当前链表的头节点list->head,将temp的后继指针next指向当前链表的尾节点list->tail,然后将当前链表的尾节点的前驱指针list->tail->pro指向temp,将当前链表的头节点的后继指针list->head->next指向temp,最后更新链表的头节点为temp,完成插入操作。
相关问题
查找错误并举出、修改#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> typedef struct num { float a; //系数 int b; //指数 struct num *next; }*num; struct LinkList // 链表类型 { num head;// 分别指向线性链表中的头结点和最后一个结点 感觉不需要tail int len; // 指示线性链表中数据元素的个数 }; struct LinkList *init(struct LinkList *list)//创建空链表 { list = (struct LinkList *)malloc(sizeof(struct LinkList)); list->len = 0; list->head = (struct num*)malloc(sizeof(struct num));//list->tail = list->head->next = NULL;//list->tail->next = return list; }; void compare(struct LinkList *list, float a, int b)//比较指数 { int i = 0; struct num*p = list->head; for (i; i <= list->len; i++) { if (b > p->b) p = p->next; else if (b = p->b){ p->b += b; break; } else{ add(list, i, a, b);//插入 break; } } if (i>list->len) add(list, i, a, b);//添加到最后一个 }; void add(struct LinkList *list, int index, float a,int b)//添加新的指数项 { struct num*p = list->head, *s; int i; for (i = -1; i<index - 1; i++) { p = p->next; } s = (struct num *)malloc(sizeof(struct num)); s->a = a; s->b = b; s->next = p->next; p->next = s; list->len++; //if (index == list->len) 感觉不需要尾结点 // list->tail = s; }; int main(){ //指数升序查找 struct LinkList *lista, *listb ; lista = init(lista); listb = init(listb); int n,b; float a; scanf("%d", &n); for (int i = 0; i < n; i++)//lista { scanf("%f%d", &a,&b); compare(lista, a, b); } scanf("%d", &n); for (int i = 0; i < n; i++)//listb { scanf("%f%d", &a, &b); compare(listb, a, b); } return 0; }
在这段代码中,有两个问题:
1. 在定义结构体 `num` 时,没有为 `next` 成员指定类型,应该将 `*num` 改为 `struct num *`。
2. 在函数 `init` 中,没有为头结点的 `next` 成员赋值,应该为其赋值为 `NULL`。
下面是修改后的代码:
```c
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct num {
float a; //系数
int b; //指数
struct num* next;
} *num;
struct LinkList // 链表类型
{
num head; // 分别指向线性链表中的头结点和最后一个结点
int len; // 指示线性链表中数据元素的个数
};
struct LinkList* init(struct LinkList* list) //创建空链表
{
list = (struct LinkList*)malloc(sizeof(struct LinkList));
list->len = 0;
list->head = (num)malloc(sizeof(struct num));
list->head->next = NULL;
return list;
};
void compare(struct LinkList* list, float a, int b) //比较指数
{
int i = 0;
num p = list->head;
for (i; i <= list->len; i++)
{
if (b > p->b)
p = p->next;
else if (b == p->b) {
p->a += a;
break;
}
else {
add(list, i, a, b); //插入
break;
}
}
if (i > list->len)
add(list, i, a, b); //添加到最后一个
};
void add(struct LinkList* list, int index, float a, int b) //添加新的指数项
{
num p = list->head, *s;
int i;
for (i = -1; i < index - 1; i++)
{
p = p->next;
}
s = (num)malloc(sizeof(struct num));
s->a = a;
s->b = b;
s->next = p->next;
p->next = s;
list->len++;
};
int main()
{
//指数升序查找
struct LinkList* lista, * listb;
lista = init(lista);
listb = init(listb);
int n, b;
float a;
scanf("%d", &n);
for (int i = 0; i < n; i++) //lista
{
scanf("%f%d", &a, &b);
compare(lista, a, b);
}
scanf("%d", &n);
for (int i = 0; i < n; i++) //listb
{
scanf("%f%d", &a, &b);
compare(listb, a, b);
}
return 0;
}
```
6-7 移动链表中的最大值到尾部 分数 10 编写函数MoveMaxToTail(),实现查找单链表中值最大的结点,并将其移动到链表尾部,注意其他结点的相对次序不变。要求尽量具有较高的时间效率。 例如输入8 12 46 30 5,输出为8 12 30 5 46 函数接口定义: void MoveMaxToTail (LinkList H ); 裁判测试程序样例: #include<stdio.h> #include<stdlib.h> typedef int DataType; struct Node { DataType data; struct Node* next; }; typedef struct Node *PNode; typedef struct Node *LinkList; void MoveMaxToTail(head); LinkList SetNullList_Link() { LinkList head = (LinkList)malloc(sizeof(struct Node)); if (head != NULL) head->next = NULL; else printf("alloc failure"); return head; } void CreateList_Tail(struct Node* head) { PNode p = NULL; PNode q = head; DataType data; scanf("%d", &data); while (data != -1) { p = (struct Node*)malloc(sizeof(struct Node)); p->data = data; p->next = NULL; q->next = p; q = p; scanf("%d", &data); } } void MoveMaxToTail (LinkList H ) { @@ } void print(LinkList head) { PNode p = head->next; while (p) { printf("%d ", p->data); p = p->next; } } void DestoryList_Link(LinkList head) { PNode pre = head; PNode p = pre->next; while (p) { free(pre); pre = p; p = pre->next; } free(pre); } int main() { LinkList head = NULL; head = SetNullList_Link(); CreateList_Tail(head); MoveMaxToTail(head); print(head); DestoryList_Link(head); return 0; }
下面是实现 MoveMaxToTail 函数的代码:
```c
void MoveMaxToTail (LinkList H ) {
if (H == NULL || H->next == NULL) return; // 链表为空或只有一个结点,直接返回
PNode p = H->next, maxNode = p, preMaxNode = H; // p 从第一个结点开始,maxNode 记录最大值结点,preMaxNode 记录前驱结点
while (p->next) { // 从第二个结点开始遍历
if (p->next->data > maxNode->data) {
maxNode = p->next; // 更新最大值结点
preMaxNode = p; // 更新前驱结点
}
p = p->next;
}
if (maxNode != p) { // 若最大值结点不是尾结点
preMaxNode->next = maxNode->next; // 从链表中删除最大值结点
maxNode->next = NULL; // 将最大值结点置为尾结点
p->next = maxNode; // 将最大值结点插入到尾结点后面
}
}
```
该函数的时间复杂度为 O(n),其中 n 是链表的长度。
阅读全文
相关推荐
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)