Java数据结构--串的链式存储结构

小灰灰 2023-10-06 09:50 27阅读 0赞

## `一、简介` ##

#### 1.1 串的概念 ####

> 串是一种特殊的线性表，其特殊性体现在数据元素时一个字符。  
> 串（或字符串）是由零个或多个字符串组成的有限序列。  
> 表示方法：S=“a1a2…an”  
> 其中：S是串名，双引号括起来的字符序列是串值；ai(1 <= i <= n)可以是字母、数字或其他字符；n为串的长度。  
> 将串值引起来的双引号本身不属于串，它的作用是避免串与常数或标识符混淆。  
> 长度为零的串称为空串，它不包含任意字符。  
> 通常将仅由一个或多个空格组成的串称为空白串。  
> 串中任意个连续字符组成的子序列称为该串的子串，包含子串对的串相应地称为主串。空串是任意串的子串，任意串是其自身的字串。  
> 子串在主串中的位置，以字串第一个字符在串的位置标示。  
> 当两个串的长度相等且各对应位置上的字符相同时，则这两个串相等。  
> 通常在程序中使用的串分为两种：串变量和串常量。在程序中串常量只能读不能写，通常是由直接量来表示。串变量是一块内存空间，里面存放的串值可以改变。

#### 1.2 串的链式存储结构 ####

> 按链式存储结构存储的串称为链串，与链表结构类似，只是链串数据域部分为字符。同样链串中结点有两个域，一个表示结点信息，称为数据域；一个表示当前结点的后续结点的引用，称为地址域。

#### 1.3 结构图 ####

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

## `二、简单实现` ##

public class LinkString {
        
    	// 头结点
    	Node head = new Node();
    	// 实际表长
    	int curlen;
    	
    	// 结点内部类
    	private class Node {
        
    		public char c;
    		public Node next;
    		
    		public Node() {
        
    			c = null;
    			next = null;
    		}
    	}
    	
    	/**
    	 * 查询
    	 * 1、在链表中查找某位置结点，则从链表头结点位置开始不断向下遍历链表，直到查找到对应位置的结点结束
    	 * 2、返回查找结点，否则结点不存在。
    	 * 
    	 * @param i
    	 * @return
    	 */
    	public Node query(int i) {
        
    		Node p = head;
    		if (i < 0 || i > curlen) {
        
    			return p;
    		}
    		for (int j = 0; j <= i; j++) {
        
    			p = p.next;
    		}
    		return p;
    	}
    	
    	/**
    	 * 插入
    	 * 1、找到插入前位置，如存在则继续，否则结束；
    	 * 2、申请、填装新结点；
    	 * 3、插入新结点，结束。
    	 * 
    	 */
    	public void insert(Cahr c, int i) {
        
    		Node data = new Node();
    		data.c = c;
    		if(i < 0 || i > curlen) {
        
    			System.out.println("i值无效");
    			return;
    		}
    		if (curlen == 0) {
        
    			head.next = data;
    		} else {
        
    			// 查询插入元素的前一个元素
    			Node p = query(i - 1);
    			// 修改前一个元素的指针
    			data.next = p.next;
    			p.next = data;
    		}
    		curlen++;
    	}
    	
    	/**
    	 * 删除结点
    	 * 
    	 * 1、找到删除结点直接前驱对应的位置，若存在则继续，否则结束；
    	 * 2、若要删除的结点存在则继续，否则继续；
    	 * 3、删除对应位置结点，结束。
    	 * 
    	 * @param i
    	 */
    	public Node delete(int i) {
        
    		Node node; // 保存删除的第i个结点
    		// 判断删除位置是否正确
    		if (i < 0 || i > curlen) {
        
    			System.out.println("删除位置i无效");
    			return null;
    		}
    		// 查找要删除结点的前一个元素
    		Node p = query(i - 1);
    		node = p.next;
    		p.next = node.next;
    		curlen--;
    		return node;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526215132308.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70