数据结构之线性表实现实验—原创

本次实验我们将是循环渐进的过程一步步的实现如何从一个单链表的节点类一步步的延申到增删改查等操作上

编写程序实现一下内容：

1. 创建一个单链表节点类，至少包括一个data和next两个域；创建一个单链表类；创建单链表判空方法；创建一个单链表对象SL，判定是否为空单链表，并输出结果。

程序代码：

class Node(object):#结点类

    def __init__(self,elem):#设置构造方法赋值

        self.elem=elem

        self.next=None #不知道地址所以设置为空

class tz(object):

    '''单链表'''

    def __init__(self):
    self.__head=None
def is_empty(self):
    return self.__head==None

if __name__=="__main__":
    SL=tz()
    print(SL.is_empty())

我们在这里class一个node节点类 设置一个构造方法并指向本身的元素 因为单链表刚开始头节点为空我们这里设置程self.node=none

程序输出：

true

尝试了一下省略“class Node（object）:”可以正常运行但是不用object会简洁

1. 在1基础上，创建单链表头插方法，向SL中连续插入data的值分别为4，3，2，1的4个节点；创建求链表长度方法；求插入节点后的SL的长度，并输出结果。

程序代码：

def toubu(self,item):
    node=Node(item)
    node.next=self.__head
    self.__head=node
def changdu(self):
    cur =self.__head
    count=0
    while cur!=None:
        count+=1
        cur=cur.next
    return count

程序输入：

SL.toubu(4)
SL.toubu(3)
SL.toubu(2)
SL.toubu(1)
print(SL.changdu())

程序输出：

True  

创建def头部的构造方法和changdu的构造方法 并让其循环加入数字来判断指针是否为空的条件最后返回count在程序输出结果即可

4

1. 在2基础上，创建单链表遍历方法，输出SL中的值，中间用逗号分隔。

程序代码：

def bianli(self):
    a=self.__head
    while a:
        print(a.item,end=' ')
        a=a.next
    print('')

程序输入：

SL.bianli()

程序输出：

1234,

1. 在2基础上，创建单链表尾插法，向SL中连续插入data的值分别为5，7，9，11，13的5个节点；插入后输出SL中的值，中间用空格分隔，并输出表长。

程序代码：

def bianli(self):
    a=self.__head
    while a:
        print(a.item,end=' ')
        a=a.next
    print('')
def weibu(self,item):
    node=Node(item)
    if self.is_empty():
        self.__head=node
    else:
        b=self.__head
        while b.next!=None:
            b=b.next
        b.next=node

程序输入：

SL.weibu(5)
SL.weibu(7)
SL.weibu(9)
SL.weibu(11)
SL.weibu(13)

print(SL.changdu())

程序输出：

1 2 3 4 5 7 9 11 13

尾插法：我们首先创建个构造方法遍历整个的元素 并让指针永远指向下一个节点 类似于头插法的方式创建尾插并输入信息 最后print输出即可

9

1. 创建在任意位置插入的节点的方法，实现在data值为5的节点之后插入一个data值为6的节点，插入后输出SL中的值，中间用空格分隔，并输出表长。

程序代码：

def renyi(self,pos,item):
    if pos<=0:
        self.toubu(item)
    elif pos>(self.changdu()-1):
        self.weibu(item)
    else:
        per=self.__head
        count=0
        while count<pos-1:
            count+=1
            per=per.next
        node=Node(item)
        node.next=per.next
        per.next=node

程序输入：

SL.renyi(5,6)
SL.bianli()
print(SL.changdu())

程序输出：

1 2 3 4 5 6 7 9 11 13

10

1. 创建单链表中删除指定元素的方法，实现在SL中data值为1、13和6的节点，每删除一个节点，进行一次SL中值的输出，中间用空格分隔，并输出表长。

程序代码：

def shanchu(self,item):
    cur=self.__head
    pre=None
    while cur!=None:
        if cur.item==item:
            if cur==self.__head:
                self.__head=cur.next
            else:
                pre.next=cur.next
            break
        else:
            pre=cur
            cur=cur.next

程序输入：

SL.shanchu(1)
SL.bianli()
SL.shanchu(13)
SL.bianli()
SL.shanchu(6)
SL.bianli()
print(SL.changdu())

程序输出：

2 3 4 5 6 7 9 11 13

2 3 4 5 6 7 9 11

2 3 4 5 7 9 11

7

1. 创建单链表查找指定元素的方法，实现在SL中查找data值为9和data值为15的节点，并输出查找的结果（是否存在？），如果表SL中存在，一并输出节点在单链表中的位置（设第一个节点的位置为1）。

程序代码：

def weizhi(self,item):
    tt=self.__head
    i=1
    while tt != None:
        if tt.item != item:
            i=i+1
            tt=tt.next
        else:
            return i

    def chazhao(self,item):
    cur = self.__head
    while cur != None:
        if cur.item == item:
            print("Ture,该节点在链表中的位置为：",end='')
            return self.weizhi(item)
        else:
            cur = cur.next
    return False

程序输入：

print(SL.chazhao(9))
print(SL.chazhao(15))

程序输出：

Ture,该节点在链表中的位置为：6

False

1. 创建单链表查找指定位置元素的方法，实现在SL中查找第5个元素，并将找到的元素输出。

程序代码：

