线性表（LinearList）：由n(n=0)个数据元素（结点）a1，a2，a3，an组成的有限序列
其中数据元素的个数n定义为表的长度
当n=0是称为空表
非空的线性表（n0）记作：（a1，a2，a3，an）
这里的数据元素ai（1=i=n）只是一个抽象的符号，其具体含义在不同的情况下可以不同
例：26个英文字母组成的英文表
（A，B，C，D，，Z）
同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系（1:1）
从上述例子可以放出线性表的逻辑特征：
在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2
有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a(n-1)
其余的内部结点ai(2=i=n-1)都有且仅有一个直接前趋a(i-1)和一个直接后继a(i+1)
2.2线性表的类型定义2.2.1数据类型定义抽象数据类型线性表的定义如下：
ADTList{数据对象：D={ai|ai属于Element，(i=1，2，，nn=0)}数据关系：R={a(i-1)，ai|a(i-1)，ai属于D，(i=2，3，，n)}基本操作：InitList(L);DestroyList(L);InsertList(L,i,e);DeleteList(L,i,e);}ADTList2.2.2基本操作定义initList(L)
操作结果：构造一个空的线性表
destroyList(L)
初始条件：线性表L已经存在
操作结果：销毁线性表L
clearList(L)
初始条件：线性表L已经存在
操作结果：将线性表L重置为空表
listIsEmpty(L)
初始条件：线性表L已经存在
操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE
lengthList(L)
初始条件：线性表L已经存在
操作结果：返回线性表L中数据元素个数
getElement(L,i,e)
初始条件：线性表L已经存在，1=i=lengthList(L)
操作结果：用e返回线性表中第i个数据元素的值
locateElement(L,e,compare())
初始条件：线性表L已经存在，compare()是数据元素判定函数
操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0
priorElement(L,cur_e,pre_e)
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义
nextElement(L,cur_e,next_e)
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败；next_e无意义
insertList(L,i,e)
初始条件：线性表L已经存在，1=i=lengthList(L)+1
操作结果：在L的第i个位置之前插入新的数据元素e，L的长度+1
deleteList(L,i,e)
初始条件：线性表L已经存在，1=i=lengthList(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1
traverseList(L,visvited())
初始条件：线性表L已经存在
操作结果：依次对线性表中每个元素调用visited()
以上提及的运算是逻辑结构上的运算。只描述了这些运算的功能是“做什么”，至于“如何做”等实现细节，只有待确定了存储结构之后才考虑。后文会给出详细代码
2.3线性表的顺序表示和实现2.3.1线性表的顺序表示线性表的顺序表示又称为顺序存储结构或顺序映像
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
顺序表中元素存储位置的计算假设线性表的每个元素需占L个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系：
由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：
例：如果每个元素占用8个存储单元，ai存储位置是2000单元，则a(i+1)存储位置是2008单元
但是线性表长可变（删除），数组长度不可动态定义
C语言中一维数组的定义方式：类型说明符数组名[常量表达式]
常量表达式中可以包含常量和符号常量，不能包含变量。即C语言中不允许对数组的大小作动态定义
所以我们可以用一变量表示顺序表的长度属性
ifndefPOLYNOMIALLISTdefineMAXSIZE100//多项式能达到的最大值typedefstruct{floatp;//系数inte;//指数}polynomial;typedefstruct{polynomial*data;//这里我用了指针，后续可以用malloc()动态分配空间intlength;//多项式中当前项的个数}polynomialList;defineLIST_INIT_SIZE100//线性表存储空间的初始分配量typedefstruct{elemType*elem;//数组intlength;//当前长度}sequenceList;sequenceListL;//定义变量L，L是sequenceList这种类型的，L是个顺序表顺序图示意图
我在定义了状态码
ifndefJUST_INCLUDE_ONCEdefineTRUE1defineOK11defineINFEASIBLE-1if//!JUST_INCLUDE_ONCE定义
typedefstruct{charelem;}sequence;typedefstruct{sequence*data;//这里我用了指针，后续可以用malloc()动态分配空间intlength;//多项式中当前项的个数}sequenceList;初始化/********************************************************************************************************************************@description：初始化顺序表*@param：list*@return：状态码*/statusinitSequenceList(sequenceList*list){list-data=(sequence*)malloc(sizeof(sequence)*MAXSIZE);if(!list-data){exit(OVERFLOW);//分配失败直接退出}list-length=0;returnOK;}销毁/********************************************************************************************************************************@description：销毁顺序表*@param：list*/voiddestroySequenceList(sequenceList*list){//判断是否为空if(list-data){free(list-data);}}清空/********************************************************************************************************************************@description：清空顺序表*@param：list*/voidclearSequenceList(sequenceList*list){list-length=0;}获取顺序表长度/********************************************************************************************************************************@description：获取顺序表的长度*@param：list*@return：长度*/intgetSequenceListLength(sequenceList*list){returnlist-length;}判断顺序表是否为空/********************************************************************************************************************************@description：判断顺序表是否为空*@param：list*@return：为空返回1*/statusisSequenceListEmpty(sequenceList*list){returnlist-length==0?TRUE:FALSE;}取值/********************************************************************************************************************************@description：取顺序表第i个元素*@param：list顺序表指针*@param：i位置*@param：e元素*@return：状态码*/statusgetSequenceListElement(sequenceList*list,inti,sequence*e){if(i1||ilist-length){returnERROR;}*e=list-data[i-1];returnOK;}这个算法时间复杂度为：O(1)
按值查找这里我们用顺序查找，是最简单的查找（暴力破解）
在线性表L中查找与指定值e相同的数据元素的位置
从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0
/********************************************************************************************************************************@description：按值查找，找元素与给定元素相同的那一项的位置*@param：list顺序表指针*@param：e字符*@return：找到返回位置；没找到返回0*/intlocateSequenceListElement(sequenceList*list,chare){inti=0;for(i=0;ilist-length;i++){if(list-data[i].elem==e){returni+1;}}return0;}算法分析：
查找次数跟给出的值有关，所以我们看平均查找长度
平均查找长度ASL（AverageSearchLength）
为了确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度
所以上面算法的时间复杂度：O(n)
插入算法思想：
判断插入位置i是否合法
判断存储空间是否已满，若已满返回ERROR
将第n至第i的元素依次向后移动一个位置，空出第i个位置
图解：
插入位置在最后/********************************************************************************************************************************@description：插入元素，位置在最后*@param：list顺序表指针*@param：e要插入的元素*@return：状态码*/statuslastInsertSequenceListElement(sequenceList*list,sequencee){//判断是否已满if(list-length==MAXSIZE){returnERROR;}list-data[list-length]=e;list-length++;returnOK;}插入位置在中间/********************************************************************************************************************************@description：插入元素，位置在中间*@param：list顺序表指针*@param：i要插入的位置*@param：e要插入的元素*@return：状态码*/statusmiddleInsertSequenceListElement(sequenceList*list,inti,sequencee){intj=0;//判断是否已满if(list-length==MAXSIZE){returnERROR;}//判断位置是否合法if(i1||ilist-length+1){returnERROR;}//从最后一个元素开始，依次向后移动一位for(j=list-length-1;j=i-1;j--){list-data[j+1]=list-data[j];}list-data[i-1]=e;list-length++;returnOK;}插入位置在最前/********************************************************************************************************************************@description：插入元素，位置在最前面*@param：list顺序表指针*@param：e要插入的元素*@return：状态码*/statusfirstInsertSequenceListElement(sequenceList*list,sequencee){//调用插在中间位置的函数，把i设为1returnmiddleInsertSequenceListElement(list,1,e);}完整的插入函数，根据i调用上面的函数
/********************************************************************************************************************************@description：完整的插入函数*@param：list顺序表指针*@param：i要插入的位置*@param：e要插入的元素*@return：状态码*/statusinsertSequenceListElement(sequenceList*list,inti,sequencee){//判断位置是否合法if(i1||ilist-length+1){returnERROR;}//判断是否已满if(list-length==MAXSIZE){returnERROR;}//判断插入位置if(i==1){returnfirstInsertSequenceListElement(list,e);}elseif(i==list-length+1){returnlastInsertSequenceListElement(list,e);}else{returnmiddleInsertSequenceListElement(list,i,e);}}插入算法的时间复杂度为：O(n)
删除算法思想：
判断删除位置i是否合法（合法值为1=i=n）
将欲删除的元素保留在e中
将第i+1至第n位的元素依次向前移动一个位置
表长减1，删除成功返回OK
/********************************************************************************************************************************@description：删除线性表L中第i个元素，用e返回其值*@param：list顺序表指针*@param：i要插入的位置*@param：e要插入的元素*@return：状态码*/statusdeleteSequenceListElement(sequenceList*list,inti,sequence*e){intj=0;//判断位置是否合法if(i1||ilist-length){returnERROR;}//用e返回被删除的元素*e=list-data[i-1];//从第i个元素开始，依次向前移动一位for(j=i;jlist-length;j++){list-data[j-1]=list-data[j];}list-length--;returnOK;}时间复杂度：O(n)
打印顺序表/********************************************************************************************************************************@description：打印顺序表*@param：list*/voidprintSequenceList(sequenceList*list){for(inti=0;ilist-length;i++){printf("%c",list-data[i].elem);}printf("\n");}2.3.3测试代码voidSequenceListMain(){sequenceListlist;//初始化initSequenceList(list);//插入5个值，分别为：a，b，c，d，efor(inti=1;i6;i++){sequencee={i+96};insertSequenceListElement(list,i,e);}//打印线性表printSequenceList(list);//输出：abcde//获取顺序表长度intlength=getSequenceListLength(list);printf("\n顺序表长度为：%d\n",length);//输出：顺序表长度为：5//获取顺序表中第3个元素sequencegetedElement;getSequenceListElement(list,3,getedElement);printf("\n顺序表中第3个元素为：%c\n",);//输出：顺序表中第3个元素为：c//获取顺序表中第一个匹配到的元素intindexGet=locateSequenceListElement(list,'d');if(indexGet){printf("\n顺序表中第一个匹配到的元素为第%d个\n",indexGet);}else{printf("\n顺序表中没有匹配到的元素\n");}//输出：顺序表中第一个匹配到的元素为第4个//获取顺序表中第一个匹配到的元素intindexNotGet=locateSequenceListElement(list,'z');if(indexNotGet){printf("\n顺序表中第一个匹配到的元素为第%d个\n",indexNotGet);}else{printf("\n顺序表中没有匹配到的元素\n");}//输出：顺序表中没有匹配到的元素//定位元素在顺序表中的位置intlocaltion=locateSequenceListElement(list,'c');printf("\n字符c在顺序表中的位置为：%d\n",localtion);//输出：字符c在顺序表中的位置为：3//删除顺序表中的某个元素sequencedelElement;deleteSequenceListElement(list,3,delElement);//打印线性表printf("\n删除第3个元素后的顺序表为：");printSequenceList(list);//输出：删除第3个元素后的顺序表为：abde//清空顺序表clearSequenceList(list);printf("\n清空顺序表后，顺序表中的元素为：");printSequenceList(list);//输出：清空顺序表后，顺序表中的元素为：//销毁顺序表destroySequenceList(list);}下面你只需在中调用SequenceListMain()
intmain(){//顺序表SequenceListMain();return0;}测试截图
2.3.4顺序表小结顺序存储的特点
利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表中的逻辑结构与存储结构一致
在访问线性表时，可以快速地计算出任何一个数据元素地存储地址。因此可以粗略地认为，访问每个元素所花时间相等
存取元素的方法称为随机存取法
顺序表的操作算法分析：
时间复杂度：查找、插入、删除算法的平均时间复杂度为O(n)
空间复杂度：O(1)没有占用辅助空间
优点：
存取密度大
可以随机存取表中任意元素
缺点：
在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储函数，数据元素的个数不能自由扩充，不灵活
2.4线性表的链式表示和实现用一组物理位置任意的存储单元来存放线性表的数据元素
这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中任意位置上的
链表中元素的逻辑次序和物理次序不一定相同
2.4.1相关术语结点：数据元素的存储映像。由数据域和指针域两部分组成
链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
示意图
用^表示0null，即最后一个结点
单链表：结点只有一个指针域的链表，称为单链表或线性链表
双链表：结点有两个指针域的链表，称为双链表
循环链表：首尾相接的链表称为循环链表
头指针、头结点和首元结点
头指针：是指向链表中第一个结点的指针
头结点：是在链表的首元结点之前附设的一个结点
首元结点：是指链表中存储第一个数据元素a1的结点
链表的存储结构示意图有以下两种形式
表示空表：
无头结点时，头指针为空时表示空表
有头结点时，当头结点的指针域为空时表示空表
设置头结点的好处：
便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理
头结点的数据域内装的是什么：
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能记入链表长度值
链式存储的特点：
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等（这种存取元素的方法称为：顺序存取法）
2.4.2单链表单链表的定义与表示定义
typedefstruct{ElementTypedata;//结点的数据域node*next;//结点的指针域}node,*linkList;//node:结点类型,linkList:结点指针类型//定义链表linkListlinklist;//定义结点指针linkListp;例如：存储学生学号、姓名、成绩的单链表结点类型定义如下
typedefstruct{charname[8];//数据域charnum[8];//数据域intscore;//数据域}elemType;typedefstruct{elemTypedata;//数据域node*next;//指针域}node,*linkList;单链表的操作这里指的是带头结点的单链表
定义为了好测试我把结构定义的简单点
typedefstructNode{chardata;//结点的数据域structNode*next;//结点的指针域}node,*singleLinkList;//node:结点类型,singleLinkList:结点指针类型初始化算法步骤：
生成新结点作为头结点，用头指针L指向头结点
将头结点的指针域置空
/********************************************************************************************************************************@description：初始化带头结点的单链表*@param：L指向头结点的头指针*@return：状态码*/statusinitSingleLinkList(singleLinkList*L){*L=(singleLinkList)malloc(sizeof(node));if(!*L){returnERROR;}(*L)-next=NULL;returnOK;}判断空表链表中无元素，称为空链表（头指针和头结点仍然在）
算法思路：
判断头结点的指针域是否为空
/********************************************************************************************************************************@description：判断头结点的指针域是否为空*@param：L头结点*@return：若为空，返回1*/statusisSingleLinkListEmpty(singleLinkListL){if(L-next==NULL){returnTRUE;}else{returnFALSE;}}销毁算法思路：
从头指针开始，依次释放所有结点
/********************************************************************************************************************************@description：销毁单链表*@param：L指向头结点的指针*@return：状态码*/statusdestroySingleLinkList(singleLinkList*L){singleLinkListp;while(*L){p=*L;*L=(*L)-next;free(p);}returnOK;}清空链表仍然存在，但链表中无元素，称为空链表（头指针和头结点仍然在）
算法思路：
依次释放所有结点，并将头结点指针域设置为空
/********************************************************************************************************************************@description：清空单链表*@param：L指向头结点的指针*@return：状态码*/statusclearSingleLinkList(singleLinkList*L){singleLinkListp,q;p=(*L)-next;while(p){q=p-next;free(p);p=q;}//头结点指针域置空(*L)-next=NULL;returnOK;}到这里要说明一下：
可以看到上面几个函数有的参数是linkList*L，有的是linkListL
带*的表示指向头结点的头指针
不带的表示为头结点
其实用C++的引用(linkListL)代码会整洁很多
获取表长算法思路：
从首元结点开始，依次计数所有结点
/********************************************************************************************************************************@description：获取链表表长*@param：L头结点*@return：表长*/intgetSingleLinkListLength(singleLinkListL){intcount=0;singleLinkListp=L-next;//p指向第一个结点，即首元结点while(p){count++;p=p-next;}returncount;}取值取单链表中的第i个元素的内容
从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构
算法思路：
从第1个结点（L-next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L-next
count做计数器，累计当前扫描过的结点数，j初值为1
当p指向扫描到的下一节点时，计数器count加1
当count=i时，p所指的结点就是要找的第i个结点
/********************************************************************************************************************************@description：取单链表中的第i个元素的内容*@param：L单链表头结点*@param：i第几个元素*@param：e元素的内容，由于我定义时是char类型，所以这边用char**@return：状态码*/statusgetSingleLinkListElement(singleLinkListL,inti,char*e){intcount=1;singleLinkListp=L-next;//p指向第一个结点，即首元结点while(pcounti){p=p-next;count++;}//循环结束找到了第i个的位置，再次进行判断if(!p||counti){returnERROR;}*e=p-data;returnOK;}查找返回地址
根据指定数据获取该数据所在的位置地址
算法步骤：
从第一个结点起，依次和e相比较
如果找到一个其值与e相等的数据元素，则返回其在链表中的”地址“
/********************************************************************************************************************************@description：根据指定数据获取该数据所在的位置（地址）*@param：L头结点*@param：e要查找的值*@return：在单链表中的地址*/singleLinkListgetSingleLinkListElementAddress(singleLinkListL,chare){singleLinkListp=L-next;while(pp-data!=e){p=p-next;}returnp;}时间复杂度：O(n)
返回位置序号
根据指定数据获取该数据所在的位置序号
算法步骤：
从第一个结点起，依次和e相比较
如果找到一个其值与e相等的数据元素，则返回其在链表中的”位置序号“
/********************************************************************************************************************************@description：根据指定数据获取该数据所在的位置序号*@param：L头结点*@param：e要查找的值*@return：在单链表中的位置序号*/intgetSingleLinkListElementIndex(singleLinkListL,chare){intcount=1;singleLinkListp=L-next;while(pp-data!=e){p=p-next;count++;}//没找到if(!p){return0;}returncount;}时间复杂度：O(n)
插入在第i个结点前插入值为e的新结点
算法思路：
/********************************************************************************************************************************@description：在第i个结点前插入值为e的新结点*@param：L头结点*@param：i要插入的位置*@param：e要插入的元素*@return：状态码*/statusinsertSingleLinkListElement(singleLinkListL,inti,chare){intcount=1;singleLinkListp=L;singleLinkLists;while(pcounti){p=p-next;count++;}//循环结束找到了第i个的位置，再次进行判断if(!p||counti){returnERROR;}s=(singleLinkList)malloc(sizeof(node));//创建一个新节点sif(!s){returnERROR;}s-data=e;s-next=p-next;p-next=s;returnOK;}时间复杂度：O(n)
删除删除第i个结点
算法思路：
/********************************************************************************************************************************@description：删除第i个结点*@param：L头结点*@param：i要删除的位置*@param：e用于接受删除的值*@return：状态码*/statusdeleteSingleLinkListElement(singleLinkListL,inti,char*e){intcount=1;singleLinkListp=L;singleLinkListq;while(p-nextcounti){p=p-next;count++;}//循环结束找到了第i个的位置，再次进行判断if(!p-next||counti){returnERROR;}//p-next=p-next-nextq=p-next;p-next=q-next;*e=q-data;//将删除的值用e接收free(q);returnOK;}时间复杂度：O(n)
单链表的建立头插法
元素插入在链表头部，也叫前插法
算法思路：
从一个空表开始，重复读入数据
生成新节点，将数据存放到新节点的数据域中
从最后一个结点开始，依次将各结点插入到链表的前端
/********************************************************************************************************************************@description：单链表的建立--头插法*@param：L头指针*@param：n要创建几个元素*@return：状态码*/statuscreateSingleLinkList_Head(singleLinkList*L,intn){singleLinkListp;//初始化单链表，调用之前写的初始化函数if(!initSingleLinkList(L)){returnERROR;}for(inti=0;in;i++){p=(singleLinkList)malloc(sizeof(node));if(!p){returnERROR;}//scanf("%c",p-data);p-data=i+97;//edcbap-next=(*L)-next;(*L)-next=p;}returnOK;}时间复杂度：O(n)
尾插法
元素插入在链表尾部，也叫做后插法
算法思路：
从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点
初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点
/********************************************************************************************************************************@description：单链表的建立--尾插法*@param：L头指针*@param：n要创建几个元素*@return：状态码*/statuscreateSingleLinkList_Tail(singleLinkList*L,intn){singleLinkListp,r;//初始化单链表，调用之前写的初始化函数if(!initSingleLinkList(L)){returnERROR;}r=*L;//r指向尾结点for(inti=0;in;i++){p=(singleLinkList)malloc(sizeof(node));if(!p){returnERROR;}//scanf("%c",p-data);p-data=i+65;//ABCDEr-next=p;r=p;//r指向新的尾结点}r-next=NULL;returnOK;}时间复杂度：O(n)
打印单链表/********************************************************************************************************************************@description：打印单链表中的元素*@param：L头结点*/voidprintSingleLinkList(singleLinkListL){singleLinkListp=L-next;while(p){printf("%c",p-data);p=p-next;}printf("\n");}测试代码voidSingleListMain(){singleLinkListsingle_link_list_head;/********************************************************************************************************************************@description：测试单链表的创建--头插法*///用头插法创建一个单链表，里面元素为：edcbacreateSingleLinkList_Head(single_link_list_head,5);printf("用头插法创建的单链表中的元素为：");printSingleLinkList(single_link_list_head);//输出：用头插法创建的单链表中的元素为：edcbasingleLinkListsingle_link_list_tail;/********************************************************************************************************************************@description：测试单链表的创建--尾插法*/createSingleLinkList_Tail(single_link_list_tail,5);printf("\n用尾插法创建的单链表中的元素为：");printSingleLinkList(single_link_list_tail);//输出：用尾插法创建的单链表中的元素为：ABCDE/********************************************************************************************************************************@description：测试清空操作，删除头插法创建的单链表single_link_list_head*/clearSingleLinkList(single_link_list_head);printf("\n清空头插法创建的单链表后，单链表中的元素为：");printSingleLinkList(single_link_list_head);//输出：清空头插法创建的单链表后，单链表中的元素为：/********************************************************************************************************************************@description：测试判断空表操作，上面已经将single_link_list_head清空*/if(isSingleLinkListEmpty(single_link_list_head)){printf("\n头插法创建的单链表为空\n");}else{printf("\n头插法创建的单链表不为空\n");}//输出：头插法创建的单链表为空/********************************************************************************************************************************@description：测试销毁操作，销毁头插法创建的单链表single_link_list_head，销毁成功返回1*/if(destroySingleLinkList(single_link_list_head)){printf("\n成功销毁头插法创建的单链表\n");}else{printf("\n销毁头插法创建的单链表失败\n");}//输出：成功销毁头插法创建的单链表/********************************************************************************************************************************@description：测试获取表长操作，获取尾插法创建的链表的长度single_link_list_tail*/inttailLinkListLength=getSingleLinkListLength(single_link_list_tail);printf("\n尾插法创建的单链表的长度为：%d\n",tailLinkListLength);//输出：尾插法创建的单链表的长度为：5/********************************************************************************************************************************@description：测试取值操作，查找在single_link_list_tail中第3个元素的内容*/charc;getSingleLinkListElement(single_link_list_tail,3,c);printf("\n尾插法创建的单链表中的第3个元素为：%c\n",c);//输出：尾插法创建的单链表中的第3个元素为：C/********************************************************************************************************************************@description：测试取值操作--返回地址*/singleLinkListp=getSingleLinkListElementAddress(single_link_list_tail,'C');printf("\n尾插法创建的单链表中的元素C的地址为：%p\n",p);//输出：尾插法创建的单链表中的元素C的地址为：0x000000000061FEB0ps：地址是会变化的/********************************************************************************************************************************@description：测试取值操作--返回位置序号*/intnum=getSingleLinkListElementIndex(single_link_list_tail,'C');printf("\n尾插法创建的单链表中的元素C的位置序号为：%d\n",num);//输出：尾插法创建的单链表中的元素C的位置序号为：3/********************************************************************************************************************************@description：测试插入操作，在C前面插入Z*/insertSingleLinkListElement(single_link_list_tail,3,'Z');printf("\n在C前面插入Z后，尾插法创建的单链表中的元素为：");printSingleLinkList(single_link_list_tail);//输出：在C前面插入Z后，尾插法创建的单链表中的元素为：ABZCDE/********************************************************************************************************************************@description：测试删除操作，删除single_link_list_tail中第3个元素*/chardeletedChar;deleteSingleLinkListElement(single_link_list_tail,3,deletedChar);printf("\n删除尾插法创建的单链表中的第3个元素后，单链表中的元素为：");printSingleLinkList(single_link_list_tail);//输出：删除尾插法创建的单链表中的第3个元素后，单链表中的元素为：ABCDEprintf("\n删除的元素为：%c\n",deletedChar);//输出：删除的元素为：Z}测试截图
2.4.3循环链表定义循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）
优点：从表中任一结点出发均可找到表中其它结点
注意：由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p-next是否为空，而是判断它们是否等于头指针
表的操作通常是在表的首尾位置上进行的，所以对循环链表我们用尾指针
合并两个循环链表带尾指针循环链表的合并（将Tb合并在Ta之后）
操作步骤：
p存表头结点p=Ta-next
Tb表头连接到Ta表尾Ta-next=Tb-next-next
释放Tb表头结点deleteTb-next
修改指针Tb-next=p
//循环链表定义和带头结点单链表定义一样typedefstructCircularNode{chardata;//结点的数据域structCircularNode*next;//结点的指针域}circularNode,*circularLinkList;/********************************************************************************************************************************@description：带尾指针循环链表的合并（将Tb合并在Ta之后）*@param：Ta*@param：Tb*@return：Tb的尾指针*/circularLinkListmergeCircularLinkList(circularLinkListTa,circularLinkListTb){circularLinkListp;circularLinkListtemp;//1.p存表头结点p=Ta-next;//2.将Ta的尾结点的指针域指向Tb的首元结点temp=Tb-next;//借用临时变量找到Tb的头结点Ta-next=temp-next;//3.将Tb的尾结点的指针域指向Ta的头结点Tb-next=p;//4.释放Tb的头结点free(temp);returnTb;}时间复杂度：O(1)
测试代码voidcircularLinkListMain(){//1.创建两个循环链表Ta，Tb，并把尾结点返回circularLinkListTa;circularLinkListTb;circularLinkListTa_tail=createCircularLinkList(Ta,5);//元素：ABCDEprintf("循环链表Ta中元素为：");printCircularLinkList(Ta);//输出：循环链表Ta中元素为：ABCDEcircularLinkListTb_tail=createCircularLinkList(Tb,5);//元素：ABCDEprintf("\n循环链表Tb中元素为：");printCircularLinkList(Tb);//输出：循环链表Tb中元素为：ABCDE//2.将Tb拼接在Ta后mergeCircularLinkList(Ta_tail,Tb_tail);printf("\n拼接后循环链表中元素为：");//printCircularLinkList(ret);printCircularLinkList(Ta);//输出：拼接后循环链表中元素为：ABCDEABCDE}测试截图
2.4.4双向链表定义在单链表的每个结点里再增加一个指向直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表
类C语言定义如下：
typedefstructDoublyNode{structDoublyNode*prior;ElementTypedata;structDoublyNode*next;}doublynode,*doublyLinkList;双向循环链表：
让头节点的前驱指针指向链表的最后一个结点
让最后一个结点的后继指针指向头结点
双向链表的对称性（设指针p指向某一结点）
p-prior-next=p=p-next-prior
在双向链表中有些操作（如：ListLength、GetElem等），因仅涉及一个方向上的指针，故它们的算法与线性链表相同。但在插入、删除时，则需要同时修改两个方向上的指针，两者的操作的时间复杂度为：O(n)
插入/********************************************************************************************************************************@description：在带头结点的双向循环链表L中第i个位置之前插入元素e*@param：L头指针*@param：i要插入的位置*@param：e要插入的元素*@return：状态码*/statusdoublyLinkListInsert(doublyLinkList*L,inti,chare){doublyLinkListp,s;intj;//1.判断i是否合法if(i1){returnERROR;}//2.找到第i个结点p=*L;j=0;while(pji){p=p-next;++j;}//3.判断i是否合法if(!p||ji){returnERROR;}//这时候以及找到第i个结点了//4.分配内存s=(doublyLinkList)malloc(sizeof(doublynode));if(!s){returnERROR;}//5.插入s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;returnOK;}删除在带头结点的双向循环链表L中删除第i个元素，并用e返回其值
/********************************************************************************************************************************@description：在带头结点的双向循环链表L中删除第i个元素，并用e返回其值*@param：L头指针*@param：i要删除第几个元素*@param：e用于接收删除的元素*@return：状态码*/statusdoublyLinkListDelete(doublyLinkList*L,inti,char*e){doublyLinkListp;intj;//1.判断i是否合法if(i1){returnERROR;}//2.找到第i个结点p=*L;j=0;while(p-nextji){p=p-next;++j;}//3.判断i是否合法if(!p-next||ji){returnERROR;}//这时候以及找到第i个结点了//4.删除*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);returnOK;}创建/********************************************************************************************************************************@description：创建双向循环链表*@param：L头指针*@param：n要创建几个元素*@return：状态码*/statuscreateDoublyLinkList(doublyLinkList*L,intn){doublyLinkListp,r;*L=(doublyLinkList)malloc(sizeof(doublynode));if(!(*L)){returnERROR;}(*L)-prior=NULL;(*L)-next=NULL;r=*L;for(inti=0;in;i++){p=(doublyLinkList)malloc(sizeof(doublynode));if(!p){returnERROR;}p-data=i+65;//datachar类型：ABCDEr-next=p;p-prior=r;r=p;}r-next=*L;(*L)-prior=r;returnOK;}测试voidDoublyLinkListMain(){/********************************************************************************************************************************@description：测试创建双向循环链表*/doublyLinkListdoubly_link_list;createDoublyLinkList(doubly_link_list,5);printf("双向循环链表中元素为：");printDoublyLinkList(doubly_link_list);//输出：双向循环链表中元素为：ABCDE/********************************************************************************************************************************@description：测试插入操作，在第3个元素前插入Z*/insertdoublyLinkList(doubly_link_list,3,'Z');printf("\n插入Z后，双向循环链表中元素为：");printDoublyLinkList(doubly_link_list);//输出：插入Z后，双向循环链表中元素为：ABZCDE/********************************************************************************************************************************@description：测试删除操作，删除第3个元素Z*/chardelDoublylinkchar;deletedoublyLinkList(doubly_link_list,3,delDoublylinkchar);printf("\n删除Z后，双向循环链表中元素为：");printDoublyLinkList(doubly_link_list);//输出：删除Z后，双向循环链表中元素为：ABCDEprintf("\n被删除的元素为：%c\n",delDoublylinkchar);//输出：被删除的元素为：Z}测试截图
2.5顺序表和链表的比较链式存储结构：
优点
结点空间可以动态申请和释放
插入和删除操纵不需要移动数据元素
缺点：
存储密度小，每个结点的指针域需额外占用存储空间
非随机存取
比较
2.6线性表的应用2.6.1线性表的合并问题描述：
假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=AUB，去掉重复元素
算法思路：依次取出Lb中的每个元素，执行以下操作：
在La中查找该元素
如果找不到，则将其插入La的最后
类C语言
voidunion(ListLa,ListLb){La_len=Listlength(La);Lb_len=Listlength(Lb);for(i=1;i=Lb_len;i++){GetElement(Lb,i,e);if(!(LocateElem(La,e))){ListInsert(La,++La_len,e);}}}时间复杂度：O(La_len*Lb_len)
2.6.2有序表合并已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列
算法步骤：
创建一个空表Lc
依次从La或Lb中“摘取”元素较小的结点插入到Lc表的最后，直至其中一个表变为空表为止
继续将La或Lb其中一个表的剩余结点插在Lc表的最后
用顺序表实现类C语言
voidMergeList_Sq(SqListLA,SqListLB,SqListLC){//指针pa和pb的初值分别指向两个表的第一个元素pa=;pb=;//新表的长度为待合并两表的长度之和=+;//为合并后的新表分配一个数组空间=newElemType[];//指针pc指向新表的第一个元素pc=;//pa_last，pb_last分别指向两表的最后一个元素pa_last=+;pb_last=+;//赋初值操作结束while(pa=pa_listpb=pb_last){//依次“摘取”两表中值较小的值if(*pa*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa=pa_list)//LB表已到达表尾，将LA中剩余元素加入LC*pc++=*pa++;while(pb=pb_last)//LA表已到达表尾，将LB中剩余元素加入LC*pc++=*pb++;}时间复杂度：O(Listlength(La)+Listlength(Lb))
空间复杂度：O(Listlength(La)+Listlength(Lb))
用链表实现类C语言
voidMergeList_L(LinkListLa,LinkListLb,LinkListLc){pa=La-next;pb=Lb-next;pc=Lc=La;//用La的头结点作为Lc的头结点while(papb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb头结点}时间复杂度：O(Listlength(La)+Listlength(Lb))
空间复杂度：O(1)
2.7案例分析与实现2.7.1连续多项式运算实现两个多项式加、减、乘运算
即将问题转化为对数组操作
相加
2.7.2稀疏多项式运算问题分析：
则有：
再：
创建一个新数组c
分别从头遍历比较a和b的每一项
指数相同：对应系数相加，若其和不为0，则在c中增加一个新项
指数不同：则将指数较小的项复制到c中
一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可
类C语言
voidCreatePolyn(PolynomialP,intn){P=newPNode;P-next=NULL;for(i=1;i=n;i++){s=newPNode;cins-coefs-expn;pre=P;q=P-next;while(qq-expns-expn){pre=q;q=q-next;}s-next=q;pre-next=s;}}多项式相加
算法步骤：
初始化指针p1和p2，分别指向Pa和Pb的首元结点
p3指向多项式的当前结点，初值为Pa的头结点
当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1-expn与p2-expn）有下列三种情况：
当p1-expn==p2-expn时，则将两个结点中的系数相加
若和不为0：则修改p1所指结点的系数值，同时删除p2所指结点
若和为0：则删除p1和p2所指结点
当p1-expnp2-expn时，则应摘取p1所指结点插入到“和多项式”链表中去
当p1-expnp2-expn时，则应摘取p2所指结点插入到“和多项式”链表中去
将非空多项式的剩余段插入到p3所指结点之后
释放Pb的头结点
/********************************************************************************************************************************@description：稀疏多项式相加*@param：La*@param：Lb*@return：多项式和*/polynomialListaddPolynomialList(polynomialListLa,polynomialListLb){polynomialListLc;initPolynomialList(Lc);polynomialListpa=La-next;polynomialListpb=Lb-next;polynomialListpc=Lc;while(papb){if(pa-expn==pb-expn){intsum=pa-coef+pb-coef;if(sum){insertPolynomialListElement(pc,1,sum,pa-expn);pc=pc-next;}pa=pa-next;pb=pb-next;}elseif(pa-expnpb-expn){insertPolynomialListElement(pc,1,pb-coef,pb-expn);pc=pc-next;pb=pb-next;}else{insertPolynomialListElement(pc,1,pa-coef,pa-expn);pc=pc-next;pa=pa-next;}}while(pa){insertPolynomialListElement(pc,1,pa-coef,pa-expn);pc=pc-next;pa=pa-next;}while(pb){insertPolynomialListElement(pc,1,pb-coef,pb-expn);pc=pc-next;pb=pb-next;}returnLc;}
