【考研数据布局——C语言描述】第二章 线性表链式存储布局上的根本操作—— ...

25计算机考研，数据布局知识点整理（内容借鉴了王道408＋数据布局课本），还会不停美满所整理的内容，后续的内容也会不停更新（可以关注），若有错误和不敷欢迎各位朋友指出!

目次
一.头插法建表（前插法）
1.算法思想
2.算法描述
二.尾差法创建（后插法）
1.算法思想
2.算法描述

---

常见的见表方法有头插法和尾插法 
一.头插法建表（前插法）

1.算法思想

①从一个空表开始，每次读入数据
②生成新结点，将读入的数据存放到新结点的数据域中
③然后将新结点插入当前链表的表头结点之后，直到竣事标志为止。
2.算法描述

1. void CreateFromHead(LinkList L)
2. /*L是带头结点的空链表头指针,通过键盘输人表中元素值,利用头插法建单链表L*/
3. {
4.   Node *s;
5.   char c;
6.   int flag=l;
7.    while( flag)/*fag初值为1,当输人“$”时置flag为0,建表结束*/
8.    {
9.       c=getchar();
10.       if(c!='$')
11.       {
12.         s=(Node * )malloc(sizeof(Node)); /*建立新结点s*/
13.         s->data=c;
14.         s->next=L->next;/*将s结点插入表头*/
15.         L->next=s;
16.       }
17.       else flag=0;
18.    }
19. }

复制代码

采用头插法创建单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的，可用来实现链表的逆置，亦称头插法建表为逆序建表法，每个结点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。
注意：在上述算法中L是指向单链表的头指针，习惯上称为单链表L。

二.尾差法创建（后插法）

1.算法思想

头插法创建单链表虽然算法简单，但生成的单链表中结点的次序与输入顺相反。若希望二者顺序一致，采用尾插法建表，即将新结点插到当前单链表的表尾上。为此需增加一个尾指针r，使之指向当前单链表的表尾。利用尾插法创建单链表的过程如图2.10所示。

2.算法描述

1. void CreateFromTail(linkList L)
2. /*L是带头结点的空链表头指针,通过键盘输人元素值,利用尾插法建单链表L*/
3.   {
4.   Node *r,*s;
5.   int fag=1; /*设置一个标志,初值为1,当输人“$”时fag为0,建表结束*/
6.   r=L; /*r指针动态指向链表的当前表尾,以便做尾插人*/
7.   while(flag) /*循环输人表中元素值,将建立新结点s插人表尾*/
8.   {
9.     c=getchar( );
10.     if(c!='$')
11.     {
12.       s=(Node * )malloc(sizeof(Node));
13.       s->data=c;
14.       r->next=s;  //插入到表尾
15.       r=s; //r指向新的尾结点
16.     }
17.     else
18.     {
19.       flag=0;
20.       r->next=NULL; /*将最后一个结点的next链域置为空,表示链表结束*/
21.     }
22. }

复制代码

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

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