单向链表
单向链表是一种常见的数据结构。
一、结构组成
- 节点：单向链表由多个节点组成。每个节点包含两个部分，一个是存储数据的部分，可以存储各种类型的数据，如整数、字符、结构体等；另一个是指向下一个节点的指针，用于连接链表中的各个节点。
- 头指针：链表有一个特殊的指针称为头指针，它指向链表的第一个节点。如果链表为空，头指针为 NULL。
二、特点
- 动态性：单向链表的长度可以在运行时动态改变，可以根据需要随时添加或删除节点。
- 内存分配：节点通常是在运行时动态分配内存，可以在堆上使用诸如 malloc （在 C 语言中）或 new （在 C++中）来分配内存空间。
- 遍历方式：只能从链表的头节点开始，沿着指向下一个节点的指针依次访问各个节点，直到到达链表的末尾（即下一个指针为 NULL）。
三、基本操做
- 插入节点：可以在链表的头部、尾部或中间位置插入新的节点。插入操作需要修改相应节点的指针，使其指向新插入的节点。
- 删除节点：根据特定条件删除链表中的节点。删除操作也需要调整相应节点的指针，以保持链表的连续性。
- 查找节点：可以遍历链表查找满足特定条件的节点。
单向链表在很多场景下都有广泛应用，比如实现栈、队列等数据结构，以及在各种算法和程序中进行动态数据存储和管理。
创建ADT
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef struct node {
DATATYPE data;
struct node *next;
}SLinkNode;
typedef struct list {
SLinkNode *head;
int clen;
}SLinkList;
1.创建链表
SLinkList * CreateSLinkList()
{
SLinkList* sll = (SLinkList*) malloc(sizeof(SLinkList));
if(NULL == sll)
{
perror("CreateSLinkList malloc");
return NULL;
}
sll->head = NULL;
sll->clen = 0 ;
return sll;
}
2.头插数据
int InsertHeadSLinkList(SLinkList* sll,DATATYPE *data)
{
SLinkNode* newnode = (SLinkNode*)malloc(sizeof(SLinkNode));
if(NULL == sll)
{
perror("inserthead malloc");
return 1;
}
memcpy(&newnode->data ,data,sizeof(DATATYPE));
newnode->next = NULL;
if(IsEmptySLinkList(sll))
{
sll->head = newnode;
}
else
{
newnode->next = sll->head;
sll->head = newnode;
}
sll->clen++;
return 0;
}3.删除数据
int DeleteSLinkList(SLinkList*sll,FUN fun,void* arg)
{
//待删除节点的前一个指针
SLinkNode*prev = NULL;
SLinkNode*tmp = sll->head;
int len = GetSizeSLinkList(sll);
if(len == 1)
{
free(sll->head);
sll->head = NULL;
sll->clen = 0 ;
return 0;
}
//至少2个节点
while(1)
{
if(fun(&tmp->data,arg))
{
if(prev)
{
prev->next = tmp->next;
}
else
{
sll->head = tmp->next;
}
free(tmp);
sll->clen--;
return 0;
}
prev = tmp;
tmp = tmp->next;
if(NULL == tmp)
{
//删除失败
//return 1;
break;
}
}
return 1;
}4.更改数据
int ModifySlinkList(SLinkList*sll,FUN fun,void* arg,DATATYPE*newdata)
{
SLinkNode* tmp= FindSlinkList(sll,fun, arg);
if(NULL == tmp)
{
fprintf(stderr,"can find\n");
return 1;
}
else
{
memcpy(&tmp->data,newdata,sizeof(DATATYPE));
}
return 0;
}5.清空链表
int DestroySLinkList(SLinkList *sll) {
SLinkNode *tmp = sll->head;
while (1) {
tmp = sll->head;
if (!tmp)
break;
sll->head = sll->head->next;
free(tmp);
}
free(sll);
return 0;
}
6.查找数据
SLinkNode * FindSlinkList(SLinkList*sll,FUN fun,void* arg)
{
SLinkNode* tmp = sll->head;
int len = GetSizeSLinkList(sll);
int i = 0;
for(i=0;i<len;i++)
{
//if(0==strcmp(tmp->data.name,name))
if(fun(&tmp->data,arg))
{
return tmp;
}
tmp = tmp->next;
}
return NULL;
}7.尾插数据
int InserTailSlinkList(SLinkList* sll,DATATYPE *data)
{
SLinkNode* newnode = (SLinkNode*)malloc(sizeof(SLinkNode));
SLinkNode* tmp=sll->head;
if(NULL == sll)
{
perror("inserthead malloc");
return 1;
}
memcpy(&newnode->data ,data,sizeof(DATATYPE));
newnode->next = NULL;
if(IsEmptySLinkList(sll))
{
sll->head = newnode;
}
else
{
while(tmp->next)
tmp=tmp->next;
tmp->next=newnode;
}
sll->clen++;
return 0;
}8.按位插入
int InserPosSlinkList(SLinkList* sll,DATATYPE *data,int pos)
{
int len = GetSizeSLinkList(sll);
if(pos<0 || pos > len)
{
return 1;
}
if(0 == pos)
{
return InsertHeadSLinkList(sll,data);
}
else if(pos == len)
{
return InserTailSlinkList(sll,data);
} else // mid
{
int i = 0;
SLinkNode *prev = sll->head;
for (i = 0; i < pos - 1; i++) {
prev = prev->next;
}
SLinkNode *newnode = malloc(sizeof(SLinkNode));
if (NULL == newnode) {
perror("insert pos malloc");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
newnode->next = prev->next;
prev->next = newnode;
}
sll->clen++;
return 0;
}9.打印数据
int ShowSLinkList(SLinkList*sll)
{
SLinkNode* tmp = sll->head ;
while(tmp)
{
printf("name:%s score:%d\n",tmp->data.name ,tmp->data.score);
tmp= tmp->next ;//i++
}
return 0;
}