单链表（不带头结点）

单链表不带头结点结构体设计：

//不带头结点的结构体设计：
typedef int ELEM_TYPE;//有效数据节点结构体设计
typedef struct Node
{ELEM_TYPE data;//数据域   （1.头结点：不保存任何数据    2.有效数据节点：保存有效值）   struct Node* next;//指针域  (1.头结点：保存第一个元素的地址    2.有效数据节点：保存下一个有效元素的地址)
}Node, * PNode;

老规矩，实现链表的基本功能：增删改查

函数声明如下：

/初始化函数(对于头结点进行赋初值)
void no_head_Init_list(struct Node** phead);//struct Node ** == PNode *//购买一个新节点
struct Node* no_head_BuyNode(ELEM_TYPE val);//头插
bool no_head_Insert_head(PNode* phead, ELEM_TYPE val);//尾插
bool no_head_Insert_tail(struct Node** phead, ELEM_TYPE val);//按位置插入(pos=0 相当于头插  pos==length 相当于尾插)
bool no_head_Insert_pos(struct Node** phead, int pos, ELEM_TYPE val);//头删
bool no_head_Del_head(struct Node** phead);//尾删
bool no_head_Del_tail(struct Node** phead);//按位置删(pos==0 相当于头删   pos==length-1 相当于尾删（pos==length非法）)
bool no_head_Del_pos(struct Node** phead, int pos);
//按值删
bool no_head_Del_val(struct Node** phead, ELEM_TYPE val);//获取值位置  （如果val值存在， 则返回其地址  不然返回NULL）
struct Node* no_head_Search(struct Node** phead, ELEM_TYPE val);//判空
bool no_head_IsEmpty(struct Node** phead);//判满  单链表不存在满这个概念//获取单链表有效数据节点个数
int no_head_Get_length(struct Node** phead);//清空  相当于直接调用销毁
void no_head_Clear(struct Node** phead);//销毁1（malloc申请来的空间 全部释放掉）
void no_head_Destroy(struct Node** phead);//销毁2
void no_head_Destroy2(struct Node** phead);//打印
void no_head_Show(struct Node** phead);

对于函数括号里面的参数为什么是二级指针呢？由于该单链表没有头结点，所以我们需要一个指针来指向第一个有效节点，那么为了能使函数内部的改变能够影响外部数据，所以需要传参数时传入二级指针。

1.初始化

void no_head_Init_list(struct Node** phead)//struct Node ** == PNode *
{//assert  phead!=NULLassert(phead != NULL);*phead = NULL;//修改一个指针，如果没有有效节点的话，将其指针指向NULL//这个指针保存第一个有效数据节点的地址   phead   *phead(保存的第一个有效数据的地址)   (*phead).next   
}

2.申请一个新节点便于插入

struct Node* no_head_BuyNode(ELEM_TYPE val)
{struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));assert(pnewnode != NULL);if (pnewnode == NULL){return NULL;}pnewnode->data = val;pnewnode->next = NULL;return pnewnode;
}

3.头插

bool no_head_Insert_head(PNode* phead, ELEM_TYPE val)
{//assertassert(phead != NULL);if (NULL == phead){return false;}//1.创建新节点struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));assert(pnewnode != NULL);pnewnode->data = val;pnewnode->next = NULL;//2.找到合适的插入位置 (头插函数 已经找到插入位置)//3.插入pnewnode->next = *phead;*phead = pnewnode;return true;
}

4.尾插

bool no_head_Insert_tail(struct Node** phead, ELEM_TYPE val)
{assert(phead != NULL);if (no_head_IsEmpty(phead))//如果我是一个空链，则执行头插函数 不要执行尾插函数{return no_head_Insert_head(phead, val);}//1.创建新节点PNode pnewnode = (PNode)malloc(sizeof(Node) * 1);assert(pnewnode != NULL);pnewnode->data = val;pnewnode->next = NULL;//2.找到合适的插入位置PNode p = *phead;for (p; p->next != NULL; p = p->next);//这里存在一个bug：如果是空链的话，*phead == p == NULL，那么语句2：p->next会报写入异常（在上面处理一下这个bug即可）//此时 指针p停留在尾结点，而不是尾结点的下一个节点p->next = pnewnode;return true;
}

5.按位置插

//按位置插入(pos=0 相当于头插  pos==length 相当于尾插)
bool no_head_Insert_pos(struct Node** phead, int pos, ELEM_TYPE val)
{assert(phead != NULL);assert(pos >= 0 && pos <= no_head_Get_length(phead));//pos == length合法  相当于尾插 但是这个位置不能用于删除if (pos == 0){return no_head_Insert_head(phead, val);}//1.购买新节点PNode pnewnode = no_head_BuyNode(val);assert(pnewnode != NULL);//2.找到合适的位置PNode p = *phead;for (int i = 1; i < pos; ++i)//这里存在一个bug：如果pos = 0,p没有办法跑到合适的位置，提前处理掉即可{p = p->next;}//3.插入pnewnode->next = p->next;p->next = pnewnode;return true;
}

