LinkList ListSearch(LinkList L, ElemType e) {//在带头结点的单链表L中,查找最后一个小于e的结点,返回其地址,没有返回查找过程中的最后一个结点地址 // 不完整,要自己完善 }
时间: 2023-05-27 19:07:53 浏览: 49
LinkList ListSearch(LinkList L, ElemType e) {
LinkList p = L->next; // 从第一个结点开始查找
LinkList pre = L; // pre指向p的前一个结点
LinkList target = NULL; // 初始化目标结点为NULL
while (p != NULL) {
if (p->data < e) {
target = p; // 更新目标结点
pre = p; // 更新pre指向目标结点的前一个结点
p = p->next; // 继续向后查找
} else {
break; // 结束查找
}
}
if (target == NULL) { // 如果没有找到目标结点
return pre; // 返回查找过程中的最后一个结点地址
} else {
return target; // 返回目标结点地址
}
}
相关问题
int GetElem(LinkList L,int i,ElemType &e) { // L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回1,否则返回0
这是一个获取带头结点单链表中第i个元素的函数,函数原型如下:
```
int GetElem(LinkList L, int i, ElemType &e);
```
其中,`L`为带头结点单链表的头指针,`i`为需要获取元素的位置,`e`为获取到的元素值。
函数的返回值为`int`类型,如果第`i`个元素存在,其值赋给`e`并返回1,否则返回0。
函数的具体实现如下:
```c++
int GetElem(LinkList L, int i, ElemType &e) {
if (i < 1) return 0; // i小于1,无法获取元素,返回0
LNode *p = L->next;
int j = 1;
while (p && j < i) { // 从头结点后的第一个结点开始遍历链表,直到找到第i个结点,或者链表遍历完毕
p = p->next;
j++;
}
if (!p || j > i) return 0; // 链表遍历完毕,仍未找到第i个结点,返回0
e = p->data;
return 1; // 找到第i个结点,将其值赋给e,并返回1
}
```
注:该函数的时间复杂度为$O(n)$,其中$n$为链表的长度。
用单链表存储线性表,写出在带头结点的单链表中插入数据元素e作为单链表的第i个元素的算法和求单链表长度ListLength()的算法。 Typedef struct Lnode { ElemType data; //数据域 struct Lnode *next; //指针域 }Lnode, *LinkList; bool ListInsert(LinkList &L, int i, ElemType e){ int ListLength( LinkList L ){
插入数据元素e作为单链表的第i个元素的算法:
```
bool ListInsert(LinkList &L, int i, ElemType e){
if(i < 1){ //i小于1无意义
return false;
}
Lnode *p = L; //p指向头结点
int j = 0; //j表示当前p指向的结点是第几个结点
while(p && j < i - 1){ //查找第i-1个结点
p = p->next;
j++;
}
if(!p){ //i大于表长加1,插入无效
return false;
}
Lnode *s = new Lnode; //新建结点s
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
```
求单链表长度ListLength()的算法:
```
int ListLength(LinkList L){
int len = 0;
Lnode *p = L->next; //p指向第一个结点
while(p){ //遍历单链表
len++;
p = p->next;
}
return len;
}
```