Chapter 6 LISTS AND STRINGS
1,List Specifications
2,List Implementations
(a),Class Templates
(b),Contiguous
(c),Simply Linked
(d),Simply Linked with Position
Pointer(e),Doubly Linked
Chapter 6 LISTS AND STRINGS
3,Strings
4,Application,Text Editor
5,Linked Lists in Arrays
6,Application,
Generating Permutations
7,Pointers and Pitfalls
DEFINITION
A list of elements of type T is a finite sequence of
elements of T together with the following operations,
1,Construct the list,leaving it empty.
2,Determine whether the list is empty or not.
3,Determine whether the list is full or not.
4,Find the size of the list.
5,Clear the list to make it empty.
6,Insert an entry at a specified position of the list.
7,Remove an entry from a specified position in the
list.
8,Retrieve the entry from a specified position in the
list.
9,Replace the entry at a specified position in the list.
10,Traverse the list,performing a given operation on
6.1 List Definition
Comparison with Standard Template Library:
◆ The STL list provides only those operations
that can be implemented efficiently in a List
implementation known as doubly linked,which we
shall study shortly.
◆ The STL list does not allow random access to an
arbitrary list position.
◆ The STL vector,does provide some random
access to a sequence of data values,but not all
the other capabilities we shall develop for a List.
◆ In this way,our study of the List ADT provides
an introduction to both the STL classes list and
List,,List( );
Post,The List has been created and is
initialized
to be empty.
Method Specifications
void List,,clear();
Post,All List entries have been removed;
the List is empty.
bool List,,empty() const;
Post,The function returns true or false
according to
whether the List is empty or not.
bool List,,full() const;
Post,The function returns true or false
according to
whether the List is full or not.
int List,,size() const;
Post,The function returns the number of
entries in the List.
Position Number in a List
◆ To find an entry in a list,we use an integer that
gives its position within the list.
◆ We shall number the positions in a list so that
the first entry in the list has position 0,the second
position 1,and so on.
◆ Locating an entry of a list by its position is
superficially like indexing an array,but there are
important differences,If we insert an entry at a
particular position,then the position numbers of
all later entries increase by 1,If we remove an
entry,then the positions of all following entries
decrease by 1.
◆ The position number for a list is defined
without regard to the implementation,For a
contiguous list,implemented in an array,the
position will indeed be the index of the entry
within the array,But we will also use the position
to find an entry within linked implementations of
a list,where no indices or
arrays are used at all.
Error_code List::insert(int position,const
List_entry &x);
Post,If the List is not full and 0 position
n,
where n is the number of entries in
the
List,the function succeeds:Any
entry
formerly at position and all later
entries have their position
numbers
increased by 1,
and x is inserted at position in the
List.
Error_code List,,remove ( int position,
List_entry &x );
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The
entry at position is removed from the List,
and
all later entries have their position
numbers
decreased by 1,The parameter x records
a copy
of the entry formerly at position.
Else,The function fails with a diagnostic
Error_code List,,retrieve(int position,
List_entry &x)
const;
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The
entry at position is copied to x; all List
entries
remain unchanged.
Else,The function fails with a diagnostic
error code.
Error_code List,,replace(int position,
const List_entry
&x);
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The entry at position is replaced by x; all
other
entries remain unchanged.
Else,The function fails with a diagnostic
error code.void List::traverse(void (*visit)(List entry
&));
Post,The action specified by function
*visit has
been performed on every entry of the
List,
6.2 Implementations of
ListsClass Templates
◆ A C++ template construction allows us to write
code,usually code to implement a class,that uses
objects of an arbitrary,generic type.
◆ In template code we utilize a parameter enclosed in
angle
brackets< > to denote the generic type.
◆ Later,when a client uses our code,the client can
substitute an actual type for the template parameter,
The client can thus obtain several actual pieces of
code from our template,using different actual types in
place of the template parameter.
?Example,We shall implement a template
class List that depends on one generic type
parameter,A client can then use our template to
declare several lists with different types of
entries with declarations of the following form:
List<int> rst list;
List<char> second list;
?Templates provide a new mechanism for
creating generic data structures,one that
allows many different specializations of a given
data structure template in a single application.
?The added generality that we get by using
templates comes at the price of slightly more
complicated class specifications and
implementations.
Contiguous(storage) Implementation
连续 /顺序 (存储 )的
One-dimensional
arrays
template <class List_entry> class List
{ public:
// methods of the List ADT
List( );
int size( ) const;
bool full( ) const;
bool empty( ) const;
void clear( );
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
求顺序表的长度判顺序表是否已 "满 "
判顺序表是否为, 空 "清空顺序表
遍历顺序表
查找表中第 position
个元素存入 x将表中第 position个元素值修改为 x删除表中第 position
个元素，其值存入 x
将 x插入表中
令其成为第
position个元素
protected:
// data members for a contiguous list implementation
int count;
List_entry entry[max_list];
};
template <class List_entry>
int List<List_entry>::size( ) const
// Post,The function returns the number of entries in the
List,
{ return count; }
template <class List_entry> Error_code List<List_entry>
::insert(int position,const List_entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n; where n
is the number of entries in the List,the function succeeds,
Any entry formerly at position and all later entries have
their position numbers increased by 1 and x is inserted at
position of the List,
Else,The function fails with a diagnostic Error_code,*/
{ if (full( )) return overflow;
if (position < 0 || position > count)
return range_error;
for (int i=count-1; i >= position; i--) entry[i +1] = entry[i];
entry[position] = x;
count++;
return success;
}
template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/* Post,The action specified by function(*visit) has been
performed on every entry of the List,beginning at
position 0 and doing each in turn,*/
{
for (int i=0; i<count; i++) (*visit)(entry[i]);
}
Performance of Methods
In processing a contiguous list with n entries:
? insert and remove operate in time
approximately proportional to n,
? List,clear,empty,full,size,replace,and
retrieve operate in constant time.
Please follow the
Error_code insert(int position,const List_entry &x)
write by yourselves:
Error_code retrieve(int position,List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Application,Contiguous List
设顺序表 la和 lb分别表示整数集合 A和 B，求,A=A∪B 。
算法思路, 集合中的元素是无重复的，可将 Lb表中的
元素从表尾起逐个删除，并在 La表查找被删元素 b，若
找不到，则将元素 b插入 La表，否则不必插入，完成后
集合 B为空。
在 List类中增加一个成员函数 (方法 ),Find
template <class List_entry>
int List<List_entry>::Find(const List_entry &x)
// 查找值为 x的元素,返回 -1没找到,否则为 x在表中的位置
{ int i=0;
while( i<count && entry[i]!= x )i++;
if(i<count) return i; else return -1;
}
下面给出：产生若干互不相等的随机整数 (集合元素 )
插入表的函数,CrtSetList ；进行集合“并”运算的
函数,SetUnion及主函数 main()的源代码。
在 class List_entry中
应当有定义
#include <stdlib.h>
#include <time.h>
#include "SQList.h"
void CrtSetList(List<int>&,int); // 产生集合元素插入表的原型声明
void SetUnion(List<int>&,List<int>&); // 集合 "并 "运算的原型声
明
void visit(int &i);
void main()
{ // 声明 List对象 La,Lb,类参数 List_entry用 <int>实例化
List<int> La,Lb; // La,Lb代表集合
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t)); // 初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? (<=15)";
cin>>s1>>s2; // 输入集合 A,B元素数 <=15，以保证 "并 "后 La的元素数
<=30
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtSetList(La,s1); // 创建集合 A并输出集合元素
cout<<"}\nSet B = { "; // 输出集合 B的名称
CrtSetList(Lb,s2);
SetUnion(La,Lb); // 求集合 A与集合 B的 "并 "
cout<<"}\n\n A Union B = { ";
La.traverse(visit); cout<<" }\n";
}
void CrtSetList(List<int>&L,int n)
// 为集合产生 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.insert(L.size(),x); // 插入表尾
cout<<x<<" "; // 输出 x ( 集合元素边产生边输出 )
}
}
void SetUnion(List<int>&La,List<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空。
{int i,k,b;
for(i=Lb.size(); i>0; i--) //从 Lb表中逐次删除素尾元素 (不必移动元素 )
{ Lb.remove(i-1,b); //调用删除算法，被删元素存入 b
k=La.Find(b); // 在 La表中查找 b
if(k==-1) // La表中找不到元素 b
La.insert(La.size(),b); // 插入至 la表尾
} //end_for
}
void visit(int &i)
{ cout<<i<<' '; }
Simply Linked
Implementationtemplate <class Node_entry> struct Node // Node
declaration:
{ Node_entry entry;
Node<Node_entry> *next;
Node( ); // constructors
Node(Node_entry,Node<Node_entry> *link=NULL);
// constructors
};
template <class List_entry>class List // List
declaration:
{ public:
// Specifications for the methods of the list ADT go
here.
~List( );
List(const List<List_entry> ©);
void operator=(const List<List_entry> ©);
protected:
// Data members for the linked list implementation now
follow.
int count;
Node<List_entry> *head;
// The following auxiliary function is used to locate list
positions
Node<List_entry> *set_position(int position) const;
};
Actions on a Linked List
Finding a List Position
◆ Function set position takes an integer parameter
position and returns a pointer to the corresponding
node of the list.
◆ Declare the visibility of set position as protected,
since set position returns a pointer to,and
therefore gives access to,a Node in the List,To
maintain an encapsulated data structure,we must
restrict the visibility of set position,Protected
visibility ensures that it is only available as a tool
for constructing other methods of the List.
◆ To construct set position,we start at the
beginning of the List and traverse it until we reach
the desired node:
template <class List_entry> Node<List_entry>
*List<List_entry>::set_position(int position) const
/* Pre,position is a valid position in the List ;0 ≤
position<count,
Post,Returns a pointer to the Node in position, */
{ Node<List_entry> *q = head;
for (int i=0; i<position; i++) q=q->next;
return q;
}
◆ If all nodes are equally likely,then,on average,
the set position function must move halfway
through the List to find a given position,Hence,
on average,its time requirement is approximately
proportional to n,the size of the List.
template <class List_entry> Error_code List<List_entry>,,
insert(int position,const List_entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n,where n
is the number of entries in the List,the function succeeds,
Any entry formerly at position and all later entries have
their position numbers increased by 1,and x is inserted at
position of the List.
Else,The function fails with a diagnostic error_code,*/
{ if (position < 0 || position > count) return range_error;
Node<List_entry> *new node,*previous,*following;
if (position > 0)
{ previous = set position(position, 1);
following = previous->next;
}
else following = head;
Insertion Method
new_node = new Node<List_entry>(x,following);
if(new_node==NULL)return overflow;
if (position==0) head = new_node;
else previous->next = new_node;
count++;
return success;
}
Insert to
Firsr entry
为了避免插入位置不同带来的处理方法的不一致，
可以在第一个元素 (“首元结点, )前，虚设一个结点称
之为, 头结点, ；这样, 头指针, 指向, 头结点,,
如下图所示：
In processing a linked List with n entries:
? clear,insert,remove,retrieve,and replace
require time approximately proportional to n.
? List,empty,full,and size operate in constant
time.
Variation,Keeping the Current Position
◆ Suppose an application processes list entries
in order or refers to the same entry several times
before processing another entry.
◆ Remember the last-used position in the list and,
if the next operation refers to the same or a later
position,start tracing through the list from this
last-used position.
◆ Note that this will not speed up every
application using lists.
◆ The method retrieve is defined as const,but its
implementation will need to alter the last-used
position of a List,To enable this,we use the
mutable qualifier,Mutable data members of a class
can be changed,even by constant methods.
template <class List_entry>class List
{public:
// Add specifications for the methods of the list ADT.
// Add methods to replace the compiler-generated
defaults.
protected:
// Data members for the linked-list implementation with
// current position follow,
◆ All the new class members have protected
visibility,so,from the perspective of a client,the
class looks exactly like the earlier implementation.
◆ The current position is now a member of the
class List,so there is no longer a need for set
position to return a pointer; instead,the function
simply resets the pointer current directly within
the List.
int count;
mutable int current position;
Node<List_entry> *head;
mutable Node<List_entry> *current;
// Auxiliary function to locate list positions follows:
void set_position(int position) const;
};
template <class List_entry> void List<List_entry>,,
set_position(int position) const
/* Pre,position is a valid position in the List, 0<=position <
count,
Post,The current Node pointer references the Node at
position, */
{ if (position < current_position) // must start over at head
of list
{ current_position = 0; current = head; }
for (; current_position != position; current_position++)
current = current->next;
}
◆ For repeated references to the same position,
neither the body of the if statement nor the body
of the for statement will be executed,and hence
the function will take almost no time.
◆ If we move forward only one position,the body
of the for statement will be executed only once,
so again the function will be very fast.
◆ If it is necessary to move backwards through
the List,then the function operates in almost the
same way as the version of set position used in
the previous implementation.
下面将 Simply (single) Linked类的声明部分
给出，实现及测试演示给大家（源代码可以
复制给大家） 。
#include <iostream.h>
enum Error_code{ success,fail,range_error };
template <class Node_entry> struct Node // Node
declaration
{ Node_entry entry;
Node<Node_entry> *next;
Node( ){ next=NULL; }
Node(Node_entry data,Node<Node_entry> *link=NULL)
{ entry=data; next=link; }
};
template <class List_entry>
class List // Single lined list declaration
{ public:
List(){ count=0; head = NULL; } // constructor
List(const List<List_entry> &); // copy constructor
~List(); // destructor
List& operator=(const List<List_entry>&);
// List:overloaded assignment"="
bool empty() const // Judge whether isEmpty?
{ return count==0; }
bool full()const; // Judge whether isFull?
int size()const // Compute the length
{ return count; }
void clear(); // to clear the List,become
empty
Error_code retrieve(int position,List_entry &x)const;
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
int find(const List_entry &x);
/* search List entry x,return -1 if not find,
otherwise return position of x */
void traverse(void (*visit)(List_entry &));
注 Simply (single) Linked类的文件名如下：
声明及实现,SLList.h
测试程序,exp_slink.cpp
Doubly Linked Lists
protected:
Node<List_entry> *head; //pointer,point to first
node
int count; //number of List_entry
Node<List_entry> *set_position(int position) const;
};
Node definition:
template <class Node_entry>
struct Node
{ // data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node( );
Node(Node_entry,Node<Node_entry> *link_back = NULL,
Node<Node_entry> *link_next = NULL);
};
List definition:
template <class List_entry> class List
{ public:
// Add specifications for methods of the list ADT.
// Add methods to replace compiler generated
defaults.
protected:
// Data members for the doubly-linked list implementation
follow:
int count;
mutable int current_position;
mutable Node<List_entry> *current;
// The auxiliary function to locate list positions
follows:
void set_position(int position) const;
◆ We can move either direction through the List
while keeping only one pointer,current,into the
List.
◆ We do not need pointers to the head or the tail
of the List,since they can be found by tracing
back or forth from any given node.
◆ To find any position in the doubly linked list,we
rst decide whether to move forward or backward
from the current position,and then we do a partial
traversal of the list until we reach the desired
position.
template <class List entry>
void List<List entry>,,set_position(int position) const
/* Pre,position is a valid position in the List, 0 ≤ position <
count,
Post,The current Node pointer references the Node at
position, */
{ if (current_position <= position)
for ( ; current_position != position; current_position++)
current = current->next;
else
for ( ; current_position != position; current_position--)
current = current->back;
}
◆ The cost of a doubly linked list is the extra
space required in each Node for a second link,
usually trivial in comparison to the space for the
information member entry.
Insertion into a Doubly Linked List
template <class List entry>Error code List<List entry>,,
insert(int position,const List entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n; where n is
the
number of entries in the List,the function succeeds,
Any
entry formerly at position and all later entries have
their
position numbers increased by1 and x is inserted at
position
of the List,
Else,the function fails with a diagnostic error code,*/
{ Node<List entry> *new node,*following,*preceding;
if (position == 0)
{ if (count == 0) following = NULL;
else { set_position(0); following = current; }
preceding = NULL;
}
else
{ set_position(position - 1); preceding = current;
following = preceding->next;
}
new_node = new Node<List entry>(x,preceding,following);
if (new node == NULL) return overflow;
if (preceding != NULL) preceding->next = new_node;
if (following != NULL) following->back = new_node;
current = new_node; current_position = position; count++;
return success;
}
下面将 Doubly Linked List类的声明部分给出，
实现及测试演示给大家（源代码可以复制给
大家） 。
注 文件名如下：
声明及实现,DLList.h
测试程序,exp_dlink.cpp
# include <iostream.h>
enum Error_code{ success,fail,range_error };
template <class Node_entry> // Node declaration
struct Node
{// data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node();
Node( Node_entry,Node<Node_entry> *link_back =
NULL,
Node<Node_entry> *link_next = NULL);
};
声明双向链表的结点结构
结点的数据域
其类型为模板
Node_entry
指向下一结点的指针
指向前一结点的指针
将 next和 back
置为, 空, 的
constructor1
next和 back缺省值
为, 空, (数据域及
指针均被初始化 )
的 constructor2
template <class List_entry>
Node<List_entry>::Node()
{ next = back = NULL; }
template <class List_entry> Node<List_entry>::
Node ( List_entry data,Node<List_entry>
*link_back,Node<List_entry> *link_next )
{ entry = data;
back = link_back;
next = link_next;
}
以双向链表的数据项
做为结点的数据域
Implementation
constructor1 Implementation
constructor2
template <class List_entry>
class List // doubly lined list declaration
{ public,
List(); // constructor
List(const List<List_entry> &); // copy constructor
~List() { clear(); } // destructor
List& operator=(const List<List_entry>&);
// List:overloaded assignment"="
int size() const { return count; } // Compute the length
bool full() const; // List whether isFull?
bool empty() const { return count==0; }
// List whether isEmpty?
void clear(); // to clear the List:become
empty
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x) const;
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
int find(const List_entry &x);
/* search List_entry x,return -1 if not find,
otherwise return position of x */
protected:
int count; //number of List_entry
mutable int current_position;
//int,Designation position of last operated node
mutable Node<List_entry> *current;
//pointer:point to last operated node
void set_position(int position) const;
// The auxiliary function to locate list positions
follows:
};
小结
顺序表的 特点 是,逻辑上相邻的元素, 存储位置也相邻 。 由
此可知, 线性表采用顺序存储有如下的优缺点：
其优点是：
⑴ 不需为表示元素间的逻辑关系而增加额外存储空间；
⑵ 可以方便地随机存取表中的任一结点 。
其缺点是：
⑴ 插入和删除运算不方便, 除表尾位置外, 在表的其
它位置上进行插入和删除操作都必须移动大量元素, 因此效
率较低；
⑵ 由于顺序表要求占用连续的存储单元, 必须预留存储空
间, 因此当表长变化较大时, 难以确定合适的存储规模, 若
按可能达到的最大长度留表空间, 则可能造成一部分空间长
期闲置而得不到充分利用, 若事先对表长估计不足, 则插入
操作可能使表长超过预先分配的空间而造成溢出 。
线性表的 链式 存储正是 针对 顺序存储的 缺点 而提出的。
Comparison of
ImplementationsContiguous storage is generally preferable
◆ when the entries are individually very small;
◆ when the size of the list is known when the
program is
written;
◆ when few insertions or deletions need to be
made except at the end of the list; and
◆ when random access is important.
Linked storage proves superior
◆ when the entries are large;
◆ when the size of the list is not known in advance;
and
◆ when flexibility is needed in inserting,deleting,
To choose among linked list
implementations,consider:
◆ Which of the operations will actually be
performed on the list and which of these are the
most important?
◆ Is there locality of reference? That is,if one
entry is accessed,is it likely that it will next be
accessed again?
◆ Are the entries processed in sequential order? If
so,then it may be worthwhile to maintain the last-
used position as part of the list structure.
◆ Is it necessary to move both directions through
the list? If so,then doubly linked lists may prove
6.3 STRINGS
Strings in C
◆ A string is defined as a sequence of characters.
◆ Examples,"This is a string" or "Name?",where
the double quotes are not part of the string,The
empty string is "".
◆ A string ADT is a kind of list,but the operations
are usually quite different from other lists.
◆ The first implementation of strings is found in
the C subset of C++,We call these C-strings,C-
strings reflect the strengths and weaknesses of
the C language:
◆ C-strings are widely available.
◆ C-strings are very efficient.
◆ C-strings objects are not encapsulated.
◆ C-strings are easy to misuse,with
consequences that can be disastrous.
◆ It is easy for a client to create either garbage or
aliases for C-string data,For example:
◆ Every C-string has type char *,Hence,a C-string
references an address in memory,the rst of a
contiguous set of bytes that store the characters
making up the string.
◆ The storage occupied by the string must
terminate with the special character value ‘\0’.
◆ The standard header le <cstring> (or <string.h>)
contains a library of functions that manipulate C-
strings.
◆ In C++,the output operator << is overloaded to
apply to Cstrings,so that a simple instruction cout
<< s prints the string s.
◆ In C++,it is easy to use encapsulation to embed
C-strings into safer class-based implementations
◆ The standard template library includes a safe
string implementation in the header le <string>,
This library implements a class called std,,string
that is convenient,safe,and efficient.
Standard C-String Library
char *strcpy(char *to,char *from);
Pre,The string from has been initialized.
Post,The function copies string from to
string to,including ‘\0’; it returns a pointer to
the beginning of the string to.
char *strncpy(char *to,char *from,size_t n);
Pre,The string from has been initialized.
Post,The function copies at most n
characters
from string from to string to; it returns a
pointer to the string to,If from has less than
n characters,the remaining positions are
padded with ‘\0’s.char *strcat(char *to,char *from);
Pre,The strings from and to have been
initialized.
Post,The function copies string from to the
end of string to,including ‘\0’; it returns a
pointer to the beginning of the string to.
typedef
unsigned int
size_t;
char *strncat(char *to,char *from,size_t n);
Pre,The string from and to has been
initialized.
Post,The function copies at most n
characters
from string from to string to,and terminates
to with ‘\0’;it returns a pointer to the
beginning of the string to.size_t strlen(c ar *s);
Pre,The string s has been initialized.
Post,The function returns the length of the
string s,not including the null byte ‘\0’ at the
end of the string s.
int strcmp(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function compares string s1 to
string s2; it returns <0 if s1< s2,0 if s1==s2,
or >0 if s1>s2.
int strncmp(char *s1,char *s2,size_t n);
Pre,The string s1 and s2 has been initialized.
Post,The function compares at most n
characters of string s1 to string s2; it returns
<0 if s1< s2,0 if s1==s2,or >0 if s1>s2.
char *strchr(char *s,char c);
Pre,The string s has been initialized.
Post,The function returns a pointer to the
first occurrence of the character c in the
string s,or it returns NULL if c is not present
in s.
char *strrchr(char *s,char c);
Pre,The string s has been initialized.
Post,The function returns a pointer to the
last
occurrence of the character c in the string s,
or it returns NULL if c is not present in s.
rear
Size_t strspn(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns the length of the
prefix of s1 that consists of characters that
appear in s2.
Size_t strcspn(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns the length of the
prefix of s1 that consists of characters that
do not appear in s2.
返回串 s1中包含串 s2
全部字符的初始段长度 返回串 s1中不包含串 s2
全部字符的初始段长度
Example:
#include<string.h>
#include<iostream.h>
void main()
{ char *s1="1234567890";
char *s2="747DC8";
char *s3="123DC8";
char *s4="12348";
cout<<"strspn(s1,s2)="<<strspn(s1,s2)<<endl;
cout<<"strcspn(s1,s2)="<<strcspn(s1,s2)<<endl;
cout<<"strspn(s1,s3)="<<strspn(s1,s3)<<endl;
cout<<"strcspn(s1,s3)="<<strcspn(s1,s3)<<endl;
cout<<"strspn(s1,s4)="<<strspn(s1,s4)<<endl;
cout<<"strcspn(s1,s4)="<<strcspn(s1,s4)<<endl;
}
strspn(s1,s2)=0
strcspn(s1,s2)=3
strspn(s1,s3)=3
strcspn(s1,s3)=0
strspn(s1,s4)=4
strcspn(s1,s4)=0
char *strpbrk(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns a pointer to the
first occurrence in the string s1 of any
character of the string s2,or it returns NULL if
no character of s2 appears in s1.
char *strstr(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns a pointer to the
first occurrence of the string s2 in the string
s1,or it returns NULL if the string s2 is not
present in s1.
返回指向 s2中任一字符
在 s1中第一次出现的指针 返回指向串 s1中包含
s2的指针。若 s2不在
s1中出现，返回 NULL
Safe Implementation of Strings
To create a safer string implementation,we embed
the C-string representation as a member of a class
String,Features:
◆ Include the string length as a data member in
the String class.
◆ The String class avoids the problems of aliases,
garbage creation,and uninitialized objects by
including an overloaded assignment operator,a
copy constructor,a destructor,and a constructor.
◆ Include overloaded versions of the Boolean
comparison operators <,>,<=,>=,==,!=,
◆ Include a constructor that uses a parameter of
type char * and translates from C-string objects to
String objects.
◆ Include a constructor to convert from a List of
characters to a String.
◆ Include a String method c_str( ) that converts
String objects to corresponding C-string objects.
◆ The resulting String class is a fully encapsulated
ADT,but it provides a complete interface both to
C-strings and to lists of characters.
String Class Specification
#include"SQList.h"
class String
{friend bool operator==(const String &first,const String
&second);
friend bool operator>(const String &first,const String
&second);
friend bool operator<(const String &first,const String
&second);
friend bool operator>=(const String &first,const String
&second);
friend bool operator<=(const String &first,const String
&second);
friend bool operator!=(const String &first,const String
&second);
friend ostream &operator<<(ostream& os,String &s);
//,流插入,,, 比较, 运算符是做为, 友元, 函数重载,
//,赋值, 运算符是做为成员函数重载,且有返回类型。
public,// methods of the string ADT
String( ) { length=0; }
~String( )
{ if(length>0){ delete[]entries; length=0; } }
String (const String ©); // copy constructor
String (const char * copy); // conversion from C-string
String (List<char> ©); // conversion fromList
String& operator= (const String ©);
//overloaded assignment operator
String& operator=(const char*);
// overloaded assignment operator
const char *c_str( ) const; // conversion to C-style
string
protected:
char *entries;
int length;
};
String (const String ©); // copy constructor
String (const char * copy); // conversion from C-string
String (List<char> ©); // conversion from List
String& operator= (const String ©);
//overloaded assignment operator
const char *c_str( ) const; // conversion to C-style
string
protected:
char *entries;
int length;
void setString(const char *copy);
};
各成员函数的实现代码如下：
# include<string.h>
# include<iostream.h>
# include"str.h"
ostream &operator<<(ostream& os,String &s)
//,<<“可输出包括 char*和指针在内的每一种内部数据，重载以输出
// 用户自定义类型的数据。
{ return os<<'"'<<s.c_str( )<<'"'<<" "; }
void String::setString(const char *copy)
{ length=strlen(copy);
entries=new char[length+1];
strcpy(entries,copy);
}
String::String (const char *in_string)
/* Pre,The pointer in_string references a C-string.
Post,The String is initialized by the C-stringin_string,
*/
{ setString(in_string); }
String::String (const String& copy)
{ setString(copy.entries); }
String::String (List<char> &in_list)
/* Post,The String is initialized by the character List
in_list, */
{ length = in_list.size( );
entries = new char[length+1];
for(int i=0; i<length; i++)in_list.retrieve(i,entries[i]);
entries[length] = '\0';
}
const char*String::c_str( ) const
/* Post,A pointer to a legal C-string object matching the
String
is returned,*/
{ return (const char*) entries; }
String& String::operator=(const String ©)
{ if(©!=this) // avoid self assignment
{ if(length>0) delete[] entries; // prevent memory leak
setString(copy.entries);
}
else cout<<"Attempted assignment of a String to
itself!\n";
return *this;
}
bool operator==(const String &first,const String
&second)
/* Post,Return true if the String first agrees with String
second,Else:Return false,*/
{ return strcmp(first.c_str(),second.c_str())==0; }
Samples of Further String Operations
void strcat(String &add_to,const String &add_on)
// Post,The function concatenates String add_on onto
the end of String add_to.
{ const char *cfirst = add_to.c_str( );
const char *csecond = add_on.c_str( );
char *copy = new char[strlen(cfirst)+ strlen(csecond)+1];
strcpy(copy,cfirst);
strcat(copy,csecond);
add_to = copy;
delete[] copy;
}
void strcpy(String ©,const String &original)
{ if(©!=&original) // avoid self copies
{ if(copy.length>0) delete[] copy.entries;
// prevent memory leak
int n = original.length;
copy.entries=new char[n+1];
strcpy(copy.entries,original.entries);
copy.length=n;
}
else cout<<"Attempted copies a String to itself!\n";
}
void strncpy(String ©,const String &original,
int n)
{ if(©!=&original) // avoid self copies
{ if(copy.length>0) delete[] copy.entries; //
prevent memory leak
int k = (original.length>n? n,original.length);
copy.entries=new char[k+1];
strncpy(copy.entries,original.entries,k);
copy.length=k;
}
else cout<<"Attempted copies a String to itself!\n";
}
int strstr(String &text,const String &target)
{ return KMP_Find(text,target); }
String read_in(istream &input)
// Post,Return a String read from an istream
parameter,{ List<char> temp;
int size = 0;
char c;
while((c=input.peek( )) != EOF && (c=input.get( )) !=
'\n')
temp.insert(size++,c);
String answer(temp);
return answer;
}
用 KMP模式匹配算法
在主串 text中查找
模式串 target
从 istream中读入
以‘ \n’或 EOF结尾的
字符串构成 String
对象，返回该对象
由于下一节应用实例“文本编辑” Edit中要用
到 String类，而 Editor类是继承于“双向链表”
的。因此本节 String中的个别部分需要修改，比
如：
String(List<char>&) 和 String read_in(istream
&input) 中,显然是用顺序存储的 List,Editor中要
用双向链表 List,这会引起混淆，我在 String中
将上述函数去掉了以 istream
&operator>>(istream&,String &s) 做为替代，完全
解决了 read_in问题，而 constructor
String(List<char>&)实际不需要，顺序存储的
List<char> 就是 char* 。下面将 String类的声明部
分给出。
class String
{
friend bool operator==(const String &first,const String
&second);
friend bool operator>(const String &first,const String
&second);
friend bool operator<(const String &first,const String
&second);
friend bool operator>=(const String &first,const String
&second);
friend bool operator<=(const String &first,const String
&second);
friend bool operator!=(const String &first,const String
&second);
friend ostream &operator<<(ostream&,String &s);
friend istream &operator>>(istream&,String &s);
friend void KMP_Fail(const String &pat,int *f);
// KMP算法中计算模式串 pat的失效函数
friend int KMP_Find(const String &tag,const String &pat);
// 用 KMP算法实现 Find
public,// methods of the string ADT
String( ){ length=0; }
~String( ) { if(length>0){ delete[ ]entries; length=0; } }
String(const String&); // copy constructor
String(const char*); // conversion from C-string
String &operator=(const String ©);
//overloaded assignment operator
String &operator=(const char*copy);
//overloaded assignment operator
const char *c_str( ) const; // conversion to C-style string
int size() { return length; }
int Find(const String &pat)const;
// 查找串 pat,找不到返回 -1，否则返回 pat在字符串中的位置
protected:
char *entries;
int length;
void setString(const char *copy); //auxiliary function
};
String类的实现及测试演示给大家。
6.4 Application:Text
EditorText Editor Operations
'R' Read the text file (name in command line) into
the
buffer,Any previous contents of the buffer
are lost,
At the conclusion,the current line will be the
first
line of the file.
'W' Write the contents of the buffer to an output
file,
Neither the current line nor the buffer is
changed.
'D' Delete the current line and move to the next
line.
'F' Find the first line,starting with the current line,
that contains a target string that will be
requested
from the user.
'L' Show the length in characters of the current
line
and the length in lines of the buffer.
'C' Change the string requested from the user to
a
replacement text,also requested from the
user,
working within the current line only.
'N' Next line,advance one line through the buffer.
'P' Previous line,back up one line in the buffer.
'B' Beginning,go to the
rst line of the buffer.
'E' End,go to the last line of the buffer.
'G' Go to a user-speci
ed line number in the buffer.
'S' Substitute a line typed in by the user for the
current line,The function should print out the
line
for verification and then request the new line.
'V' View the entire contents of the buffer,printed
out
to the terminal.
The Main Program
#include "Edit.h"
#include <stdlib.h>
void main(int argc,char *argv[ ])
/* Pre,Names of input and output files are given as
command-line
arguments.
Post,Reads an input file that contains lines (character
strings),
performs simple editing operations on the lines,and
writes
the edited version to the output file.
Uses,methods of class Editor */
{ if (argc != 3)
{ cout << "Usage:\n\t edit inputfile_outputfile" << endl;
命令行参数
参数个数,
参数字符串
命令行参数
个数应当是 3？
ifstream file_in(argv[1]);
if(file_in == 0)
{ cout << "Can't open input file "<<argv[1]<<endl;
exit(1);
}
ofstream file_out(argv[2]); if(file_out == 0)
{ cout << "Can't open output file " << argv[2] << endl;
exit (1);
}
Editor buffer(file_in,file_out);
while(buffer.get_command( ))
buffer.run_command( );
file_in.close(); file_out.close();
}
Declare and open
the input stream
Declare and open
the output stream
The Editor Class Specification
class Editor, public List<String>
{ public:
Editor(ifstream& file_in,ofstream& file_out);
bool get_command( );
void run_command( );
private:
ifstream infile;
ofstream outfile;
char user_command;
// auxiliary functions
Error_code next_line( );
Error_code previous_line( );
The Editor Class Specification
Error_code goto_line( );
Error_code insert_line( );
Error_code substitute_line( );
Error_code change_line( );
void read_file( );
void write_file( );
void find_string( );
};
Editor类声明、实现及运行主程序对文本
文件进行“行编辑” 的情况演示并讲解。
6.5 Linked Lists in Arrays
◆ This section shows how to implement linked
lists using only integer variables and arrays.
◆ Begin with a large workspace array and regard
the array as our allocation of unused space.
◆ Set up our own functions to keep track of which
parts of the array are unused and to link entries of
the array together in the desired order.
Static linked list
静态链表
◆ The one feature of linked lists that we must
invariably lose in this implementation method is
the dynamic allocation of storage.
◆ Applications where linked lists in arrays may
prove preferable are those where
◆ the number of entries in a list is known in
advance,
◆ the links are frequently rearranged,but
relatively few additions or deletions are made,
or
◆ the same data are sometimes best treated as
a linked list and other times as a contiguous list.See book Pg.252 Fi,6.6
按姓名序递增 按 math序递减按 CS序递减
Pg.254 Fig.6.7 available-space list
illustrated
按姓名序递增
表头指针 可用空间表头指针
Class Declaration,Linked Lists in
Arraystypedef int index
#define max_list 50
template <class List_entry>
class Node
{ public:
List_entry entry;
index next;
};
template <class List_entry>
class List
{ public:
List( );
int size( ) const;
bool full( ) const;
index type
Defined to int
Note,
next not is pointer
but index
用数组存储的链表
(静态链表 )的类声明
bool empty( ) const;
void clear( );
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x)
const;
Error_code replace(int position,const List_entry
&x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry
&x);
protected:
Node<List_entry> workspace[max_list];
index available,last_used,head;
int count;
index new_node( );
void delete_node(index n);
int current_position(index n) const;
相当于 OS内存管理
的动态分配算子
new operator
相当于动态结构的
delete operator
返回存储在
数组下标 n的数据元素
在 List表的位置号
返回 在 List表
中位置号为 position
的数据元素 在存储
数组中 的 下标
template <class List_entry>
index List<List_entry>::new_node( )
/* Post:The index of the first available Node in workspace
is returned; the data members available,last_used,and
workspace are updated as necessary,If the workspace is
already full,-1 is returned,*/
{ index new_index;
if(available != -1)
{ new_index = available;
available = workspace[available].next;
}
else if(last_used<max_list-1) new_index=++last_used;
else return -1;
workspace[new_index].next = -1;
return new_index;
}
template <class List_entry>
void List<List_entry>::delete_node(index old_index)
/* Pre,The List has a Node stored at index old_index.
Post,The List index old_index is pushed onto the linked
stack
of available space;available,last_used,and
workspace
are updated as necessary,*/
{ index previous;
if( old_index==head ) head=workspace[old_index].next;
else{ previous=set_position(current_position(old_index)-
1);
workspace[previous].next=workspace[old_index].next;
}
用数组存储的链表 (静态链表 )的类声明 (比课本
增加了复制构造、‘ =’运算符重载及根据给定
值在 List中查找等方法 )，各个方法及函数的
实现代码及与动态单链表、双向链表完全相同
的例子程序 (仅仅所包含的头文件不同 )均可以
演示给大家。
对于没有提供指针类型的高级语言，若
要采用链表结构，则可用数组存储的静态链表
实现。
虽然静态链表在存储分配上有不足之处，
但它和动态链表一样，具有插入和删除方便的
特点。
值得指出的是,即使对那些具有指针类
型的语言，静态链表也有其用武之地。特别是
当线性表的长度不变，仅需改变结点间的相对
关系时，静态链表比动态链表更加方便、高效。
6.6 Application,Generating
Permutations
Pg.261 Fig.6.8 Generating
Permutations
The section left Self-
educated.
Pointers and Pitfalls
◆ Use C++ templates to implement generic data
structures.
◆ Don't confuse contiguous lists with arrays.
◆ Choose your data structures as you design
your algorithms,and avoid making premature
decisions.
◆ Always be careful about the extreme cases and
handle them gracefully,Trace through your
algorithm to determine what happens when a data
structure is empty or full.
◆ Don't optimize your code until it works perfectly,
and then only optimize it if improvement in
efficiency is definitely required,First try a simple
your data structures,Change to a more
sophisticated implementation only if the simple
one proves too inefficient.
◆ When working with general lists,rst decide
exactly what operations are needed,and then
choose the implementation that enables those
operations to be done most easily.
◆ Study several simple examples to see whether
or not recursion should be used and how it will
work.
◆ In choosing between linked and contiguous
implementations of lists,consider the necessary
operations on the lists,Linked lists are more
flexible in regard to insertions,deletions,and
rearrangement; contiguous lists allow random
◆ Contiguous lists usually require less computer
memory,computer time,and programming effort
when the items in the list are small and the
algorithms are simple,When the list holds large
data entries,linked lists usually save space,time,
and often programming effort.
◆ Dynamic memory and pointers allow a program
to adapt automatically to a wide range of
application sizes and provide flexibility in space
allocation among different data structures,Static
memory (arrays and indices) is sometimes more
efficient for applications whose size can be
completely specified
in advance.
◆ For advice on programming with linked lists in
dynamic memory,see the guidelines in Chapter 4.
◆ Avoid sophistication for sophistication's sake,
Use a simple method if it is adequate for your
application.
◆ Don't reinvent the wheel,If a ready-made class
template or function is adequate for your
application,consider using it.
1,List Specifications
2,List Implementations
(a),Class Templates
(b),Contiguous
(c),Simply Linked
(d),Simply Linked with Position
Pointer(e),Doubly Linked
Chapter 6 LISTS AND STRINGS
3,Strings
4,Application,Text Editor
5,Linked Lists in Arrays
6,Application,
Generating Permutations
7,Pointers and Pitfalls
DEFINITION
A list of elements of type T is a finite sequence of
elements of T together with the following operations,
1,Construct the list,leaving it empty.
2,Determine whether the list is empty or not.
3,Determine whether the list is full or not.
4,Find the size of the list.
5,Clear the list to make it empty.
6,Insert an entry at a specified position of the list.
7,Remove an entry from a specified position in the
list.
8,Retrieve the entry from a specified position in the
list.
9,Replace the entry at a specified position in the list.
10,Traverse the list,performing a given operation on
6.1 List Definition
Comparison with Standard Template Library:
◆ The STL list provides only those operations
that can be implemented efficiently in a List
implementation known as doubly linked,which we
shall study shortly.
◆ The STL list does not allow random access to an
arbitrary list position.
◆ The STL vector,does provide some random
access to a sequence of data values,but not all
the other capabilities we shall develop for a List.
◆ In this way,our study of the List ADT provides
an introduction to both the STL classes list and
List,,List( );
Post,The List has been created and is
initialized
to be empty.
Method Specifications
void List,,clear();
Post,All List entries have been removed;
the List is empty.
bool List,,empty() const;
Post,The function returns true or false
according to
whether the List is empty or not.
bool List,,full() const;
Post,The function returns true or false
according to
whether the List is full or not.
int List,,size() const;
Post,The function returns the number of
entries in the List.
Position Number in a List
◆ To find an entry in a list,we use an integer that
gives its position within the list.
◆ We shall number the positions in a list so that
the first entry in the list has position 0,the second
position 1,and so on.
◆ Locating an entry of a list by its position is
superficially like indexing an array,but there are
important differences,If we insert an entry at a
particular position,then the position numbers of
all later entries increase by 1,If we remove an
entry,then the positions of all following entries
decrease by 1.
◆ The position number for a list is defined
without regard to the implementation,For a
contiguous list,implemented in an array,the
position will indeed be the index of the entry
within the array,But we will also use the position
to find an entry within linked implementations of
a list,where no indices or
arrays are used at all.
Error_code List::insert(int position,const
List_entry &x);
Post,If the List is not full and 0 position
n,
where n is the number of entries in
the
List,the function succeeds:Any
entry
formerly at position and all later
entries have their position
numbers
increased by 1,
and x is inserted at position in the
List.
Error_code List,,remove ( int position,
List_entry &x );
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The
entry at position is removed from the List,
and
all later entries have their position
numbers
decreased by 1,The parameter x records
a copy
of the entry formerly at position.
Else,The function fails with a diagnostic
Error_code List,,retrieve(int position,
List_entry &x)
const;
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The
entry at position is copied to x; all List
entries
remain unchanged.
Else,The function fails with a diagnostic
error code.
Error_code List,,replace(int position,
const List_entry
&x);
Post,If 0 ≤ position<n,where n is the number of
entries in the List,the function succeeds,
The entry at position is replaced by x; all
other
entries remain unchanged.
Else,The function fails with a diagnostic
error code.void List::traverse(void (*visit)(List entry
&));
Post,The action specified by function
*visit has
been performed on every entry of the
List,
6.2 Implementations of
ListsClass Templates
◆ A C++ template construction allows us to write
code,usually code to implement a class,that uses
objects of an arbitrary,generic type.
◆ In template code we utilize a parameter enclosed in
angle
brackets< > to denote the generic type.
◆ Later,when a client uses our code,the client can
substitute an actual type for the template parameter,
The client can thus obtain several actual pieces of
code from our template,using different actual types in
place of the template parameter.
?Example,We shall implement a template
class List that depends on one generic type
parameter,A client can then use our template to
declare several lists with different types of
entries with declarations of the following form:
List<int> rst list;
List<char> second list;
?Templates provide a new mechanism for
creating generic data structures,one that
allows many different specializations of a given
data structure template in a single application.
?The added generality that we get by using
templates comes at the price of slightly more
complicated class specifications and
implementations.
Contiguous(storage) Implementation
连续 /顺序 (存储 )的
One-dimensional
arrays
template <class List_entry> class List
{ public:
// methods of the List ADT
List( );
int size( ) const;
bool full( ) const;
bool empty( ) const;
void clear( );
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
求顺序表的长度判顺序表是否已 "满 "
判顺序表是否为, 空 "清空顺序表
遍历顺序表
查找表中第 position
个元素存入 x将表中第 position个元素值修改为 x删除表中第 position
个元素，其值存入 x
将 x插入表中
令其成为第
position个元素
protected:
// data members for a contiguous list implementation
int count;
List_entry entry[max_list];
};
template <class List_entry>
int List<List_entry>::size( ) const
// Post,The function returns the number of entries in the
List,
{ return count; }
template <class List_entry> Error_code List<List_entry>
::insert(int position,const List_entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n; where n
is the number of entries in the List,the function succeeds,
Any entry formerly at position and all later entries have
their position numbers increased by 1 and x is inserted at
position of the List,
Else,The function fails with a diagnostic Error_code,*/
{ if (full( )) return overflow;
if (position < 0 || position > count)
return range_error;
for (int i=count-1; i >= position; i--) entry[i +1] = entry[i];
entry[position] = x;
count++;
return success;
}
template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/* Post,The action specified by function(*visit) has been
performed on every entry of the List,beginning at
position 0 and doing each in turn,*/
{
for (int i=0; i<count; i++) (*visit)(entry[i]);
}
Performance of Methods
In processing a contiguous list with n entries:
? insert and remove operate in time
approximately proportional to n,
? List,clear,empty,full,size,replace,and
retrieve operate in constant time.
Please follow the
Error_code insert(int position,const List_entry &x)
write by yourselves:
Error_code retrieve(int position,List_entry &x);
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Application,Contiguous List
设顺序表 la和 lb分别表示整数集合 A和 B，求,A=A∪B 。
算法思路, 集合中的元素是无重复的，可将 Lb表中的
元素从表尾起逐个删除，并在 La表查找被删元素 b，若
找不到，则将元素 b插入 La表，否则不必插入，完成后
集合 B为空。
在 List类中增加一个成员函数 (方法 ),Find
template <class List_entry>
int List<List_entry>::Find(const List_entry &x)
// 查找值为 x的元素,返回 -1没找到,否则为 x在表中的位置
{ int i=0;
while( i<count && entry[i]!= x )i++;
if(i<count) return i; else return -1;
}
下面给出：产生若干互不相等的随机整数 (集合元素 )
插入表的函数,CrtSetList ；进行集合“并”运算的
函数,SetUnion及主函数 main()的源代码。
在 class List_entry中
应当有定义
#include <stdlib.h>
#include <time.h>
#include "SQList.h"
void CrtSetList(List<int>&,int); // 产生集合元素插入表的原型声明
void SetUnion(List<int>&,List<int>&); // 集合 "并 "运算的原型声
明
void visit(int &i);
void main()
{ // 声明 List对象 La,Lb,类参数 List_entry用 <int>实例化
List<int> La,Lb; // La,Lb代表集合
int s1,s2; // s1,s2是存放 La,Lb大小的变量
time_t t;
srand((unsigned)time(&t)); // 初始化随时间变化的随机数种子
cout<<"Please input Size of SetA && SetB =? =? (<=15)";
cin>>s1>>s2; // 输入集合 A,B元素数 <=15，以保证 "并 "后 La的元素数
<=30
cout<<"\nSet A = { "; // 输出集合 A的名称
CrtSetList(La,s1); // 创建集合 A并输出集合元素
cout<<"}\nSet B = { "; // 输出集合 B的名称
CrtSetList(Lb,s2);
SetUnion(La,Lb); // 求集合 A与集合 B的 "并 "
cout<<"}\n\n A Union B = { ";
La.traverse(visit); cout<<" }\n";
}
void CrtSetList(List<int>&L,int n)
// 为集合产生 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.insert(L.size(),x); // 插入表尾
cout<<x<<" "; // 输出 x ( 集合元素边产生边输出 )
}
}
void SetUnion(List<int>&La,List<int>&Lb)
// 将 La表和 Lb表所表示的集合做 "并 "，存入 La表,Lb表被清空。
{int i,k,b;
for(i=Lb.size(); i>0; i--) //从 Lb表中逐次删除素尾元素 (不必移动元素 )
{ Lb.remove(i-1,b); //调用删除算法，被删元素存入 b
k=La.Find(b); // 在 La表中查找 b
if(k==-1) // La表中找不到元素 b
La.insert(La.size(),b); // 插入至 la表尾
} //end_for
}
void visit(int &i)
{ cout<<i<<' '; }
Simply Linked
Implementationtemplate <class Node_entry> struct Node // Node
declaration:
{ Node_entry entry;
Node<Node_entry> *next;
Node( ); // constructors
Node(Node_entry,Node<Node_entry> *link=NULL);
// constructors
};
template <class List_entry>class List // List
declaration:
{ public:
// Specifications for the methods of the list ADT go
here.
~List( );
List(const List<List_entry> ©);
void operator=(const List<List_entry> ©);
protected:
// Data members for the linked list implementation now
follow.
int count;
Node<List_entry> *head;
// The following auxiliary function is used to locate list
positions
Node<List_entry> *set_position(int position) const;
};
Actions on a Linked List
Finding a List Position
◆ Function set position takes an integer parameter
position and returns a pointer to the corresponding
node of the list.
◆ Declare the visibility of set position as protected,
since set position returns a pointer to,and
therefore gives access to,a Node in the List,To
maintain an encapsulated data structure,we must
restrict the visibility of set position,Protected
visibility ensures that it is only available as a tool
for constructing other methods of the List.
◆ To construct set position,we start at the
beginning of the List and traverse it until we reach
the desired node:
template <class List_entry> Node<List_entry>
*List<List_entry>::set_position(int position) const
/* Pre,position is a valid position in the List ;0 ≤
position<count,
Post,Returns a pointer to the Node in position, */
{ Node<List_entry> *q = head;
for (int i=0; i<position; i++) q=q->next;
return q;
}
◆ If all nodes are equally likely,then,on average,
the set position function must move halfway
through the List to find a given position,Hence,
on average,its time requirement is approximately
proportional to n,the size of the List.
template <class List_entry> Error_code List<List_entry>,,
insert(int position,const List_entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n,where n
is the number of entries in the List,the function succeeds,
Any entry formerly at position and all later entries have
their position numbers increased by 1,and x is inserted at
position of the List.
Else,The function fails with a diagnostic error_code,*/
{ if (position < 0 || position > count) return range_error;
Node<List_entry> *new node,*previous,*following;
if (position > 0)
{ previous = set position(position, 1);
following = previous->next;
}
else following = head;
Insertion Method
new_node = new Node<List_entry>(x,following);
if(new_node==NULL)return overflow;
if (position==0) head = new_node;
else previous->next = new_node;
count++;
return success;
}
Insert to
Firsr entry
为了避免插入位置不同带来的处理方法的不一致，
可以在第一个元素 (“首元结点, )前，虚设一个结点称
之为, 头结点, ；这样, 头指针, 指向, 头结点,,
如下图所示：
In processing a linked List with n entries:
? clear,insert,remove,retrieve,and replace
require time approximately proportional to n.
? List,empty,full,and size operate in constant
time.
Variation,Keeping the Current Position
◆ Suppose an application processes list entries
in order or refers to the same entry several times
before processing another entry.
◆ Remember the last-used position in the list and,
if the next operation refers to the same or a later
position,start tracing through the list from this
last-used position.
◆ Note that this will not speed up every
application using lists.
◆ The method retrieve is defined as const,but its
implementation will need to alter the last-used
position of a List,To enable this,we use the
mutable qualifier,Mutable data members of a class
can be changed,even by constant methods.
template <class List_entry>class List
{public:
// Add specifications for the methods of the list ADT.
// Add methods to replace the compiler-generated
defaults.
protected:
// Data members for the linked-list implementation with
// current position follow,
◆ All the new class members have protected
visibility,so,from the perspective of a client,the
class looks exactly like the earlier implementation.
◆ The current position is now a member of the
class List,so there is no longer a need for set
position to return a pointer; instead,the function
simply resets the pointer current directly within
the List.
int count;
mutable int current position;
Node<List_entry> *head;
mutable Node<List_entry> *current;
// Auxiliary function to locate list positions follows:
void set_position(int position) const;
};
template <class List_entry> void List<List_entry>,,
set_position(int position) const
/* Pre,position is a valid position in the List, 0<=position <
count,
Post,The current Node pointer references the Node at
position, */
{ if (position < current_position) // must start over at head
of list
{ current_position = 0; current = head; }
for (; current_position != position; current_position++)
current = current->next;
}
◆ For repeated references to the same position,
neither the body of the if statement nor the body
of the for statement will be executed,and hence
the function will take almost no time.
◆ If we move forward only one position,the body
of the for statement will be executed only once,
so again the function will be very fast.
◆ If it is necessary to move backwards through
the List,then the function operates in almost the
same way as the version of set position used in
the previous implementation.
下面将 Simply (single) Linked类的声明部分
给出，实现及测试演示给大家（源代码可以
复制给大家） 。
#include <iostream.h>
enum Error_code{ success,fail,range_error };
template <class Node_entry> struct Node // Node
declaration
{ Node_entry entry;
Node<Node_entry> *next;
Node( ){ next=NULL; }
Node(Node_entry data,Node<Node_entry> *link=NULL)
{ entry=data; next=link; }
};
template <class List_entry>
class List // Single lined list declaration
{ public:
List(){ count=0; head = NULL; } // constructor
List(const List<List_entry> &); // copy constructor
~List(); // destructor
List& operator=(const List<List_entry>&);
// List:overloaded assignment"="
bool empty() const // Judge whether isEmpty?
{ return count==0; }
bool full()const; // Judge whether isFull?
int size()const // Compute the length
{ return count; }
void clear(); // to clear the List,become
empty
Error_code retrieve(int position,List_entry &x)const;
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
int find(const List_entry &x);
/* search List entry x,return -1 if not find,
otherwise return position of x */
void traverse(void (*visit)(List_entry &));
注 Simply (single) Linked类的文件名如下：
声明及实现,SLList.h
测试程序,exp_slink.cpp
Doubly Linked Lists
protected:
Node<List_entry> *head; //pointer,point to first
node
int count; //number of List_entry
Node<List_entry> *set_position(int position) const;
};
Node definition:
template <class Node_entry>
struct Node
{ // data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node( );
Node(Node_entry,Node<Node_entry> *link_back = NULL,
Node<Node_entry> *link_next = NULL);
};
List definition:
template <class List_entry> class List
{ public:
// Add specifications for methods of the list ADT.
// Add methods to replace compiler generated
defaults.
protected:
// Data members for the doubly-linked list implementation
follow:
int count;
mutable int current_position;
mutable Node<List_entry> *current;
// The auxiliary function to locate list positions
follows:
void set_position(int position) const;
◆ We can move either direction through the List
while keeping only one pointer,current,into the
List.
◆ We do not need pointers to the head or the tail
of the List,since they can be found by tracing
back or forth from any given node.
◆ To find any position in the doubly linked list,we
rst decide whether to move forward or backward
from the current position,and then we do a partial
traversal of the list until we reach the desired
position.
template <class List entry>
void List<List entry>,,set_position(int position) const
/* Pre,position is a valid position in the List, 0 ≤ position <
count,
Post,The current Node pointer references the Node at
position, */
{ if (current_position <= position)
for ( ; current_position != position; current_position++)
current = current->next;
else
for ( ; current_position != position; current_position--)
current = current->back;
}
◆ The cost of a doubly linked list is the extra
space required in each Node for a second link,
usually trivial in comparison to the space for the
information member entry.
Insertion into a Doubly Linked List
template <class List entry>Error code List<List entry>,,
insert(int position,const List entry &x)
/* Post,If the List is not full and 0 ≤ position ≤ n; where n is
the
number of entries in the List,the function succeeds,
Any
entry formerly at position and all later entries have
their
position numbers increased by1 and x is inserted at
position
of the List,
Else,the function fails with a diagnostic error code,*/
{ Node<List entry> *new node,*following,*preceding;
if (position == 0)
{ if (count == 0) following = NULL;
else { set_position(0); following = current; }
preceding = NULL;
}
else
{ set_position(position - 1); preceding = current;
following = preceding->next;
}
new_node = new Node<List entry>(x,preceding,following);
if (new node == NULL) return overflow;
if (preceding != NULL) preceding->next = new_node;
if (following != NULL) following->back = new_node;
current = new_node; current_position = position; count++;
return success;
}
下面将 Doubly Linked List类的声明部分给出，
实现及测试演示给大家（源代码可以复制给
大家） 。
注 文件名如下：
声明及实现,DLList.h
测试程序,exp_dlink.cpp
# include <iostream.h>
enum Error_code{ success,fail,range_error };
template <class Node_entry> // Node declaration
struct Node
{// data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node();
Node( Node_entry,Node<Node_entry> *link_back =
NULL,
Node<Node_entry> *link_next = NULL);
};
声明双向链表的结点结构
结点的数据域
其类型为模板
Node_entry
指向下一结点的指针
指向前一结点的指针
将 next和 back
置为, 空, 的
constructor1
next和 back缺省值
为, 空, (数据域及
指针均被初始化 )
的 constructor2
template <class List_entry>
Node<List_entry>::Node()
{ next = back = NULL; }
template <class List_entry> Node<List_entry>::
Node ( List_entry data,Node<List_entry>
*link_back,Node<List_entry> *link_next )
{ entry = data;
back = link_back;
next = link_next;
}
以双向链表的数据项
做为结点的数据域
Implementation
constructor1 Implementation
constructor2
template <class List_entry>
class List // doubly lined list declaration
{ public,
List(); // constructor
List(const List<List_entry> &); // copy constructor
~List() { clear(); } // destructor
List& operator=(const List<List_entry>&);
// List:overloaded assignment"="
int size() const { return count; } // Compute the length
bool full() const; // List whether isFull?
bool empty() const { return count==0; }
// List whether isEmpty?
void clear(); // to clear the List:become
empty
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x) const;
Error_code replace(int position,const List_entry &x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry &x);
int find(const List_entry &x);
/* search List_entry x,return -1 if not find,
otherwise return position of x */
protected:
int count; //number of List_entry
mutable int current_position;
//int,Designation position of last operated node
mutable Node<List_entry> *current;
//pointer:point to last operated node
void set_position(int position) const;
// The auxiliary function to locate list positions
follows:
};
小结
顺序表的 特点 是,逻辑上相邻的元素, 存储位置也相邻 。 由
此可知, 线性表采用顺序存储有如下的优缺点：
其优点是：
⑴ 不需为表示元素间的逻辑关系而增加额外存储空间；
⑵ 可以方便地随机存取表中的任一结点 。
其缺点是：
⑴ 插入和删除运算不方便, 除表尾位置外, 在表的其
它位置上进行插入和删除操作都必须移动大量元素, 因此效
率较低；
⑵ 由于顺序表要求占用连续的存储单元, 必须预留存储空
间, 因此当表长变化较大时, 难以确定合适的存储规模, 若
按可能达到的最大长度留表空间, 则可能造成一部分空间长
期闲置而得不到充分利用, 若事先对表长估计不足, 则插入
操作可能使表长超过预先分配的空间而造成溢出 。
线性表的 链式 存储正是 针对 顺序存储的 缺点 而提出的。
Comparison of
ImplementationsContiguous storage is generally preferable
◆ when the entries are individually very small;
◆ when the size of the list is known when the
program is
written;
◆ when few insertions or deletions need to be
made except at the end of the list; and
◆ when random access is important.
Linked storage proves superior
◆ when the entries are large;
◆ when the size of the list is not known in advance;
and
◆ when flexibility is needed in inserting,deleting,
To choose among linked list
implementations,consider:
◆ Which of the operations will actually be
performed on the list and which of these are the
most important?
◆ Is there locality of reference? That is,if one
entry is accessed,is it likely that it will next be
accessed again?
◆ Are the entries processed in sequential order? If
so,then it may be worthwhile to maintain the last-
used position as part of the list structure.
◆ Is it necessary to move both directions through
the list? If so,then doubly linked lists may prove
6.3 STRINGS
Strings in C
◆ A string is defined as a sequence of characters.
◆ Examples,"This is a string" or "Name?",where
the double quotes are not part of the string,The
empty string is "".
◆ A string ADT is a kind of list,but the operations
are usually quite different from other lists.
◆ The first implementation of strings is found in
the C subset of C++,We call these C-strings,C-
strings reflect the strengths and weaknesses of
the C language:
◆ C-strings are widely available.
◆ C-strings are very efficient.
◆ C-strings objects are not encapsulated.
◆ C-strings are easy to misuse,with
consequences that can be disastrous.
◆ It is easy for a client to create either garbage or
aliases for C-string data,For example:
◆ Every C-string has type char *,Hence,a C-string
references an address in memory,the rst of a
contiguous set of bytes that store the characters
making up the string.
◆ The storage occupied by the string must
terminate with the special character value ‘\0’.
◆ The standard header le <cstring> (or <string.h>)
contains a library of functions that manipulate C-
strings.
◆ In C++,the output operator << is overloaded to
apply to Cstrings,so that a simple instruction cout
<< s prints the string s.
◆ In C++,it is easy to use encapsulation to embed
C-strings into safer class-based implementations
◆ The standard template library includes a safe
string implementation in the header le <string>,
This library implements a class called std,,string
that is convenient,safe,and efficient.
Standard C-String Library
char *strcpy(char *to,char *from);
Pre,The string from has been initialized.
Post,The function copies string from to
string to,including ‘\0’; it returns a pointer to
the beginning of the string to.
char *strncpy(char *to,char *from,size_t n);
Pre,The string from has been initialized.
Post,The function copies at most n
characters
from string from to string to; it returns a
pointer to the string to,If from has less than
n characters,the remaining positions are
padded with ‘\0’s.char *strcat(char *to,char *from);
Pre,The strings from and to have been
initialized.
Post,The function copies string from to the
end of string to,including ‘\0’; it returns a
pointer to the beginning of the string to.
typedef
unsigned int
size_t;
char *strncat(char *to,char *from,size_t n);
Pre,The string from and to has been
initialized.
Post,The function copies at most n
characters
from string from to string to,and terminates
to with ‘\0’;it returns a pointer to the
beginning of the string to.size_t strlen(c ar *s);
Pre,The string s has been initialized.
Post,The function returns the length of the
string s,not including the null byte ‘\0’ at the
end of the string s.
int strcmp(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function compares string s1 to
string s2; it returns <0 if s1< s2,0 if s1==s2,
or >0 if s1>s2.
int strncmp(char *s1,char *s2,size_t n);
Pre,The string s1 and s2 has been initialized.
Post,The function compares at most n
characters of string s1 to string s2; it returns
<0 if s1< s2,0 if s1==s2,or >0 if s1>s2.
char *strchr(char *s,char c);
Pre,The string s has been initialized.
Post,The function returns a pointer to the
first occurrence of the character c in the
string s,or it returns NULL if c is not present
in s.
char *strrchr(char *s,char c);
Pre,The string s has been initialized.
Post,The function returns a pointer to the
last
occurrence of the character c in the string s,
or it returns NULL if c is not present in s.
rear
Size_t strspn(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns the length of the
prefix of s1 that consists of characters that
appear in s2.
Size_t strcspn(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns the length of the
prefix of s1 that consists of characters that
do not appear in s2.
返回串 s1中包含串 s2
全部字符的初始段长度 返回串 s1中不包含串 s2
全部字符的初始段长度
Example:
#include<string.h>
#include<iostream.h>
void main()
{ char *s1="1234567890";
char *s2="747DC8";
char *s3="123DC8";
char *s4="12348";
cout<<"strspn(s1,s2)="<<strspn(s1,s2)<<endl;
cout<<"strcspn(s1,s2)="<<strcspn(s1,s2)<<endl;
cout<<"strspn(s1,s3)="<<strspn(s1,s3)<<endl;
cout<<"strcspn(s1,s3)="<<strcspn(s1,s3)<<endl;
cout<<"strspn(s1,s4)="<<strspn(s1,s4)<<endl;
cout<<"strcspn(s1,s4)="<<strcspn(s1,s4)<<endl;
}
strspn(s1,s2)=0
strcspn(s1,s2)=3
strspn(s1,s3)=3
strcspn(s1,s3)=0
strspn(s1,s4)=4
strcspn(s1,s4)=0
char *strpbrk(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns a pointer to the
first occurrence in the string s1 of any
character of the string s2,or it returns NULL if
no character of s2 appears in s1.
char *strstr(char *s1,char *s2);
Pre,The string s1 and s2 has been initialized.
Post,The function returns a pointer to the
first occurrence of the string s2 in the string
s1,or it returns NULL if the string s2 is not
present in s1.
返回指向 s2中任一字符
在 s1中第一次出现的指针 返回指向串 s1中包含
s2的指针。若 s2不在
s1中出现，返回 NULL
Safe Implementation of Strings
To create a safer string implementation,we embed
the C-string representation as a member of a class
String,Features:
◆ Include the string length as a data member in
the String class.
◆ The String class avoids the problems of aliases,
garbage creation,and uninitialized objects by
including an overloaded assignment operator,a
copy constructor,a destructor,and a constructor.
◆ Include overloaded versions of the Boolean
comparison operators <,>,<=,>=,==,!=,
◆ Include a constructor that uses a parameter of
type char * and translates from C-string objects to
String objects.
◆ Include a constructor to convert from a List of
characters to a String.
◆ Include a String method c_str( ) that converts
String objects to corresponding C-string objects.
◆ The resulting String class is a fully encapsulated
ADT,but it provides a complete interface both to
C-strings and to lists of characters.
String Class Specification
#include"SQList.h"
class String
{friend bool operator==(const String &first,const String
&second);
friend bool operator>(const String &first,const String
&second);
friend bool operator<(const String &first,const String
&second);
friend bool operator>=(const String &first,const String
&second);
friend bool operator<=(const String &first,const String
&second);
friend bool operator!=(const String &first,const String
&second);
friend ostream &operator<<(ostream& os,String &s);
//,流插入,,, 比较, 运算符是做为, 友元, 函数重载,
//,赋值, 运算符是做为成员函数重载,且有返回类型。
public,// methods of the string ADT
String( ) { length=0; }
~String( )
{ if(length>0){ delete[]entries; length=0; } }
String (const String ©); // copy constructor
String (const char * copy); // conversion from C-string
String (List<char> ©); // conversion fromList
String& operator= (const String ©);
//overloaded assignment operator
String& operator=(const char*);
// overloaded assignment operator
const char *c_str( ) const; // conversion to C-style
string
protected:
char *entries;
int length;
};
String (const String ©); // copy constructor
String (const char * copy); // conversion from C-string
String (List<char> ©); // conversion from List
String& operator= (const String ©);
//overloaded assignment operator
const char *c_str( ) const; // conversion to C-style
string
protected:
char *entries;
int length;
void setString(const char *copy);
};
各成员函数的实现代码如下：
# include<string.h>
# include<iostream.h>
# include"str.h"
ostream &operator<<(ostream& os,String &s)
//,<<“可输出包括 char*和指针在内的每一种内部数据，重载以输出
// 用户自定义类型的数据。
{ return os<<'"'<<s.c_str( )<<'"'<<" "; }
void String::setString(const char *copy)
{ length=strlen(copy);
entries=new char[length+1];
strcpy(entries,copy);
}
String::String (const char *in_string)
/* Pre,The pointer in_string references a C-string.
Post,The String is initialized by the C-stringin_string,
*/
{ setString(in_string); }
String::String (const String& copy)
{ setString(copy.entries); }
String::String (List<char> &in_list)
/* Post,The String is initialized by the character List
in_list, */
{ length = in_list.size( );
entries = new char[length+1];
for(int i=0; i<length; i++)in_list.retrieve(i,entries[i]);
entries[length] = '\0';
}
const char*String::c_str( ) const
/* Post,A pointer to a legal C-string object matching the
String
is returned,*/
{ return (const char*) entries; }
String& String::operator=(const String ©)
{ if(©!=this) // avoid self assignment
{ if(length>0) delete[] entries; // prevent memory leak
setString(copy.entries);
}
else cout<<"Attempted assignment of a String to
itself!\n";
return *this;
}
bool operator==(const String &first,const String
&second)
/* Post,Return true if the String first agrees with String
second,Else:Return false,*/
{ return strcmp(first.c_str(),second.c_str())==0; }
Samples of Further String Operations
void strcat(String &add_to,const String &add_on)
// Post,The function concatenates String add_on onto
the end of String add_to.
{ const char *cfirst = add_to.c_str( );
const char *csecond = add_on.c_str( );
char *copy = new char[strlen(cfirst)+ strlen(csecond)+1];
strcpy(copy,cfirst);
strcat(copy,csecond);
add_to = copy;
delete[] copy;
}
void strcpy(String ©,const String &original)
{ if(©!=&original) // avoid self copies
{ if(copy.length>0) delete[] copy.entries;
// prevent memory leak
int n = original.length;
copy.entries=new char[n+1];
strcpy(copy.entries,original.entries);
copy.length=n;
}
else cout<<"Attempted copies a String to itself!\n";
}
void strncpy(String ©,const String &original,
int n)
{ if(©!=&original) // avoid self copies
{ if(copy.length>0) delete[] copy.entries; //
prevent memory leak
int k = (original.length>n? n,original.length);
copy.entries=new char[k+1];
strncpy(copy.entries,original.entries,k);
copy.length=k;
}
else cout<<"Attempted copies a String to itself!\n";
}
int strstr(String &text,const String &target)
{ return KMP_Find(text,target); }
String read_in(istream &input)
// Post,Return a String read from an istream
parameter,{ List<char> temp;
int size = 0;
char c;
while((c=input.peek( )) != EOF && (c=input.get( )) !=
'\n')
temp.insert(size++,c);
String answer(temp);
return answer;
}
用 KMP模式匹配算法
在主串 text中查找
模式串 target
从 istream中读入
以‘ \n’或 EOF结尾的
字符串构成 String
对象，返回该对象
由于下一节应用实例“文本编辑” Edit中要用
到 String类，而 Editor类是继承于“双向链表”
的。因此本节 String中的个别部分需要修改，比
如：
String(List<char>&) 和 String read_in(istream
&input) 中,显然是用顺序存储的 List,Editor中要
用双向链表 List,这会引起混淆，我在 String中
将上述函数去掉了以 istream
&operator>>(istream&,String &s) 做为替代，完全
解决了 read_in问题，而 constructor
String(List<char>&)实际不需要，顺序存储的
List<char> 就是 char* 。下面将 String类的声明部
分给出。
class String
{
friend bool operator==(const String &first,const String
&second);
friend bool operator>(const String &first,const String
&second);
friend bool operator<(const String &first,const String
&second);
friend bool operator>=(const String &first,const String
&second);
friend bool operator<=(const String &first,const String
&second);
friend bool operator!=(const String &first,const String
&second);
friend ostream &operator<<(ostream&,String &s);
friend istream &operator>>(istream&,String &s);
friend void KMP_Fail(const String &pat,int *f);
// KMP算法中计算模式串 pat的失效函数
friend int KMP_Find(const String &tag,const String &pat);
// 用 KMP算法实现 Find
public,// methods of the string ADT
String( ){ length=0; }
~String( ) { if(length>0){ delete[ ]entries; length=0; } }
String(const String&); // copy constructor
String(const char*); // conversion from C-string
String &operator=(const String ©);
//overloaded assignment operator
String &operator=(const char*copy);
//overloaded assignment operator
const char *c_str( ) const; // conversion to C-style string
int size() { return length; }
int Find(const String &pat)const;
// 查找串 pat,找不到返回 -1，否则返回 pat在字符串中的位置
protected:
char *entries;
int length;
void setString(const char *copy); //auxiliary function
};
String类的实现及测试演示给大家。
6.4 Application:Text
EditorText Editor Operations
'R' Read the text file (name in command line) into
the
buffer,Any previous contents of the buffer
are lost,
At the conclusion,the current line will be the
first
line of the file.
'W' Write the contents of the buffer to an output
file,
Neither the current line nor the buffer is
changed.
'D' Delete the current line and move to the next
line.
'F' Find the first line,starting with the current line,
that contains a target string that will be
requested
from the user.
'L' Show the length in characters of the current
line
and the length in lines of the buffer.
'C' Change the string requested from the user to
a
replacement text,also requested from the
user,
working within the current line only.
'N' Next line,advance one line through the buffer.
'P' Previous line,back up one line in the buffer.
'B' Beginning,go to the
rst line of the buffer.
'E' End,go to the last line of the buffer.
'G' Go to a user-speci
ed line number in the buffer.
'S' Substitute a line typed in by the user for the
current line,The function should print out the
line
for verification and then request the new line.
'V' View the entire contents of the buffer,printed
out
to the terminal.
The Main Program
#include "Edit.h"
#include <stdlib.h>
void main(int argc,char *argv[ ])
/* Pre,Names of input and output files are given as
command-line
arguments.
Post,Reads an input file that contains lines (character
strings),
performs simple editing operations on the lines,and
writes
the edited version to the output file.
Uses,methods of class Editor */
{ if (argc != 3)
{ cout << "Usage:\n\t edit inputfile_outputfile" << endl;
命令行参数
参数个数,
参数字符串
命令行参数
个数应当是 3？
ifstream file_in(argv[1]);
if(file_in == 0)
{ cout << "Can't open input file "<<argv[1]<<endl;
exit(1);
}
ofstream file_out(argv[2]); if(file_out == 0)
{ cout << "Can't open output file " << argv[2] << endl;
exit (1);
}
Editor buffer(file_in,file_out);
while(buffer.get_command( ))
buffer.run_command( );
file_in.close(); file_out.close();
}
Declare and open
the input stream
Declare and open
the output stream
The Editor Class Specification
class Editor, public List<String>
{ public:
Editor(ifstream& file_in,ofstream& file_out);
bool get_command( );
void run_command( );
private:
ifstream infile;
ofstream outfile;
char user_command;
// auxiliary functions
Error_code next_line( );
Error_code previous_line( );
The Editor Class Specification
Error_code goto_line( );
Error_code insert_line( );
Error_code substitute_line( );
Error_code change_line( );
void read_file( );
void write_file( );
void find_string( );
};
Editor类声明、实现及运行主程序对文本
文件进行“行编辑” 的情况演示并讲解。
6.5 Linked Lists in Arrays
◆ This section shows how to implement linked
lists using only integer variables and arrays.
◆ Begin with a large workspace array and regard
the array as our allocation of unused space.
◆ Set up our own functions to keep track of which
parts of the array are unused and to link entries of
the array together in the desired order.
Static linked list
静态链表
◆ The one feature of linked lists that we must
invariably lose in this implementation method is
the dynamic allocation of storage.
◆ Applications where linked lists in arrays may
prove preferable are those where
◆ the number of entries in a list is known in
advance,
◆ the links are frequently rearranged,but
relatively few additions or deletions are made,
or
◆ the same data are sometimes best treated as
a linked list and other times as a contiguous list.See book Pg.252 Fi,6.6
按姓名序递增 按 math序递减按 CS序递减
Pg.254 Fig.6.7 available-space list
illustrated
按姓名序递增
表头指针 可用空间表头指针
Class Declaration,Linked Lists in
Arraystypedef int index
#define max_list 50
template <class List_entry>
class Node
{ public:
List_entry entry;
index next;
};
template <class List_entry>
class List
{ public:
List( );
int size( ) const;
bool full( ) const;
index type
Defined to int
Note,
next not is pointer
but index
用数组存储的链表
(静态链表 )的类声明
bool empty( ) const;
void clear( );
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position,List_entry &x)
const;
Error_code replace(int position,const List_entry
&x);
Error_code remove(int position,List_entry &x);
Error_code insert(int position,const List_entry
&x);
protected:
Node<List_entry> workspace[max_list];
index available,last_used,head;
int count;
index new_node( );
void delete_node(index n);
int current_position(index n) const;
相当于 OS内存管理
的动态分配算子
new operator
相当于动态结构的
delete operator
返回存储在
数组下标 n的数据元素
在 List表的位置号
返回 在 List表
中位置号为 position
的数据元素 在存储
数组中 的 下标
template <class List_entry>
index List<List_entry>::new_node( )
/* Post:The index of the first available Node in workspace
is returned; the data members available,last_used,and
workspace are updated as necessary,If the workspace is
already full,-1 is returned,*/
{ index new_index;
if(available != -1)
{ new_index = available;
available = workspace[available].next;
}
else if(last_used<max_list-1) new_index=++last_used;
else return -1;
workspace[new_index].next = -1;
return new_index;
}
template <class List_entry>
void List<List_entry>::delete_node(index old_index)
/* Pre,The List has a Node stored at index old_index.
Post,The List index old_index is pushed onto the linked
stack
of available space;available,last_used,and
workspace
are updated as necessary,*/
{ index previous;
if( old_index==head ) head=workspace[old_index].next;
else{ previous=set_position(current_position(old_index)-
1);
workspace[previous].next=workspace[old_index].next;
}
用数组存储的链表 (静态链表 )的类声明 (比课本
增加了复制构造、‘ =’运算符重载及根据给定
值在 List中查找等方法 )，各个方法及函数的
实现代码及与动态单链表、双向链表完全相同
的例子程序 (仅仅所包含的头文件不同 )均可以
演示给大家。
对于没有提供指针类型的高级语言，若
要采用链表结构，则可用数组存储的静态链表
实现。
虽然静态链表在存储分配上有不足之处，
但它和动态链表一样，具有插入和删除方便的
特点。
值得指出的是,即使对那些具有指针类
型的语言，静态链表也有其用武之地。特别是
当线性表的长度不变，仅需改变结点间的相对
关系时，静态链表比动态链表更加方便、高效。
6.6 Application,Generating
Permutations
Pg.261 Fig.6.8 Generating
Permutations
The section left Self-
educated.
Pointers and Pitfalls
◆ Use C++ templates to implement generic data
structures.
◆ Don't confuse contiguous lists with arrays.
◆ Choose your data structures as you design
your algorithms,and avoid making premature
decisions.
◆ Always be careful about the extreme cases and
handle them gracefully,Trace through your
algorithm to determine what happens when a data
structure is empty or full.
◆ Don't optimize your code until it works perfectly,
and then only optimize it if improvement in
efficiency is definitely required,First try a simple
your data structures,Change to a more
sophisticated implementation only if the simple
one proves too inefficient.
◆ When working with general lists,rst decide
exactly what operations are needed,and then
choose the implementation that enables those
operations to be done most easily.
◆ Study several simple examples to see whether
or not recursion should be used and how it will
work.
◆ In choosing between linked and contiguous
implementations of lists,consider the necessary
operations on the lists,Linked lists are more
flexible in regard to insertions,deletions,and
rearrangement; contiguous lists allow random
◆ Contiguous lists usually require less computer
memory,computer time,and programming effort
when the items in the list are small and the
algorithms are simple,When the list holds large
data entries,linked lists usually save space,time,
and often programming effort.
◆ Dynamic memory and pointers allow a program
to adapt automatically to a wide range of
application sizes and provide flexibility in space
allocation among different data structures,Static
memory (arrays and indices) is sometimes more
efficient for applications whose size can be
completely specified
in advance.
◆ For advice on programming with linked lists in
dynamic memory,see the guidelines in Chapter 4.
◆ Avoid sophistication for sophistication's sake,
Use a simple method if it is adequate for your
application.
◆ Don't reinvent the wheel,If a ready-made class
template or function is adequate for your
application,consider using it.
