给定一个带头结点的单链表,删除掉倒数第三个元素并返回其值到e,写出void delete(SLList &L, ElemType &e)
时间: 2024-02-25 10:55:45 浏览: 22
好的,以下是实现代码:
```c++
void delete(SLList &L, ElemType &e){
if(L == NULL || L->next == NULL || L->next->next == NULL){ //链表为空或者只有一个或两个结点,无法删除倒数第三个结点
e = NULL;
return;
}
SList p = L, q = L->next, r = q->next;
while(r->next != NULL){ //遍历链表,找到倒数第三个结点
p = p->next;
q = q->next;
r = r->next;
}
e = q->data; //将倒数第三个结点的值保存到e中
p->next = r; //删除倒数第三个结点
free(q); //释放倒数第三个结点的空间
}
```
需要注意的是,该函数中的 `SLList` 是指向链表头结点的指针,`SList` 是指向链表结点的指针,`ElemType` 是链表中存储的数据类型。此外,如果链表为空或只有一个或两个结点,无法删除倒数第三个结点,此时将 `e` 赋值为 `NULL`。
相关问题
用void Distribute(SLList &L,int i,ArrType &f,ArrType &e); void Collect(SLList &L,int i,ArrType f,ArrType e); void RadixSort(SLList &L);实现基数排序
好的,我来解释一下这段代码的实现方式:
基数排序是一种非比较排序算法,它根据关键字位数的不同,将待排序数据分配到桶中,再按照桶的顺序依次输出,从而达到排序的目的。具体来说,基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。这样通过分配和收集的过程,基数排序可以保证排序的稳定性。
下面是具体实现的步骤:
1. 定义一个链表数据结构 SLList,以及两个数组 f 和 e。
2. 实现 Distribute 函数,用于将链表 L 中的每个元素按照关键字 i 的值分配到 f 和 e 数组中。
3. 实现 Collect 函数,用于将 f 和 e 数组中的元素按照顺序收集到链表 L 中。
4. 实现 RadixSort 函数,用于实现基数排序的主体逻辑。
具体实现过程可以参考下面的代码:
```c++
#define RADIX 10 // 基数为10
typedef int ArrType; // 数组元素类型
struct Node {
ArrType data;
Node* next;
};
typedef Node* SLList; // 定义链表类型
// 将链表 L 中的元素按照关键字 i 的值分配到 f 和 e 数组中
void Distribute(SLList &L,int i,ArrType &f,ArrType &e) {
Node* p = L->next;
while (p) {
int j = (p->data / i) % RADIX;
if (!f[j]) {
f[j] = p->data;
e[j] = p->data;
} else {
Node* q = new Node;
q->data = p->data;
e[j]->next = q;
e[j] = q;
}
p = p->next;
}
}
// 将 f 和 e 数组中的元素按照顺序收集到链表 L 中
void Collect(SLList &L,int i,ArrType f,ArrType e) {
L = new Node;
L->next = nullptr;
Node* tail = L;
for (int j = 0; j < RADIX; j++) {
if (f[j]) {
Node* p = new Node;
p->data = f[j];
tail->next = p;
tail = p;
if (f[j] != e[j]) {
Node* q = f[j]->next;
while (q) {
Node* r = new Node;
r->data = q->data;
tail->next = r;
tail = r;
q = q->next;
}
}
}
}
tail->next = nullptr;
}
// 实现基数排序的主体逻辑
void RadixSort(SLList &L) {
ArrType f, e;
for (int i = 1; i <= 1000; i *= RADIX) {
// 初始化 f 和 e 数组
for (int j = 0; j < RADIX; j++) {
f[j] = e[j] = nullptr;
}
// 分配和收集
Distribute(L, i, f, e);
Collect(L, i, f, e);
}
}
```
以上就是基数排序的具体实现方法,希望能够对你有所帮助!
将结构体改为typedef char Keytype; typedef struct { Keytype keys[MAXNUM_KEY];//关键字 int next; }SLCell;//静态链表的节点类型 typedef struct { SLCell r[MAX_SPACE];//静态链表的可利用空间,0下标是头节点 int keynum;//记录的关键字个数 int recnum;//静态链表的当前长度 }SLList;//静态链表类型 typedef int ArrType[RADIX];//数组类型
好的,根据你的要求,我来将结构体改为 typedef 来定义类型:
```c++
typedef char Keytype;
typedef struct {
Keytype keys[MAXNUM_KEY];
int next;
} SLCell;
typedef struct {
SLCell r[MAX_SPACE];
int keynum;
int recnum;
} SLList;
typedef int ArrType[RADIX];
```
这样就定义了静态链表节点类型 SLCell,静态链表类型 SLList,以及数组类型 ArrType。注意,这里的 MAXNUM_KEY 和 MAX_SPACE 需要在代码中先进行定义。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)