typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
bool InitList(LinkList &L) {
L = NULL;
return true;
}
bool InitList(LinkList &L) {
L = (LNode *) malloc(sizeof(LNode)); //分配一个头结点
if (L == NULL) //内存不足, 分配失败
return false;
L->next = NULL; //申请一个头结点,将指针域置空。
return true;
}
头结点和头指针的区分:不管带不带头结点,头指针始终指向单链表的第一个结点,而头结点是带头结点的单链表中的第一个结点,结点内通常不存储信息。
bool Empty(LinkList L) {
return L == NULL;
}
bool Empty(LinkList L) {
return L->next == NULL;
}
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) return false;
if (i==1) {
LNode *s = (LNode *) malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j = 1; //记录指针p当前在第几结点
p = L; //L指向头结点, 且头结点不存数据
while (p != NULL && j < i - 1) { //循环找到第i-1个结点, 在其后添加数据
p = p->next;
j++;
}
if (p == NULL) return false;
LNode *s = (LNode *) malloc(sizeof(LNode));
s->data = e; //赋值
s->next = p->next; //先将p原先后面的结点 与 新节点s相连接
p->next = s; //再将p的结点 与 新节点s相连接
return true;
}
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) return false;
LNode *p; //指针p指向当前扫描到的结点
int j = 0; //记录指针p当前在第几结点
p = L; //L指向头结点, 且头结点不存数据
while (p != NULL && j < i - 1) { //循环找到第i-1个结点, 在其后添加数据
p = p->next;
j++;
}
if (p == NULL) return false; //判断i的值是否合法
LNode *s = (LNode *) malloc(sizeof(LNode));
s->data = e; //赋值
s->next = p->next; //先将p原先后面的结点 与 新节点s相连接
p->next = s; //再将p的结点 与 新节点s相连接
return true;
}
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) return false;
LNode *s = (LNode *) malloc(sizeof(LNode));
if (s == NULL) return false;
s->data = e;
s->next = p->next;
p->next = s; //将结点s连接在p之后
return true;
}
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) return false;
LNode *p; //指针p指向当前扫描到的结点
int j = 0; //记录指针p当前在第几结点
p = L; //L指向头结点, 且头结点不存数据
while (p != NULL && j < i - 1) { //循环找到第i-1个结点, 在其后添加数据
p = p->next;
j++;
}
return InsertNextNode(p, e );
}
bool InsertPriorNode(LNode *p, int e) {
if (p == NULL) return false;
LNode *s = (LNode *) malloc(sizeof(LNode));
if (s == NULL) return false;
s->next = p->next;
p->next = s; //新结点s连到p之后
s->data = p->data; //将p的值复制到s中
p->data = e; //e赋值给p, 这时候s相当于原先的p, 现在的p为前插的新结点
return true;
}
//L 单链表 i 删除的位序 e 删除的值
bool ListDelete(LinkList &L, int i, int &e) {
if (i < 1) return false;
LNode *p;
int j = 0;
p = L; //L指向头结点
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL) return false; //i的值不合法
if (p->next == NULL) return false; //第i-1个结点后无其他结点
LNode *q = p->next; //令p指向被删除的结点
e = q->data; //用e返回删除结点的值
p->next = q->next; //将q结点从链表中断开
free(q); //释放结点的存储空间
return true;
}
bool ListDeleteWithout(LinkList &L, int i, int &e) {
if (i < 1) return false;
if (i == 1) {
LNode *p = L->next;
e = p->data;
L->data = p->data;
L->next = p->next;
free(p);
return true;
}
LNode *p;
int j = 1;
p = L; //L指向头结点
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL) return false; //i的值不合法
if (p->next == NULL) return false; //第i-1个结点后无其他结点
LNode *q = p->next; //令p指向被删除的结点
e = q->data; //用e返回删除结点的值
p->next = q->next; //将q结点从链表中断开
free(q); //释放结点的存储空间
return true;
}
扩展: 删除结点 *p
要删除某个给定结点 *p, 通常的做法实现从链表的头结点开始顺序找到其前驱结点, 然后执行删除操作, 算法的时间复杂度为O(n)
其实, 删除结点 *p的操作可用删除 *p的后继结点操作来实现, 实质就是将其后继结点的值赋予其身, 然后删除后继结点, 也能使得时间复杂度为O(1)
q = p->next;
p->data = q->data; //q->data也可写成p->next->data
p->next = q->next;
free(q);
重点理解前插和删除的特殊操作
算法思想:从单链表的第一个结点开始,顺着指针域逐个往下搜索,直到找到第 i 个结点为止,否则返回最后一个结点的指针域NULL。
核心代码
// 查找单链表L中第 i 个位置的结点指针
LNode *GetElem(LinkList L, int i) {
if (i < 0) return NULL;
LNode *p;
int j = 0;
p = L;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
算法思想:从单链表的第一个结点开始,依次比较表中各个结点的数据域的值,若某结点数据域的值等于x,则返回该结点的指针并记录结点的位置index;若整个单链表中没有这样的结点,则返回空。
核心代码
/**
* 查找值x在单链表L中的结点指针
* @param L 单链表
* @param e 查找的值
* @param index 值所对应的位置
* @return
*/
LNode *LocateElem(LinkList L, int e, int &index) {
index = 1;
LNode *p = L->next;
while (p != NULL && p->data != e) { //从第1个结点查找data值为e的结点
p = p->next;
index++;
}
return p;
}
算法思想:首先初始化一个单链表,其头结点为空,然后循环插入新结点*s:将s的next指向头结点的下一个结点,然后将头结点的next指向s。
核心代码
LinkList HeadInsert(LinkList &L) {
InitList(L); //初始化单链表
int x;
scanf("%d", &x);
while (x != 9999) {
LNode *s = (LNode *) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中, L为头指针
scanf("%d", &x);
}
return L;
}
需要指出的是,头插法建立的单链表中结点的次序和输入数据的顺序不一致,是相反的。若希望两者的顺序是一致的,则可采用尾插法建立单链表。
算法思想:首先初始化一个单链表,然后声明一个尾指针r,让r始终指向当前链表的尾结点,循环向单链表的尾部插入新的结点*s,将尾指针r的next域指向新结点,再修改尾指针r指向新结点,也就是当前链表的尾结点。最后别忘记将尾结点的指针域置空。
核心代码
LinkList TailInsert(LinkList &L) {
InitList(L); //初始化单链表
int x;
LNode *s, *r = L;
scanf("%d", &x);
while (x != 9999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置为空
return L;
}
算法思想:声明一个指针p,p指向头结点指向的第一个结点,如果p指向的结点不为空,那么长度加一,将p指向下一个结点,直到遍历到最后一个结点为止。
核心代码
int Length(LinkList L) {
int len = 0;
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}
算法思想:声明一个指针p,从头结点指向的第一个结点开始,如果p不为空,那么就输出当前结点的值,并将p指向下一个结点,直到遍历到最后一个结点为止。
核心代码
void PrintList(LinkList L) {
LNode *p = L->next;
while (p) {
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
/**
* @Author JiaHaoHao
* @Date 2022/07/01 12:44
* @ClassName: test11
* @Description: 单链表建立
*/
#include "stdio.h"
#include "stdlib.h"
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
bool InitList(LinkList &L) {
L = (LNode *) malloc(sizeof(LNode));
if (L == NULL)
return false;
L->next = NULL;
return true;
}
/**
* 前插法建立单链表
* @param L
* @return
*/
LinkList HeadInsert(LinkList &L) {
InitList(L); //初始化单链表
int x;
scanf("%d", &x);
while (x != 9999) {
LNode *s = (LNode *) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中, L为头指针
scanf("%d", &x);
}
return L;
}
/**
* 尾插法建立单链表
* @param L
* @return
*/
LinkList TailInsert(LinkList &L) {
InitList(L); //初始化单链表
int x;
LNode *s, *r = L;
scanf("%d", &x);
while (x != 9999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置为空
return L;
}
//打印链表
void PrintList(LinkList L) {
LNode *p = L->next;
while (p) {
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
/**
* 按位序查找
* @param L
* @param i
* @return
*/
LNode *GetElem(LinkList L, int i) {
if (i < 0) return NULL;
LNode *p;
int j = 0;
p = L;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
/**
* 按值查找
* @param L 单链表
* @param e 查找的值
* @param index 值所对应的位置
* @return
*/
LNode *LocateElem(LinkList L, int e, int &index) {
index = 1;
LNode *p = L->next;
while (p != NULL && p->data != e) { //从第1个结点查找data值为e的结点
p = p->next;
index++;
}
return p;
}
//表长
int Length(LinkList L) {
int len = 0;
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}
int main() {
LinkList L;
// HeadInsert(L); //头插法建立
TailInsert(L); //尾插法建立
PrintList(L); //打印链表;
int i = 3;
printf("第%d个值为%d\n", i, GetElem(L, i)->data);
int e = 4;
int index = -1;
LocateElem(L, e, index);
printf("值为%d的结点为%d\n", e, index);
printf("表长: %d\n", Length(L));
return 0;
}
运行结果
// 尾插法创建
C:\Users\User\Desktop\dataStructure\cmake-build-debug\01xianxingbiao11.exe
1 5 9 8 4 5 6 2 1 4 9999
1 5 9 8 4 5 6 2 1 4
第3个值为9
值为4的结点为5
表长: 10
Process finished with exit code 0