数据结构 - 单链表

单链表定义

danliang

定义单链表

struct LNode{  // 节点
    ElemType data;   	// 每个节点存放一个数据元素
    struct LNode *next;	// 指针指向下一个节点 指针域
};

/**
 * 增加一个新的节点：在内存中申请一个节点所需要的空间，并用指针p指向这个节点
**/
struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));

C语言： typedef关键字 -- 数据类型重命名 typedef <数据类型> <别名> 如：typedef int zhengshu

struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));
//可以写为如下：

typedef struct LNode LNode
LNode * p =(LNode *) malloc(sizeof(LNode));

在《数据结构》中定义的单链表代码如下：

typedef struct LNode{
    ELemType data;   	// 每一个节点存放一个数据元素
    struct LNode *next; // 每个节点存放一个数据元素
}LNode, *LinkList;

// 以上代码实际上时以下代码的简化

struct LNode{
    ElemType data;  	// 每个节点存放一个数据元素
    struct * next 		// 指针指向下一个节点
};

typedef struct LNode LNode;
typedef struct *LinkList;

// 要表示一个单链表的时，只需要声明一个头指针L，指向单链表的第一个节点
// LNode * L;  声明一个指向单链表第一个结点指针
// 或：LinkList L;  声明一个指向单链表第一个节点的指针

初始化单链表：

// 不带头节点的单链表
typedef struct LNode{
    ElemType data;
  struct LNode *next;
}LNode,*LinkList;

// 初始化一个空的单链表
bool InitList(LinkList &L){
    L =NULL;  // 空表，暂时没有节点， 防止有脏数据
    return true;
}

void test(){
    LinkList L; // 声明一个单链表的指针
    // 初始化一个单链表
    InitList(L);
    //...后续代码
}

   // 带头节点的单链表

  typedef struct LNode{
      ELemType data;
      struct LNode * next;
  }LNode,*LinkList;
  
  // 初始化一个单链表（带头节点）
  bool InitList(LinkList &L){
      L = (LNode*)malloc(sizeof(LNode)); // 给头节点分配一块内存
      if(L==NULL){ // 内存不足，分配失败
          return false;
      }
      L->= NULL; // 在头节点之后暂时还没有节点
      return true;
  }
  
  void test(){
      
      LinkList L; // 声明一个单链表的指针
      InitList(L) // 初始化单链表
  }

单链表的插入

按位序插入（带头节点）

ListInsert(&L,i,e)：插入操作。在表中的第i个位置插上指定元素e。

找到第i - 1 个节点，将新节点插入其后

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode,*LinkList;

// 在第i个位置插入元素e（带头节点）
bool ListInsert(LinkList &L, int i, int e) {
	if (i<1) {
		return false;
	}
	LNode *p; // 指针p指向当前扫面到的节点
	int j = 0; // 当前p指向的是第几个节点
	p = L; // L指向头节点，头节点是第0个节点（不包含数据）
	while (p!=NULL&&j<i-1) { // 循环找到第i-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;
}
// 初始化单链表
bool Init(LinkList &L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L==NULL) {
		printf("内存不足，分配失败！");
		return false;
	}
	L->next = NULL; // 后面没有节点了
	printf("分配成功！");
	return true;
}
int main() {

	LinkList L; // 声明一个单链表的指针
	Init(L); // 初始化单链表
	ListInsert(L, 1, 1);
	return 0;
}

平均时间复杂度为O(n)

按位序插入（不带头节点）

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
	int data;
	struct LNode*next;
}LNode,*LinkList;

bool ListInsert(LinkList &L,int i,int e) {
	if (i<1) { // 插入第1个节点的操作和其他的节点操作不同
		return false;
	}
	if (i == 1) {
		LNode *s = (LNode*)malloc(sizeof(LNode)); // 分配一块内存空间来创建节点
		s->data = e;    //将插入的数据赋值到内存空间中
		s->next = L;    //将新建的内存指针指向头节点
		L = s;			// 头指针指向新节点
		return true;
	}
	LNode *p;			// 指针p指向当前扫描的节点
	int j = 1;			// 当前p指向的是第几个节点
	p = L;				// p指向第1个节点（注意：不是头节点）
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p==NULL) {
		return false;
	}
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
// 初始化单链表
bool Init(LinkList &L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L==NULL) {
		printf("内存不足，分配失败！");
		return false;
	}
	L->next = NULL; // 后面没有节点了
	printf("分配成功！");
	return true;
}
int main() {

	LinkList L; // 声明一个单链表的指针
	Init(L); // 初始化单链表
	ListInsert(L, 1, 1);
	return 0;
}

如果不带头节点，则插入、删除第1个元素时，需要更改头指针L

指定节点的后插操作

typedef struct LNode{
    int data;
    struct LNode *next;
}

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

