嵌入式学习的第二十天-数据结构-调试+链表的一般操作

一、调试

1.一般调试

2.找段错误

二、链表的一般操作

1.单链表的修改

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;
}

2.单链表的销毁

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

3.查找中间节点

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

 4.找倒数第k个节点

/*** @brief 查找倒数第k个节点* * @param ll 需要查找的链表* @param k 倒数第k个节点* @return LinkNode* 找到对应的节点*/
LinkNode*FindKLastLinkList(LinkList*ll,int k)
{LinkNode*slow = ll->head;LinkNode*fast = ll->head;int i = 0;for(i = 0;i<k;++i){fast =fast->next;}while (fast) {fast =fast->next;slow = slow->next;}return slow;
}

5.链表的逆序

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

6.链表的排序(插入法排序) 

int SertSortLinkList(LinkList*ll)
{LinkNode*pinsert = ll->head;LinkNode*ptmp = pinsert->next;LinkNode*next = ptmp->next;ptmp->next = NULL;ll->head->next = NULL;while (1) {pinsert = ll->head;while (pinsert->next&&ptmp->data.age>pinsert->data.age&&ptmp->data.age>pinsert->next->data.age){pinsert=pinsert->next;}if(pinsert->data.age>ptmp->data.age){ptmp->next=ll->head;ll->head=ptmp;}else{ptmp->next=pinsert->next;pinsert->next=ptmp;}ptmp=next;if(NULL==ptmp){break;}next=next->next;ptmp->next=NULL;}return 0;
}

7.循环链表

int circultlarLinkList(LinkList* ll)
{LinkNode* slow = ll->head;LinkNode* fast = ll->head;while(fast){fast  =fast->next;if(NULL == fast){return 0;;}if(slow == fast){return 1;}fast =fast->next;slow = slow->next;}return 0;
}

三、顺序表和链表的优缺点

1.存储方式

• 顺序表是一段连续的存储单元
• 链表是逻辑结构连续物理结构（在内存中的表现形式）不连续

2.时间性能

（1）查找：顺序表O(1)  链表  O(n)

（2）插入和删除：顺序表 O(n)  链表   O(1)

3.空间性能

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