Lists
A list is a finite,ordered sequence of data
items.
Important concept,List elements have a
position.
Notation,<a0,a1,…,an-1>
What operations should we implement?
List Implementation Concepts
Our list implementation will support the
concept of a current position.
We will do this by defining the list in terms of
left and right partitions.
? Either or both partitions may be empty.
Partitions are separated by the fence.
<20,23 | 12,15>
List ADT Page 90
template <class Elem> class List
{ public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
virtual int leftLength() const = 0;
virtual int rightLength() const = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const =0;
virtual void print() const = 0;
} ;
List ADT (continue)
Array-Based List Insert
Array-Based List Class Page 93
template <class Elem>
class AList, public List<Elem>
{ private:
int maxSize;
int listSize;
int fence;
Elem* listArray;
public:
AList(int size=DefaultListSize)
{ maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
Array-based list
Maximum size of list
Actual elem count
Position of fence
Array holding list
~AList() { delete [ ] listArray; }
void clear()
{ delete [ ] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
void setStart() { fence = 0; }
void setEnd() { fence = listSize; }
void prev() { if (fence != 0) fence--; }
void next()
{ if (fence < listSize) fence++; }
int leftLength() const { return fence; }
int rightLength() const
{ return listSize - fence; }
bool setPos(int pos)
{ if ((pos >= 0) && (pos <= listSize))
fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it) const
{ if (rightLength() == 0) return false;
else { it = listArray[fence];
return true;
}
}
Insert
template <class Elem>
bool AList<Elem>::insert(const Elem&
item)
{ if (listSize == maxSize) return false;
for(int i=listSize; i>fence; i--)
listArray[i] = listArray[i-1];
listArray[fence] = item;
listSize++;
return true;
} Insert at front of
right partition
Shif Elems up to
make roomIncrement list size
Append
template <class Elem>
bool AList<Elem>::append(const Elem& item)
{
if (listSize == maxSize) return false;
listArray[listSize++] = item;
return true;
} Append Elem to
end of the list
Remove
template <class Elem> bool
AList<Elem>::remove(Elem& it)
{ if (rightLength() == 0) return false;
it = listArray[fence];
for(int i=fence; i<listSize-1; i++)
listArray[i] = listArray[i+1];
listSize--;
return true;
}
Remove and return
first Elem in right
partitionCopy ElemShift them down
Decrement size
main
#include <iostream.h>
#include "AList.h“
void main()
{ // Declare some sample lists
AList<int> L1;
AList<char> L2(26);
int i,j;
cout<<"List L1 is,";
for(i=0; i<5; i++){ j=i*2+1; L1.insert(j); }
for(i=1; i<6; i++){ j=i*2; L1.append(j); }
L1.print();
cout<<"\nList L1 move next 2 pos,";
L1.setStart(); L1.next(); L1.next(); L1.print();
cout<<"\nList L1 remove,";
L1.remove(j); L1.print();
cout<<"Remove elem is " <<j <<endl;
cout<<"\nList L1 insert 39,";
j=39; L1.insert(j); L1.print();
char c;
cout<<"\nList L2 is,";
for(i=0; i<26; i++) { c=i+65; L2.append(c); }
for(i=0; i<13; i++)L2.next();
L2.print();
}
result
List L1 is,< ┃ 9 7 5 3 1 2 4 6 8 10 >
List L1 move next 2 pos,< 9 7 ┃ 5 3 1 2 4 6 8 10 >
List L1 remove,< 9 7 ┃ 3 1 2 4 6 8 10 >
Remove elem is 5
List L1 insert 39,< 9 7 ┃ 39 3 1 2 4 6 8 10 >
List L2 is,< A B C D E F G H I J K L M ┃ N O P Q R S T U V
W X Y Z >
Link Class
Dynamic allocation of new list elements.
template <class Elem> class Link
{ public:
Elem element;
Link *next;
Link(const Elem& elemval,Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL)
{ next = nextval; }
};
Singly-linked list nodeValue for this node
Pointer to next node
template <class Elem>
class LList, public List<Elem>
{ private:
Link<Elem>* head;
Link<Elem>* tail;
Link<Elem>* fence;
int leftcnt;
int rightcnt;
void init()
{ fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
Point to list headerPointer to last ElemLast element on leftSize of left
Size of right
void removeall()
{ while(head != NULL)
{ fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size=DefaultListSize) { init(); }
~LList() { removeall(); }
void clear() { removeall(); init(); }
… page 97
Return link nodes
to free store
Destructor
Linked List Class (add)
template <class Elem>
int LList<Elem>::find(const Elem&x)
/* search Elem x,return -1 if not find,
otherwise return position of x */
{ Link<Elem> *q = head->next; int i=0;
while(q&& q->element!=x) q=q->next,i++;
if(q) return i; else return -1;
}
template<class Elem>LList<Elem>::
LList(const LList<Elem>©)
// copy constructor
{ init();
Link<Elem> *s = head,*q = head->next,
*p=copy.head->next ;
while(p)
{ q = new Link<Elem>(p->element);
s->next = q; s = q; p = p->next;
}
setPos(copy.leftcnt);
}
template <class Elem>LList<Elem>& LList<Elem>::
operator=(LList<Elem>& copy)
// overloaded assignment "="
{ if (copy.Size() == 0) clear();
else
{ Link<Elem> *s = head,*q = head->next,
*p = copy.head->next ;
while ( p && q )
{ q->element=p->element;
s=q,q=q->next; p=p->next;
}
// continue
if(q)
do{ p=q->next; delete q; q=p; }while(q);
else
while(p)
{ q = new Link<Elem>(p->element);
s->next = q; s = q; p = p->next;
}
setPos(copy.leftcnt);
}
return *this;
}
/* 求整数集合 A = (A-B)∪ (B-A)
（求集合 A,B的对称差存入集合 A）。
算法思路：
分别用带头结点的单链表 La Lb表示集合 A和 B，
用 for循环逐个从 Lb表中取元素存入 x中，
在 La表中查找 x，若找到，则 x∈ A∩B，将 x从
La表删除；否则 x∈ B－ A，将 x插入 La表，
for循环结束算法完成；此时 La表代表所求的
(A-B)∪ (B-A)集合,Lb保持不变。
#include <stdlib.h>
#include <time.h>
#include "LList.h"
void Symm_diff(LList<int>&,LList<int>&);
// 求以单链表存储的两个集合“对称差”之原型 (prototype)声
明
void CrtLinkList(LList<int>&,int);
//为集合产生若干互不相等的整数插入链表的原型声明
void SetUnion(LList<int>&,LList<int>&);
// 求以单链表存储的两个集合“并”之原型声明
void main()
{ LList<int> La,Lb,Lc;
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t));
//初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? ";
cin>>s1>>s2; // 输入集合 A,B元素数
cout<<"\nSet A = < | "; // 输出集合 A的名称
CrtLinkList(La,s1); // 创建集合 A,输出集合元素
cout<<" >\n Length="<<s1<<"\n\nSet B = < | ";
// 输出集合 B的名称
// continue
CrtLinkList(Lb,s2); // 创建集合 B,输出集合元素
cout<<" >\n Length="<<s2<<"\n\nC=A is ";
Lc=La; Lc.print();
cout<<" \n Length="<<s1<<"\n\n(A-B)∪ (B-A) = ";
Symm_diff(La,Lb); // La = (A-B)∪ (B-A)
La.print();
cout<<"List La now Length = "<<La.Size()<<endl;
cout<<" \n\n C∪ B=";
SetUnion(Lc,Lb); Lc.print();
LList<int> Ld(La);
cout<<" \n\n Ld="; Ld.print();
}
void CrtLinkList(LList<int>& L,int n)
// 为链表 L产生 n个互不相等的整数插入表 尾
{ int x,i,j ;
for(i=0; i<n; i++)
// 用随机数发生器产生 n个集合元素,不得重复
{ do{ x=rand() % 37; } // 产生 0-36间的随机整数
while((j=L.find(x))!=-1);
// 在集合中找 x,找不到则脱离循环
L.append(x); // 插入表尾
cout<<x<<" "; // 输出 x ( 集合元素边产生边输出 )
}
}
void Symm_diff(LList<int>& La,LList<int>& Lb)
{ int x,i;
Lb.setStart();
for(int j=0; j<Lb.Size(); j++)
{ Lb.getValue(x); // 取集合 B的元素
Lb.next();
if ((i=La.find(x)) == -1) // 集合 B的元素不在 A中
La.insert(x); // 插入 A集合
else // 集合 B的元素在 A中,删除之
{ La.setPos(i); La.remove(x); }
}
}
void SetUnion(LList<int>&La,LList<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空。
{int i,k,b;
Lb.setStart();
for (i=Lb.Size(); i>0; i--)
// 从 Lb表中逐次删除素尾元素，这样不必移动元素
{ Lb.remove(b); // 调用删除算法，被删元素存入 b
k=La.find(b); // 在 La表中查找 b
if(k==-1) // La表中找不到元素 b
La.insert(b); // 插入至 la表尾
} // end_for
}
Comparison of Implementations
Array-Based Lists:
? Insertion and deletion are ?(n).
? Prev and direct access are ?(1).
? Array must be allocated in advance.
? No overhead if all array positions are full.
Linked Lists:
? Insertion and deletion are ?(1).
? Prev and direct access are ?(n).
? Space grows with number of elements.
? Every element requires overhead.
Space Comparison
,Break-even” point:
DE = n(P + E);
n = DE
P + E
E,Space for data value.
P,Space for pointer.
D,Number of elements in array.
Freelists
System new and delete are slow.
// Singly-linked list node with freelist
template <class Elem> class Link {
private:
static Link<Elem>* freelist; // Head
public:
Elem element; // Value for this node
Link* next; // Point to next node Link(const Elem& elemval,
Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL) {next=nextval;}
void* operator new(size_t); // Overload
void operator delete(void*); // Overload
};
Freelists (2)
template <class Elem>
Link<Elem>* Link<Elem>::freelist = NULL;
template <class Elem> // Overload for new
void* Link<Elem>::operator new(size_t) {
if (freelist == NULL) return,:new Link;
Link<Elem>* temp = freelist; // Reuse
freelist = freelist->next;
return temp; // Return the link
}
template <class Elem> // Overload delete
void Link<Elem>::operator delete(void* ptr){
((Link<Elem>*)ptr)->next = freelist;
freelist = (Link<Elem>*)ptr;
}
Doubly Linked Lists
Simplify insertion and deletion,Add a prev pointer.
// Doubly-linked list link node
template <class Elem> class Link {
public:
Elem element; // Value for this node
Link *next; // Pointer to next node
Link *prev; // Pointer to previous node
Link(const Elem& e,Link* prevp =NULL,
Link* nextp =NULL)
{ element=e; prev=prevp; next=nextp; }
Link(Link* prevp =NULL,Link* nextp =NULL)
{ prev = prevp; next = nextp; }
};
Doubly Linked Lists
Doubly Linked Insert
Doubly Linked Insert
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item) {
fence->next =
new Link<Elem>(item,fence,fence->next);
if (fence->next->next != NULL)
fence->next->next->prev = fence->next;
if (tail == fence) // Appending new Elem
tail = fence->next; // so set tail
rightcnt++; // Added to right
return true;
}
Doubly Linked Remove
Doubly Linked Remove
// Remove,return first Elem in right part
template <class Elem>
bool LList<Elem>::remove(Elem& it) {
if (fence->next == NULL) return false;
it = fence->next->element;
Link<Elem>* ltemp = fence->next;
if (ltemp->next != NULL)
ltemp->next->prev = fence;
else tail = fence; // Reset tail
fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space
rightcnt--; // Removed from right
return true;
}
Dictionary
Often want to insert records,delete records,search for records.
Required concepts:
? Search key,Describe what we are looking for
? Key comparison
– Equality,sequential search
– Relative order,sorting
? Record comparison
Comparator Class
How do we generalize comparison?
? Use ==,<=,>=,Disastrous
? Overload ==,<=,>=,Disastrous
? Define a function with a standard name
– Implied obligation
– Breaks down with multiple key fields/indices for same object
? Pass in a function
– Explicit obligation
– Function parameter
– Template parameter
Comparator Example
class intintCompare {
public:
static bool lt(int x,int y)
{ return x < y; }
static bool eq(int x,int y)
{ return x == y; }
static bool gt(int x,int y)
{ return x > y; }
};
Comparator Example (2)
class PayRoll {
public:
int ID;
char* name;
};
class IDCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return x.ID < y.ID; }
};
class NameCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return strcmp(x.name,y.name) < 0; }
};
Dictionary ADT
// The Dictionary abstract class.
template <class Key,class Elem,
class KEComp,class EEComp>
class Dictionary {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&,Elem&) = 0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&,Elem&)
const = 0;
virtual int size() = 0;
};
Unsorted List Dictionary
template <class Key,class Elem,
class KEComp,class EEComp>
class UALdict, public
Dictionary<Key,Elem,KEComp,EEComp> {
private,AList<Elem>* list;
public:
bool remove(const Key& K,Elem& e) {
for(list->setStart(); list->getValue(e);
list->next())
if (KEComp::eq(K,e)) {
list->remove(e);
return true;
}
return false;
}
};
Stacks
LIFO,Last In,First Out.
Restricted form of list,Insert and remove
only at front of list.
Notation:
? Insert,PUSH
? Remove,POP
? The accessible element is called TOP.
Stack ADT
// Stack abtract class
template <class Elem> class Stack {
public:
// Reinitialize the stack
virtual void clear() = 0;
// Push an element onto the top of the stack.
virtual bool push(const Elem&) = 0;
// Remove the element at the top of the stack,
virtual bool pop(Elem&) = 0;
// Get a copy of the top element in the stack
virtual bool topValue(Elem&) const = 0;
// Return the number of elements in the stack.
virtual int length() const = 0;
};
Array-Based Stack
// Array-based stack implementation
private:
int size; // Maximum size of stack
int top; // Index for top element
Elem *listArray; // Array holding elements
Issues:
? Which end is the top?
? Where does,top” point to?
? What is the cost of the operations?
Linked Stack
// Linked stack implementation
private:
Link<Elem>* top; // Pointer to first elem
int size; // Count number of elems
What is the cost of the operations?
How do space requirements compare to the array-based stack implementation?
Queues
FIFO,First in,First Out
Restricted form of list,Insert at one end,
remove from the other.
Notation:
? Insert,Enqueue
? Delete,Dequeue
? First element,Front
? Last element,Rear
Queue Implementation (1)
Queue Implementation (2)
A list is a finite,ordered sequence of data
items.
Important concept,List elements have a
position.
Notation,<a0,a1,…,an-1>
What operations should we implement?
List Implementation Concepts
Our list implementation will support the
concept of a current position.
We will do this by defining the list in terms of
left and right partitions.
? Either or both partitions may be empty.
Partitions are separated by the fence.
<20,23 | 12,15>
List ADT Page 90
template <class Elem> class List
{ public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
virtual int leftLength() const = 0;
virtual int rightLength() const = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const =0;
virtual void print() const = 0;
} ;
List ADT (continue)
Array-Based List Insert
Array-Based List Class Page 93
template <class Elem>
class AList, public List<Elem>
{ private:
int maxSize;
int listSize;
int fence;
Elem* listArray;
public:
AList(int size=DefaultListSize)
{ maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
Array-based list
Maximum size of list
Actual elem count
Position of fence
Array holding list
~AList() { delete [ ] listArray; }
void clear()
{ delete [ ] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
void setStart() { fence = 0; }
void setEnd() { fence = listSize; }
void prev() { if (fence != 0) fence--; }
void next()
{ if (fence < listSize) fence++; }
int leftLength() const { return fence; }
int rightLength() const
{ return listSize - fence; }
bool setPos(int pos)
{ if ((pos >= 0) && (pos <= listSize))
fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it) const
{ if (rightLength() == 0) return false;
else { it = listArray[fence];
return true;
}
}
Insert
template <class Elem>
bool AList<Elem>::insert(const Elem&
item)
{ if (listSize == maxSize) return false;
for(int i=listSize; i>fence; i--)
listArray[i] = listArray[i-1];
listArray[fence] = item;
listSize++;
return true;
} Insert at front of
right partition
Shif Elems up to
make roomIncrement list size
Append
template <class Elem>
bool AList<Elem>::append(const Elem& item)
{
if (listSize == maxSize) return false;
listArray[listSize++] = item;
return true;
} Append Elem to
end of the list
Remove
template <class Elem> bool
AList<Elem>::remove(Elem& it)
{ if (rightLength() == 0) return false;
it = listArray[fence];
for(int i=fence; i<listSize-1; i++)
listArray[i] = listArray[i+1];
listSize--;
return true;
}
Remove and return
first Elem in right
partitionCopy ElemShift them down
Decrement size
main
#include <iostream.h>
#include "AList.h“
void main()
{ // Declare some sample lists
AList<int> L1;
AList<char> L2(26);
int i,j;
cout<<"List L1 is,";
for(i=0; i<5; i++){ j=i*2+1; L1.insert(j); }
for(i=1; i<6; i++){ j=i*2; L1.append(j); }
L1.print();
cout<<"\nList L1 move next 2 pos,";
L1.setStart(); L1.next(); L1.next(); L1.print();
cout<<"\nList L1 remove,";
L1.remove(j); L1.print();
cout<<"Remove elem is " <<j <<endl;
cout<<"\nList L1 insert 39,";
j=39; L1.insert(j); L1.print();
char c;
cout<<"\nList L2 is,";
for(i=0; i<26; i++) { c=i+65; L2.append(c); }
for(i=0; i<13; i++)L2.next();
L2.print();
}
result
List L1 is,< ┃ 9 7 5 3 1 2 4 6 8 10 >
List L1 move next 2 pos,< 9 7 ┃ 5 3 1 2 4 6 8 10 >
List L1 remove,< 9 7 ┃ 3 1 2 4 6 8 10 >
Remove elem is 5
List L1 insert 39,< 9 7 ┃ 39 3 1 2 4 6 8 10 >
List L2 is,< A B C D E F G H I J K L M ┃ N O P Q R S T U V
W X Y Z >
Link Class
Dynamic allocation of new list elements.
template <class Elem> class Link
{ public:
Elem element;
Link *next;
Link(const Elem& elemval,Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL)
{ next = nextval; }
};
Singly-linked list nodeValue for this node
Pointer to next node
template <class Elem>
class LList, public List<Elem>
{ private:
Link<Elem>* head;
Link<Elem>* tail;
Link<Elem>* fence;
int leftcnt;
int rightcnt;
void init()
{ fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
Point to list headerPointer to last ElemLast element on leftSize of left
Size of right
void removeall()
{ while(head != NULL)
{ fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size=DefaultListSize) { init(); }
~LList() { removeall(); }
void clear() { removeall(); init(); }
… page 97
Return link nodes
to free store
Destructor
Linked List Class (add)
template <class Elem>
int LList<Elem>::find(const Elem&x)
/* search Elem x,return -1 if not find,
otherwise return position of x */
{ Link<Elem> *q = head->next; int i=0;
while(q&& q->element!=x) q=q->next,i++;
if(q) return i; else return -1;
}
template<class Elem>LList<Elem>::
LList(const LList<Elem>©)
// copy constructor
{ init();
Link<Elem> *s = head,*q = head->next,
*p=copy.head->next ;
while(p)
{ q = new Link<Elem>(p->element);
s->next = q; s = q; p = p->next;
}
setPos(copy.leftcnt);
}
template <class Elem>LList<Elem>& LList<Elem>::
operator=(LList<Elem>& copy)
// overloaded assignment "="
{ if (copy.Size() == 0) clear();
else
{ Link<Elem> *s = head,*q = head->next,
*p = copy.head->next ;
while ( p && q )
{ q->element=p->element;
s=q,q=q->next; p=p->next;
}
// continue
if(q)
do{ p=q->next; delete q; q=p; }while(q);
else
while(p)
{ q = new Link<Elem>(p->element);
s->next = q; s = q; p = p->next;
}
setPos(copy.leftcnt);
}
return *this;
}
/* 求整数集合 A = (A-B)∪ (B-A)
（求集合 A,B的对称差存入集合 A）。
算法思路：
分别用带头结点的单链表 La Lb表示集合 A和 B，
用 for循环逐个从 Lb表中取元素存入 x中，
在 La表中查找 x，若找到，则 x∈ A∩B，将 x从
La表删除；否则 x∈ B－ A，将 x插入 La表，
for循环结束算法完成；此时 La表代表所求的
(A-B)∪ (B-A)集合,Lb保持不变。
#include <stdlib.h>
#include <time.h>
#include "LList.h"
void Symm_diff(LList<int>&,LList<int>&);
// 求以单链表存储的两个集合“对称差”之原型 (prototype)声
明
void CrtLinkList(LList<int>&,int);
//为集合产生若干互不相等的整数插入链表的原型声明
void SetUnion(LList<int>&,LList<int>&);
// 求以单链表存储的两个集合“并”之原型声明
void main()
{ LList<int> La,Lb,Lc;
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t));
//初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? ";
cin>>s1>>s2; // 输入集合 A,B元素数
cout<<"\nSet A = < | "; // 输出集合 A的名称
CrtLinkList(La,s1); // 创建集合 A,输出集合元素
cout<<" >\n Length="<<s1<<"\n\nSet B = < | ";
// 输出集合 B的名称
// continue
CrtLinkList(Lb,s2); // 创建集合 B,输出集合元素
cout<<" >\n Length="<<s2<<"\n\nC=A is ";
Lc=La; Lc.print();
cout<<" \n Length="<<s1<<"\n\n(A-B)∪ (B-A) = ";
Symm_diff(La,Lb); // La = (A-B)∪ (B-A)
La.print();
cout<<"List La now Length = "<<La.Size()<<endl;
cout<<" \n\n C∪ B=";
SetUnion(Lc,Lb); Lc.print();
LList<int> Ld(La);
cout<<" \n\n Ld="; Ld.print();
}
void CrtLinkList(LList<int>& L,int n)
// 为链表 L产生 n个互不相等的整数插入表 尾
{ int x,i,j ;
for(i=0; i<n; i++)
// 用随机数发生器产生 n个集合元素,不得重复
{ do{ x=rand() % 37; } // 产生 0-36间的随机整数
while((j=L.find(x))!=-1);
// 在集合中找 x,找不到则脱离循环
L.append(x); // 插入表尾
cout<<x<<" "; // 输出 x ( 集合元素边产生边输出 )
}
}
void Symm_diff(LList<int>& La,LList<int>& Lb)
{ int x,i;
Lb.setStart();
for(int j=0; j<Lb.Size(); j++)
{ Lb.getValue(x); // 取集合 B的元素
Lb.next();
if ((i=La.find(x)) == -1) // 集合 B的元素不在 A中
La.insert(x); // 插入 A集合
else // 集合 B的元素在 A中,删除之
{ La.setPos(i); La.remove(x); }
}
}
void SetUnion(LList<int>&La,LList<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空。
{int i,k,b;
Lb.setStart();
for (i=Lb.Size(); i>0; i--)
// 从 Lb表中逐次删除素尾元素，这样不必移动元素
{ Lb.remove(b); // 调用删除算法，被删元素存入 b
k=La.find(b); // 在 La表中查找 b
if(k==-1) // La表中找不到元素 b
La.insert(b); // 插入至 la表尾
} // end_for
}
Comparison of Implementations
Array-Based Lists:
? Insertion and deletion are ?(n).
? Prev and direct access are ?(1).
? Array must be allocated in advance.
? No overhead if all array positions are full.
Linked Lists:
? Insertion and deletion are ?(1).
? Prev and direct access are ?(n).
? Space grows with number of elements.
? Every element requires overhead.
Space Comparison
,Break-even” point:
DE = n(P + E);
n = DE
P + E
E,Space for data value.
P,Space for pointer.
D,Number of elements in array.
Freelists
System new and delete are slow.
// Singly-linked list node with freelist
template <class Elem> class Link {
private:
static Link<Elem>* freelist; // Head
public:
Elem element; // Value for this node
Link* next; // Point to next node Link(const Elem& elemval,
Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL) {next=nextval;}
void* operator new(size_t); // Overload
void operator delete(void*); // Overload
};
Freelists (2)
template <class Elem>
Link<Elem>* Link<Elem>::freelist = NULL;
template <class Elem> // Overload for new
void* Link<Elem>::operator new(size_t) {
if (freelist == NULL) return,:new Link;
Link<Elem>* temp = freelist; // Reuse
freelist = freelist->next;
return temp; // Return the link
}
template <class Elem> // Overload delete
void Link<Elem>::operator delete(void* ptr){
((Link<Elem>*)ptr)->next = freelist;
freelist = (Link<Elem>*)ptr;
}
Doubly Linked Lists
Simplify insertion and deletion,Add a prev pointer.
// Doubly-linked list link node
template <class Elem> class Link {
public:
Elem element; // Value for this node
Link *next; // Pointer to next node
Link *prev; // Pointer to previous node
Link(const Elem& e,Link* prevp =NULL,
Link* nextp =NULL)
{ element=e; prev=prevp; next=nextp; }
Link(Link* prevp =NULL,Link* nextp =NULL)
{ prev = prevp; next = nextp; }
};
Doubly Linked Lists
Doubly Linked Insert
Doubly Linked Insert
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item) {
fence->next =
new Link<Elem>(item,fence,fence->next);
if (fence->next->next != NULL)
fence->next->next->prev = fence->next;
if (tail == fence) // Appending new Elem
tail = fence->next; // so set tail
rightcnt++; // Added to right
return true;
}
Doubly Linked Remove
Doubly Linked Remove
// Remove,return first Elem in right part
template <class Elem>
bool LList<Elem>::remove(Elem& it) {
if (fence->next == NULL) return false;
it = fence->next->element;
Link<Elem>* ltemp = fence->next;
if (ltemp->next != NULL)
ltemp->next->prev = fence;
else tail = fence; // Reset tail
fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space
rightcnt--; // Removed from right
return true;
}
Dictionary
Often want to insert records,delete records,search for records.
Required concepts:
? Search key,Describe what we are looking for
? Key comparison
– Equality,sequential search
– Relative order,sorting
? Record comparison
Comparator Class
How do we generalize comparison?
? Use ==,<=,>=,Disastrous
? Overload ==,<=,>=,Disastrous
? Define a function with a standard name
– Implied obligation
– Breaks down with multiple key fields/indices for same object
? Pass in a function
– Explicit obligation
– Function parameter
– Template parameter
Comparator Example
class intintCompare {
public:
static bool lt(int x,int y)
{ return x < y; }
static bool eq(int x,int y)
{ return x == y; }
static bool gt(int x,int y)
{ return x > y; }
};
Comparator Example (2)
class PayRoll {
public:
int ID;
char* name;
};
class IDCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return x.ID < y.ID; }
};
class NameCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return strcmp(x.name,y.name) < 0; }
};
Dictionary ADT
// The Dictionary abstract class.
template <class Key,class Elem,
class KEComp,class EEComp>
class Dictionary {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&,Elem&) = 0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&,Elem&)
const = 0;
virtual int size() = 0;
};
Unsorted List Dictionary
template <class Key,class Elem,
class KEComp,class EEComp>
class UALdict, public
Dictionary<Key,Elem,KEComp,EEComp> {
private,AList<Elem>* list;
public:
bool remove(const Key& K,Elem& e) {
for(list->setStart(); list->getValue(e);
list->next())
if (KEComp::eq(K,e)) {
list->remove(e);
return true;
}
return false;
}
};
Stacks
LIFO,Last In,First Out.
Restricted form of list,Insert and remove
only at front of list.
Notation:
? Insert,PUSH
? Remove,POP
? The accessible element is called TOP.
Stack ADT
// Stack abtract class
template <class Elem> class Stack {
public:
// Reinitialize the stack
virtual void clear() = 0;
// Push an element onto the top of the stack.
virtual bool push(const Elem&) = 0;
// Remove the element at the top of the stack,
virtual bool pop(Elem&) = 0;
// Get a copy of the top element in the stack
virtual bool topValue(Elem&) const = 0;
// Return the number of elements in the stack.
virtual int length() const = 0;
};
Array-Based Stack
// Array-based stack implementation
private:
int size; // Maximum size of stack
int top; // Index for top element
Elem *listArray; // Array holding elements
Issues:
? Which end is the top?
? Where does,top” point to?
? What is the cost of the operations?
Linked Stack
// Linked stack implementation
private:
Link<Elem>* top; // Pointer to first elem
int size; // Count number of elems
What is the cost of the operations?
How do space requirements compare to the array-based stack implementation?
Queues
FIFO,First in,First Out
Restricted form of list,Insert at one end,
remove from the other.
Notation:
? Insert,Enqueue
? Delete,Dequeue
? First element,Front
? Last element,Rear
Queue Implementation (1)
Queue Implementation (2)
