0% found this document useful (0 votes)
78 views135 pages

2 - Lists-Note Version

- Live class will begin April 9 at 10:30 Beijing time to discuss data structures including lists, stacks, queues, and strings. - Questions about previous topics on structure, ADT, algorithms, and asymptotic analysis will also be addressed. - Recursion will be covered, including examples of calculating factorials and Fibonacci numbers recursively as well as analyzing recursive procedures.

Uploaded by

Rakibul Islam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
78 views135 pages

2 - Lists-Note Version

- Live class will begin April 9 at 10:30 Beijing time to discuss data structures including lists, stacks, queues, and strings. - Questions about previous topics on structure, ADT, algorithms, and asymptotic analysis will also be addressed. - Recursion will be covered, including examples of calculating factorials and Fibonacci numbers recursively as well as analyzing recursive procedures.

Uploaded by

Rakibul Islam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 135

Live class will begin April 9 10:30 Beijing Time

• Any questions about the previous part?


Structure: Why?Basic;
• Structure logical/storage
• ADT
• Algorithm ADT: What?

➢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.

Logical structure Storage structure


ADT of List
• ADT List{
• Data:D={ai| ai∈Elemset, (i=1,2,…,n, n>=0)}
• Structure{<ai-1,ai>| ai-1,ai ∈D}
• Operation:
• InitList(&L); destroyList(&L);
• ListInsert(&L,I,e); ListDelete(&L,I,&e);
• …
• } ADT List
• There is no rule telling us which operations must be supported for
each ADT
• This is a design decision
• Based on your demands
Basic operation

• InitList(&L) (Initialization List)


• Result: Create an empty List

• 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

• Not only save the data


• But also the relation (linear) between elements

• 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)

• Storage structure 0 1 i-1 n-1


• Array a1 a2 … ai … an

Why the array index start with 0?


• A question about Array and List.
• Q:If lists gives us the freedom then why do we have to learn
Array and use Array?

• Do we need to eliminate the old methods or even old


programming language?
• Computer

Programming language • Machine


• To increase the efficiency
goal • human

• Programmer
• Speed: Autonomous vehicles/self-driving

• Space: system

• Power waste NASA


Embedded system
The Internet of things
• Object-oriented
• Process oriented

• 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],

• each unit is an int type variable


• [ ] is an operator
• index must??be legal
• hidden danger?
• int number[100];
• number[cnt]=x;
• Compiler will NOT check the range of the index
• the illegal index may cause the program crash
• segmentation fault
• You may lucky,nothing serious happen
• int a[0];
• Can exist,but useless
• Application
• input some integers (range from [0,9]),count the times of
each number,input -1 means finish
• We can use the index to save some information !!
• Free(do not need to define,do not need space)
• Fast
Size
Define
Initialize
Operation
Output
struct
• Why?
• We need to upgrade our “container”.
• one data-variable-type
• many data-same type-array
• many data-different type-?
define struct

struct name {
member1;
member2;
member3;
};
struct point { struct point {
int x; int x;
int y; int y;
}; } p1,p2;

struct point p1,p2; both p1,p2 are point type


there‘s x and y in p1,p2
inside or outside of the function?
struct & function
• 1.you can transmit the whole struct into the function
• (copy everything into the function,need space & time)

• 2. you can transmit the pointer into the function


• Why the array index start with 0?
• How to find each element in the array

a1 a2 … ai-1 ai ai+1 … an

• If each element take 8 storage units,the address of ai is 2000,where is the


ai+1?
• Assume each element take len storage ,then
• LOC( ai+1 )=LOC( ai )+ len
• How about the position ai with the a1
• LOC( ai)=LOC( a1)+(i-1)*len

• Index 1 2 i-1 i i+1 n


a1 a2 … ai-1 ai ai+1 … an
• Index 0 1 i-2 i-1 I n-1

• What‘s the difference?


• We find ai by calculating the address.
• One less subtraction if index stat with 0
• Find(ai)in array O(?)
Array implementation of Lists
• Logical structure List(a1,a2,…,ai,…,an)

• Storage structure 0 1 i-1 n-1 Maxsize-1


a1 a2 … ai … an n

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

• Not only save the data


• But also the relation (linear) between elements

• Storage structure
• Sequential storage:continuous memory space
• Linked storage:by pointer
Array implementation of Lists
• Logical structure List(a1,a2,…,ai,…,an)

• Storage structure 0 1 i-1 n-1 Maxsize-1


a1 a2 … ai … an n

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)

• Storage structure 0 1 i-1 n-1 Maxsize-1


a1 a2 … ai … an n

#define Maxsize 100 typedef struct{


