行业知识
笔记-线性表-链表-单链表的定义 建立 插入 删除 查找
���：
（）本文若未声明是否带头结点的代码，默认都是带头结点的
定义
相对于顺序表：
（）优点：不需要大片连续的空间，改变表长方便
缺点：不可以随机存取，要耗费一定的存储空间存放指针
单链表的简单模型：
| a1 | 指针指向a2 | a2 | 指针指向a3 | a3 | NULL |
a1也会有一个指针指向，每一个结点的存储空间包括：数据元素+指向下一个结点的指针
代码：
定义一个单链表结点
struct LNode{ //定义单链表结点类型 ElemType data; //数据域：存放数据元素（每个节点存放一个数据元素） struct LNode *next; //指针域：存放指向下一个结点的指针} 增加新结点要在内存中申请结点所需的空间，并且用一个指针指向这个结点
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));
创造一个新的结点，并用指针p指向这个结点
可以使用typedef将数据类型重命名来简化操作
typedef struct LNode LNode; //typedef关键字+数据类型struct LNode+别名LNodeLNode *p=(LNode *)malloc(sizeof(LNode));
也可以这样进行替代
typedef struct LNode{ ElemType data; struct LNode *next;}LNode, *LinkList;//等价于struct LNode{ ElemType data; struct LNode *next;};typedef struct LNode LNode;typedef struct LNode *LinkList; 这种替代方式，可以让想定义结点时候，强调返回的是结点就用LNode定义，强调定义的是单链表就用LinkList定义
查找单链表L的第i个元素：（带头节点）
typedef struct LNode{ int data; struct LNode *next;}LNode, *LinkList;LNode* GetElem(LinkList L, int i) { int j = 1; LNode* p = L->next; //1 if (i == 0) //2 return L; if (i next; j++; } return p; //5} 函数的两个参数：指向单链表头节点的指针L 元素的位序i
1 先定义一个p指针指向头节点的下一个节点
2 如果查找的是第零个元素的位置，则直接返回头节点L
3 如果查找的位置是负数，则判断查找的数据不合理
4 如果p指针不是指向空位置（链表还有数据），p指针就一直移动到第i个位置，即p指针此时指向第i个元素，就可以直接返回p得出该元素
打印链表的数据
void printList(LNode *L) { LNode *p = L->next; // 跳过头节点 while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n");} 求表长
int length(LinkList L) { int len = 0; LNode* p = L; while (p->next != NULL) { p = p->next; len++; } return len;} 建立
判断单链表是否为空
bool Empty(LinkList L) { if (L == NULL) return true; else return false;}//或者bool Empty(LinkList L) { return (L == NULL);} 初始化单链表：
不带头结点：
bool InitL(LinkList& L) { L = NULL; //保证链表是空的 return true;} 带头结点：
bool InitL(LinkList& L) { L = (LNode*)malloc(sizeof(LNode)); //分配头结点空间 if (L == NULL) //内存不足分配失败 return false; L->next = NULL; //保证头结点下一个指向一个空位，单链表是空的 return true;} 头结点可以方便为什么进行操作，头结点本身不存储数据
头插法建立单链表：
LinkList List_Head(LinkList &L) { LNode* s; int x; L = (LinkList)malloc(sizeof(LNode)); //1 L->next = NULL; //2 printf("输入第一个节点的值："); scanf("%d", &x); //3 while (x != 000) { //4 s = (LNode*)malloc(sizeof(LNode)); //5 s->data = x; //6 s->next = L->next; //7 L->next - s; //8 printf("请输入下面的节点值（输入000结束输入）："); scanf("%d", &x); //9 } return L; } 1 创建头结点，为其分配空间
2 头结点的下一个指向一个空位置，保证链表初始是空的
3 输入第一个节点的值
4 接下来输入其他节点的值，设置一个规则：输入000即可结束输入
5 为接下来的节点分配空间
6 保存之前输入过的值，存到下一个新节点
7 8 将新的节点插入到头结点之后
9 输入下一个节点的值，依次循环，如果输入000就结束输入
头插法的作用：链表的逆置
尾插法建立单链表：
LinkList List_Tail(LinkList& L) { int x; L = (LinkList)malloc(sizeof(LNode)); LNode* s, * r = L; //1 scanf("%d", &x); while (x != 000) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; //2 r = s; //3 printf("请输入下面的节点值（输入000结束输入）："); scanf("%d", &x); } r->next = NULL; //4 return L;} 1 开始s和r都指向头结点，r指针会在后面作为表尾指针
2 将新的节点，插入到尾结点的后面
3 更新尾结点为新插入的节点
4 尾结点指针置空
插入
按位序插入
带头结点
bool ListInsert(LinkList& L, int i,int e) { if (i next; j++; } if (p == NULL) return false; LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; //5 s->next = p->next; //6 p->next = s; //7 return true;} 1 设置一个指针p，指向当前扫描到的结点
2 设置一个计数器，表示当前指向的是第几个结点
3 将p结点指向头结点，这个时候计数器是0，依据这个定义进行下面的循环判断
4 循环到第i个元素停止，下面就进行插入了
5 先将e值赋给s指向的数据域
6 将第i个节点的下一个置给新的节点
7 将原来的第i个节点的下一个指向新的节点
67两步完成了对s的插入
平均时间复杂度：O（n）
不带头结点
bool ListInsertNohead(LinkList& L, int i, int e) { if (i data = e; s->next = L; L = s; return true; } LNode* p; int j = 1; p = L; while (p != NULL && j next; j++; } if (p == NULL) { return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; //3 s->next = p->next; p->next = s; return true;} 1 插入第一个节点的操作和其他的节点操作不一样，所以要单独拎出来，要把元素e值赋给s的数据域，并且用头指针指向新的节点
2 指针扫描到第i个结点
3 逻辑和带头结点的一样不再赘述
很明显不带头结点的更加不方便，所以我们尽量都要带头结点
平均时间复杂度：O（n）
指定节点的插入
前插
bool InsertPriorNode(LNode* p, int e) { if (p == NULL) return false; LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) //1 return false; s->next = p->next; //2 p->next = s; //3 s->data = p->data; //4 p->data = e; //5 return true; //6} 1 内存分配失败导致插入失败
2 将新节点s的下一个指向的设置为原来p结点下一个指向的东西
3 将p节点的下一个指向新的节点s，完成s的插入
4 将p的数据赋给新节点s
5 将e赋给p节点，作为p位置的新值
形成实际上的将e插到了p的前面（实际上是e代替了原来p的位置，但是将p赋到了新的节点，这个节点在原来p的后面）
时间复杂度：O（1）
后插
bool InsertNextNode(LNode* p, int e) { if (p == NULL) return false; LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) //1 return false; s->data = e; s->next = p->next; p->next = s; return true;} 将s节点插入到p的后面
1 某些情况下可能会有分配失败的情况，例如内存不足
时间复杂度：O（1）
删除
按位序删除
bool ListDelete(LinkList& L, int i,int& e) { if (i next; j++; } if (p == NULL) return false; if (p->next == NULL) return false; LNode* q = p->next; //2 e = q->data; //3 p->next = q->next; //4 free(q); //5 return true;} 还未删除时是这样的
p q q的下一个节点
↑
要被删除的
1 循环到第i-1个结点（p这是指向的不是要被删除的节点）
2 设置一个新的节点q指向被删除的节点
3 用e来存放将被删除的节点的数据域并且我们这个函数要使用这个值，所以在定义的时候要加&
4 将p指向的节点的下一个设置为q下一个节点，这里就相当于把q从链表的链中剔除了
5 删除p节点（要被删除的第i个基点）
指定节点的删除
void DeletNodeP(LinkList L, LNode*p) { LNode* pre = L; LNode* thisone = L->next; while (thisone != NULL) { if (thisone == p) { //1 pre->next = thisone->next; free(thisone); break; } pre = thisone; thisone = thisone->next; }} 也是设置两个指针，一个是当前节点一个是前一个节点
1 当设置的thisone和p是一个位置时进行对p的删除操作
我们来展示一下王道上面的解决方法：
bool DeletNode(LNode* p) { if (p == NULL) return false; LNode* q = p->next; p->data = p->next->data; //1 p->next = q->next; free(q); return true;} 这种方法的局限在于，如果要删除的是最后一个节点，那只能另外处理这种情况
1 如果是最后一个节点的next是没有数据的，所以这句代码没有办法操作
但是好处是时间复杂度为O（1），不需要循环处理非常方便
我这种方法需要循环，时间复杂度高一些，所以大家自行取舍
指定数据的删除
void DeletNode(LinkList& L, int e) { LNode* p = L->next; //1 LNode* q = L; while (p != NULL) { if (p->data == e) { //2 q->next = p->next; free(p); p = q->next; //3 } else { //4 q = p; p = p->next; } }} 1 设置两个指针，一个p指向当前节点，一个q指向p的前一个节点（删除时会使用q）
2 如果遍历过程中发现了数据域等于e的位置， 就进行p的删除
3 p删除之后继续遍历寻找是否还有跟e相等的位置继续删除
4 当前节点不是e的值时，就继续遍历
查找
按位查找
返回第i个元素的值
完整代码
LNode* GetElem(LinkList L, int i) { if (i next; j++; } return p;} 1 设置一个指针p，指向当前扫描到的节点
2 定义一个j，让j作为计数器，指示出当前p指向的第几个结点
3 p设置在头结点上开始（并且上面j设置为0，表示头结点是第0个节点）
4 循环找到第i个结点
时间复杂度
O（n）
按值查找
找到数据域等于e的结点
完整代码
LNode* LocateElemData(LinkList L, int e) { LNode* p = L->next; //1 while (p != NULL && p->data != e) //2 p = p->next; return p;} 1 设置一个p指针从第一个数据域开始依次比较
2 p指针指的数据不等于e就依次下移动，直到有一个数据等于e即得出结果
最后p指针只会返回结点指针，或者NULL
时间复杂度
O（n）
参考资料：
王道考研 数据结构
下一篇：手机云端服务器怎么安装?
