单链表_单链表面 - CSDN
单链表 订阅
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 展开全文
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
信息
外文名
Singly Linked List
类    型
数据结构元素
建立过程
申请空间、得到数据、建立链接
中文名
单链表
简    介
地址任意的存储单元存放数据元素
实    质
一种链式存取的数据结构
单链表单链表简介
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。链接方式存储的线性表简称为链表(Linked List)。链表的具体存储表示为:① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。┌───┬───┐│data │next │└───┴───┘data域--存放结点值的数据域next域--存放结点的直接后继的地址(位置)的指针域(链域)链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的,每个结点只有一个链域的链表称为单链表(Single Linked List)。单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。链表由头指针唯一确定,单链表可以用头指针的名字来命名。终端结点无后继,故终端结点的指针域为空,即NULL。
收起全文
  • 单链表的基本操作

    2018-08-26 14:29:35
    链表:一种链式存储的线性表,用一组地址任意的存储单元...单链表的存储结构 typedef int DataType; typedef struct ListNode { DataType _data; //当前节点中所保存的元素 struct ListNode* _pNext; //指向...

    链表:一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称为存储单元为一个节点。
    这里写图片描述

    单链表的存储结构

    typedef int DataType;
    
    typedef struct ListNode
    {
        DataType _data;                 //当前节点中所保存的元素
        struct ListNode* _pNext;    //指向链表中下一个结点
    
    }SLinkList, SListNode;
    链表的分类

    这里写图片描述

    单链表的基本操作

    void PrintSLinkList(SLinkList* pHead);//打印
    void InitSLinkList(SLinkList** ppHead);//初始化
    void DestroySLinkList(SLinkList** ppHead);//销毁
    void PushBack(SLinkList** ppHead, DataType data);//尾部插入
    void PopBack(SLinkList** ppHead);//尾部删除
    void PushFront(SLinkList** ppHead, DataType data);//头部插入
    void PopFront(SLinkList** ppHead);//头部删除
    SLinkList* Find(SLinkList* pHead, DataType data);//查找元素的位置
    void Delete(SLinkList** ppHead, SLinkList* pos);//指定位置删除元素
    void Revome(SLinkList** ppHead, DataType data);//删除第一个出现的指定元素
    void RemoveAll(SLinkList** ppHead, DataType data);//删除出现的所有元素
    int GetLinkListLength(SLinkList* pHead);//计算单链表的长度
    void BubbleSort(SLinkList** ppHead);//冒泡排序

    0.打印
    //打印
    void PrintSLinkList(SLinkList* pHead)
    {
        SLinkList* cur = pHead;
        while (cur)
        {
            printf("%d -> ", cur->_data);
            cur = cur->_pNext;
        }
        printf("NULL\n");
    }
    1.初始化

     初始化就是让指向单链表的指针指向空,因为要改变指针的志向所以需要传指针的地址

    //初始化
    void InitSLinkList(SLinkList** ppHead)
    {
        assert(ppHead);
        *ppHead = NULL;
    }
    2.销毁

     因为单链表都是用malloc开辟的内存空间,所以每次使用结束都要将其释放掉,所以就有一个销毁函数,将所有的结点释放掉,并让指向链表的指针指向空。

    //销毁
    void DestroySLinkList(SLinkList** ppHead)
    {
        SLinkList* cur = *ppHead;
        SLinkList* del = NULL;
    
        assert(ppHead);
    
        while (cur)
        {
            del = cur;
            cur = cur->_pNext;
    
            free(del);
            del = NULL;
        }
        *ppHead = NULL;
    }

    节点的函数

     由于后面的插入会用malloc开辟空间,制作节点,所以在这里提前将我封装的函数写下来

    SLinkList* BuyNode(DataType data)
    {
        SLinkList* p = (SLinkList*)malloc(sizeof(SLinkList));
        //malloc开辟的空间一定要判断成功还是失败
        if (p == NULL)
        {
            perror("BuyNode::malloc");
            return NULL;
        }
        //空间开辟成功,将赋给节点中的数据域,将指针域赋为空指针
        p->_data = data;
        p->_pNext = NULL;
        //返回节点的地址
        return p;
    }
    3.尾部插入
    1.空链表:直接连接,不需要遍历
    2.非空链表:找到最后一个节点,连接
    

     尾部插入,顾名思义就要知道它的尾部在哪里,所以,我们要遍历取找它的尾部,单恋表的最后一个元素没有指向任何元素,所以它指向小孩一个节点的指针指向空,找到后插入。单链表有时是一个空表,需要改变指针的值,所以需要传指针的地址。
    这里写图片描述

    //尾部插入
    void PushBack(SLinkList** ppHead, DataType data)
    {
        SLinkList* NewNode = NULL;
        SLinkList* cur = *ppHead;
    
        assert(ppHead);
    
        NewNode = BuyNode(data);
    
        //1.空链表:直接连接
        if (*ppHead == NULL)
        {
            *ppHead = NewNode;
        }
        //2.非空链表
        else
        {
            //a.找最后一个结点
            while (cur->_pNext)
            {
                cur = cur->_pNext;
            }
            //b.连接
            cur->_pNext = NewNode;
        }
    }
    4.尾部删除
    1.空链表:不能删除,直接结束
    2.只有一个节点:删除,将头指针置空
    3.两个及以上的节点:找到最后一个节点并将倒数第二个节点置空
    
    //尾部删除
    void PopBack(SLinkList** ppHead)
    {
        SLinkList* cur = *ppHead;
        assert(ppHead);
        //1.空链表:不能删除,直接结束
        if (*ppHead == NULL)
        {
            printf("单链表为空,不能删除!!!\n");
            return;
        }
        //2.只有一个元素:删除,并将头结点置空
        else if ((*ppHead)->_pNext == NULL)
        {
            free((*ppHead)->_pNext);
            *ppHead = NULL;
        }
        //3.两个及以上的元素:找最后一个元素,删除
        else
        {
            while (cur->_pNext->_pNext != NULL)
            {
                cur = cur->_pNext;
            }
            free(cur->_pNext);
            cur->_pNext = NULL;
        }
    }

    5.头部插入
    单链表的头部插入都需要改变指向链表指针的指向,所以不分情况可以直接操作
    
    //头部插入
    void PushFront(SLinkList** ppHead, DataType data)
    {
        SLinkList* NewNode = NULL;
        assert(ppHead);
    
        NewNode = BuyNode(data);
    
        NewNode->_pNext = *ppHead;
        *ppHead = NewNode;
    }
    6.头部删除
    单链表为空,不能随其进行删除操作,所以需要分别其为空链表还是非空链表
    
    //头部删除
    void PopFront(SLinkList** ppHead)
    {
        SLinkList* cur = *ppHead;
        assert(ppHead);
        //1.空链表,不能删除
        if (*ppHead == NULL)
        {
            printf("单链表为空,不能删除!!!\n");
            return;
        }
        //2.非空链表
        *ppHead = cur->_pNext;
        free(cur);
        cur = NULL;
    }
    7.查找元素的位置

     从单链表的第一个节点开始,判断当前节点的数据域的值是否与给定的值相等。若相等,则返回该节点的地址,否则继续比较下一个节点,直到链表结束。若节点不存在,则返回空。

    //查找元素的位置
    SLinkList* Find(SLinkList* pHead, DataType data)
    {
        SLinkList* cur = pHead;
        while (cur != NULL)
        {
            if (cur->_data == data)
                break;
            cur = cur->_pNext;
        }
        return cur; //有可能返回空值或所查元素的地址
    }
    8.指定位置删除元素

     遍历单链表,由于要删除指定位置的元素,需要将前一个节点的next指针域指向被删除节点的下一个节点。
    这里写图片描述

    //指定位置删除元素
    void Delete(SLinkList** ppHead, SLinkList* pos)
    {
        SLinkList* cur = *ppHead;
        SLinkList* del = NULL;
        assert(ppHead);
        //空链表
        if (*ppHead == NULL)
            return;
        //要删除位置元素为第一个节点
        if (*ppHead == pos)
            PopFront(ppHead);
        while (cur != NULL && cur->_pNext != pos)
        {
            cur = cur->_pNext;
        }
        if (cur != NULL)
        {
            cur->_pNext = cur->_pNext->_pNext;
            free(pos);
            pos = NULL;
        }
    }
    9.删除第一个出现的元素

     找到第一个指定元素出现的元素的前一个节点,指向被删除元素的下一个节点。因为是使用malloc开辟的空间,所以要用free()释放掉。
    这里写图片描述

    //删除第一个出现的指定元素
    void Revome(SLinkList** ppHead, DataType data)
    {
        SLinkList* cur = *ppHead;
        SLinkList* pre = NULL;
        assert(ppHead);
        //链表为空
        if (*ppHead == NULL)
            PopFront(ppHead);
        //链表非空
        while (cur != NULL)
        {
            if (cur->_data == data)
            {
                //首节点为所删元素
                if (pre == NULL)
                    PopFront(ppHead);   //头删法
                else
                {
                    pre->_pNext = cur->_pNext;
                    free(cur);
                    cur = NULL;
                }
                return;
            }
            pre = cur;
            cur = cur->_pNext;
        }
    }
    10.删除出现的所有元素

    这里写图片描述

    //删除出现的所有元素
    void RemoveAll(SLinkList** ppHead, DataType data)
    {
        SLinkList* cur = *ppHead;
        SLinkList* pre = NULL;
        SLinkList* del = NULL;
        assert(ppHead);
        //空链表
        if (*ppHead == NULL)
            return;
        //非空链表
        while (cur != NULL)
        {
            if (cur->_data == data)
            {
                //要删除的元素是第一个节点
                if (pre == NULL)
                {
                    del = cur;
                    cur = cur->_pNext;
                    *ppHead = cur;
                }
                else
                {
                    //用del指定需要被删除的元素,将被删除元素从链表上取下来
                    del = cur;
                    cur = cur->_pNext;
                    pre->_pNext = cur;
                }
                //删除需要删除的结点
                free(del);
                del = NULL;
            }
            else
            {
                pre = cur;
                cur = cur->_pNext;
            }
        }
    }
    11.计算单链表的长度

     利用count,对链表的结点进行计数。

    //计算单链表的长度
    int GetLinkListLength(SLinkList* pHead)
    {
        SLinkList* cur = pHead;
        int len = 0;
        //空链表
        if (pHead == NULL)
            return 0;
        //非空链表
        while (cur != NULL)
        {
            len++;
            cur = cur->_pNext;
        }
        return len;
    }
    11.冒泡排序

       外循环为链表的长度-1次,设置一个尾结点,外循环每执行一次,尾结点向前移动一步。

    //冒泡排序
    void BubbleSort(SLinkList** ppHead)
    {
        SLinkList* pTail = NULL;    //标记:未排序元素的最后一个元素
        SLinkList* pPre = NULL;
        SLinkList* pCur = NULL;
    
        assert(ppHead);
        //趟数
        while (pTail != *ppHead)
        {
            pPre = *ppHead;
            pCur = *ppHead;
            //单趟
            while (pCur != pTail)
            {
                //升序
                if (pPre->_data > pCur->_data)
                {
                    DataType tmp = pPre->_data;
                    pPre->_data = pCur->_data;
                    pCur->_data = tmp;
                }
                pPre = pCur;
                pCur = pCur->_pNext;
            }
            pTail = pPre;
        }
    }
    12.选择排序
    void SelectsortLinkList(SLinkList *pHead)
    {
        SLinkList *max = pHead;  //最大值指针
        SLinkList *tail = pHead;
        SLinkList *cur = NULL;
        DataType node = 0;
        int length = GetLinkListLength(pHead) - 1;
        //尾结点,tail指向空
        while (tail != NULL)
        {
            tail = tail->_pNext;
        }
        while (length--)
        {
            max = pHead;
            cur = pHead->_pNext;
            while (cur->_pNext != tail)
            {
                //找到链表的最大值
                if (cur->_data > max->_data)
                {
                    max = cur;
                }
                cur = cur->_pNext;
            }
            //比较链表尾结点是不是最大值
            if (cur->_data > max->_data)
            {
                max = cur;
            }
            if (max != cur)
            {
                //交换
                node = max->_data;
                max->_data = cur->_data;
                cur->_data = node;
            }
            tail = cur;
        }
    }
    展开全文
  • 单链表及其节点 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域, 一个域用于数据元素的存储,另一个域是指向其他单元的指针。 这里具有一个数据域和多个指针域的存储单元通常...

    单链表及其节点

    链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,
    一个域用于数据元素的存储,另一个域是指向其他单元的指针。
    这里具有一个数据域和多个指针域的存储单元通常称为 结点(node)

    一种最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素,
    指针域用于指向下一个具有相同结构的结点。
    因为只有一个指针结点,称为单链表 
     
        
    链表的第一个结点和最后一个结点,分别称为链表的 首结点和 尾结点。
    尾结点的特征是其 next 引用为空(null)。
    链表中每个结点的 next 引用都相当于一个指针,指向另一个结点,
    借助这些 next 引用,我们可以从链表的首结点移动到尾结点。
    在单链表中通常使用 head 引用来指向链表的首结点,由 head 引用可以完成对整个链表中所有节点的访问。

         
        在单链表结构中还需要注意的一点是,由于每个结点的数据域都是一个 Object 类的对象,
        因此,每个数据元素并非真正如图中那样,而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。
    与数组类似,单链表中的结点也具有一个线性次序,即如果结点 P 的 next 引用指向结点 S,则 P 就是 S 的直接前驱,S 是 P 的直接后续。
    单链表的一个重要特性就是只能通过前驱结点找到后续结点,而无法从后续结点找到前驱结点。


    单链表的查询、添加、删除操作分析
        查询操作
        在单链表中进行查找操作,只能从链表的首结点开始,通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作。
        
    例如需要在单链表中查找是否包含某个数据元素 e,则方法是使用一个循环变量 p,起始时从单链表的头结点开始,
    每次循环判断 p所指结点的数据域是否和 e 相同,如果相同则可以返回 true,否则让p指向下一个节点,继续循环直到链表中所有
    结点均被访问,此时 p 为 null
         

             关键操作:
            1.起始条件:p = head;
            2.结束条件:
                找到:e.equals(p.getData())==true
                未找到  p == null
            3.p指向下一个结点: p  = p.getNext();
            
            缺点:逐个比较,频繁移动指针,导致效率低下
            
            注意:如果要查询第i个元素的值,无法直接定位,也只能从首结点开始逐个移动到第i个结点,效率同样低下。
        添加操作
        在单链表中数据元素的插入,是通过在链表中插入数据元素所属的结点来完成的。
        对于链表的不同位置,插入的过程会有细微的差别。
        中间、末尾的添加过程其实是一样的,关键是在首部添加,会有不同,会改变整个单链表的起始结点。
        
         

            以添加中间结点为例
            1.指明新结点的后继  s.setNext(p.getNext());   或者 s.next = p.next
            2.指明新结点的前驱(其实是指明前驱结点的后继是新结点) p.setNext(s)    或者 p.next = s;
            
        添加节点不需要移动元素,只需要修改元素的指针即可,效率高。
        但是如果需要先查询到添加位置再添加新元素,因为有逐个查询的过程,效率不高。


        删除操作
            类似添加操作
             
             
        
        在使用单链表实现线性表的时候,为了使程序更加简洁,我们通常在单链表的最前面添加一个哑元结点,也称为头结点。
        在头结点中不存储任何实质的数据对象,其 next 域指向线性表中 0 号元素所在的结点,
        可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便,常用头结点。
        一个带头结点的单链表实现线性表的结构图如图 所示。
         

    单链表的代码实现:

    
    /**
     * 单链表
     * @author Administrator
     *
     */
    public class SingleLinkedList implements List{
    	
    	public Node head = new Node();//只有一个头结点
    	
    	public int size;//默认长度是0,头结点不算
    	
    	public SingleLinkedList(){
    		
    	}
    
    	@Override
    	public int size() {
    		
    		return size;
    	}
    	/**
    	 * 和数组可是不一样了!!!
    	 */
    	@Override
    	public Object get(int i) {
    		return null;
    	}
    
    	@Override
    	public boolean isEmpty() {		
    		return size == 0;
    	}
    
    	@Override
    	public boolean contains(Object e) {		
    		return this.indexOf(e)>=0;
    	}
    
    	@Override
    	public int indexOf(Object e) {
    		Node p = head.getNext();
    		for(int i = 0 ;i<size;i++){
    			//取出当前结点的值
    			Object data = p.getData();
    			//判断是否相同
    			if(e.equals(data)){
    				return i;
    			}
    			//移动指针
    			p = p.getNext();
    		}
    		
    		return -1;
    	}
    
    	@Override  
    	public void add(int i, Object e) {
    		//判断i的范围,提高健壮性
    		if(i<0 || i>size){
    			throw new IndexOutOfBoundsException("索引越界异常:"+i);
    		}
    		//定位到前一个结点
    		Node p = head;
    		for(int j = 0 ;j<i;j++){
    			p = p.getNext();
    		}
    		
    		//创建一个新结点
    		Node s = new Node();
    		s.setData(e);
    		
    		//完成添加操作
    		s.setNext(p.getNext());//指明新结点的后继
    		p.setNext(s);//指明新结点的前驱(其实是指明前驱结点的后继是新结点)
    		
    		//size增1
    		size++;
    	}	
    	
    
    	@Override
    	public void add(Object e) {
    		int i = this.size;
    		this.add(i,e);
    		
    	}
    
    	@Override
    	public boolean addBefore(Object obj, Object e) {
    		return false;
    	}
    
    	@Override
    	public boolean addAfter(Object obj, Object e) {
    		return false;
    	}
    
    	@Override
    	public Object remove(int i) {
    		
    		return null;
    	}
    
    	@Override
    	public boolean remove(Object e) {
    		//先确定前驱结点和要删除结点
    		Node p = head;  
    		Node s = head.getNext();
    		boolean flag = false;//默认该结点不存在
    		while(s!= null ){
    			//判断是否找到
    			if(e.equals(s.getData())){
    				flag = true;
    				break;
    			}
    			//如果没有找到,移动指针到后一个结点
    			p = s;
    			s = s.getNext();			
    		}
    		//如果找到,就删除
    		if(flag){
    			p.setNext(s.getNext());
    			s.setNext(null);
    			s =null;
    		}
    		return flag;
    		
    	}
    
    	@Override
    	public Object replace(int i, Object e) {
    		return null;
    	}
    
    	@Override
    	public String toString() {
    		StringBuilder builder = new StringBuilder("[");
    		Node p = head.getNext();
    		while(p!=null){			
    			//取出结点值
    			Object data = p.getData();
    			//加入StringBuffer
    			builder.append(data+",");
    			//后移一个结点
    			p = p.getNext();
    		}
    		//删除最后的一个逗号
    		if(builder.length()>1){
    			builder.deleteCharAt(builder.length()-1);
    		}
    		builder.append("]");
    		
    		return builder.toString();
    	}
    	
    	
    }
    
    
    	测试类
    public class Test {
    	
    	public static void main(String[] args) {
    		//创建线性顺序表
    		List list = new SingleLinkedList();
    		//向末尾添加元素
    		list.add("11111");
    		list.add("aaaaa");
    		list.add("bbbbb");
    		list.add("33333");
    		list.add("22222");
    		
    		list.add(2, "AAAAA");
    		System.out.println(list.toString());
    		list.remove("AAAAA");
    		System.out.println(list.toString());
    		//进行各种操作验证添加
    //		System.out.println(list.size());
    //		System.out.println(list.isEmpty());
    //		System.out.println(list.contains("AAAAA"));
    //		System.out.println(list.indexOf("22222"));
    //		
    //		System.out.println(list.toString());
    		
    	}
    
    }
    

    作业
    1.提取获取第i结点前一个结点方法:getPreviousNode(int i)
       提取data是e结点前一个结点方法:getPreviousNode(Object e)
       并进行重用
    2.完成SingleLinkedList类没有实现的方法
     

    展开全文
  • 单链表的存储方式

    链表的分类及存储方式

    单链表

    在这里插入图片描述
    在这里插入图片描述

    双链表

    在这里插入图片描述
    在这里插入图片描述

    双向循环链表

    在这里插入图片描述
    在这里插入图片描述

    创建一个单链表

    //不是链表的结构体
    //链表中一个节点的结构体
    typedef struct SListNode {
    	DataType data; // 值 
    	struct SListNode *Next; // 指向下一个结点 
    } SListNode;
    

    链表要实现的功能

    // 初始化 ,构造一条空的链表
    void SListInit(SListNode **ppFirst);
    
    //打印链表
    void SListInit(SListNode **ppFirst);
    
    // 尾部插入 
    void SListPushBack(SListNode** ppFirst, DataType data);
    
    // 头部插入 
    void SListPushFront(SListNode **ppFirst, DataType data);
    
    // 尾部删除 
    void SListPopBack(SListNode **ppFirst);
    
    // 头部删除 
    void SListPopFront(SListNode **ppFirst);
    
    // 给定结点插入,插入到结点前 
    void SListInsert(SListNode **ppFirst, SListNode *pPos, DataType data);
    
    // 给定结点删除 
    void SListErase(SListNode **ppFirst, SListNode *pPos);
    
    // 按值删除,只删遇到的第一个 
    void SListRemove(SListNode **ppFirst, DataType data);
    
    // 按值删除,删除所有的 
    void SListRemoveAll(SListNode **ppFirst, DataType data);
    
    // 销毁 ,需要销毁每一个节点
    void SListDestroy(SListNode **ppFirst);
    
    // 按值查找,返回第一个找到的结点指针,如果没找到,返回 NULL 
    int SListFind(SListNode *pFirst, DataType data);
    

    链表的各种功能具体实现

    链表的初始化

    void SListInit(SListNode **ppFirst)//初始化
    {
    	assert(ppFirst != NULL);
    	*ppFirst = NULL;
    }
    

    打印链表

    //打印链表
    void SListPrint(SListNode *First)
    {
    	for (SListNode*cur = First; cur != NULL; cur = cur->Next)
    	{
    		printf("%d-->", cur->data);
    	}
    	printf("\n");
    	return 0;
    }
    

    尾插

    在这里插入图片描述

    //申请新节点
    static SListNode* CreateNode(DataType data)
    {
    	SListNode*node = (SListNode*)malloc(sizeof(SListNode));
    	node->data = data;
    	node->Next = NULL;
    	return node;
    }
    // 尾部插入 
    void SListPushBack(SListNode** ppFirst, DataType data)
    {
    	assert(ppFirst != NULL);
    	SListNode *node = CreateNode(data);
    	if (*ppFirst == NULL)//判断链表不为空
    	{
    		*ppFirst = node;
    		return;
    	}
    	//找链表中的最后一个节点
    	SListNode* cur = *ppFirst;
    	while (cur->Next != NULL)
    	{
    		cur = cur->Next;
    	}
    	cur->Next = node;//插入新申请的节点
    }
    

    头插

    void SListPushFront(SListNode **ppFirst, DataType data)
    {
    	assert(ppFirst != NULL);
    	SListNode *node = CreateNode(data);
    	node->Next = *ppFirst;
    	*ppFirst = node;
    }
    

    尾删

    在这里插入图片描述

    // 尾部删除 
    void SListPopBack(SListNode **ppFirst)
    {
    	assert(ppFirst != NULL);
    	assert(*ppFirst != NULL);
    	if ((*ppFirst)->Next == NULL)
    	{
    		free(*ppFirst);
    		*ppFirst = NULL;
    		return;
    	}
    	SListNode*cur = *ppFirst;
    	while (cur->Next->Next != NULL)
    	{
    		cur = cur->Next;
    	}
    	free(cur->Next);
    	cur->Next = NULL;
    }
    

    头删

    在这里插入图片描述

    // 头部删除 
    void SListPopFront(SListNode **ppFirst)
    {
    	assert(ppFirst != NULL);
    	assert(*ppFirst != NULL);//链表不是空链表
    	SListNode *first = *ppFirst;
    	*ppFirst = (*ppFirst)->Next;
    	free(first);
    }
    

    给定结点插入,插入到结点前

    在这里插入图片描述

    void SListInsert(SListNode **ppFirst, SListNode *pPos, DataType data)
    {
    	assert(ppFirst != NULL);
    	if (*ppFirst == pPos)
    	{
    		SListPushFront(ppFirst, data);
    		return;
    	}
    	SListNode*newNode = CreateNode(data);
    	SListNode*cur;
    	//找到pos前的一个节点
    	for (cur = *ppFirst; cur->Next != pPos; cur = cur->Next){ }
    	//改变的是字段内的值,而不是指针的值
    	cur->Next = newNode;
    	newNode->Next = pPos;
    }
    

    给定结点删除

    在这里插入图片描述

    // 给定结点删除 
    void SListErase(SListNode **ppFirst, SListNode *pPos)
    {
    	if (*ppFirst == pPos)
    	{
    		SListPopFront(ppFirst);
    		return;
    	}
    	SListNode *cur = *ppFirst;
    	while (cur->Next != pPos)
    	{
    		cur = cur->Next;
    	}
    	cur->Next = pPos->Next;
    	free(pPos);
    }
    

    按值删除,只删遇到的第一个

    // 按值删除,只删遇到的第一个 
    void SListRemove(SListNode **ppFirst, DataType data)
    {
    	SListNode *cur = *ppFirst;
    	SListNode *prev = NULL;
    	assert(ppFirst != NULL);
    	if (*ppFirst == NULL)
    		return;
    	while (cur)
    	{
    		if (cur->data == data)
    		{
    			//删除
    			//1.删除的是第一个节点
    			if (*ppFirst == cur)
    			{
    				*ppFirst = cur->Next;
    				free(cur);
    				cur = NULL;
    			}
    			else//删除中间节点
    			{
    				prev->Next = cur->Next;
    				free(cur);
    				cur = NULL;
    			}
    			break;
    		}
    		prev = cur;
    		cur = cur->Next;
    	}
    }
    

    按值删除,删除所有的

    // 按值删除,删除所有的 
    void SListRemoveAll(SListNode **ppFirst, DataType data)
    {
    	SListNode *cur = NULL;
    	SListNode *prev = NULL;
    	assert(ppFirst != NULL);
    	if (*ppFirst == NULL)
    		return;
    	cur = *ppFirst;
    	while (cur)
    	{
    		if (cur->data == data)
    		{
    			//删除
    			//1.删除的是第一个节点
    			if (*ppFirst == cur)
    			{
    				*ppFirst = cur->Next;
    				free(cur);
    				cur = *ppFirst;
    			}
    			else//删除中间节点
    			{
    				prev->Next = cur->Next;
    				free(cur);
    				cur = prev;
    			}
    		}
    		prev = cur;
    		cur = cur->Next;
    	}
    }
    
    

    销毁 ,需要销毁每一个节点

    // 销毁 ,需要销毁每一个节点
    void SListDestroy(SListNode **ppFirst)
    {
    	SListNode*cur = NULL;
    	SListNode*del = NULL;
    	assert(ppFirst);
    	cur = *ppFirst;
    	while (cur)
    	{
    		del = cur;
    		cur = cur->Next;
    		free(del);
    		del = NULL;
    	}
    	*ppFirst = NULL;
    }
    

    按值查找,返回第一个找到的结点指针,如果没找到,返回 NULL

    // 按值查找,返回第一个找到的结点指针,如果没找到,返回 NULL 
    SListNode *  SListFind(SListNode *pFirst, DataType data)
    {
    	for (SListNode *cur = pFirst; cur != NULL; cur = cur->Next)
    	{
    		if (cur->data == data)
    		{
    			return cur;
    		}
    	}
    	return NULL;
    }
    

    如有不足之处,欢迎指正!!

    展开全文
  • 单链表

    2020-06-07 09:50:03
    文章目录概览:代码:B话少说,先把代码整出来结点:链表:创建:基本方法 概览: 链表简单来说就是把一个个结点连接起来,各个结点他不一定时连续的 单每个结点规定了有数据域,指向下一个结点的next域 ...

    概览:

    链表简单来说就是把一个个结点连接起来,各个结点他不一定时连续的
    单每个结点规定了有数据域,指向下一个结点的next域
    所以,它有这样的一些好处,

    1. 他不需要开辟一整块连续的空间来存储链表
    2. 它增加一个结点时,不用像数组一样移动后面的所有元素,只用规定上一个结点的next和这个结点的next域就好。

    代码:B话少说,先把代码整出来

    结点:

    class Node{
    	int no;
    	String data;
    	Node next;
    }
    构造方法,get/set方法,toString方法
    

    链表:

    创建:

    public class SingleLinkList{
    	private Node head;
    	public SingleLinkList(){
    		head = new node(0);
    	}
    

    基本方法

    找到某个节点
    必须要能找到才能插入啊

    public Node get(int i) throws Exception{
    	 Node temp = head;
            int j = 1;
            while(temp.no!=i || j<=i){
                temp = temp.next;
                j++;
            }
            if (temp.no == i){
                return temp;
            }else {
                throw new Exception("第"+i+"个结点不存在");
            }
    }
    

    添加结点
    把node结点插入到链表第i个

    public void add(Node node,int i){
    	Node preNode = this.get(i-1);
    	node.next = preNode.next;
    	preNode.next = add;
    }
    

    展示链表
    写到这先把这个方法写一下,方便测试自己其他方法有问题没

    public void show(){
    	Node temp = head;
    	while(temp.next != null){
    		temp = temp.next;
            System.out.println(temp.toString());
    	}//想连头节点一起看,把这两句调换一下位置就行
    }
    

    删除结点

    public void delNode(int i) throws Exception {
            if (i<0 || this.getNode(i)==null){
                throw new Exception("不存在该元素");
            }
    
            Node preNode = this.getNode(i-1);
            Node temp = preNode.next;
            preNode.next = temp.next;
        }
    

    清列表

     public void cleanList(){
            Node temp = head;
            while(temp.next!=null){
                temp = temp.next;
            }
            head.next = temp.next;
        }
    

    其实写到这,双链表和循环链表不想单独记博客了,感觉也没啥写的了
    双向链表就是把Node结点加了个指向上一个结点的域,随之而来的是链表增加结点和删除结点方法的改变,也差不多啦
    循环链表就是把最后一个结点指向头节点,让最后一个小朋友的手拉第一个小朋友,然后拉成一个圈…
    看着之前的笔记自己想着写的博客,欢迎订正,好吧~

    展开全文
  • 单链表的实现

    2019-06-21 11:30:56
    关于单链表的一些操作,今天重新梳理了一下 话不多说,先上代码 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int ElemType,Status; typedef struct LNode{ ...
  • 1、什么是链表?链表的分类? 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 数据结构中: 2、链表的分类 共有8种链表结构 ......
  • 链表: 通过一组任意的存储单元来存储线性表中的数据元素,由一个个结点构成。 链表之所以让初学者难以理解,是因为要回溯到上一个结点,并利用这个结点,很多人的思维一直都是往下面追溯,所以才会觉得难以理解,...
  • 单链表(1)

    2019-02-03 13:26:37
    • 头指针 – 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。 – 头指针具有标识作用,所以常用头指针冠以链表的名字(指针变量的名字)。 – 无论链表是否为空,头指针均不为空。...
  • 理解顺序表以及单链表各自的有点以及缺点! - 2.熟悉单链表的形式,对于头指针,头结点,尾结点,数据域和指针域这些名词要知道是什么! - 3.熟悉单链表的结点结构 - 4.区分**头指针**与**头结点**! - 5.熟悉创建...
  • Java单链表反转 Java实现单链表翻转 使用递归法实现单链表反转,使用遍历反转法:递归反转法是从后往前逆序反转指针域的指向,而遍历反转法是从前往后反转各个结点的指针域的指向。  【尊重原创,转载请注明出处】...
  • 单链表的创建算法

    2016-04-08 20:27:42
    单链表的创建算法  当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。  单链表的示意图如下:    Head指针为单链表的头指针,单链表L:L既是单链表的名字,也是其头指针。链表中的最后一个...
  • 如何把一个单链表进行反转? 方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。 方法2:使用3个指针遍历单链表,逐个链接点进行反转。 方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head...
  • 创建单链表 关于数据结构的入门,就是从顺序表和单链表开始。 我们不讲顺序表,直接从单链表开始我们的数据结构和算法的学习之路。 单链表就是一种特殊的结构体组合而成的数据结构,关于单链表的创建方法有很多种,...
  • 单链表的就地逆置

    2018-06-13 17:14:34
    单链表的就地逆置是指辅助空间O(1)的逆置方法,有两种方法:普通循环(头插法重新建立带头节点的新链表)和递归。下面我们详细介绍这两种方法:方法一:头插法算法思想:逆置链表初始为空,表中节点从原链表中依次...
  • 单链表的最大特点是可以将物理地址上不连续的数据连接起来,通过指针来对物理地址进行操作,实现增删改查等功能。 单链表分为两种:有头链表和无头链表。 无头单链表,也就是phead一只是一个指针,指向链表的第一...
  • 1.单链表的排序,排序算法有很多种,但是大多数是基于单链表的顺序存储的,单链表的排序要怎么实现。 大家都知道单链表最重要的就是指针,因为单链表不是顺序存储的,所以对排序时必须是指针的后移,才能访问下一个...
  • 单链表C++实现代码

    2020-05-06 15:44:26
    因为没什么事做就写一下单链表的操作,反正是基础数据结构,长时间不写的话再写会出现一下小的细节毛病,多练习练习,理解也更加深点。 单链表写顺,队列的入队出队就是单链表的头插和尾删而已,栈的入栈出栈就是...
  • 1. 已知单链表L为按值递增有序的,编写算法将数据元素e插入到单链表L中,使之仍有序。 2、编写算法单链表L中删除最后一个值为e的数据元素。 3、已知单链表L为按值递增有序的,编写算法将数据元素值在区间[e1,e2]内...
  • 解题思路:这道题本来是让反转单链表的,不过前提肯定是要以建立单链表。因此我分成了两个方法,一个init建立单链表,一个reverse反转单链表。(幸好做了这道题,不然都不会发现自己忘了单链表怎么建立,查漏补缺)...
  • 建立一个单链表

    2020-07-30 23:31:51
    建立一个单链表,在单链表上实现插入、删除和查找等操作,有菜单。 ⑴初始化字符型单链表H; ⑵采用尾插法建立单链表H,如(a,b,c,d,c); ⑶输出单链表H的长度; ⑷输出单链表H的第i个元素,如输出单链表H的第3...
1 2 3 4 5 ... 20
收藏数 100,953
精华内容 40,381
热门标签
关键字:

单链表