[数据结构与算法]C语言实现单链表的基本操作

C语言实现单链表的基本操作

一：单链表

1：定义

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

2：特点

• 物理上不连续，逻辑上连续：可以将物理地址上不连续的内存空间连接起来，通过指针来对物理地址进行操作，实现逻辑上的连续（线性）。
• 头指针：单链表中每个结点的存储地址是存放在其前趋结点的next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定。
• 尾巴：终端结点无后继，故终端结点的指针域为空，即NULL。

二：单链表相关实现算法

L=(LinkList) malloc(sizeof (LinkList)); 在分配内存空间时，得注意malloc（）函数的使用

1：单链表结构体定义

• typedef int Elemtype：指的是在当前程序中Elemtype就代表的int（整型）的数据类型，相当于给int类型起了一个别名。
• 其中LNode,*LinkList写在{}后面的目的是为了方便使用。

/*数据元素类型*/
typedef int ElemType;
/*单链表结构体定义*/
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
}LNode,*LinkList;
//LinkList L; 声明一个指向单链表第一个结点的指针,这种方法代码可读性更强
/*
等价于
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
};
 typedef struct Lnode Lnode;
 typedef struct Lnode * Linklist;
*/

2：单链表的初始化

//初始化一个单链表--带头结点
LinkList InitList(LinkList L){
    //申请一块LinkList类型的空间给L
    L=(LinkList) malloc(sizeof (LinkList));   //f分配一个头结点
    if(L==NULL){
        return NULL;     //内存不足，分配失败
    }
    //将L的指针域设为空
    L->next=NULL;
    return L;
}

3：按照指定位序插入

按照位序插入 在第i个位置插入，插入的元素的值为e
思想：

• 首先判断i的值是否合法
• 初始化好一个指向头结点的指针
• 定义一个整型变量用来存储当前指针所指向结点的位置
• 其次将定义的指针移动到i-1结点点处
• 然后判断移动i-1位置的结点是否为NULL
• 在不为NULL的情况下，开辟一个新的LinkList类型的空间，其数据域中存入e
• 最后，进行连接结点的操作。

//按照位序插入   在第i个位置插入，插入的元素的值为e
int ListInsert(LinkList L,int i,ElemType e){
    if(i<1){//位置不合法
        return 0;
    }
    LNode *p;        //指针p指向当前扫描到的结点
    int j=0;         //当前指针指向的第几个元素
    p=L;             //L指向头指针，这里把头结点假设为第0个结点（不存在数据）
    //移动到第i-1个结点出
    while (p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    p = NULL;
    if(p){//i值所对应的结点不合法
        return 0;
    }
    //创建一个新的结点，并对新结点进行连接操作
    LNode *s= (LNode *)malloc(sizeof (LNode));
     s->data=e;//将待插入的数据放到新创建的指针的data中
     s->next=p->next;//将s与p结点的后继结点相连接
     p->next=s;//将p与结点s相连接
    return 1;
}

3：创建一个新结点

//创建一个新结点，并指定其数据域
LNode* CreatNode(int data){
    LNode *newNode=(LNode *) malloc(sizeof (LNode));
    if(newNode==NULL){
        printf("分配结点失败,请检查内存!");
        return NULL;
    }
    //将data传入新结点的数据域
    newNode->data=data;
    newNode->next=NULL;
    //返回新结点的指针
    return newNode;
}

4：指定结点的后插操作

后插操作：在p结点之后插入元素

思想：

• 首先对待插入的结点进行判断
• 然后利用malloc函数申请一个结点的内存空间
• 对该内存空间进行判断
• 将待插入的数据放到新建结点的数据域中
• 然后利用链表的连接操作即可

//指定结点的后插操作:在p结点后插入数据元素
int InsertNextNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    //然后进行取e值,连接结点的操作
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}

5：指定结点的前插操作

前插操作：在p结点之前插入元素

思想:
第一种：通过遍历单链表找到p的前驱结点q，然后在q结点后面插入一个新的元素。由于这种所耗费的时间复杂度为O(n)。

第二种：（偷天换日）–时间复杂度为O(1)

• 将新结点s连接的p之后
• 然后将p中的数据域中的值复制到新结点s
• 将p中的元素用待插入的元素进行覆盖

//指定结点的前插操作
int InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    s->next=p->next;//将新结点s连接的p之后
    p->next=s;
    s->data=p->data;//然后将p中的数据域中的值复制到新结点s
    p->data=e;      //将p中的元素用待插入的元素进行覆盖
    return 1;
}

