数据结构——单链表（小白入门第二天）_typedef struct lnode

一、什么是单链表？

定义：每个结点 除了存放数据元素外，还要存储指向下一个节点的指针；

优点：不要求大片连续空间，改变容量方便；

缺点：不可随机存取，要耗费一定空间存放指针

局限性：无法逆向检索

二、用代码定义一个单链表

方法一：

struct LNode {
    ElemType data;//定义单链表节点类型  data变量用来存放数据元素（数据域）每个节点存放一个数据元素
    struct LNode* next;//定义指向下一个节点的指针（指针域） 指针指向下一个节点
};
struct LNode* p = (struct LNode*)malloc(sizeof(struct LNode));//增加一个新节点；再内存中申请一个节点所需空间，并用指针p指向这个结点

typedef<数据类型><别名>

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

方法二：

struct LNode {
    ElemType data;
    struct LNode* next;
};//先定义数据类型
 
typedef struct LNode LNode;//struct LNode 重命名为LNode
typedef struct LNode* LinkList;//用LinkList表示这个一个指向Struct LNode的指针

方法三：（方法二的简写）

typedef struct LNode{
ELemType data;
struct LNode* next;
}LNode, * LinList;

三、表示一个单链表

只需要声明一个头指针L，指向单链表的第一个结点

两种表达方式实质含义相同，强调重点不同 

 四、初始化单链表

4.1不带头结点的单链表：

4.2带头结点的单链表：

 L->next = NULL;( L这个指针指向的next指针域设置为NULL)

五、单链表的插入

5.1按位序插入（带头结点）

ListInsert(&L,i,e):插入操作；再表L的第i个位置上插入指定元素e，先找到i-1个结点

然后用malloc申请一个新结点，存入元素e，然后对指针进行修改

代码框架

typedef struct LNode
{
  ElemType data;  //数据域
  struct LNode *next; //指针域
}LNode,*LinkList;//定义结点
 
bool ListInsert(LinkList &L,int i,ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
  if(i<1)
	  return false;//i从1开始
  LNode *p;
  int j=0;//第0个结点,指向头结点,实际从第一个开始;表示当前p指向第几个跌点
  p=L; //L指向头结点,头结点不存数据
  while(p!=NULL && j<i-1) /* 寻找第i-1个结点 */
  {
    p=p->next;
    j++;
  }
  /*i-1插入新结点*/
  if(p==NULL)
	  return false;
  LNode *s;//新的结点s;
  s=(LinkList)malloc(sizeof(LNode)); /* 生成新结点 */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s; 
  return true;
}

(55条消息) 王道2-06 单链表的插入 删除_黑糖儿*的博客-CSDN博客

代码实现

#include <stdio.h>
#include<stdlib.h>
typedef struct LNode{ //定义单链表结点类型 
    int data;  //数据域 
    struct LNode *next; //指针域 (为什么next指针域要定义为struct LNode呢，)
}LNode, *LinkList;
 //(为什么next指针域要定义为struct LNode呢?)
//next指针用来指向链表的下一个结点，该结点同样为一个LNode结构体，
//因此next要声明为指向LNode结构体的指针struct LNode*
bool InitList(LinkList &L)
{
	L = (LNode *)malloc(sizeof(LNode));
	if(L == NULL)
		return false;
	L->next = NULL;
	return true;
} 
 
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e){  
    //判断i的合法性, i是位序号(从1开始)
    if(i<1)
        return false;
    
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL  寻找第i-1个结点
        p = p->next;             //p指向下一个结点
        j++;
    }
 
    if (p==NULL)                 //i值不合法
        return false;
    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;  
    s->next = p->next;
    p->next = s;                 //将结点s连到p后,后两步千万不能颠倒qwq
 
    return true;
}
 
void test()
{
	LinkList L;
	if(InitList(L))
		printf("true");
	printf("\n");
	
	ListInsert(L,1,3);
	ListInsert(L,2,5);
	LNode *s = L->next;
	
	while(s)
	{
		printf("%d ",s->data);
		s = s->next;
	}
	return;
}
 
int main(void)
{
	test();
	return 0;
}

(55条消息) 【数据结构】单链表按位序插入（带头节点）_向前的诚_的博客-CSDN博客_按位序插入

s->data = e;//将结点s的data值设置为e

s->next = p->next;//链表指针赋值，将p的下一个节点位置赋给s的下一个结点

p->next = s;//将结点s连接到p之后

平均复杂度O（n）

5.2按位序插入（不带头结点）

特殊处理：

if(i==1)
  {
	  LNode *s;//新的结点s;
	  s=(LinkList)malloc(sizeof(LNode)); /* 生成新结点 */
	  s->data=e; /* 插入L中 */
	  s->next=L;//p->next就是头指针
	  L=s; 
	  return true;
  }
  int j=1;//j从1开始

代码实现：
 

#include<stdio.h>
#include<stdlib.h>
 
#define ElemType int
typedef struct LNode{  //定义单链表结点类型 
	ElemType data;     //每个结点存放一个数据元素 
	struct LNode* next; //指针指向下一个结点 
}LNode,*LinkList;
 
//初始化一个空白的单链表 
bool InitList(LinkList &L)
{
	L=NULL;    //空表，暂时还没有存放任何结点（防止脏数据） 
	return true;
}
 
