#pragma once
typedef int ELEM_TYPE;
//有效数据节点结构体设计(头结点借用)
typedef struct Node
{
ELEM_TYPE data;//数据域 (1.头结点:不保存任何数据 2.有效数据节点:保存有效值)
struct Node *next;//指针域 (1.头结点:保存第一个元素的地址 2.有效数据节点:保存下一个有效元素的地址)
}Node, PNode;
/*
//有效数据节点结构体设计
typedef struct Node
{
union
{
int length;
ELEM_TYPE data;//数据域 存放有效值
};
struct Node *next;//指针域 存放下一个有效数据节点的地址
}Node, PNode;
//头结点结构体设计:
typedef struct Head
{
struct Node *next;//指针域 保存第一个有效数据节点的地址
}Head, *PHead;
*/
//带头结点的单链表有哪些操作函数:
//初始化函数(对于头结点进行赋初值)
void Init_list(struct Node *plist);
//购买一个新节点
struct Node *BuyNode(ELEM_TYPE val);
//头插
bool Insert_head(struct Node *plist, ELEM_TYPE val);
//尾插
bool Insert_tail(struct Node *plist, ELEM_TYPE val);
//按位置插入(pos=0 相当于头插 pos==length 相当于尾插)
bool Insert_pos(struct Node *plist, int pos, ELEM_TYPE val);
//头删
bool Del_head(struct Node *plist);
//尾删
bool Del_tail(struct Node *plist);
//按位置删(pos==0 相当于头删 pos==length-1 相当于尾删(pos==length非法))
bool Del_pos(struct Node *plist, int pos);
//按值删
bool Del_val(struct Node *plist, ELEM_TYPE val);
//获取值位置 (如果val值存在, 则返回其地址 不然返回NULL)
struct Node* Search(struct Node *plist, ELEM_TYPE val);
//判空
bool IsEmpty(struct Node *plist);
//判满 单链表不存在满这个概念
//获取单链表有效数据节点个数
int Get_length(struct Node *plist);
//清空 相当于直接调用销毁
void Clear(struct Node *plist);
//销毁1(malloc申请来的空间 全部释放掉)
void Destroy(struct Node *plist);
//销毁2
void Destroy2(struct Node *plist);
//打印
void Show(struct Node *plist);
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "list.h"
/*
需要前驱的操作函数:插入,删除等(让指针p指向头结点,判断依据是下一个节点存不存在,存在的话向后走一步)
for(struct Node *p=plist; p->next!=NULL; p=p->next);//如果指针p循环外还使用,就提到for外面定义
不需要前驱的操作函数:查找,获取有效值个数,打印等(让指针p指向第一个元素地址,判断依据是当前指向的节点存不存在,存在的话向后走一步)
for(struct Node *p=plist->next; p!=NULL; p=p->next);
*/
//带头结点的单链表有哪些操作函数:
//初始化函数(对于头结点进行赋初值)
void Init_list(struct Node *plist)
{
assert(plist != NULL);
if(NULL == plist)
{
return;
}
//plist->data; 头结点的数据域不需要赋值
plist->next = NULL;
}
//购买一个新节点
struct Node *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;
}
//头插
bool Insert_head(struct Node *plist, ELEM_TYPE val)
{
//1.判断参数合法性
assert(plist != NULL);
if(NULL == plist)
{
return false;
}
//2.1申请新节点 (插入一个节点, malloc申请一个节点)
struct Node*pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
assert(pnewnode != NULL);
if(pnewnode == NULL)
{
return false;
}
//2.2将val值赋值给新节点
pnewnode->data = val;
//pnewnode->next = NULL; //?
//3.找到合适的插入位置 (因为是头插函数, 所以直接可以得到合适的插入位置)
//4.插入
pnewnode->next = plist->next;//因为plist的next域指向首元素地址
plist->next = pnewnode;
return true;
}
//尾插
bool Insert_tail(struct Node *plist, ELEM_TYPE val)
{
//assert
//1.购买新节点
struct Node * pnewnode = BuyNode(val);
assert(pnewnode != NULL);
if(NULL == pnewnode)
{
return false;
}
//2.找到合适的插入位置
struct Node *p = plist;//因为指针p在for循环外面,还要使用,所以定义在for外面
for(p; p->next!=NULL; p=p->next);
//此时p指向尾结点
//3.插入
pnewnode->next = p->next; //pnewnode->next = NULL;
p->next = pnewnode;
return true;
}
//按位置插入(pos=0 相当于头插 pos==length 相当于尾插)
bool Insert_pos(struct Node *plist, int pos, ELEM_TYPE val)
{
assert(plist != NULL);
assert(pos >=0 && pos<=Get_length(plist));
//1.购买新节点
struct Node * pnewnode = BuyNode(val);
assert(pnewnode != NULL);
if(NULL == pnewnode)
{
return false;
}
//2.找到合适的插入位置
struct Node *p = plist;
for(int i=0; i<pos; i++)
{
p=p->next;
}
//3.插入
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
//头删
bool Del_head(struct Node *plist)
{
//assert
if(IsEmpty(plist))//删除需要判空
return false;
struct Node *p = plist->next;
plist->next = p->next;//plist->next = plist->next->next;
free(p);
return true;
}
//尾删
bool Del_tail(struct Node *plist)
{
//assert
if(IsEmpty(plist)) //删除需要判空
return false;
struct Node *p = plist;
for(p; p->next!=NULL; p=p->next); // 此时p指向尾结点
struct Node *q = plist;
for(q; q->next!=p; q=q->next); // 此时q停在尾结点的前面
q->next = p->next;//q->next = NULL;
free(p);
return true;
}
//按位置删(pos==0 相当于头删 pos==length-1 相当于尾删(pos==length非法))
bool Del_pos(struct Node *plist, int pos)
{
assert(plist != NULL);
assert(pos >=0 && pos<Get_length(plist));//length这个位置 可以插不能删
if(IsEmpty(plist)) //删除需要判空
return false;
/*struct Node *p = plist;
for(int i=0; i<=pos; i++)
{
p=p->next;
}*/
struct Node *q = plist;
for(int i=0; i<pos; i++)
{
q=q->next;
}
struct Node *p = q->next;
q->next = p->next;
free(p);
return true;
}
//按值删
bool Del_val(struct Node *plist, ELEM_TYPE val)
{
//assert
struct Node *p = Search(plist, val);
if(p == NULL)
{
return false;
}
struct Node *q = plist;
for(q; q->next!=p; q=q->next);
//q在待删除节点p的前面
q->next = p->next;
free(p);
return true;
}
//获取值位置 (如果val值存在, 则返回其地址 不然返回NULL)
struct Node* Search(struct Node *plist, ELEM_TYPE val)
{
//assert
for(struct Node *p = plist->next; p!=NULL; p=p->next)
{
if(p->data == val)
{
return p;
}
}
return NULL;
}
//判空
bool IsEmpty(struct Node *plist)
{
//assert
return plist->next == NULL;
}
//判满 单链表不存在满这个概念
//获取单链表有效数据节点个数
int Get_length(struct Node *plist)
{
//assert
int count = 0;
for(struct Node *p=plist->next; p!=NULL; p=p->next)
{
count++;
}
return count;
}
//清空 相当于直接调用销毁
void Clear(struct Node *plist)
{
Destroy(plist);
}
//销毁1(malloc申请来的空间 全部释放掉)
void Destroy(struct Node *plist)
{
//assert
//一直循环判断(判断单链表里还有没有节点,如果有,则头删一次)
/*while(!IsEmpty(plist))
{
Del_head(plist);
}
plist->next = NULL;*/
while(plist->next != NULL)
{
struct Node *p = plist->next;
plist->next = p->next;
free(p);
}
plist->next = NULL;
}
//销毁2
void Destroy2(struct Node *plist)
{
//assert
struct Node *p = plist->next;
struct Node *q = NULL;//q先不要赋值为p->next 因为p有可能指向NULL
plist->next = NULL;//接下来 就和我头结点没有任何关系了
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
}
//打印
void Show(struct Node *plist)
{
for(struct Node *p=plist->next; p!=NULL; p=p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
#include <stdio.h>
#include "assert.h"
#include <stdlib.h>
#include <vld.h>
//#include "sqlist.h"
//#include "Dsqlist.h"
#include "list.h"
int main()
{
struct Node head;
Init_list(&head);
for(int i=0; i<20; i++)
{
Insert_pos(&head, i, i+1);
}
Show(&head);
Insert_head(&head, 100);
Insert_tail(&head, 200);
Show(&head);
printf("length = %d\n", Get_length(&head));
Del_head(&head);
Del_tail(&head);
Show(&head);
Del_pos(&head, 4);
Del_val(&head, 14);
Show(&head);
printf("length = %d\n", Get_length(&head));
//Destroy(&head);
Destroy2(&head);
//printf("%d\n", sizeof(struct Node));
return 0;
}