数据结构C语言版 第二章 线性表 知识梳理+作业习题详解.docx
数据结构（C语言版）第二章线性表知识梳理+作业习题详解#defineover(i,s,t)for(registerintis;it;i)#definelver(i,t,s)for(registerintit;is;-i)typedeflonglongll;constintN5e57;typedefstructitemdoublecoef;/项数intexpn;/系数Item;typedefstructlistItem*elem;/指向数据元素的基地址intlength;/线性表的当前长度SqList;voidfindncoef(SqListB,intn)/找到并打印线性表第N项的系数if(nB.length|n1)puts(error!);elseprintf(%dn,B.elemn-1.expn);voidadd(SqListA,SqListB,SqList*C)inti0,j0,k0;while(iA.lengthjB.length)if(A.elemi.expnB.elemj.expn)C-elemk.coefA.elemi.coef;C-elemk.expnA.elemi.expn;elseif(A.elemi.expnB.elemj.expn)C-elemk.coefB.elemj.coef;C-elemk.expnB.elemj.expn;else/指数一样inttmpA.elemi.coefB.elemj.coef;if(tmp)C-elemk.coeftmp;C-elemk.expnB.elemj.expn;k,i,j;elsei,j;if(i!A.length)/线性表A中还有剩余while(iA.length)C-elemk.coefA.elemi.coef;C-elemk.expnA.elemi.expn;else/B中还有剩余while(iB.length)C-elemk.coefB.elemj.coef;C-elemk.expnB.elemj.expn;C-lengthk;boolIsEmpty(SqListL)if(L.length0)returntrue;elsereturnfalse;intn,m,length;inta10000;intmain()scanf(%d,length);SqListA;/定义一个线性表AA.elem(Item*)malloc(sizeof(Item)*length);A.elem0.coef7;A.elem0.expn0;A.elem1.coef3;A.elem1.expn1;A.elem2.coef9;A.elem2.expn8;A.elem3.coef5;A.elem3.expn17;A.length4;SqListB;B.elem0.coef8;B.elem0.expn1;B.elem1.coef22;B.elem1.expn7;B.elem2.coef-9;B.elem2.expn8;B.length3;return0;优点存储密度大结点本身所占存储量/结点构造所占存储量可以随机存取表中任一元素缺点在插入、删除某一元素时需要挪动大量元素浪费存储空间属于静态存储形式数据元素的个数不能自由扩大二、线性表链式存储构造链表0.链表的根本概念建议每次写的时候都加一个头节点各结点由两个域组成数据域存储元素数值数据指针域存储直接后继结点的存储位置结点数据元素的存储映像。由数据域以及指针域两局部组成链表n个结点由指针链组成一个链表。它是线性表的链式存储映像称为线性表的链式存储构造单链表、双链表、循环链表结点只有一个指针域的链表称为单链表或者线性链表有两个指针域的链表称为双链表首尾相接的链表称为循环链表头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素a1的结点头结点是在链表的首元结点之前附设的一个结点数据域内只放空表标志以及表长等信息Q1.怎样表示空表有头结点时当头结点的指针域为空时表示空表Q2.在链表中设置头结点有什么好处1.便于首元结点的处理首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作以及其它位置一致无须进展特殊处理;便于空表以及非空表的统一处理无论链表是否为空头指针都是指向头结点的非空指针因此空表以及非空表的处理也就统一了。头结点的数据域可以为空可以存放线性表长度等附加信息但此结点不能计入链表长度值。结点在存储器中的位置是任意的即逻辑上相邻的数据元素在物理上不一定相邻这种存取元素的方法被称为顺序存取法优点数据元素的个数可以自由扩大插入、删除等操作不必挪动数据只需修改链接指针修改效率较高缺点存储密度小存取效率不高必须采用顺序存取即存取数据元素时只能按链表的顺序进展访问顺藤摸瓜1.前插法代码实例因为是前插法所以是倒着顺序插入的先入后出先插入的在后面#includestdio.h#includestdlib.h#includestdbool.h#defineover(i,s,t)for(registerintis;it;i)#definelver(i,t,s)for(registerintit;is;-i)typedeflonglongll;/#defineint_int128typedefstructitem/doublecoef;intexpn;ElemType;