//在第i个位置插入元素e:
bool ListInsert(LinkList &L,int i,ElemType e)
{
	if(i<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指向第一个结点（不是头结点） 
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(p==NULL)return false;   //i值不合法 
	LNode* s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
 
void OutputList(LinkList L)
{
	LinkList p=L;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
 
int main()
{   //声明一个指向单链表的指针 
	LinkList L;
	//初始化一个空表 
	InitList(L);
	//在单链表的第i个位置插入元素i: 
	for(int i=1;i<=5;i++)ListInsert(L,i,i);
	//输出单链表中的所有元素： 
	OutputList(L);
	
	return 0;
}

注意j最开始设置为1，表示p刚开始指向的结点是第一个结点

5.3指定结点的后插操作

InsertNextNode（LNode *p，ElemType e）；

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;
 
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->next = p->next;
    p->next = s;           //将结点s连到p之后
    return true;
}

(55条消息) 数据结构单链表：指定结点的前插、后插操作_挑灯夜未央的博客-CSDN博客_指定结点的前插操作

时间复杂度O（1）

直接调用InsertNextNode（p，e）；

5.4 指定节点的前插操作

InsertPriorNode（LNode *p,ElemType e）;

单链表只能往后找，不能往前面。

malloc——先申请一个结点s；

 p->next = s——把新结点作为原来p结点的后置结点；

s->data = p->data——把p结点以前存放的数据元素复制到s结点；

p->data = e——把新插入的元素e放入原来p位置；

方法一：

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->next = p->next;      
    p->next = s;           //新结点s连到p之后
    s->data = p->data;     //将p中元素复制到s中
    p->data = e;           //p中元素覆盖为e
    return true;
}
 
//核心思想：由于没法直接找到p结点的前结点，可以先把s结点插入p结点之后，
//再把p结点的数据复制到s结点，最后把p中数据赋值为新插入值e。

方法二：

时间复杂度O（1）

六、单链表的删除

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

ListDelete(&L,i,&e)——删除操作，删除表中L中第i个位置的元素，并用e返回删除元素的值

找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点

//删除指定结点
bool DeleteNode(LNode *p){
    if(p==NULL)
      return false;
      LNode *q=p->next;  //令q指向*p的后继结点
      p->data=p->next->data;  //和后继结点交换数据域
      p->next=q->next;
      free(q);
      return true; 
}//如果p结点是最后一个结点，则只能从表头开始依次寻找p的前驱 ，时间复杂度O（n）

 ①找到第i-1个结点

bool ListDelete(LinkList &L, int i, int e){  
    //判断i的合法性, i是位序号(从1开始)
    if(i<1)
        return false;
    
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）
 
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL  寻找第i-1个结点
        p = p->next;             //p指向下一个结点
        j++;
    }

②LNode *q = p->next;

定义指针q指向p结点的下一个，即第i结点

 ③e=q->data;

接下来q结点里的数据元素复制到e里面去（e是引用型，前面要加&）

④  p->next=q->next;

p的next指向q的next ，即NULL????????

⑤  free(q);

释放q的内存空间

最好时间度O（1）

最坏时间度O（n）

 6.2 指定结点的删除

DeleteNode(LNode *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;
      free(q);
      return true; 
}//如果p结点是最后一个结点，则只能从表头开始依次寻找p的前驱 ，时间复杂度O（n）

 p->data=p->next->data——将p后继结点的数据复制到p的数据域里面

再让p结点的后继节点指向q的后继节点

 释放归还q结点

 七、单链表的查找

7.1 按位查找

GetElem(L,i)——获取表L中第i个位置的元素的值；

LNode * GetElem(LinkList L, int i){
    if (i<0){
        return NULL;
    }
    LNode *p;
    int j = 0;
    p=L;
    while (p!= NULL && j<i){
        p = p->next;
        j++;
    }
    return p;
}

在单链表的按位插入和删除中已经实现了第i-1个结点的查找

7.2 按值查找

 
LNode * LocateElem(LinkList L, int e){
    LNode *p = L->next;
    while (p != NULL && p->data != e){
        p = p->next;
    }
    return p;
}

①LNode *p = L->next——头指针p指向头结点的下一个结点

②while (p != NULL && p->data != e)——p≠NULL并且p的数据域≠e

p = p->next——满足条件让p指针指向下一个结点

 平均时间复杂度O（n）

7.3 求表的长度

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

时间复杂度O(n)

八、单链表的建立

①初始化一个单链表

#include<stdio.h>
#include<stdlib.h>
 
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);
}
 

(55条消息) 单链表的初始化代码_啊哈哈哈哈大魔王的博客-CSDN博客_初始化单链表的代码

②每次取一个数据元素插入到表尾/表头

8.1 尾插法

位序插入

每次都要从头开始遍历，时间复杂度为O（n^2）

设置一个表尾指针r，每次就都从表尾插入

 
LinkList List_TailInsert(LinkList &L){
    int x;
    L = (LinkList ) malloc(sizeof (LNode));
    LNode *s,*r=L;
    scanf("%d", &x);//输入节点的值
    while (x!=9999){//输入9999表示结束（可为任意值）
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;
        r = s;
        scanf("%d", &x);
    }
    r->next =NULL;
    return L;
}

  L = (LinkList ) malloc(sizeof (LNode))——malloc申请一个头结点，即初始化单链表的操作

LNode *s,*r=L——申明两个指针s，r都指向头结点

 s=(LNode *) malloc(sizeof (LNode))——申请新结点，让s指向新结点
 s->data=x——把新结点的数值设为x（输入值）

 r->next=s——把r的下一个指针指向s结点

r = s——让r指针指向s结点

........

 

8.2 头插法

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

 涉及其他知识点：

bool

返回值True or  False

(55条消息) C++中定义一个函数为bool类型的作用_&Mr.Gong的博客-CSDN博客_c++bool函数怎么用