重头开始嵌入式第三十七天（数据结构链表）

单向链表

单向链表是一种常见的数据结构。

一、结构组成

- 节点：单向链表由多个节点组成。每个节点包含两个部分，一个是存储数据的部分，可以存储各种类型的数据，如整数、字符、结构体等；另一个是指向下一个节点的指针，用于连接链表中的各个节点。

- 头指针：链表有一个特殊的指针称为头指针，它指向链表的第一个节点。如果链表为空，头指针为 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;
}