C语言程序设计与数据结构.ppt

线性表的链式存储
主讲教师--胡运玲
一、单链表
二、带头结点的单链表的构造及操作
三、其它形式的链表
用一组地址任意的存储单元存放线性表中的数据元素。
一、单链表
以元素+ 指针= 结点
以“结点的序列”表示线性表称作链表
数据元素
指针
以线性表中第一个数据元素的存储地址作为线性表的地址,称作线性表的头指针
头结点
a1 a2 …... an ^
头指针
头指针
有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针
空指针
线性表为空表时,
头结点的指针域为空

Typedef struct LNode {
int data; // 数据域
struct Lnode *next; // 指针域
} NODE;
结点和单链表的 C 语言描述
NODE *head;// head为单链表的头指针
1、单链表的构造
构造方法有两种:
一种是在单链表的头部插入结点
按输入数据的逆序构造。
另一种是在单链表的尾端插入结点
按输入数据的顺序构造。
二、带头结点的单链表的构造及操作
在单链表的尾端插入结点构造链表(C语言实现)
Initlist(int n)
{
int i;
NODE *p,*q;
head=(NODE *)malloc(sizeof(NODE));
q=head; // q指向头节点
for(i=1;i<=n;i++)
{
p=(NODE *)malloc(sizeof(NODE));
// p指向新生成的新结点
scanf("%d",&p->data);
q->next=p; q=p; // 将p指向的结点连在链表的尾端
}
q->next=NULL; // 链表的尾端
}
构造存放线性表(25,45,18)的链表.
head
q
p
25
q
p
45
q
p
18
q
2、单链表操作的实现
GetElem(L, i, e) // 取第i个数据元素
ListInsert(&L, i, e) // 插入数据元素
ListDelete(&L, i, e) // 删除数据元素
ClearList(&L) // 重置线性表为空表
CreateList(&L, n)
// 生成含 n 个数据元素的链表