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

也想出现在这里？点击联系我~

单向链表特点：

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

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

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

节点-> 数据域+指针域

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

链表的操作代码：

#include “linklist.h”
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

LinkList *CreateLinkList()
{ // 1000
LinkList *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;
}
// 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;
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;
}