数据结构-链表-单向链表

分手后的思念是犯贱 2023-10-04 13:17 46阅读 0赞

#### 数据结构-链表-单向链表 ####

##### 链表（Linked List）是由许多相同数据类型的数据按特定顺序排列而成的线性表。 #####

一个单向链表节点基本上是由两个元素（数据字段和指针）所组成的，而指针将会指向下一个元素在内存中的地址

在单向链表中，第一个节点是链表头指针，指向最后一个节点的指针设为None，表示它是链表尾，不指向任何地方。

1.  建立单向链表
    
    在python中，先定义一个类，关键属性是next（指针字段）
    
        class student:
        		def __init__(self):
        				self.name = ''
        				self.score = 0
        				self.next = None
    
    完成之后就是链表的设计，首先需要指定链表头，可以实例一个对象，然后指定next的元素，随后逐渐将next后移，即是将next赋值为下一个元素
    
        head = student()  #建立链表头
        head.next = None	#链表头的下一个元素指向None
        ptr = head	#初始指针的位置，从第一个开始
        select = 0
        
        while select != 2:
        		print("(1) 新增	(2) 离开")
        		try:
        				select = int (input('请输入选项：'))
        		except ValueError:
        				print("输入错误，请重新输入/n")
        		if select ==1:
        				new_data = student()	#新增下一个元素
        				new_data.name = input('姓名：')
        				new_data.score = input('成绩：')
        				ptr.next = new_data		#指针指向新的元素
        				new_data.next = None		#新元素的next设置为None
        				ptr = ptr.next		#指针后移
2.  遍历单向数组
    
    遍历的过程就是使用指针运算来访问链表的每个节点，在循环中逐渐将指针后移，实现链表的遍历
    
        ptr = head.next		#设置存取指针从链表的头部开始
        while ptr != None:
        		print('姓名：%s/t成绩：%d'%(ptr.name,ptr.score))
        		ptr = ptr.next		#将ptr移动下一个元素
3.  在单向链表中插入新节点
    
    可以分为三种情况，在链表的头部，链表的尾部，链表中间的任意位置
    
     *  插入到链表的头部
        
            newnode.next = first
            first = newnode
     *  插入到尾部
        
            ptr.next = newnode
            newnode.next = None
     *  插入到链表中的任意位置
        
            newnode.next = x.next
            x.next = newnode
4.  单向链表中删除节点
    
    可以分为三种情况，在链表的头部，链表的尾部，链表中间的任意位置
    
     *  在链表的头部
        
        头部删除的节点是top
        
            top = head
            head = head.next
     *  在链表的尾部
        
            ptr.next = tail
            ptr.next = None
     *  在链表中间的任意位置
        
        删除的元素是 y
        
            y = ptr.next
            ptr.next = y.next
5.  单向链表的反转
    
    简单地说，就是将链表的指向反转过来，就需要三个指针常量来转换
    
        class employee:
        		def __init__(self):
        				self.name = ''
        				self.salary = 0
        				self.next = None
        	
        	def invert(x):		#x为链表的头指针
        			p = x 	#将p指向链表的开头
        			q = None		#q是p的前一个节点
        			while p != None:
        					r =q	#将r接到q之后
        					q = p	#将q接到p之后
        					p = p.next	#p移到一下个节点
        					q.next = r	#q连接到之前的节点
        			return q
6.  单向链表的连接
    
    只需要将一个的尾部与另一个的头部相连即可
    
        def concatlist(ptr1,ptr2):	#ptr1和ptr2分别是链表头
        		ptr = ptr1
        		while ptr.next != None:		#找到ptr1的尾部元素
        				ptr = ptr.next
        		ptr.next = ptr2
        		return ptr1
7.  多项式链表表示法
    
    在数组结构中也表示过多项式，但是使用数组结构表示时常出现一些问题，比如在多项式内容变化时，对数组结构影像相当大，算法处理也不容易。由于数组是静态数据结构，因此事先需要定义一块连续的且足够大的内存空间，这样就容易造成了内存空间浪费
    
    使用链表表示，每一个元素需要三个变量
    
    <table> 
     <thead> 
      <tr> 
       <th>COEF</th> 
       <th>EXP</th> 
       <th>LINK</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>表示该变量的系数</td> 
       <td>表示该变量的指数</td> 
       <td>指向下一个节点的指针</td> 
      </tr> 
     </tbody> 
    </table>
    
    A(x) = 3X^3 + 6X -2表示为
    
    <table> 
     <thead> 
      <tr> 
       <th>COEF</th> 
       <th>EXP</th> 
       <th>LINK</th> 
       <th></th> 
       <th>COEF</th> 
       <th>EXP</th> 
       <th>LINK</th> 
       <th></th> 
       <th>COEF</th> 
       <th>EXP</th> 
       <th>LINK</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>3</td> 
       <td>2</td> 
       <td>\</td> 
       <td>------&gt;</td> 
       <td>6</td> 
       <td>1</td> 
       <td>\</td> 
       <td>------&gt;</td> 
       <td>-2</td> 
       <td>0</td> 
       <td>\</td> 
      </tr> 
     </tbody> 
    </table>
    
        def create_link(data):		#建立多项式子程序
        		newnode = LinkedList()
        		if not newnode:
        				print('内存分配失败')
        				sys.exit(0)
        		if i == 0:
        				newnode.coef = data[i]
        				newnode.exp = 3 - i
        				newnode.next = None
        				head = newnode
        				ptr = head
        		elif data[i] != 0:
        				newnode.coef =data[i]
        				newnode.exp = 3 - i
        				newnode.next = None
        				ptr.next = newnode
        				ptr = newnode
        		return head