typedef struct{ ElemType *elem;
ElemType elem[Maxsize]; int length;
int length; }SqList;
}SqList; L.elem=(ElemType*)malloc(sizeof(ElemType)*Maxsize);
#define Maxsize 100
typedef struct{
ElemType elem[Maxsize];
• static array int length;
}SqList;
• int a[10]
• you can use a symbol,still need to be a constant,can NOT be a variable
int n;
scanf(“%d”,&n);
int a[n]; X
• We still need to change the size of array
• dynamic array
typedef struct{
ElemType *elem;
• dynamic array int length;
int m; }SqList;
scanf(“%d”,&m); L.elem=(ElemType*)malloc(sizeof(ElemType)*Maxsize;

int *p;
p=(int*)malloc(m*(sizeof(int)));


free(p);
• Each element is complex type
• ISBN,Name,Price #define Maxsize 10000

typedef struct{ //Book information


char num[20]; //ISBN
char name[50]; //Name
float price; //Price
}Book;

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

• 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
• 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

Status InitList_Sq(SqList &L){


L.elem=(ElemType*)malloc(sizeof(ElemType)*Maxsize);
if(!L.elem) exit(OVERFLOW);
L.length=0;
return OK;
}
• destroy List
void DestroyList (SqList &L){
if (L.elem) delete L.elem; //c++
}

• clear List

void ClearList (SqList &L){


L.Length=0;
}
• Get the length of the List
int GetLength (SqList L){
return (L.length);
}

• test a List is empty or not


int IsEmpty (SqList L){
if (L.Length==0); return 1;
else return 0;
}
• Get the value of position i
int GetElem(SqList L,int i,ElemType &e){
if(i<1 || i>L.Length) return ERROR; // is the position reasonable?
e=L.elem[i-1];
return OK;
}

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;
}

int LocateElem(SqList L,ElemType e){


i=0;
while(i<L.Length && L.elem[i]!=e) i++;
if(i<L.length) return i+1;
return 0;
}
• O(?)
int LocateElem(SqList L,ElemType e){
for(i=0;i<L.Length;i++)
if(L.elem[i]==e) return i+1;
return 0;
}

ASL(average search length)


• Insertion
• 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

• Insert at the end


• Insert in the middle
• Insert at the beginning
• thinking:
• Whether the insertion position is legal
• Whether the space is full
• Push the array down one spot to make room
• Insert the new element
• Increase Length
• insertion
Status ListInsert_Sq(SqList &L,int i,ElemType e){
if(i<1 || i>L.Length+1) return ERROR;
if(L.Length==Maxsize) return ERROR;
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];
• Whether the insertion position is legal
L.elem[i-1]=e;
• Whether the space is full
L.length++; • Push the array down one spot to make room
return OK; • Insert the new element
• Increase Length
}
• O(?)

• 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

• delete at the end


• delete in the middle
• delete at the beginning
• thinking:
• whether the deletion position is legal
• keep the value if you need
• move the elements to keep the linear relation
• decrease Length
• deletion
Status ListDelete_Sq(SqList &L,int i,){
if ((i<1) || (i>L.Length)) return ERROR;
for(j=i;j<=L.Length;j++)
L.elem[j-1]=L.elem[j];
L.length--;
return OK;
}
• O(?)

• disadvantage
• Summary of the sequential List
➢advantage:easy to visit
save the space
➢disadvantage:insert/delete O(n)

• reason:the list is stored contiguous


• linked list
Linked list
• consists of a series of structures,not necessarily adjacent in
memory
• each structure contains
➢the element
➢a pointer to its successor (Next pointer)

Data Next
List (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)

• hundred family surn

• ame 百家姓

• 天地玄黄 宇宙洪荒
• 云腾致雨 露结为霜
• 始制文字 乃服衣裳
List (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)

address Data Next

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

ZHAO QIAN SUN LI

ZHOU WU ZHENG WANG ^


• in order to access this list, we need to know where the first cell
can be found
• pointer variable/ first element pointer

• careless coding will lose the list


• header
• header (dummy node)
• the header is in position 0
• without header

• with header
• whether or not a header should be used ?
➢special case (delete the first element)
➢empty list

• what’s the header’s data?


Data Next
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
a1 a2 … an

• Define the List L:LinkList L;

• Define the node with pointer;Lnode *p; LinkList p;


E.X. Try to save students’ information(ID,name,score)by node

typedef struct student{ typedef struct {


char num[8]; char num[8];
char name[8]; char name[8];
int score; int score;
struct student *next; } Elemtype;
}Lnode,*LinkList;
typedef struct Lnode{
Elemtype data;
struct Lnode *next;
}Lnode,*LinkList;
Basic operation of linked 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)
typedef struct Lnode{
• Initialization of linked List ElemType data;
Struct Lnode *next;
• Creat an header;
}Lnode,*LinkList;
• Make the next of header NULL;

Status InitList_L(LinkList &L) {


L=(LinkList) malloc (sizeof(LNode));
L->next=NULL;
return OK;
}
• test whether a linked list is empty

• check the next of header, NULL or not;