6,。头删

bool no_head_Del_head(struct Node** phead)
{assert(phead != NULL);if (no_head_IsEmpty(phead))//如果是空链，返回假{return false;}struct Node* p = *phead;*phead = p->next;free(p);return true;
}

7.尾删（不带头结点的单链表尾删较为麻烦，会有两种风险）

bool no_head_Del_tail(struct Node** phead)
{assert(phead != NULL);//两种风险   第一种：q有可能为NULL（由于空链导致）if (no_head_IsEmpty(phead)){return false;}//什么情况下：q不为NULL，但是q->next为NULL？  //有节点，但是仅有一个节点//两种风险   第二种：q->next有可能为NULL（由于导致）if ((*phead)->next == NULL) //仅有一个首元素节点{return no_head_Del_head(phead);//仅有一个节点,尾删和头删没区别}PNode q = *phead;for (q; q->next->next != NULL; q = q->next);//q向后一次项探测两步(有bug风险:1.p可能为NULL  2.p->next为NULL)//此时q停在倒数第二个节点（尾删的待删除节点的上一个节点）struct Node* p = q->next;//p通过q来直接指向待删除节点q->next = p->next;free(p);return true;
}

8.按位置删

//按位置删(pos==0 相当于头删   pos==length-1 相当于尾删（pos==length非法）)
bool no_head_Del_pos(struct Node** phead, int pos)
{assert(phead != NULL);assert(pos >= 0 && pos < no_head_Get_length(phead));if (no_head_IsEmpty(phead))//判空{return false;}if (pos == 0){return no_head_Del_head(phead);}struct Node* q = *phead;for (int i = 1; i < pos; i++){q = q->next;}struct Node* p = q->next;q->next = p->next;free(p);return true;
}

9.按值删

bool no_head_Del_val(struct Node** phead, ELEM_TYPE val)
{assert(phead != NULL);if ((*phead)->data == val)//判断首元素的值  如果  == val{return no_head_Del_head(phead);}PNode p = no_head_Search(phead,val);if (p == NULL){return false;}PNode q = *phead;for (q; q->next != p; q = q->next);;//存在一个bug：如果要删除的值就是首元素的值,这时，q没有合适的位置去指向,所以在开头加上处理//此时  p指向待删除节点//q应该指向p的上一个节点q->next = p->next;free(p);return true;
}

10.获取值得位置

//获取值位置  （如果val值存在， 则返回其地址  不然返回NULL）
struct Node* no_head_Search(struct Node** phead, ELEM_TYPE val)
{assert(phead != NULL);for (struct Node* p = *phead; p != NULL; p = p->next){if (p->data == val){return p;}}return NULL;
}

11.判空

12.获取单链表有效节点的个数

//判空
bool no_head_IsEmpty(struct Node** phead)
{assert(phead != NULL);return (*phead) == NULL;
}//判满  单链表不存在满这个概念//获取单链表有效数据节点个数
int no_head_Get_length(struct Node** phead)
{assert(phead != NULL);int cout = 0;for (PNode p = *phead; p != NULL; p = p->next){cout++;}return cout;
}

13.清空、销毁、打印（销毁给出两种方法）

//清空  相当于直接调用销毁
void no_head_Clear(struct Node** phead)
{no_head_Destroy(phead);
}//销毁1（malloc申请来的空间 全部释放掉）
void no_head_Destroy(struct Node** phead)
{assert(phead != NULL);while (*phead != NULL){PNode p = (*phead);*phead = p->next;free(p);}*phead = NULL;
}//销毁2
void no_head_Destroy2(struct Node** phead)
{assert(phead != NULL);struct Node* p = *phead;struct Node* q;*phead = NULL;while (p != NULL){q = p->next;free(p);p = q;}
}//打印
void no_head_Show(struct Node** phead)
{assert(phead != NULL);for (PNode p = *phead; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");
}

接下来在主函数里测试一下

int main()
{struct Node* head;//头指针no_head_Init_list(&head);//初始化for (int i = 0; i < 20; i++){no_head_Insert_pos(&head, i, i + 1);}//将1到20分别按位置插入no_head_Show(&head);//打印no_head_Insert_head(&head, 100);//头插100no_head_Insert_tail(&head, 200);//尾插200no_head_Show(&head);//打印printf("length = %d\n", no_head_Get_length(&head));//打印单链表有效数据节点的长度no_head_Del_head(&head);//头删no_head_Del_tail(&head);//尾删no_head_Show(&head);//打印no_head_Del_pos(&head, 4);//将第4个有效节点删除no_head_Del_val(&head, 14);//将数据为14的节点删除no_head_Show(&head);//打印printf("length = %d\n", no_head_Get_length(&head));//打印单链表有效数据节点的长度//Destroy(&head);no_head_Destroy2(&head);//销毁//printf("%d\n", sizeof(struct Node));return 0;
}

结果：