二、线性表

序言 结构如下插入逻辑 图解code 删除 图解code 链表反转 图解 code函数一览

序言

单向链表（单链表）是线性表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

结构如下

插入逻辑

图解

code

//add to list end bool insert_element_slist(Node *pHead, int pos, ELEMENT data) { Node *tempNode = pHead; if (pHead == NULL) { return false; } if (pos == 1) { //链表没有0位置.要找的是pos-1位置插入.所以pos-1特殊处理 Node *newNode = malloc(sizeof(Node)); newNode->next = tempNode->next; newNode->data = data; tempNode->next = newNode; return true; } tempNode = get_element_slist(tempNode, pos - 1); if (tempNode == NULL) { return false; } Node *newNode = malloc(sizeof(Node)); newNode->data = data; newNode->next = tempNode->next; tempNode->next = newNode; return true; };

删除

图解

code

bool del_element_slist(Node *pHead, int pos, ELEMENT *pData) { if (pHead == NULL) { printf("del_element_slist head is null"); return false; } if (pos == 1) { Node *freeNode = pHead->next; if (freeNode == NULL) { printf("del node is null when pos = 1"); return false; } pHead->next = freeNode->next; *pData = freeNode->data; free(freeNode); freeNode = NULL; return true; } PNode tempNode = pHead; //找pos-1个节点 tempNode = get_element_slist(tempNode, pos - 1); if (tempNode == NULL) { return false; } //转移指针 Node *freeNode = tempNode->next; if (freeNode == NULL) { return false; } tempNode->next = tempNode->next->next; *pData = freeNode->data; //释放 free(freeNode); return true; }

链表反转

图解

反转前

反转后

code

//反转链表 HEAD->A->B->C C->B->A->HEAD此时 C变成HEAD. // HEAD数据不计入链表.原来的HEAD没有数据.此时变成了数据位. Node *reverse_slist(Node *pHead) { if (!pHead) { return NULL; } Node *pNow = pHead; //逻辑的当前节点 Node *pPre = NULL; //逻辑的上一个节点 Node *pNext = NULL;//逻辑的下一个节点 Node *pTail = NULL;//用来保存最后一个反转的尾指针 while (pNow != NULL) { pNext = pNow->next; //得到下一个节点 if (pNext == NULL) { //如果为空.证明pNow是tail pTail = pNow; } pNow->next = pPre; //当前节点指向前一个节点.真正反转的操作.只有这一步.其余的都是循环的赋值 pPre = pNow; //把pNow赋值给pPre.当成普通赋值即可.为了下一次pNow->next = pPre;做准备 pNow = pNext;//当成普通变量赋值.pNext = pNow->next; //循环遍历链表 } pHead->next = NULL; return pTail; };

函数一览

void init_slist(PNode *pHead); bool is_emppy_slist(Node *pHead); bool insert_element_slist(Node *pHead, int pos, ELEMENT data); bool del_element_slist(Node *pHead, int pos, ELEMENT *pData); PNode get_element_slist(PNode pHead, int pos); void clear_slist(Node *pHead); void destroy_slist(Node *pHead); int get_length_slist(Node *pHead); void print_slist(Node *pHead); Node *reverse_slist(Node *pHead); Node *reverse_slist_plus(Node *pHead);

引用: http://blog.csdn.net/xyh269/article/details/70238501 http://www.cnblogs.com/QG-whz/p/5170147.html

code地址: https://github.com/HumorSmith/DataStructure/tree/master/link_list