2. Linked Lists first Address Data Pointer LZHAOCQIANC 0010 SUN 1011 0011 OIAN 0010 sUN匚Ls NULL 0110ZHAO0011 1011 nULL To link '" QIAN: Head pointer first=0110list_ptr N1, N2 N1=(list_ ptr)malloc(sizeof(struct list node)); N2 =(ist _ptr)malloc(sizeof(struct list node)) Initialization: N1→>data= ZHAO; N2->data =QIAN N1->ink E n2 typedef struct list node *list_ ptr N2->link NULL, typedef struct list node i first= n1 char data[41 list_ ptr link list_ptr first first ZHAo[QIAN日NULL
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 i first= newnode; newnode newnode first first (入前) (插入后)
▪ 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->links p=>ink- newnode newnode- newnode 入后
• 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->ink= newnode i P newnode newnode 入后)
• 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(“无效的插入位置!m”);/终止插入 return 0 ListNode x newnode /创建新结点 (ListNode *)malloc( sizeof (listnode));
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) );