[工学]02--线性表.ppt

Typedef int datatype; typedef struct node /*结点类型定义*/ {datatype data; /*数据域*/ struct node *next; }JD; /*next为指针域， 指向该结点的后继*/ JD *head,*p; /*指针类型说明*/ 指针p与指向的结点关系示意图： p 结点 (*p) 说明： p---指向链表中某一结点的指针。 *p---表示 由指针p所指向的结点。 (*p).data或p-data----表示由p所指向结点的数据域。 (*p).next或p-next----表示由p所指向结点的指针域。 P=(JD*)malloc(sizeof(JD))---- 对指针p赋值使其指向某一结点（按需生成一个JD结点类型的新结点）。 其中： (JD*)----进行类型转换。 Sizeof(JD)---求结点需用占用的字节数。 Malloc(size)--在内存中分配size个连续可用字节的空间。 Free(p)--系统回收p结点。（动态） ? 单链表的基本运算 （1）建立单链表之 -------①头插法建表： 思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域 中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 算法思想：将新结点插入到当前链表的表尾上，可增加一个尾指针r，使其始终指向链表的尾结点。 p 头、尾插法建表分析： 上述头、尾插法建表由于没有生成（附 加）头结点，因此开始结点和其它结点 的插入处理并不一样，原因是开始结点 的位置存放在头指针中，而其余结点的 位置是在其前趋结点的指针域 。 ③尾插法建表的改进算法 思想： 设头结点，使第一个结点和其余结点的插入操作一致。 （表）头结点（在第一个结点之前附设） ---其指针域 存贮指向第一个结点的指针（即第一个结点的存贮位置）。 头结点的数据域：可有可无 头结点的指针域：指向第一个结点的指针。 ①按序号查找 设单链表的长度为n，要查找表中第I个结点，算法思想如下： 从头结点开始顺链扫描，用指针p指向当前扫描到的结点，用j作统计已扫描结点数的计数器，当p扫描下一个结点时，j自动加1。 P的初值指向头结点，j的初值为0。 当j=I时，指针p所指的结点就是第I个结点。 datatype GetElem_L(JD *L, int i, datatype e) { JD *P; int j； p = L; j = 0; while(p j i){ p = p -next; ++j; } if (! P || j i) return ERROR; /*第i个元素不存在*/ e = p-data; return OK; }//GetElem_L ②按值查找： 在链表中，查找是否有结点等于给定值key的结点，若有的话，则返回首次找到的值为key的结点的存储位置；否则返回null. 算法思想： 从开始结点出发，顺链逐个结点的值和给定值key作比较。 算法描述（略） 设指针p指向单链表的某一确定的结点，指针s指向等待插入的、其值为x的新结点。 （两种操作）： ①后插--将新结点*s插入结点*p之后。 ②前插--将新结点*s插入结点*p之前。 算法思想：取一新结点，将其数据域置为新结点，再修改有关结点的链域： 把原p结点的直接后继结点作为s结点的直接后继，s结点作为p结点的直接后继。 先找到p结点的前趋结点（单链表无前趋指针），然后修改其链域，使其指向待插入的s结点，而将s结点指向p结点。 ?单链表的基本运算 (4)删除运算 Datatype ListDelete_L(JD* L, int i , datatpye e) {//在带头结点的单链线性表L中，删除第i个元素，并由e返回 JD*p ; int j; p = L ; j = 0; while (p-next j i-1) {//寻找第i个结点,并令p指向