数据结构与算法学习链表

链表分为单链，双链和循环链表，链表C语言实现：

 //  单链 
typedef  struct   NodeType
{
　　  char   elem;
　　NodeType  *  next;
} Node;

  //  双链 
typedef  struct   DuobleNodeType
{
　　  char   elem;
　　NodeType  * next;
     NodeType  * prev; 
}DoubleNode;

1.单链表反转。

以微软的一道面试题为例，编写一个函数，给定一个链表的头指针，要求只遍历一次，将单链表中的元素顺序反转过来。

给出反转函数：

Node* LinkList_reverse(Node*  head) 
{ 
    Node  *preNode,*curNode,* nextNode; 
  
      if (head==NULL)  return  NULL; //  空链表  
  
     if (head->next == NULL)  return  head; //  仅一个元素  
   
    curNode  = head;preNode=NULL; //  初始化  
  
     while  (curNode) 
    { 
        nextNode  = curNode->next; //  先记录下一个结点  
        curNode->next = preNode; //  改变链表方向（逆置）  
        preNode = curNode; //  将当前结点作为下一次循环的前一个结点  
        curNode = nextNode; //  向后推移一个结点  
     } 
  
      return  preNode; //  当遍历完链表后curNode应该为空，此时preNode链表头(head)  
}

2.链表添加节点

 //  在给定的节点前插入新节点 
 void  LinkList_Add(Node* ptr,Node*  newNode)
{
      int  temp =  0  ;
    newNode ->next = ptr-> next;
    ptr ->next =  newNode;
    temp  = ptr-> e;
    ptr ->e = newNode-> e;
    newNode ->e =  temp;
}

3.无头链表删除给定节点

同样以一面试题为例

假设一个没有头指针的单链表，一个指针指向此单链表中间的一个节点（非第一个或最后一个节点），请将该节点删除。

 //  删除节点 
 void  LinkList_Delete(Node*  ptr)
{
    Node * temp = ptr-> next;
      if (temp !=  NULL)
    {
    ptr ->e = temp-> e;
    ptr ->next = temp-> next;
    delete temp;  //这里delete好像有问题，以后再看下
      }
}

标签: 数据结构 , 算法

作者： Leo_wl

出处： http://www.cnblogs.com/Leo_wl/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

版权信息

查看更多关于数据结构与算法学习链表的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did47605

更新时间：2022-09-24 阅读：35次