不带头结点的单向链表的基本操作.pptx

不带头结点的单向链表的基本操作不带头结点的单向链表的基本操作初始化插入删除遍历一个基本操作对应一个函数假定链表上存放的是学生的数据（姓名，年龄）LWu 20Li 18He 20 ^链表操作所需自定义的数据类型 学生数据（姓名，年龄）typedef struct{ char name[20]; //存放姓名 int age; //存放年龄}STU;注意：上面省略了结构体名链表操作所需自定义的数据类型结点类型（学生数据类型，指针类型）指向结点的指针类型typedef struct node{ STU data; //存放学生数据 struct node *next; //存放下一个结点地址}NODE, *LINK;初始化操作功能：创建一个空链表初始条件：已知头指针变量（没有确定的值）操作结果：头指针变量为空，发生了改变操作前：L?操作后：L^初始化函数int initLink(LINK L){ L=NULL; return 1;}操作前：L?操作后：L^插入操作功能：在指定位置插入一个新的结点已知条件： 链表的头指针，插入的位置，插入的数据操作的结果： 链表上多了一个结点，链表的头指针可能改变。插入操作例：在i=2的位置上插入学生数据x（liu,19）21L操作前：Li 18He 20 ^操作后：21LLi 18He 20 ^liu 19pK=1插入操作例：在i=2的位置上插入学生数据x（liu,19）21L操作前：Li 18He 20 ^用工作指针p记住第i-1个结点的地址用k记p指向的结点序号步骤1：LLi 18He 20 ^p=L; k=1;while(p!=NULL ki-1){k++; p=p-next;}pK=1插入操作例：在i=2位置上插入学生数据x（liu,19）21L操作前：Li 18He 20 ^判断能否进行插入。如果i1,会出现ki-1,不能插入；如果i3，会出现p为空，不能插入。步骤2：LLi 18He 20 ^if(ki-1 || p==NULL) printf(“位置非法，不能插入\0”);pK=1②①sliu 19插入操作例：在i=2位置上插入学生数据x（liu,19）21L操作前：Li 18He 20 ^步骤3：生成新结点，将数据放入结点，插入到链表中。LLi 18He 20 ^s=new NODE;s-data=x;s-next=p-next;p-next=s;pK=1②①sliu 19插入操作例：在i=1位置上插入学生数据x（liu,19）21L操作前：Li 18He 20 ^步骤3：生成新结点，将数据放入结点，插入到链表中。LLi 18He 20 ^s=new NODE;s-data=x;s-next=L;L=s;插入函数int insertLink(LINK L, int i, STU x){ LINK p,s; int k; p=L; k=1; while(ki-1 p!=NULL){k++; p=p-next;} if(ki-1 || p==NULL) { printf(“位置非法，不能插入\n”); return 0; } s=new NODE; s-data=x; if(i==1) //插入的是第一个结点 { s-next=L; L=s; return 1; } //插入的不是第一个结点 s-next=p-next; p-next=s; return 1; }删除操作功能：将指定位置上的结点删除已知条件： 链表的头指针，删除的位置操作的结果： 链表上少了一个结点，链表的头指针可能改变。删除操作例：删除位置为i=1的结点21L操作前：Li 18He 20 ^操作后：1LHe 20 ^删除操作例：删除在i=1的位置上的学生21L操作前：Li 18He 20 ^用q记住第1个结点的地址，再删除q指向的结点，并释放空间步骤1：q21LLi 18He 20 ^ q=L; L=q-next; delete q;pK=1删除操作例：删除在i=2的位置上的学生21L操作前：Li 18He 20 ^用工作指针p记住第i-1个结点的地址用k记p指向的结点序号步骤1：LLi 18He 20 ^p=L; k=1;while( p-next!=NULL ki-1) { k++; p=p-next; }pK=1删除操作例：删除i=2位置上的结点21L操作前：Li 18He 20 ^步骤2：判断能否进行删除。如果i1,会出现ki-1,不能删除；如果i=3会出现 p-next为空，不能删除LLi 18He 20 ^if( ki-1 || p-next==NU