学习嵌入式的第二十一天——数据结构——链表

单向链表特点：

存储的内存空间不连续 。为了弥补顺序存储存劣势。

优势
插入，删除   O(1)
动态存储 ，在程序运行期间决定大小。

劣势：
不能随机访问   O(N) 

节点-> 数据域+指针域 

顺序表(数组) 只有数据域

链表的操作代码：

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>LinkList *CreateLinkList()
{  // 1000LinkList *ll = malloc(sizeof(LinkList));if (NULL == ll){perror("CreateLinkList malloc");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");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 0 == list->clen;
}int ShowLinkList(LinkList *list)
{LinkNode *tmp = list->head;while (tmp){printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex,tmp->data.age, tmp->data.score);// tmp++tmp = tmp->next;}return 0;
}int InsertTailLinkList(LinkList *list, DATATYPE *data)
{if (IsEmptyLinkList(list)){return InsertHeadLinkList(list, data);}else{LinkNode *tmp = list->head;// tmp 需要停在最后一个有效节点上while (tmp->next){tmp = tmp->next;}LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertTailLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;tmp->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;}// insertheadif (0 == pos){return InsertHeadLinkList(list, data);}// inserttailelse 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;tmp->next = newnode;}list->clen++;return 0;
}int GetSizeLinkList(LinkList *list)
{return list->clen;
}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 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--;}//非第一个节点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;
}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;
}