玳瑁的嵌入式日记D20-08019（数据结构）
strtok
strtok 是 C 语言标准库 <string.h> 中的一个字符串分割函数，用于按照指定的分隔符将字符串拆分成多个子串（令牌，token）。
char *strtok(char *str, const char *delim);
示例
栈和堆的空间大小
栈 通常较小，默认大小在 1MB~8MB 之间（取决于操作系统和编译器设置）
自动分配和释放
堆 通常很大，理论上可接近系统的可用物理内存 + 虚拟内存总和。
动态分配
链式存储
解决顺序存储的缺点，插入和删除，动态存储问题。
特点：
线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续。可以被存储在任意内存未被占用的位置上。
所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。
为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);
单链表中，c语言的描述
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef struct node {
DATATYPE data; //数据域
struct node *next,*prev; //指针域
}LinkNode;
typedef struct list {
LinkNode *head;
int tlen;
int clen;
}LinkList;
LinkList *CreateLinkList(int len);
int InsertHeadLinkList(LinkList *list, DATATYPE data);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ReviseLinkList(LinkList *list, char *name, DATATYPE data);
int DestroyLinkList(LinkList *list);
int InsertTailLinkList(LinkList *list, DATATYPE data);
LinkList *CreateLinkList()
{
LinkList *ll = malloc(sizeof(LinkList));
if(NULL == ll)
{
perror("CreateLinkList malloc error");
return NULL;
}
ll->head = NULL;
ll->clen = 0;
return ll;
}
int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{ //头插
LinkNode *newnode = malloc(sizeof(LinkNode));
if(NULL == newnode)
{
perror("InsertHeadLinkList malloc error");
return 1;
}
//新结点初始化
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
//链表为空
if(!IsEmptyLinkList(list))
{
newnode->next = list->head;
}
list->head = newnode;
list->clen++;
return 0;
}
int IsEmptyLinkList(LinkList *list)
{
return list->clen == 0;
}
int ShowLinkList(LinkList *list)
{
LinkNode *temp = list->head;
while(temp)
{
printf("name:%s, age:%d, score:%d, sex:%c\n", temp->data.name, temp->data.age, temp->data.score, temp->data.sex);
temp = temp->next; //重点，如何偏移
}
return 0;
}
int InsertTailLinkList(LinkList *list, DATATYPE *data)
{ // 尾插
if(IsEmptyLinkList(list))
{
return InsertHeadLinkList(list, data);
}
else
{
LinkNode *temp = list->head;
while(temp->next)
{
temp = temp->next;
} //temp停在末尾最后一个元素，而不是停在NULL
LinkNode *newnode = malloc(sizeof(LinkNode));
if(NULL==newnode)
{
perror("InsertTailLinkList malloc error");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
temp->next = newnode;
}
list->clen++;
return 0;
}
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos)
{ //位插
int len = GetSizeLinkList(list);
if (pos < 0 || pos > len)
{
fprintf(stderr, "InsertPosLinkList pos error\n");
return 1;
}
// inserthead
if (0 == pos)
{
return InsertHeadLinkList(list, data);
}
// inserttail
else if (pos == len)
{
return InsertTailLinkList(list, data);
}
else //中间插入
{
LinkNode *tmp = list->head;
int off = pos - 1;
// tmp 需要停在待插下标节点的前一位置
while (off--)
{
tmp = tmp->next;
}
LinkNode *newnode = malloc(sizeof(LinkNode));
if (NULL == newnode)
{
perror("InsertposLinkList malloc");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
newnode->next = tmp->next;
// 先链接原本的后面部分，再连接newcode
tmp->next = newnode;
}
list->clen++;
return 0;
}
int GetSizeLinkList(LinkList *list)
{
return list->clen;
}
gdb
int DeleteLinkList(LinkList *list, char *name)
{
if (IsEmptyLinkList(list))
{
fprintf(stderr, "DeleteLinkList empty list\n");
return 1;
}
LinkNode *tmp = list->head;
//删除的是第一个节点
if (0 == strcmp(tmp->data.name, name))
{
list->head = list->head->next;
free(tmp);
list->clen--; // 头部处理，因为更前面没又可以停放tep的地方，需要单独处理
}
//非第一个节点
else
{
while (tmp->next)
{
if (0 == strcmp(tmp->next->data.name, name))
{
//标记待删除的节点
LinkNode *del = tmp->next;
//链表的指针跨过待删节点
tmp->next = tmp->next->next;
free(del);
list->clen--;
break;
}
tmp = tmp->next;
}
}
return 0;
}
LinkNode *FindLinkList(LinkList *list, char *name)
{
LinkNode *tmp = list->head;
while (tmp)
{
if (0 == strcmp(tmp->data.name, name))
{
return tmp;
}
// tmp++;
tmp = tmp->next;
}
return NULL;
}
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data)
{
LinkNode* tmp = FindLinkList(list, name);
if(NULL == tmp)
{
printf("modify error\n");
return 1;
}
memcpy(&tmp->data,data,sizeof(DATATYPE));
return 0;
}
int DestroyLinkList(LinkList *list)
{
LinkNode* tmp = list->head;
//删除链表
while(tmp)
{
list->head = list->head->next;
free(tmp);
tmp = list->head;
}
// 释放链表表头
free(list);
return 0;
}