数据类型及API声明
线性表的链式存储是指每个结点都含有一个指针域，指针域指向下一个结点，这样每个节点包含了自身信息和下一个结点的位置，像链条一样连在一起，线性表的链式存储就是我们常说的链表。一般来说，我们都会给链表加一个表头，表头的指针域指向链表的第一个元素（链表的0号位置），在表头中可以存储链表长度信息。
1. //声明一个链表类型，他可以根据需要转为我们需要的类型 2. typedef void LinkedList; 3. 4. //链表结点 5. typedef struct LinkedListNode LinkedListNode; 6. 7. //链表表头 8. typedef struct LinkedListHead LinkedListHead; 9. 10. //创建线性表并返回线性表句柄 11. LinkedList* LinkedList_Create(); 12. 13. //销毁线性表（释放内存） 14. void LinkedList_Destroy(LinkedList* lList); 15. 16. //清空线性表（不释放内存） 17. void LinkedList_Clear(LinkedList* lList); 18. 19. //返回线性表长度（元素个数） 20. int LinkedList_Length(LinkedList* lList); 21. 22. //插入元素 23. int LinkedList_Insert(LinkedList* lList, LinkedListNode* node, int pos); 24. 25. //返回pos处的元素 26. LinkedListNode* LinearList_Get(LinkedList* lList, int pos); 27. 28. //删除一个结点并返回结点值 29. LinkedListNode* LinearList_Delete(LinkedList* lList, int pos); 30.
链表的API实现
链表结点结构体
链表的结点数据类型是一个结构体，结构体内部只有一个指向本身数据类型的指针，用于存放下一个结点的位置。链表结点只起到连接的作用，它负责把插入的结点一个个链接在链表中，不包含任何业务数据。当我们需要根据自己的业务创建链表时，只需要把我们自己的数据结构体第一个域设置为该链表结点LinkedListNode类型的指针即可，也就是我们的数据结构包含链表结点，并且起始地址相同（链表结点放在数据结构第一个域），这样在做类型转换等操作时，就免去了通过偏移量寻址的操作。
1. struct LinkedListNode 2. { 3. LinkedListNode* next; 4. };
表头结构体
表头包含一个链表结构体，用于指向链表的0号结点，包含一个数据，用于指示链表长度。
1. struct LinkedListHead 2. { 3. LinkedListNode head; 4. int length; 5. };
创建链表并返回链表句柄
- 函数功能：创建一个链表并返回链表句柄，其实就是创建一个表头
- 函数参数：无，链式结构不需要提前分配内存，而线性表的顺序结构需要提前分配内存
- 函数返回：表头
1. LinkedList* LinkedList_Create() 2. { 3. LinkedList* head = NULL; 4. head = (LinkedList*)malloc(sizeof(LinkedListHead)); 5. if (head == NULL) 6. { 7. printf("err: head = (LinkedList*)malloc(sizeof(LinkedListHead))\n"); 8. return NULL; 9. } 10. memset(head, 0, sizeof(LinkedListHead)); 11. return head; 12. }
销毁链表
- 函数功能：销毁线性表就是释放表头资源，销毁链表前需要逐个删除链表结点
- 函数参数：链表句柄
- 函数返回：无
1. void LinkedList_Destroy(LinkedList* lList) 2. { 3. LinkedListHead* pList; 4. if (lList == NULL) 5. { 6. printf("err: lList == NULL \n"); 7. return; 8. } 9. pList = (LinkedListHead*)lList; 10. free(pList); 11. }
清空链表
- 函数功能：返回到链表刚创建的状态，即表头指针域指向NULL，长度置为0
- 函数参数：链表句柄
- 函数返回：无
1. void LinkedList_Clear(LinkedList* lList) 2. { 3. LinkedListHead* pList; 4. if (lList == NULL) 5. { 6. printf("err: lList == NULL \n"); 7. return; 8. } 9. pList = (LinkedListHead*)lList; 10. pList->length = 0; 11. pList->head.next = NULL; 12. }
返回链表长度
- 函数功能：获取链表长度，即结点个数
- 函数参数：链表句柄
- 函数返回：节点个数
1. int LinkedList_Length(LinkedList* lList) 2. { 3. LinkedListHead* pList; 4. if (lList == NULL) 5. { 6. printf("err: lList == NULL \n"); 7. return -1; 8. } 9. pList = (LinkedListHead*)lList; 10. return pList->length; 11. }
插入元素
- 函数功能：在链表中插入一个元素，被插入的元素已经在主调函数分配好内存，只需把链表结点LinkedListNode串接起来即可
- 函数参数：lList 链表句柄 node 待插入元素 pos 插入位置
- 函数返回：成功返回0
1. int LinkedList_Insert(LinkedList* lList, LinkedListNode* node, int pos) 2. { 3. int i = 0; 4. LinkedListHead* pList = NULL; 5. LinkedListNode* pCurrent = NULL; 6. if ((lList == NULL) || (node == NULL) || (pos < 0)) 7. { 8. printf("err: (lList == NULL) || (node == NULL) || (pos < 0)\n"); 9. return -1; 10. } 11. pList = (LinkedListHead*)lList; 12. pCurrent = &(pList->head); 13. for (i = 0; i < pos; i++) 14. { 15. pCurrent = pCurrent->next; 16. } 17. node->next = pCurrent->next; 18. pCurrent->next = node; 19. pList->length++; 20. return 0; 21. }
插入元素示意图
插入元素时需要借助一个辅助指针变量pCurrent，pCurrent为当前指针位置，初始状态他应该指向表头，当我们需要在pos号位置插入元素时，就将pCurrent后移pos位，比如要在2号位置插入，将pCurrent后移2次，那么pCurrent将指在1号结点处，而1号结点的next域指向2号结点，这时只需要把待插入结点插在pCurrent后面即可完成插入。插入时，应先将2号结点的位置赋给待插入结点的指针域，这样做是为了防止后续结点（2号结点）丢失，然后再把待插入结点赋给pCurrent的指针域即可完成整个插入过程。
返回指定位置元素
- 函数功能：获取一个指定位置的元素
- 函数参数：lList 链表句柄 pos 要获取的元素标号
- 函数返回：获取的结点元素
1. LinkedListNode* LinearList_Get(LinkedList* lList, int pos) 2. { 3. int i = 0; 4. LinkedListHead* pList = NULL; 5. LinkedListNode* pCurrent = NULL; 6. if ((lList == NULL) || (pos < 0)) 7. { 8. printf("err: lList == NULL \n"); 9. return NULL; 10. } 11. pList = (LinkedListHead*)lList; 12. pCurrent = &(pList->head); 13. for (i = 0; ((i < pos) && (pCurrent->next != NULL)); i++) 14. { 15. pCurrent = pCurrent->next; 16. } 17. return pCurrent->next; 18. }
删除结点并返回被删除结点
- 函数功能：删除一个结点并返回该结点
- 函数参数：lList 链表句柄 pos 要删除的链表结点元素
- 函数返回：被删除的结点
1. LinkedListNode* LinearList_Delete(LinkedList* lList, int pos) 2. { 3. int i = 0; 4. LinkedListHead* pList = NULL; 5. LinkedListNode* pCurrent = NULL; 6. LinkedListNode* pTemp = NULL; 7. if ((lList == NULL) || (pos < 0)) 8. { 9. printf("err: lList == NULL \n"); 10. return NULL; 11. } 12. pList = (LinkedListHead*)lList; 13. pCurrent = &(pList->head); 14. for (i = 0; i < pos; i++) 15. { 16. pCurrent = pCurrent->next; 17. } 18. pTemp = pCurrent->next; 19. pCurrent->next = pTemp->next; 20. pList->length--; 21. return pTemp; 22. }
删除元素示意图
删除结点需要借助两个辅助指针，一个pCurrent指示当前结点，其作用类似于插入节点中的pCurrent，另一个pTemp用于保存被删除结点，删除时，只需要pCurrent的指针域指向pTemp指针域的内容即可完成删除。
测试函数
1. #include "LinkedList.h" 2. 3. typedef struct 4. { 5. LinkedListNode* node; 6. int len; 7. char* str; 8. }MyStr; 9. 10. int main() 11. { 12. int i = 0; 13. LinkedList* mList = NULL; 14. MyStr s1, s2, s3, s4, s5; 15. MyStr* temp = NULL; 16. s1.str = "hello"; 17. s2.str = "Linked"; 18. s3.str = "List"; 19. s4.str = "C"; 20. s5.str = "!"; 21. 22. mList = LinkedList_Create(); 23. LinkedList_Insert(mList, (LinkedListNode*)&s5, 0); 24. LinkedList_Insert(mList, (LinkedListNode*)&s4, 0); 25. LinkedList_Insert(mList, (LinkedListNode*)&s3, 0); 26. LinkedList_Insert(mList, (LinkedListNode*)&s2, 0); 27. LinkedList_Insert(mList, (LinkedListNode*)&s1, 0); 28. 29. for (i = 0; i < 5; i++) 30. { 31. temp = (MyStr*)LinearList_Get(mList, i); 32. printf("%s ", temp->str); 33. } 34. printf("\n"); 35. 36. for (i = 0; i < 5; i++) 37. { 38. temp = (MyStr*)LinearList_Delete(mList, 0); 39. printf("str: %s\n", temp->str); 40. } 41. 42. printf("len: %d\n", LinkedList_Length(mList)); 43. 44. LinkedList_Destroy(mList); 45. 46. system("pause"); 47. return 0; 48. }
具体代码资源已上传，可在下面的链接免费下载
