数据结构华中科技大学计算机学院(3) 2001-3-12
数据结构 华中科技大学计算机学院(3) ------------------------------------------------ 2001-3-12
2.3线性表的链式存储结构 2.3.1单链表 1单链表的结点结构 data next 前驱a(-) 一后继a(+1 结点类型说明 例1C语言的“结构”类型 struct node I ElemType data //data为抽象元素类型 struct node米next;//next为指针类型 指向结点的指针变量head,p,q说明: struct node *head, *p, *q
2.3 线性表的链式存储结构 2.3.1单链表 1 单链表的结点结构: data next 前驱a(i-1) ─→ ai ─→后继a(i+1) 结点类型说明 例1 C语言的“结构”类型： struct node { ElemType data； //data为抽象元素类型 struct node *next； //next为指针类型 }； 指向结点的指针变量head,p,q说明: struct node *head,*p,*q；
例2用 typedef定义指针类型 typedef struct lnode i Elem Type data //data为抽象元素类型 struct node米next;//next为指针类型 1 *Linklist 指针变量head,p,q的说明 Linklist head, p, g; 2.单链表的一般形式: (1)不带表头结点的单链表: data next head a2 an∧ 头指针 首结点 尾结点 其中:data称为数据域,next称为指针域/链域 当head=NUL,为空表;否则为非空表
例2 用typedef定义指针类型: typedef struct Lnode { ElemType data； //data为抽象元素类型 struct node *next； //next为指针类型 } *Linklist； 指针变量head,p,q的说明: Linklist head,p,q； 2.单链表的一般形式: (1)不带表头结点的单链表： data next head ---→ a1 ---→ a2 --→ ...--→ an ∧ 头指针 首结点 尾结点 其中：data称为数据域，next称为指针域/链域 当 head==NULL,为空表；否则为非空表
(2)带表头结点的单链表: a.非空表 data next head--→// al an ∧ 头指针表头结点首结点 尾结点 b.空表: data next head //∧ 头指针表头结点 其中:head指向表头结点, head->data不放元素, head->next指向首结点a1, 当head>next=NULL,为空表;否则为非空表
(2)带表头结点的单链表： a.非空表: data next head ---→ /// --→ a1 --→...--→ an ∧ 头指针 表头结点 首结点 尾结点 b.空表: data next head ---→ /// ∧ 头指针 表头结点 其中：head指向表头结点， head->data不放元素， head->next指向首结点a1, 当head->next==NULL,为空表；否则为非空表
3.单链表操作和算法举例: (1)生成单链表 例1输入一列整数,以0为结束标志,生成“先进先出”单链 表。 若输入:2,8,5,0,则生成: tail head #define null o /定义符号常量NUL # define leng sizeof( struct lnode)//结点所占的单元数 struct lnode //定义结点类型 i int data //data为整型 struct node next //next为指针类型
3.单链表操作和算法举例： (1) 生成单链表。 例1 输入一列整数，以0为结束标志,生成“先进先出”单链 表。 若输入：2,8,5,0，则生成： tail ↓ head -→ /// --→ 2 --→ 8 --→ 5 --→ 0 ∧ #define NULL 0 //定义符号常量NULL #define LENG sizeof(struct Lnode) //结点所占的单元数 struct Lnode //定义结点类型 { int data； //data为整型 struct node *next； //next为指针类型 }；