博客

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

定义结构

typedef struct LINK//定义结构链表
{
    int data;//数据域
    struct LINK *next;//指针域
}link;

初始化链表

link * initlink(){//初始化一个单链表
    link * p=(link*)malloc(sizeof(link));//创建头结点
    link * temp = p;//创建一个临时指针指向头结点
    for(int i=10;i>=1;i--){//创建一个1-10的单链表
        link *a = (link*)malloc(sizeof(link));//申请一个新节点
        a->data = i;
        a->next = NULL;//初始化新节点
        temp->next=a;
        temp = temp->next;//临时指针指向下一个
    }
    return p;
}

遍历输出链表

void putout(link *p){//遍历输出链表
    link *temp = p;
    while(temp->next){
        temp = temp->next;
        printf("%d ",temp->data);
    }
    printf("\n");
}

按序查找元素

int finddata(link *p,int i){//按序查找元素的位置,i为要查找的值
    link *temp = p;
    int j = 0;
    while(j<i && temp){
        temp = temp->next;
        j++;
    }
    return temp->data;
}

插入

link * insertelme(link *p,int loc,int elem){//插入元素，loc为位置，elem为元素的值
    link *temp = p;
    for(int i=1;i<loc;i++){
        if(temp == NULL){
        printf("插入地址无效\n");
        return p;
        }
        temp = temp->next;
    }
    link * a = (link*)malloc(sizeof(link));
    a->data = elem;
    a->next = temp->next;
    temp->next = a;
    return p;
}

删除

link * delete(link *p,int loc){//删除元素，loc为删除的位置
    link *temp = p;
    for(int i=1;i<loc;i++){
        temp = temp->next;
    }
    temp->next = temp->next->next;
    return p;
}

改变指定位置的元素

link * change(link *p,int loc,int elem){//改变元素的值，loc为元素的位置，elem为更改后的值
    link *temp = p;
    for(int i=1;i<=loc;i++){
        temp = temp->next;
    }
    temp->data = elem;
    return p;
}

链表长度

int lenth(link *p){
    int cnt = 0;
    link *temp = p;
    while(temp->next){
        temp = temp->next;
        cnt++;
    }
    return cnt;
}

整合代码

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

typedef struct LINK//定义结构链表
{
    int data;//数据域
    struct LINK *next;//指针域
}link;

link * initlink();//初始化链表
int finddata(link *p,int i);//按序查找元素的位置,i为要查找的值
link *insertelme(link *p,int loc,int elem);//插入元素，loc为位置，elem为元素的值
link * delete(link *p,int loc);//删除元素，loc为删除的位置
link * change(link *p,int loc,int elem);//改变元素的值，loc为元素的位置，elem为更改后的值
int lenth(link *p);//查链表的长度
void putout(link *p);//输出p链表

int main(){//可以在这里修改各个函数的值，来进一步理解
    printf("初始化单链表为：\n");
    link *p = initlink();
    putout(p);

    printf("按序查找7的位置:\n");
    int fdata=finddata(p,7);
    printf("%d\n",fdata);
    

    printf("在第3位插入2\n");
    p = insertelme(p,3,2);
    putout(p);

    printf("删除第4位的节点\n");
    p = delete(p,4);
    putout(p);

    printf("更改第7位的数据为1\n");
    p = change(p,7,1);
    putout(p);

    printf("单链表的长度为：\n");
    int a =lenth(p);
    printf("%d",a);

    return 0;
}

link * initlink(){//初始化一个单链表
    link * p=(link*)malloc(sizeof(link));//创建头结点
    link * temp = p;//创建一个临时指针指向头结点
    for(int i=10;i>=1;i--){//创建一个10-1的单链表
        link *a = (link*)malloc(sizeof(link));//申请一个新节点
        a->data = i;
        a->next = NULL;//初始化新节点
        temp->next=a;
        temp = temp->next;//临时指针指向下一个
    }
    return p;
}

void putout(link *p){//遍历输出链表
    link *temp = p;
    while(temp->next){
        temp = temp->next;
        printf("%d ",temp->data);
    }
    printf("\n");
}

int finddata(link *p,int i){
    link *temp = p;
    int j = 0;
    while(j<i && temp){
        temp = temp->next;
        j++;
    }
    return temp->data;
}


link * insertelme(link *p,int loc,int elem){
    link *temp = p;
    for(int i=1;i<loc;i++){
        if(temp == NULL){
        printf("插入地址无效\n");
        return p;
        }
        temp = temp->next;
    }
    link * a = (link*)malloc(sizeof(link));
    a->data = elem;
    a->next = temp->next;
    temp->next = a;
    return p;
}

link * delete(link *p,int loc){
    link *temp = p;
    for(int i=1;i<loc;i++){
        temp = temp->next;
    }
    temp->next = temp->next->next;
    return p;
}

link * change(link *p,int loc,int elem){
    link *temp = p;
    for(int i=1;i<=loc;i++){
        temp = temp->next;
    }
    temp->data = elem;
    return p;
}

int lenth(link *p){
    int cnt = 0;
    link *temp = p;
    while(temp->next){
        temp = temp->next;
        cnt++;
    }
    return cnt;
}

输出结果

初始化单链表为：
10 9 8 7 6 5 4 3 2 1 
按序查找7的位置:
4
在第3位插入2
10 9 2 8 7 6 5 4 3 2 1
删除第4位的节点
10 9 2 7 6 5 4 3 2 1
更改第7位的数据为1
10 9 2 7 6 5 1 3 2 1
单链表的长度为：
10