目录

 

1、链表的概念

1.1 链表的定义

1.2 头指针、头结点和首元结点

1.3 空表的表示

1.4 头结点的好处

1.5 头结点的数据域

1.6 链表（链式存储结构）的特点

2、单链表的定义

3、单链表的基本操作

3.1 初始化

3.2 判断空表

3.3 销毁

3.4 清空

3.5 求单链表的表长

3.6 取第i个元素值

3.7 查找

3.7.1 按值查找

3.7.2 按位查找

3.8 插入

3.9 删除

4、建立单链表

4.1 头插法——每次插在头结点的后头

4.2 尾插法——元素插入在链表的尾部

---

 

1、链表的概念

1.1 链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针

1.2 头指针、头结点和首元结点

头指针：是指向链表中第一结点的指针；

首元结点：是指链表中存储第一个数据元素a1的结点；

头节点：是在链表的首元结点之前附设的一个结点；

1.3 空表的表示

1）无头结点的链表：头指针为空时表示空表

2）有头结点的链表：当头结点的指针域为空时表示空表

1.4 头结点的好处

• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表上的其他位置上的操作一致，无须进行特殊处理。

• 无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。

1.5 头结点的数据域

头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值

1.6 链表（链式存储结构）的特点

1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上还不相邻

2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其他结点，所以寻找的第一个结点和最后一个结点所花的时间不等（顺序存取法）

注意：顺序表是随机存取，顺序存储

链表是顺序存取，非顺序存储

2、单链表的定义

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名，若头指针的名是：L，则把链表称为表L

不带头结点的单链表

定义链表头指针L：LinkList L；

定义结点指针P：LNode *p；

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

3、单链表的基本操作

3.1 初始化

//初始化一个空的单链表
bool InitList(LinkList &L){
    L=new LNode;//或L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;       //空表，暂时还没有任何结点。防止脏数据
    return OK;
}

3.2 判断空表

int LIstEmpty(LinkList L){//若L为空表，贼返回1，否则返回0
    if(L—>next)//非空
        return 0;
    else
        return 1;
}

3.3 销毁

L指向头结点的指针域，这样就指向了下一个结点，然后再指向下一个结点的指针域，不断操作，销毁单链表

Status DestroyList_L(LinkLIst &L){
    Lnode *p;//LinkList p;
    while(L){
        p=L;//将头结点的指针赋值给p,从头结点开始
        L=L->next;
        delete p;
    }
}

3.4 清空

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

算法思路：依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList & L){
    Lnode *p，*q；//或者LinkList p,q;
    p=L->next;
    while(p){   //没到表尾
        q=p->next;
        delete p;
        p=q;
    }
    L->next=NULL;   //头结点指针为空
    return OK;
}

3.5 求单链表的表长

int ListLength_L(LinkList L){
    LinkList p;
    p=L->next;
    i=0;
    while(p){
        i++；
        p=p->next;
    }
    return i;
}

3.6 取第i个元素值

Status GetElem_L(LinkList L,int i,ElemType &e){
    p=L->next;  //初始化
    j=1;        //初始化
    while(p&&j//向后扫描，直到p指向第i个元素或p为空
        p=p->next;
        j++;
    }
    if(!p\\j>i) return ERROR;   //第i个元素不存在
    e=p->data;                  //取第i个元素
    return OK;
}//GetElem_L

3.7 查找

3.7.1 按值查找

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

3.7.2 按位查找

//按位查找，返回第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个结点
        p=p->next;
        j++;
    }
    return p;
}

3.8 插入

1）首先找到ai-1的存储位置p

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

3）插入新结点：

• 新结点的指针域指向结点ai

• 结点ai-1的指针域指向新结点

第一步、将p指向的结点的指针域（原本下个结点的地址）赋值给s的指针域 s->next = p->next;

第二步、将s的指针域赋值给将p指向的结点的指针域（原本下个结点的地址）p->next = s

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

3.9 删除

算法步骤：

第一步、首先找到ai-1的存储位置p，保存要删除的ai的值

第二步、令p->next指向ai-1；

将i的指针域（i+1的指针）指向i-1的指针域（i的指针）：p->next = p->next ->next

Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;
    j=0;
    while(p->next&&j1){//寻找第i个结点，并令p指向其前驱
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i-1)//删除位置不合适
        return ERROR;
    q=p->next;//临时保存被删结点的地址以备释放
    p->next=q->next//改变删除结点前驱结点的指针域
    e=q->data;//保存删除结点的数据域
    delete q;//释放删除结点的空间
    return OK;
}//ListDelete_L

4、建立单链表

4.1 头插法——每次插在头结点的后头

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

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

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

 

void CreateList_H(LinkList &L,int n){
    //逆位序输入n个元素的值，建立带表头结点的单链表L
    L=(LinkList)malloc(sizeof(LNode));//L = new LNode
    L->next=NULL;           //先建立一个带头结点的空链表
    LNode *p;
    for(int i=n;i>0;i--){
        p=(LinkList)malloc(sizeof(LNode));//生成新结点*p
        cin>>p->data;       //输入元素值复制给新结点*p的数据域
        p->next=L->next;L->next=p;  //将新结点*p插入到头结点之后    
    }
}

4.2 尾插法——元素插入在链表的尾部

void CReateLIst_R(LinkList &L,int n){
    //正位序输入n个元素的值，建立带表头结点的单链表L
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;       //先建立一个带头结点的空链表
    LNode *p;
    LNode *r=L；         //尾指针r指向头结点
    for(i=0;i
        p=(LinkList)malloc(sizeof(LNode));//生成新结点
        cin>>p->data;       //输入元素值复制给新结点*p的数据域
        p->next=NULL;       //新插入的结点指针置空
        r->next=p;          //将新结点*p插入尾结点*r之后
        r=p;                //r指向新的尾结点*p
    }
}