下载文档原格式
1，若进栈序列为1，2，3，4，则下列不可能的出栈序列为（）A，1，4，3，2B，2，3，4，1C，3，1，4，2D，3，4，2，12，链表不具备的特点是（）A，可随机访问任意一个结点B，插入和删除时不需要移动任何元素C，不必事先估计存储空间D，所需空间与其长度成正比3，对线性表，在下列情况下应该采用链表表示的是（）A，经常需要随机地存取元素B，经常需要进行插入和删除操作C，表中元素需要占据一片连续的存储空间D，表中元素的个数不变4，如果最常用的操作是取第I个结点及其前驱，最节省时间的存储方式是（）A，单链表B，双向链表C，单循环链表D，顺序表5，与单链表相比，双链表的优点之一是（）A，插入、删除操作更加简单B，可以随机访问C，可以省略表头指针和表尾指针D，顺序访问相邻结点更加灵活6，栈和队列的共同点是（）A，都是先进先出B，都是后进先出C，都只允许在端点处插入和删除元素D，没有共同点7，判断一个栈ST（最多元素为maxsize）为空的条件是（）A，ST -> top ! = -1B，ST -> top = = -1C，ST -> top ! = maxsize-1D，ST -> top = = maxsize-18，判断一个栈ST（最多元素为maxsize）为满空的条件是（）A，ST -> top ! = -1B，ST -> top = = -1C，ST -> top ! = maxsize-1D，ST -> top = = maxsize-19，带头结点的单链表head为空的判定条件是（）A，head＝＝NULLB，head -> next = =NULLC，head -> next = = headD，head ! =NULL10，下列关于线性表、栈、队列的叙述，错误的是（）A，线性表是给定的n个元素（n必须大于0）组成的序列B，线性表允许在表的任何位置插入和删除元素C，栈只允许在其一端进行插入和删除D，队列允许在其一端进行插入和另一端进行删除11，下列关于线性表的叙述中错误的是（）A，若用顺序存储，表中元素的存储位置是连在一起的B，若用链表存储，便于插入和删除运算C，若用链表存储，不需要占用一片相邻的存储空间D，表的插入和删除只允许在表的一端进行12，数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始，连续存放在存储器内，该数组按行存放，则元素A[8][5]的起始地址为（）A，SA＋141B，SA＋144C，SA＋222D，SA＋22513，数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始，连续存放在存储器内，该数组按列存放，则元素A[5][8]的起始地址为（）A，SA＋141B，SA＋180C，SA＋222D，SA＋22514，二维数组A[10][20]采用列序为主方式存储每个元素占一个存储单元，且A[0][0]的存储位置是200，则A[6][12]的地址是（）A，332B，C，320D，E，305F，30615，二维数组A[10…20][5…10]采用行序为主方式存储每个元素占4个存储单元，且A[10][5]的存储位置是1000，则A[18][9]的地址是（）A，1184B，C，1180D，1208E，121216，有一个10阶对称矩阵A，采用压缩存储方式（行序为主序，且A[0][0]＝1），则A[8][5]的地址是（）A，40B，41C，43D，42答案CA B D D CB D B A DC B A C D。
第2章线性表班级学号__________-姓名一、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。
链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（×）2. 链表的物理存储结构具有同链表一样的顺序。
链表的存储结构特点是无序，而链表的示意图有序。
（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
链表的结点不会移动，只是指针内容改变。
（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
前一半正确，但后一半说法错误，那是链式存储的优点。
顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（×）7. 线性表在物理存储空间中也一定是连续的。
线性表有两种存储方式，顺序存储和链式存储。
后者不要求连续存放。
（×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。
（×）9. 顺序存储方式只能用于存储线性结构。
顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。
（后一节介绍）（×）10. 线性表的逻辑顺序与存储顺序总是一致的。
理由同7。
链式存储就无需一致。
习题2.1选择题1、线性表的顺序存储结构是一种（A）的存储结构，线性表的链式存储结构是一种（B）的存储结构。
A、随机存取B、顺序存取C、索引存取D、散列存取2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（B）。
A、顺序存储方式B、链式存储方式C、散列存储方式D、索引存储方式3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（B）。
A、p->next=s ; s->next=p->next ;B、s->next=p->next ; p->next=s ;C、p->next=s ; s->next=p ;D、s->next=p ; p->next=s ;4、单链表中各结点之间的地址（ C D）。
A、必须连续B、部分地址必须连续C、不一定连续D、连续与否都可以5、在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（B）个元素。
A、n-iB、n-i+1C、n-i-1D、i2.2填空题1、顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样。
插入一个元素大约移动表中的（n/2）个元素，删除一个元素时大约移动表中的（(n-1)/2）个元素。
2、在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理顺序）来体现的；在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。
3、对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插入一个新结点的时间复杂度为（o(n)）。
4、在双向链表中，每个结点包含两个指针域，一个指向（前驱）结点，另一个指向（后继）结点。
数据结构习题(有答案) 第１章绪1。
1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。
（1) A= （ D,R )，其中,D = { ａ1，ａ2,ａ３，a４}, R={ ｝(2） B= （ D,R ),其中，D = ｛ a，ｂ,c,d，ｅ｝, R＝｛ (a,ｂ),(ｂ，c），（c，d）,(d，e）｝（3) C= （ D，Ｒ），其中，D = ｛ a，b，c,d，ｅ,f，g}, R=｛（d,b)，(d,g），(1）集合(2) 线性表a b c d e(３）树fgabcde(4）图1453621 / 48·····谢阅。
（b,a),（ｂ，c),（ｇ，e），（e，f)}（4) K= （ D,R ），其中,Ｄ= ｛ 1，2，3,4，5，６}, R=｛〈1，2＞,〈2，3＞，〈2，4＞，<3，４>，<３，５>，＜3，6>,<4,5〉,〈４，6〉}1.２设n为正整数,求下列各程序段中的下划线语句的执行次数。
（1) i=1；ｋ=0ｗhiｌe(i 〈=n-1){k+=１0＊i ；i＋+;（2) fｏr （ｉnt i=１；ｉ＜=n； i+＋）ｆor （int j＝１; j〈=ｎ; ｊ+＋)｛ｃ［i］［j］=0；解:(１) n－1（2) ∑∑∑====ninjnkn111312 / 48·····谢阅。
｝ﻩ fｏr(inｔk=1； k〈=n; ｋ＋＋）c[ｉ]［j］=c[i］［j]+a[ｉ］［k]*ｂ［k］[j］｝（3) x=０；ｙ=０;for （int ｉ＝1; i＜=n; i++)fｏr (inｔ j=1; j<＝ｉ; ｊ+＋)for (inｔk=1; k〈＝ｊ; k ＋＋）(３）62)1)(nn(n21)(216)12)(1(2121212)1(1112111111++=+•+++•=+=+==∑∑∑∑∑∑∑∑========nnnnniii ijnininiijjkniijni3 / 48·····谢阅。
一、单选题1、在长度为n的顺序表中的第i( 1 <= i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（）。
A.O(n*n)B.O(log2n)C.O(1)D.O(n)正确答案：D2、在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为（）。
A.iB.n-i+1C.n-i-1D.n-i正确答案：B3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.不必事先估计存储空间C.可随机访问任一元素D.所需存储空间与线性表程度成正比正确答案：C4、在一单链表中，删除指针p所指的后继结点，以下语句正确的是（）。
A.p->next=p->next->next; free(p->next);B. p=p->next;C.free(p->next);p->next=p->next->next;D.s=p->next;p->next=s->next;free(s);正确答案：D5、假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（）。
A.nB.n/2C.(n-1)/2D.(n+1)/2正确答案：C6、设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（）。
A.Base+(i-1)×mB.Base+(i+1)×mC.Base-i×mD.Base+i×m正确答案：A7、长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i 的合法值应该是（）。
A.1≤i≤n-1B.0≤i≤n+1C.i>0D.1≤i≤n+1正确答案：D解析：一般插入位置从1开始。
8、非空单链表结点结构为【data,next】，若指针p所指结点是尾结点，则（）表达式为真。
第二章线性表习题一判断题1．线性表的逻辑顺序与存储顺序总是一致的。
2．顺序存储的线性表可以按序号随机存取。
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
7．线性表的链式存储结构优于顺序存储结构。
8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。
(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（）个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。
(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。
4．用链表表示线性表的优点是（）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。
(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。
习题二参考答案一、选择题1.链式存储结构的最大优点是（ D ）。
A.便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。
A.106B. 107C.124D.1283.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。
A.顺序表B. 带头结点的单链表C.不带头结点的单链表D. 循环单链表4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。
A.顺序表B. 用头指针标识的循环单链表C. 用尾指针标识的循环单链表D. 双向链表5.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。
A.s.setNext(p); q.setNext(s);B. p.setNext(s.getNext()); s.setNext(p);C. q.setNext(s.getNext()); s.setNext(p);D. p.setNext(s); s.setNext(q);6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。
A.O(1)B. O(log2n)C. O(n)D. O(n2)7.要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，需要移动（ B ）个数据元素。
A.iB. n-i-1C. n-iD. n-i+18.在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ D ）。
A.p.setNext(s); s.setPrior(p); p.getNext().setPrior(s);s.setNext(p.getPrior());B.p.setNext(s); p.getNext().setPrior(s); s.setPrior(p);s.setNext(p.getNext());C.s.setPrior(p); s.setNext(p.getNext()); p.setNext(s);p.getNext().setPrior(s);D.s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);p.setNext(s);9.顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。
数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。
A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。
A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。
A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。
A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。
A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。
A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采⽤链式存储时，结点的存储地址（）。
A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。
《数据结构》教材课后习题+答案数据结构第一章介绍数据结构是计算机科学中重要的概念，它涉及到组织和存储数据的方法和技术。
数据结构的选择对于算法的效率有着重要的影响。
本教材为读者提供了丰富的课后习题，以帮助读者巩固所学知识并提高解决问题的能力。
下面是一些选定的习题及其答案，供读者参考。
第二章线性表习题一：给定一个顺序表L，编写一个算法，实现将其中元素逆置的功能。
答案一：算法思路：1. 初始化两个指针i和j，分别指向线性表L的首尾两个元素2. 对于L中的每一个元素，通过交换i和j所指向的元素，将元素逆置3. 当i>=j时，停止逆置算法实现：```pythondef reverse_list(L):i, j = 0, len(L)-1while i < j:L[i], L[j] = L[j], L[i]i += 1j -= 1```习题二：给定两个线性表A和B，编写一个算法，将线性表B中的元素按顺序插入到线性表A中。
答案二：算法思路：1. 遍历线性表B中的每一个元素2. 将B中的元素依次插入到A的末尾算法实现：```pythondef merge_lists(A, B):for element in B:A.append(element)```第三章栈和队列习题一：编写一个算法，判断一个表达式中的括号是否匹配。
表达式中的括号包括小括号"()"、中括号"[]"和大括号"{}"。
答案一：算法思路：1. 遍历表达式中的每一个字符2. 当遇到左括号时，将其推入栈中3. 当遇到右括号时，判断栈顶元素是否与其匹配4. 当遇到其他字符时，继续遍历下一个字符5. 最后判断栈是否为空，若为空则表示括号匹配算法实现：```pythondef is_matching(expression):stack = []for char in expression:if char in "([{":stack.append(char)elif char in ")]}":if not stack:return Falseelif (char == ")" and stack[-1] == "(") or (char == "]" and stack[-1] == "[") or (char == "}" and stack[-1] == "{"):stack.pop()else:return Falsereturn not stack```习题二：利用两个栈实现一个队列。
第2章线性表线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。
本章主要介绍线性表的定义、表示和基本运算的实现。
重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：●线性表的逻辑结构特征●线性表的顺序存储和链式存储两种存储结构的特点●在两种存储结构下基本操作的实现2-1 重点难点指导2-1-1 相关术语1．线性表线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。
如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。
通常用头指针来惟一标识一个链表。
6．头结点要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。
当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．头结点的作用要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储1．顺序表顺序存储的线性表称为顺序表。
其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
具体实现：在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。
考虑到线性表的运算有插入、删除等，即表长是可变的，因此，数组的容量需设计得足够大，设用data[MaxSize]来表示，其中MaxSize是一个根据实际问题定义的足够大的整数，线性表中的数据从data[0] 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MaxSize个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。
这种存储思想的具体实现可以是多样的。
方法一：可以用一个数组和表示长度的变量共同完成上述思想，如：#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数DataType data[MaxSize];int last;这样表示的顺序表如图2-1所示。
数据元素分别存放在data[0]到data[last]中。
这样使用简单方便，但有时不便管理。
0 1 …i-1 i …n-1 n MaxSize-1datalast图2-1 线性表的顺序存储示意图方法二：从结构上考虑，通常将data 和last 封装成一个结构作为顺序表的类型：#define MaxSize ……//MaxSize为根据实际问题定义的足够大的整数typedef struct{DataType data[MaxSize];int last; //表示线性表最后一个元素位置。
}SeqList;定义一个顺序表变量：SeqList L ;这样表示的线性表如图2-2（a）所示。
表长为st+1，线性表中的数据元素a1~a n分别存储在L.data[0]~L.data[st]中。
方法三：由于教科书中的算法用Visual C++语言描述，根据Visual C++语言中的一些规则，有时定义一个指向SeqList 类型的指针更为方便：SeqList *L ；L是一个指针变量，线性表的存储空间通过L=new SeqList操作（Visual C++语句，不同的语言版本可能有所不同）来获得。
L 中存放的是顺序表的地址，这样表示的线性表如图2-2（b ）所示。
表长表示为（*L ）.last+1或L -＞last+1，线性表中数据元素的存储空间为：L-＞data[0] ~ L-＞data[L-＞last]。
读者通过上述介绍的几种表示方式，进一步体会顺序存储的“理念”，做题时根据题意灵活掌握，在读写算法时注意相关数据结构的类型说明。
图2-2 线性表的顺序存储示意图2．顺序表的优缺点优点1：顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。
设a １的存储地址为Loc(a １)，每个数据元素占d 个存储地址，则第i 个数据元素的地址为：Loc(a i )=Loc(a １)+(i-1)*d 1≤i ≤n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i 个数据元素的地址来，这就是顺序表具有按数据元素的序号随机存取的特点。
优点2：存储密度高。
缺点1：在顺序表中做插入和删除运算时，平均需移动大约表中一半的元素；缺点2：顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，因此分配不足则会造成溢出；分配过大，又可能造成存储单元的浪费。
2-1-3 链表1．单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素a i ，除了存放数据元素自身的信息 a i 之外，还需要和a i 一起存放其后继 a i+1 所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图2-3所示，每个元素都如此。
因此n 个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。
因为每个结点中只有一个指向后继的指针，所以称其图2-3 单链表结点结构L.data L ->data 0 1 2 3 4 5st MaxSize -1（a ）表长为st+1（b ）表长为L->last+1MaxSize -1L ->length 643 2 1 0 a 1 a 2 a 3 a4 a5 a 6……a 1 a 2 a 3 a 4 a 5 a 6L->last 5 66为单链表。
链表是由一个个结点构成的，结点定义如下：typedef struct Node{DataType data;struct Node *next;}LNode,*LinkList;LNode是结点的类型，*LinkList是指向LNode结点的指针类型。
作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2-4的形式表示。
图2-4 单链表通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。
2．单循环链表对于单链表而言，最后一个结点的指针域是空指针，如果将该链表的头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。
对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使操作效率得以提高。
3．双向循环链表在单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p->next，而找其前驱结点则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继结点的时间性能是O(1)，找前Array驱的时间性能是O(n)，如果希望找前驱结点的时间性能也达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱结点的指针域，结点的结构如图2-5所示，用这种结点组成的链表称为双图2-5 双向链表向链表。
双向链表结点及指针类型定义如下：typedef struct DLNode{DataType data;struct DLNnode *prior,*next;}DLNode,*DLinkList;和单链表类似，双向链表通常也是用头指针标识。
通过双向链表中某结点的指针p既可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的指针p->prior。
这样在有些操作中需要找前驱结点时，则勿需再用循环。
设p指向双向循环链表中的某一结点，即p中是该结点的指针，则p->prior->next表示的是p所指结点之前驱结点的后继结点的指针，即与p相等；类似，p->next->prior表示的是p所指结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式：p->prior->next = p = p->next->prior4．静态链表静态链表是指以数组方式存放链表的数据，数组的每个元素包含有数据域data和指针域next，这里的指针域next与链表中的指针域不同的是其存放的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称之为静态指针。
在以静态链表方式存储链表时，数组中含有两个单链表，一个是数据元素的链表，一个是空结点的链表，故还需要设置两个整型变量，分别用于存放链表首元素（或头结点）在数组中的位置和空结点链表的首位置。
静态链表存储定义如下：#define MAXSIZE ……//足够大的数typedef struct {DataType data;int next;}SNode; //结点类型SNode sd[MAXSIZE]; //数组sd以静态链表方式存放链表数据int SL,AV; //两个头指针变量5．链式存储的优缺点链式存储的优缺点与顺序存储互补：优点1：对链表做插入和删除运算时，只需改变指针，不需移动数据。
优点2：不需要事先分配空间，便于表的扩充。
缺点1：存储密度降低，因为每个结点中除了存放数据元素的值还有一个指针域。
缺点2：不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。
2-1-4 线性表的基本运算1．基于顺序表的运算顺序表中常做的运算有插入、删除、合并、查找等，做这些运算时，要掌握一个原则：时刻体现顺序存储的思想，即元素之间物理相邻和逻辑相邻的一致性。
（1）在顺序表中插入元素：①插入元素时，检查顺序表是否已满，已满则不能做插入操作。
