[数据结构与算法]单链表算法题

头插法建立单链表

#include "stdio.h"
#include "stdlib.h"

//单链表存储结构
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;//区别：LNode指向某个结点, *LinkList指向整个单链表 
 
//初始化 分配空间 
void InitList_L(LinkList &L){
	L = (LinkList)malloc(sizeof(LNode));
	
	L->next = NULL;
}
//头插法 
void CreateListHead_L(LinkList &L){
	for(int i = 0; i < 5; i++){
		LNode *p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		
		p->next = L->next;
		L->next = p;
	}
}

void visit(int e) {
    printf("%d ",e);
}
//输出单链表 
void ListTraverse_L(LinkList L, void (*pfn_visit)(int)) {
	for(LNode *p = L->next; p != NULL; p = p->next){
		pfn_visit(p->data);
	}
}

int main(){
    //1.声明
    LinkList L;
    //2.初始化
    InitList_L(L);
    //3.建立单链表
    CreateListHead_L(L);
    //4.输出
    ListTraverse_L(L, visit);
    return 0;
}

头插法建立单链表完善

//用到的库文件
#include <stdio.h>	//printf();scanf()
#include <stdlib.h> //exit()
#define OK		1
#define ERROR	0
#define OVERFLOW	-2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
//#define ElemType int	//也可以用宏定义确定ElemType类型
typedef int ElemType;
//-----线性表的单链表存储结构-----
typedef struct	LNode {		//自定义数据类型
    ElemType data;			//数据域
    struct LNode *next;	//指针域
} LNode, *LinkList;

// 操作结果：构造一个空的线性表L。
Status InitList_L(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    if(!L) {						//存储分配失败
        printf("初始化失败");
        exit(OVERFLOW);			//exit(-2)程序异常退出
    }
    L->next = NULL;				// 先建立一个带头结点的单链表，并使头结点的指针域为NULL
    return OK;
}// InitList_L

Status CreatListHead_L(LinkList L){
    printf("请输入5个元素：");
    for (int i=0; i<5; i++){	// 生成新结点
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);	//输入元素值 赋给新生成结点的数据域
        p->next = L->next;			//插入到表头
        L->next = p;
    }
    return OK;
}

