CHAPTER 3 Lists
§ 1 Abstract Data Type (ADT)
【 Definition】 Data Type = { Objects }? { Operations }
〖 Example〗 int = { 0,?1,?2,,INT_MAX,INT_MIN }
{?,?,?,?,?, }
【 Definition】 An Abstract Data Type (ADT) is a data
type that is organized in such a way that the
specification on the objects and specification of the
operations on the objects are separated from the
representation of the objects and the implementation
on the operations.
§ 2 The List ADT
Objects,( item0,item1,,itemN?1 )
Operations:
Finding the length,N,of a list.
Printing all the items in a list.
Making an empty list.
Finding the k-th item from a list,0? k < N.
Inserting a new item after the k-th item of a list,0? k < N.
Deleting an item from a list.
Finding next of the current item from a list.
Finding previous of the current item from a list.
ADT:
1,Simple Array implementation of Lists (seqlist)
array[ i ] = itemi
MaxSize has to be estimated.
Address Content
array+i itemi
array+i+1 itemi+1
…… ……
…… ……
Sequential mapping
Find_Kth takes O(1) time.
Insertion and Deletion not
only take O(N) time,but also
involve a lot of data movements
which takes time.
SeqList?s(顺序表 )definition
#define ListSize 100 //max length
typedef int ListData;
typedef struct {
ListData * data; //base address
int length; //current items? length
} SeqList ;
Basic operation of SeqList
Initialize
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n” );
exit (1);
}
L.length = 0;
}
Find value,find the position of x in
the SeqList,return position of x in L,-1
if not found.
int Find ( SeqList &L,ListData x ) {
int i = 0;
while ( i < L.length && L.data[i] != x )
i++;
if ( i < L.length ) return i;
else return -1;
}
Find value,whether x is in L
int IsIn ( SeqList &L,ListData x )
{ int i = 0,found=0;
while ( i < L.length &&!found )
if(L.data[i] != x ) i++;
else found=1;
return found;
}
Solve the length of SeqList
int Length ( SeqList & L ) {
return L.length;
}
Find k_th,return the k_th data in l
ListData GetData ( SeqList &L,int i ) {
if ( i >= 0 && i < L.length )
return L.data[i];
else printf (,参数 i 不合理 ！ \n” );
}
FindSucceed
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i+1;
else return -1;
}
FindPrevious
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i-1;
else return -1;
}
Insertion
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50Insert x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
The average moving number of times(AMN) if it is equal probability
to insert the new element into all positions.
Insertion
int Insert ( SeqList &L,ListData x,int i ) {
//insert the new element into position i
if (i < 0 || i > L.length || L.length == ListSize)
return 0; //failure
else {
for ( int j = L.length; j > i; j-- )
L.data[j] = L.data[j -1];
L.data[i] = x; L.length++;
return 1; //successful
}
}
Deletion
1
0
2
1
2
1)(11)(1=
n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 6316
delete x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
The average moving number of times(AMN) if it is equal
probability to delete every element
Deletion routine for SeqList
int Delete ( SeqList &L,ListData x ) {
//delete x
int i = Find (L,x); //find x in l
if ( i >= 0 ) {
L.length --;
for ( int j = i; j < L.length; j++ )
L.data[j] = L.data[j+1];
return 1; //successful
}
return 0; //x is not in l
}
Application of SeqList,union of set
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
Intersection of set
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
2,Linked Lists
Address Data Pointer
0010
0011
0110
1011
SUN
QIAN
ZHAO
LI
1011
0010
0011
NULL
Head pointer first = 0110
ZHAO QIAN
SUN LI
first
NULL
Initialization:
typedef struct list_node *list_ptr;
typedef struct list_node {
char data [ 4 ] ;
list_ptr link ;
} ;
list_ptr first ;
To link?ZHAO? and?QIAN?:
list_ptr N1,N2 ;
N1 = (list_ptr)malloc(sizeof(struct list_node));
N2 = (list_ptr)malloc(sizeof(struct list_node));
N1->data = ‘ZHAO’ ;
N2->data = ‘QIAN’ ;
N1->link = N2 ;
N2->link = NULL ;
first = N1 ;
ZHAO QIAN
first
NULL
Basic operation of Linked Lists
Insertion（ three cases）
the first case,insert new node before
the first node
newnode->link = first ;
first = newnode;
（插入前） （插入后）
first
newnode newnode
first
The second case,insert new node in
the middle
newnode->link = p->link;
p->link = newnode；
(插入前 ) (插入后 )
newnode
p
newnode
p
The third case,insert new node at the end
newnode->link = p->link;
p->link = newnode；
p
(插入前 ) (插入后 )
newnode newnode
p
Integrity algorithm:
int Insert ( LinkList& first,int x,int i ) {
//在链表第 i 个结点处插入新元素 x,i 是结点号，从 0开始
ListNode * p = first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL && first != NULL ) {
printf (,无效的插入位置 !\n” );//终止插入
return 0;
}
ListNode * newnode = //创建新结点
(ListNode *) malloc ( sizeof (ListNode) );
newnode->data = x;
if ( first == NULL || i == 0 ) { //插入空表或非空表第一个结点之前
newnode->link = first;//新结点成为第一个结点
if(first==NULL)last=newnode;//若是空表，表尾指针指向新结点
first = newnode;
}
else {//插在表中间或末尾
newnode->link = p->link;
if(p->link ==NULL)last=newnode;
p->link = newnode;
}
return 1;
}
Deletion
a1
ptr
NULLai ai+1 an...,..
b
pre
node
pre->link =
node->link
free ( node )
takes O(1) time.
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL || p->link == NULL ) {//找不到第
i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->link;
p->link = q->link;
}
if (q==last) last=p;//删除表尾结点
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
Linked lists with a header
The header is in position 0,it hasn?t data
,just regarded as a sentinel node.
The purpose of setting a header:
Simplify the operations of linked list to achieve
Not empty list empty list
^ana1first first ^
Insertion
q->link = p->link;
p->link = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
Before insertion After insertion
q q
insertp p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1;
}
Deletion q = p->link;
p->link = q->link;
delete q;
Before deletion
first
(not empty） (empty）
first
^
first
p q
^
p q
first
After deletion
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->link == NULL)
return 0;//i值不合理或空表
q = p->link;
p->link = q->link; //删除结点
free ( q ); //释放
return 1;
}
Create a linked list through inserting forward
Read data in continuous motion from the beginning
of creating an empty list：
Create a new node
Then store the reading data in the new node?s
data domain.
Insert this new node into list in the first position
Complete at the end of data reading
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; ListNode *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
Insert the new node at end of the list.
Rear pointer r is always point the end
node of the list,so insert the new node in
the back of it；
^
q
first ^
r
^first ^
r
Create a linked list through inserting backward
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
r ->link = q; r =q; //插入到表末端
}
r ->link = NULL;
return head;
}
Make list empty
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
ListNode *q;
while ( first->link != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->link; first->link = q->link;
free( q ); //释放
}
last=first;
}
Calculate the list length
int Length ( LinkList first ) {
ListNode *p = first->link; //指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->link; count++;
}
return count;
}
Find value
ListNode * Find ( LinkList first,ListData value )
{
//在链表中从头搜索其数据值为 value的结点
ListNode * p = first->link;
//指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->link;
return p;
}
Find value in the position i
ListNode * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL;
ListNode * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
1
ZHANG － 1
3
4
5
6
－ 1
－ 1
2
3
4
5
6
－ 1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
Empty list （ after inserting a new node）
Simple Array implementation of linked Lists
Static linked lists
head
ptr
ptr
head
1
ZHANG 2
WANG 6
LI 4
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
-1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
After inserting some nodes Insert chen in front of 3
Static linked lists
ptr
head head
Ptr = -
1
Simple Array implementation of linked Lists
1
ZHANG 2
WANG 6
LI 5
ZHAO － 1
WU -1
CHEN 3
0
1
2
3
4
5
6
After zhao deleted
ptr
Definition of the static linked list
const int MaxSize = 100; //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
Initialize lists
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = -1;
SL.newptr = 1; //当前可分配空间从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1; //构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
Find value
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link; //指针 p 指向链表第一个结点
while ( p != -1 )//逐个查找有给定值的结点
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
return p;
}
Find the node in position i
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1;//参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {//循环查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
Insert a new node into list before position i
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
Remove the position i node
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
Feature,The last node keep a pointer back to
the first。 We can search all nodes if we have
any one node address.
Storage Structure,linked list
circular list with head
an-1first a1a0
first
(空表 )
(非空表 )
§ 3 Circular List
Insertion of circular list
Josephus problem
Use circularly linked list to solve Josephus problem
N people sitting around,First person begins to number from one,and
continue doing this one by one at clockwise,when it comes to the
person who numbers m,then let him out,The next person begins to
number from one,when it comes to the person who numbers m,then
let him out,Continue doing this until there is only one person left,
Then this person is the winner.
For example,n = 8 m = 3
Solution of Josephus problem
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
The Polynomial
Add a data member (link) in every node of the polynomial?s
linked list representation,using it as link pointer.
Advantages:
– The number of polynomial can be added dynamically,
and there is no memory overflow problem.
– Insert and delete conveniently,and don not need to
move node.
Procedure to add two polynomials
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
Polynomial operator + ( const Polynomial
& ah,const Polynomial & bh ) {
Term *pa,*pb,*pc,*p;
ListIterator<Element> Aiter ( ah.poly );
ListIterator<Element> Biter ( bh.poly );
//建立两个多项式对象 Aiter,Biter
pa = pc = Aiter.First ( ); // pa 检测指针
pb = Biter.First ( ); // pb 检测指针
pa = Aiter.Next ( ); pb = Biter.Next( );
// pa,pb 越过表头结点
delete pb;
while ( Aiter.NotNull ( ) && Biter.NotNull ( ) )
switch ( compare ( pa→exp,pb→exp ) ) {
case '=',
pa→coef = pa→coef + pb→coef;
p = pb; pb = Biter.Next ( ); delete p;
if ( !pa→coef ) {
p = pa; pa = Aiter.Next ( );
delete p;
}
else {
pc→link = pa; pc = pa;
pa = Aiter.Next ( );
}
break;
case '<',
pc→next = pb; pc = pb;
pb = Biter.Next ( ); break;
case '>',
pc→next = pa; pc = pa;
pa = Aiter.Next ( );
}
if ( Aiter.NotNull ( ) ) pc→next = pa;
else pc→next = pb;
}
Node structure of doubly linked list：
prior data next
point prevoious point succeed
not empty list empty list
firstfirst
§ 4 Doubly Linked List
Definition of doubly linked list
typedef int ListData;
typedef struct dnode {
ListNode data;
struct dnode * prior,* next;
} DblNode;
typedef DblNode * DblList;
Create empty doubly linked list
void CreateDblList ( DblList & first ) {
first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ print (,存储分配错 !\n” ); exit (1); }
first->prior = first->next = first;
//表头结点的链指针指向自己
}
Solve the length of doubly linked list
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
Insertion(not empty)
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
insert 25 after node *p
first
first
31 48 15
p
p
31 48 25 15
q
Insertion(empty)
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
insert 25 after node *p
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
Deletion for doubly linked list
p->next->prior = p->prior;
p->prior->next = p->next;
(not empty)
delete 48
first
first
31 48 15
p
31 15
Deletion for doubly linked list
p->next->prior = p->prior;
p->prior->next = p->next;
first31
pdelete 31
empty
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//删除结点 p
free ( p ); //释放
return 1;
}
Cursor Implementation of Linked Lists (no pointer)
Features that a linked list must have:
a) The data are stored in a collection of structures,Each
structure contains data and a pointer to the next structure.
b) A new structure can be obtained from the system?s global
memory by a call to malloc and released by a call to free.
Cursor
Space
Element
Next
0 1 2 S-1… …
1 2 3 S-1 0
Note,The interface for the cursor implementation (given in
Figure 3.27 on p,52) is identical to the pointer
implementation (given in Figure 3.6 on p,40).
Element
Next 2 5 S-2 0
0 1 2 S-1… …
malloc:
p
p = CursorSpace[ 0 ].Next ;
CursorSpace[ 0 ].Next = CursorSpace[ p ].Next ;
x
Element
Next 2 5 S-2 0
0 1 2 S-1… …
p
free(p):
2
CursorSpace[ p ].Next = CursorSpace[ 0 ].Next ;
p
CursorSpace[ 0 ].Next = p ;
Note,The cursor implementation
is usually significantly faster
because of the lack of memory
management routines.
Read operation
implementations given in
Figures 3.31-3.35
§ 1 Abstract Data Type (ADT)
【 Definition】 Data Type = { Objects }? { Operations }
〖 Example〗 int = { 0,?1,?2,,INT_MAX,INT_MIN }
{?,?,?,?,?, }
【 Definition】 An Abstract Data Type (ADT) is a data
type that is organized in such a way that the
specification on the objects and specification of the
operations on the objects are separated from the
representation of the objects and the implementation
on the operations.
§ 2 The List ADT
Objects,( item0,item1,,itemN?1 )
Operations:
Finding the length,N,of a list.
Printing all the items in a list.
Making an empty list.
Finding the k-th item from a list,0? k < N.
Inserting a new item after the k-th item of a list,0? k < N.
Deleting an item from a list.
Finding next of the current item from a list.
Finding previous of the current item from a list.
ADT:
1,Simple Array implementation of Lists (seqlist)
array[ i ] = itemi
MaxSize has to be estimated.
Address Content
array+i itemi
array+i+1 itemi+1
…… ……
…… ……
Sequential mapping
Find_Kth takes O(1) time.
Insertion and Deletion not
only take O(N) time,but also
involve a lot of data movements
which takes time.
SeqList?s(顺序表 )definition
#define ListSize 100 //max length
typedef int ListData;
typedef struct {
ListData * data; //base address
int length; //current items? length
} SeqList ;
Basic operation of SeqList
Initialize
void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc
( ListSize * sizeof ( ListData ) );
if ( L.data == NULL ) {
printf (,存储分配失败 !\n” );
exit (1);
}
L.length = 0;
}
Find value,find the position of x in
the SeqList,return position of x in L,-1
if not found.
int Find ( SeqList &L,ListData x ) {
int i = 0;
while ( i < L.length && L.data[i] != x )
i++;
if ( i < L.length ) return i;
else return -1;
}
Find value,whether x is in L
int IsIn ( SeqList &L,ListData x )
{ int i = 0,found=0;
while ( i < L.length &&!found )
if(L.data[i] != x ) i++;
else found=1;
return found;
}
Solve the length of SeqList
int Length ( SeqList & L ) {
return L.length;
}
Find k_th,return the k_th data in l
ListData GetData ( SeqList &L,int i ) {
if ( i >= 0 && i < L.length )
return L.data[i];
else printf (,参数 i 不合理 ！ \n” );
}
FindSucceed
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i+1;
else return -1;
}
FindPrevious
int Next ( SeqList &L,ListData x ) {
int i = Find(x);
if ( i >0 && i < L.length ) return i-1;
else return -1;
}
Insertion
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50Insert x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
The average moving number of times(AMN) if it is equal probability
to insert the new element into all positions.
Insertion
int Insert ( SeqList &L,ListData x,int i ) {
//insert the new element into position i
if (i < 0 || i > L.length || L.length == ListSize)
return 0; //failure
else {
for ( int j = L.length; j > i; j-- )
L.data[j] = L.data[j -1];
L.data[i] = x; L.length++;
return 1; //successful
}
}
Deletion
1
0
2
1
2
1)(11)(1=
n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 6316
delete x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
The average moving number of times(AMN) if it is equal
probability to delete every element
Deletion routine for SeqList
int Delete ( SeqList &L,ListData x ) {
//delete x
int i = Find (L,x); //find x in l
if ( i >= 0 ) {
L.length --;
for ( int j = i; j < L.length; j++ )
L.data[j] = L.data[j+1];
return 1; //successful
}
return 0; //x is not in l
}
Application of SeqList,union of set
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
Intersection of set
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
2,Linked Lists
Address Data Pointer
0010
0011
0110
1011
SUN
QIAN
ZHAO
LI
1011
0010
0011
NULL
Head pointer first = 0110
ZHAO QIAN
SUN LI
first
NULL
Initialization:
typedef struct list_node *list_ptr;
typedef struct list_node {
char data [ 4 ] ;
list_ptr link ;
} ;
list_ptr first ;
To link?ZHAO? and?QIAN?:
list_ptr N1,N2 ;
N1 = (list_ptr)malloc(sizeof(struct list_node));
N2 = (list_ptr)malloc(sizeof(struct list_node));
N1->data = ‘ZHAO’ ;
N2->data = ‘QIAN’ ;
N1->link = N2 ;
N2->link = NULL ;
first = N1 ;
ZHAO QIAN
first
NULL
Basic operation of Linked Lists
Insertion（ three cases）
the first case,insert new node before
the first node
newnode->link = first ;
first = newnode;
（插入前） （插入后）
first
newnode newnode
first
The second case,insert new node in
the middle
newnode->link = p->link;
p->link = newnode；
(插入前 ) (插入后 )
newnode
p
newnode
p
The third case,insert new node at the end
newnode->link = p->link;
p->link = newnode；
p
(插入前 ) (插入后 )
newnode newnode
p
Integrity algorithm:
int Insert ( LinkList& first,int x,int i ) {
//在链表第 i 个结点处插入新元素 x,i 是结点号，从 0开始
ListNode * p = first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL && first != NULL ) {
printf (,无效的插入位置 !\n” );//终止插入
return 0;
}
ListNode * newnode = //创建新结点
(ListNode *) malloc ( sizeof (ListNode) );
newnode->data = x;
if ( first == NULL || i == 0 ) { //插入空表或非空表第一个结点之前
newnode->link = first;//新结点成为第一个结点
if(first==NULL)last=newnode;//若是空表，表尾指针指向新结点
first = newnode;
}
else {//插在表中间或末尾
newnode->link = p->link;
if(p->link ==NULL)last=newnode;
p->link = newnode;
}
return 1;
}
Deletion
a1
ptr
NULLai ai+1 an...,..
b
pre
node
pre->link =
node->link
free ( node )
takes O(1) time.
int Delete ( LinkList& first,int i ) {
//在链表中删除第 i 个结点
ListNode *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = first; first = first->link; }
else {
p = first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->link; k++; } //找第 i-1个结点
if ( p == NULL || p->link == NULL ) {//找不到第
i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->link;
p->link = q->link;
}
if (q==last) last=p;//删除表尾结点
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
Linked lists with a header
The header is in position 0,it hasn?t data
,just regarded as a sentinel node.
The purpose of setting a header:
Simplify the operations of linked list to achieve
Not empty list empty list
^ana1first first ^
Insertion
q->link = p->link;
p->link = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
Before insertion After insertion
q q
insertp p
int Insert (LinkList first,ListData x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
ListNode * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
ListNode * newnode = //创建新结点
(ListNode *) malloc (sizeof (ListNode) );
newnode->data = x;
newnode->link = p->link; //链入
p->link = newnode;
return 1;
}
Deletion q = p->link;
p->link = q->link;
delete q;
Before deletion
first
(not empty） (empty）
first
^
first
p q
^
p q
first
After deletion
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
ListNode * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->link == NULL)
return 0;//i值不合理或空表
q = p->link;
p->link = q->link; //删除结点
free ( q ); //释放
return 1;
}
Create a linked list through inserting forward
Read data in continuous motion from the beginning
of creating an empty list：
Create a new node
Then store the reading data in the new node?s
data domain.
Insert this new node into list in the first position
Complete at the end of data reading
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; ListNode *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
head->link = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
Insert the new node at end of the list.
Rear pointer r is always point the end
node of the list,so insert the new node in
the back of it；
^
q
first ^
r
^first ^
r
Create a linked list through inserting backward
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (ListNode));
ListNode *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (listNode *) malloc (sizeof(ListNode));
q->data = ch; //建立新结点
r ->link = q; r =q; //插入到表末端
}
r ->link = NULL;
return head;
}
Make list empty
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
ListNode *q;
while ( first->link != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->link; first->link = q->link;
free( q ); //释放
}
last=first;
}
Calculate the list length
int Length ( LinkList first ) {
ListNode *p = first->link; //指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->link; count++;
}
return count;
}
Find value
ListNode * Find ( LinkList first,ListData value )
{
//在链表中从头搜索其数据值为 value的结点
ListNode * p = first->link;
//指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->link;
return p;
}
Find value in the position i
ListNode * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL;
ListNode * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->link; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
1
ZHANG － 1
3
4
5
6
－ 1
－ 1
2
3
4
5
6
－ 1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
Empty list （ after inserting a new node）
Simple Array implementation of linked Lists
Static linked lists
head
ptr
ptr
head
1
ZHANG 2
WANG 6
LI 4
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
-1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
After inserting some nodes Insert chen in front of 3
Static linked lists
ptr
head head
Ptr = -
1
Simple Array implementation of linked Lists
1
ZHANG 2
WANG 6
LI 5
ZHAO － 1
WU -1
CHEN 3
0
1
2
3
4
5
6
After zhao deleted
ptr
Definition of the static linked list
const int MaxSize = 100; //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
Initialize lists
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = -1;
SL.newptr = 1; //当前可分配空间从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1; //构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
Find value
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link; //指针 p 指向链表第一个结点
while ( p != -1 )//逐个查找有给定值的结点
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
return p;
}
Find the node in position i
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1;//参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {//循环查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
Insert a new node into list before position i
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
Remove the position i node
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
Feature,The last node keep a pointer back to
the first。 We can search all nodes if we have
any one node address.
Storage Structure,linked list
circular list with head
an-1first a1a0
first
(空表 )
(非空表 )
§ 3 Circular List
Insertion of circular list
Josephus problem
Use circularly linked list to solve Josephus problem
N people sitting around,First person begins to number from one,and
continue doing this one by one at clockwise,when it comes to the
person who numbers m,then let him out,The next person begins to
number from one,when it comes to the person who numbers m,then
let him out,Continue doing this until there is only one person left,
Then this person is the winner.
For example,n = 8 m = 3
Solution of Josephus problem
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
The Polynomial
Add a data member (link) in every node of the polynomial?s
linked list representation,using it as link pointer.
Advantages:
– The number of polynomial can be added dynamically,
and there is no memory overflow problem.
– Insert and delete conveniently,and don not need to
move node.
Procedure to add two polynomials
AH = 1 - 10x6 + 2x8 +7x14
BH = - x4 + 10x6 - 3x10 + 8x14 +4x18
Polynomial operator + ( const Polynomial
& ah,const Polynomial & bh ) {
Term *pa,*pb,*pc,*p;
ListIterator<Element> Aiter ( ah.poly );
ListIterator<Element> Biter ( bh.poly );
//建立两个多项式对象 Aiter,Biter
pa = pc = Aiter.First ( ); // pa 检测指针
pb = Biter.First ( ); // pb 检测指针
pa = Aiter.Next ( ); pb = Biter.Next( );
// pa,pb 越过表头结点
delete pb;
while ( Aiter.NotNull ( ) && Biter.NotNull ( ) )
switch ( compare ( pa→exp,pb→exp ) ) {
case '=',
pa→coef = pa→coef + pb→coef;
p = pb; pb = Biter.Next ( ); delete p;
if ( !pa→coef ) {
p = pa; pa = Aiter.Next ( );
delete p;
}
else {
pc→link = pa; pc = pa;
pa = Aiter.Next ( );
}
break;
case '<',
pc→next = pb; pc = pb;
pb = Biter.Next ( ); break;
case '>',
pc→next = pa; pc = pa;
pa = Aiter.Next ( );
}
if ( Aiter.NotNull ( ) ) pc→next = pa;
else pc→next = pb;
}
Node structure of doubly linked list：
prior data next
point prevoious point succeed
not empty list empty list
firstfirst
§ 4 Doubly Linked List
Definition of doubly linked list
typedef int ListData;
typedef struct dnode {
ListNode data;
struct dnode * prior,* next;
} DblNode;
typedef DblNode * DblList;
Create empty doubly linked list
void CreateDblList ( DblList & first ) {
first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ print (,存储分配错 !\n” ); exit (1); }
first->prior = first->next = first;
//表头结点的链指针指向自己
}
Solve the length of doubly linked list
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
Insertion(not empty)
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
insert 25 after node *p
first
first
31 48 15
p
p
31 48 25 15
q
Insertion(empty)
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
insert 25 after node *p
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
Deletion for doubly linked list
p->next->prior = p->prior;
p->prior->next = p->next;
(not empty)
delete 48
first
first
31 48 15
p
31 15
Deletion for doubly linked list
p->next->prior = p->prior;
p->prior->next = p->next;
first31
pdelete 31
empty
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//删除结点 p
free ( p ); //释放
return 1;
}
Cursor Implementation of Linked Lists (no pointer)
Features that a linked list must have:
a) The data are stored in a collection of structures,Each
structure contains data and a pointer to the next structure.
b) A new structure can be obtained from the system?s global
memory by a call to malloc and released by a call to free.
Cursor
Space
Element
Next
0 1 2 S-1… …
1 2 3 S-1 0
Note,The interface for the cursor implementation (given in
Figure 3.27 on p,52) is identical to the pointer
implementation (given in Figure 3.6 on p,40).
Element
Next 2 5 S-2 0
0 1 2 S-1… …
malloc:
p
p = CursorSpace[ 0 ].Next ;
CursorSpace[ 0 ].Next = CursorSpace[ p ].Next ;
x
Element
Next 2 5 S-2 0
0 1 2 S-1… …
p
free(p):
2
CursorSpace[ p ].Next = CursorSpace[ 0 ].Next ;
p
CursorSpace[ 0 ].Next = p ;
Note,The cursor implementation
is usually significantly faster
because of the lack of memory
management routines.
Read operation
implementations given in
Figures 3.31-3.35