int ListEmpty (LinkList L) {


if(L->next)
return 0;
else
return 1; //if the L is empty,return 1
}
• destroy linked List

free all the nodes

• P=L; • L=L->next; • End: L==NULL;


• free(p); • Loop: L!=NULL;
• destroy linked List
Status DestroyList_L (LinkList &L){
• P=L; Lnode *p; // or LinkList p;

• L=L->next; while (L) {

• free(p); p=L;
L=L->next;

• End: L==NULL; free(p);


• Loop: L!=NULL; }
return OK;
}
• clear linked List
• clear vs. destroy? The header is still there

• P=L->next; • Loop: • End: p==NULL;


• p=q; • Loop: p!=NULL;
• q=p->next; • q=q->next;
• free(p); • L->next=NULL;
• clear linked List
• P=L->next; Status ClearList_L (LinkList &L){

• q=p->next; Lnode *p,*q;


• free(p); while (p) {

• Loop:
q=p->next;
• p=q; free(p);
• q=q->next; p=q;
• End: p==NULL; }
• Loop: p!=NULL; L->next=NULL;

• L->next=NULL; return OK;


}
• Length of the linked List
• count the number of nodes
int ListLength(LinkList L){
LinkList p;
p=L->next;
i=0;
while (p) {
i++;
p=p->next;
}
return i;
}
• Get the value of position i

Status GetElem_L(LinkList L,int i,ElemType &e){


p=L->next; j=1;
while(p && j<i){
p=p->next;++j;
}
if(!p || j>i) return ERROR;
e=p->data;
return OK;
} 顺藤摸瓜 follow the vine to get the melon
• search

• p=L->next; • p=p->next; • p->data!=e;


• search (return the pointer)

Lnode *LocateElem_L (LinkList L,ElemType e) {


p=L->next;
while(p && p->data!=e)
p=p->next;
return p;
}
• search (return the position)

int LocateElem_L (LinkList L,ElemType e) {


p=L->next;
j=1;
while(p && p->data!=e)
{p=p->next; j++}
if(p) return j;
else return 0;
}
• insertion
insert the new node before the number i node

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

Sequential List Linked List


• space: over estimate • space: extra space
• time: • time:
➢visit ➢visit
➢insert/delete ➢insert/delete

which way is better?


Example of Lists
• the polynomial
• single-variable polynomial
• f(x)=a0+a1x+…+an-1xn-1+anxn
• goal: easy to save
• easy to calculate (+,-,*…)
• what do we need to save
• x?
• a0 a1… an coefficient / 系数
• 0 1 …n exponent/ 指数
Sequential List of the polynomial
• f(x)=4x5-8x3+3x2+1
• coefficient & exponent

• use the index of array to save exponent

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

p->exp < q->exp: p is one node of the result


move p to next,q still there
compare
p->exp and q->exp p->exp > q->exp: q is one node of the result
insert q before p, move q to next,p still there
0:delete p,
p->exp = q->exp: add coef free p,q,move p,q to next
0:modify the coefficient,
free q, move p,q to next

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

pre p pre p pre pp p

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

which way is better?


depend on the problem
trade-off 舍得
• Can we combine the Sequential List and Linked List?
• cursor (游标)
• How to find the predecessor in a Linked list?
• scan from the header (one way)
• doubly linked list
• circularly linked list
• Experiment Part
• Session1-Part1
• Create a List (0,1,…,499,501,…,999,1000)
• Implemented by array
• Insert 500 into correct position to keep the list sorted
• How to calculate the operation time (insertion)?
• Experiment Part
• Session1-Part1
• Create a List (0,1,…,499,501,…,999,1000)
• Implemented by array
• Insert 500 into correct position to keep the list sorted
• How to calculate the operation time (insertion)?
• # include <time.h>
• Clock()
• Time()
• clock_t start,finish;
• double TheTimes;
•…
• start=clock();
•…
• finish=clock();
• TheTimes= (double)(finish-start)/CLOCK_PER_SEC;
• Experiment Part
• Session1-Part2
• Create a List (0,1,…,499,501,…,999,1000)
• Implemented by Linked Lists
• Insert 500 into correct position to keep the list sorted
• Compare the insertion time between the array and linked list
• Experiment Part
• Session2-Part1
• Josephus problem/circle
• Jewish historian in 1st century; VS. Roman
• n (total number);k(random number to be killed)n>k;
• only one left
• try array first;
• other version: Monkey King
• Experiment Part
• Session2-Part2
• Josephus problem/circle
• Jewish historian in 1st century; VS. Roman
• n (total number);k(random number to be killed)n>k;
• only one left
• circularly linked list
• Experiment Part
• Session3-Part1
• create a linked list
• enter the data from the keyboard
• Experiment Part
• Session3-Part2
• create a linked list by two methods
• Head insertion/ Tail insertion
• reverse input / normal

You might also like