// 初始条件：线性表L已存在。
// 操作结果：依次对L的每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。
Status visit(ElemType e) {
    printf("%d ",e);
    return OK;
}
Status ListTraverse_L(LinkList L, Status (*pfn_visit)(ElemType)) {
    LinkList p = L->next;			//指针重新指向头结点
    if(!p)	{
        printf("线性表未初始化。\n");
        return ERROR;
    }
    printf("结果是：");
    while(p) {
        pfn_visit(p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}// ListTraverse

int main(){
    LinkList L;
    InitList_L(L);
    CreatListHead_L(L);
    ListTraverse_L(L, visit);
    return 0;
}

尾插法函数

void CreateListTail(LinkList &L, int n) {
	LNode *p, *r = L;
	for(int i=0; i<n; i++){
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

单链表插入函数

// 初始条件：线性表L已存在，1≤pos≤ListLength(L)+1。
// 操作结果：在L中第pos个位置之前插入新的元素e，L的长度加1。
Status ListInsert_L(LinkList &L, int pos, ElemType e) {
    LinkList p = L;				//定义一个结构体指针变量p，指向线性表起始位置（头结点）L。
    int j = 0;
    //寻找第pos-1个结点，并令p指向其前趋。
    //p非空，且j<pos-1，说明指针位于线性表内
    
    
    if (!p || j>pos-1)	return ERROR;
    // 生成新结点s
    
    // 将插入的元素值赋给 新生成结点的数据域
    
    // 新生成结点的指针域 指向下一个结点
    
    // 结点pos-1的指针域 指向新生成的结点
    
    printf("插入的元素：%d, 插入的位置：%d\n", e, pos);
    return OK;
}// ListInsert_L 算法2.9

单链表删除函数

// 初始条件：线性表L已存在且非空，1≤pos≤ListLength(L)。
// 操作结果：删除L的第pos个数据元素，并用e返回其值,L的长度减1。
Status ListDelete_L(LinkList &L, int pos, ElemType &e) {
	LinkList p = L;	//定义一个结构体指针变量p，指向线性表起始位置（头结点）L。
    int j = 0;
    //寻找第pos-1个结点，并令p指向其前趋。
    //p非空，且j<pos-1，说明指针位于线性表内
    while(p && j < pos-1){
    	p = p->next;
    	j++;
	}
	LinkList q = p->next;
	p->next = q->next;
	e = q->data;
	printf("您要删除的数据是 %d \n", e);
	free(q);
    return OK;
}// ListDelete_L 算法2.10

head.h

//用到的库文件
#include <stdio.h>	//printf();scanf()
#include <stdlib.h> //exit()
#include <malloc.h>	//malloc()
#include <time.h>	//srand((unsigned)time(NULL));
//函数结果状态代码
#define TRUE	1
#define FALSE	0
#define OK		1
#define ERROR	0
#define INFEASIBLE	-1
#define OVERFLOW	-2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
//#define ElemType int	//也可以用宏定义确定ElemType类型
typedef int ElemType;
//-----线性表的单链表存储结构-----
typedef struct	LNode {		//自定义数据类型
    ElemType data;			//数据域
    struct LNode *next;	//指针域
} LNode, *LinkList;

Status InitList_L(LinkList &L);
Status DestroyList_L(LinkList &L);
Status ClearList_L(LinkList &L);
Status ListEmpty_L(LinkList L);
int ListLength_L(LinkList L);
Status GetElem_L(LinkList L, int i, ElemType &e);
Status compare(ElemType listElem, ElemType e);
int LocateElem_L(LinkList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType));
Status PriorElem_L(LinkList L, ElemType cur_e, ElemType &pre_e);
Status NextElem_Sq(LinkList L, ElemType cur_e, ElemType &next_e);
Status ListInsert_L(LinkList &L, int pos, ElemType e);
Status ListDelete_L(LinkList &L, int pos, ElemType &e);
Status visit(ElemType e);
Status ListTraverse_L(LinkList L, Status (*pfn_visit)(ElemType));
Status CreateList(LinkList &L);
void CreateList_L(LinkList &L, int n);
void CreateListTail(LinkList &L, int n);

单链表更多基本操作

// 操作结果：构造一个空的线性表L。
Status InitList_L(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode));
    if(!L) {						//存储分配失败
        printf("初始化失败");
        exit(OVERFLOW);			//exit(-1)程序异常退出
    }
    L->next = NULL;				// 先建立一个带头结点的单链表，并使头结点的指针域为NULL
    return OK;
}// InitList_L

// 初始条件：线性表L已存在。
// 操作结果：销毁线性表L。
Status DestroyList_L(LinkList &L) {
    free(L);						//释放线性表头结点指针域
    return OK;
}// DestroyList_L

// 初始条件：线性表L已存在。
// 操作结果：将L重置为空表。
Status ClearList_L(LinkList &L) {
    LinkList p = L->next, ptmp;	//p指向线性表头结点
    while(p) {						//释放每个结点的指针域
        ptmp = p->next;
        free(p);
        p = ptmp;
    }
    L->next = NULL;				//头结点指针域为空
    return OK;
}// ClearList_L

// 初始条件：线性表L已存在。
// 操作结果：若L为空表，返回TRUE，否则返回FALSE
Status ListEmpty_L(LinkList L) {
    return L->next ? FALSE : TRUE;
}// ListEmpty_L

// 初始条件：线性表L已存在。
// 操作结果：返回L中数据元素个数。
int ListLength_L(LinkList L) {
    int nElem = 0;
    LinkList p = L->next;			//p指向第一个结点
    while(p) {
        nElem ++;
        p = p->next;
    }
    return nElem;
}// ListLength

// 初始条件：线性表L已存在，1≤i≤ListLength(L) 。
// 操作结果：用e返回L中第i个数据元素的值。
Status GetElem_L(LinkList L, int i, ElemType &e) {
    LinkList p = L->next;			//初始化，p指向第一个结点
    int j = 1;						//j为计数器
    while ( p && j<i ) {			//顺指针向后查找，直到p指向第i个元素或p为空
        p = p->next;
        ++ j;
    }
    if ( !p || j>i )
        return ERROR;				//第i个元素不存在
    e = p->data;					//取第i个元素
    return OK;
}// GetElem_L 算法2.8

// 初始条件：线性表L已存在，compare()是数据元素判定函数。
// 操作结果：返回L中第1个与e满足compare()的数据元素的位序，若这样的数据元素不存在，则返回值为0。
Status compare(ElemType listElem, ElemType e) {
    return listElem == e ? TRUE : FALSE;
}// Compare
int LocateElem_L(LinkList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) {
    int pos = 1;
    LinkList p = L->next;			//p指向链表第1个元素
    while(p && !(*pfn_compare)(p->data, e)) {
        ++ pos;
        p = p->next;				//指针后移	p->next = NULL时 意味着找到表尾元素了
    }
    if(pos<=ListLength_L(L))		//pos的值在线性表中，返回元素的位序
        return pos;
    else
        return 0;
}// LocateElem_L

// 初始条件：线性表L已存在。
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status PriorElem_L(LinkList L, ElemType cur_e, ElemType &pre_e) {
    int i = LocateElem_L(L, cur_e, compare);
    if(i==0 || i==1) return ERROR;
    GetElem_L(L, i-1, pre_e);
    return OK;
}// PriorElem_L

// 初始条件：线性表L已存在。
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，pre_e无定义。
Status NextElem_Sq(LinkList L, ElemType cur_e, ElemType &next_e) {
    int i = LocateElem_L(L, cur_e, compare);
    if(i==0 || i==ListLength_L(L)) return ERROR;
    GetElem_L(L, i+1, next_e);
    return OK;
}// NextElem_Sq

// 顺位序输入(随机产生)n个元素的值，建立带表头结点的单链线性表L（尾插法）。
void CreateListTail(LinkList &L, int n) {
    srand((unsigned)time(NULL));	//初始化随机数种子
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;				//先建立一个带头结点的单链表
    for (int i=0; i<n; ++i) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        //scanf("%d", &p->data);	//输入元素值
        p->data = rand()%100;		//随机生成100以内的数字，将生成的元素值赋给新生成结点的数据域
        //插入到表尾
        L->next = p;				//上一结点的指针域指向新生成的结点（将新生成结点的指针域赋给上一结点的指针的指针域）
        p->next = NULL;			//将新结点的指针域置空
    }
}

