C语言线性链表

1线性表的链式存储结构每个元素由结点(Node)构成;结点间的逻辑关系是线性的，即线性表;结点在计算机中可以不连续存储;链表可以扩充，只受存储介质大小的限制;数据和数据间的关系分别存储Node:链表分类按照链式存储的原则，可以有多种形式的链表线性链表（单链表）循环链表双向链表a1ana3a2H^头结点a1anrear头结点a1anrear3typedefintElemType;typedefstructLNode{ElemTypedata;//结点的数据域structLNode*next;//结点的指针域}LNode,*LinkList;单链表的定义4单链表的存储映像Phead初始化：InitList(&L)销毁：DestroyList(&L)清空：ClearList(&L)判表空：ListEmpty(L)求表长：ListLength(L)取元素值：GetElem(L,i,&e)查找某元素：LocateElem(L,e)求前驱：PriorElem(L,cur_e,&pre_e)求后继：NextElem(L,cur_e,&next_e)插入：ListInsert(&L,i,e)删除：ListDelete(&L,i,&e)遍历：ListTraverse(L,Visit())单链表的基本操作6单链表的插入操作Step1：s-next=p-next;Step2：p-next=s；当!当!当!万无一失吗???有没有问题呢?7单链表插入操作的特殊情况（1）Xss-nextbahead核心语句：s-next=p;//head;head=s；在第一个结点前插入……原语句：s-next=p-next;p-next=s；p8单链表插入操作的特殊情况（2）在末尾插入Xss-next核心语句：s-next=NULL;p-next=s；pbahead原语句：s-next=p-next;p-next=s；9单链表插入操作的特殊情况（3）空表插入核心语句：s-next=NULL;head=s；head==NULLXheads原语句：s-next=p-next;p-next=s；太麻烦了！！！赶快想个办法吧！10解决之道：带表头结点的单链表^头指针表头结点head空表：头指针表头结点head^…首结点：存储第一个数据元素11s-next=p-next;p-next=s；Xss-next带表头节点单链表的插入操作abheadp(1)表头插入：(2)空表插入：headp^Xs^欧耶！太给力了!!!单链表插入操作的算法描述statusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的链表中的第i个结点前插入元素ep=L;j=0;while(p&&ji-1){p=p-next;++j;}//查找第i-1个结点if(!p||ji-1)return-1;//i值不合法s=(LNode*)malloc(sizeof(LNode));//申请新结点的空间s-data=e;s-next=p-next;p-next=s;//插入操作returnOK;}//ListInsert_LP29算法2.913小结：带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅做标志。有时可用来存储附加信息。设置表头结点的好处：统一了链表第一位置和其他位置的操作；统一了空表和非空表的操作；以空间赢得时间使得各种链表（单向链表、双向链表、单向循环链表和双向循环链表）的空链表状态得到区分；亦表明各种空链表结构是不同的。Note：只要不特殊说明，用的就是带头结点的链表。14课后作业对照不带头结点和带头结点两种单链表的插入操作，自行分析两种单链表对于删除操作的不同。（书面作业）说明：必须要做！虽然不讲，但是是考试内容！2.3.3链表基本算法实现(1)——初始化生成一个带头结点的空链表^头指针表头结点headStatusInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//创建头结点returnOK;}//InitList_L;16链表基本算法实现(2)——建立单链表建立链表的过程是一个动态生成的过程：从空表状态，依次建立各元素结点，并逐个插入head^步骤：（1）找到单链表的末尾；（2）将新结点插入。尾插法方法1：调用基本算法建立链表；使用基本算法:voidInitList(&L)；voidListInsert(&L,i,e)思想：1.初始化链表；2.将结点逐个插入表尾方法2：自编算法建立思想：1.初始化链表；2.申请一个结点；3.初始化它的值；4.结点链入表尾；5.结束否？6.Yes，结束创建操作；7.No，重复步骤2-6；尾插法建立单链表算法18方法2：尾插法建立单链表intCreatListR(LinkList&H){intelement;LinkListL;LNode*s,*last;//s指向新结点，last指向链表的最后结点L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//建立头结点last=L;cinelement;while(element!=0){s=(LNode*)malloc(sizeof(LNode));//申请新结点s-data=element;s-next=NULL;last-next=s;//新结点链入链表last=s;//last指向新的最后结点cinelement;}H=L；return0;}//CreatListR方法1实现：利用基本算法建立链表LinkListCallFunc_CreatLinkList(){LinkListL;inti=0;InitList(L);//初始化链表i=1;scanf(&x);while(x!=flag)//建立链表,flag结束标志{ListInsert(L,i,x);//结点插入链表末尾i++;scanf(&x);}returnL;}输入：67，23，10，45，36L3645102367^T(n)=O(n)如果不设last指针，则T(n)=O(n2)不省心，总要记住表尾。如何改进？尾插法建立单链表性能分析头插法头插法建立单链表（P30算法2.11）voidCreatList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带头结点的单链表LL=(LinkList)malloc(sizeof(LNode));L-next=NULL;//建立头结点for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));cinp-data;p-next=L-next;L-next=p;}}CreatList_L输入：36，45，10，23，67L3645102367^22总结：单链表的优缺点优点能有效利用存储空间；用指针指示数据元素之间的后继关系，便于进行插入、删除等操作；缺点：不能随机存取数据元素。同时，还丢失了一些顺序表有的长处，如数据元素在线性表中的“位序”，在的单链表中都“看不见”了。不便于在表尾插入元素，需遍历整个表才能找到表尾。23其他类型的链表——双向链表a1ana3a2H^空表：H^^typedefintElemType;typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;24小结：顺序表和链表的比较1.选用原则长度已知，且变化不大，则选择顺序表；长度不定，或变化大，则选用链表。1.主要操作的特点顺序表：插入、删除费时间移动数据，取数据快速；链表：插入、删除快速，取数据费时间。25Pn(x)=a0+a1x+a2x2+⋯+anxn=∑i=0naixi多项式(Polynomial)n阶多项式Pn(x)有n+1项。系数为a0,a1,a2,…,anx的指数为0,1,2,…,n。按升幂排列2.4线性表应用：一元多项式的表示和相加26多项式的存储表示方法1：按指数从0至n的次序保存所有项的系数。每个数据项系数类型为float，多项式存储为floatcoef[maxDegree];问题：对于指数不全的多项式如P2000(x)=3+5x1000–14x2000太浪费.27方法2：仅保存非0系数项的系数和指数方法2：改进的顺序表coefexptypedefstruct{floatcoef;//系数intexp;//指数}Poly_node;Poly_nodeSqPoly[m+1];28a1e1a0e0a2e2amem^Hcoefexpnext方法3：用单链表实现typedefstructPoly_ListNode{floatcoef;//系数intexp;//指数structPoly_ListNode*next;}Poly_ListNode;Poly_ListNode*SqPoly;1.若学生记录信息为：[学号、姓名、成绩]，要求以顺序表实现。请分别以静态存储和动态存储两种形式写出其数据结构描述。#defineListSize100typedefintElemType;typedefstruct{ElemTypeelem[ListSize];intlength;}Sqlist;typedefstruct{intnumber;charname[10];intscore;}ElemType;静态分配存储结构#defineListSize100typedefstruct{intnumber;charname[10];intscore;}Student;typedefstruct{Studentelem[ListSize];intlength;}Sqlist;#defineListSize100typedefintElemType;typedefstruct{ElemTypeelem[ListSize];intlength;}Sqlist;typedefstruct{intnumber;charname[10];intscore;}Student;动态分配存储结构#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;typedefstruct{intnumber;charname[10];intscore;}ElemType;应用举例：编程实现手机电话簿管理1.数据结构用双向循环链表，每个结点的信息是：prior姓名电话号码next2.基本功能（1）电话按姓名字母序排序放置；（2）能插入新的电话号码；（3）能删除电话号码；（4）可以按姓名查询电话号码；（5）可以快速查询电话号码；……