存储结构比较项目 | 顺序表 | 链表 |
---|---|---|
存储空间 | 预先分配,会导致空间闲置或溢出现象 | 动态分配,不会出现存储空间闲置或溢出现象 |
存储密度 | 不用为表示结点间的逻辑关系而增加额外的存储开销,存储密度等于1 | 需要借助指针来体现元素间的逻辑关系,存储密度小于1 |
存取元素 | 随机存取,按位置访问元素的时间复杂度为O(1) | 顺序存取,按位置访问元素时间复杂度为O(n) |
插入、删除 | 平均移动约表中一半元素,时间复杂度为O(n) | 不需移动元素,确定插入、删除位置后,时间复杂度为O(1) |
适用情况 | ① 表长变化不大,且能事先确定变化的范围 ② 很少进行插入或删除操作,经常按元素位置序号访问数据元素 | ① 长度变化较大 ② 频繁进行插入或删除操作 |
#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
#!/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]
```python
#!/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]
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]
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。