摘要：案例引入一元多项式的运算了解每一项的指数与其在线性表中的对应关系。线性表的链式表示又称为非顺序映像或链式映像。问题三头结点的数据域内装的是什么答头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
数据结构第一章知识汇总：
线性表的知识是数据结构中的重点及基础，涉及到的知识会比较多，但对线性表的操作反复进行理解与实践会使你对线性表的理解更加深刻、学的更好。
了解线性表内元素的关系，书上对这部分也有了比较详细的介绍，在此我仅用图把它们的关系罗列出来。
了解每一项的指数与其在线性表中的对应关系。
创建新数组c，分别从头遍历比较a和b的每一项，指数相同，对应系数相加，若其和不为零，则在c中增加一个新项。指数不相同，则将指数较小的项复制到c中。当一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可。
对于稀疏多项式，每个项的指数不再代表一个数组的下标，因此分别要开辟空间存放系数和指数。
对于指数不是依次增加的多项式，要学会如何去存储数据。例如：
因此当我们在存储上面两个多项式时，如果仍然使用顺序表进行存储，则缺点有：（1）存储空间分配不灵活。（2）运算的空间复杂度高。我们应该使用链式结构进行存储。
进行上面两个多项式的相加：
分析：首先我们从A的结点开始，往后一位则是指数为0，系数为7的结点，与B进行比较，发现B中没有指数为0的结点，我们不作处理，再对链表A后面的结点进行分析。发现链表A与链表B都有指数为1的结点，则将它们的系数相加放在链表A中。以此类推进行分析。过程与结果如下图：
对于图书信息管理系统，我们经常会有查找、插入、删除、修改、排序、计数等操作，用顺序表或链表存储图书信息的方式如下：
小结：
(1) 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
(2) 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用多带带编写一个程序,过于耗费成本。
(3) 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。
线性表主要分为顺序表与链表，它们的重要基本操作有初始化、取值、查找、插入、删除。顺序表的存储方式为随机存储，链表的存储方式为顺序存储。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻。
顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。
数据元素相互之间的存储关系：
顺序表的类型定义：
#define MAXSIZE 100 //最大长度typedef struct { ElemType *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList；图书表的顺序存储结构类型定义：
#define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct //图书信息定义{ char no[20]; //图书ISBN char name[50]; //图书名字 float price; //图书价格}Book; typedef struct{ Book *elem; //存储空间的基地址 int length; //图书表中当前图书个数 }SqList; //图书表的顺序存储结构类型为SqList以下是对顺序表操作的具体步骤，对于简单的代码，在代码后面我注释说明；而相对复杂的代码，我再具体进行解释及说明。
方法1：参数为引用类型：
Status InitList_Sq(SqList &L) //构造一 个空的顺序表L{ L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK;}方法2：参数用指针类型：
Status InitList_Sq(SqList *L) //构造一个空的顺序表L{ L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0 return OK;}获取顺序表L中的某个数据元素的内容：
int GetElem(SqList L,int i,ElemType &e){ if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR e=L.elem[i-1]; //第i-1的单元存储着第i个数据 return OK;}这个算法的时间复杂度为O(1)。
在线性表L中查找值为e的数据元素:
int LocateELem(SqList L,ElemType e){ for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; //返回查找值为e的位置 return 0;}要求顺序表查找算法的时间复杂度要先了解一个知识：什么是平均查找长度？（简称ASL），书上对平均查找长度有明确的解释，我这里就简单地解释一下。平均查找长度就是（每个元素被操作的概率）乘以（最坏情况下n次到第i个元素的和除以2）。例如查找操作，假设一共有n个元素，因为每一个元素都有被查找的可能，因此概率为n分之1，假设最坏情况是循环第n次才找到该元素，因此时间复杂度就为n分之1乘以i的1到n的和。
在线性表L中第i个数据元素之前插入数据元素e：
Status ListInsert_Sq(SqList &L,int i ,ElemType e){ if(i<1 || i>L.length+1) return ERROR; //i值不合法 if(L.length==MAXSIZE) return ERROR; //当前存储空间已满 for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移 L.elem[i-1]=e; //将新元素e放入第i个位置 ++L.length; //表长增1 return OK;}时间复杂度为O(n)。
将线性表L中第i个数据元素删除：
Status ListDelete_Sq(SqList &L,int i){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 for (j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK;}时间复杂度：O(n)。
销毁线性表L：
void DestroyList(SqList &L){ if (L.elem) delete[]L.elem; //释放存储空间}清空线性表L：
void ClearList(SqList &L) { L.length=0; //将线性表的长度置为0}求线性表L的长度：
int GetLength(SqList L){ return (L.length); }判断线性表L是否为空：
int IsEmpty(SqList L){ if (L.length==0) return 1; else return 0;}(1) 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。
(2) 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。
这种存取元素的方法被称为随机存取法。
优点：
(1) 存储密度大（结点本身所占存储量/结点结构所占存储量）。
(2) 可以随机存取表中任一元素。
缺点：
(1) 在插入、删除某一元素时，需要移动大量元素。
(2) 浪费存储空间。
(3) 属于静态存储形式，数据元素的个数不能自由扩充。
因此，为了克服顺序表的缺点而产生了链表。
结点：数据元素的存储映像。由数据域和指针域两部分组成。
链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
链式存储结构定义：
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
线性表的链式表示又称为非顺序映像或链式映像。
链表示意图：
链表各结点由两个域组成：
数据域：存储元素数值数据。
指针域：存储直接后继结点的存储位置。
单链表、双链表、循环链表：
结点只有一个指针域的链表，称为单链表或线性链表。
有两个指针域的链表，称为双链表。
首尾相接的链表称为循环链表。
头指针、头结点、首元结点：
头指针是指向链表中第一个结点的指针。
首元结点是指链表中存储第一个数据元素a1的结点。
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息。
链表有两种表现形式：头结点的有无。
问题一：如何表示空表？
答：有头结点时，当头结点的指针域为空时表示空表。
如图所示：
问题二：在链表中设置头结点有什么好处？
答：
(1) 便于首元结点的处理。首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理。
(2) 便于空表和非空表的统一处理。无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
问题三：头结点的数据域内装的是什么？
答：头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
如图所示：
链表（链式存储结构）的特点：
(1) 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
(2) 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
这种存取元素的方法被称为顺序存取法。
优点：
(1) 数据元素的个数可以自由扩充。
(2) 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高。
缺点：
(1) 存储密度小。
(2) 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）。
typedef struct Lnode{ ElemType data; //数据域 struct LNode *next; //指针域}LNode,*LinkList; //LNode指结点，*LinkList指的是指针// *LinkList为Lnode类型的指针LNode与*LinkList相等，创建的都是指针。
注意区分指针变量和结点变量两个不同的概念：
后面的代码中会大量用到指针，我觉得用图来进行说明更方便理解。
Status InitList_L(LinkList &L){ L=new LNode;//设置一个头结点 L->next=NULL;//头结点的指针域置空 return OK; } 单链表的销毁：
Status DestroyList_L(LinkList &L){ LinkList p;//设置指针p while(L) { p=L; L=L->next; delete p; //删除结点 } return OK; }清空单链表
Status ClearList(LinkList & L){ // 将L重置为空表 LinkList p,q; p=L->next; //p指向第一个结点 while(p) //没到表尾 { q=p->next; delete p; p=q; } L->next=NULL; //头结点指针域为空 return OK; }求单链表表长
int ListLength_L(LinkList L){//返回L中数据元素个数 LinkList p; p=L->next; //p指向第一个结点 i=0; while(p){//遍历单链表,统计结点数 i++; p=p->next; } return i; }判断表是否为空
int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0 if(L->next) //非空 return 0; else return 1; }链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。
算法步骤：
(1) 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
(2) j做计数器，累计当前扫描过的结点数，j初值为1。
(3) 当p指向扫描到的下一结点时，计数器j加1。
(4) 当j = i时，p所指的结点就是要找的第i个结点。
Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next;j=1; //初始化 while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p || j>i)return ERROR; //第i个元素不存在 e=p->data; //取第i个元素 return OK; }//GetElem_L 算法步骤：
(1) 从第一个结点起，依次和e相比较。
(2) 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址；
(3) 如果查遍整个链表都没有找到其值和e相等的元素，则返回或“NULL”。
1.返回L中值为e的数据元素的地址，查找失败返回NULL。
LNode *LocateELem_L (LinkList L，Elemtype e) { p=L->next; while(p &&p->data!=e) p=p->next; return p; } 2.返回L中值为e的数据元素的位置序号，查找失败返回0。
int LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的位置序号，查找失败返回0 p=L->next; j=1; while(p &&p->data!=e) {p=p->next; j++;} if(p) return j; else return 0;} 1.任意位置插入：
算法步骤：
//在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&j<i−1){p=p->next;++j;} //寻找第i−1个结点 if(!p||j>i−1)return ERROR; //i大于表长 + 1或者小于1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }//ListInsert_L 2.头插法
算法步骤：
从一个空表开始，重复读入数据：
(1) 生成新结点。
(2) 将读入数据存放到新结点的数据域中。
(3) 将该新结点插入到链表的前端。
void CreateList_F(LinkList &L,int n){ L=new LNode; L->next=NULL; //先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=new LNode; //生成新结点 cin>>p->data; //输入元素值 p->next=L->next;L->next=p; //插入到表头 } }//CreateList_F 3.尾插法
算法步骤：
(1) 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
(2) 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
void CreateList_L(LinkList &L,int n){ //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; r=L; //尾指针r指向头结点 for(i=0;i<n;++i){ p=new LNode; //生成新结点 cin>>p->data; //输入元素值 p->next=NULL; r->next=p; //插入到表尾 r=p; //r指向新的尾结点 } }//CreateList_L 算法步骤：
(1) 找到ai-1存储位置p。
(2) 保存要删除的结点的值。
(3) 令p-＞next指向ai的直接后继结点。
(4) 释放结点ai的空间。
删除示意图：
//将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; }//ListDelete_L 1.查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
2.插入和删除: 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
3.但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。
从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到。
对循环链表，有时不给出头指针，而给出尾指针，可以更方便的找到第一个和最后一个结点。
首先设置一个指针指向第一个链表的头结点处，连接各个元素，连接完毕后去掉第二个链表的头结点，即完成循环链表的合并。
LinkList Connect(LinkList Ta,LinkList Tb){//假设Ta、Tb都是非空的单循环链表 p=Ta->next; //①p存表头结点 Ta->next=<
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119950.html
摘要：第五题为压轴题考了三叉霍夫曼树数据结构期末机考大致有道题，难度由浅入深，根据去年实际体验，大致人均题。最后一题会比较难，可能会遇到比较复杂的数据结构，机考过程中前四题全部后可以试一下。输入第一行为测试数据数。每组测试数据的输出占一行。 ...
摘要：不仅阐明了应对一系列问题的解决方案，还介绍了在百花齐放的公链项目中的核心竞争力，并透露了主网会在月份正式发布的利好消息。共识之夜圆满落幕月日，联合星球日报及区块律动举办的共识之夜圆满落幕。 亲爱的ETM小伙伴： 随着高考、中考、期末考陆续结束 学生们似乎迎来了一年中最轻松的时刻 而对于区块链圈的人来说 却到了最难熬的时期 丰水期来临本是好事 奈何币价起起伏伏 算力再次大幅提升 伊朗加入...
摘要：不仅阐明了应对一系列问题的解决方案，还介绍了在百花齐放的公链项目中的核心竞争力，并透露了主网会在月份正式发布的利好消息。共识之夜圆满落幕月日，联合星球日报及区块律动举办的共识之夜圆满落幕。 亲爱的ETM小伙伴： 随着高考、中考、期末考陆续结束 学生们似乎迎来了一年中最轻松的时刻 而对于区块链圈的人来说 却到了最难熬的时期 丰水期来临本是好事 奈何币价起起伏伏 算力再次大幅提升 伊朗加入...
摘要：阿里作为的一员，面试是有难度的。原没有那小公司练手，很多同学都是裸考阿里。 这个总结其实来得挺晚的，但是又非常必要。我很有幸参加了今年的春秋招，并且前往深圳和北京这两个城市体验一线城市的精彩和心酸，无论是去深圳的一家小公司，还是转战北京小米。最终签约成都华为。我都有好多话想说。但是今天不是故事会，而是求职分享会，我希望我在本年度春秋招的所见所得能帮助你们应对明年的招聘 接下来请看一个时...
马上就要开始啦这次共组织15个组队学习 涵盖了AI领域从理论知识到动手实践的内容 按照下面给出的最完备学习路线分类 难度系数分为低、中、高三档 可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
阅读 713·2021-11-22 13:54
阅读 2643·2021-09-28 09:36
阅读 1138·2021-09-14 17:57
阅读 2803·2019-08-30 15:55
阅读 1847·2019-08-30 15:44
阅读 441·2019-08-29 12:31
阅读 2472·2019-08-28 18:18
阅读 1090·2019-08-26 13:58