6：按位序删除

按位序删除 --i指的是第i个结点，e用来返回删除的结点的数据域的数值

思想:首先得遍历到第i-1个结点，对该节点进行判空以及对该节点的后继结点进行判空操作，然后修改指针的执行删除第i个结点。

//按位序删除  --i指的是第i个结点，e用来返回删除的结点的数据域的数值
int ListDelete(LinkList L,int i,ElemType e){
    if(i<1){
        return 0;
    }
    LNode *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 0;
    }
    if(p->next==NULL) {//表示p结点后再无结点
        return 0;
    }
    LNode  *q=p->next;//令指针q指向待删除的结点
    e=q->data;      //用来记录删除结点的数据域中的值
    p->next=q->next; //将待删除的结点*q从当前链表中断开
    free(q);//释放结点所占用的内存空间
    return e;
}

7：指定结点的删除

由于删除该结点得修改前驱结点的next指针
方法1：传入头指针，循环寻找p的前驱结点
方法2：偷天换日（类似与结点前插的实现）–利用数据域中的值进行更新。

思想:

• 将待删除指针后面的数据域给待删除元素
• 然后只需将待删除指针后面的结点删除即可

//指定结点的删除--偷天换日
int DeleteNodee(LNode *p){
    if(p==NULL){
        return 0;
    }
    //这里如果p是最后一个结点，只能从表头依次寻找p的前驱结点
    LNode *q=p->next;   //令q指向*p的后继结点
    p->data=q->data;    //和后继结点交换数据域
    p->next=q->next;    //将*q结点从链表中断开
    free(q);    //释放后继结点的存储空间
    return 1;
}

8：按位查找

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

9：按值查找

//按值查找
LNode * LocateElem(LinkList L,ElemType e){
    LNode  *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

10：求单链表的长度

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

11：创键单链表

a:头插法:可用于链表的逆置

思想：

• 数据是通过输入来获取
• 没插入一个结点先申请一个结点所需的内存空间
• 然后利用头指针和新结点连接起来

//头插法
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;
    L=(LinkList *) malloc(sizeof(LNode));   //创建头结点
    L->next=NULL;   //初始为空链表
    scanf("%d",&x); //输入结点的值
    while (x!=1000){  //当输入1000时结束
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); //输入结点的值
    }
    return L;
}

b:尾插法

思想：

• 用一个指针一直为表尾指针
• 利用表尾指针和新开辟的内存空间进行操作

//尾插法
LinkList List_TailInsert(LinkList L){
    int  x;
    L=(LinkList) malloc(sizeof (LNode));//建立头结点，初始化一空表
    LNode *s,*r=L;          //r为表尾指针
    scanf("%d",&x); //输入结点的值
    while (x!=1000){    //当输入1000代表结束
        //在r结点之后插入x元素
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;      
        r=s;            //r指向新的表的尾结点
        scanf("%d",&x); //输入结点的值
    }
    r->next=NULL;           //为几点指针置为空
    return L;
}

三：完整代码

/**
 * 单链表的实现
 */
#include "stdio.h"
#include "stdlib.h"				//提供malloc()和free()
/*数据元素类型*/
typedef int ElemType;
/*单链表结构体定义*/
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
}LNode,*LinkList;



