网站 色彩,2345网址导航,外包网络安全技术措施,互联网编程数组
数组在分配内存的时候需要先告诉系统它有多大#xff0c;为什么呢#xff1f;打个比方#xff0c;我们有以一列的凳子#xff0c;按顺序排布#xff0c;一个位置只放一个#xff0c;数组呢#xff0c;是一个家庭#xff0c;数组这个家庭呢#xff0c;他们得挨着…数组
数组在分配内存的时候需要先告诉系统它有多大为什么呢打个比方我们有以一列的凳子按顺序排布一个位置只放一个数组呢是一个家庭数组这个家庭呢他们得挨着坐不能分开。如果说只有一个家庭来的时候他们想坐哪就可以坐哪但是呢倘若在他们来之前就有很多个家庭那他们就不一定能挨着坐了他们得先告诉管理员他们有几个人管理员才能按照他们的人数多少来给他们分配相应的位置。
链表
同样是坐凳子这一个例子但列表和数组这个家庭呢不太一样他们呢不需要都挨着坐他们每个人有空位就坐下了。那假如妈妈想要找到她的孩子又该怎么办呢机智的妈妈想出了一个好点子那就是让前一个人记住下一个坐的位置下一个人再记住下下一个人的位置通过位置去找寻他们。因此链表里头每个数据都由两部份组成分别是自己本身所携带的信息和下一个人的位置最后一个数据因为没有下一个了所以它所携带的位置一般为null。
数组VS链表
访问各个元素的成本 对于数组而言我们拿到它的位置接着按顺序遍历一遍就可以访问到每一个元素了因此它的时间复杂度是O1对于链表来说我们通过拿到它第一个位置按照地址去遍历一遍假设一共有n个元素那它的时间复杂度为On
内存的使用 对于数组来说我们想要创建一个大的数组那我们就得用一块更大的内存空间来承载。假设数组里面的一个数据的大小是4个字节一共有4个数据我们的内存空间为7个数据这就占据了28个字节。还有一种情形就是内存空间已经填满了可是数组又想去扩大那我们只能够创建一块更大的数据空间。 对于链表而言我们不存在什么多余的空间但每一个数据都要包含一个4字节的地址和一个不知道多少字节的内容。所占内存的大小就是数据量再乘上内容所需的字节与储存地址所需的字节之和。数组和链表两者之间其实并不存在哪一个所占内存大哪一个小这主要取决于数据量的多少数组所需内存的字节数内容所要的字节数我们进行相应的计算后比对。我们需要根据相应的情形对其进行分析。
插入数据的成本
在开头处进行插入 数组开头插入数据就意味着现有的数据每一个都得后移一个位因此它的时间复杂度为O(n) 链表开头插入的话我们就只需要在最前面添加内容并储存此前第一个数据的位置。
在结尾处插入 数组我们讨论的是动态数组如果还没填满的话时间复杂度就是O(1),如果已经填满了那我们就需要遍历全部数据再在最后的位置添加此时的时间复杂度是O(N) 链表我们需要遍历一遍数据再在最后添加一个数据因此此时的时间复杂度就是O(n)
在中间处插入 无论是数组还是链表我们都得去遍历到这个数据前面的每一项因此他们的时间复杂度都为O(n)
简易性 在编程语言中数组的实现会更为简单而链表的实现则为比较容易出错和复杂
代码
//创建链表
#define _CRT_SECURE_NO_WARNINGS
#includestdlib.h
#includestdio.h
//定义节点节点内包含数据和指向下一个数据的地址
struct Node {int data;struct Node* next;//指针
};
//建一个头有了头就能找到其他的数据
struct Node* head;//全局变量
void insert(int x) {struct Node* temp (struct Node*)malloc(sizeof(struct Node)); temp-data x;temp-next NULL;if (head ! NULL)temp-next head;head temp;
}
void print() {struct Node* temp head;printf(List is:);while (temp ! NULL){printf(%d, temp-data);temp temp-next;}printf(\n);
}
int main() {head NULL; //空链表//做一个交互知道要填几个数据 printf(How many numbers do yop want to input\n);//拿一个变量n来接住这个填充数int n;//填入数据scanf(%d, n);int x;for(int i 0; i n; i) {printf(please input the number\n);scanf(%d, x);insert(x);print();}}
在ds中给出的示例代码为
#ifndef LIST_H
#define LIST_H#include algorithm
using namespace std;template typename Object
class List
{private: // The basic doubly linked list node.// Nested inside of List, can be public// because the Node is itself privatestruct Node{Object data;Node *prev;Node *next;Node( const Object d Object{ }, Node * p nullptr, Node * n nullptr ): data{ d }, prev{ p }, next{ n } { }Node( Object d, Node * p nullptr, Node * n nullptr ): data{ std::move( d ) }, prev{ p }, next{ n } { }};public:class const_iterator{public:// Public constructor for const_iterator.const_iterator( ) : current{ nullptr }{ }// Return the object stored at the current position.// For const_iterator, this is an accessor with a// const reference return type.const Object operator* ( ) const{ return retrieve( ); }const_iterator operator ( ){current current-next;return *this;}const_iterator operator ( int ){const_iterator old *this;( *this );return old;}const_iterator operator-- ( ){current current-prev;return *this;}const_iterator operator-- ( int ){const_iterator old *this;--( *this );return old;}bool operator ( const const_iterator rhs ) const{ return current rhs.current; }bool operator! ( const const_iterator rhs ) const{ return !( *this rhs ); }protected:Node *current;// Protected helper in const_iterator that returns the object// stored at the current position. Can be called by all// three versions of operator* without any type conversions.Object retrieve( ) const{ return current-data; }// Protected constructor for const_iterator.// Expects a pointer that represents the current position.const_iterator( Node *p ) : current{ p }{ }friend class ListObject;};class iterator : public const_iterator{public:// Public constructor for iterator.// Calls the base-class constructor.// Must be provided because the private constructor// is written; otherwise zero-parameter constructor// would be disabled.iterator( ){ }Object operator* ( ){ return const_iterator::retrieve( ); }// Return the object stored at the current position.// For iterator, there is an accessor with a// const reference return type and a mutator with// a reference return type. The accessor is shown first.const Object operator* ( ) const{ return const_iterator::operator*( ); }iterator operator ( ){this-current this-current-next;return *this;}iterator operator ( int ){iterator old *this;( *this );return old;}iterator operator-- ( ){this-current this-current-prev;return *this;}iterator operator-- ( int ){iterator old *this;--( *this );return old;}protected:// Protected constructor for iterator.// Expects the current position.iterator( Node *p ) : const_iterator{ p }{ }friend class ListObject;};public:List( ){ init( ); }~List( ){clear( );delete head;delete tail;}List( const List rhs ){init( );for( auto x : rhs )push_back( x );}List operator ( const List rhs ){List copy rhs;std::swap( *this, copy );return *this;}List( List rhs ): theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }{rhs.theSize 0;rhs.head nullptr;rhs.tail nullptr;}List operator ( List rhs ){ std::swap( theSize, rhs.theSize );std::swap( head, rhs.head );std::swap( tail, rhs.tail );return *this;}// Return iterator representing beginning of list.// Mutator version is first, then accessor version.iterator begin( ){ return iterator( head-next ); }const_iterator begin( ) const{ return const_iterator( head-next ); }// Return iterator representing endmarker of list.// Mutator version is first, then accessor version.iterator end( ){ return iterator( tail ); }const_iterator end( ) const{ return const_iterator( tail ); }// Return number of elements currently in the list.int size( ) const{ return theSize; }// Return true if the list is empty, false otherwise.bool empty( ) const{ return size( ) 0; }void clear( ){while( !empty( ) )pop_front( );}// front, back, push_front, push_back, pop_front, and pop_back// are the basic double-ended queue operations.Object front( ){ return *begin( ); }const Object front( ) const{ return *begin( ); }Object back( ){ return *--end( ); }const Object back( ) const{ return *--end( ); }void push_front( const Object x ){ insert( begin( ), x ); }void push_back( const Object x ){ insert( end( ), x ); }void push_front( Object x ){ insert( begin( ), std::move( x ) ); }void push_back( Object x ){ insert( end( ), std::move( x ) ); }void pop_front( ){ erase( begin( ) ); }void pop_back( ){ erase( --end( ) ); }// Insert x before itr.iterator insert( iterator itr, const Object x ){Node *p itr.current;theSize;return iterator( p-prev p-prev-next new Node{ x, p-prev, p } );}// Insert x before itr.iterator insert( iterator itr, Object x ){Node *p itr.current;theSize;return iterator( p-prev p-prev-next new Node{ std::move( x ), p-prev, p } );}// Erase item at itr.iterator erase( iterator itr ){Node *p itr.current;iterator retVal( p-next );p-prev-next p-next;p-next-prev p-prev;delete p;--theSize;return retVal;}iterator erase( iterator from, iterator to ){for( iterator itr from; itr ! to; )itr erase( itr );return to;}private:int theSize;Node *head;Node *tail;void init( ){theSize 0;head new Node;tail new Node;head-next tail;tail-prev head;}
};#endif
