node *p = L->next;是什么意思
时间: 2024-05-27 14:08:44 浏览: 11
这行代码表示将链表 L 的头节点的指针域所指向的第一个节点的指针赋值给指针变量 p。也就是说,p 指向链表 L 中的第一个节点。其中,node 是链表节点的结构体类型,L 是指向链表头节点的指针。该语句通常用于遍历链表,可以通过 p 不断地向后遍历链表中的节点,直到 p 指向 NULL,即链表的尾部节点。
相关问题
node* searchid(long long id, node* L) {//按学号查找 node* p = L; while (p->next != NULL) {//遍历链表 if (p->next->id == id) { return p; } p = p->next; } return NULL; }将这个改为折半查找法
折半查找法(二分查找)是一种适用于有序数组的查找算法,因为链表并没有顺序,所以无法直接使用折半查找法。但可以对链表进行转换,将其转换成有序的数组,然后再使用折半查找法。这种转换需要额外的空间存储,时间复杂度也会有所增加。因此,这里我们不对链表进行转换,而是使用一种基于折半查找法的优化算法,称为“插值查找法”。
插值查找法的基本思想是根据查找值在数组中的大致位置,从而确定查找范围,从而提高查找效率。具体实现过程如下:
```c++
node* searchid(long long id, node* L) {
node* left = L;
node* right = NULL;
// 先找到链表的尾节点
while (L->next != NULL) {
L = L->next;
}
right = L;
while (left != right && left->next != right) {
// 计算查找值在当前范围内的大致位置
double pos = (double)(id - left->id) / (right->id - left->id);
node* mid = left->next;
// 根据位置比例,计算中间节点的位置
for (int i = 0; i < (int)(pos * (right->id - left->id)); i++) {
mid = mid->next;
}
if (mid->id == id) {
return left;
} else if (mid->id < id) {
left = mid;
} else {
right = mid;
}
}
if (left->next != NULL && left->next->id == id) {
return left;
}
return NULL;
}
```
在这个函数中,我们使用了两个指针left和right,分别指向链表的头节点和尾节点。然后,通过计算查找值在当前范围内的大致位置,从而确定中间节点的位置。接着,根据中间节点的值和查找值的大小关系,缩小查找范围。最后,如果找到了目标节点,则返回其前一个节点的指针,否则返回NULL。
需要注意的是,插值查找法并不是适用于所有情况的最优算法,因为如果数据分布不均匀,可能会出现查找效率较低的情况。但是,对于数据分布均匀的链表,插值查找法可以提高查找效率。
#include<stdio.h> #define MAXSIZE 100 #include<malloc.h> typedef struct node{ int data; struct node*next; }LNode,*Linklist; void create(Linklist L){ int m; Linklist s; s=L; while(1){ scanf("%d",&m); if(m==0)break; Linklist p=(Linklist)malloc(sizeof(LNode)); p->data=m; p->next=NULL; s->next=p; s=p; } } int lentgh(Linklist L){ Linklist p=L->next; int len=0; while(p){ p=p->next; len++; } return len; } void Bobblesort(Linklist L){ int len=lentgh(L); Linklist p; int a; for(int i=0;i<len-1;i++){ p=L->next; for(int j=0;j<len-i-1;j++){ if(p->data>p->next->data) { a=p->next->data; p->next->data=p->data; p->data=a; } p=p->next; } } } void Delete(Linklist L){ Linklist p=L->next; while(p->next){ if(p->data==p->next->data) { Linklist tmp=p->next; p->next=p->next->next; free(tmp); }p=p->next; } } void output(Linklist L){ Linklist p; p=L->next; while(p){ printf("%d ",p->data); p=p->next; } } int main(){ Linklist L; L=(Linklist)malloc(sizeof(LNode)); create(L); Bobblesort(L); Delete(L); output(L); }为什么不对
这段代码存在以下问题:
1.在create函数中,传入的参数是Linklist类型,即指向节点的指针,但是在函数内部对其进行修改时,并没有传入指向指针的指针,导致在函数外部无法获取到链表的头指针。
2.在Delete函数中,当p->data==p->next->data时,应该先判断p->next是否为NULL,否则会出现访问NULL指针的错误。
3.在Delete函数中,当删除节点时,应该将p指向被删除节点的前一个节点,否则会出现遍历不完整的情况。
4.在main函数中,应该对L进行初始化,即将L指向NULL,否则L中会存在随机值,导致程序出现未知错误。
下面是修改后的代码:
```c
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef struct node{
int data;
struct node *next;
}LNode, *Linklist;
void create(Linklist *L){
int m;
Linklist s;
*L = (Linklist)malloc(sizeof(LNode));
s = *L;
while(1){
scanf("%d",&m);
if(m == 0) break;
Linklist p = (Linklist)malloc(sizeof(LNode));
p->data = m;
p->next = NULL;
s->next = p;
s = p;
}
}
int len(Linklist L){
Linklist p = L->next;
int len = 0;
while(p){
p = p->next;
len++;
}
return len;
}
void BubbleSort(Linklist L){
int i, j, len = len(L);
Linklist p;
int a;
for(i = 0; i < len - 1; i++){
p = L->next;
for(j = 0; j < len - i - 1; j++){
if(p->data > p->next->data){
a = p->next->data;
p->next->data = p->data;
p->data = a;
}
p = p->next;
}
}
}
void Delete(Linklist L){
Linklist p = L->next;
Linklist tmp;
while(p != NULL && p->next != NULL){
if(p->data == p->next->data){
tmp = p->next;
p->next = tmp->next;
free(tmp);
}else{
p = p->next;
}
}
}
void output(Linklist L){
Linklist p;
p = L->next;
while(p){
printf("%d ",p->data);
p = p->next;
}
}
int main(){
Linklist L = NULL;
create(&L);
BubbleSort(L);
Delete(L);
output(L);
return 0;
}
```
注意:这里修改后的代码仅仅是修正了代码的问题,但是并没有改变代码的逻辑,所以如果前面存在的逻辑错误,还需要根据具体需求进行修改。