§2.3 线性表的链式表示和实现
数 据 结 构
第二章 线性表
§2.3 线性表的链式表示和实现
2.3.1 线性链表
一、线性表的链式存储结构
1、▲：线性表的链式表示是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。表示每个数据元素的两部分（数据、后继元素存储地址）信息组合在一起被称为结点；它包括两个域：其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针域（next），指针域中存储的信息称为指针或链。N个结点（ai（1≤i≤n）的存储映射）链结成一个链表，即为线性表(a1，a2，… ai-1，ai，ai+1，…an)的链式存储结构（非顺序映射）。头指针指示链表中结点的存储地址。
链式存储结构的特点：插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。它是非随机存取结构。
链表可分为单链表、循环链表和双向链表。
2、单链表：
▲：单链表：链表中的每一个结点中只包含一个指针域的称为单链表或线性链表。
单链表的描述
单链表可由头指针唯一确定，在C语言中，用结构指针来描述。
typedef struc LNode{
}LNode, *LinkList
单链表的操作：
算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。假设p是指向线性表中第I个数据元素（结点ai）的指针，则p→next是指向第I+1个数据元素（结点ai+1）的指针，或若p→
Status GetElem_L(LinkList L, int i, ElemType){
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
p=L→ j=1;
while(p && j&i){
p=p→ ++j;
return OK;
}//GetElem_L
时间复杂度O（n）。
②插入操作：
要在数据元素a和b 之间插入元素x。
算法思想：决定a和b之间的相邻关系是由a 的指针决定的。若要实现插入，生成x结点，然后让a 的指针指向x 且x 的指针指向b。实现三个元a、x和b的逻辑关系。
设p为指向结点a 的指针，s为指向结点x的指针，则修改s、a的指针： vs→next=p→next；p→next=s；
Status ListInsert_L(ListLInk &L,
int i, ElemType e){
//在带头结点的单链表L中第i个位置前插入元素
while(p && j&i-1){p=p→ ++j;}
if (!p || j&i-1) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s→data=e; s→next=p-
p→next=s;
return OK;
}// LinkList_L
③删除操作：
在单链表数据元素a、b、c三个相邻的元素中删除b，算法思想：就是要让a 的指针直接指向c，使b从链表中脱离。即，p→next=p→next→next
可见，在已知链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，紧需修改指针而不需要移动元素。
④建立单链表：
算法2.9 P30是从表尾到表头逆向建立单链表算法，其时间复杂度为O（n）。
⑤有序单链表的合并：
例：将两个有序链表合并为一个有序链表。
算法思想：设立三个指针pa、pb和pc 分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到合并表中，即，让合并表的当前指针指向该元素，然后，修改指针。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。
本算法注意以下问题：
（1）删除第i个元素，i的取值为 1&=i&=n ,否则第i个元素不存在，因此，要检查删除位置的有效性。
（2）当表空时不能做删除，因表空时 L-&last的值为-1，条件（i&1 || i&L-&last+1）也包括了对表空的检查。
（3）删除 ai 之后，该数据已不存在，如果需要，先取出 ai ，再做删除。
删除算法的时间性能分析：
与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1～an
都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数：
在等概率情况下，pi =1/ n，则：
这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。
算法2.10 P31
3、静态单链表
▲：静态链表：有些高级语言没有指针，我们可以用数组来表示单链表，在数组中以整型游标来代替指针。这种用数组描述的链表称为静态链表。
静态链表的描述：
}component, SLinklist[MAXSIZE];
静态链表的操作和动态链表相似。以整型游标代替动态指针。S[0].cur指示第一个结点在数组中的位置。S[i].data表示存储在线性表中第I个数据元素。S[i].cur 指示第i+1个结点的位置。I= S[i].cur的操作为指针后移。
静态链表的操作：
①静态链表中的定位函数算法
LocateElem_SL(SLinkList L, ElemType){
//在静态链表L中查找值为e的元素。
//若找到，则返回它在L中的位序，否则返回0。
while(i &&S[i].data!=e) i=S[i].
}//LocateElem_SL
②算法2.14
int IsEmpty(LINK_LIST L)
if (L.head-&next==NULL) return TRUE;
else return FALSE;
通过e返回链表L中第i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType *e)
if (i&1||i&ListLength(L)) exit ERROR;
//检测i值的合理性
for (p=L.head,j=0; j!=i;p=p-&next,j++);
/ 到第i个结点
//将第i个结点的内容赋给e指针所指向的存储单元中
在链表L中检索值为e的数据元素
NODE *LocateELem(LINK_LIST L,EntryType e)
for (p=L.head-&p&&p-&item!=e;p=p-&next);
//寻找满足条件的结点
return(p);
返回链表L中结点e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE* e)
if (L.head-&next==e) return NULL;
//检测第一个结点
for (p=L.p-&next&&p-&next!=e;p=p-&next);
if (p-&next==e)
esle return NULL;
返回链表L中结点e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE* e)
for(p=L.head-&p&&p!=e;p=p-&next);
if (p) p=p-&
在链表L中第i个数据元素之前插入数据元素e
int ListInsert(LINK_LIST *L,int i,EntryType e)
NODE *p,*s;
if (i&1||i&ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s-&item=e;
for (p=L-&head,j=0;p&&j&i-1;p=p-&j++);
//寻找第i-1个结点
s-&next=p-&
p-&next=s;
//将s结点插入
return OK;
将链表L中第i个数据元素删除，并将其内容保存在e中。
int ListDelete(LINK_LIST *L,int i,EntryType *e)
NODE *p*s;
if (i&1||i&ListLength(L)) return ERROR;
//检查i值的合理性
for(p=L-&head, j=0;j&i-1;p=p-&next,j++);
//寻找第i-1个结点
//用s指向将要删除的结点
p-&next=s-&
//删除s指针所指向的结点
return OK;
2.3.2 循环链表
循环链表：是另一种形式的链式存储结构，其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环链表可分为单链和多链的。
循环链表的操作：和线性链表基本一致，差别仅在于循环条件判定是否为空改为是否为头指针,即：p或p-&next=s。
2.3.3 双向链表一、双向链表
结论：循环链表并不适用于经常访问前驱结点的情况，其执行时间为Ｏ(n)。
解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表。
1、▲：双向链表：在双向链表的结点中有两个指针域，分别指向前驱和后继。
v双向链表也可以有循环链表。
2、双向链表的描述：
typedef struct
struct DuLNode
struct DuLNode
} DuLNode, *DuL
3、双向链表的操作：
若d为指向表中某一接点的指针（即d为DuLinkList 型变量），则显然有d-&next-&prior=d-&prior-&next=d
双指针使得链表的双向查找更为方便、快捷。NextElem和PriorElem的执行时间为O（1）。
仅需涉及一个方向的指针的操作和线性链表的操作相同。
插入和删除需同时修改两个方向的指针。
在循环链表中，访问结点的特点：
访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。
4、用C语言实现双向循环链表的类型定义―― vtypedef strcut du_node{
//双向链表的结点类型 vEntryT vstruct du_node *prior,* v}DU_NODE; vtypedef struct{
//双向链表类型 vDU_NODE * v}DU_LINK_LIST;
4、用C语言实现双向循环链表的类型定义―― vtypedef strcut du_node{
//双向链表的结点类型
struct du_node *prior,*
typedef struct{
//双向链表类型
}DU_LINK_LIST;
初始化双向循环链表DL
int InitDuList(DU_LINK_LIST *DL)
DL-&head=(DU_NODE*)malloc(sizeof(DU_NODE));
//为头结点分配存储单元
if (DL-&head==NULL) return ERROR;
DL-&head-&next=DL-&
//让头结点的next域指向自身
DL-&head-&prior=DL-&
//让头结点的prior域指向自身
return OK;
在双向循环链表DL中，第i个数据元素之前插入数据元素e
在一个结点之前插入一个新结点的过程。
在双向循环链表中的p结点之前插入s结点应使用下列语句序列：
s-&next=p;
s-&prior=p-&
p-&prior-&next=s;
p-&prior=s;
完整的算法：
int DuListInsert(DU_LINK_LIST *L,int i,EntryType e)
vDU_NODE *p,*s;
if (i&1||i&ListLength(DL)+1) return ERROR;
//检测i值的合理性
s=(DU_NODE*)malloc(sizeof(DU_NODE));
//为新结点分配存储单元
if (s==NULL) return ERROR;
s-&item=e;
for (p=L-&head,j=0;p&&j&i;p=p-&j++);
//寻找第i 个结点
s-&next=p;
s-&prior=p-&
//将新结点插入
p-&prior-&next=s;
p-&prior=s;
return OK; }
创建双向循环链表DL vvoid Create_Du_Link_List(DU_LINK_LIST *DL)
if (InitDulist(DL)==ERROR) exit ERROR;
scanf(“%d”,&data);
for (int i=1;i++){
DuListInsert(DL,i,data);
scanf(“%d”,&data);
二、线性链表
问题及解决：链表在空间的合理利用上和插入、删除时不需要移动等的优点，所以在很多场合下，它是线性表的首选存储结构，但有些操作如：求线性表的长度等不如线性表方便，为此从实际应用角度出发，定义线性链表及其基本操作。
带头结点的线性链表类型定义及其操作，见P37。可见其算法时间复杂度大部分与表长无关。
三、顺序表和链表的比较
在本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。通过对它们的讨论可知它们各有优缺点，顺序存储有三个优点：
(1) 方法简单，各种高级语言中都有数组，容易实现。
(2) 不用为表示结点间的逻辑关系而增加额外的存储开销。
(3) 顺序表具有按元素序号随机访问的特点。
但它也有两个缺点：
在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。
需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
链表的优缺点恰好与顺序表相反。在实际中怎样选取存储结构呢？通常有以下几点考虑：
1．基于存储的考虑
顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对＂MAXSIZE＂要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于1的。
2．基于运算的考虑
在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。
3．基于环境的考虑 v顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。
总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的线性表称为链表。
通过上面线性表结构的学习，我们会发现插入和删除一个数据时我们需要移动大量的数据
这样的我们的时间的复杂度是O(n)。这个时候我们就会想有没有这样，我们中间会留好足够的空隙，我们只要是在访问第一个元素的时候知道下一个元素的地址就可以了。由于这样的设想我们就有了线性表链式存储结构。
讲个事：学前班老师带着同学们去游玩，然后回去了，老师让同学们排好队。然后问谁没在？
然后 同学就马上告诉老师谁谁谁没在，速度非常快的。他们是为什么这么快知道的呢？
原来是老师在带同学们游玩前都要告诉同学们记住你的前面的那个人，这样，一排队，谁不在同学们就知道了。
讲这个事是因为它跟我们的链式存储结构呢有点类似。帮助大家理解。
链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的线性表称为链表。
根据链表的构造方式的不同可以分为：
1.单向链表
2.单向循环链表
3.双向循环链表
单链表是构成链表的每个结点只有一个指向直接后继结点的指针。
单链表中每个结点的结构：
对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。最后一个意味着就没了直接后继了，所以线性链表的最后一个结点指针为空。
有时，我们为了方便对链表进行操作，会在单链表的第一个结点前附近设一个结点，这个结点称为头结点。头结点的数据域可以存东西，也可以不存东西。指针域存储指向第一个结点的指针。
我想到这个地方的话，大家应该对这个链表结构应该有个了解了。那么接下来，我们看看我们应该怎么设计：
链表插入数据：
链表的删除数据：
讲个故事，大家就知道怎么删除了。
有一天我心情大好，带着老婆孩子出去玩，我左手牵着我的老婆，右手牵着我的儿子。这样走在路上。突然来了一个美女，我看呆了，被老婆发现了，然后（老婆马上要开始删除数据了，删除我），老婆推开我的手，然后走到我跟儿子的中间，搬开我跟儿子的手，她用她的右手牵着儿子的左手走了，这样我就被删除了。
那么链式表的删除过程跟这个是一模一样的。
链表读取数据：
在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的，但是再单链表中，由于第i个元素在哪里我们没办法一开始就知道，我们必须从头开始找。因此对于单链表实现获取第i个元的数据操作在算法上要复杂一些。
获得链表第i个数据的算法思路：
1：声明一个结点P指向链表第一个结点，初始化j从1开始。
2：当j&i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1.
3：若到链表末尾p为空，则说明第i个元素不存在。
4：否则查找成功，返回结点p的数据。
我们的结点类：
package org.lixiyuan.
public class Node {
& Object element;//数据域
& Node next;//指针区域
& * 头结点构造
& * @param nextNode
&public Node(Node nextNode){
& &this.next=nextN
& * 非头结点构造
& * @param obc
& * @param nextNode
&public Node(Objectobc,Node nextNode){
& &this.element=
& &this.next=nextN
&public ObjectgetElement() {
& &return element;
&public void setElement(Object element) {
& &this.element =
&public Node getNext() {
& &return next;
&public void setNext(Node next) {
& &this.next =
List接口：
package org.lixiyuan.
public interface List {
&//获取长度
&public int getSize();
&//判断是否为空
&public boolean isEmpty();
&//插入一个元素
&public void insert(int index,Object obj) throws E
&//删除一个元素
&public void delete(int index) throws E
&//获取一个元素
&public Object get(int index) throws E
LinkList类：
package org.lixiyuan.
import org.lixiyuan.jiegou.L
public class LinkList implements List {
&public Node current;//当前结点
&public int size;//结点个数
&public Node header;//头指针
& * 空链表构造
&public LinkList(){
& &header=current=new Node(null);
& &this.size=0;//初始长度为零
& * 我们要找到我们要操作的这个结点的前一个结点
& * @param index
&public &void dingwei(int index) throws Exception{
& &if(index&-1||index&size-1){
& & &//小于-1就是说等于-1也是可以的，当然可以了，因为我们的有头结点和第一结点之说，第一节点就是0
& & &//而我们的-1就是头结点
& & &throw new Exception("参数不对");
& &if(index==-1){//那就说明我就是头结点，当然没有前面的结点了啊。
& & &return ;
& &current= header.next;//头指针指向当前指针
& &int i=0;
& &while(current!=null&&i&index){
& & &//当退出的时候是i==index说明我们找到了当前结点
& & &//这个时候我们也把当前结点的前一个结点找到了
& & &current=current.next;
&@Override
&public void delete(int index) throws Exception {
& &if(isEmpty()){
& & &throw new Exception("链表为空");
& &if(index&size||index&0){
& & &throw new Exception("参数错误");
& &dingwei(index-1);
& &current.setNext(current.next.next);
& &size--;
&@Override
&public Object get(int index) throws Exception {
& &if(isEmpty()){
& & &throw new Exception("链表为空");
& &if(index&-1||index&=size){
& & &throw new Exception("参数错误");
// &int i=0;
// &current=header.
// &while(current!=null&&i==index){
// & &current=current.
& &dingwei(index);
& &return current.getElement();
&@Override
&public int getSize() {
& &// TODO Auto-generated method stub
& &return this.size;
&@Override
&public void insert(int index, Object obj) throws Exception {
& &if(index&0||index&size){
& & &throw new Exception("参数错误");
& & &dingwei(index-1);//定位到要操作结点的前一个结点对象
& & &current.setNext(new Node(obj,current.next));
& & &size++;
&@Override
&public boolean isEmpty() {
& &// TODO Auto-generated method stub
& &return size==0;
package org.lixiyuan.
public class Test {
& * @param args
&public static void main(String[] args) throws Exception {
& &LinkList list=new LinkList();
& &for (int i = 0; i &10; i++) {
& & & int temp = ((int)(Math.random()*100))%100;
& & & &list.insert(i, temp);
& & & &System.out.print(temp+" ");
& &list.delete(4);
& & & &System.out.println("\n------删除第五个元素之后-------");
& & &for(int i=0;i&list.size;i++)
& & & &System.out.print(list.get(i)+" ");
测试结果：
52 85 86 89 57 67 91 48 65 38
------删除第五个元素之后-------
52 85 86 89 67 91 48 65 38
& 开源中国(OSChina.NET) |
开源中国社区(OSChina.net)是工信部
指定的官方社区数据结构/算法｜LOFTER（乐乎） - 记录生活，发现同好
LOFTER for ipad —— 记录生活，发现同好
&nbsp&nbsp被喜欢
&nbsp&nbsp被喜欢
{list posts as post}
{if post.type==1 || post.type == 5}
{if !!post.title}${post.title|escape}{/if}
{if !!post.digest}${post.digest}{/if}
{if post.type==2}
{if post.type == 3}
{if !!post.image}
{if post.type == 4}
{if !!post.image}
{if !!photo.labels && photo.labels.length>0}
{var wrapwidth = photo.ow < 500?photo.ow:500}
{list photo.labels as labs}
{var lbtxtwidth = Math.floor(wrapwidth*(labs.ort==1?labs.x:(100-labs.x))/100)-62}
{if lbtxtwidth>12}
{if !!labs.icon}
{list photos as photo}
{if photo_index==0}{break}{/if}
品牌${make||'-'}
型号${model||'-'}
焦距${focalLength||'-'}
光圈${apertureValue||'-'}
快门速度${exposureTime||'-'}
ISO${isoSpeedRatings||'-'}
曝光补偿${exposureBiasValue||'-'}
镜头${lens||'-'}
{if data.msgRank == 1}{/if}
{if data.askSetting == 1}{/if}
{if defined('posts')&&posts.length>0}
{list posts as post}
{if post_index < 3}
{if post.type == 1 || post.type == 5}
{if !!post.title}${post.title|escape}{/if}
{if !!post.digest}${post.digest}{/if}
{if post.type == 2}
{if post.type == 3}
{if post.type == 4}
{if drlist.length>0}
更多相似达人：
{list drlist as dr}{if drlist.length === 3 && dr_index === 0}、{/if}{if drlist.length === 3 && dr_index === 1}、{/if}{if drlist.length === 2 && dr_index === 0}、{/if}{/list}
暂无相似达人，
{if defined('posts')&&posts.length>0}
{list posts as post}
{if post.type == 2}
{if post.type == 3}
{if post.type == 4}
this.p={ currentPage:1,pageNewMode:true,isgooglead3:false,ishotrecompost:false,visitorId:0, first:'',tag:'数据结构/算法',recommType:'new',recommenderRole:0,offset:20,type:0,isUserEditor:0,};作业答案_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
上传于||暂无简介
大小：609.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢君，已阅读到文档的结尾了呢~~
数据结构课后习题答案第2章,数据结构课后习题答案,数据结构课后习题,数据结构习题答案,数据结构课后答案,数据结构练习题及答案,数据结构习题集答案,数据结构教程课后答案,数据结构复习题答案,课后习题答案网
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构课后习题答案第2章
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口