当前位置：首页 > news >正文

玳瑁的嵌入式日记D21-08020（数据结构）

news 2025/8/21 13:05:43

双向链表

double link list

typedef struct dou_node {
DATATYPE data;
struct dou_node *prev;
struct dou_node *next;
}DouLinkNode;

双向链表：

节点 = 数据 + NEXT +PREV .
手撕代码(增加+删除)
增加，删除的操作，需要 tmp 停止待操作节点的前一节点上。
查找操作进行了扩展，回调函数(函数指针)。解耦合，扩展功能。

查找顺序表O(1) 链表 O(n)
插入和删除顺序表 O(n) 链表 O(1)

空间性能
顺序表需要预先分配空间，大小固定
链表不需要预先分配，大小可变，动态分配

int InsertHeadDouLinkList(DouLinkList *list,DATATYPE *data)
{
DouLinkNode *newnode = (DouLinkNode*)malloc(sizeof(DouLinkNode));
if ( NULL == newnode )
{
perror( "IsertHeadDouLinkList malloc error" );
return 1;
}
memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->prev = NULL;
newnode->next = NULL;
if ( IsEmptyLinkList(list) )
{
list->head = newnode;
}
else{
newnode->next = list->head;
list->head->prev = newnode;
list->head = newnode;
}
list->clen++;
return 0;
}

int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{
if (IsEmptyLinkList(dl))
{
return InsertHeadDouLinkList(dl, data);
}
else
{
DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
if (NULL == newnode)
{
perror("InsertTailDouLinkList malloc");
return 1;
}
memcpy(&newnode->data, data, sizeof(DATATYPE));
newnode->next = NULL;
newnode->prev = NULL;

DouLinkNode *tmp = dl->head;
while (tmp->next)
{
tmp = tmp->next;
}

newnode->prev = tmp;
tmp->next = newnode;
}
dl->clen++;
return 0;
}

int InsertPosLinkList(DouLinkList *list, DATATYPE *data,int pos)
{
if(pos<0 || pos > list->clen)
{
printf("InsertPosLinkList pos error\n");
return 1;
}

if(pos == 0)
{
return InsertHeadDouLinkList(list,data);
}
else if(pos == list->clen)
{
return InsertTailDouLinkList(list, data);
}else
{

DouLinkNode *newnode = malloc(sizeof(DouLinkNode));
if(NULL == newnode)
{
perror("InsertPosLinkList malloc error");
return 1;
}
memcpy(&newnode->data,data,sizeof(DATATYPE));
newnode->next = NULL;
newnode->prev = NULL;
DouLinkNode *tmp = list->head;
for(int i = 0; i < pos; i++)
{
tmp = tmp->next;
}

newnode->next = tmp;
newnode->prev = tmp->prev;
tmp->prev->next = newnode;
tmp->prev = newnode;
list->clen++;

}
return 0;
}

gdb

typedef enum {DIR_FORWARD,DIR_BACKWARD}DIRECT; //枚举

int ShowLinkList(DouLinkList *list,DIRECT direct)
{
DouLinkNode *tmp = list->head;
if(DIR_FORWARD == direct)
{
while(tmp)
{
printf("%s \n",tmp->data.data);
tmp = tmp->next;
}

}else
{
while(tmp->next)
{
tmp = tmp->next;
} // 移到最后
while(tmp)
{
printf("%s \n",tmp->data.data);
tmp = tmp->prev;
}
}

return 0;
}

int ReviseLinkList(DouLinkList *list)
{
if(list == NULL|| list->clen == 0)
{
printf("RviseLinkList error");
return 1;
}
DouLinkNode *prev = NULL;
DouLinkNode *curr = list->head;
DouLinkNode *next = NULL;

while(curr!=NULL)
{
next = curr->next;
prev = curr->prev;
curr->next = prev; //后移
prev = curr;
curr = next;
}
list->head = prev;
return 0;
}

**DouLinkNode FindDouLinkList(DouLinkList dl,PFUN fun, void*arg);**

DouLinkNode *FindDouLinkList(DouLinkList *dl,PFUN fun, void*arg)
{
DouLinkNode* tmp = dl->head;
while(tmp)
{
// if(0==strcmp(tmp->data.name,name))
if ( fun ( &tmp->data , arg))
{
return tmp;
}
tmp=tmp->next;
}
return NULL;
}

int findperbyname(DATATYPE*data,void* arg)
{
// 从void* -> 其他类型指针，需要强转
return 0 == strcmp(data->name,(char*)arg);
}

int findperbyage(DATATYPE*data,void* arg)
{
// 从void* -> 其他类型指针，需要强转
return data->age == *(int*)arg;;
}

printf("------------------------find-----------------------------\n");
char want_name[] = "lisi";
int age =50;
DouLinkNode* tmp = FindDouLinkList(list,findperbyname ,want_name);
if (NULL == tmp)
{
printf("cant find per %s\n",want_name);
}
else
{
printf("find it,name:%s score:%d\n",tmp->data.name,tmp->data.score);
}

查看全文

http://www.xdnf.cn/news/1334035.html