Chapter-2-Linear-List数据结构-入门课件-第二篇.ppt

Singly-Linked form Data Field Pointer Field Data Field Predecessor Pointer Successor Pointer Doubly-Linked form Idiomatic description for Doubly-linked form Predecessor Pointer Data Field Successor Pointer …… a1 a2 an ^ head header cell The symbol ^ means NULL, that indicates the pointer does not point to anywhere. 2.3.3 Characters of Linked List Example: Several students make a date for journey during holiday. Because of the long distance between them, to save the fee of toll telephone, they stipulate a one-way connection that each one at most notice one person and be noticed by only one. The student Jack in Seattle is the starter, each one’s linkman lists as follows: Boston Frank 34 … … … 14 Washington Anna 5 … … … … … … … … … … … … 6 Princeton Simon 33 ^ San Francisco Mary 27 5 Seattle Jack 21 33 Los Angeles Shirley 14 27 New York Bill 6 San Diego Lynn 1 Linkman Address Name No. Conclusions: The logical contiguous nodes are not always contiguous in physics. The head and tail node in a linked list are different from others——the head node needs a head pointer to denote and the content of the pointer field of tail node must be null (or nil). In general, the pointer field of the data element is always defined as the pointer type. The serial number of data element of linked list does not start from 0. Jack 5 Shirley 33 Anna 14 Simon 6 Bill 27 Mary ^ head 2.3.4 Operations in Singly-Linked List Initialization ① Define data type and pointers. To simplify the programming, we defined some macros. #define L sizeof(struct chain) #define NEW(s) (SLL *)malloc(s) #include stdio.h typedef struct chain { int n; struct chain *next; }SLL; SLL *head,*p,*q; ② Create an empty list head=NULL; ③ Input the head node p=NEW(L); p-next=NULL; scanf(%d,p-n); head=p; head p 27 ^ ^ ④ Supplement nodes q=NEW(L); scanf(%d,q-n); p-next=q; q-next=NULL; ⑤ To supplement repeatedly, a flag could be u