ds2.3.1陆小马功钟浩.ppt

§2.3 线性表的链式表示和实现 （一）单链表及其实现 §2.3 线性表的链式表示和实现 线性链表及其特点 单链表的类型定义 单链表基本操作的实现 在单链表中插入元素 在单链表中删除元素 建立单链表的两种方法 清空和销毁单链表 顺序表和单链表的比较 1.线性链表及其特点 顺序表的缺点 线性链表——线性表的链式存储结构 结点，数据域，指针域 n个结点连接成链表，单链表 头指针，头结点 1.线性链表及其特点 线性链表的特点 空间上：可以使用离散的空间 时间上：只能从头指针开始顺序访问，不能随机访问。 2.单链表的类型定义 单链表结点的类型定义 struct LNode { ElemType data; //数据域 LNode *next; //指针域 }; 单链表 typedef LNode *LinkList; 3.单链表基本操作的实现 （1）初始化空表 InitList(L) 分配头结点，并令其指针域为空。 Status InitList ( LinkList L ) { L = malloc(sizeof(LNode)); //分配头结点 if ( L==NULL ) exit(1); L-next = NULL; //头结点指针域为空 return OK; } 3.单链表基本操作的实现 （2）判空 ListEmpty(L) 检查头结点指针域是否为空。 Status ListEmpty ( LinkList L ) { if ( L-next == NULL ) return TRUE; else return FALSE; } 3.单链表基本操作的实现 （3）求长度 ListLength(L) 令指针p沿着链表移动，同时对元素进行计数。 int ListLength ( LinkList L ) { j = 0; //计数器 p = L-next; while ( p ) { j++; //计数 p = p-next; //沿链表移动到下一个元素 } return j; //元素个数 } 3.单链表基本操作的实现 遍历链表（依次访问链表中的元素）的方法 p = L-next; while ( p ) { … //操作p指向的结点 p = p-next; //沿链表移动到下一个元素 } 3.单链表基本操作的实现 （4）元素定位 Locate(L,e) 遍历链表，找到元素e则返回位序， int LocateElem ( LinkList L, ElemType e ) { j = 0; //计算位序 p = L-next; while ( p ) { j++; if ( p-data==e ) return j; //返回位序 p = p-next; } return 0; //没找到 } int LocateElem ( LinkList L, ElemType e ) { p = L-next; j = 1; // j用于伴随计数 while ( p p-data!=e ) { p = p-next; j++; } if ( p ) return j; else return 0; } 3.单链表基本操作的实现 （5）取元素 Get(L,i,e) Status GetElem ( LinkList L, int i, ElemType e ) { p = L-next; j = 1; while ( p ji ) { p = p-next; j++; } if ( p j==i ) { e = p-data; //取出并返回数据 return OK; } else return ERROR; } 4.在单链表中插入元素ListInsert(L,i,e) （1）如何插入第i个元素？ 4.在单链表中插入元素ListInsert(L,i,e) （1）如何插入第i个元素？ 4.在单链表中插入元素ListInsert(L,i,e) （2）算法 令p指向ai-1（ai的前驱） 新建结点s（数据域为e） 在p之后插入新结点s（修改两个指针） Status ListInsert ( LinkList L, int i, ElemType e ) { //令p指向第i-1个结点 p = L; j = 0; while ( p ji-1 ) { p = p-next; j++; } if ( p j==i-1 ) { //新建结点s s = malloc(sizeof(LNode)); if ( s==NULL ) exi