数据结构(C语言)链表.ppt

The Linked Chain
The Linked Chain
What is Linked Chain( Linked List)
How to build a Linked Chain
To Implement the basic operation of Linked Chain
To Implement Polynomial’ Addition Using Linked Chain
Some different types Linked Chain
The Linked Chain
以链式结构存储的线性表
用一组在物理位置上任意的存储单元来存储线性表的结点,存储单元不一定是相邻的
物理位置上的关系不能反映结点间的逻辑关系
用一组任意位置的存储单元存储线性表的数据元素
结点间的逻辑关系借助结点中的指针实现
每个数据元素,除存储本身信息外,还需存储其直接后继的信息
结点
数据域:元素本身信息
指针(地址)域:指示直接后继的存储位置
The Linked Chain
Struct node * next
datatype element (eg. int element;char element)
Use Node
a
b
c
d
e
null
firstNode
size = number of elements
The Struct of Chain
链表中,每个结点只包含一个指针域
结点类型的C, C++语言描述:
struct node
{
datatype element;
struct node *next;
}
typedef struct node Node;
The Struct of Chain
结点类型的JAVA语言描述:
public class Node
{ //Node为结点类型
public Datatype element ;
public Node next;
}
Constructors Of ChainNode
Create a new node :
Node * p = (Node *)malloc(sizeof(Node)) /*C*/
Node p = new Node(); /*Java*/
null
null
null
element
next
element
Set node data:
= element;
Set chain Link:
= next;
The Function isEmpty
/** ***@return true iff list is empty */
boolean isEmpty()
{return size == 0;}
The Function size()
/** ***@return current number of elements in list */
int size()
{return size;}
The Function Length()
Int getLength(Node *head)
{ Node p ; int i ;
if(head == null) return 0;
i = 0; p = head;
while(p !=null){
i++;
p = p->next;
}
return i;
}