严蔚敏数据结构C语言版 P34 算法2.17
静态链表的插入:
由于严书静态链表写的不是很清楚(反正是可选章节得知道理解即可),这里采用大话数据结构的插入思想,当然还是自己理解敲出的,所以仅供参考
/*严蔚敏数据结构C语言版 P34 算法2.17静态链表的插入:由于严书静态链表写的不是很清楚(反正是可选章节得知道理解即可),这里采用大话数据结构的插入思想,当然还是自己理解敲出的,所以仅供参考*///头文件#include<stdio.h>#include<stdlib.h>//宏区#define SIZEMAXE 10//结构typedef struct{int data;int NEXT;}SqLink,PLink[SIZEMAXE];//函数声明void Null_link_list(PLink);//将静态链表初始化(先全挂在备用头结点下)int allot_Link_list(PLink);//分配空闲结点void Link_list_build(PLink);//静态链表的建立void Link_printf(PLink);//输出静态链表的值void Link_list_into(PLink);//静态链表的插入//函数区void Null_link_list(PLink Link)//将静态链表初始化(先全挂在备用头结点下){int i = 0;while (i < SIZEMAXE)//依次挂在备用头结点下{Link[i].NEXT = i + 1;//将下一个结点挂在前一个结点上i++;//记录i}Link[SIZEMAXE - 1].NEXT = NULL;//将最后的尾巴挂起}int allot_Link_list(PLink Link)//分配空闲结点{int i;if (i)//只要当前有分配的空间{i = Link[0].NEXT;//用个临时存储量存储可以分配的结点Link[0].NEXT = Link[i].NEXT;//将被分配结点的下一个结点挂在备用头结点下}if(NULL == i)//如果没有可分配的备用结点{printf("没有可分配的空闲结点了,请重新检查程序!\n");//提醒用户exit(0);//正常终止程序}return i;//返回被分配结点的下标}void Link_list_build(PLink Link)//静态链表的建立{int S;//用于指向表尾int val, j, wd;int i = allot_Link_list(Link);//分配头结点printf("输入要建立静态链表的结点个数(10 >= x > 0):");//提示用户scanf_s("%d", &val);//用户输入个数while (SIZEMAXE < val || val <= 0){printf("个数非法,重新输入结点个数(10 >= x > 0):");//提示用户scanf_s("%d", &val);//用户输入个数}S = i;//初始化移动游标for(j = 1;j <= val;j++){printf("输入第%d个结点的值:", j);//提示用户scanf_s("%d", &wd);//输入值S = allot_Link_list(Link);//分配空闲结点Link[S].data = wd;//将值赋给新结点Link[i].NEXT = S;//将新结点的值挂在前一个结点i = S;//游标移动}Link[S].NEXT = NULL;//将有效结点的尾结点的游标挂起}void Link_printf(PLink Link)//输出静态链表的值{int i = Link[1].NEXT;//i指向第一个有效静态结点printf("\n当前静态链表的数据为:");while (i)//节点不为NULL{printf("%d ", Link[i].data);//输出当前结点的数据i = Link[i].NEXT;//i指向下一结点的下标}printf("\n");}void Link_list_into(PLink Link)//静态链表的插入{int i, j, k, s, o;printf("输入插入的位置:");//提醒用户scanf_s("%d", &i);//记录插入的位置printf("输入插入的数据:");//提醒用户scanf_s("%d", &j);//记录插入的数据while (SIZEMAXE < i || i <= 0){printf("插入的位置非法,重新输入插入的位置:");//提醒用户scanf_s("%d", i);//重新记录插入的位置printf("插入的数据非法,重新输入插入的数据:");//提醒用户scanf_s("%d", j);//重新记录插入的数据}s = 1;//s是指向有效结点的头游标for (k = 1;k < i;k++)//找到插入结点的前一个结点{s = Link[k].NEXT;//s记录位置k++;//记录循环的次数}o = allot_Link_list(Link);//分配空闲结点Link[o].data = j;//数据发送给新分配的结点Link[o].NEXT = Link[s].NEXT;//新分配的结点指向插入位置的结点Link[s].NEXT = o;//原本插入位置的结点的前一个结点指向新分配的结点}//主函数int main(void){PLink Link;//创造空表Null_link_list(Link);//将静态链表初始化(先全挂在备用头结点下)Link_list_build(Link);//静态链表的建立Link_printf(Link);//输出静态链表的值Link_list_into(Link);//静态链表的插入Link_printf(Link);//输出静态链表的值return 0;}
这是本程序的头文件
//头文件#include<stdio.h>#include<stdlib.h>
这是本程序的宏区
//宏区#define SIZEMAXE 10
这是本程序的静态链表的结构
//结构typedef struct{int data;int NEXT;}SqLink,PLink[SIZEMAXE];
这是本程序的函数声明:
//函数声明void Null_link_list(PLink);//将静态链表初始化(先全挂在备用头结点下)int allot_Link_list(PLink);//分配空闲结点void Link_list_build(PLink);//静态链表的建立void Link_printf(PLink);//输出静态链表的值void Link_list_into(PLink);//静态链表的插入
这是本程序的静态链表初始化(先全挂在备用头结点下):
void Null_link_list(PLink Link)//将静态链表初始化(先全挂在备用头结点下){int i = 0;while (i < SIZEMAXE)//依次挂在备用头结点下{Link[i].NEXT = i + 1;//将下一个结点挂在前一个结点上i++;//记录i}Link[SIZEMAXE - 1].NEXT = NULL;//将最后的尾巴挂起}
这是本程序的分配空闲结点:
int allot_Link_list(PLink Link)//分配空闲结点{int i;if (NULL != Link[0].NEXT)//只要当前有分配的空间{i = Link[0].NEXT;//用个临时存储量存储可以分配的结点Link[0].NEXT = Link[i].NEXT;//将被分配结点的下一个结点挂在备用头结点下}else//如果没有可分配的备用结点{printf("没有可分配的空闲结点了,请重新检查程序!\n");//提醒用户exit(0);//正常终止程序}return i;//返回被分配结点的下标}
这是本程序的静态链表的建立
void Link_list_build(PLink Link)//静态链表的建立{int S;//用于指向表尾int val, j, wd;int i = allot_Link_list(Link);//分配头结点printf("输入要建立静态链表的结点个数(10 >= x > 0):");//提示用户scanf_s("%d", &val);//用户输入个数while (SIZEMAXE < val || val <= 0){printf("个数非法,重新输入结点个数(10 >= x > 0):");//提示用户scanf_s("%d", &val);//用户输入个数}S = i;//初始化移动游标for(j = 1;j <= val;j++){printf("输入第%d个结点的值:", j);//提示用户scanf_s("%d", &wd);//输入值S = allot_Link_list(Link);//分配空闲结点Link[S].data = wd;//将值赋给新结点Link[i].NEXT = S;//将新结点的值挂在前一个结点i = S;//游标移动}Link[S].NEXT = NULL;//将有效结点的尾结点的游标挂起}
这是本程序的插入操作:
void Link_list_into(PLink Link)//静态链表的插入{int i, j, k, s, o;printf("输入插入的位置:");//提醒用户scanf_s("%d", &i);//记录插入的位置printf("输入插入的数据:");//提醒用户scanf_s("%d", &j);//记录插入的数据while (SIZEMAXE < i || i <= 0){printf("插入的位置非法,重新输入插入的位置:");//提醒用户scanf_s("%d", i);//重新记录插入的位置printf("插入的数据非法,重新输入插入的数据:");//提醒用户scanf_s("%d", j);//重新记录插入的数据}s = 1;//s是指向有效结点的头游标for (k = 1;k < i;k++)//找到插入结点的前一个结点{s = Link[k].NEXT;//s记录位置k++;//记录循环的次数}o = allot_Link_list(Link);//分配空闲结点Link[o].data = j;//数据发送给新分配的结点Link[o].NEXT = Link[s].NEXT;//新分配的结点指向插入位置的结点Link[s].NEXT = o;//原本插入位置的结点的前一个结点指向新分配的结点}
这是本程序的输出静态链表的值
void Link_printf(PLink Link)//输出静态链表的值{int i = Link[1].NEXT;//i指向第一个有效静态结点printf("\n当前静态链表的数据为:");while (i)//节点不为NULL{printf("%d ", Link[i].data);//输出当前结点的数据i = Link[i].NEXT;//i指向下一结点的下标}printf("\n");}
这是本程序的主函数部分:
int main(void){PLink Link;//创造空表Null_link_list(Link);//将静态链表初始化(先全挂在备用头结点下)Link_list_build(Link);//静态链表的建立Link_printf(Link);//输出静态链表的值Link_list_into(Link);//静态链表的插入Link_printf(Link);//输出静态链表的值return 0;}
模块处理,方便观看理解程序~
感谢观看
再次感谢~