《C++》解密--单链表

目录

一、概念与结构

二、实现单链表

三、链表的分类

四、单链表算法题

---

一、概念与结构

        1、节点

          结点的组成主要有：当前结点要保存的数据和保存下一个节点的地址（指针变量）

        图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点。

        链表中每个结点都是独立申请的（如果需要插入数据时才去申请一块结点的空间），我们需            要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

        2、链表的性质

【链表机构在逻辑上是连续的，在物理结构上不一定连续。

【结点一般是从堆上申请的。

【从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

  

二、实现单链表

 1、创立文件

 2、定义链表的结构

【SList.h】

//定义链表(结点)的位置typedef int SLTDataType;typedef struct SListNode{SLTDataType data;struct SListNode* next;}SLTNode;void SLTPrint(SLTNode* phead);

3、打印函数

【SList.h】

//打印函数void SLTPrint(SLTNode* phead);

【SList.c】

//打印函数void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}

【test.c】

//创建一个链表，并且打印链表void createSList(){SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//第一个结点的地址作为参数传递过去SLTNode* plist = node1;SLTPrint(node1);}

4、判断插入时，空间是否足够

【SList.c】

//判断插入数据时，空间是否足够SLTNode* SLTBuyNode(SLTDataType x){SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;}

5、尾插

【SList.h】

//尾插void SLTPushBack(SLTNode** pphead,SLTDataType x);

【SList.c】

//尾插void SLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//形参：pphead --> 实参：&plist//*pphead 解引用 --> plist//申请新结点SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间if (*pphead == NULL){*pphead = newnode;}else{//尾节点 --> 新结点//找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail --> newnodeptail->next = newnode;}}

【test.c】

