数据结构线性表课件.pptVIP

2.3 线性表的链式表示及实现 2.3.1 单链表： 数据域 指针域 存储地址 数据域 指针域 1 Li 43 7 Qian 13 13 Sun 1 19 Wang NULL 25 Wu 37 31 Zhao 7 37 Zheng 19 43 Zhou 25 31 头指针H 2.3 线性表的链式表示及实现 单链表： 线性链表的逻辑状态 Li Zhao Qian Sun Zhou Wu Zheng Wang ^ H 2.3 线性表的链式表示及实现 单链表： a1 an ^ a2 ... 头指针H 头结点 H ^ 非空表 空表 二、线性链表的定义 typedef int DataType; /* 定义元素类型为整型，也可定义为其他类型 */ struct LNode; /* 单链表结点类型 */ typedef struct LNode *PNode; /* 结点指针类型 */ struct LNode /* 单链表结点结构 */ { ElemType data; LNode *next; }; 2.3 线性表的链式表示及实现 2.3 线性表的链式表示及实现 基本操作：1.取元素 Status GetElem_L(LinkList L, int i, ElemType e){ // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p=L-next; j=1; while (p ji) { p=p-next; ++j; } if (!p || ji) return ERROR; e= p-data; return OK; } //GetElem_L 单链表结点插入和删除时的情形 2.3 线性表的链式表示及实现 a b p 单链表 a b p c s-next = p-next; ? 注：顺序不能反 单链表插入结点时的情况 p-next = p-next-next; 单链表删除结点时的情况 a b x s p ? p-next = s; 2.3 线性表的链式表示及实现 2.插入元素 Status ListInsert_L(LinkList L, int i, ElemType e){ //在L中第i个元素之前插入元素e p = L; j = 0; while (p ji-1) {p=p-next; ++j;} if (!p || ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s-data = e; s-next = p-next; p-next = s; return OK; }//ListInsert_L 2.3 线性表的链式表示及实现 3.删除元素 Status ListDelete_L(LinkList L, int i, ElemType e){ //在L中删除第i个元素，并由e返回其值 p = L; j = 0; while (p-next ji-1) {p=p-next; ++j;} if (!(p-next) || ji-1) return ERROR; q=p-next; p-next = q-next; e=q-data; free(q); return OK; }//ListDelete_L 2.3 线性表的链式表示及实现 4.创建链表 Void CreateList_L(LinkList L, int n){ /* 创建一个带头结点的链表 */ L=(LinkList)malloc(sizeof(LNode)); L-next=NULL; for (i=n; i0; --i){ p= (LinkList)malloc( sizeof(LNode) ); scanf (p-data); p-next=L-next; L-next = p; } } // CreateList_L 5.将两个有序链表归并为一个新的有序链表。 分析：有两个非递减有序链表La, Lb. 现归并La, Lb得到Lc。其条件为大于前者，不小于后者 Void MergeList_L(LinkList Lc, LinkList La,