03.线性表(二)链式存储结构.单链表1，链式单链
链式存储结构.单链表1 1.基本概念 为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置) (1)数据域：存储线性表数据元素数据信息的域称为数据域； (2)指针域：把存储直接后继位置(下一个数据元素的地址)的域称为指针域，指针域中存储的信息为指针或链； (3)结点(Node):由数据域和指针域两部分信息组成数据元素ai的存储映像，称为结点。 (4)头指针：把链表中第一个结点的存储位置叫做头指针，因此整个链表的存取就必须从头指针开始进行。 (5)头结点：为了更加方便地对链表进行操作，我们在单链表的第一个结点前附设一个结点，即为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。升华笔记一：头指针和头结点的异同？ 头指针： a.头指针是指链表指向第一个结点的存储位置指针，若链表有头结点，则是指向头结点的指针。 b.头指针具有标识作用，所以常用头指针冠以链表的名字； c.无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 头结点： a.头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(也可以存放链表的长度); b.有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就同一了; c.头结点不一定是链表必要素。
2.单链表 n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2....an)的链式存储结构，因为此链表的每个结点只包含一个指针域，所以称之为单链表。
3.链式存储结构指针代码示例
/*线性表的单链表存储结构
* 结点由存放数据元素的数据域和存放后继结点地址的指针域组成*/
typedef
int ElemType; typedef struct Node { ElemType data; //int类型成员变量，作为结点的数据域 struct Node *next; //struct Node类型成员指针变量，作为结点的指针域 }Node; typedef struct Node *LinkList; //定义LinkList 注释： (1)Node相当于struct Node结构体;*LinkList相当于struct Node结构体 (2)假设指针p是指向线性表第i个元素的指针，则结点ai数据域和指针域为p->data、p->next即： p->data的值为该结点ai的数据域，内容是一个数据元素; p->next的值是一个指针，指向第(i+1)个元素(结点)的存储地址，即指向ai+1的指针 即p->data=ai p->next->data=ai+1
4.单链表的读取、插入与删除操作
(1)单链表的读取操作
实现操作： GetElem(LinkList
L,int i,ElemType *e),从单链表L中取出第i个数据元素,存放到指针变量i指向的地址空间中。
算法思路：不像线性表的顺序存储结构可以很容易的从任意位置读取一个元素，单链表的数据元素读取必须从头开始找，即工作指针p后移。
a.声明一个结点p指向链表第一个结点，初始化j从1开始遍历
b.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1，直到链表末尾p为空。则说明第i个元素不存在
c.如果p为空结点或者遍历位置超过i，抛出异常
d.查找成功，返回结点p的数据。
源码实现：
/*初始条件：顺序线性表L已存在，1=《i<=ListLength(L)
*操作结构：用e返回L中第i个数据元素的值*/
#define OK 1
#define ERROR 0
typedef int Status; typedef int ElemType;
typedef struct Node *LinkList; //定义LinkList
Status GetElem(LinkList L,int i,ElemType *e) { int j; LinkList p; //声明一个结点p p=p->next; //让结点p指向链表L的第一个结点 j=1; while(p&&j<i) //从链表第一个结点开始遍历，直到j=i-1，让p指向存储i-1位置所在的结点 { p=p->next; //让p指向下一个结点 j++; } if(!p || j>i) return ERROR; *e=p->data; //查找成功，将链表中的第i个元素的数据存储到指针e指向的空间 return OK; } 注释：p为新定义的一个结点，while(p&&j<i)的作用是使结点p从链表第一个结点开始遍历，直到j=i-1，让p指向存储i-1位置所在的结点，直到链表末尾p为空是说明第i个元素不存在。
(2)单链表插入操作 实现操作： ListInsert(LinkList *L,int i,ElemType e),将数据元素e插入到单链表L第i个位置 算法思路： s->next =p->next; p->next=s; a.声明一个结点p指向链表第一个结点，初始化j从1开始遍历 b.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1，直到链表末尾p为空，则说明第i个元素不存在。 c.如果p为空结点或者遍历位置超过i，抛出异常 d.如果查找成功， -在系统中生成一个空结点s -将数据元素e赋值给s->data; -单链表的插入标准语句s->next=p->next,p->next=s 源码实现： /*初始条件：顺序线性表L已存在，1=《i<=ListLength(L) *操作结构：将数据元素e插入到单链表L第i个位置*/ #define OK 1 #define ERROR 0 typedef int Status;
typedef int ElemType;
typedef struct Node *LinkList; //定义LinkList
Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; //声明一个结点p p=*L; j=1; while(p&&j<i) //从链表第一个结点开始遍历，直到j=i-1，让p指向存储i-1位置所在的结点 { p=p->next; //让p指向下一个结点 j++; } if(!p || j>i) return ERROR; s=(LinkList)malloc(sizeof(Node)); //生成新结点，即在内存中找了一小块空地，准备用来存放e数据s结点 s->data=e; //关键1：查找成功，将数据元素e赋值给s结点的数据域 s->next =p->next;//关键2：将结点p的后继结点赋值给s的后继(p->next为指向结点p下一个存储地址所在的结点) p->next=s; //关键3：设置结点p的后继结点为结点s return OK; } 注释：p为新定义的一个结点，while(p&&j<i)的作用是使结点p从链表第一个结点开始遍历，直到j=i-1，让p指向存储i-1位置所在的结点，直到链表末尾p为空是说明第i个元素不存在。 (3)单链表删除操作 实现操作： ListDelete(LinkList *L,int i,ElemType *e),删除单链表L中第i个数据元素，并将数据存放至指针e指向的空间中 算法思路：{ p->next=p->next->next(或者q=p->next;p->next=q->next) } a.声明一个结点p指向链表第一个结点，初始化j从1开始遍历 b.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1，直到链表末尾p为空，则说明第i个元素不存在。 c.如果p为空结点或者遍历位置超过i，抛出异常 d.如果查找成功 -将欲删除的结点p->next赋值给q -设置结点p的后继结点为q->next，即p->next=q->next; -将结点q的数据域数据存放至e e.释放q结点，返回成功标识 源码实现： /*初始条件：顺序线性表L已存在，1=《i<=ListLength(L) *操作结构：删除单链表L中第i个数据元素，并将数据存放至指针e指向的空间中*/ #define OK 1 #define ERROR 0 typedef int Status;
typedef int ElemType;
typedef struct Node *LinkList; //定义LinkList
Status ListInsert(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; //声明一个结点p p=*L; j=1; while(p->next&&j<i) //从链表第一个结点开始遍历，直到j=i-1，让p指向存储i-1位置所在的结点 { p=p->next; //让p指向下一个结点 j++; } if(!p || j>i) return ERROR; q=p->next; //设置q为p的后继结点 p->next=q->next; //将q的后继结点设置为p的后继结点 *e=q->data; //将q结点中的数据给e free(q); //设置完成后，让系统回收此结点，释放内存 return OK; }
升华笔记二：s、p、s->data、s->next、p->next辨析? (1)LinkList p,s：声明两个结点p、s，包含数据域和指针域; (2)s->data：为结点s的数据域，其值为一个数据 (3)s->next:：为结点s的指针域，其值为下一个结点存储地址 (4)s->next=p->next：将结点p的下一个结点存储地址赋值给s结点指针域 (5)p->next=s; 将结点s设置为p的下一个结点 事实上，(4)(5)我们可以这样理解： 假设初始链表相连两个结点p、q，即......-p-q-......,现在我们需要在结点p、q之间插入一个结点s，则 方法如下：由于p->next=q 则s->next=q //结点s后继为q p->next=s //结点p后继为s，此时即可形成......-p-s-q-......
5.顺序存储结构性能分析 (1)查找：最好情况时间复杂度为O(1)，最坏情况事件复杂度为O(2) (2)删除、插入：单链表的插入和删除主要由两部分组成：第一部分是遍历查询第i个元素；第二部分就是插入和删除元素 从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储解雇是没有太大的优势。但是如果我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。而对于单链表，我们只需要在第一次找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。 总结：对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。
本站文章为和通数据库网友分享或者投稿，欢迎任何形式的转载，但请务必注明出处.
同时文章内容如有侵犯了您的权益，请联系QQ：970679559，我们会在尽快处理。