1. 单链表就地逆置

**题目描述：**试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 O(1）。

void Reverse_L_1(LinkList &L){
    LNode *p, *r;
    p = L->next;
    L->next = NULL;
    while (p != NULL){
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
}

解法二：

void Reverse_L_2(LinkList &L){
    LNode *pre, *p = L->next, *r = p->next;
    p->next = NULL;
    while(r != NULL){
        pre = p;
        p = r;
        r = r->next;
        p->next = pre;
    }
    L->next = p;
}

2. 从头到尾反向输出各结点的值

**题目描述：**设 L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

void Print_reverse_L(LinkList L){
    if(L->next != NULL)
        Print_reverse_L(L->next);
    if(L != NULL)
        printf("%d ", L->data);
}//递归思想

void Print_reverse_L_02(LinkList L){
    if(L->next != NULL)
        Print_reverse_L_02(L->next);
    if(L != NULL)
        printf("%d ", L->data);
}//递归思想
//main函数中传入参数L->next;

3. 删除所有值为x的结点（带头结点）

**题目描述：**在带头结点的羊链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一 ，试编写算法以实现上述操作。

void Del_x_2(LinkList &L, ElemType x){
    LNode *p = L->next, *pre = L, *q;
    while(p != NULL){
        if(p->data == x){
            q=p;
            p=p->next;
            pre->next = p;
            free(q);
        }else{
            pre = p;
            p = p->next;
        }
    }
}

解法二：

void Del_x_2(LinkList &L, ElemType x){
	LNode *p = L->next, *pre = L, *q; 
	while(p!= NULL){
		if(p->data == x){
			q = p;
			pre->next = p->next;
			free(p);
			p = q->next;
		}
		else{
			pre = pre->next;
			p = p->next;
		}
	}
}

4. 删除所有值为x的结点（不带头结点）

**题目描述：**设计一个递归算法 ，删除不带头结点的单链表 L 中所有值为 x 的结点

void Del_x_1(LinkList &L, ElemType x){
    LNode *p;
    if(L == NULL) return;
    if(L->data == x){
        p = L;
        L = L->next;
        free(p);
        Del_x_1(L, x);
    }else
        Del_x_1(L->next, x);
}

5. 删除最小值结点（假设唯一）

**题目描述：**试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法（假设最小值结点是唯一的）

LinkList Delete_Min(LinkList &L){
    LNode *pre = L, *p = pre->next;
    LNode *minpre = pre, *minp = p;
    while(p != NULL) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    free(minp);
    return L;
}

6.判断带头结点的非空单链表是否递增有序

算法思想：

若单链表长度为1，则结论显然成立。
若单链表长度大于1，
则需判断每个结点的数据值
是否小于后继结点的数据值。
所以本算法应设两个指针p和q，
p指向当前结点，
q始终指向p的后继（如果后继结点存在），在扫描的过程中进行p和q值的比较，然后将p和q同时后移。

//判断带头结点的非空单链表是否递增有序
void Increase(LinkList L){
    LNode *p = L->next, *q;
    while(p->next != NULL){
        q = p->next;
        if(p->data <= q->data)
            p = q;
        else{
            printf("no！\n");
            return;
        }
    }
    printf("yes！\n");
}

7.移动最小值结点到链表最前面**

在一个带头结点的非空单链表中，将数据域值最小的结点移到链表的最前面，要求不得额外申请新的结点。

算法思想：

首先查找最小值结点q，
然后将其移到链表的最前面，
实质上是将该结点从链表中摘下，
再插入到表头位置。
需要注意的是：
从链表中摘下其实就是删除操作，
所以需要设一个指针pre指向q的前驱。

//数据域值最小的结点移到链表的最前面
void MoveMin(LinkList L){
    LNode *q = L->next, *pre = L;
    LNode *p = q;
    while(p->next != NULL){
        if(p->next->data < q->data){
            pre = p;
            q = p->next;
        }
        p = p->next;
    }
    //如果最小值是第一个结点，则无需下一步操作
	//不是第一个结点，则把最小值结点插入表头位置
    if(q != L->next){
        pre->next = q->next;
        q->next = L->next;
        L->next = q;
    }
}

找到最小值结点，我们在前面综合应用题4，删除最小值结点已经做过，当时是用了四个指针，上面的代码只用了三个，是对之前做了优化，之前代码回顾：

LinkList Delete_Min(LinkList &L){
    LNode *pre = L, *p = pre->next;
    LNode *minpre = pre, *minp = p;
    while(p != NULL) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    free(minp);
    return L;
}

8. 有序单链表插入元素x，仍有序

实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数x，并保持该序列的有序性。

算法思想：

先生成一个待插入的结点s，
然后依次与链表中各结点的数据域比较大小，
找到该结点的插入位置，插入即可

寻找插入位置有两种方法：
(1)设指针p, 比较s和p->next的数据域大小，
找到插入位置后，插入在p的后面。
(2)设指针q和p，q指向p的前驱，
比较s和p的数据域大小，
找到插入位置后，将s插入在q和p之间。

我们以第2种方法为例

//在递增的整数序列链表（带头结点）中插入一个新整数x，并保持该序列的有序性
Status Insert_LinkList(LinkList L, int x){
    LinkList s = (LinkList) malloc(sizeof (LNode));
    if(!s) return ERROR;
    s->data = x;
    LNode *q = L;
    LNode *p = L->next;
    while(p && p->data <= x){
        q = p;
        p = p->next;
    }
    s->next = p;
    q->next = s;
    return OK;
}

Status Insert_LinkList1(LinkList L, int x){
    LinkList s = (LinkList) malloc(sizeof (LNode));
    if(!s) return ERROR;
    s->data = x;
    LNode *p = L;
    while(p->next && p->next->data <= x){
        p = p->next;
    }
    s->next = p->next;
    p->next = s;
    return OK;
}

9. 删除有序单链表中值相同的多余结点

在一个带头结点，值非递减有序的单链表中，设计算法删除值相同的多余结点。

算法思想：

有序链表中值相同的元素一定连续存储，
可从头到尾扫描一遍单链表，
若当前结点与后继结点的元素值不相等，则指针后移；
否则删除该后继结点。

//删除有序单链表中值相同的多余结点
void Purge(LinkList L)
{
    LNode *p = L->next, *q;
    while(p->next != NULL)  //从前向后扫描链表
    {
        q = p->next;
        if(p->data == q->data)   //相邻元素比较，值相同则删除后一个结点
        {
            p->next = q->next;
            free(q);
        }
        else
            p = p->next;
    }
}

错误代码示范：样例1 2 2 2 3无法通过

void Purge1(LinkList L){
    LNode *p = L->next;
    while(p){
        if(p->data == p->next->data){
            p->next = p->next->next;
        }
        p=p->next;
    }
}

修改后：

void Purge(LinkList L){
	LNode *p = L;
	LNode *q;
	while(p->next != NULL){
		if(p->data == p->next->data){
			q = p->next;
			p->next = p->next->next;
			free(q);
		}
		else
			p = p->next;
	}
}

10.查找倒数第m个结点

请设计时间和空间上都尽可能高效的算法，在不改变链表的前提下，求链式存储的线性表的倒数第m（>0）个元素。

算法思想：

时间复杂度为O(n)，空间复杂度为O(1)，
也就是扫描一遍链表即查找成功。
可以设两个指针p和q，
先让q从前向后移动m个位置，
再让p和q同时后移。
这样p和q之间间隔m个结点，
当q指向表尾结点时，p就指向倒数第m个结点。
这种方法只需扫描一遍链表，时间复杂度为O(n)。

//查找倒数第m个结点
int BackLocate(LinkList L, int m){
    LNode *p , *q;
    p = q = L->next;
    int count = 0;
    while(q != NULL)    {
        count++;
        if(count > m)
            p = p->next;
        q = q->next;
    }
    if(m > count)	  //当m大于链表长度时，返回ERROR
        return ERROR;
    return p->data;
}

11.有序链表的连续删除

已知一个带头结点的单链表，数据域值为整型，且递增有序，设计算法删除链表中大于mink且小于maxk的所有元素，并释放被删结点的存储空间。

算法思想：

由于单链表是有序的，
大于mink且小于maxk的所有元素位置连续。
为此，可以查找第一个大于mink的结点，
然后依次删除小于maxk的结点。

**需要注意：**删除结点时需要记住被删结点的前驱结点，可以设指针p指向第一个大于mink的前驱结点，设指针q指向小于maxk的结点，在删除过程中，p是保持不动的。
注意：元素值等于mink和maxk的结点不能删除。

//有序链表的连续删除
void DeleteBetween(LinkList L, int mink, int maxk){
    LNode *p = L, *q, *u;
    while(p->next && p->next->data <= mink)
        p = p->next;   //p指向第一个大于mink的前驱结点
    if(p->next) {
        q = p->next;    //p不动，q指向操作对象
        while(q->data < maxk)   //依次删除p之后小于maxk的结点
        {
            u = q->next;          //u暂存后继结点的地址
            p->next = q->next;
            free(q);
            q = u;       //指针q后移
        }
    }
}

12.单链表按值递减排序

void Sort(LinkList &L){
    LNode *p = L->next, *pre;
    LNode *r = p->next;
    p->next = NULL;
    p = r;
    while(p!=NULL){
        r=p->next;
        pre = L;
        while(pre->next != NULL && pre->next->data > p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r;
    }
}