单链表的定义
- 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名
- 若头指针名是L，则把链表称为表L
单链表的存储结构定义
typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; // 指针域 }LNode,*LinkList; // *LinkList为Lnode类型的指针
其中，LNode,*LinkList是等价的
在定义指针类型时候就可以直接用LinkList
注意区分指针变量和结点变量两个不同的概念
指针变量p：表示结点地址
结点变量*p：表示一个结点
单链表的实现
1.初始化(构造一个空表 )
【算法步骤】
- 生成新结点作头结点，用头指针L指向头结点。
- 头结点的指针域置空。
【算法描述】
Status InitList_L(LinkList &L){ L=new LNode; L->next=NULL; return OK; }
求链表长度
指针p依次指向各个结点
从第一个元素开始“数”
一直“数”到最后一个结点
int ListLength_L(LinkList L){ //返回L中数据元素个数 LinkList p; p=L->next; //p指向第一个结点 i=0; while(p){ //遍历单链表,统计结点数 i++; p=p->next; } return i; }
判断链表是否为空
//判断表是否为空 int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0 if(L->next) //非空 return 0; else return 1; }
2. 取值
链表的查找：
要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。
【算法步骤】
- 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
- j做计数器，累计当前扫描过的结点数，j初值为1。
- 当p指向扫描到的下一结点时，计数器j加1。
- 当j = i时，p所指的结点就是要找的第i个结点。
【算法描述】
//获取线性表L中的某个数据元素的内容 Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next; j=1; //初始化 while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p || j>i) return ERROR; //第i个元素不存在 e=p->data; //取第i个元素 return OK; }
3.查找
【算法描述】
- 从第一个结点起，依次和e相比较。
- 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址;
- 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。.
【算法描述】
返回该链表
//在线性表L中查找值为e的数据元素 LNode *LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的地址，查找失败返回NULL p=L->next; while(p &&p->data!=e) p=p->next; return p; }
返回该结点的索引值
//在线性表L中查找值为e的数据元素 int LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的位置序号，查找失败返回0 p=L->next; j=1; while(p &&p->data!=e) {p=p->next; j++;} if(p) return j; else return 0; }
4. ※ 插入（插在第 i 个结点之前）
将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间
- 找到ai-1存储位置p
- 生成一个新结点*s
- 将新结点*s的数据域置为x
- 新结点*s的指针域指向结点ai
- 令结点p的指针域指向新结点s
//在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&j<i−1) { p=p->next; ++j; } //寻找第i−1个结点 if(!p||j>i−1) return ERROR; //i大于表长 + 1或者小于1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }
5. 删除（删除第 i 个结点）
- 找到ai-1存储位置p
- 保存要删除的结点的值
- 令p-＞next指向ai的直接后继结点
- 释放结点ai的空间
//将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; }
链表的运算时间效率分析
查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。
插入和删除: 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n) 。
