数据结构教程 第七课 第八课 线性表的链式表示与实现.doc

本课主题： 实验一 线性表的顺序存储实验教学目的： 掌握顺序表的定义及操作的C语言实现方法教学重点： 顺序表的操作的C语言实现方法教学难点： 顺序表的操作的C语言实现方法实验内容：利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。实验要求：在上机前写出全部源程序。本课主题： 线性表的链式表示与实现教学目的： 掌握线性链表、单链表、静态链表的概念、表示及实现方法教学重点： 线性链表之单链表的表示及实现方法。教学难点： 线性链表的概念。授课内容：一、复习顺序表的定义。二、线性链表的概念：以链式结构存储的线性表称之为线性链表。特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象，称为结点。2000:10002000:10102000:10202000:10302000:10402000:10502000:1060.2000:4000头指针2000:10062000:1030a32000:1040a6NULLa12000:1060a42000:1050a52000:1020a22000:1010数据域指针域next=NULL;return 1;else return 0;2插入操作Status ListInsert_L(LinkList &L,int i,ElemType e)p=L,j=0;while(p&jnext;+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_L3删除操作Status ListDelete_L(LinkList &L,int i,ElemType &e)p=L,j=0;while(p&jnext;+j;if(!p-next|ji-1) return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;/ListDelete_L4取某序号元素的操作Status GetElem_L(LinkList &L,int i,ElemType &e)p=L-next,j=1;while(p&jnext;+j;if(!p|ji) return ERROR;e=p-data;return OK;/GetElem_L5归并两个单链表的算法void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)/已知单链线性表La和Lb的元素按值非递减排列/归并后得到新的单链线性表Lc,元素也按值非递减排列pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=p