25计算机考研,数据结构知识点整理(内容借鉴了王道408+数据结构教材),还会不断完善所整理的内容,后续的内容也会不断更新(可以关注),若有错误和不足欢迎各位朋友指出!
目录
一.头插法建表(前插法)
1.算法思想
2.算法描述
二.尾差法建立(后插法)
1.算法思想
2.算法描述
常见的见表方法有头插法和尾插法
一.头插法建表(前插法)
1.算法思想
①从一个空表开始,每次读入数据
②生成新结点,将读入的数据存放到新结点的数据域中
③然后将新结点插入当前链表的表头结点之后,直到结束标志为止。
2.算法描述
void CreateFromHead(LinkList L)
/*L是带头结点的空链表头指针,通过键盘输人表中元素值,利用头插法建单链表L*/
{Node *s;char c;int flag=l;while( flag)/*fag初值为1,当输人“$”时置flag为0,建表结束*/{c=getchar();if(c!='$') { s=(Node * )malloc(sizeof(Node)); /*建立新结点s*/s->data=c;s->next=L->next;/*将s结点插入表头*/L->next=s;}else flag=0;}
}
采用头插法建立单链表时,读入数据的顺序与生成的链表中元素的顺序是相反的,可用来实现链表的逆置,亦称头插法建表为逆序建表法,每个结点插入的时间为O(1),设单链表长为n,则总时间复杂度为O(n)。
注意:在上述算法中L是指向单链表的头指针,习惯上称为单链表L。
二.尾差法建立(后插法)
1.算法思想
头插法建立单链表虽然算法简单,但生成的单链表中结点的次序与输入顺相反。若希望二者顺序一致,采用尾插法建表,即将新结点插到当前单链表的表尾上。为此需增加一个尾指针r,使之指向当前单链表的表尾。使用尾插法建立单链表的过程如图2.10所示。
2.算法描述
void CreateFromTail(linkList L)
/*L是带头结点的空链表头指针,通过键盘输人元素值,利用尾插法建单链表L*/{Node *r,*s;int fag=1; /*设置一个标志,初值为1,当输人“$”时fag为0,建表结束*/r=L; /*r指针动态指向链表的当前表尾,以便做尾插人*/while(flag) /*循环输人表中元素值,将建立新结点s插人表尾*/{c=getchar( );if(c!='$'){s=(Node * )malloc(sizeof(Node));s->data=c;r->next=s; //插入到表尾r=s; //r指向新的尾结点}else{flag=0;r->next=NULL; /*将最后一个结点的next链域置为空,表示链表结束*/}
}
因为附设了一个指问表尾结点的指针,所以时间复杂度和头插法的相同