Python常见的数据结构实现

　　一、链表class LinkNode:                         #单链表结点类     def __init__(self,data=None):       #构造函数         self.data=data                  #data属性         self.next=None  class LinkList:                         #单链表类     def __init__(self):                 #构造函数         self.head=LinkNode()            #头结点head         self.head.next=None       def CreateListF(self, a):		    #头插法：由数组a整体建立单链表         for i in range(0,len(a)):       #循环建立数据结点s             s=LinkNode(a[i])			#新建存放a[i]元素的结点s             s.next=self.head.next		#将s结点插入到开始结点之前,头结点之后             self.head.next=s       def CreateListR(self, a):			#尾插法：由数组a整体建立单链表         t=self.head						#t始终指向尾结点,开始时指向头结点         for i in range(0,len(a)):		#循环建立数据结点s             s=LinkNode(a[i]);			#新建存放a[i]元素的结点s             t.next=s					#将s结点插入t结点之后             t=s         t.next=None						#将尾结点的next成员置为null      def geti(self, i):		            #返回序号为i的结点         p=self.head         j=-1         while (j=0                             #检测参数i正确性的断言         p=self.geti(i)         assert p is not None                    #p不为空的检测                return p.data      def __setitem__(self, i, x):                #设置序号为i的元素         assert i>=0                             #检测参数i正确性的断言         p=self.geti(i)         assert p is not None                    #p不为空的检测         p.data=x      def GetNo(self,e):							#查找第一个为e的元素的序号         j=0         p=self.head.next	         while p is not None and p.data!=e:             j+=1									#查找元素e             p=p.next         if p is None:             return -1						    #未找到时返回-1         else:             return j							#找到后返回其序号      def Insert(self, i, e):					    #在线性表中序号i位置插入元素e         assert i>=0                             #检测参数i正确性的断言         s=LinkNode(e)		                    #建立新结点s         p=self.geti(i-1)				        #找到序号为i-1的结点p         assert p is not None                    #p不为空的检测                s.next=p.next							#在p结点后面插入s结点         p.next=s      def Delete(self,i): 						#在线性表中删除序号i位置的元素         assert i>=0							    #检测参数i正确性的断言         p=self.geti(i-1)					    #找到序号为i-1的结点p         assert p.next is not None               #p.next不为空的检测                p.next=p.next.next;						#删除p结点的后继结点      def display(self):					        #输出线性表         p=self.head.next         while p is not None:             print(p.data,end=＂ ＂)             p=p.next;         print()if __name__ == ＂__main__＂:   L=LinkList()   for i in range(1,6):     L.Add(i)   print(＂L: ＂,end=＂＂),L.display()   print(＂序号为2的元素=%d＂ %(L[2]))   print(＂设置序号为2的元素为8＂)   L[2]=8   print(＂序号为2的元素=%d＂ %(L[2]))   n=L.getsize()   print(＂size=%d＂ %(n))   for i in range(0,n):     print(＂删除%d序号的元素＂ %(0))     L.Delete(0)     print(＂L: ＂,end=＂＂),L.display()   print(＂size=%d＂ %(L.getsize()))
　　二、顺序表 class SqList:     def __init__(self):							#构造函数         self.initcapacity=5;           		    #初始容量设置为10         self.capacity=self.initcapacity			#容量设置为初始容量         self.data=[None]*self.capacity			#设置顺序表的空间         self.size=0								#长度设置为0       def resize(self, newcapacity):				#改变顺序表的容量为newcapacity         assert newcapacity>=0					#检测参数正确性的断言         olddata=self.data         self.data=[None]*newcapacity         self.capacity=newcapacity         for i in range(self.size):             self.data[i]=olddata[i]      def CreateList(self, a):                    #由数组a中元素整体建立顺序表         for i in range(0,len(a)):             if self.size==self.capacity:		#出现上溢出时                 self.resize(2*self.size);	    #扩大容量             self.data[self.size]=a[i]             self.size+=1                        #添加后元素个数增加1      def Add(self, e): 			        		#在线性表的末尾添加一个元素e         if self.size==self.capacity:		    #顺序表空间满时倍增容量             self.resize(2*self.size)         self.data[self.size]=e					#添加元素e         self.size+=1				        	#长度增1      def getsize(self):                          #返回长度         return self.size         def __getitem__(self,i):                    #求序号为i的元素         assert 0<=i=self.size):						#未找到时返回-1             return -1;         else:             return i;							#找到后返回其序号      def Insert(self, i, e):                     #在线性表中序号i位置插入元素e         assert 0<=i<=self.size                  #检测参数i正确性的断言         if self.size==self.capacity:		    #满时倍增容量             self.resize(2*self.size)         for j in range(self.size,i,-1):	        #将data[i]及后面元素后移一个位置             self.data[j]=self.data[j-1]         self.data[i]=e			        		#插入元素e         self.size+=1				        	#长度增1      def Delete(self, i): 		        		#在线性表中删除序号i的元素         assert 0<=i<=self.size-1	        	#检测参数i正确性的断言         for j in range(i,self.size-1):             self.data[j]=self.data[j+1]         #将data[i]之后的元素前移一个位置         self.size-=1                            #长度减1         if self.capacity>self.initcapacity and self.size<=self.capacity/4:             self.resize(self.capacity//2)       #满足要求容量减半                  def display(self):		                	#输出顺序表         for i in range(0,self.size):             print(self.data[i],end=＂ ＂)         print()  if __name__ == ＂__main__＂:     L=SqList()     for i in range(1,6):         L.Add(i)     print(＂L: ＂,end=＂＂),L.display()     print(＂序号为2的元素=%d＂ %(L[2]))     print(＂设置序号为2的元素为8＂)     L[2]=8     print(＂序号为2的元素=%d＂ %(L[2]))     n=L.getsize()     print(＂size=%d＂ %(n))     for i in range(0,n):         print(＂删除%d序号的元素＂ %(0))         L.Delete(0)         print(＂L: ＂,end=＂＂),L.display()     print(＂size=%d＂ %(L.getsize()))
　　三、顺序栈 #顺序栈 class SqStack:     def __init__(self):             #构造函数         self.data=[]                #存放栈中元素，初始为空      def empty(self):                #判断栈是否为空         if len(self.data)==0:             return True         return False      def push(self,e):               #元素e进栈         self.data.append(e)      def pop(self):                  #元素出栈         assert not self.empty()     #检测栈为空         return self.data.pop()      def gettop(self):               #取栈顶元素         assert not self.empty()     #检测栈为空         return self.data[len(self.data)-1]  if __name__ == ＂__main__＂:     st=SqStack()     st.push(1)     st.push(2)     st.push(3)     st.push(4)     print(＂出栈顺序:＂,end=＂ ＂)     while not st.empty():         print(st.pop(),end=＂ ＂)     print()
　　四、非循环列表 MaxSize=100                             #假设容量为100 class SqQueue:      			        #非循环队列类     def __init__(self):                 #构造方法         self.data=[None]*MaxSize        #存放队列中元素         self.front=-1                   #队头指针         self.rear=-1                    #队尾指针          def empty(self):				    #判断队列是否为空         return self.front==self.rear      def push(self,e):				    #元素e进队         assert not self.rear==MaxSize-1      #检测队满         self.rear+=1         self.data[self.rear]=e              def pop(self):						#出队元素         assert not self.empty()         #检测队空         self.front+=1         return self.data[self.front]         def gethead(self):					#取队头元素         assert not self.empty()         #检测队空         return self.data[self.front+1]  if __name__ == ＂__main__＂:     qu=SqQueue()     qu.push(1)     qu.push(2)     qu.push(3)     while not qu.empty():         print(qu.pop(),end=＂ ＂)     print()
　　五、链栈 class LinkNode:                         #单链表结点类     def __init__(self,data=None):       #构造方法         self.data=data                  #data域         self.next=None                  #next域  class LinkStack:                        #链栈类     def __init__(self):                 #构造方法         self.head=LinkNode()            #头结点head         self.head.next=None      def empty(self):                    #判断栈是否为空         if self.head.next==None:             return True         return False              def push(self,e):                   #元素e进栈         p=LinkNode(e)         p.next=self.head.next         self.head.next=p      def pop(self):                      #元素出栈         assert self.head.next!=None     #检测空栈的异常         p=self.head.next;         self.head.next=p.next         return p.data      def gettop(self):                     #取栈顶元素         assert self.head.next!=None         #检测空栈的异常         return self.head.next.data  if __name__ == ＂__main__＂:     st=LinkStack()     st.push(1)     st.push(2)     st.push(3)     st.push(4)     print(＂出栈顺序:＂,end=＂ ＂)     while not st.empty():         print(st.pop(),end=＂ ＂)     print()
　　六、链队 class LinkNode:                         #链队结点类     def __init__(self,data=None):       #构造方法         self.data=data                  #data域         self.next=None                  #next域 class LinkQueue:      			        #链队类     def __init__(self):                 #构造方法         self.front=None                 #队头指针         self.rear=None                  #队尾指针     def empty(self):					#判断队是否为空         return self.front==None     def push(self,e):			        #元素e进队         s=LinkNode(e)                   #新建结点s         if self.empty():				#原链队为空             self.front=self.rear=s         else:							#原链队不空             self.rear.next=s			#将s结点链接到rear结点后面             self.rear=s     def pop(self):						#出队操作         assert not self.empty()			#检测空链队         if self.front==self.rear:		#原链队只有一个结点             e=self.front.data			#取首结点值             self.front=self.rear=None	#置为空队         else:							#原链队有多个结点             e=self.front.data			#取首结点值             self.front=self.front.next	#front指向下一个结点         return e      def gethead(self):				    #取队顶元素操作         assert not self.empty()			#检测空链队         e=self.front.data			    #取首结点值         return e   if __name__ == ＂__main__＂:     qu=LinkQueue()     qu.push(1)     qu.push(2)     qu.push(3)     qu.push(4)     print(＂队头元素: %d＂ %(qu.gethead()))     print(＂出队顺序:＂,end=＂ ＂)     while not qu.empty():         print(qu.pop(),end=＂ ＂)     print()
　　七、顺序栈 #顺序栈 class SqStack:     def __init__(self):             #构造函数         self.data=[]                #存放栈中元素，初始为空      def empty(self):                #判断栈是否为空         if len(self.data)==0:             return True         return False      def push(self,e):               #元素e进栈         self.data.append(e)      def pop(self):                  #元素出栈         assert not self.empty()     #检测栈为空         return self.data.pop()      def gettop(self):               #取栈顶元素         assert not self.empty()     #检测栈为空         return self.data[len(self.data)-1]  if __name__ == ＂__main__＂:     st=SqStack()     st.push(1)     st.push(2)     st.push(3)     st.push(4)     print(＂出栈顺序:＂,end=＂ ＂)     while not st.empty():         print(st.pop(),end=＂ ＂)     print()