void SListTest01(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPrint(plist);  //1->NULLSLTPushBack(&plist, 2);SLTPrint(plist);  //1->2->NULLSLTPushBack(&plist, 3);SLTPrint(plist);  //1->2->3->NULLSLTPushBack(&plist, 4);SLTPrint(plist);  //1->2->3->4->NULL}

【运行结果】

6、头插

【SList.h】

//头插void SLTPushFront(SLTNode** pphead,SLTDataType x);

【SList.c】

//头插void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL}

【运行结果】

7、尾删

【SList.h】

//尾删void SLTPopBack(SLTNode** pphead);

【SList.c】

//尾删void SLTPopBack(SLTNode** pphead){//判断链表是不是空，若为空则不可以删assert(pphead && *pphead);//处理只有一个结点的情况：要删除的就是头结点（当next指针为空）if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾结点ptail 和尾结点的前一个结点prevSLTNode* ptail = *pphead;SLTNode* prev = NULL;//遍历数组,找尾结点while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//尾删SLTPopBack(&plist);SLTPrint(plist);  //4->3->2->NULLSLTPopBack(&plist);SLTPrint(plist);  //4->3->NULLSLTPopBack(&plist);SLTPrint(plist);  //4->NULLSLTPopBack(&plist);SLTPrint(plist);  //NULL}

【运行结果】

8、头删

【SList.h】

//头删void SLTPopFront(SLTNode** pphead);

【SList.c】

//头删void SLTPopFront(SLTNode** pphead){assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//删除*pphead --> nextfree(*pphead);*pphead = next;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//SLTPrint(plist);   //4->3->2->1->NULL//头删SLTPopFront(&plist);SLTPrint(plist);  //3->2->1->NULLSLTPopFront(&plist);SLTPrint(plist);  //2->1->NULLSLTPopFront(&plist);SLTPrint(plist);  //1->NULLSLTPopFront(&plist);SLTPrint(plist);  //NULL}

【运行结果】

9、查找

【SList.h】

//查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

【SList.c】

//查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x){assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//跳出循环，说明没找到return NULL;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 3);if (find == NULL){printf("没找到！\n");}else{printf("find it!\n");}}

【运行结果】

10、在指定位置之前插入数据

【SList.h】

//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

【SList.c】

//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);//如果pos恰好是头结点if (pos == *pphead){SLTPushFront(pphead, x); //相当于头插}else{SLTNode* newnode = SLTBuyNode(x);//找到pos的前一个结点:prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//跳出这个循环，说明prev的前一个结点就是pos//将newnode插入prev和pos之间newnode->next = pos;prev->next = newnode;}}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//在指定位置之前插入数据SLTInsert(&plist, find, 11); //在2之前插入11SLTPrint(plist);   //4->3->11->2->1->NULL}

【运行结果】

11、在指定位置之后插入数据

【SList.h】

//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x);

【SList.c】

//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* newnode = SLTBuyNode(x);//把newnode放到pos的下一个位置（pos->next）newnode->next = pos->next;pos->next = newnode;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//在指定位置之后插入数据SLTInsertAfter(find, 9);  //在2之后插入9SLTPrint(plist);  //4->3->2->9->1->NULL}

【运行结果】

12、删除pos结点

【SList.h】

//删除pos结点void SLTErase(SLTNode** pphead, SLTNode* pos);

【SList.c】

//删除pos结点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pos);assert(pphead && *pphead);//头插（如果pos恰好为头结点*pphead,那就没有前一个结点prev了）if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){ //遍历数组，寻找posprev = prev->next;} //跳出循环，prev刚好是pos的前一个结点(要删除pos)prev->next = pos->next;free(pos);pos = NULL;}}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//删除pos结点SLTErase(&plist, find);  //删除pos(2)这个结点SLTPrint(plist);  //4->3->1->NULL}

【运行结果】

13、删除pos之后的结点

【SList.h】

//删除pos之后的结点void SLTEraseAfter(SLTNode* pos);

【SList.c】

//删除pos之后的结点void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);//删除pos的下一个结点，就要让pos的下一个结点直接指向pos的next的next//但是后面要把pos->next释放删除掉，所以先把这个指针保存起来SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//删除pos之后的结点SLTEraseAfter(find);SLTPrint(plist);  //4->3->2->NULL} 

【运行结果】

14、销毁链表

【SList.h】

//销毁链表void SListDestroy(SLTNode** pphead);

【SList.c】

//销毁链表void SListDestroy(SLTNode** pphead){assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;}

【test.c】

void SListTest01(){SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);   //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//销毁链表    SListDestroy(&plist);    SLTPrint(plist);  //NULL} 

【运行结果】

三、链表的分类

四、单链表算法题

1、反转链表

【思路】

【代码】

typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head){    //处理空链表    if(head == NULL)    {        return head;    }    //创建三个指针 ListNode* n1,*n2,*n3; n1 = NULL , n2 = head , n3 = n2->next;    while(n2) {  n2->next = n1;  n1 = n2;  n2 = n3;  if(n3)  {    n3 = n3->next;  } } //此时n1就是链表反转后新的头结点head return n1;}

2、链表的中间结点

【思路】

【代码】

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head)  {    ListNode* slow = head,*fast = head;  //慢指针每次走一步  //快指针每次走两步  while(fast && fast->next)  //等价于fast!=NULL && fast->next!=NULL//当fast或fast->fast任何一个为空指针（为假）时，就跳出循环  {    slow = slow->next;    fast = fast->next->next;  }    //此时slow指向得节点刚好就是中间节点    return slow; }

3、合并两个有序链表

【思路】

【代码】

typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {  //处理链表为空的情况  if(list1 == NULL)  {    return list2;  }  if(list2 == NULL)  {    return list1;  }  //创建新链表  ListNode*newHead = NULL,*newTail = NULL;  //创建两个指针分别指向两个链表的头结点  ListNode* l1 = list1;  ListNode* l2 = list2;  //比大小  while(l1 && l2)  {     if(l1->val < l2->val)     {       //l1尾插到新链表中       if(newHead == NULL)       {        newHead = newTail = l1;       }       else       {        newTail->next = l1;        newTail = newTail->next;       }       l1 = l1->next;     }     else     {         //l2尾插到新链表         if(newHead == NULL)       {        newHead = newTail = l2;       }       else       {        newTail->next = l2;        newTail = newTail->next;       }         l2 = l2->next;     }  }  //跳出while循环，只有两种情况：l1为空（l2肯定不为空） 或 l2为空（l1不为）  if(l1)  //l1不为空  {    newTail->next = l1;  }  if(l2)  //l2不为空  {    newTail->next = l2;  }  return newHead;}

4、链表分割

【思路】

【代码】

class Partition {public:    ListNode* partition(ListNode* pHead, int x)     {         //创建两个非空链表：小链表、大链表        //小链表        ListNode* lessHead,*lessTail;        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));        //大链表         ListNode* greaterHead,*greaterTail;        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));        //遍历原链表，与x比较大小        // >=x的尾插进入大链表 ， <x的尾插进入小链表        ListNode* pcur = pHead;        while(pcur)  //等价于pcur != NULL        {            if(pcur->val < x)            { //尾插到小链表               lessTail->next = pcur;               lessTail = lessTail->next;            }            else             { //尾插到大链表              greaterTail->next = pcur;              greaterTail = greaterTail->next;            }            pcur = pcur->next;        }        //将大链表的尾结点的next置为空         greaterTail->next = NULL;         //让大小链表首尾相连         lessTail->next = greaterHead->next;         ListNode* ret = lessHead->next;         free(lessHead);         free(greaterHead);         lessHead = greaterHead = NULL;         return ret;    }};

5、链表的回文结构

【代码】

class PalindromeList {public:ListNode* findMidNode(ListNode* phead){//使用快慢指针，寻找中间结点    ListNode* slow = phead;    ListNode* fast = phead;    while(fast && fast->next)    {        slow = slow->next;        fast = fast->next->next;    }    return slow;}ListNode* reverseList(ListNode* phead){    //链表反转    ListNode* n1,*n2,*n3;    n1 = NULL;    n2 = phead;    n3 = n2->next;    while(n2)    {        n2->next = n1;        n1 = n2;        n2 = n3;        if(n3)        {            n3 = n3->next;        }    }    return n1;}    bool chkPalindrome(ListNode* A)     {        //1、找中间结点        ListNode* mid = findMidNode(A);        //2、根据中间结点，将中间结点后的链表反转        ListNode* right = reverseList(mid);        //3、从原链表的头和反转链表比较结点值 (开始时，left指头，right指尾)        ListNode* left = A;        while(right)        {            if(left->val != right->val)            {                return false;            }            left = left->next;            right = right->next;        }        return true;    }};

未完待续...