描述:
顺序表和链表是数据结构的基础结构之一,同样也是面试的基础。初学者对于Seqlist和List的增删改查的基础练习,为其后的Tree,HashTable,Binary Linked List,Trigeminal linked list等数据结构打下坚实的基础。
C语言下的Seqlist:
- <span style="font-size:18px;">
▲顺序表有其限制性,对于静态的顺序表来说,其存储空间由一开始宏定义的Max_Size设置,而后不能再作变化,除非更改宏值。对于动态的顺序表,其增加了capacity容量的概念,可每次动态增长其size的值,可以参考点击进入此网站,不过cplusplus中的顺序表不再是Seqlist,而更名为Vector。
C++下的Seqlist:
- <span style="font-size:18px;">
- #include<iostream>
- using namespace std;
-
- SeqList::SeqList()
- :_array(NULL)
- , _size(0)
- , _capacity(0)
- {}
- //顺序表只考虑深拷贝
-
-
- //传统写法
- SeqList(const SeqList& s)
- :_array(new DataType[s._size])
- ,_size(s._size)
- ,_capacity(s._capacity)
- memcpy(_array, s._array, sizeof(DataType)*(_size));
- }
- SeqList& operator=(const SeqList& s)
- {
- if (this != &s)
- {
- DataType* tmp = new DataType[s._size];
- delete[] _array;
- _array = tmp;
- _size = s._size;
- _capacity = s._capacity;
- memcpy(_array, s._array, sizeof(DataType)*(_size));
- }
- return *this;
- }
-
-
- //现代写法
- SeqList::SeqList(DataType* array, const size_t size)
- :_array(new DataType[size])
- , _size(size)
- , _capacity(size)
- {
- memcpy(_array, array, sizeof(DataType)*size);
- }
- SeqList::SeqList(const SeqList& s)
- :_array(NULL)
- {
- SeqList tmp(s._array, s._size);
- swap(_array, tmp._array);
- _size = s._size;
- _capacity = s._size; //容量用_size,防止越界
- }
-
-
- SeqList& SeqList::operator=(SeqList& s)
- {
- if (this != &s)
- {
- swap(_array, s._array);
- _size = s._size;
- _capacity = s._capacity;
- }
- return *this;
- }
-
-
- SeqList::~SeqList()
- {
- if (_array)
- {
- delete[] _array;
- }
- }
-
-
-
- void SeqList::_CheckCapacity()//检查容量
- {
- if (_size >= _capacity)
- {
- _capacity = 2 * _capacity + 3;//_capacity是否为0
- _array = (DataType*)realloc(_array, _capacity*sizeof(DataType));//realloc扩容,后面用字节数表示
- }
- }
-
- void SeqList::PrintSepList()//打印顺序表
- {
- for (int i = 0; i < (int)_size; i++)
- {
- cout << _array[i] << "-";
- }
- cout << "NULL" << endl;
- }
-
-
-
- void SeqList::PushBack(DataType x)//尾插
- {
- _CheckCapacity();
- _array[_size++] = x;
- }
-
-
-
- void SeqList::PopBack()//尾删
- {
- if (_size > 0)
- {
- _array[_size--] = NULL;
- }
- else
- cout << "SeqList is empty" << endl;
- }
-
-
-
- void SeqList::PushFront(DataType x)////头插
- {
- _CheckCapacity();
- for (int i = (int)_size; i >0 ; i--)
- {
- _array[i] = _array[i - 1];
- }
- _array[0] = x;
- _size++;
- }
-
-
-
- void SeqList::PopFront()//头删
- {
- if (_size > 0)
- {
- _array[0] = NULL;
- for (int i = 0; i < (int)_size; i++)
- {
- _array[i] = _array[i + 1];
- }
- _size--;
- }
- else
- cout << "SeqList is empty" << endl;
- }
-
-
-
- void SeqList::Insert(size_t pos, DataType x)//指定位置处插入一个数
- {
- if (pos <= 0 || pos > _size + 1)
- {
- cout << "position is error!" << endl;
- }
- else if (pos == _size)
- SeqList::PushBack(x);
- else
- {
- for (int i = (int)(++_size); i > ((int)pos - 1); i--)
- {
- _array[i] = _array[i - 1];
- }
- _array[pos - 1] = x;
- }
- }
-
-
-
- void SeqList::Erase(size_t pos)//删除指定位置
- {
- if (pos <= 0 || pos > _size + 1)
- {
- cout << "position is error!" << endl;
- }
- else if (pos == _size)
- SeqList::PopBack();
- else
- {
- _array[pos - 1] = NULL;
- for (int i = pos - 1; i < (int)_size; i++)
- {
- _array[i] = _array[i + 1];
- }
- _size--;
- }
- }
-
-
- size_t SeqList::Find(DataType x)//查找某数
- {
- int i;
- for (i = 0; i < (int)_size; i++)
- {
- if (x == _array[i])
- return i + 1;
- }
- if (i == (int)_size)
- return 0;
- return -1;
- }</span>
▲注意:代码中并未给出struct/class结构体的定义,只是实现了结构体中每一个函数的定义,且是在类体外定义的(前有Seqlist::作用域符)。
C下的List:
▲对于单链表来说,节点的增删其头删/头插比尾删/尾插来的简单些,所以只实现了头插和头删操作。
C++下的List:
- <span style="font-size:18px;">
▲对于Sort排序算法,在此选择了最易实现和理解的冒泡排序,对于其它的排序(选排,插排,堆排,计数排,基数排,快排等),可自由选择合适的排序算法。
最后总结下顺序表&链表的异同:
★顺序表特点:逻辑上数据元素相邻,物理存储位置也相邻,并且存储空间需要预先分配。
优点:
(1)方法简单,各种高级语言中都有数组,容易实现。
(2)不用为表示节点间的逻辑关系而增加额外的存储开销。
(3)顺序表具有按元素序号随机访问的特点。
缺点:
(1)在顺序表中做插入、删除操作时,平均移动表中的一半元素,因此对n较大的顺序表效率低。
(2)需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。
★单链表特点:在链表中逻辑上相邻的数据元素,物理存储位置不一定相邻,它使用指针实现元素之间的逻辑关系。并且存储空间是动态分配的。
优点:
链表的最大特点是: 插入、删除运算方便。
缺点:
(1)要占用额外的存储空间存储元素之间的关系,存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单 元之比。
(2)链表不是一种随机存储结构,不能随机存取元素。
★两种结构的适用场景:
(1)顺序表的存储空间是静态分配的,在程序执行之前必须明确规定它的存储规模,也就是说事先对“Max_Size”要有合适的设定,设定过大会造成存储空间的浪费,过小造成溢出。因此,当对线性表的长度或存储规模难以估计时,不宜采用顺序表。
(2)链表的动态分配则可以克服这个缺点。链表不需要预留存储空间,也不需要知道表长如何变化,只要内存空间尚有空闲,就可以再程序运行时随时地动态分配空间,不需要时还可以动态回收。因此,当线性表的长度变化较大或者难以估计其存储规模时,宜采用动态链表作为存储结构。
(3)链表中除数据域外还需要在每个节点上附加指针。如果节点的数据占据的空间小,则链表的结构性开销就占去了整个存储空间的大部分。当顺序表被填满时,则没有结构开销。在这种情况下,顺序表的空间效率更高。由于设置指针域额外地开销了一定的存储空间,从存储密度的角度来讲,链表的存储密度小于1。因此,当线性表的长度变化不大而且事先容易确定其大小时,为节省存储空间,则采用顺序表作为存储结构比较适宜。
(4)基于运算的考虑(时间) :顺序存储是一种随机存取的结构,而链表则是一种顺序存取结构,因此它们对各种操作有完全不同的算法和时间复杂度。例如,要查找线性表中的第i个元素,对于顺序表可以直接计算出a(i)的的地址,不用去查找,其时间复杂度为0(1).而链表必须从链表头开始,依次向后查找,平均需要0(n)的时间。所以,如果经常做的运算是按序号访问数据元素,显然顺表优于链表。 反之,在顺序表中做插入,删除时平均移动表中一半的元素,当数据元素的信息量较大而且表比较长时,这一点是不应忽视的;在链表中作插入、删除,虽然要找插入位置,但操作是比较操作,从这个角度考虑显然后者优于前者。
(5)基于环境的考虑(语言)
顺序表容易实现,任何高级语言中都有数组类型;链表的操作是基于指针的。所以相较而言顺序表的适应范围更广一些,相对来讲前者简单些,也是用户考虑的一个因素。
▲ 总之,两种存储结构各有优劣,选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表,即主要操作是查找操作的线性表,适于选择顺序存储;而频繁做插入删除运算的(即动态性比较强)的线性表适宜选择链式存储。
|