1、定义：
通过一组任意的存储单元来存储线性表中的数据元素。为了建设数据元素之间的线性关系，对每个链表节点，除了寄存元素本身的信息外，还须要寄存一个指向下一个节点
构造体：
typedef int ElemType;typedef struct LNode { //定义单链表节点类型 ElemType data; //每个节点寄存一个数据元素 struct LNode *next; //指针指向下一个节点} LNode, *LinkList; //强调这是一个单链表应用LinkList，强调节点应用LNode*2、创立一个单链表
2.1 用头插法建设单链表
新节点插入到以后列表的表头：
代码实现：
/** * 用头插法建设单链表 * @param L * @return */LinkList List_HeadInsert(LinkList &L) { //逆向建设单链表 LNode *s; int x; L = (LinkList) malloc(sizeof(LNode)); //创立头节点 L->next = NULL; //初始为空链表 scanf("%d", &x); //输出节点的值 while (x != 9999) { //输出9999示意完结 s = (LNode *) malloc(sizeof(LNode)); //创立新节点 s->data = x; s->next = L->next; L->next = s; //将新节点插入表中，L为头指针 scanf("%d", &x); } return L;}采纳头插法建设单链表时，读入数据的程序与生成的链表中的元素的程序式相同的
2.2 用尾插法建设单链表
新节点插入到以后列表的表尾，该办法须要一个尾指针指向链表的最初一个节点，图中未画出尾指针：
代码实现：
/** * 用尾插法建设单链表 * @param L * @return */LinkList List_TailInsert(LinkList &L) { //正向建设单链表 int x; //设ElemType为整型 L = (LinkList) malloc(sizeof(LNode)); //建设头节点 LNode *s, *r = L; //r为表尾指针 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;}3、基本操作
3.1 在指定节点前插入元素
实现原理图：
代码实现:
/** * 前插操作，在p节点之前插入元素e * @param p * @param e * @return */bool InsertPriorNode(LNode *p, ElemType 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; //p中的元素改为e return true;}3.2 在指定节点后插
代码实现：
/** * 后插操作，在p节点之后插入元素e * @param p * @param e * @return */bool InsertNextNode(LNode *p, ElemType e) { if (p == NULL) { return false; } LNode *s = (LNode *) malloc(sizeof(LNode)); if (s == NULL) { //内存调配失败 return false; } s->data = e; //用节点s保留数据元素e s->next = p->next; // 留神先后顺序 p->next = s; return true;}3.3 按位序删
代码实现：
/** * 按位序删除，带头结点 * @param L * @param i * @param e * @return */bool ListDelete(LinkList &L, int i, ElemType e) { if (i < 1) { return false; } LNode *p; //指针p指向以后扫描到的节点 int j = 0; //以后p指向的是第几个节点 p = L; //L指向头节点，头节点是第0个节点，不存数据 while (p != NULL && j < i - 1) { //循环找到第 i-1 个节点 p = p->next; j++; } if (p == NULL) { //i值不非法 return false; } if (p->next == NULL) { //第i-1个节点之后已无其余节点 return false; } LNode *q = p->next; //令q指向被删除的节点 e = q->data; //用e返回元素的值 p->next = q->next; //将*q节点从链中断开 free(q); //开释节点的存储空间 return true;}3.4 按位查找
/** * 按位查找，返回第i个元素，带头节点 * @param L * @param i * @return */LNode *GetElem(LinkList L, int i) { if (i < 0) { return NULL; } LNode *p; //指针p指向以后扫描到的节点 int j = 0; //以后p指向的是第几个节点 p = L; //L指向头节点，头节点是第0个节点，不存数据 while (p != NULL && j < i) { //循环找到第 i 个节点 p = p->next; j++; } return