1 class item (object):
  2     def __init__(self, data):
  3         self.data = data
  4         self.next = None
  5 
  6 class SLinkList(object):
  7     '''
  8     静态链表，就是用数组来模拟链表，那么数组的下标就当做是节点的地址，
  9     这个概念是静态链表的核心
 10     '''
 11     def __init__(self, size = 100):
 12         '''
 13         初始化主要是用于初始化链表的大小，而非创建链表
 14         '''
 15         self.link = [item(None) for i in range(size + 1)]    # 申请 size 大小的节点空间 [0,1,2,...,size]，其中下标 0 的节点作为头结点
 16         self.link[0].next = None    # 表示空表
 17         self.link[0].space = 1   # 指向第一个节点，因为初始化时第一个节点为空闲节点
 18 
 19         i = 1
 20         while i < size:
 21             self.link[i].next = i+1    # 利用空闲节点连成一个新的表，并且头结点的 space 始终指向下一个空闲的节点
 22             i += 1
 23 
 24         self.link[i].next = None    # 空闲表尾指向 None
 25 
 26         self.length = 0    # 链表长度
 27         self.rear = 0    # 表尾指针
 28 
 29     def CreateSLinkList_R(self, data):
 30         '''
 31         用尾插法创建链表
 32         '''
 33         if self.length > 0:     # 非空表无需创建
 34             print("THIS SLINKLIST IS NOT NULL")
 35             return
 36             
 37         for each in data:
 38            if not self.Append(each):
 39                print("CreateR: NO SPACE!")
 40                return
 41 
 42 
 43     def CreateSLinkList_F(self, data):
 44         '''
 45         用头插法创建链表
 46         '''
 47         if self.length > 0:     # 非空表无需创建
 48             print("THIS SLINKLIST IS NOT NULL")
 49             return
 50 
 51         self.Append(data[0])    # 先添加第一个节点
 52         for each in data[1:]:    # 在第一个位置前插入
 53             if self.InsertBefore(each, 1) == 'NS':
 54                 print("CreateF: NO SPACE!")
 55 
 56 
 57     def LocateElement(self, data):
 58         '''
 59         定位第一个与 data 值相同的节点，并返回该节点的下标
 60         '''
 61         i = self.link[0].next
 62         while i and self.link[i] != data:
 63             i = self.link[i].next
 64         return i
 65 
 66     def Malloc_SL(self):
 67         '''
 68         类似于 C 中 malloc 函数申请空间，返回空闲节点的下标
 69         '''
 70         i = self.link[0].space
 71         if self.link[0].space:
 72             self.link[0].space = self.link[i].next
 73 
 74         return i
 75 
 76     def Free_SL(self, k):
 77         '''
 78         释放空间，并返回下标 k 节点的值
 79         '''
 80         self.link[k].data = None
 81         self.link[k].next = self.link[0].space
 82         self.link[0].space = k
 83 
 84     def DeleteElement(self, data):
 85         '''
 86         删除第一个匹配到的节点，并返回删除节点的下标
 87         '''
 88         prior = index = 0
 89         while index != None and self.link[index].data != data:
 90             prior = index
 91             index = self.link[index].next
 92 
 93         if not index:
 94             print("DELETE:\tNot Found!")
 95             return False
 96 
 97         if not self.link[index].next:    # 判断是否是删除表尾元素，是则改变表尾指针
 98             self.rear = prior
 99 
