欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的基本操作

程序员文章站 2024-03-06 08:14:07
...

单链表的操作是数据结构中最基础的,每次看完就会忘,总是记个大概。总结一下:

单链表中的单位是结点,那么结点中包含数据域和指针域,指针域指向下一个结点的地址。

1、定义结点(定义结构):

//定义结点结构
typedef struct LNode{
    int data;              //数据域
    struct LNode *next;    //指针域
}LNode,*Linklist;

2、初始化结点:

(结构定义 了,但是数据并没有装进结构,初始化就是把数据域和指针域都初始化,一般情况数据域给定数值或字符,指针域初始化为NULL,还要注意的是初始化的结点返回的都是指针

// 初始化一个节点
Linklist initnode(int data)
{
    Linklist pnode = (Linklist)malloc(sizeof(LNode));
    pnode->data = data;    // 初始化数据域
    pnode->next = NULL;    // 初始化指针域为NULL

    return pnode;
}

3、尾插法建立链表

//创建一个链表节点(尾插法)
Linklist createlink_bytail(Linklist phead, int data)
{
    Linklist pnode = initNode(data);//初始化结点,这里注意,只要是插入元素,第一步都是要把数据初始化成结点
    Linklist ptmp = phead;          //定义一个临时指针,指向头结点

    if(NULL == phead)               //当链表为空,直接返回初始化的结点
    {              
        return pnode;
    }
    else
    {
        while(ptmp->next != NULL)  //找到最后一个结点,插在尾部
        {
            ptmp = ptmp->next;
        }
        ptmp->next = pnode;
    }
    return phead;
}
    

4、链表的长度

//求链表长度
int linklen(Linklist phead)
{
    int len = 0;            //计数器
    Linklist ptmp = phead;
    
    while(ptmp != NULL)
    {    
        len++;              //遍历链表,计数器加1,这里要注意的是和下一行不能交换位置,因为是第一个结点直接是 1 了
        ptmp = ptmp->next;
    }
    
    return len;
}

5、按位置查找

//按位置查找
int getElem(Linklist phead,int i)
{
    int e;
    Linklist ptmp = phead;
    int j = 0;
    while(ptmp != NULL && j < i)
    {
        ptmp = ptmp ->next;
        ++j;
    }
    e = ptmp ->data;
    return e;        
}

6、按位置插入

//按位置插入
//在 i 位置之前,插入元素数据 e
void insertList(Linklist phead,int i,int e)
{
    Linklist ptmp = phead;
    Linklist pnode = initNode(e);
    int j = 0;
    while(ptmp != NULL && j < i - 1)
    {
        ptmp = ptmp->next;
        ++j;
    }
    pnode->next = ptmp->next;
    ptmp->next = pnode;
}

7、按位置删除

//按位置删除
//删除第 i 个元素
void listDelete(Linklist phead,int i)
{
    Linklist ptmp = phead;
    Linklist q;
    int j = 0;
    while(ptmp != NULL && j < i - 1)// 这里注意想要删除第 i 个元素,首先要找到的是i前面的位置
    {
        ptmp = ptmp ->next;
        ++j;
    }
    q = ptmp ->next;        // 现在ptmp是要删除的结点的上一个的位置,所以要找到它的下个结点再处理
    ptmp ->next = q ->next; // 本来是想这么写,ptmp ->next = ptmp ->next ->next; 然后发现没法释放结点
    free(q);                // 如果想把这个删除的结点值返回可以在做个返回值,要在调用free()之前,e = q ->data
}

8、链表的排序(冒泡)

// 单链表的排序(冒泡排序)
//首先讲正常的一个数组冒泡排序
    const int N = 6;
    int a[N] = {4,5,1,9,7,6};
    for(int i = 0;i < N - 1;i++)
        for(int j = 0;j < N - i - 1;j++)
            if(a[j] > a[j + 1])
            {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
//链表的冒泡排序,虽然链表有两个域,但是其实只是交换数据域即可
Linklist linkSort(Linklist phead)
{
    Linklist p = phead;
    int n = linklen(phead);
    for(int i = 0;i < n - 1;i++)
    {
        p = phead; // 和普通数组做比较,第一轮比较完之后,继续从开始的两个元素开始比较,
                   // 而链表的p已经移到了最后,所以要先挪到最左再重新开始
                   // 而且这里还要看链表是否带有头结点,如果有头结点,我认为应该是 p = phead->next;
        for(int j = 0;j < n - i - 1;j++)
        {
            if(p->data > p->next->data)
            {
                int temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p ->next;
        }
    }
    return phead;
}

 

相关标签: 数据结构