嵌入式学习笔记 D20 ：单向链表的基本操作

• 单向链表的创建
• 单向链表的插入
• 单向链表的删除及清空
• 单向链表的修改
• 单向链表的查找
• 单向链表的逆序

一、单向链表的创建

LinkList *CreateLinkList() {LinkList *ll = malloc(sizeof(LinkList));if (NULL == ll) {fprintf(stderr, "CreateLink malloc");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}

判断链表是否为空：

int IsEmptyLinkList(LinkList *ll)
{return 0 == ll->clen;
}

获取链表长度：

int GetSizeLinkList(LinkList *ll)
{return ll->clen;
}

遍历链表并输出：

int ShowLinkList(LinkList *ll)
{LinkNode *tmp = ll->head;int len = GetSizeLinkList(ll);int i ;for(i = 0 ; i < len ; ++i){printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);tmp = tmp->next;}return 0;
}

二、单向链表的插入

1.头插法：

int InsertHeadLinkList(LinkList *ll, DATATYPE *data)
{LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode) {fprintf(stderr, "InsertHeadLinkList malloc");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));//memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next = NULL;if(IsEmptyLinkList(ll)){ll->head = newnode;}else{newnode->next = ll->head;ll->head = newnode;}ll->clen++;return 0;
}

2.尾插法：

int InsertTailLinkList(LinkList *ll, DATATYPE *data)
{if(IsEmptyLinkList(ll)){return InsertHeadLinkList(ll,data);}else{LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode) {fprintf(stderr, "InsertTailLinkList malloc");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));//memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next = NULL;LinkNode *tmp1 = ll->head;while(tmp1->next){tmp1 = tmp1->next;}tmp1->next = newnode;ll->clen++;}return 0;
}

3.指定位置插入：（重点掌握）

int InsertPosLinkList(LinkList *ll, DATATYPE *data, int pos)
{int len = GetSizeLinkList(ll);if(pos < 0 || pos > len){return 1;}if(0 == pos){return InsertHeadLinkList(ll, data); //cha ru 1 ge jie dian malloc 2 ci hui xie lou nei cun}else if(len == pos){return InsertTailLinkList(ll, data);}else{LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode) {fprintf(stderr, "InsertPosLinkList malloc");return 1;}memcpy(&newnode->data,data,sizeof(DATATYPE));newnode->next = NULL;int i = 0;LinkNode *tmp = ll->head;while(tmp->next){++i;if(i == pos){newnode->next = tmp->next;tmp->next = newnode;break;}tmp = tmp->next;}ll->clen++;}return 0;
}

三、单向链表的删除及清空

1.单向链表的删除（指定名字对应的结点）

int DeleteLinkList(LinkList *ll,char *name)
{LinkNode *tmp = ll->head;if(IsEmptyLinkList(ll)){return 1;}if(0 == strcmp(tmp->data.name,name)){ll->head = ll->head->next;free(tmp);ll->clen--;return 0;}while(tmp->next){if (0 == strcmp(tmp->next->data.name,name)){LinkNode *tmp2 = tmp->next;tmp->next = tmp->next->next;free(tmp2);ll->clen--;return 0;}tmp = tmp->next;}return 1;
}

2.单向链表的清空：

int DestroyLinkList(LinkList **ll)
{LinkNode *tmp = (*ll)->head;while(tmp){if(NULL == tmp){break;}(*ll)->head = (*ll)->head->next;free(tmp);tmp = (*ll)->head;}free(*ll);*ll = NULL;return 0;
}

四、单向链表的修改

int ModifyLinkList(LinkList *ll,char *name,DATATYPE *data)
{DATATYPE *tmp = FindLinkList(ll,name);if(NULL == tmp){return 1;}memcpy(tmp, data, sizeof(DATATYPE));return 0;
}

五、单向链表的查找

1.查找指定姓名的数据域

DATATYPE *FindLinkList(LinkList *ll,char *name)
{LinkNode *tmp = ll->head;while(tmp){if(0 == strcmp(tmp->data.name,name)){return &tmp->data;}tmp = tmp->next;}return NULL;
}

2.查找链表的中间结点位置

LinkNode *Findmiddleofpoint(LinkList *ll)
{LinkNode *slow = ll->head;LinkNode *fast = ll->head;while(fast){fast = fast->next;if(fast == NULL ){break;}slow = slow->next;fast = fast->next;}return slow;
}

3.查找链表中倒数第k个结点位置

LinkNode *Findlastofpoint(LinkList *ll, int k)
{if(IsEmptyLinkList(ll)){return NULL;}if(k > ll->clen || k <= 0){return NULL;}LinkNode *slow = ll->head;LinkNode *fast = ll->head;int i;for (i = 0; i < k;++i){fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}return slow;
}

六、单向链表的逆序

int InverseLinkList(LinkList *ll)
{if(IsEmptyLinkList(ll)){return 1;}int len = GetSizeLinkList(ll);if( 1 == len){return 0;}LinkNode *prev = NULL;LinkNode *tmp = ll->head;LinkNode *next = ll->head->next;while(1){tmp->next = prev;prev = tmp;tmp = next;if(NULL == tmp){break;}next = next->next;}ll->head = prev;return 0;
}

总结：

        单向链表的优点：插入和删除的时间复杂度为O(1)，优于顺序表。且在空间性能上不需要预先分配，大小可变，能够动态分配满足要求。

        单向链表的缺点：查找的时间复杂度为O(n)。