调整链表元素,不可避免且最常见的操作就是调整某个确定链表中元素的位序,需要注意以下几点:
1. 防止在调整过程中形成闭环导致无限循环
2. 防止在调整过程中导致被调整元素后的元素内存地址丢失
针对这两个问题,我们通常会设立辅助指针变量,对于问题一,我们设立一个pre指针,该指针始终指向被调整元素节点的前驱节点,用于切断前驱节点与被调整节点之间的链,从而防止闭环的出现,对于问题二,我们设立一个pro指针,该指针始终指向被调整元素的后继节点,防止该节点与后继节点断链后,丢失地址,因此这类问题我们一般都是设立三个指针:
一个用于防止闭环出现(通常仅在循环外部使用一次,断链防闭环),一个用于循环遍历整个链表进行操作(即while循环中的条件),另一个用于防止丢失地址
针对这个方法,看一个例题,基于直接插入排序对单链表进行排序的算法
void sortLinklist(Linklist &L) {
Linklist p, pro, ppro;
p = L->next; //p指向已有序序列的最后一个元素节点
pro = p->next;//pro指向待排序序列的第一个节点
ppro = pro->next;//ppro指向pro的下一个节点,防止断链后位置丢失
Linklist pre = L; // pre用于在有序序列中循环遍历确认插入的位置
p->next = NULL; //第一个数据节点指针置空
while (pro) {
ppro = pro->next;
pro->next = NULL;
ElemType temp = pro->data;
while (pre->next != NULL && pre->next->data < temp) {
pre = pre->next;
}
pro->next = pre->next;
pre->next = pro;
pro = ppro;
//if(ppro){ ppro = ppro->next; }
}
printListWithNoLeaderNode(L);
}
再一个例题:对链表就地逆置(就地:即空间复杂度为O(1)的算法)
void reverseLinklist(Linklist &L) {
Linklist p, q, proq;
p = L->next;
q = p->next;
proq = q->next;
p->next = NULL;
while (q) {
q->next = NULL;
q->next = L->next;
L->next = q;
q = proq;
if (proq != NULL) { proq = proq->next; }
}
printListWithNoLeaderNode(L);
}
两个题需要特别注意的是:在被处理节点的前驱节点指针不断后移的过程中,要避免出现空指针异常,通常有两种设置方法:
1. 在循环代码段的开始部分就进行后移
2.在循环代码段结束部分通过if语句来限定指针的移动
最后,附上基本接口
#define _CRT_SECURE_NO_WARNINGS #include#include #define MaxSize 20 #define ElemType int typedef struct LNode { ElemType data; struct LNode* next; }LNode, * Linklist; typedef struct { ElemType data[MaxSize]; int top; }SqStack; //基本接口 Linklist createSingleLinklistByTileInsert(Linklist& L) { Linklist s; L = (LNode*)malloc(sizeof(LNode)); LNode* r = L; int x; printf("Please enter the text you need!"); scanf("%d", &x); while (x != 9999) { s = (Linklist)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; printf("Please enter the text you need!"); scanf("%d", &x); } r->next = NULL; return L; } Linklist creatSinglleLinklistWithNoLeaderByTileInsert(Linklist& L) { int f, x; L = (LNode*)malloc(sizeof(LNode)); Linklist s, r = L; printf("请确定第一个节点的值:"); scanf("%d", &f); L->data = f; printf("Please enter the text you need!"); scanf("%d", &x); while (x != 9999) { s = (Linklist)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; printf("Please enter the text you need!"); scanf("%d", &x); } r->next = NULL; return L; } void printListWithNoLeaderNode(Linklist L) { Linklist p = L->next; while (p) { printf("%3d", p->data); p = p->next; } } void InitStack(SqStack& S) { S.top = -1; } bool push(SqStack &S,ElemType x) { if (S.top == MaxSize - 1) { return false; } S.data[++S.top] = x; return true; } bool pop(SqStack& S, ElemType& x) { if (S.top == -1) { return false; } x = S.data[S.top--]; return true; } bool isEmpty(SqStack S) { if (S.top == -1) { return true; } else { return false; } } //基本接口



