宜宾网站建设公司

c#如何实现单向链表的查删改功能

这篇文章主要介绍了c#如何实现单向链表的查删改功能，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

成都创新互联一直通过网站建设和网站营销帮助企业获得更多客户资源。 以"深度挖掘，量身打造，注重实效"的一站式服务，以成都做网站、成都网站建设、移动互联产品、网络营销推广服务为核心业务。十载网站制作的经验，使用新网站建设技术，全新开发出的标准网站，不但价格便宜而且实用、灵活，特别适合中小公司网站制作。网站管理系统简单易用，维护方便，您可以完全操作网站资料，是中小公司快速网站建设的选择。

slist.h//头文件

#ifndef _SLIST_H_
#define _SLTST_H_

#include
#include
#include
#include

typedef int SLTDataType; 
typedef struct SListNode 
{ 
    SLTDataType data;    
    struct SListNode* next;
}SListNode;

void SListInit(SListNode** pphead);
void SListDestory(SListNode** pphead);

SListNode* BuySListNode(SLTDataType x);
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPopFront(SListNode** pphead);
SListNode* SListFind(SListNode* pphead, SLTDataType x); // 在pos的后面进行插入 
void SListInsertAfter(SListNode* pos, SLTDataType x); // 在pos的前面进行插入 
void SListEraseAfter(SListNode* pos); 
void SListRemove(SListNode** pphead, SLTDataType x);
void SListRemoveAll(SListNode** pphead, SLTDataType x);
void SListPrint(SListNode* pphead);

void SListReverse(SListNode **pphead);
void SListReverse2(SListNode **pphead);

SListNode* getIntersectionNode(SListNode* headA, SListNode*headB);
SListNode *detectCycle(SListNode *head);

#endif

slist.c//源文件

#include"slist.h"

void SListInit(SListNode** pphead)//初始化
{
    *pphead = NULL;
}
void SListDestory(SListNode** pphead)
{
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        while ((*pphead)->next)
        {
            SListEraseAfter(*pphead);
        }
        free(*pphead);
        *pphead = NULL;
    }
}

SListNode* BuySListNode(SLTDataType x)
{
    SListNode* res = (SListNode *)malloc(sizeof(SListNode));
    res->data = x;
    res->next = NULL;
    return res;
}
void SListPushFront(SListNode** pphead, SLTDataType x)
{
    SListNode* tmp = BuySListNode(x);
    tmp->next = *pphead;
    *pphead = tmp;
}
void SListPopFront(SListNode** pphead)
{
    if (*pphead == NULL)
    {
        return;
    }
    /*(*pphead)->date = (*pphead)->next;*/
    SListNode* tmp = (*pphead)->next;
    free(*pphead);
    *pphead = tmp;
}
SListNode* SListFind(SListNode* pphead, SLTDataType x)//找x数据 
{
    SListNode* tmp;
    for (tmp = pphead; tmp; tmp = tmp->next)
    {
        if (tmp->data == x)
        {
            return tmp;
        }
        return NULL;
    }
}
void SListInsertAfter(SListNode* pos, SLTDataType x)//把x插到pos后面
{
    SListNode* tmp = BuySListNode(x);
    tmp->next = pos->next;
    pos->next = tmp;
}
void SListEraseAfter(SListNode* pos)//删除pos后面的数据
{
    SListNode* tmp = pos->next;
    if (tmp == NULL)
    {
        return;
    }
    pos->next = tmp->next;
    free(tmp);
}
void SListRemove(SListNode** pphead, SLTDataType x)//移除x
{
    SListNode* tmp;
    if (*pphead == NULL)
    {
        return;
    }
    if ((*pphead)->data==x)
    {
        SListPopFront(*pphead);
    }
    else
    {
        for (tmp = *pphead; tmp->next; tmp = tmp->next)
        {
            SListEraseAfter(pphead);
            return;
        }
    }
}
void SListRemoveAll(SListNode** pphead, SLTDataType x)
{
    SListNode* tmp;
    if (*pphead && (*pphead)->data == x)
    {
        SListPopFront(*pphead);
    }
    for (; tmp = *pphead; tmp&&tmp->next)
    {
        if (tmp->next == x)
        {
            SListEraseAfter(tmp);
        }
        else
        {
            tmp = tmp->next;
        }
    }
}
void SListPrint(SListNode* pphead)
{
    SListNode* cur;
    printf("pphead->");
    for (cur = pphead; cur; cur = cur->next)
    {
        printf("%d->", cur->data);
    }
    printf("NULL\n");
}
void SListReverse(SListNode **pphead)//反转链表
{
    SListNode *head = *pphead;   //此指针在每次循环中始终指向当前链表的头
    SListNode *tmp = head->next; //此指针在每次循环中始终指向要被后删头插的节点
    SListNode *oldh = *pphead;   //此指针在每次循环中始终指向原本的头结点，不会改变指向

    while (tmp) //如果tmp为空，则代表逆序结束，旧头的next已经是空的了，成为新链表的末尾
    {
        oldh->next = tmp->next; //将tmp架空，实际是后删操作的一部分
        tmp->next = head; //让tmp变成新的头，实际是头插操作的一部分 
        head = tmp; //换头
        tmp = oldh->next; //让tmp变成下次循环中待删除的节点
    }
    *pphead = head;
}
void SListReverse2(SListNode **pphead)//反转链表
{
    SListNode *pre = *pphead;   //被执行操作的前一个节点
    SListNode *cur = pre->next; //被执行操作的节点
    SListNode *next = cur;      //被执行操作的后一个节点，暂时指在cur，在循环开始的时候跳转到其后一个节点
    pre->next = NULL; //此时的头，将会是转换后的尾，这里是在设置链表尾节点
    while (next)
    {
        next = next->next; //先让next变成下一个节点，之所以不放在最后，是因为会有next为空的限制
        cur->next = pre; //让原本指着后面的指到前面来（先后转）
        pre = cur; //为了下次循环而传递数据，这里是设置下次循环的上一个节点（本次执行操作的节点将会成下次循环的上一个节点）
        cur = next; //同上（本次的下一个节点将会成为下次的被执行节点）
    }

    *pphead = pre; //循环跳出后cur和next都已经指向空了，pre才是新的头
}

