1
数据结构——链表
发布于: 2 小时前
链式存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
有关术语
结点：数据元素的存储映像。由数据域和指针域两部分组成
数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置
链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
单链表
结点只有一个指针域的链表，称为单链表或线性链表
双链表
有两个指针域的链表，称为双链表
循环链表
首尾相接的链表称为循环链表
头指针
指向链表中第一个结点的指针
首元结点
指链表中存储第一个数据元素 a1 的结点
头结点
在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
设置头结点的好处
便于首元结点的处理
首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
链表的特点
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等
链表的优缺点
优点
数据元素的个数可以自由扩充
插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点
存储密度小
存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）
顺序表和链表的比较
C++代码实现
#include<iostream>#include<stdlib.h>using namespace std;
#define OVERFLOW -2#define OK 1#define ERROR -1
typedef int Status;typedef int Elemtype;
/* typedef struct LNode{ Elemtype data; struct LNode *next;}LNode;
typedef struct{ lnode *l;}LinkList; */
typedef struct LNode { Elemtype data; struct LNode* next;}LNode, * LinkList;
// 构造一个空的单链表Status InitList(LinkList& L){ L = new LNode; // 头指针L指向头结点 if (!L) exit(OVERFLOW); L->next = NULL; // 指针域置空 return OK;}
// 前插法创建单链表void CreateList_H(LinkList& L, int n){ LinkList p; int i; L = new LNode; L->next = NULL; // 先建立一个带头结点的空链表 // for(i = 0; i < n; ++i) for (i = 1; i < n + 1; ++i) { cout << "请输入第" << i << "个结点的数据" << endl; p = new LNode; // 生成新结点*p cin >> p->data; // 输入元素赋值给新结点*p的数据域 p->next = L->next; L->next = p; // 将新结点*p插入到头结点之后 }}
// 尾插法创建单链表Status CreateList_L(LinkList& L, int n){ LinkList r, p; int i; L = new LNode; L->next = NULL; // 尾结点指向头结点 r = L; for (i = 1; i < n + 1; ++i) { cout << "请输入第" << i << "个结点的数据" << endl; p = new LNode; // 生成新结点 cin >> p->data; p->next = NULL; r->next = p; r = p; } return OK;}
// 取值Status GetElem(LinkList L, int i, Elemtype& e){ // 根据序号i获取元素的值，用e返回值 int j; LinkList p; for (p = L->next, j = 1; j < i && p; j++) p = p->next; if (!p || j > i) return ERROR; e = p->data; return OK;}
// 在链表中查找值为e的元素的位置，返回其地址LinkList LocateElem_L(LinkList L, Elemtype e){ LinkList p; p = L->next; while (p && p->data != e) { p = p->next; } return p;}
// 插入Status ListInsert(LinkList& L, int i, Elemtype& e){ LinkList p, s; int j; for (p = L, j = 0;j < i - 1 && p; j++) p = p->next; if (!p || j > i) return ERROR; s = new LNode; s->data = e; s->next = p->next; p->next = s; return OK;}
// 删除Status ListDelete(LinkList& L, int i, Elemtype& e){ LinkList p, q; int j; for (p = L, j = 0;j < i - 1 && p; j++) p = p->next; if (!p || j > i) return ERROR; q = p->next; p->next = q->next; e = q->data; delete q; return OK;}
// 销毁Status DestroyList(LinkList& L){ LinkList p; while (L) { p = L; L = L->next; delete p; } return OK;}
// 清空Status ClearList(LinkList& L){ LinkList p, q; p = L->next; // p指向第一个结点 while (p) // 没到表尾 { q = p->next; delete p; p = q; } L->next = NULL; // 头结点指针域为空 return OK;}
// 求表长int ListLength_L(LinkList L){ // 返回L中数据元素的个数 int i; LinkList p; p = L->next; // p指向第一个结点 i = 0; while (p) // 遍历单链表，统计结点数 { i++; p = p->next; } return i;}
// 判断表是否为空int ListEmpty(LinkList L) { // 若L为空，返回1；否则，返回0 if (L->next) return 0; else return 1;}
int main(){ LinkList L; Elemtype e; int i, n;
// 创建链表测试 cout << "请输入表长："; cin >> n; // 尾插法创建 CreateList_L(L, n);
cout << "表长为："; cout << ListLength_L(L) << endl;
// 查找测试 cout << "请输入您需要查找元素的位置："; cin >> i; GetElem(L, i, e); cout << e;
// 删除测试 cout << "请输入您要删除的元素的位置："; cin >> i; ListDelete(L, i, e); cout << e;
return 0;}
复制代码
Python 代码实现
SingleNode
#!/usr/bin/env python # -*- coding: utf-8 -*- # @Date : 2019-10-02 09:32:38 # @Author : Your Name (you@example.org) # @Link : http://example.org # @Version : $Id$ class SingleNode(object): def __init__(self, item): self.item = item self.next = None class SingleLinkList(object): def __init__(self): self._head = None def isEmpty(self): return self._head == None def length(self): cur = self._head count = 0 while cur: count += 1 cur = cur.next return count def travel(self): cur = self._head while cur: print(cur.item, end=" ") cur = cur.next print() return None def addFirst(self, item): node = SingleNode(item) node.next = self._head self._head = node def append(self, item): node = SingleNode(item) if self.isEmpty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = node def insert(self, pos, item): if pos <= 0: self.addFirst(item) elif pos > (self.length() - 1): self.append(item) else: node = SingleNode(item) count = 0 pre = self._head # 数据从0开始 # 从1开始 应该为 pos - 2 while count < (pos - 1): count += 1 pre = pre.next node.next = pre.next pre.next = node def remove(self, item): cur = self._head pre = None while cur: if cur.item == item: if not pre: self._head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next def search(self, item): cur = self._head while cur: if cur.item == item: return True cur = cur.next return False if __name__ == '__main__': sll = SingleLinkList() sll.addFirst(10) sll.addFirst(20) sll.append(30) sll.travel() sll.remove(10) sll.travel() print(sll.search(30)) print(sll.search(10)) sll.insert(2, 40) sll.travel() print(sll.length()) print(sll.isEmpty()) sll.insert(2, 50) sll.travel()
复制代码
20 10 30 20 30 True False 20 30 40 3 False 20 30 50 40 [Finished in 0.6s]
复制代码
SingleCycLinkedList
#!/usr/bin/env python # -*- coding: utf-8 -*- # @Date : 2019-10-02 11:13:14 # @Author : Your Name (you@example.org) # @Link : http://example.org # @Version : $Id$ class SingleNode(object): def __init__(self, item): self.item = item self._head = None class SingleCysLinkedList(object): def __init__(self): self._head = None def is_empty(self): return self._head == None def length(self): if self.is_empty(): return 0 count = 1 cur = self._head while cur.next != self._head: count += 1 cur = cur.next return count def travel(self): if self.is_empty(): return cur = self._head print(cur.item, end=" ") while cur.next != self._head: cur = cur.next print(cur.item, end=" ") print() def addFirst(self, item): node = SingleNode(item) if self.is_empty(): self._head = node node.next = self._head else: node.next = self._head cur = self._head while cur.next != self._head: cur = cur.next cur.next = node self._head = node def append(self, item): node = SingleNode(item) if self.is_empty(): self._head = node node.next = self._head else: node.next = self._head cur = self._head while cur.next != self._head: cur = cur.next cur.next = node node.next = self._head def insert(self, pos, item): if pos<= 0: self.addFirst(item) elif pos > (self.length() - 1): self.append(item) else: node = SingleNode(item) cur = self._head count = 0 while count < (pos - 1): count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self, item): if self.is_empty(): return cur = self._head pre = None if cur.item == item: # 删除第一个元素 if cur.next != self._head: while cur.next != self._head: cur = cur.next cur.next = self._head.next self._head = self._head.next else: # 只有一个元素 self._head = None else: pre = self._head while cur.next != self._head: if cur.item == item: pre.next = cur.next return else: pre = cur cur = cur.next if cur.item == item: pre.next = cur.next def search(self, item): if self.is_empty(): return False cur = self._head if cur.item == item: return True while cur.next != self._head: cur = cur.next if cur.item == item: return True return False if __name__ == '__main__': ll = SingleCysLinkedList() ll.addFirst(1) ll.addFirst(2) ll.append(3) ll.insert(2, 4) ll.insert(4, 5) ll.insert(0, 6) print("length: {0}".format(ll.length())) ll.travel() print(ll.search(3)) print(ll.search(7)) ll.remove(1) print("length:", ll.length()) ll.travel()
复制代码
length: 6 6 2 1 4 3 5 True False length: 5 6 2 4 3 5 [Finished in 0.4s]
复制代码
DLinkList
#!/usr/bin/env python # -*- coding: utf-8 -*- # @Date : 2019-10-02 12:10:18 # @Author : Your Name (you@example.org) # @Link : http://example.org # @Version : $Id$ class Node(object): def __init__(self, item): self.item = item self.next = None self.prev = None class DLinkList(object): def __init__(self): self._head = None def is_empty(self): return self._head == None def length(self): cur = self._head count = 0 while cur: count += 1 cur = cur.next return count def travel(self): cur = self._head while cur: print(cur.item, end=" ") cur = cur.next print() def add(self, item): node = Node(item) if self.is_empty(): self._head = node else: node.next = self._head self._head.prev = node self._head = node def append(self, item): node = Node(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = node node.prev = cur def search(self, item): cur = self._head while cur: if cur.item == item: return True cur = cur.next return False def insert(self, pos, item): if pos <= 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: node = Node(item) cur = self._head count = 0 # 移动到指定位置的前一个位置 while count < (pos - 1): count += 1 cur = cur.next # 将node的prev指向cur node.prev = cur # 将node的next指向cur的下一个结点 node.next = cur.next # 将cur的下一个结点的prev指向node cur.next.prev = node # 将cur的next指向node cur.next = node def remove(self, item): if self.is_empty(): return else: cur = self._head if cur.item == item: if cur.next == None: self._head = None else: cur.next.prev = None self._head = cur.next return while cur: if cur.item == itme: cur.prev.next = cur.next cur.next.prev = cur.prev break cur = cur.next if __name__ == '__main__': ll = DLinkList() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) ll.insert(4, 5) ll.insert(0, 6) print("length:", ll.length()) ll.travel() print(ll.search(3)) print(ll.search(4)) ll.remove(1) print("length: {}".format(ll.length())) ll.travel()
复制代码
length: 6 6 2 1 4 3 5 True True length: 5 2 1 4 3 5 [Finished in 0.1s]
复制代码
划线
评论
复制
发布于: 2 小时前阅读数: 2
版权声明: 本文为 InfoQ 作者【若尘】的原创文章。
原文链接:【http://xie.infoq.cn/article/6c73bdcdf194db25d4707cb79】。文章转载请联系作者。
若尘
关注
还未添加个人签名 2021.01.11 加入
还未添加个人简介
评论