链表

什么是链表，链表的分类？ 链表是一种物理存储结构上非连续 非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 链表的分类多样,一下情况组合起来有8中结构 1.单向 双向 2.带头 不带头 3.循环 非循环

单链表的基本操作

#pragma once typedef int SDataType; typedef struct SListNode { SDataType _data; struct SListNode* _pNext; }Node, *PNode; typedef struct SList { PNode _pHead;//指向链表中的第一个结点 }SList; void SListInit(SList* s); void SListPushBack(SList* s, SDataType data); void SListPopBack(SList* s); void SListPushFront(SList* s, SDataType data); void SListPopFront(SList* s); void SListInsert(PNode pos, SDataType data); void SListErase(SList* s, PNode pos); PNode SListFind(SList* s, SDataType data); int SListSize(SList* s); int SListEmpty(SList* s); void SListRemove(SList* s, SDataType data); void SListRemoveAll(SList* s, SDataType data); void SListClear(SList* s); void SListDestroy(SList* s); void TestSList(); #include<stdio.h> #include"SList.h" #include<stdlib.h> #include<malloc.h> #include<assert.h> void SListInit(SList* s) { assert(s); s->_pHead = NULL; } PNode BuySListNode(SDataType data) { PNode pNewNode = (PNode)malloc(sizeof(Node)); if (NULL == pNewNode) { assert(0); return NULL; } pNewNode->_data = data; pNewNode->_pNext = NULL; return pNewNode; } void SListPushBack(SList* s, SDataType data) { assert(s); PNode pNewNode = BuySListNode(data); if (s->_pHead == NULL) { //空链表 s->_pHead = pNewNode; } else { //链表非空 //找链表中最后一个结点 PNode pCur = s->_pHead; while (pCur->_pNext) { pCur = pCur->_pNext; } pCur->_pNext = pNewNode; } } void SListPopBack(SList* s) { assert(s); if (NULL == s->_pHead) { return; } else if (NULL == s->_pHead->_pNext) { //一个结点 free(s->_pHead); s->_pHead = NULL; } else { //多个结点 PNode pPre = NULL; PNode pCur = s->_pHead; while (pCur->_pNext) { pPre = pCur; pCur = pCur->_pNext; } free(pCur); pPre->_pNext = NULL; } } void SListPushFront(SList* s, SDataType data) { assert(s); PNode pNewNode = BuySListNode(data); pNewNode->_pNext = s->_pHead; s->_pHead = pNewNode; } void SListPopFront(SList* s) { assert(s); if (NULL == s->_pHead) { return; } PNode pDelNode = s->_pHead; s->_pHead = pDelNode->_pNext; free(pDelNode); } void SListInsert(PNode pos, SDataType data) { if (pos == NULL) { return; } else { PNode pNewNode = BuySListNode(data); pNewNode->_pNext = pos->_pNext; pos->_pNext = pNewNode; } } void SListErase(SList* s,PNode pos) { assert(s); if (pos == NULL || s->_pHead == NULL) { return; } if (pos == s->_pHead) { s->_pHead = pos->_pNext; } else { PNode pPrePos = s->_pHead; while ( pPrePos&&pPrePos->_pNext != pos) { pPrePos = pPrePos->_pNext; } if (pPrePos) { pPrePos->_pNext = pos->_pNext; } } free(pos); } PNode SListFind(SList* s, SDataType data) { assert(s); PNode pCur = s->_pHead; while (pCur) { if (pCur->_data == data) { return pCur; } pCur = pCur->_pNext; } return NULL; } int SListSize(SList* s) { assert(s); PNode pCur = s->_pHead; int count = 0; while (pCur) { count++; pCur = pCur->_pNext; } return count; } int SListEmpty(SList* s){ assert(s); return NULL == s->_pHead; } //删除链表中第一个知我data的结点 void SListRemove(SList* s, SDataType data) { assert(s); if (s->_pHead == NULL) { return; } PNode pPre = NULL; PNode pCur = s->_pHead; while(pCur) { if (pCur->_data == data) { if (pCur == s->_pHead) { s->_pHead = pCur->_pNext; } else { pPre->_pNext = pCur->_pNext; } free(pCur); return; } else { pPre = pCur; pCur = pCur->_pNext; } } } void SListRemoveAll(SList* s, SDataType data) { if (s->_pHead == NULL) { return ; } PNode pPre = NULL; PNode pCur = s->_pHead; while (pCur) { if (pCur->_data == data) { if (pPre == NULL) { //第一个结点 s->_pHead = pCur->_pNext; free(pCur); pCur = s->_pHead; } else { //非第一个结点 pPre->_pNext = pCur->_pNext; free(pCur); pCur = pPre->_pNext; } } else { pPre = pCur; pCur = pCur->_pNext; } } } void SListClear(SList* s) { assert(s); s->_pHead = NULL; } void SListDestroy(SList* s) { assert(s); s->_pHead = NULL; } void PrintSList(SList* s) { assert(s); PNode pCur = s->_pHead; while (pCur) { printf("%d--->", pCur->_data); pCur = pCur->_pNext; } printf("NULL\n"); } void TestSList() { SList s; SListInit(&s); SListPushBack(&s, 1); SListPushBack(&s, 2); SListPushBack(&s, 3); SListPushBack(&s, 4); SListPushBack(&s, 5); PrintSList(&s); SListPopBack(&s); PrintSList(&s); SListPopBack(&s); PrintSList(&s); SListPopBack(&s); PrintSList(&s); SListPopBack(&s); PrintSList(&s); SListPopBack(&s); PrintSList(&s); SListPushFront(&s, 1); PrintSList(&s); SListPushFront(&s, 2); PrintSList(&s); SListPushFront(&s, 3); PrintSList(&s); SListPushFront(&s, 4); PrintSList(&s); SListPushFront(&s, 5); PrintSList(&s); /*SListPopFront(&s); PrintSList(&s); SListPopFront(&s); PrintSList(&s); SListPopFront(&s); PrintSList(&s); SListPopFront(&s); PrintSList(&s); SListPopFront(&s); PrintSList(&s);*/ //void SListInsert(PNode pos, SDataType data) SListInsert(SListFind(&s, 2), 6); PrintSList(&s); SListErase(&s, SListFind(&s, 6)); PrintSList(&s); printf("%d\n", SListSize(&s)); if (SListEmpty(&s)) { printf("链表为空\n"); } else { printf("链表非空\n"); } SListInsert(SListFind(&s, 2), 5); PrintSList(&s); SListRemoveAll(&s,5); PrintSList(&s); SListDestroy(&s); }