数据结构与算法第二章线性表（二）
内容提要
z线性表的概念（逻辑结构）
z线性表的顺序表示和实现（顺序表）z线性表的链式表示和实现（链表）z线性表的应用
线性表的链式表示和实现
z单链表
z循环链表
z双向链表
单链表
z线性表的链式表示
z单链表的基本运算
z单链表的完整程序示例
z头结点的作用
数据域指针域
3143Zhou25
typedef struct Node *PLinkList ; /* 单链表指针类型*/
空表判断：plist->link == NULL
单链表
z线性表的链式表示
z单链表的基本运算
z单链表的完整程序示例
z头结点的作用
单链表基本运算及其实现
•创建空的单链表Plinklist createNullList_link(void)
•int insertPost link( PLinkList pllist, PNode p, DataType x)插入结点se os_(s p s,Node p,ype) int insertPre_link( PLinkList pllist, PNode p, DataType x)
int insert link( PLinkList pllist, int i, DataType x)
_(p,,yp)
•删除结点int deleteV_link(PLinkList pllist, DataType x)
int deleteP_link(PLinkList pllist, PNode p)
•定位运算PNode locate_link(PlinkList pllist, DataType x)
PNode locatePre_link(PlinkList pllist, DataType x)
PNode find_link( PLinkList pllist, int i)
•判空运算isNullList_Link(PLinkList pllist)
单链表的基本运算
z创建
z判空
z插入
z删除
z取值
z查找
链表的定义
z
运算的实现
{数据域可以有多个信息。
{数据说明
struct Node;/* 单链表结点类型*/
typedef struct Node *PNode;/* 结点指针类型*/ struct Node /* 单链表结点结构*/
{ DataType info;
PNode link; };
typedef struct Node *PLinkList ; /* 单链表指针类型*/
13
建立带有头节点的空链表z函数名：createNulllist_link
z功能: 建立带有头节点的空链表
z程序：
PLinkList createNulllist link
PLinkList createNulllist_link(void)
{ PLinkList pllist;
pllist =(PLinkList) malloc (sizeof(struct Node) );
/*申请表头结点空间*/
if(pllist ! = NULL) pllist ->link = NULL;
if(pllist ! = NULL) pllist >
else printf(“out of space!\n”);
t (lli t)
return (pllist);
}
单链表的基本运算
z创建
z判空
z插入
z删除
z取值
z查找
判断单链表是否为空
z函数名：isNulllist_link
z功能: 判断带头结点的单链表pllist是否为空链
lli t
表。
z程序：
int isNulllist_link(PLinklist pllist)
int isNulllist link
{ return (pllist->link==NULL);
}
单链表的基本运算
z创建
z判空
z插入
z删除
z取值
z查找
ld
在单链表中插入值为x 的元素-old z 函数名：insertPre_link
z 功能:在pllist 带头结点的单链表中下标为i(第i+1个)的结点前插入一个值为ｘ的元素，并返回插入成功与否的标志。程序
z 程序：int insert_link( PLinkList pllist, int i, DataType x) a b
p
a
b p
>inf x;
单链表
q->info=x;q->link = p-> link;p > link = q;x
q
p-> link = q;
int insertPre_link(PLinkList pllist,int i,DataType x)
p q;{PNode p,q;p =pllist;int j=0;while(p!=null &&j {p=p->link;j++;}if(j!=i)/*查找失败*/ j {printf(“i=%d is not reasonable.\n”,i);return 0;} /**/q =(PNode)malloc(sizeof(struct Node ));/申请新节点/ if (q ==null ) /*申请失败*/{printf("Out of space!!!\n");return 0;} else /*插入链表中*/ { q->info =x;q->link =p->link;p->link =q; a p return 1; } }a b 演示