100         self.link[prior].next = self.link[index].next
101         self.length -= 1
102         self.Free_SL(index)
103         return index
104 
105     def InsertBefore(self, data, k):
106         '''
107         在第 k 个元素前插入元素, 并返回新节点下标
108         '''
109         if self.link[0].space == None:    # 表满
110             print("no space!!!")
111             return "NS"
112 
113         if k <= 0 or k > self.length:  # 超出当前链表可插入范围
114             print("out of range!!!")
115             return "OFR"
116 
117         count = 0
118         index = 0
119         while count < k - 1 :    # 找到第 k-1 个节点，直接在改节点后插入新的元素 
120             index = self.link[index].next
121             count += 1
122 
123         node_index = self.Malloc_SL()    # 申请一个新的节点
124         self.link[node_index].data = data    # 写入数据
125         self.link[node_index].next = self.link[index].next    # 将新节点的 next 指向第 k 个节点
126         self.link[index].next = node_index    # 将第 k-1 个节点的 next 指向新节点 node_index
127         self.length += 1
128         return node_index
129 
130     def Append(self, data):
131         '''往链表表尾添加元素, 并返回新添加元素的下标'''
132         node_index = self.Malloc_SL()
133 
134         if not node_index:
135             print("Append: NO SPACE!")
136             return False
137         
138         self.link[node_index].data = data
139         self.link[node_index].next = None
140         self.link[self.rear].next = node_index
141         self.rear = node_index
142         self.length += 1
143         return node_index
144 
145     def Walk(self):
146         '''打印链表中所有元素'''
147         print("WALK:\t", end = '')
148         index = self.link[0].next
149         while index:
150             print(self.link[index].data, end = '')
151             index = self.link[index].next
152         print("")
153 
154     def Detail(self):
155         '''输出链表中各元素的详细信息'''
156         print("\nDETAIL:")
157         index = self.link[0].next
158         count = 1
159         while index:
160             print("SN:\t%d\tDATA:\t%s\tADDR:\t%d\tNEXT:\t%s" % \
161                 (count, self.link[index].data, index, str(self.link[index].next)))
162             index = self.link[index].next
163             count += 1
164 
165         print("Length:\t%d\nRear:\t%d\n" % (self.length, self.rear))
166 
167 
168 if __name__ == '__main__':
169     SL = SLinkList()
170     while True:
171         print()
172         opt = input("请选择创建链表的方式： 1. 尾插法 2. 头插法 \nOPTION:\t")
173         if opt == '1':
174             data_str = input("INPUT DATA:\t")
175             SL.CreateSLinkList_R(data_str)
176             break
177         elif opt == '2':
178             data_str = input("INPUT DATA:\t")
179             SL.CreateSLinkList_F(data_str)
180             break
181         else:
182             print("请做出正确选择！")
183             continue
184 
185     while True:
186         opt = input("\n 请选择操作： 1. 插入数据 2. 删除数据 3. 遍历链表 4. 查看链表详细结构 5. 在链表末尾添加数据 6. 退出程序 \nOPTION:\t")
187         if opt == '1':
188             data_str = input("请输入插入数据：\t")
189             pos = input("请输入插入位置：\t")
190             node_addr = SL.InsertBefore(data_str[0], int(pos))
191             if node_addr != 'NS' and node_addr != 'OFR':
192                 print("成功删除元素 %s，元素地址为：%d" % (data_str[0], node_addr))
193             else:
194                 print("INSERT ERROR!!!")
195 
196         elif opt == '2':
197             data_str = input("请输入删除数据：\t")
198             data_pos = SL.DeleteElement(data_str[0])
199             if data_pos:
200                 print("成功删除元素 %s，元素地址为：%d" % (data_str[0],data_pos))
201 
202         elif opt == '3':
203             print('')
204             SL.Walk()
205         elif opt == '4':
206             SL.Detail()
207         elif opt == '5':
208             data_str = input("请输入数据:\t")
209             node_addr = SL.Append(data_str[0])
210             print("成功添加元素：\t%s\t 元素地址为：\t%d" % (data_str[0], node_addr))
211         elif opt == '6':
212             break
213         else:
214             print("请做出正确选择！")

  1 # -*- coding:utf8 -*-
  2 #/usr/bin/env python
  3 
  4 class Node(object):
  5     def __init__(self, data, pnext = None):
  6         self.data = data
  7         self._next = pnext
  8 
  9     def __repr__(self):
 10         return str(self.data)
 11 
 12 class ChainTable(object):
 13     def __init__(self):
 14         self.head = None
 15         self.length = 0
 16 
 17     def isEmpty(self):
 18         return (self.length == 0)
 19 
 20     def append(self, dataOrNode):
 21         item = None
 22         if isinstance(dataOrNode, Node):
 23             item = dataOrNode
 24         else:
 25             item = Node(dataOrNode)
 26 
 27         if not self.head:
 28             self.head = item
 29             self.length += 1
 30 
 31         else:
 32             node = self.head
 33             while node._next:
 34                 node = node._next
 35             node._next = item
 36             self.length += 1
 37 
 38     def delete(self, index):
 39         if self.isEmpty():
 40             print "this chain table is empty."
 41             return
 42 
 43         if index < 0 or index >= self.length:
 44             print 'error: out of index'
 45             return
 46 
 47         if index == 0:
 48             self.head = self.head._next
 49             self.length -= 1
 50             return
 51 
 52         j = 0
 53         node = self.head
 54         prev = self.head
 55         while node._next and j < index:
 56             prev = node
 57             node = node._next
 58             j += 1
 59 
 60         if j == index:
 61             prev._next = node._next
 62             self.length -= 1
 63 
 64     def insert(self, index, dataOrNode):
 65         if self.isEmpty():
 66             print "this chain tabale is empty"
 67             return
 68 
 69         if index < 0 or index >= self.length:
 70             print "error: out of index"
 71             return
 72 
 73         item = None
 74         if isinstance(dataOrNode, Node):
 75             item = dataOrNode
 76         else:
 77             item = Node(dataOrNode)
 78 
 79         if index == 0:
 80             item._next = self.head
 81             self.head = item
 82             self.length += 1
 83             return
 84 
 85         j = 0
 86         node = self.head
 87         prev = self.head
 88         while node._next and j < index:
 89             prev = node
 90             node = node._next
 91             j += 1
 92 
 93         if j == index:
 94             item._next = node
 95             prev._next = item
 96             self.length += 1
 97 
 98     def update(self, index, data):
 99         if self.isEmpty() or index < 0 or index >= self.length:
100             print 'error: out of index'
101             return
102         j = 0
103         node = self.head
104         while node._next and j < index:
105             node = node._next
106             j += 1
107 
108         if j == index:
109             node.data = data
110 
111     def getItem(self, index):
112         if self.isEmpty() or index < 0 or index >= self.length:
113             print "error: out of index"
114             return
115         j = 0
116         node = self.head
117         while node._next and j < index:
118             node = node._next
119             j += 1
120 
121         return node.data
122 
123 
124     def getIndex(self, data):
125         j = 0
126         if self.isEmpty():
127             print "this chain table is empty"
128             return
129         node = self.head
130         while node:
131             if node.data == data:
132                 return j
133             node = node._next
134             j += 1
135 
136         if j == self.length:
137             print "%s not found" % str(data)
138             return
139 
140     def clear(self):
141         self.head = None
142         self.length = 0
143 
144     def __repr__(self):
145         if self.isEmpty():
146             return "empty chain table"
147         node = self.head
148         nlist = ''
149         while node:
150             nlist += str(node.data) + ' '
151             node = node._next
152         return nlist
153 
154     def __getitem__(self, ind):
155         if self.isEmpty() or ind < 0 or ind >= self.length:
156             print "error: out of index"
157             return
158         return self.getItem(ind)
159 
160     def __setitem__(self, ind, val):
161         if self.isEmpty() or ind < 0 or ind >= self.length:
162             print "error: out of index"
163             return
164         self.update(ind, val)
165 
166     def __len__(self):
167         return self.length