
typedef struct Lnode{ //声明结点的类型和指向结点的指针类型
ElemType data;        //结点的数据域
struct Lnode *next;   //结点的指针域
｝Lnode,*LinkList;    //LinkList为指向结构体Lnode的指针类型

实例：


typedef Struct Student{
   char num[8];          //数据域
   char name[8];         //数据域
   int score;            //数据域
   struct student *next  //指针域
｝Lnode,*LinkList;

其中*next是指向一个同样是Struct Student结构类型的结点的指针。

2.2.2变量定义

LinkList L；

LNode *p，*s；

2.2.3重要操作

①p=L；//p指向头结点

②s=L->next; //s指向首元结点

③p=p->next; //p指向下一结点

三、单链表基本操作的实现

3.1单链表的初始化（带头结点的单链表）

即构造一个空表。

——>

(头结点）

3.1.1算法步骤

①生成新结点作为头结点，用头指针L指向头结点。

②将头结点的指针域置空。

3.1.2算法描述


Status InitList_L(LinkList &L){
  L=new LNode;           //或L=(LinkList) malloc(sizeof(LNode));
  L-->next=NULL;
  return OK;
}

3.2单链表的取值

取单链表中第i个元素的内容

3.2.1算法步骤

①从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next。

②j做计数器，累计当前扫描过的结点数，j初值为1。

③当p指向扫描到的下一结点时，计数器j加1。

④当j==i时，p所指的结点就是要找的第i个结点。

·特殊情况：

①i大于元素个数，则指针输出为空。

②i为0或负数，则直接不需要操作。

3.2.3算法描述


Status GetElem_L(LinkList L, int i,ElemType &e){  //获取线性表L中的某个数据元素的内容，通过变量e返回
  p=L—>next;j=1;    //初始化
  while(p&&j<i){    //向后扫描，直到p指向第i个元素或p为空
     p=p->next;++j;
  }
  if(!p||j>i) return ERROR;  //第i个元素不存在(p为空时，或者i大于元素个数)
  e=p->data;                 //取第i个元素
  return OK;
}//GetElem_L

3.3单链表的查找

·按值查找——查找数据元素；根据指定数据获取该数据所在的位置（地址）

3.3.1算法步骤

①从第一个结点起，依次和e相比较。

②如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址。

③如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。

3.3.2算法描述

①查找某个值的地址


Lnode *LocateElem_L(LinkList L,Elemtype e){ //在线性表L中查找值为e的数据元素，找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
 p=L->next;   //p指向首元结点
 while(p&&p->data!=e)  //p不为空且还未找到要查的值
    p=p->next;         //p继续往下扫描，进行查找，直到找到要查找的值，则循环结束。
 return p;             //返回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指向空结点。
     {p=p->next;j++;}
  if(p) return j;      //如果p存在不为空，就返回j的值
  else return 0;       //否则，返回0的值，查找失败
}

3.4单链表的插入

在第i个结点前插入值为e的新结点

3.4.1算法步骤

①首先找到a(i-1)的存储位置p

②生成一个数据域为e的新结点s

③插入新结点：

a.新结点的指针域指向结点a(i)；s->next=p->next

b.结点a(i-1)的指针域指向新结点。p->next=s

步骤a b不能互换，否则会丢失a(i)的地址。

3.4.2算法描述


Status ListInsert_L(LinkList &L,int i,ElemType e){ //在L中第i个元素之前插入数据元素e
   p=L;j=0;
   while(p && j<i-1){p=p->next;++j;}  //寻找第i-1各结点，p指向i-1结点
   if(!p || j>i-1) return ERROR;      //i大于表长+1或者小于1，插入位置非法
   s=new LNode; s->data=e;            //生成新结点s，将结点s的数据域置为e
   s->next=p->next;                   //将结点s插入L中
   p->next=s;
   return OK;
} //ListInsert_L

3.5单链表的删除

删除第i个结点

3.5.1算法步骤

①首先找到a(i-1)的存储位置p，保存要删除的a(i)的值。

②令p->next指向a(i+1)

③释放结点a(i)的空间。

3.5.2算法描述


Status ListDelete_L(LinkList &L,int i, ElemType &e){  //将线性表L中第i个数据元素删除
  p=L；j=0;
  while(p->next && j<i-1){p=p->next;++j;}      //寻找第i个结点，并令p指向其前驱
  if(!(p->next)||j>i-1) return ERROR;          //删除位置不合理（大于n、小于1)
  q=p->next;                                   //临时保存被删结点的地址以备释放
  p->next=q->next;                             //改变删除结点前驱结点的指针域
  e=q->data;                                   //保存删除结点的数据域
  detele q;                                    //释放删除结点的空间
return OK；
}//ListDelete_L

查找、插入、删除算法时间效率分析

①查找：因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n）

②插入和删除：因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)

但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)

3.6单链表的建立

3.6.1头插法

元素插在链表头部，也叫前插法

①从一个空表开始，重复读入数据

②生成新结点，将读入数据存放到新结点的数据域中

③从最后一个结点开始，依次将各结点插入到链表的前端

算法描述


void CreateList_H(LinkList &L,int n(n个结点){
    L=new LNode;
    L->next=NULL;  //先建立一个带头结点的单链表，指针域为空
    for(i=n;i>0;--i){
      p=new LNode; //生成新结点p
      cin>>p->data; //输入元素值
      p->next=L->next; //将头结点的空给到p的指针域，来插入到表头
      L->next=p;
    }
}//CreateList_H

算法的时间复杂度为O(n)

3.6.2尾插法

元素插入在链表尾部，也叫尾插法

①从一个空表开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点

②初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

算法描述


//正位序输入n个元素的值，建立带头结点的单链表L
void CreateList_R(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    r=L;          //尾指针r指向头结点
    for(i=0;i<n;i++){
       p=new LNode;  //生成新结点
       cin>>p-data;  //输入元素值
       r-next=p;     //插入到表尾
       r=p；         //r指向新的尾结点
    }
}//CreateList_R

算法的时间复杂度为O(n)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/829641