(2.3.1)--ch2-03建立单链表.pdf

《(2.3.1)--ch2-03建立单链表.pdf》由会员分享，可在线阅读，更多相关《(2.3.1)--ch2-03建立单链表.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法Data Structures and Algorithms建立单链表 Create a Singly Linked ListData Structures and AlgorithmsData Structures and Algorithms2CHAPTER2 Linear ListLinear List（A,B,C,D,E,F,D,H）Singly Linked List：Head Pointer HHead Pointer HStorage AddressStorage AddressData FieldData FieldPoiter FieldPoiter Fiel

2、d 1 D 43 1 D 43 7 B 13 7 B 13 13 C 1 13 C 1 19 H NULL 19 H NULL 25 F 37 25 F 37 31 A 7 31 A 7 37 G 19 37 G 19 43 E 25 43 E 253131AHBCDEFGH Data Structures and AlgorithmsData Structures and AlgorithmsData Structures and AlgorithmsData Structures and Algorithms3CHAPTER2 Linear List2.4 Chain storage of

3、 linear listsSingly Linked List：each node has only one pointer fieldA singly linked list has two fields for each nodeData Field：Pointer Field：used to store the data value of the nodeused to store the direct successor address or location of data elements Head Pointer ：Pointer to the head node of the

4、linked list.Node：While storing the value of each data element in the linear list at the same time that indicates the subsequent nodesaddress(or location)information,the storage image composed of these two pieces of information is called a node.Definition of node：typedef struct Node ElemType data；str

5、uct Node *next；LNode,*LinkList；Data Structures and AlgorithmsData Structures and Algorithms4CHAPTER2 Linear List2.4 Chain storage of linear listsSingly Linked Listp=（LinkList）malloc(sizeof(LNode)；Indicates the operation of applying for a storage unit of type LNodeand assigning its address to the var

6、iable p;free（p）Indicates that the space of the node pointed to by the pointer p is released.Data Structures and AlgorithmsData Structures and Algorithms5CHAPTER2 Linear List2.4 Chain storage of linear lists Create a singly linked listHead insert methodsAs points to the newly applied nodes-data=A;LsA

7、Insert the first node：Insert a node：LAsB:Starting from an empty list,repeatedly read in the data to generate new nodes to store the read data in the data field of the new node,and then insert the new node after the header node of the current linked list until the end of reading is marked.s-next=L-ne

8、xt;L-next=s;Can the order be reversed?LInitialize empty listData Structures and AlgorithmsData Structures and Algorithms6CHAPTER2 Linear List2.3 线性表的链式存储线性表的链式存储 建立单链表建立单链表头插法建表头插法建表算法算法 Linklist CreateFromHead()LinkList L;LNode *s;int x;int flag=1;L=(Linklist)malloc(sizeof(LNode)；L-next=NULL;scanf(

9、“%d”,&x);while(x!=-1)s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=L-next;L-next=s;scanf(“%d”,&x);return L;Data Structures and AlgorithmsData Structures and Algorithms7CHAPTER2 Linear List2.4 Chain storage of linear lists Create a singly linked listTail insert methodsAs points to the newly applied

10、nodes-data=A;HsAInsert the first node：Insert a node：sBInsert the new node into the end of the current singly linked list.Add a tail pointer r to point to the end of the current singly linked list.r-next=s;r=s;Can the order be reversed?HInitialize empty listrrHArrData Structures and AlgorithmsData St

11、ructures and Algorithms8CHAPTER2 Linear List2.4 Chain storage of linear lists 建立单链表建立单链表尾插法建表尾插法建表算法算法 Linklist CreateFromTail()LinkList L;LNode*r,*s;int x;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(“%d”,&x);while(x!=-1)s=(LNode*)malloc(sizeof(LNode);s-data=x;r-next=s;r=s;scanf(“%d”,&x);r-

12、next=NULL;return L;Data Structures and AlgorithmsData Structures and Algorithms9Createing a singly linked list algorithm summary:1.Head insert method：Insert a node at the head of the linked list to create a singly linked list.The data read-in sequence is exactly the opposite of the logical sequence

13、in the linear list.2.Tail insert method：Insert a node at the end of the linked list to create a singly linked list.The data read-in sequence is exactly the same as the logical sequence in the linear list.Reflection questions:If a singly-linked list H with a header node design algorithm to implement：

14、taking the first element in the list as a standard，all nodes in the list whose value is less than the first element are placed before the first element node，all nodes with a value greater than the first element are placed after the first element node.2015335 HData Structures and AlgorithmsData Structures and Algorithms ThanksD Da at ta a S St tr ru uc ct tu ur re es s a an nd d A Al lg go or ri it th hm ms s