《数据结构》—— 单链表的插、删、查操作

数据结构》—— 单链表的插、删、查操作"/>

《数据结构》—— 单链表的插、删、查操作

单链表

• • 一、链表介绍
  • • 1.1 顺序表与链表优缺点比较
    • 1.2 单链表定义
  • 二、单链表基本操作
  • • 2.1 按位序插入（带头结点后插）
    • 2.2 指定结点的后插操作
    • 2.3 指定结点的前插操作
    • 2.4 按位序删除（带头结点）
    • 2.5 指定结点p的删除操作
    • 2.6 按位置查找值
    • 2.7 按值查找表结点

一、链表介绍

1.1 顺序表与链表优缺点比较

顺序表
优点：可以随时存取表中的任意一个元素；
缺点：插入和删除操作需要移动大量元素。

链式存储线性表
优点：不需要使用地址连续的存储单元，插入和删除操作不需要移动元素，而只需修改指针；
缺点：失去顺序表可随机存取的优点。

单链表
优点：解决顺序表需要大量连续存储单元的缺点；
缺点：单链表附加指针域，浪费存储空间，查找某个特定的结点时，需要从表头开始遍历，依次查找。

1.2 单链表定义

线性表的链式存储称单链表，单链表结构由数据域(data)与指针域(next)组成。数据域存储数据元素；指针域存放其后继结点的地址。

单链表实现方式：
不带头结点 --> 空表判断: L= =NULL。代码书写不便
带头结点 --> 空表判断: L-> next==NULL。写代码更方便(基本提倡写这种)

单链表结点类型代码描述：

typedef struct LNode {int data; // 结点的数据域struct LNode *next; // 结点的指针域
} LNode, *LinkList; // LinkList为指向结构体LNode的指针类型

“LinkList"等价于"LNode”。前者强调这是链表，后者强调这是结点，合适的地方使用合适的名字，代码可读性更高。

二、单链表基本操作

2.1 按位序插入（带头结点后插）

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。平均时间复杂度O(n)

【分析】: 1、先定义链表结构；2、在算法中，判断是否i位置<1，创建指针*p指向头结点，在循环中 *p找到第 i-1个节点，进行插入；3、创建一个节点s存储元素e，p的next位置是s的next位置，即把p赋值给s：s->next=p->next；接着变成p的next是s，即p->next=s。

typedef struct LNode {ElemType data; // 结点的数据域struct LNode *next; // 结点的指针域
} LNode, *LinkList; // LinkList为指向结构体LNode的指针类型//第i个位置上插入指定元素e
bool ListInsert(LinkList &L, int i, ElemType e){if(i<1)return false;LNode *p; // 指针p指向当前扫描到的结点int j=0;  // 当前p指向的是第几个结点p =L;     // L指向头结点，头结点是第0个结点(不存数据)while (p!=NULL && j<i-1) { //循环找到第 1-1个结点p=p->next;j++;}if(p==NULL) 	// i值不合法return false;LNode *s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next=p->next;p->next=s;     // 将结点s连到p之后return true;   // 插入成功
}

若不带头结点的后插法，在第一个结点的操作与其他结点不同！
【分析】: 1、创建新节点 *s，2、s的数据域为元素e，s的next为L本身；3、那么s会变成原本的L。

if(i==1){ // 插入第1个结点的操作与其他结点操作不同LNode *s = (LNode*)malloc(sizeof(LNode));s->data = e;S->next=L ;L=s;	//头指针指向新结点return true;
}

2.2 指定结点的后插操作

//后插操作:在p结点之后插入元素e
bool InsertNextNode (LNode *p, ElemType e){if (p==NULL)return false;LNode *s = (LNode *)malloc(sizeof(LNode));if (s==NULL) //内存分配失败return false;s->data = e;    //用结点s保存数据元素es->next=p->next;p->next=s;     //将结点s连到p之后return true;
}
调用:return InsertNextNode(p,e)

2.3 指定结点的前插操作

前插操作:在p结点之前插入元素e。
如何找到 p 结点的前驱结点？
【分析1】：已知p结点，可以传入头指针L，循环查找p的前驱q，再对q后插，则可以完成算法操作。时间复杂度O(n)。

【分析2】：已知p结点，创建s结点，我们思考当p的元素值是e，而s的元素值是p，那么可以就是前插操作！！

1. s的next=p的next；
2. p的next=s；
3. s的data=p的data；
4. p的data是e。

// 前插操作:在p结点之前插入元素e。
bool InsertPriorNode (LNode *p, ElemType e){if (p==NULL)return false;LNode *s = (LNode *)malloc(sizeof(LNode));if (s==NULL) //内存分配失败return false;s->next=p->next;p->next=s;     //将结点s连到p之后s->data=p->datap->data=e;     // p中元素覆盖为ereturn true;
}

2.4 按位序删除（带头结点）

ListDelete(&L,i,&e)：删除操作。删除表L中第i个结点的元素，并用e返回删除元素的值。时间复杂度O(n)

【分析】：跟2.1的插入操作类似，只是核心代码不一样。检查删除结点的位置合法性，查找出第i-1个结点 *p，然后讲 *p的指针域指向被删除结点 *q的下一结点，最后释放 *q。

	if(p==NULL) 	// i值不合法return false;if(p->next == NULL) // 第i个结点没有return false;LNode *q=p->next;   // 令q指向被删除结点e = q->data;        // 用e返回元素的值p->next=q->next;   // 将*q结点从链中“断开”free(q);        // 释放结点的存储空间return true;    // 删除成功

2.5 指定结点p的删除操作

【分析】：要删除p结点。p的前驱未知，后继q可求。那么p与p的next交换数据域，再把q的next赋值给p的next即可，最后释放q。时间复杂度O(1)

//删除指定结点p
bool DeleteNode (LNode *p){if (p==NULL)return false;LNode *q=p->next;    // 令q指向*p的后继结点p->data=p->next->data; // 和后继结点交换数据域p->next=q->next;       // 将*q结点从链中“断开”free(q);        // 释放后继结点的存储空间return true;
}
【注意】当指定结点是最后一个结点时，需要特殊处理

2.6 按位置查找值

按位查找，返回第i个元素(带头结点)
【分析】：1、判断i的合法位置，创建结点 *p指向头结点L；2、while循环找到第i个结点，最后return p。时间复杂度O(n)

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

// 按位查找，返回第i个元素(带头结点)
LNode *GetElem(LinkList L, int i){if(i<0 )return NULL;LNode *p;   //指针p指向当前扫描到的结点int j=0;    //当前p指向的是第几个结点p=L;       //L指向头结点，头结点是第0个结点(不存数据)while (p!=NULL && j<i) { //循环找到第i个结点p=p->next;j++;}return p;
}

2.7 按值查找表结点

从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e,则返回该结点的指针:若整个单链表中没有这样的结点，则返回NULL，时间复杂度O(n)。

LNode *LocateElem (LinkList L, ElemType e) {LNode *p=L->next;while (p!=NULL&&p->data!=e) // 从第1个结点开始查找data域为e的结点p-p->next; return P;    // 找到后返回该结点指针，否则返回NULL
}