事业单位考试计算机基础知识:建立单链表——有序单链表
【导语】在事业单位考试中,计算机专业知识的复习向来是考生复习备考阶段的一大重点,其中中公为计算机基础知识的复习为考生提供知识点梳理,帮助考生备考!
有序单链表:是指原表中结点的数据值,按从小到大(或从大到小)的顺序排列。为了建立一个有序单链表,每次生成的新结点,总是插入到当前链表的合适位置。在带表头结点的单链表中,所有位置上的插入操作都是一致的,不需要做特殊处理。
若用换行符‘n’作为输入结束标志,pre为指向当前结点前件的指针、cur为指向当前结点的指针,则建立带表头结点的有序单链表的算法如下:
LinkList CreateList_or( )
{
LinkList H,pre,cur; /*pre将指向当前结点的前件,cur将指向当前结点*/
char ch;
H =(LinkList)malloc(sizeof(
ListNode)); /*生成表头结点*/
if(!H)
{ printf("n 存储分配失败");
exit(1);
}
H->next=NULL;/*表初值为空*/
while((ch=getchar( ))!=’n’)
{
pre=H;/*pre指向当前结点的前件*/
cur=H->next;/*cur指当前结点*/
while(cur&&cur->data
/*找出新结点在表中的合适位置*/
{
pre=cur;
cur=cur->next;
}
cur=(LinkList)malloc(sizeof(
ListNode)); /*生成新结点*/
if(!cur)
{
printf("n 存储分配失败");
exit(1);
}
cur->data=ch;
cur->next=pre->next; /*新结点插在pre所指结点的后面*/
pre->next=cur;/*尾指针指向新结点*/
}
return(H); /*返回头指针*/
}
容易看出,以上3个算法的时间复杂度均为O(n)。
更多相关信息请访问事业单位考试资料网
欢迎关注(中公教育事业单位招聘考试频道)
及时掌握事业单位招聘考试信息
回复“2022”领取备考大礼包
声明:本站点发布的来源标注为“中公教育”的文章,版权均属中公教育所有,未经允许不得转载。
如果对你有帮助的话,就点个赞吧!





