IT评测·应用市场-qidao123.com

标题: 【考研数据布局——C语言描述】第二章线性表链式存储布局上的根本操作—— [打印本页]

作者: 写过一篇 时间: 2024-6-27 20:48
标题: 【考研数据布局——C语言描述】第二章线性表链式存储布局上的根本操作——
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链域置为空,表示链表结束*/
}
}

复制代码

由于附设了一个指问表尾结点的指针，所以时间复杂度和头插法的相同

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)