线性表之单链表基本操作

2024-02-01 19:02:52

单链表的定义

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

data	next

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取地存储结构，即不能直接找到表中某个特定地结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

单链表的基本操作（带头结点）

头插法与尾插法

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

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

void Print_List(LinkList L){
    LNode *p;
    p = L->next;
    while (p){
        printf("%5d", p->data);
        p = p->next;
    }
    printf("\n");
}

/*********************************
头插法
*********************************/

LNode* List_HeadInsert(LinkList L){
    LNode *s;
    int x;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x!=-1){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

/************************************
尾插法
************************************/
LNode* List_TailInsert(LinkList L){
    int x;
    L = (LNode*)malloc(sizeof(LNode));
    LNode *s, *r=L;
    scanf("%d", &x);
    while (x!=-1){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r=s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

头插法

第一步是s->next=L->next 。让待插入的结点的指针指向头结点所指向的位置。

第二步是L->next = s 。让头结点的指针指向待插入结点s，这样就完成了头插。

注意： 第一步与第二步不能弄混了，则就会出错， a 1 a_1 a1部分之后的结点会全部丢失，s结点的指针会指向自己。

尾插法

第一步是s->next = r->next

第二步是r->next = s

第三步是r=s，将r往后移动，才能实现尾插。

按位序查找结点值

/*********************************
按位序查找结点值
**********************************/
LNode *GetElem(LinkList L, int i)
{
    int j = 1;
    LNode *p;
    p = L->next;
    if (i==0)
        return L;
    if (i<1)
        return NULL;
    while (p && j < i)
    {
        p = p->next;
        j ++;
    }
    return p;
}

按值查找表结点

/*******************************
按值查找表结点
*******************************/
LNode *LocateElem(LinkList L, int e)
{
    LNode *p;
    p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    if (!p)
    {
        printf("该链表中没有%d这个值\n", e);
    }
    return p;
}

插入结点操作(通常情况下是后插)

/***************************
插入结点操作(通常情况下是后插)
****************************/
void InsertNode(LinkList L, int i, int e)
{
    LNode *p, *s;
    s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    p = GetElem(L, i-1);
    if (!p)
        printf("插入失败\n");
    else
    {
        s->next = p->next;
        p->next = s;
        printf("插入成功\n");
        // 以上就是后插部分，如果要改成前插，则需要再添加几行代码
//        int temp = p->data;
//        p->data = s->data;
//        s->data = temp;
    }
//    return L;
}

按位删除结点

/********************************
按位删除结点
********************************/

void DeleteNode(LinkList L, int i)
{
    LNode *p, *s;
    p = GetElem(L, i-1);
    if (!p)
        printf("无法删除\n");
    else
    {
        s = p->next;
        p->next = s->next;
        free(s);
        printf("删除成功\n");
    }
}

按值删除结点(仅删除一个)

/*************************************
按值删除结点(仅删除一个)
**************************************/

void DeleteNode2(LinkList L, int e)
{
    LNode *q, *p;
    q = L->next;
    p = L;
    while (q && q->data != e)
    {
        p = q;
        q = q->next;
    }
    if (!q)
        printf("该值不链表中\n");
    else
    {
        p->next = q->next;
        free(q);
        printf("删除成功\n");
    }
}

求表长

/***************************
求表长
***************************/
int Length(LinkList L)
{
    int length=0;
    LNode *p;
    p = L->next;
    while (p)
    {
        length ++;
        p = p->next;
    }
    return length;
}

主函数代码

int main()
{
    LNode* L, *res;
    L = (LNode*)malloc(sizeof(LNode));
    res = (LNode*)malloc(sizeof(LNode));
//    L = List_HeadInsert(L);
    L = List_TailInsert(L);
    Print_List(L);
    res = GetElem(L, 2);
    printf("该节点值为：%d\n", res->data);
    InsertNode(L, 2, 3);
    Print_List(L);
    DeleteNode(L, 2);
    Print_List(L);
    DeleteNode2(L, 34);
    Print_List(L);
    printf("这个单链表表长为:\t%d\n", Length(L));
    return 0;
}

码农公寓