typedef struct LNode {
	int data;
	struct LNode*next;
}LNode,*LinkList;

// 在第i个位置插入元素e(带头节点)
bool ListInsert(LinkList &L, int i, int e) {
	if (i < 1) {
		return false;
	}
	LNode *p;	// 指针p指向当前扫描到的节点
	int j = 0;	// 当前p指向的是第几个节点
	p = L;		// 指向头结点，头结点时第0个节点(不保存数据)
	while (p != NULL&&j<i-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;
	return true;*/

	// 以上注释代码可以用
	return InsertNextNode(p, e);

}

指定节点的前插操作

bool InserPriorNode(LNode *p,ELemType e)

上面那种情况如何能够找到p节点的前驱节点呢？

所以需要传入一个==头指针==，如下：

bool InsertPriorNode (LinkList L,LNode *p,ElemType e)

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode,*LinkList;

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

}

在要插入之前的元素中的数据和指针重新指向，如上图所示；

单链表的删除

按位序删除（带头节点）

ListDelete(&L,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值 找到第i-1个节点，将其指针指向第i+1个节点

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode,*LinkList;

// 按位序删除（带头节点）
bool ListDelete(LinkList &L, int i, int &e) {
	if (i<1) {
		return false;
	}
	LNode *p;	// 指针p指向当前扫描的节点
	int j = 0;  // 指针p指向的是第几个节点
	p = L;		// 指向头节点，头节点是第0个节点（不保存数据）
	while (p!=NULL&&j<i-1) {	// 循环找到第 i-1个节点
		p = p->next;
		j++;
	}
	if (p==NULL) { // i值不合法
		return false;
	}
	if (p->next==NULL) {	// 第i-1个节点之后已无其他节点
		return false;
	}
	LNode *q = p->next;		// 令q指向被删除节点
	e = q->data;			// 用e返回元素的值
	p->next = q->next;		// 将*q节点从链中“断开”
	free(q);				// 释放节点的存储空间
	return true;			// 删除成功
}

时间复杂度 最坏、平均的时间复杂度 = O(n) 最好时间复杂度 = O(1)

指定节点删除

bool DeleteNode(LNode *p)

删除节点p：需要修改前驱节点的next指针

• 方法1：传入头指针，循环寻找p的前驱节点
• 方法2：偷天换日

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;
}

单链表的查找

按位查找

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

按值查找

// 按值查找，找到数据与 == e 的节点
LNode* LocateELem(LinkList L,ElemType e){
    LNode *p = L->next;
    // 从第1个节点开始查找数据域中e的节点
    while(p!=NULL&&p->data!=e){
        p = p->next;
    }
    return p;		// 找到后返回该节点指针,否则返回NULL
}

单链表的长度

// 求表的长度
int length(LinkList L){
    int len  =0 ; // 统计表长
    LNode *p = L;
    while(p->next !=NULL){
        p = p ->next;
        len++;
    }
    return len;
       
}

单链表的建立

如果给你很多元素（ElemType），要把它们存在一个单链表里边，怎么操作？

• Step1：初始化一个单链表
• Step2：每次取一个数据元素，插入到表尾/表头

尾插法建立单链表

typedef struct LNode{	// 定义 单链表节点类型
    ElemType data;		// 每一个节点存放一个数据元素
    struct LNode *next; // 指针指向下一个节点
}LNode,*LinkList;

// 初始化一个单链表（带头节点）
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //	分配一个头节点
    if(L==NULL){
        return false;	// 内存不足分配失败
    }
    L->next =NULl;		// 头节点之后还没有节点
    return true;
}

void test(){
    LinkList L; 	// 声明一个指向单链表的指针
    // 初始化一个空表
    InitList(L);
    
   // 后续操作
}

设置length 记录链表的长度

while(){
    // 每次取一个数据元素e;
    ListInsert(L,length+1,e); // 插到尾部
    length++;
}

具体代码如下：

LinkList List_TailInsert(LinkList &L){ // 正向建立单链表
    int x;							   // 设ElemType为整形
    L =(LinkList)malloc(sizeof(LNode));// 建立头节点
    LNode *s,*r=L;						// r为表尾指针
    scanf("%d",&x);						// 输入节点的值
    while(X!9999){						// 输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r = s;							//  r指向新的表尾点
        scanf("%d"&x);
    }
    r->next =NULL;						// 表尾节点置空
    return L;
    
}

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){	// 逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));	// 创建头节点
    L->next =NULL;						// 初始为空表
    scanf("%d",&x);						// 输出插入的元素
    while(x!9999){						// 当输入9999表示结束
        s(LNode *)malloc(sizeof(LNode));// 创建新节点
        s->data=x;
        s->next=L->next;
        L->next=s;						// 将新节点插入到表中，L为头指针
        scanf("%d",&x)
    }
    return L
}

头插法可以用作单链表的逆置