运行效率：这里考虑 N
个元素的情况：平均而言，必须移动一半的元素才能腾出空间。假设在位置插入的可能性相同，最坏的情况是在位置
0 插入。必须在插入之前将所有 N 个项目移动一个位置，所以这是 O(N)
运行时间。最好的情况下是O(1)
以下是伪代码实现：
// insert element at the current position voidinsert(const E& it){ Assert(listSize>=maxSize, “Exceed capacity”); //shift Elements up for(int i=listSize; i>curr; i--) listArray[i] = listArray[i-1]; listArray[curr] = it; // insert the element listSize++; // increment list size }
// Remove and return the current element E remove(){ Assert((curr>=0)&&(curr<listSize), “no element); E it = listArray[curr]; // Copy the element for(int i=curr; i<listSize-1; i++) // Shift them down listArray[i] = listArray[i+1]; listSize--; // Decrement size return it; }
//Return true if K is in list, otherwise,false boolfind(List<int>& L, int K){ int it; for(L.moveToStart(); L.currPos()<L.Length(); L.next()) { it = getValue(); //return value of curr element if (K == it) returntrue; // Found it } returnfalse; // Not found }
在C++的STL库中提供了vector，可以动态扩容。
链表实现
特征
使用动态内存分配，根据需要为新列表元素分配内存。
元素称为节点，它们使用指针链接。
通过将节点链接在一起来跟踪列表。
当您想要插入或删除时更改链接。
节点实现
// An implementation of a simple // singly-linked list node template <typename E> classLink { public: E element; //value for this node Link *next; //Pointer to next node in list //Constructors Link(const E& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } };
关键变量
头指针head – 用于扫描整个列表
尾指针rear – 加速“追加”操作
Curr 指针 – 指向当前元素
cnt – 存储列表的长度
//Class LList //inherit the abstract class List template <typename E> classLList: public List<E>{ private: Link<E>* head; //Pointer to list header Link<E>* tail; //Pointer to last element Link<E>* curr; //access to current element int cnt; //Size of list voidinit()//used by constructor { curr = tail = head = new Link<E>; cnt =0; } voidremoveall()//used by deconstructor { while(head != NULL) { curr=head; head=head->next; delete curr; } } }
操作
插入
创建一个新的链表节点，存储新元素
设置新节点的下一个字段
设置 curr 指向的节点的下一个字段
//Insert a node to current position public: voidinsert(const E& it){ curr->next = newLink<E>(it, curr->next); //先创建新节点指向12，再将cur的下一个元素指向新节点 if (tail == curr) tail = curr->next; //new tail //如果是在尾部插入，那么需要更新tail cnt++; }
//Append a node at the tail of the list voidappend(const E& it){ tail = tail->next = newLink<E>(it, NULL); cnt++; }
删除
删除节点只需要重定向要删除的节点周围的一些指针即可。
记得回收被删除节点占用的空间
// Remove and return current element E remove(){ E it = curr->next->element; Link<E> *ltemp = curr->next; if (tail == curr->next) //删除的恰好是尾部元素 tail =curr; // Reset tail curr->next = curr->next->next; //remove element delete ltemp; //reclaim space cnt--; //decrement the list size return it; }
后继
//Next – move curr one pos toward the tail voidnext(){ // no change if already at end if (curr != tail) { curr = curr->next; } }
前驱
//Prev – move curr one pos toward the head voidprev(){ if (curr == head) return; // No previous element Link<E>* temp = head; //march down list until the previous element while (temp->next!=curr) temp=temp->next; curr = temp; }
比较
linked lists are more space efficient when implementing lists whose
number of elements varies widely or is unknown.
链表在以下情况下更节省空间：实现其元素数量的列表变化很大或未知。
Array-based lists are generally more space efficient when the user
knows in advance approximately how large the list will become.
// The stack ADT template <typename E> classStack { private: voidoperator=(const Stack&) {} //Protect assignment Stack(const Stack&) {} //Protect copy assignment public: // Push an element onto the top of the stack. virtualboolpush(const E& it) = 0; // Remove the element at the top of the stack. virtual E pop()= 0; // Return a copy of the top element virtualconst E& topValue()const= 0; };
数组实现
栈必须声明为固定的大小
emplate <typename E> classAstack: public Stack<E> { private: int maxSize; // Maximum size of stack int top; // Index for top element (free position) E *listArray; // Array holding stack elements public: AStack(int size=defaultSize) //Constructor { maxSize=size; top=0; listArray=new E[size]; } ~Astack() { delete [] listArray; } //Destructor
数组尾部元素作为栈顶：
通过将元素追加到列表尾部来将其压入堆栈，每次成本都是\(O(1)\)
顶部设置
堆栈中第一个空闲位置的数组索引，空栈的顶部设置是0。
Push：先插入元素，然后递增top
Pop：先递减top，然后移除top元素；
注意两个操作的顺序。
代码实现：
voidclear(){ top=0; } //Reinitialize
voidpush(const E& it){ // put “it” on stack Assert(top != maxSize, “Stack is full”); listArray[top++] = it; }
E pop(){//pop top element Assert(top != 0, “Stack is empty”); return listArray[--top]; }
const E& topValue()const{ //return top element Assert(top != 0, “Stack is empty”); return listArray[top-1]; }
链表实现
注意：元素仅从列表头部插入和删除
//A linked stack template <typename E> classLStack: public Stack<E> { private: Link<E>* top; //pointer to first element int size; //number of elements public: LStack(int sz = defaultSize){ //Constructor top = NULL; size = 0; } ~LStack() { clear(); } //Destructor
代码实现：
voidclear(){ //reinitialize while (top != NULL) { //delete link nodes Link<E>* temp = top; top = top->next; delete temp; } size = 0; }
voidpush(const E& it){ //put “it” on the stack top = newLink<E>(it, top); size++; }
E pop(){ //remove “it” from stack Assert(top != NULL, “Stack is empty”); E it = top->element; Link<E>* ltemp = top->next; delete top; top = ltemp; size--; return it; }
const E& topValue()const{ //return top value Assert(top != 0, “Stack is empty”); return top->element; }
//Array Implementation for Queue template <typename E> classAQueue: public Queue<E> { private: int maxSize; // Maximum size of queue int front; // Index of front element int rear; // Index of back element E *listArray; // Array holding queue elements int currSize; //length of queue … };
//Array-based Implementation (solution 2) template <typename E> classAQueue: public Queue<E> { private: int maxSize; // Maximum size of queue int front; // Index of front element int rear; // Index of rear element E *listArray; //Array holding queue elements public: AQueue(int size =defaultSize) { // Constructor- Make list array one position // larger for empty slot maxSize = size+1; rear = 0; front = 1; listArray = new E[maxSize]; } ~AQueue() { delete [] listArray; }
//reinitialize voidclear(){rear = 0; front = 1;} voidenqueue(const E& it){//put “it” in queue Assert(((rear+2) % maxSize) != front,“Queue is full”); rear = (rear+1)%maxSize; listArray[rear] = it; }
E dequeue(){//take element out Assert(length() != 0, “Queue is empty”); E it = listArray[front]; front =(front+1)%maxSize; return it; }
//get front value const E& frontValue()const{ Assert(length()!=0, “Queue is empty”); return listArray[front]; }
