第 四 讲 线性表（二）

教学目标 理解线性表的链式存储结构； 掌握链式线性表中的结点类型定义； 熟练掌握线性表的基本操作在链式存储结构上实现； 理解循环链表和双向链表的基本概念及其操作。 2/19

2.3 线性表的链式表示与实现 a1 a2 an a3 … 数据元素和结点 数据域和指针域 单向链表 3/19

头指针、空指针和头结点 头指针 空指针 头结点 L a1 a2 a3 L a1 a2 a3 4/19

结点类型定义 a1 a2 an a3 … data next typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; 讨论：LNode与LinkList的区别是什么？ 5/19

初始化操作 Status InitList(LinkList &L){ L = (LinkList) malloc(sizeof(LNode)); if (L==NULL) return 0; L->next = NULL; return OK; } L 算法的时间复杂度为：O(1)。 6/19

查询操作GetElem(L, i, &e) 算法的时间复杂度为：O(ListLength(L))。 Status GetElem_L(LinkList L, int i, ElemType &e) { // L为带头结点的单链表的头指针。取得第i个数据元素给e，成功返回OK,否则返回ERROR p = L->next; j = 1; // 初始化 while (p！=NULL && j<i) { // 顺指针向后查找第i个元素 p = p->next; ++j; } if ( !p ||j>i) return ERROR; // 第i个元素不存在 e = p->data; // 取第i个元素 return OK; } // GetElem_L j=1 算法的时间复杂度为：O(ListLength(L))。 7/19

插入操作ListInsert(&L, i, e) s=(LinkList)malloc(sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; s 8/19

Status ListInsert_L(LinkList &L, int i, ElemType e) // 在带头结点单链表L中第i个数据元素之前插入数据元素e p = L; j = 0; // 初始化 while (p && j < i-1) { p = p->next; ++j; } // 寻找第i-1个结点 if (!p || j > i-1) return ERROR; // i小于1或者大于表长 s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e; s->next = p->next; p->next = s; // 插入L中 return OK; } // LinstInsert_L 算法的时间复杂度为：O(ListLength(L))。 思考题：如果没有头结头，则应该如何实现？ 9/19

删除操作ListDelete_L(&L, i, &e) q = p->next; p->next = p->next->next; e=q->data; free(q); ^ 10/19

Status ListDelete_L(LinkList &L,int i,ElemType &e) 　//在带头结点的单链表 L 中删除第 i 个结点，并用 e 返回该结点中 //数据元素的值，查找第 i 个结点并使 p 指向其直接前趋 　p=L; j=0; // 初始化 while (p&&j<i-1) {p=p->next; ++j;} 　if (p==NULL||j>i-1) return ERROR;　// i 值非法 if(p->next != NULL){ 　q=p->next;　//令 q 指向待删结点 　p->next=q->next;　//在链表中删除结点 　e=q->data;　//用 e 返回被删结点中元素值 　free(q); //释放空间 } 　return OK; }//ListDelete_L 算法的时间复杂度为：O(ListLength(L))。 11/19

在链表的头部插入结点建立单链表 Status Creat_LinkList((LinkList &L,int n){ // 输入数据建立单链表，要求从头部插入结点 L = (LinkList) malloc(sizeof(LNode)); L->next=NULL; // 初始化 for(i=n; i>0; i--) { p = (LinkList) malloc(sizeof(LNode)); scanf (& p->data ); p->next=L->next; L->next=p; } return OK; 12/19

链式存储结构的优缺点 链式存储结构的优点是插入和删除操作不需要移动大量结点。 链式存储结构的缺点是必须从链表头部开始顺序查找 。 13/19

循环链表 单向链表 p->next!=NULL 循环链表p->next==head 单向链表与循环链表的主要区别是循环结束条件不同 单向链表 p->next!=NULL 循环链表p->next==head 14/19

双向链表 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *pre; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; 15/19

双向链表的插入操作 s = (DuLinkList)malloc(sizeof(DuLNode)); s->next = p->next; p->next->pre = s; s->pre = p; p>next = s; 16/19

双向链表的删除操作 q=p->next; p->next=q->next; q->next->pre=p; free(q); 17/19

小结 本讲主要介绍了线性链表的基本概念以及插入和删除等基本操作在线性链表上的实现，循环链表和双向链表的基本概念及其基本操作。重点介绍了头结点的作用以及插入和删除操作在线性链表上的实现。 18/19

作业与实验 作业 实验 设链式线性表中的数据已递增有序，要求设计一个算法将数据x插入到线性表的适当位置上以保持线性表的有序性。 编写程序创建一个保存学生基本信息的单链表，实现学生信息的插入、删除、查看等功能。 实验 实验一：线性表的基本操作及其应用 19/19