单链表是通过一组任意的存储单元来存储线性表中的数据元素的。每个元素包括两部分：存放数据元素的域值为数据域data，存放其后继地址的域称为指针域next。
显然，除第一个元素外，每个元素都有一个直接前驱。为方便操作，一般设一个头指针H指向第一个结点；除最后一个元素外，每个元素都有一个直接后继。为方便操作，指定线性表中最后一个结点的指针域为"空"(NULL)。
单链表的存储结构用C语言描述如下：
typedef int ElemType; // 自定义链表的数据元素为整数。
typedef struct LNode
{
ElemType data; // 存放结点的数据元素。
struct LNode* next; // 指向下一个结点的指针。
}LNode, * LinkList;
//定义头指针变量
LinkList H;
上面的LNode是结点的类型，LinkList是指向LNode类型结点的指针类型。
通常用头指针来标识一个单链表，如单链表H。是指该链表的第一个结点的地址放在了指针变量H中，头指针为NULL，则表示一个空表。
Part2：代码解释关于单链表的操作，主要掌握以下几点：
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include typedef int ElemType; // 自定义链表的数据元素为整数。 typedef struct LNode { ElemType data; // 存放结点的数据元素。 struct LNode* next; // 指向下一个结点的指针。 }LNode, * LinkList; int main() { LinkList LL = NULL; // 声明链表指针变量。 LL = InitList1(); // Way1:初始化链表 // InitList2(&LL); // Way2:初始化链表，传入指针变量LL的地址。 ElemType ee; // 创建一个数据元素。 return0; }
这部分就是单链表的存储结构，LNode是结点的类型，LinkList是指向LNode类型结点的指针类型。
2.初始化链表 2.1Way1// 初始化链表LL，返回值：失败返回NULL，成功返回头结点的地址。
LNode* InitList1()
{
LNode* head = (LNode*)malloc(sizeof(LNode)); // 分配头结点。
if (head == NULL) return NULL; // 内存不足，返回失败。
head->next = NULL; // 头结点的下一结点暂时不存在，置空。
return head;
}
初始化链表，函数的返回类型为LNode*，即初始化成功，就返回头结点的地址。malloc动态内存开辟，开辟多大空间呢？用sizeof(LNode)进行计算；强制类型转换为LNode*，赋给头结点head，头结点的类型也是LNode*。
如果头结点为空，则说明内存不足，返回失败；否则，就将头结点的下一个节点置空，返回头结点的地址。
2.2Way2// 传入指针变量的地址的方法。
// 初始化链表，返回值：0-失败；1-成功。
int InitList2(LinkList* LL)
{
// 在本函数中，LL是指针的指针，用于存放指针的地址。
if (*LL != NULL) { printf("链表LL已存在，在初始化之前请先释放它。n"); return 0; }
LNode* head = (LNode*)malloc(sizeof(LNode)); // 分配头结点。
if (head == NULL) return 0; // 内存不足，返回失败。
head->next = NULL; // 头结点的下一结点暂时不存在，置空。
*LL = head;
return 1;
}
第二种初始化方法，直接将链表的指针变量传入，用一个指针接受，则在本函数中，LL就是指针的指针，用于存放指针的地址。函数内的操作与第一种方法类似，不同之处在于第一种方法是返回头结点的地址，在main函数中赋给LL；而该方法则是在函数内部就将头结点地址赋给LL，返回1表示初始化成功。
3.求链表长度// 求链表的长度，返回值：>=0-表LL结点的个数。
int LengthList(LinkList LL)
{
if (LL == NULL) { printf("链表LL不存在。n"); return 0; } // 判断链表是否存在。
LNode* pp = LL->next; // 头结点不算，从第1个结点开始。
int length = 0;
while (pp != NULL)
{
pp = pp->next;
length++;
}
return length;
}
- 判断链表是否存在；
- 创建指针指向链表第一个结点，同时创建临时变量，指针后移的同时临时变量自增；
- 返回链表的长度
// 在链表LL的第ii个位置插入元素ee，返回值：0-失败；1-成功。
int InsertList(LinkList LL, unsigned int ii, ElemType* ee)
{
if ((LL == NULL) || (ee == NULL)) { printf("链表LL或元素ee不存在。n"); return 0; } // 判断表和元素是否存在。
// 判断插入位置是否合法
if (ii < 1) { printf("插入位置（%d）不合法，应该在大于0。n", ii); return 0; }
// 要在位序ii插入结点，必须找到ii-1结点。
LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。
while ((pp != NULL) && (kk < ii - 1))
{
pp = pp->next; kk++;
// printf("pp=%p,kk=%dn",pp,kk);
}
if (pp == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return 0; }
LNode* tmp = (LNode*)malloc(sizeof(LNode)); // 分配一个结点。
if (tmp == NULL) return 0; // 内存不足，返回失败。
// 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。
memcpy(&tmp->data, ee, sizeof(ElemType));
// 处理next指针。
tmp->next = pp->next;
pp->next = tmp;
return 1;
///
// 以上代码可以用以下代码代替。
// LNode *pp=LocateNode(LL,ii-1);
// return InsertNextNode(pp,ee);
///
}
- 首先，保证传入的链表和元素存在；
- 其次，插入的位置必须大于0；
- 注意：在单链表上插入、删除一个结点时，必须知道其前驱节点；所以让指针pp指向头结点，此时kk为0；pp逐步后移，每后移一次，kk自增1。直到找到要插入位置的前驱结点，就跳出循环。
- 此时进行判断，如果pp是空空指针，说明要插入的位置超过表长，非法；
- 跳过层层判断，此时我们找到了要插入位置的前一个结点，我们分配一个新结点，data数据域放我们要插入的元素，next指针进行相对应的处理即可。由下图，可更容易理解这两行代码。
- 插入成功，最后返回1，插入元素的函数就完成了！
next指针处理方式图解：
// 在链表LL的头部插入元素ee，返回值：0-失败；1-成功。
int PushFront(LinkList LL, ElemType* ee)
{
return InsertList(LL, 1, ee);
}
这个容易，只需将插入的位置传入参数1即可。
4.3在表尾插入元素// 在链表LL的尾部插入元素ee，返回值：0-失败；1-成功。
int PushBack(LinkList LL, ElemType* ee)
{
if ((LL == NULL) || (ee == NULL)) { printf("链表LL或元素ee不存在。n"); return 0; } // 判断表和元素是否存在。
LNode* pp = LL; // 从头结点开始。
// 找到最后一个结点。
while (pp->next != NULL) pp = pp->next;
LNode* tmp = (LNode*)malloc(sizeof(LNode)); // 分配一个结点。
if (tmp == NULL) return 0; // 内存不足，返回失败。
// 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。
memcpy(&tmp->data, ee, sizeof(ElemType));
// 处理next指针。
tmp->next = NULL;
pp->next = tmp;
return 1;
}
- 由于不知道链表的长度，所以不能使用已有的InsertList函数。
- 首先，保证传入的链表和元素存在；
- 然后，创建指针pp,指向头结点并不断后移，直到找到最后一个结点。
- 分配一个新的结点，data数据域放我们要插入的元素，将新结点的next域置为NULL，并让原来最后一个结点的next域存储新的结点地址。
- 插入成功，返回1即可。
若结合已有的求链表长度的函数，则该函数也可以改写为：
// 在链表LL的尾部插入元素ee，返回值：0-失败；1-成功。
int PushBack(LinkList LL, ElemType* ee)
{
int len = LengthList(LL);
return InsertList(LL, len+1, ee);
}
这里注意传入的第二个参数是len+1，如果传入len，那么在链表的最后一个位置插入元素，则原先的表尾元素会向后移一位，就变成在倒数第二个位置插入元素了。
5.删除元素 5.1在任意位置删除元素// 删除链表LL中的第ii个结点，返回值：0-位置ii不合法；1-成功。
int DeleteNode(LinkList LL, unsigned int ii)
{
if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。
// 判断删除位置是否合法
if (ii < 1) { printf("删除位置（%d）不合法，应该在大于0。n", ii); return 0; }
// 要删除位序ii结点，必须找到ii-1结点。
LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。
while ((pp != NULL) && (kk < ii - 1))
{
pp = pp->next; kk++;
}
if (pp->next == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return 0; }
LNode* tmp = pp->next; // tmp为将要删除的结点。
pp->next = pp->next->next; // 写成pp->next=tmp->next更简洁。
free(tmp);
return 1;
}
参考向链表中插入元素，对next指针的处理方式如下：
// 删除链表LL中第一个结点，返回值：0-位置不合法；1-成功。
int PopFront(LinkList LL)
{
return DeleteNode(LL, 1);
}
5.3在链表尾部删除元素
// 删除链表LL中最后一个结点，返回值：0-位置不合法；1-成功。
int PopBack(LinkList LL)
{
if (LL == NULL) { printf("链表LL不存在。n"); return 0; } // 判断表和元素是否存在。
// 必须加上这个判断，否则下面的循环pp->next->next不成立。
if (LL->next == NULL) { printf("链表LL为空，没有尾结点。n"); return 0; } // 判断表是否为空。
// 要删除最后一个结点，必须找到最后一个结点的前一个结点。
LNode* pp = LL; // 从第0个结点开始。
// 找到倒数第二个结点（包括头结点）。
while (pp->next->next != NULL) pp = pp->next;
// 释放最后一个结点。
free(pp->next);
pp->next = NULL;
return 1;
}
由于表长未知，任从头结点开始，找到倒数第二个结点，将最后一个结点释放，并将倒数第二个结点的next指针域置为NULL。当然，如果结合已有的求链表长度的函数，也可以简化该函数。
6.查找某一位置的元素及地址// 获取链表中第ii个结点，成功返回结点的地址，失败返回空。
// 注意，ii可以取值为0，表示头结点。
LNode* LocateNode(LinkList LL, unsigned int ii)
{
if (LL == NULL) { printf("链表LL不存在。n"); return NULL; } // 判断表和元素是否存在。
LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。
while ((pp != NULL) && (kk < ii))
{
pp = pp->next; kk++;
}
if (pp == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return NULL; }
return pp;
}
也是设置一个结点pp，不断向后找；当kk=0时，进入while循环，pp已经指向了第1个结点；kk=1时，pp则指向第2个结点。依此类推，要找ii位置的结点，则最后一次循环时kk=i-1。
7.查找某一元素的地址// 查找元素ee在链表LL中的结点地址，如果没找到返回NULL，否则返回结点的地址。
LNode* LocateElem(LinkList LL, ElemType* ee)
{
LNode* pp = LL->next; // 从第1个数据结点开始。
while (pp != NULL)
{
// 如果数据元素是结构体，以下代码要修改。
if (pp->data == *ee) return pp;
pp = pp->next;
}
return NULL;
}
查找某一元素的地址，从第一个结点开始，依次向后，如果pp->data==*ee，说明已经找到相应的元素，就返回pp的值。当然，也可以从头结点开始查找。
8.根据结点插入元素无论插入还是删除元素，都要找到该结点的前一个结点！
8.1在指定结点后插入元素// 在指定结点pp之后插入元素ee，返回值：0-失败；1-成功。
int InsertNextNode(LNode* pp, ElemType* ee)
{
if (pp == NULL) { printf("结点pp不存在。n"); return 0; }
LNode* tmp = (LNode*)malloc(sizeof(LNode));
if (tmp == NULL) return 0;
memcpy(&tmp->data, ee, sizeof(ElemType));
tmp->next = pp->next;
pp->next = tmp;
return 1;
}
只要是插入元素，一定需要分配新的内存空间给要插入的结点(即这里的tmp)。图解如下：
// 在指定结点pp之前插入元素ee，返回值：0-失败；1-成功。
int InsertPriorNode(LNode* pp, ElemType* ee)
{
if (pp == NULL) { printf("结点pp不存在。n"); return 0; }
// 在指定结点pp之前插入采用偷梁换柱的方法：
// 1、分配一个新的结点；
// 2、把pp结点的数据和指针复制到新结点中。
// 3、把待插入元素的数据存入pp结点中。
LNode* tmp = (LNode*)malloc(sizeof(LNode));
if (tmp == NULL) return 0;
// 把pp结点的数据和指针复制到tmp中。
memcpy(&tmp->data, &pp->data, sizeof(ElemType));
tmp->next = pp->next;
// 把待插入的元素存入pp中。
memcpy(&pp->data, ee, sizeof(ElemType));
pp->next = tmp;
return 1;
}
因为我们只能找到指定结点之后的元素，而无法找到指定结点之前的元素，所以在指定结点之前插入元素，采用偷梁换柱的方法。图解如下：
//删除指定元素，返回值：0-失败；1-成功。
int DeleteElem(LinkList LL, ElemType* ee)
{
if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。
// 要删除位序ii结点，必须找到ii-1结点。
LNode* pp = LL->next; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。
while ((pp != NULL) && (pp->next->data!=(*ee)))
{
pp = pp->next;
}
// 注意，以下行的代码与视频中的不一样，视频中的是 if ( pp==NULL )，有bug。
if (pp->next == NULL) { printf("元素不存在，无法删除！n"); return 0; }
LNode* tmp = pp->next; // tmp为将要删除的结点。
pp->next = tmp->next;
free(tmp);
return 1;
}
参考按结点删除元素，不难理解。
10.翻转链表// 把链表pp结点之后的结点原地逆置（反转），返回值：0-失败；1-成功。
void ReverseList(LNode* pp)
{
LNode* ss; // 当前结点。
LNode* ssnext; // 当前结点的下一结点。
ss = pp->next; // 从pp结点之后的结点开始反转。
pp->next = NULL; // pp->next指向空。
while (ss != NULL)
{
ssnext = ss->next; // 保留ss下一结点的地址。
// 以下两行相当于在pp之后插入ss结点。
ss->next = pp->next;
pp->next = ss;
ss = ssnext; // ss结点后移。
}
}
把pp结点之后的结点进行翻转，相当于把pp结点之后的元素逐个紧跟在pp结点后插入，其逻辑类似于：
while循环图解：
(假设将第2个结点之后的结点进行翻转)
注意：第一次循环，pp->next=NULL;
循环部分不容易理解，可以结合图例进行思考。
11.合并链表// 采用归并的方法，将两个升序的链表La和Lb，合并成一个升序的链表Lc。
int MergeList(LinkList La, LinkList Lb, LinkList Lc)
{
if ((La == NULL) || (Lb == NULL) || (Lc == NULL)) { printf("表La、Lb、Lc至少有一个不存在。n"); return 0; }
La = La->next; //从第一个结点开始
Lb = Lb->next; //从第一个结点开始
LNode* pp;
// 把La和Lb合并到Lc中。
while ((La != NULL) && (Lb != NULL))
{
// 取La和Lb的较小者。
if (La->data <= Lb->data)
{
pp = La; La = La->next;
}
else
{
pp = Lb; Lb = Lb->next;
}
// 把较小者追加到Lc中。
Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。
Lc = Lc->next;
memcpy(&Lc->data, &pp->data, sizeof(ElemType));
Lc->next = NULL;
}
// 把链表La其它的元素追加到Lc中。
while (La != NULL)
{
Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。
Lc = Lc->next;
memcpy(&Lc->data, &La->data, sizeof(ElemType));
Lc->next = NULL;
La = La->next;
}
// 把链表Lb其它的元素追加到Lc中。
while (Lb != NULL)
{
Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。
Lc = Lc->next;
memcpy(&Lc->data, &Lb->data, sizeof(ElemType));
Lc->next = NULL;
Lb = Lb->next;
}
return 1;
}
结合前面顺序表的合并操作，不难理解链表的合并。
12.清空链表// 清空链表。
void ClearList(LinkList LL)
{
// 清空链表LL是指释放链表全部的结点，但不包括头结点。
if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。
LNode* tmp1;
LNode* tmp2 = LL->next; // 保留头结点，从头结点的下一个结点开始释放。
while (tmp2 != NULL)
{
tmp1 = tmp2->next;
free(tmp2);
tmp2 = tmp1;
}
LL->next = NULL; // 这行代码一定不能少，否则会留下野指针。
对于清空链表，因为传入的是链表的头结点，所以需要创建两个指针变量，rmp1进行移动，tmp2存储链表的第一个结点。tmp1不断向后移动，找下一个结点；tmp2则负责释放相应的内存空间。需要注意的是在最后需要把LL->next置为空，防止野指针出现。
13.销毁链表Way1：
// 销毁链表LL。
void DestroyList1(LinkList LL)
{
// 销毁链表LL是指释放链表全部的结点，包括头结点。
LNode* tmp;
while (LL != NULL)
{
tmp = LL->next; // tmp保存下一结点的地址。
free(LL); // 释放当前结点。
LL = tmp; // LL指针移动到下一结点。
}
// LL=NULL; // LL在本函数中相当于局部变量，就算置空了也不会影响调用者传递的LL，所以LL=NULL没有意义。
return;
}
对于销毁链表，不需要额外的指针变量存储链表第1个结点的信息，所以只需要一个指针变量，不断向后移动，并释放其所指向的内存空间。
Way2：
// 销毁链表LL。
void DestroyList2(LinkList* LL)
{
// 如果函数的参数是指针的指针，可以启用以下代码。
LNode* tmp1, * tmp2;
tmp1 = *LL;
while (tmp1 != NULL)
{
tmp2 = tmp1->next; // tmp保存下一结点的地址。
free(tmp1); // 释放当前结点。
tmp1 = tmp2; // LL指针移动到下一结点。
}
*LL = NULL; // 把链表的指针置为空，表示链表不存在了。
return;
}
传入指针变量。
Part3：完整代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include typedef int ElemType; // 自定义链表的数据元素为整数。 typedef struct LNode { ElemType data; // 存放结点的数据元素。 struct LNode* next; // 指向下一个结点的指针。 }LNode, * LinkList; void menu() { printf("*************************************************n"); printf("***** 0.Exit 1.LengthList *******n"); printf("***** 2.Insert 3.PushFront *******n"); printf("***** 4.PushBack 5.Delete *******n"); printf("***** 6.PopFront 7.PopBack *******n"); printf("***** 8.IsEmpty 9.LocateNode *******n"); printf("*****10.LocateElem 11.MergeList *******n"); printf("*****12.InsertNextNode 13.InsertPriorNode *******n"); printf("*****14.ReverseList 15.DeleteElem *******n"); printf("*****16.ClearList *******n"); printf("*************************************************n"); } // 初始化链表LL，返回值：失败返回NULL，成功返回头结点的地址。 LNode* InitList1(); // 传入指针变量的地址的方法。 // 初始化链表，返回值：0-失败；1-成功。 int InitList2(LinkList* LL); // 销毁链表LL。 void DestroyList1(LinkList LL); // 销毁链表LL。 // 传入指针的地址的方法。 void DestroyList2(LinkList* LL); // 清空链表。 void ClearList(LinkList LL); // 在链表LL的第ii个位置插入元素ee，返回值：0-失败；1-成功。 int InsertList(LinkList LL, unsigned int ii, ElemType* ee); // 打印链表中全部的元素。 void PrintList(LinkList LL); // 在链表LL的头部插入元素ee，返回值：0-失败；1-成功。 int PushFront(LinkList LL, ElemType* ee); // 在链表LL的尾部插入元素ee，返回值：0-失败；1-成功。 int PushBack(LinkList LL, ElemType* ee); // 删除链表LL中的第ii个结点，返回值：0-位置ii不合法；1-成功。 int DeleteNode(LinkList LL, unsigned int ii); // 删除链表LL中第一个结点，返回值：0-位置不合法；1-成功。 int PopFront(LinkList LL); // 删除链表LL中最后一个结点，返回值：0-位置不合法；1-成功。 int PopBack(LinkList LL); // 求链表的长度，返回值：>=0-表LL结点的个数。 int LengthList(LinkList LL); // 判断链表是否为空，返回值：0-非空或失败，1-空。 int IsEmpty(LinkList LL); // 获取链表中第ii个结点，成功返回结点的地址，失败返回空。 // 注意，ii可以取值为0，表示头结点。 LNode* LocateNode(LinkList LL, unsigned int ii); // 查找元素ee在链表LL中的结点地址，如果没找到返回NULL，否则返回结点的地址。 LNode* LocateElem(LinkList LL, ElemType* ee); // 在指定结点pp之后插入元素ee，返回值：0-失败；1-成功。 int InsertNextNode(LNode* pp, ElemType* ee); // 在指定结点pp之前插入元素ee，返回值：0-失败；1-成功。 int InsertPriorNode(LNode* pp, ElemType* ee); //删除指定元素ee，返回值：0-失败；1-成功。 int DeleteElem(LNode* pp, ElemType* ee); // 采用归并的方法，将两个升序的链表La和Lb，合并成一个升序的链表Lc。 int MergeList(LinkList La, LinkList Lb, LinkList Lc); // 把链表pp结点之后的结点原地逆置（反转），返回值：0-失败；1-成功。 void ReverseList(LNode* pp); int main() { LinkList LL = NULL; // 声明链表指针变量。 LL = InitList1(); // Way1:初始化链表 // InitList2(&LL); // Way2:初始化链表，传入指针变量LL的地址。 //printf("LL=%pn", LL); ElemType ee; // 创建一个数据元素。 printf("在表中插入元素（1、2、3、4、5、6、7、8、9、10）。n"); ee = 1; InsertList(LL, 1, &ee); ee = 2; InsertList(LL, 1, &ee); ee = 3; InsertList(LL, 1, &ee); ee = 4; InsertList(LL, 1, &ee); ee = 5; InsertList(LL, 1, &ee); ee = 6; InsertList(LL, 1, &ee); ee = 7; InsertList(LL, 1, &ee); ee = 8; InsertList(LL, 1, &ee); ee = 9; InsertList(LL, 1, &ee); ee = 10; InsertList(LL, 1, &ee); PrintList(LL); int input = 0; int count = 0; menu(); do { count++; if (count % 5 == 0) { menu(); } printf("请选择:"); scanf("%d", &input); switch (input) { case 0: DestroyList1(LL); LL = NULL; break; case 1: int length = LengthList(LL); printf("链表的长度为:%dn", length); break; case 2: int x = 0; int y = 0; printf("依次输入插入的位置及插入的元素:>"); scanf("%d %d", &x, &y); printf("在第%d个位置插入元素%dn", x, y); ee = y; InsertList(LL, x, &ee); PrintList(LL); break; case 3: int w = 0; printf("在表头插入元素:>"); scanf("%d", &w); ee = w; PushFront(LL, &ee); PrintList(LL); break; case 4: int u = 0; printf("在表尾插入元素:>"); scanf("%d", &u); ee = u; PushBack(LL, &ee); PrintList(LL); break; case 5: int b = 0; printf("删除表中第几个元素:>"); scanf("%d", &b); DeleteNode(LL, b); PrintList(LL); break; case 6: printf("删除第一个元素。n"); PopFront(LL); PrintList(LL); break; case 7: printf("删除表尾元素。n"); PopBack(LL); PrintList(LL); break; case 8: if (IsEmpty(&LL) == 1) printf("链表为空。n"); else printf("链表不为空。n"); break; case 9: LNode * tma; int d = 0; printf("输入你要查找第几个结点:>"); scanf("%d", &d); if ((tma = LocateNode(LL, d)) != NULL) printf("第%d个结点的地址是=%p，ee=%dn", d,tma,tma->data); break; case 10: LNode * tmb; int s = 0; printf("输入你要查找的元素值:>"); scanf("%d", &s); ee = s; if ((tmb = LocateElem(LL, &ee)) != NULL) printf("元素值为%d的地址是=%pn", s, tmb); else printf("未找到该元素!n"); break; case 11: LinkList La, Lb, Lc; La=InitList1(); Lb=InitList1(); Lc=InitList1(); ee=1; PushBack(Lb, &ee); ee=2; PushBack(La, &ee); ee=3; PushBack(Lb, &ee); ee=4; PushBack(Lb, &ee); ee=5; PushBack(La, &ee); ee=6; PushBack(Lb, &ee); ee=7; PushBack(Lb, &ee); ee=8; PushBack(Lb, &ee); ee=9; PushBack(La, &ee); ee=10; PushBack(La, &ee); printf("表La的内容为:>"); PrintList(La); printf("表Lb的内容为:>"); PrintList(Lb); MergeList(La,Lb,Lc); printf("表Lc的内容为:>"); PrintList(Lc); DestroyList1(La); La=NULL; DestroyList1(Lb); Lb=NULL; DestroyList1(Lc); Lc=NULL; break; case 12: int p = 0; int q = 0; printf("请输入指定的结点和要插入的元素:>"); scanf("%d %d", &p, &q); ee = p; LNode * tmp = LocateElem(LL, &ee); ee = q; InsertNextNode(tmp, &ee); PrintList(LL); break; case 13: int h = 0; int i = 0; printf("请输入指定的结点和要插入的元素:>"); scanf("%d %d", &h, &i); ee = h; LNode* rac = LocateElem(LL, &ee); ee = i; InsertPriorNode(rac, &ee); PrintList(LL); break; case 14: printf("从这个结点之后原地逆置:>"); int f = 0; scanf("%d", &f); ee = f; LNode* tme = LocateElem(LL, &ee); ReverseList(tme); PrintList(LL); break; case 15: int c = 0; printf("输入要删除的元素:>"); scanf("%d", &c); ee = c; DeleteElem(LL, &ee); PrintList(LL); break; case 16: ClearList(LL); PrintList(LL); break; default: printf("选择错误n"); break; } } while (input); return 0; } // 初始化链表LL，返回值：失败返回NULL，成功返回头结点的地址。 LNode* InitList1() { LNode* head = (LNode*)malloc(sizeof(LNode)); // 分配头结点。 if (head == NULL) return NULL; // 内存不足，返回失败。 head->next = NULL; // 头结点的下一结点暂时不存在，置空。 return head; } // 传入指针变量的地址的方法。 // 初始化链表，返回值：0-失败；1-成功。 int InitList2(LinkList* LL) { // 在本函数中，LL是指针的指针，用于存放指针的地址。 if (*LL != NULL) { printf("链表LL已存在，在初始化之前请先释放它。n"); return 0; } LNode* head = (LNode*)malloc(sizeof(LNode)); // 分配头结点。 if (head == NULL) return 0; // 内存不足，返回失败。 head->next = NULL; // 头结点的下一结点暂时不存在，置空。 *LL = head; return 1; } // 销毁链表LL。 void DestroyList1(LinkList LL) { // 销毁链表LL是指释放链表全部的结点，包括头结点。 LNode* tmp; while (LL != NULL) { tmp = LL->next; // tmp保存下一结点的地址。 free(LL); // 释放当前结点。 LL = tmp; // LL指针移动到下一结点。 } // LL=NULL; // LL在本函数中相当于局部变量，就算置空了也不会影响调用者传递的LL，所以LL=NULL没有意义。 return; } // 销毁链表LL。 void DestroyList2(LinkList* LL) { // 如果函数的参数是指针的指针，可以启用以下代码。 LNode* tmp1, * tmp2; tmp1 = *LL; while (tmp1 != NULL) { tmp2 = tmp1->next; // tmp保存下一结点的地址。 free(tmp1); // 释放当前结点。 tmp1 = tmp2; // LL指针移动到下一结点。 } *LL = NULL; // 把链表的指针置为空，表示链表不存在了。 return; } // 清空链表。 void ClearList(LinkList LL) { // 清空链表LL是指释放链表全部的结点，但不包括头结点。 if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。 LNode* tmp1; LNode* tmp2 = LL->next; // 保留头结点，从头结点的下一个结点开始释放。 while (tmp2 != NULL) { tmp1 = tmp2->next; free(tmp2); tmp2 = tmp1; } LL->next = NULL; // 这行代码一定不能少，否则会留下野指针。 return; } // 在链表LL的第ii个位置插入元素ee，返回值：0-失败；1-成功。 int InsertList(LinkList LL, unsigned int ii, ElemType* ee) { if ((LL == NULL) || (ee == NULL)) { printf("链表LL或元素ee不存在。n"); return 0; } // 判断表和元素是否存在。 // 判断插入位置是否合法 if (ii < 1) { printf("插入位置（%d）不合法，应该在大于0。n", ii); return 0; } // 要在位序ii插入结点，必须找到ii-1结点。 LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。 int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。 while ((pp != NULL) && (kk < ii - 1)) { pp = pp->next; kk++; // printf("pp=%p,kk=%dn",pp,kk); } if (pp == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return 0; } LNode* tmp = (LNode*)malloc(sizeof(LNode)); // 分配一个结点。 if (tmp == NULL) return 0; // 内存不足，返回失败。 // 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。 memcpy(&tmp->data, ee, sizeof(ElemType)); // 处理next指针。 tmp->next = pp->next; pp->next = tmp; return 1; /// // 以上代码可以用以下代码代替。 // LNode *pp=LocateNode(LL,ii-1); // return InsertNextNode(pp,ee); /// } // 删除链表LL中的第ii个结点，返回值：0-位置ii不合法；1-成功。 int DeleteNode(LinkList LL, unsigned int ii) { if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。 // 判断删除位置是否合法 if (ii < 1) { printf("删除位置（%d）不合法，应该在大于0。n", ii); return 0; } // 要删除位序ii结点，必须找到ii-1结点。 LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。 int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。 while ((pp != NULL) && (kk < ii - 1)) { pp = pp->next; kk++; } if (pp->next == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return 0; } LNode* tmp = pp->next; // tmp为将要删除的结点。 pp->next = pp->next->next; // 写成pp->next=tmp->next更简洁。 free(tmp); return 1; } // 在链表LL的头部插入元素ee，返回值：0-失败；1-成功。 int PushFront(LinkList LL, ElemType* ee) { return InsertList(LL, 1, ee); } // 在链表LL的尾部插入元素ee，返回值：0-失败；1-成功。 int PushBack(LinkList LL, ElemType* ee) { //if ((LL == NULL) || (ee == NULL)) { printf("链表LL或元素ee不存在。n"); return 0; } // 判断表和元素是否存在。 //LNode* pp = LL; // 从头结点开始。 找到最后一个结点。 //while (pp->next != NULL) pp = pp->next; //LNode* tmp = (LNode*)malloc(sizeof(LNode)); // 分配一个结点。 //if (tmp == NULL) return 0; // 内存不足，返回失败。 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。 //memcpy(&tmp->data, ee, sizeof(ElemType)); 处理next指针。 //tmp->next = NULL; //pp->next = tmp; //return 1; int len = LengthList(LL); return InsertList(LL, len+1, ee); } // 删除链表LL中第一个结点，返回值：0-位置不合法；1-成功。 int PopFront(LinkList LL) { return DeleteNode(LL, 1); } // 删除链表LL中最后一个结点，返回值：0-位置不合法；1-成功。 int PopBack(LinkList LL) { if (LL == NULL) { printf("链表LL不存在。n"); return 0; } // 判断表和元素是否存在。 // 必须加上这个判断，否则下面的循环pp->next->next不成立。 if (LL->next == NULL) { printf("链表LL为空，没有尾结点。n"); return 0; } // 判断表是否为空。 // 要删除最后一个结点，必须找到最后一个结点的前一个结点。 LNode* pp = LL; // 从第0个结点开始。 // 找到倒数第二个结点（包括头结点）。 while (pp->next->next != NULL) pp = pp->next; // 释放最后一个结点。 free(pp->next); pp->next = NULL; return 1; } // 打印链表中全部的元素。 void PrintList(LinkList LL) { if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。 LNode* pp = LL->next; // 从第1个结点开始。 printf("当前链表的内容为:>"); while (pp != NULL) { printf("%-3d", pp->data); // 如果元素ee为结构体，这行代码要修改。 pp = pp->next; } printf("n"); } // 求链表的长度，返回值：>=0-表LL结点的个数。 int LengthList(LinkList LL) { if (LL == NULL) { printf("链表LL不存在。n"); return 0; } // 判断链表是否存在。 LNode* pp = LL->next; // 头结点不算，从第1个结点开始。 int length = 0; while (pp != NULL) { pp = pp->next; length++; } return length; } // 判断链表是否为空，返回值：0-非空或失败，1-空。 int IsEmpty(LinkList LL) { if (LL == NULL) return 0; if (LL->next == NULL) return 1; return 0; } // 获取链表中第ii个结点，成功返回结点的地址，失败返回空。 // 注意，ii可以取值为0，表示头结点。 LNode* LocateNode(LinkList LL, unsigned int ii) { if (LL == NULL) { printf("链表LL不存在。n"); return NULL; } // 判断表和元素是否存在。 LNode* pp = LL; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。 int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。 while ((pp != NULL) && (kk < ii)) { pp = pp->next; kk++; } if (pp == NULL) { printf("位置（%d）不合法，超过了表长。n", ii); return NULL; } return pp; } // 查找元素ee在链表LL中的结点地址，如果没找到返回NULL，否则返回结点的地址。 LNode* LocateElem(LinkList LL, ElemType* ee) { LNode* pp = LL; // 从第1个数据结点开始。 while (pp != NULL) { // 如果数据元素是结构体，以下代码要修改。 if (pp->data == *ee) return pp; pp = pp->next; } return NULL; } // 采用归并的方法，将两个升序的链表La和Lb，合并成一个升序的链表Lc。 int MergeList(LinkList La, LinkList Lb, LinkList Lc) { if ((La == NULL) || (Lb == NULL) || (Lc == NULL)) { printf("表La、Lb、Lc至少有一个不存在。n"); return 0; } La = La->next; Lb = Lb->next; LNode* pp; // 把La和Lb合并到Lc中。 while ((La != NULL) && (Lb != NULL)) { // 取La和Lb的较小者。 if (La->data <= Lb->data) { pp = La; La = La->next; } else { pp = Lb; Lb = Lb->next; } // 把较小者追加到Lc中。 Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。 Lc = Lc->next; memcpy(&Lc->data, &pp->data, sizeof(ElemType)); Lc->next = NULL; } // 把链表La其它的元素追加到Lc中。 while (La != NULL) { Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。 Lc = Lc->next; memcpy(&Lc->data, &La->data, sizeof(ElemType)); Lc->next = NULL; La = La->next; } // 把链表Lb其它的元素追加到Lc中。 while (Lb != NULL) { Lc->next = (LNode*)malloc(sizeof(LNode)); // 分配一个新结点。 Lc = Lc->next; memcpy(&Lc->data, &Lb->data, sizeof(ElemType)); Lc->next = NULL; Lb = Lb->next; } return 1; } // 在指定结点pp之后插入元素ee，返回值：0-失败；1-成功。 int InsertNextNode(LNode* pp, ElemType* ee) { if (pp == NULL) { printf("结点pp不存在。n"); return 0; } LNode* tmp = (LNode*)malloc(sizeof(LNode)); if (tmp == NULL) return 0; memcpy(&tmp->data, ee, sizeof(ElemType)); tmp->next = pp->next; pp->next = tmp; return 1; } // 在指定结点pp之前插入元素ee，返回值：0-失败；1-成功。 int InsertPriorNode(LNode* pp, ElemType* ee) { if (pp == NULL) { printf("结点pp不存在。n"); return 0; } // 在指定结点pp之前插入采用偷梁换柱的方法： // 1、分配一个新的结点； // 2、把pp结点的数据和指针复制到新结点中。 // 3、把待插入元素的数据存入pp结点中。 LNode* tmp = (LNode*)malloc(sizeof(LNode)); if (tmp == NULL) return 0; // 把pp结点的数据和指针复制到tmp中。 memcpy(&tmp->data, &pp->data, sizeof(ElemType)); tmp->next = pp->next; // 把待插入的元素存入pp中。 memcpy(&pp->data, ee, sizeof(ElemType)); pp->next = tmp; return 1; } //删除指定元素，返回值：0-失败；1-成功。 int DeleteElem(LinkList LL, ElemType* ee) { if (LL == NULL) { printf("链表LL不存在。n"); return; } // 判断链表是否存在。 // 要删除位序ii结点，必须找到ii-1结点。 LNode* pp = LL->next; // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。 int kk = 0; // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。 while ((pp != NULL) && (pp->next->data!=(*ee))) { pp = pp->next; } // 注意，以下行的代码与视频中的不一样，视频中的是 if ( pp==NULL )，有bug。 if (pp->next == NULL) { printf("元素不存在，无法删除！n"); return 0; } LNode* tmp = pp->next; // tmp为将要删除的结点。 pp->next = tmp->next; free(tmp); return 1; } // 把链表pp结点之后的结点原地逆置（反转），返回值：0-失败；1-成功。 void ReverseList(LNode* pp) { LNode* ss; // 当前结点。 LNode* ssnext; // 当前结点的下一结点。 ss = pp->next; // 从pp结点之后的结点开始反转。 pp->next = NULL; // pp->next指向空。 while (ss != NULL) { ssnext = ss->next; // 保留ss下一结点的地址。 // 以下两行相当于在pp之后插入ss结点。 ss->next = pp->next; pp->next = ss; ss = ssnext; // ss结点后移。 } }
本课内容结束！