def tzzs(self,item):
    cur= self.__head
    i=1
    while cur!= None:
        if i!=item:
            i+=1
            cur=cur.next
        else:
            return cur.item

程序输入：

print(SL.tzzs(5))

程序输出：

7

1. 在单链表递增有序的基础上，创建将元素x插入，保持其有序性方法；实现在SL中插入data值为8的元素，使SL仍然有序，输出SL的值。

程序代码：

def xiaozhen(self,item):
    node=Node(item)
    if self.is_empty():
        self.__head=node
    else:
        cur=self.__head
        i=0
        while cur!=None:
            if cur.item<item:
                i+=1
                cur=cur.next
            else:
                return self.renyi(i,item)

程序输入：

SL.xiaozhen(8)
SL.bianli()

程序输出：

234578911

1. 针对单链表创建删除自第i个元素起连续k个元素方法；实现在SL中从第2个元素开始的连续3个元素，输出SL的值。

程序代码：

    def duang(self,pos,item):
    j=0
    while j<item:
        self.shanchu(self.tzzs(pos))
        j+=1

SL.duang(2,3)
SL.bianli()

程序输出：

278911

本次实验的全部代码：

class Node:
    def __init__(self,item):
        self.item=item
        self.next=None
class tz:
    def __init__(self):
        self.__head=None
    def is_empty(self):
        return self.__head==None
    def toubu(self,item):
        node=Node(item)
        node.next=self.__head
        self.__head=node
    def changdu(self):
        cur =self.__head
        count=0
        while cur!=None:
            count+=1
            cur=cur.next
        return count
    def bianli(self):
        a=self.__head
        while a:
            print(a.item,end=' ')
            a=a.next
        print('')
    def weibu(self,item):
        node=Node(item)
        if self.is_empty():
            self.__head=node
        else:
            b=self.__head
            while b.next!=None:
                b=b.next
            b.next=node
    def renyi(self,pos,item):
        if pos<=0:
            self.toubu(item)
        elif pos>self.changdu()-1:
            self.weibu(item)
        else:
            per=self.__head
            count=0
            while count<pos-1:
                count+=1
                per=per.next
            node=Node(item)
            node.next=per.next
            per.next=node
    def shanchu(self,item):
        cur=self.__head
        pre=None
        while cur!=None:
            if cur.item==item:
                if cur==self.__head:
                    self.__head=cur.next
                else:
                    pre.next=cur.next
                break
            else:
                pre=cur
                cur=cur.next
    def weizhi(self,item):
        tt=self.__head
        i=1
        while tt != None:
            if tt.item != item:
                i=i+1
                tt=tt.next
            else:
                return i
    def chazhao(self,item):
        cur = self.__head
        while cur != None:
            if cur.item == item:
                print("Ture,该节点在链表中的位置为：",end='')
                return self.weizhi(item)
            else:
                cur = cur.next
        return False
    def tzzs(self,item):
        cur= self.__head
        i=1
        while cur!= None:
            if i!=item:
                i+=1
                cur=cur.next
            else:
                return cur.item
    def xiaozhen(self,item):
        node=Node(item)
        if self.is_empty():
            self.__head=node
        else:
            cur=self.__head
            i=0
            while cur!=None:
                if cur.item<item:
                    i+=1
                    cur=cur.next
                else:
                    return self.renyi(i,item)
    def duang(self,pos,item):
        j=0
        while j<item:
            self.shanchu(self.tzzs(pos))
            j+=1

if __name__=="__main__":
    SL=tz()
    print(SL.is_empty())
    SL.toubu(4)
    SL.toubu(3)
    SL.toubu(2)
    SL.toubu(1)
    print(SL.changdu())
    SL.weibu(5)
    SL.weibu(7)
    SL.weibu(9)
    SL.weibu(11)
    SL.weibu(13)
    SL.bianli()
    print(SL.changdu())
    SL.renyi(5,6)
    SL.bianli()
    print(SL.changdu())
    SL.shanchu(1)
    SL.bianli()
    SL.shanchu(13)
    SL.bianli()
    SL.shanchu(6)
    SL.bianli()
    print(SL.changdu())
    print(SL.chazhao(9))
    print(SL.chazhao(15))
    print(SL.tzzs(5))
    SL.xiaozhen(8)
    SL.bianli()
    SL.duang(2,3)
    SL.bianli()

输出结果：

True

4

1 2 3 4 5 7 9 11 13

9

1 2 3 4 5 6 7 9 11 13

10

2 3 4 5 6 7 9 11 13

2 3 4 5 6 7 9 11

2 3 4 5 7 9 11

7

Ture,该节点在链表中的位置为：6

False

7

2 3 4 5 7 8 9 11

2 7 8 9 11

线性表和顺序链表的关系 灵活运用了线性表中的概念包括头插法尾插法和游标删除等还要考虑在一个线性表中的特殊情况例如在insert插入时的cur.next和cur.next+1之间的关系及 包括 索引从0开始的pos在remove中

判断当前节点是不是头节点及怎么判断头节点的方法 if cur.next == self.__head

等 在查找的def中查找节点是否存在就要对应一个特殊情况  链表是否为空链表  查找链表是否存在及遍历链表比对数据 查看节点是否存在  并理解了什么叫后继节点在开始设置构造方法进行赋值 如果不知道一个地址则可以设置成功 用cur游标移动遍历元素 遍历每个节点所以  count=0  用count来记录数量