//输入两个链表，找出它们的第一个公共结点
SListNode* getIntersectionNode(SListNode* headA, SListNode*headB)
{
    int lenA = 0;
    int lenB = 0;
    int gap, i;
    SListNode* cur = 0;
    SListNode * longerlist = headA;
    SListNode * shorterlist = headB;
    for (cur = 0; cur; cur = headA->next)
    {
        lenA++;
    }
    for (cur = 0; cur; cur = headB->next)
    {
        lenB++;
    }
    gap = abs(lenA - lenB);
    if (lenA > lenB)
    {
        longerlist = headA;
        shorterlist = headB;
    }
    else
    {
        longerlist = headB;
        shorterlist = headA;
    }
    for (i = 0; i < gap; i++)
    {
        longerlist=longerlist->next;
    }
    for (; longerlist&&shorterlist; longerlist = longerlist->next, shorterlist = shorterlist->next)
    {
        if (longerlist == shorterlist)
        {
            return longerlist;
        }
    }
    return NULL;
}

// 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
SListNode *detectCycle(SListNode *head)
{
    SListNode * fast = head;
    SListNode * slow = head;

    while (fast && slow && fast->next)
    {
        fast = fast->next->next;//遍历速度为2
        slow = slow->next;//遍历速度为1
        if (fast == slow)//判断两不同遍历速度的交点
        {
            break;
        }
    }

    for (; fast && fast->next; fast = fast->next, head = head->next)//交点到入环的第一个节点距离等于头节点到入环的第一个节点
    {
        if (fast == head)
        {
            return fast;
        }
    }
    return NULL;
}

main.c//测试

#include"slist.h"
#if 0 //1，选择程序段
int main()//测试
{
    SListNode *phead1;
    //SListNode *phead2;
    SListNode *tmp;
    SListNode *tmp2;
    SListInit(&phead1);
    //SListInit(&phead2);
    SListPushFront(&phead1, 8);
    tmp = phead1;
    SListPushFront(&phead1, 7);
    SListPushFront(&phead1, 6);
    SListPushFront(&phead1, 5);
    SListPushFront(&phead1, 4);
    SListPushFront(&phead1, 3);
    tmp2 = phead1;
    SListPushFront(&phead1, 2);
    SListPushFront(&phead1, 1);
    tmp->next = tmp2;
    //phead2->next = phead1->next->next;
    SListNode * ret = detectCycle(phead1);
    if (ret)
    {
        printf("%d\n", ret->data);
    }
    else
    {
        printf("NULL\n");
    }
    //SListDestory(&phead1);
    //SListDestory(&phead2);
    return 0;
}

#else
int main()//测试
{
    SListNode *phead;
    SListInit(&phead);
    SListPushFront(&phead, 1);
    SListPushFront(&phead, 2);
    SListPushFront(&phead, 3);
    SListPushFront(&phead, 4);
    SListPushFront(&phead, 5);
    SListPushFront(&phead, 6);
    SListPushFront(&phead, 7);
    SListPushFront(&phead, 8);
    SListPushFront(&phead, 9);
    //SListPopFront(&phead);
    //SListPopFront(&phead);
    /*
    SListInsertAfter(SListFind(phead, 6), 9);
    SListEraseAfter(SListFind(phead, 4));
    SListRemove(&phead, 7);
    SListPrint(phead);
    */
    //SListRemoveAll(&phead, 8);
    SListReverse2(&phead);
    SListPrint(phead);
    SListDestory(&phead);
    //SListPrint(phead);
    return 0;
}

#endif
//int main()//约瑟夫环问题，链表解决
//{
//  SListNode *phead;
//  SListNode *plast;
//  SListNode *cur;
//  int m = 11, n = 3;
//  int i;
//  SListInit(&phead);
//  SListPushFront(&phead, m);
//  plast = phead;
//  for (i = m - 1; i >= 1; i--)
//  {
//      SListPushFront(&phead, i);
//  }
//  plast->next = phead;
//  cur = plast;
//  for (; m > 1; m--)
//  {
//      for (i = 1; i < n; i++)
//      {
//          cur = cur->next;
//          printf("%d号报数字%d\n", cur->data, i);
//      }
//      printf("%d号被去掉\n", cur->next->data);
//      SListEraseAfter(cur);
//  }
//  printf("%d号最终获胜\n", cur->data);
//  free(cur);
//  return 0;
//}

感谢你能够认真阅读完这篇文章，希望小编分享的“c#如何实现单向链表的查删改功能”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!


新闻名称：c#如何实现单向链表的查删改功能
浏览地址：http://hbruida.cn/article/geddhs.html

其他资讯