Python實現(xiàn)環(huán)形鏈表

第Python實現(xiàn)環(huán)形鏈表本文實例為大家分享了Python實現(xiàn)環(huán)形鏈表的具體代碼，供大家參考，具體內(nèi)容如下

我們將單向鏈表的最后一個節(jié)點的指針指向鏈表的頭部（第一個節(jié)點），那么就形成了一個環(huán)形鏈表。環(huán)形節(jié)點可以從任意節(jié)點開始遍歷其他的節(jié)點。

這里主要實現(xiàn)了環(huán)形鏈表節(jié)點的遍歷、添加、插入、刪除，反轉。

代碼如下：

classPlayer:

"""節(jié)點類"""

def__init__(self):

"""初始化姓名，分數(shù)，指針"""

=''

self.score=0

self.next=None

defergodic(head,num=None,is_print=False):

"""遍歷函數(shù)，num是遍歷到哪一個位置序號，is_print是否觸發(fā)打印方法"""

ifhead.nextisNone:

returnNone

ptr=head

count=0

whileTrue:

count+=1

ifis_print:

print('No.'+str(count),,ptr.score,'---',)

ifcount==num:

break

ifptr.next==head:

break

ptr=ptr.next

returnptr

#返回遍歷完成后的最后一個節(jié)點

definvert(x):

#x是鏈表的第一個節(jié)點

"""反轉環(huán)形鏈表"""

y=x.next

#y是x原來的next

x.next=ergodic(x)

#將第一個節(jié)點的next指向最后一個節(jié)點(因為反轉了)

whileTrue:

#循環(huán)反轉后面的所有節(jié)點

r=y.next

y.next=x

ifr==head:

#r是head說明y已經(jīng)是原本鏈表的最后一個節(jié)點了

returny

#返回y，這個y是反轉后的鏈表的第一個節(jié)點

x=y

y=r

head=Player()

ptr=head

whileTrue:

select=input("(1).新增

(2).查看

(3).插入

(4).刪除

(5).反轉

(6).離開\n輸入：")

ifselect=="1":

#新增節(jié)點

ptr=ergodic(head)

#獲取當前鏈表最后一個節(jié)點

ifptrisNone:

#ptr為None說明當前在添加第一個節(jié)點head

=input("姓名：")

head.score=input("分數(shù)：")

head.next=head

else:

#添加第一個節(jié)點之后的節(jié)點

next_data=Player()

next_=input("姓名：")

next_data.score=input("分數(shù)：")

next_data.next=head

ptr.next=next_data

elifselect=="2":

#遍歷查看鏈表所有節(jié)點

ergodic(head,is_print=True)

#遍歷鏈表，將打印參數(shù)設為True

elifselect=='3':

#向鏈表中任意位置插入節(jié)點，位置以序號表示，即第一個節(jié)點序號為1，第二個節(jié)點序號為2，以此類推

try:

num=int(input("請輸入需要插入的節(jié)點位置序號："))

#輸入序號必須是大于0的正整數(shù)，如果輸入大于最后一個節(jié)點的序號則插入到最后一個節(jié)點之后

ifnum1:

print("輸入必須為大于0的正整數(shù)")

continue

exceptValueError:

print("輸入有誤")

continue

ptr=ergodic(head,num-1)

#獲取需要插入位置的前一個節(jié)點

insert_data=Player()

insert_=input("姓名：")

insert_data.score=input("分數(shù)：")

insert_data.next=ptr.next

ptr.next=insert_data

ifnum==1:

#如果插入位置是1的話，那么head將發(fā)生變化

head=insert_data

elifselect=='4':

#刪除鏈表中任意位置的節(jié)點

try:

num=int(input("請輸入需要刪除的節(jié)點位置序號："))

#輸入序號必須是大于0的正整數(shù)，如果輸入大于最后一個節(jié)點的序號則刪除最后一個節(jié)點

ifnum1:

print("輸入必須為大于0的正整數(shù)")

continue

exceptValueError:

print("輸入有誤")

continue

ptr=ergodic(head,num-1)

#獲取需要刪除位置的前一個節(jié)點

ifptr==ergodic(head,num):

#輸入序號過大時需要做特殊處理，因為輸入序號過大也代表刪除最后一個節(jié)點，那么這時我需要獲取這最后一個節(jié)點的前一個節(jié)點

ptr=ergodic(ptr)

ptr.next=ptr.next.next

ifnum==1:

#如果刪除位置是1的話，那么head將發(fā)生變化

head=ptr.next

elifselect=='5':

#反轉鏈表

new_first=invert(head)

#獲取新的第一個節(jié)點

head=new_first

#head指向新的第一個節(jié)點

print