2 - Lists-Note Version
2 - Lists-Note Version
➢Algorithm: data、relation、operation
➢Description:natural language-pseudocode-code
➢Analysis:worst、average、beat case
➢Asymptotic analysis:notation θ、O;typical growth rates;rules(How to
analysis program fragment)
exercises
T(n) =C+T(n-1)
• Recursive procedures: T(n-1)=C+T(n-2)
• n!(factorial) T(n-2)=C+T(n-3)
……
T(2) =C+T(1)
T(1) =C0
T(n) =C(n-1)+C0
• O(?) =O(n)
Just a simple loop!
Recursion will make your code simple
• Another recursive example
Bad(int N){
/1/ if(N == 0);
Not all recursion can give you result
/2/ return 0;
/3/ else
/4/ return Bad(N/3+1)+N-1;
}
Any problem?
Bad(1)=?
The computer will repeatedly make call to Bad(1)
in attempt to resole its value
System will run out of space and crash
• Two fundamental rules of recursion
➢1.Base cases. You must always have some base cases,which can be
solved without recursion.
➢2.Making progress. For each cases that are to be solved recursively,the
recursive call must always be to a case that makes progress towards a base
case.
• Not all recursion is highly efficient
Fib(int N)
{
/1/ if(N <= 1);
/2/ return 1;
/3/ else
/4/ return Fib(N-1)+Fib(N-2);
}
There is a huge amount of redundant work
First call on line 3,Fib(N-1),actually computes Fib(N-2)
The information is thrown away and recomputed by the second call on line 3
• Should not scare you away from using recursion
• If you don’t familiar with the recursion
• READ the textbook Chapter 1(1.3).
Chapter 2 Linear structure
• List
• linear structure • Stack
• Queue
• Logical • String …
structure
• Tree
• nonlinear structure
Data • graph
structure
• Storage
structure
• operation • find、sort、insert、delete…
• General form of list
• (a1,a2,a3,…,an)
• Finite sequence
• Data element with same type
• Size: n
• Empty list: special list of size 0
• Index: position of each element in the List
• ai is an abstract symbol,can be many things
• E.g. Alphabet by the 26 English letters
• (A,B,C,D,…,Z)
• Data elements are letters
• The relation between these element-linear
• Can NOT change the order
• E.g. Students’ information
• Each element is complex type (name,ID,…)
• E.g. the computer numbers of our school since 1998
• (6,17,28,50,92,188)
• Imply the information of years
• E.g. twelve constellation
• (Aries,Taurus,Gemini,Cancer,Leo,…,Pisces)
• (白羊座,金牛座,双子座,巨蟹座,狮子座,…,双鱼座)
• For list,the order is important
• ai+1 follows ai ; ai-1 precedes ai
• ai+1 is successor of ai 后继
• ai-1 is predecessor of ai 前驱
• The first element of the list is a1, not define the predecessor of a1.
• The last element is an,not define the successor of an.
• DestroyList(&L)
• Condition: List L already exist
• Result: destroy the List L
• ClearList(&L)
• Condition: List L already exist
• Result: make the List to empty
Basic operation
• ListEmpty(L)
• Condition: List L already exist
• Result: if the List is empty,return TRUE;else return FALSE
• ListLength(L)
• Condition: List L already exist
• Result: return the numbers of elements in List
Basic operation
• GetElem(L,i,&e)
• Condition: List L already exist, 1<=i<=ListLength(L)
• Result: return the ith element value to e
• ListLength(L)
• Condition: List L already exist
• Result: return the numbers of elements in List
Basic operation
• PriorElem(L,cur_e,&pre_e)
• Condition: List L already exist
• Result: if the cur_e in the List, and it’s not the first one, then return the
predecessor to the pre_e
• NextElem(L,cur_e,&next_e)
• Condition: List L already exist
• Result: if the cur_e in the List, and it’s not the last one, then return the
successor to the next_e
Basic operation
• ListInsert(&L,i,e)
• Condition: List L already exist, 1<=i<=ListLength(L)+1
• Result: before the position i, insert the new element e, size+1
Basic operation
• ListDelete(&L,i,&e)
• Condition: List L already exist, 1<=i<=ListLength(L).
• Result: delete the element at the position i, return the value to e, size-1
• These ADT operations are defined on logical structure
• Just define “What” here
• (goal,condition,result)
• “How to implement?”
• after storage structure is determined
• Logical structure → Storage structure
• Storage structure
• Sequential storage:continuous memory space
• Linked storage:by pointer
• sequential storage:continuous memory space
• Physical adjacency represents logical continuity
• e.g. List(1,2,3,4,5,6)
• sequential storage √
1 2 3 4 5 6
• continuous memory address
1 2 3 4 5 6
• Empty memory space between the element
• Destroy the original logical structure X
• What do we have to implement sequential storage?
• continuous memory space
• index
• array
Array implementation of Lists
• Logical structure List(a1,a2,…,ai,…,an)
• Programmer
• Speed: Autonomous vehicles/self-driving
• Space: system
• How to drive?
• How to build a car?
• How to choose these programming languages?
• For work
• For study
• pointer
• Scanf(“%d”,&i)
• * get value
• & get address
int i;
int *p=&i;
int* p,q;
int *p,q;
Live class will begin April 16 10:30 Beijing Time
Array
• Why?
• We are lazy.
• E.X. let user input some positive integers, calculate the average and output
those larger than the average?
• to record these numbers
• int num1,num2,num3……?
• We need something to keep many variables
• int number[100];
Array
• Container
• 放东西的东西
Array
• Container
• Every element is the same type
• Can NOT change the size after definition
• <type> variable[element number];
• int grade[100];
• double weight[20];
• int a[10];
• 10units:a[0], a[1],… a[9],
struct name {
member1;
member2;
member3;
};
struct point { struct point {
int x; int x;
int y; int y;
}; } p1,p2;
a1 a2 … ai-1 ai ai+1 … an
Array:size is fixed
Contradiction?
List:size will change (insert、delete)
Overestimate(maxsize>n)
Define:the whole array :Maxsize
just use part of it :n
• Logical structure → Storage structure
• Storage structure
• Sequential storage:continuous memory space
• Linked storage:by pointer
Array implementation of Lists
• Logical structure List(a1,a2,…,ai,…,an)
Array:size is fixed
Contradiction?
List:size will change (insert、delete)
Overestimate(maxsize>n)
Define:the whole array :Maxsize
just use part of it :n
Array implementation of Lists
• Logical structure List(a1,a2,…,ai,…,an)
int *p;
p=(int*)malloc(m*(sizeof(int)));
…
…
free(p);
• Each element is complex type
• ISBN,Name,Price #define Maxsize 10000
typedef struct{
Book *elem;
int length;
}SqList;
Define type and variable
• Just like
#define Maxsize 100
• int a;//define variable a,a is
typedef struct{
int type
Elem Type *elem;
int length; • SqList L;//define variable L,
}SqList; // define the List type • L is a SqList type
• L is a List
• after we define the variable,then the computer will allocate memory
space
• then we can operate the List
• Size of L?
Sequential List in memory
#define Maxsize 100
typedef struct{ • SqList L;//define variable L,
Elem Type elem[Maxsize]; • L is a SqList type
int length; • L is a List
}SqList; // define the List type
• Index 0 1 2 3 4 5 6 7 … 99
• List a b c d e f g 7
• L.elem L.length
• Array: L.elem[0] L.elem[1] L.elem[2] … … L.elem[99]
• Index 0 1 2 3 4 5 6 7 … 99
• List a b c d e f g 7
• L.elem L.length
• L->elem
• Which one is right?
• If you use pointer
• SqList *L;
Basic operation of List
• InitList(&L) //initialization,create an empty List
• DestoryList(&L) //destroy the List L
• ClearList(&L) //clean the List
• ListInsert(&L,i,e)
• ListDelete(&L,i,&e)
• IsEmpty(L)
• ListLength(L)
• LocateElem(L,e)
• GetElem(L,i,&e)
• Status code
• #define TRUE 1
• #define FALSE 0
• #define OK 1
• #define ERROR 0
• #define OVERFLOW -2
• Initialization of List
• clear List
O(?)
• search
• if exist:return the position
• if not:return 0
• search
int LocateElem(SqList L,ElemType e){
for(i=0;i<L.Length;i++)
if(L.elem[i]==e) return i+1;
return 0;
}
• Index 0 1 2 3 4 5 6 7 … 99
• List a b d e a f 6
• L.elem L.length
• disadvantage
• deletion
• Array: L.elem[0] L.elem[1] L.elem[2] … … L.elem[99]
• Index 0 1 2 3 4 5 6 7 … 99
• List a b d e a f 6
• L.elem L.length
• disadvantage
• Summary of the sequential List
➢advantage:easy to visit
save the space
➢disadvantage:insert/delete O(n)
Data Next
List (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
• ame 百家姓
• 天地玄黄 宇宙洪荒
• 云腾致雨 露结为霜
• 始制文字 乃服衣裳
List (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
1 LI 43
?
7 QIAN 13
H 13 SUN 1
31 19 WANG NULL
25 WU 37
31 ZHAO 7
37 ZHENG 19
43 ZHOU 25
H
• with header
• whether or not a header should be used ?
➢special case (delete the first element)
➢empty list
• free(p); p=L;
L=L->next;
• Loop:
q=p->next;
• p=q; free(p);
• q=q->next; p=q;
• End: p==NULL; }
• Loop: p!=NULL; L->next=NULL;
21 18 30 75 30 56 ∧
e i=3
e
21 18 30 75 30 56 ∧
step
1.find node ai-1;
2.creat a new node (data=e);
3.insert the new node;
• insertion
Status ListInsert_L (LinkList &L, int i, ElemType e) {
p=L; j=0;
while(p && j<i-1)
{p=p->next; ++j; }
if(!p || j>i-1) return ERROR; // illegal position
s=(LinkList)malloc(sizeof(Lnode)); s->date=e;
s->next=p->next;
p->next=s;
return OK;
}
• deletion
21 18 30 75 30 56 ∧
i=3
21 18 75 30 56 ∧
step
1.find node ai-1;
2.save the value of ai if you need;
3.connect the node ai-1 and ai+1
• deletion
Status ListDelete_L (LinkList &L, int i, ElemType &e) {
p=L; j=0;
while(p->next && j<i-1)
{p=p->next; ++j; } //locate the position (i-1)
if(!(p->next) || j>i-1) return ERROR; // illegal position
q=p->next;
p->next=q->next;
e=q->data;
free(q);
return OK;
}
O(?) of the operation
• search
• insert
• delete
• creat an Linked List
• Head insertion
• Tail insertion
• Head insertion
• reverse input
• L(a, b, c, d, e) input e,d,… ,a
• Head insertion
L =(Lnode*)malloc(sizeof(LNode));
L->next=NULL;
p =(Lnode*)malloc(sizeof(LNode));
//p=new Lnode; C++
p->data=an;
p->next=L->next; L->next=p;
p =(Lnode*)malloc(sizeof(LNode));
p->data=an-1 ;
p->next=L->next; L->next=p;
• Head insertion
void CreateList_H (LinkList &L, int n) {
L =(Lnode*)malloc(sizeof(LNode));
L->next=NULL;
for(i=n; i>0; --i) {
p=(Lnode*)malloc(sizeof(LNode));
scanf(&p->data);
p->next=L->next;
L->next=p;
}
return OK;
}
• Tail insertion
• normal input
• L(a, b, c, d, e) input a,b,… ,e
• link every new node to the “tail”
p->data=ai; p->next=NULL;
r->next=p;
r=p;
• Tail insertion
void CreateList_R (LinkList &L, int n) {
L =(Lnode*)malloc(sizeof(LNode)); L->next=NULL;
r=L; // rear pointer
for(i=n; i<0; ++i) {
p=(Lnode*)malloc(sizeof(LNode));
scanf(&p->data);
p->next=NULL;
r->next=p;
r=p;
}
}
Sequential List VS. Linked List
• Sequential storage:continuous memory space
• Linked storage:by pointer
1 0 3 -8 0 4
• easy to save easy to calculate
• R=(p0+q0,p1+q1, p2+q2 …)
• f(x)=x+3x2000 ?
• waste space
• waste time
• linked list
• Node
➢data:coefficient & exponent
➢next
typedef struct node
{ int coef, exp; coef exp next
struct node *next;
};
how to calculate? +
A( x ) = 7 + 3 x + 9 x 8 + 5 x17
B ( x ) = 8 x + 22 x 7 − 9 x 8
C ( x ) = A( x ) + B ( x ) = 7 + 11x + 22 x 7 + 5 x17
A -1 7 0 3 1 9 8 5 17 ^
B -1 8 1 22 7 -9 8 ^
C -1 7 0 11 1 22 7 5 17 ^
p,q point to the first element Node
A -1 7 0 3 1 9 8 5 17 ^
P
B -1 8 1 22 7 -9 8 ^
q
procedure to add two polynomials
pa 11
3 111 99 88 55 17
pa -1
-1 77 00 11 17 ^^
pb
pb -1
-1 88 11 22
22 77 -9
-9 88 ^^ q=NULL
q q q
pre
pa -1 7 0 11 1 22 7 5 17 ^
Sequential List VS. Linked List
• Sequential storage:continuous memory space
• Linked storage:by pointer