//初始化一个单链表--带头结点
LinkList InitList(){
    //申请一块LinkList类型的空间给L
    LinkList L=(LinkList) malloc(sizeof (LinkList));   //f分配一个头结点
    if(L==NULL){
        return NULL;     //内存不足，分配失败
    }
    //将L的指针域设为空
    L->next=NULL;
    return L;
}
//按照位序插入   在第i个位置插入，插入的元素的值为e
int ListInsert(LinkList L,int i,ElemType e){
    if(i<1){//位置不合法
        return 0;
    }
    LNode *p;        //指针p指向当前扫描到的结点
    int j=0;         //当前指针指向的第几个元素
    p=L;             //L指向头指针，这里把头结点假设为第0个结点（不存在数据）
    //移动到第i-1个结点出
    while (p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL){//i值所对应的结点不合法
        return 0;
    }
    //创建一个新的结点，并对新结点进行连接操作
    LNode *s= (LNode *)malloc(sizeof (LNode));
     s->data=e;//将待插入的数据放到新创建的指针的data中
     s->next=p->next;//将s与p结点的后继结点相连接
     p->next=s;//将p与结点s相连
    return 1;
}
//创建一个新结点，并指定其数据域
LNode* CreatNode(int data){
    LNode *newNode=(LNode *) malloc(sizeof (LNode));
    if(newNode==NULL){
        printf("分配结点失败,请检查内存!");
        return NULL;
    }
    //将data传入新结点的数据域
    newNode->data=data;
    newNode->next=NULL;
    //返回新结点的指针
    return newNode;
}
//指定结点的后插操作:在p结点后插入数据元素
int InsertNextNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    //然后进行取e值,连接结点的操作
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}
//指定结点的前插操作
int InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    s->next=p->next;//将新结点s连接的p之后
    p->next=s;
    s->data=p->data;//然后将p中的数据域中的值复制到新结点s
    p->data=e;      //将p中的元素用待插入的元素进行覆盖
    return 1;
}
//按位序删除  --i指的是第i个结点，e用来返回删除的结点的数据域的数值
int ListDelete(LinkList L,int i,ElemType e){
    if(i<1){
        return 0;
    }
    LNode *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 0;
    }
    if(p->next==NULL) {//表示p结点后再无结点
        return 0;
    }
    LNode  *q=p->next;//令指针q指向待删除的结点
    e=q->data;      //用来记录删除结点的数据域中的值
    p->next=q->next; //将待删除的结点*q从当前链表中断开
    free(q);//释放结点所占用的内存空间
    return e;
}
//指定结点的删除--偷天换日
int DeleteNode(LNode *p){
    if(p==NULL){
        return 0;
    }
    //这里如果p是最后一个结点，只能从表头依次寻找p的前驱结点
    LNode *q=p->next;   //令q指向*p的后继结点
    p->data=q->data;    //和后继结点交换数据域
    p->next=q->next;    //将*q结点从链表中断开
    free(q);    //释放后继结点的存储空间
    return 1;
}
//按位查找，返回第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){//循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}
//按值查找
LNode * LocateElem(LinkList L,ElemType e){
    LNode  *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}
//求单链表的长度
int LengthList(LinkList L){
    int len=0;
    LNode  *p=L->next;
    while (p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}
//头插法
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;
    L=(LinkList *) malloc(sizeof(LNode));   //创建头结点
    L->next=NULL;   //初始为空链表
    scanf("%d",&x); //输入结点的值
    while (x!=1000){  //当输入1000时结束
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); //输入结点的值
    }
    return L;
}
//尾插法
LinkList List_TailInsert(LinkList L){
    int  x;
    L=(LinkList) malloc(sizeof (LNode));//建立头结点，初始化一空表
    LNode *s,*r=L;          //r为表尾指针
    scanf("%d",&x); //输入结点的值
    while (x!=1000){    //当输入1000代表结束
        //在r结点之后插入x元素
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;
        r=s;            //r指向新的表的尾结点
        scanf("%d",&x); //输入结点的值
    }
    r->next=NULL;           //为几点指针置为空
    return L;
}
//判空操作
int  IsEmpty(LinkList L){
    if(L->next==NULL){
        return 1;
    }
    return 0;
}
//打印
void PrintList(LinkList L) {
    LNode *p;
    p=L->next;
    printf("单链表的数据为");
    while (p!=NULL){
        printf("%d   ",p->data);
        p=p->next;
    }
    printf("\n");

}
    int main(){
        //定义一个链表
        LinkList L = NULL;
        //[2]将链表初始化
        L = InitList();
//        L=List_TailInsert(L);      //利用尾插法创建单链表
        L=List_HeadInsert(L);        //利用头插法创建单链表--与输入的数值相逆
        PrintList(L);                //打印头插法创建的单链表
        if(IsEmpty(L)==1){           //对单链表进行判空
            printf("当前链表是空的！\n");
        } else{
            printf("当前链表不是空的！\n");
        }
        int len=LengthList(L);       //求链表的长度
        printf("当前单链表的长度为%d\n",len);

        LNode *s=LocateElem(L,2); //按照值查找
        printf("查找成功！值为%d\n",s->data);

       DeleteNode(s);           //删除s结点
        printf("删除成功!删除后的");
        PrintList(L);

        ListInsert(L,2,11);
        printf("新增成功!新增后");
        PrintList(L);
        return 0;

    }