个人网站可以干什么,电脑上怎么做网页,网页制作步骤图文,网站内容seo链式存储结构1 线性表的链式存储结构1.1不带头结点的单向链表1.2 带头结点的单向链表2 单向链表的基本操作实现2.1 单向链表的初始化操作2.2 单向链表的插入操作2.3. 单链表的删除操作2.4.单向链表的更新操作2.5.单向链表的求长度操作2.6.单向链表的定位操作2.7.单向链表的遍历…
链式存储结构1 线性表的链式存储结构1.1不带头结点的单向链表1.2 带头结点的单向链表2 单向链表的基本操作实现2.1 单向链表的初始化操作2.2 单向链表的插入操作2.3. 单链表的删除操作2.4.单向链表的更新操作2.5.单向链表的求长度操作2.6.单向链表的定位操作2.7.单向链表的遍历操作2.8.单向链表的创建操作2.9.基于建表算法的就地逆置操作1 线性表的链式存储结构
线性表的链式存储结构是指用一组数据类型相同的结点串接成一个单向链表每一个结点是一个结构体类型的变量由数据域和指针域组成其中数据域用于存放数据元素指针域用于存放直接后继结点的地址。
单链表分为带头结点和不带头结点
1.1不带头结点的单向链表
头指针直接指向第一个结点的地址 链表是否为空判断标准头指针指向NULL时为空链表。
1.2 带头结点的单向链表
头指针指向的结点称为头结点通常数据域为空不存放数据头结点的直接后继结点是第一个结点。 判断链表是否为空取决于头结点的指针域是否为空。 在带头结点的单向链表中进行插入和删除是由于第一个结点和其他结点的前驱邻接节点和后接邻接节点都是相同类型的结点因此对带头结点的单向链表所做的插入和删除操作不会改变头指针的值实现的代码比不带头结点的单向链表相对简单。
2 单向链表的基本操作实现
凡是操作单向链表都必须记住链表的头指针其余结点通过结点的指针域均可以依序得到。基本链表的基本操作者大致分为两类。一类是以查找为基础的算法设计比如定位以及根据条件找到相应位置后的插入和删除等另一类是建表为基础的算法设计比如将存放在链表中的一组数据逆序存放对存放在链表中的一组数据进行排序等。
2.1 单向链表的初始化操作
【算法实现】 方法一将建立的带结点的头指针存到主调函数的某个头指针变量H。调用时主调函数提供存放头指针变量H的地址为被调函数的参数。
int initLinkList1(LinkList* L)
{*L (LinkList)malloc(sizeof(LNode));if (*L NULL){return 0;}return 1;
}方法二将建立的带头结点的头指针用返回值返回给主调函数。调用时主调函数用赋值语句接受被调函数返回的头指针。
LinkList initLinkList2()
{LinkList L;//申请头结点空间将头结点地址赋值给头指针L (LinkList)malloc(sizeof(LNode));//判断是否申请成功if (L NULL)return NULL;L-next NULL;return L;//返回地址的值
}2.2 单向链表的插入操作
单向链表的插入操作是将学生数据插入到单向链表的指定位置i。 由于单向链表每个结点的指针域记得是直接后继结点所以要想使插进入的新结点* s成为第i个结点即让 *s的指针域记原来ai所在结点的地址并让原来a-i所在结点的指针域记 * s的地址实现这些操作的前提是找到ai-1所在结点的指针域记 *的地址实现这些操作的前提是找到ai-1所在的第i-1个结点。如何找到第i-1个结点呢用一个工作指针变量p向后继方向移动在移动的过程中用一个整型变量pos记p指向结点的位置。由于链表只能顺序查找让p从头结点开始pLpos0.当p不为空且p未到达第i-1个结点时条件pNULLposi-1为真则pp-next;pos;直至条件不成立。由于插入位置i给定值因此插入应考虑i取值的正确性即如果i1则结束操作如果in1,则p为空结束操作如果1in1,则p指向第i-1个结点posi-1插入新结点 * s。插入的主要代码为①s-nextp-next;②p-nexts。 分析因为插入的结点总是在头结点之后所以插入操作不会引起头指针L的改变由于插入操作必须知道插入的位置和插入的数据元素所以对应的应该有三个形参算法如下。 【算法】
int insertLinkList(LinkList L, int i, STD x)
{LinkList p, s;int pos 0;//pos记头结点的位置0p L;//p的初值为头指针if (i 1){printf(插入位置越下界插入失败\n);return 0;}while (p ! NULL pos i - 1){p p-next;pos;}if (p NULL){printf(插入位置越上界插入失败\n);return 0;}//生成新的结点if ((s (LinkList)malloc(sizeof(LNode)) NULL)){perror(insertLinkList::);return 0;}//将s指向的新结点在指定位置插入s-data x;s-next p-next;p-next s;return 1;
}【算法分析】 寻找插入位置将数据插进来需要从第一个结点开始比较。最好的情况是o1最坏的情况是O(n)等概率加权平均是O(n)。
2.3. 单链表的删除操作
单链表的删除操作就是将指定位置的学生数据删除。 【算法实现】
int deleteLinkList(LinkList L, int i, STD* x)
{LinkList p L,q;//p的初值为头指针int pos 0;//pos记录结点的位置0if (L-next NULL){printf(链表为空删除失败!\n);return 0;}if (i 1){printf(删除位置越下界删除失败\n);return 0;}//让p记住第i-1个结点pos记住p指向结点的位置while (p-next!NULLposi-1){p p-next;pos;}if (p-next NULL){printf(删除位置越上界删除失败\n);return 0;}q p-next;p-next q-next;*x q-data;free(q);return 1;
}【算法分析】 寻找删除位置将数据删除需要从第一个结点开始比较。最好的情况是O(1)最坏的情况是O(n)等概率加权平均是O(n)。
2.4.单向链表的更新操作
单向链表的更新操作是用新数据元素替换指定位置i处的数据元素。 【算法实现】
int updateLinkList(LinkList L, int i, STD x)
{LinkList p;int pos;if (L-next NULL){printf(链表为空不能更新\n);return 0;}if (i 1){printf(更新位置越下界不能更新!\n);return 0;}//p指向第一个结点pos记p指向结点的位置p L-next;pos 1;while (p ! NULL pos i){p p-next;pos;}if (p NULL){printf(更新位置越上界不能更新\n);return 0;}p-data x;return 1;//更新成功}【算法分析】 寻找更新数据的位置需要从第一个结点开始比较。最好的情况是O(1)最坏的情况是O(n)等概率加权平均是O(n)。
2.5.单向链表的求长度操作
单向链表的求长度操作是计算单向链表中数据元素个数。 【算法实现】
int LinkListLength(LinkList L)
{LinkList p L-next;int n 0;while (p){n;p p-next;}return n;
}2.6.单向链表的定位操作
单向链表的定位操作是根据条件得到某个数据元素的地址。定位操作又称为查找操作。 分析定位操作不会引起头指针的变化但是必须提供查找的条件所以定位函数应该有2个形参。如果查找成功返回结点所在地址否则返回空。 【算法实现】
LinkList locationLinkList(LinkList L, char* name)//依据姓名查找
{LinkList p L-next;//p指向第一个数据结点while (p){if (strcmp(p-data.name, name) ! 0){p p-next;}else{return p;}}return NULL;
}2.7.单向链表的遍历操作
单向链表的遍历操作是输出单链表中存放的所有数据元素 【算法】
void dispLinkList(LinkList L)
{LinkList p L-next;//p指向第一个数据结点while (p){printf(%10s%7.2f\n, p-data.name, p-data.score);p p-next;}return;
}算法中的指针变量p可以不定义直接用形参L代替p。但是为了提高算法的可读性约定这里的L在调用指向链表的头结点在后序的操作中不要改变L的值。如需寻找链表上的其他结点建议用另外工作指针去完成相应的操作。
2.8.单向链表的创建操作
单向链表的创建操作是创建一个空链表并依序插入新的结点。 常见的创建单向链表的算法有三种。分别如下。 1用初始化函数和插入函数组合得到算法如下。 【算法】
void createLinkList(LinkList* L)
{int n 1;STD x;char yn;initLinkList1(L); //调用初始化函数创建空表do{printf(请输入第%d个学生的姓名和分数用空格隔开, n);scanf(%s%f, x.name, x.score);getchar();//空读回车insertLinkList(*L, n, x);//调用插入函数将新节点插入在尾部printf(继续请输入吗Y/N:);scanf(%c, yn);} while (yn Y || yn y);
}2头插法将新结点插入到头结点之后和原来的第一个结点之前。 分析为了使新结点是第一个结点必须使用新结点的指针域记原来的第1个结点头结点的指针域记新结点。 【头插法算法如下】
int frontCreateLinkList(LinkList* L)
{STD x;LinkList p;char yn;int n 0;initLinkList(L);//创建空表do{printf(请输入第%d个学生的姓名和分数用空格隔开, n);scanf(%s%f, x.name, , x.score);getchar();//空读回车if ((p (LinkList)malloc(sizeof(LNode))) NULL){perror(frontCreateLinkList::);return 0;}//将新结点p插入到头结点之后和原来的第一个结点之前p-next (*L)-next;(*L)-next p;printf(继续输入吗Y/N:);scanf(%c, yn);} while (yn y || yn Y);return 1;
}3尾插法将新结点插入到原来的尾结点之后。 分析原来的单向链表只有头指针。现在进行尾插必须已知尾结点。因此尾插算法需要一个工作指针记住当前的尾结点称尾指针。用原结点的指针域记新插入的结点尾指针记新的尾结点使新结点为新的尾结点。 【尾插法算法如下】
int rearCreateLinkList(LinkList* L)
{STD x;LinkList p, R;char yn;int n 0;//创建空表if ((*L (LinkList)malloc(sizeof(LNode))) NULL){perror(rearCreateLinkList::);return 0;}(*L)-next NULL;R *L;//R是尾指针do{printf(请输入第%d个学生的姓名和分数用空格隔开, n);scanf(%s%f, x.name, x.score);getchar();//空读回车//创建新结点if ((p (LinkList)malloc(sizeof(LNode))) NULL){perror(rearCreateLinkList::);return 0;}p-data x;p-next NULL;//将新结点p插入到原来的尾结点之后R记录新的尾结点pR-next p;R p;printf(继续输入吗Y/N);scanf(%c, yn);} while (yn y || yn Y);return 1;
}创建链表的三种算法的比较如下由于调用函数需要花费系统开销因此多次调用插入函数insertLinkList()创建链表的效率较低头插法创建链表的数据元素顺序与输入数据元素的顺序相反尾插法创建链表与输入数据元素的顺序相同。
2.9.基于建表算法的就地逆置操作
所谓的就地逆置指的是原来的一组数据已经存放在一个带头结点的单向链表中现在将这组数据逆序存放结点的存储空间数原来的只是改变了结点的指向。这相当于重新做一次创建链表的头插法。 分析首先将原链表置成空表再将原链表的每个数据结点依次做头插即可。需要注意的是要用两个辅助指针变量p和q协助完成其中p记每次待插入的第一个结点q记p的直接后继结点直至所有结点插入完成。 【算法实现如下】
void inverLink(LinkList L)
{LinkList p, q;if (L-next NULL){printf(表空\n);return;}p L-next;//p记链表的第一个结点L-next NULL;//置L为空链表while (p ! NULL){q p-next;//q记p的直接后继结点//对*p做头插p-next L-next;L-next p;//p记下一个待插入的结点p q;}
}对已知链表进行排序与就地逆置的算法思想相似只不过对每一个待排序的结点不是做头插而是根据排序的要求先找插入位置重新作用做一次插入的创建链表。
