华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 线性表（2/2）2.3 线性表的链式存储结构

数据结构华中科技大学计算机学院(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为指针类型 }；

初始化: headl输入2:ha-bm12 、③ ail tail 输入8:hed-Dm2 tail 每次输入新元素后: 生成新结点;p= malloc((结点大小);p->data=e;p→next=NULL; ②添加到表尾;tail-> next=p 设置新表尾。tail-p;

初始化：head //// ^ 输入2： head //// tail tail 2 ^ p ① ③ ② 每次输入新元素后： • 生成新结点；p=malloc(结点大小）; p->data=e; p->next=NULL; ② 添加到表尾；tail->next=p; ③ 设置新表尾。tail=p; head //// tail 8 ^ ① ③ ② 输入8： 2 p

先进先出表的产生过程(1,2,3,40) head 4 0 头指针头结点、 head=malloc(sizeof(struct node)) p=malloc(sizeof(struct node)) tail=head tail->next=p =malloc(sizeof(struct node)) tail=p tail->next=p ail-p tail->next=NULL:

先进先出表的产生过程(1,2,3,4,0)： head p /// 1 2 3 4 0 p p p p 头指针 头结点 tail head=malloc(sizeof(struct node)) tail=head tail p=malloc(sizeof(struct node)) tail->next=p tail=p p=malloc(sizeof(struct node)) tail tail->next=p tail=p tail tail tail tail->next=NULL; ^

算法:生成“先进先出”单链表(链式队列) struct Lnode *creatI() struct lnode*head,*tail,*p;//变量说明 int e: head=( struct lnode*) malloc(LENG);//生成表头结点 tail=head: //尾指针指向表头 do{p=( struct lnode米) malloc(LENG);//生成新结点 scanf(%d,&e);/输入一个数 p->data=e //装入输入的元素e tail->next=p //新结点链接到表尾 all-p; //尾指针指向新结点 while(e!=0) //不为0 tail->next=NULL //尾结点的next置为空指针 return head //返回头指针

算法：生成“先进先出”单链表（链式队列） struct Lnode *creat1( ) { struct Lnode *head,*tail,*p； //变量说明 int e； head=(struct Lnode *)malloc(LENG)； //生成表头结点 tail=head； //尾指针指向表头 do{ p=(struct Lnode *)malloc(LENG)；//生成新结点 scanf(“%d”,&e)； //输入一个数 p->data=e； //装入输入的元素e tail->next=p； //新结点链接到表尾 tail=p； //尾指针指向新结点 } while (e!=0)； //不为0 tail->next=NULL； //尾结点的next置为空指针 return head； //返回头指针 }

例2生成“后进先出”单链表(链式栈)。输入:2,8,5,0,生成: head 0 5 8 2∧ 算法: struct Lnode *creat() //生成“后进先出”单链表 I struct Lnode *head, *p head=( struct lnode*) malloc(LENG);/生成表头结点 head->next=NULL //置为空表 do {p=( struct lnode*) malloc(LENG);//生成新结点 scanf(%d3,&(p>data);//输入数,送新结点的data p->next=head->next //新结点插入表头结点之后 head->next=p //尾指针指向新结点 } while(p>data!=0);//不为0 return head //返回头指针

例2 生成“后进先出”单链表(链式栈)。输入:2,8,5,0,生成： head --→ /// --→ 0 --→ 5 --→ 8 --→ 2 ∧ 算法： struct Lnode *creat2( ) //生成“后进先出”单链表 { struct Lnode *head,*p； head=(struct Lnode *)malloc(LENG)；//生成表头结点 head->next=NULL； //置为空表 do { p=(struct Lnode *)malloc(LENG)；//生成新结点 scanf(“%d”,&(p->data))；//输入数,送新结点的data p->next=head->next； //新结点插入表头结点之后 head->next=p； //尾指针指向新结点 } while (p->data!=0)； //不为0 return head； //返回头指针 }

初始化: headm输入2: headw2 输入8:head-m 每次输入新元素后: 生成新结点; p=mall(结点大小);p->data=e; ②新结点指针指向首元素;p->next-head->next 新结点作为首元素:head->next=p

初始化：head //// ^ 输入2： head //// 2 ^ p ① ② 每次输入新元素后： • 生成新结点； p=malloc(结点大小）; p->data=e; ② 新结点指针指向首元素；p->next=head->next; ③ 新结点作为首元素： head->next=p; head //// 2 ^ ① ② 8 输入8： p ③ ③