数据结构——链表总结
本文最后更新于285 天前,其中的信息可能已经过时,如有错误请发送邮件到echobydq@gmail.com

单链表操作

  1. Status 是函数的类型,其值是函数结果状态代码

    typedef int Status

  2. //函数结果状态代码

    #define True 1

    #define False 0

    #define OK 1;

    #define ERROR 0

    #define INFEASIBLE -1

    #define OVERFLOW -2


     

1.单链表的定义和表示

typedef struct {
    char name[10];
    char num[20];
    double score;
}Stu;

typedef struct LNode {
    Stu data;
    struct LNode *next;
}LNode,*LinkList;

 

2.初始化链表(带头结点的单链表)

思路:

  1. 生成新结点作头结点,用头指针L指向头结点
  2. 头结点的指针域置空
Status InitList_L(LinkList L)
{
    L = (LinkList)mallloc(sizeof(LNode));
    L->next = NULL;
    return OK;
}

 

3.判断链表是否为空

  1. 空表:链表中无元素(头指针和头结点仍然存在)

    思路:判断头结点指针域是否为空

    Status ListEmpty(LinkList L)
    {
       if(L->netx)
           return 0;
        else
            return 1;
    }
    

 

4.销毁单链表

思路:从头指针开始,依次释放所有结点

Status DestroyList_L(LinkList L)
{
    LNode *p; //或者 LinkList p;
    while(L)
    {
        p=L;
        L=L->next;
        free p;
    }
}

 

5.清空单链表

思路:依次释放所有结点,并为头结点指针域设置为空

Status ClearList(LinkList L)
{
    LNode *p,*q;
    p=L->next;
    while(p)
    {
        q = p->next;
        free p;
        p = q;
    }
    L->next = NULL; //头结点指针域为空
    return OK;
}

 

6.求单链表长度

思路:从首元结点开始,依次计数所有结点

Status ListLength_L(LinkList L)
{
    LNode *p;
    p = L->next; //p指向第一个结点
    int i = 0;
    while(p)  //遍历单链表,统计结点数
    {
        i++;
        p = p->next;
    }
    return i;
}

 

7.取值

Status GetElem_L(LinkList L, int i, ElemType e)
{
    LinkList p = L->next; 
    int j = 1;  //p指向第一个结点,j做计数器,累计当前扫描过的结点数
    while(p && j<i)  //向后扫描,p指向第i个元素或者p为空
    {
        p = p->next;
        j++;
    }
    if (!p || j>i)   //第i个元素不存在
        return ERROR;
    e = p->data;    //取第i个元素
    return Ok;
}

 

8.按值查找

Status LocatElem_L(LinkList L,Elemtype e)
{
    LinkList p = L->next;
    int j = 1;
    while(p && p->data != e)
    {
        p = p->next;  //遍历
        j++;          //位置序号
    }
    if(p)
        return i;
    else 
        return 0;
}

 

9.插入值

思路:

  1. 想要在链表第 i 个元素前面插入新结点,则需要将指针指向第 i-1 个元素,从而将其 next 域中保存的第 i 个元素地址赋值给新结点,实现链接
LinkList p = L;
int j = 0;
while(p && j<i-1)
  1. 代码中创建了指向头结点的指针变量,初始化起点并非首元结点,所以要想在第 i 个位置插入,while 循环次数需为 i-1

    若初始化为首元结点,即

    LinkList p = L->next;
    

    则 while 循环次数为 i-2,从而根据循环次数要求去初始化 j 或改变循环结束的条件

     

Status ListInsert_L(LinkList L, int i, Elemtype e)
{
    LinkList p = L;
    int j = 0;
    while(p && j<i-1)
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i-1)
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return Ok;
}

 

10. 删除第 i 个结点

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

 

单链表的创建

1. 头插法(前插法)

思路:

  1. 从一个空表L开始,重复读入数据;
  2. 生成新结点,将读入数据存放到新结点的数据域中
  3. 从最后一个结点开始,依次将各结点插入到链表的前端
void CreatList_H(LinkList L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;  //建立一个带头结点的单链表
    for(i=n; i>0; --i)
    {
       p = (LinkList)malloc(sizeof(LNode));  //生成新结点p
        scanf(&p->data);                    //获取输入值
        p->next = L->next;                //插入到表头
        L->next = p;
    }
}

 

2. 尾插法(后插法)

思路:

  1. 从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针 r 指向链表的尾结点
  2. 初始时,r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点后,r 指向新结点
void CreatList(LinkList L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r;
    r = L;   //尾指针 r 指向头结点
    for(i=0; i<n; i++)
    {
        p = (LinkList)malloc(sizeof(LNode));   //生成新结点,输入元素值
        scanf(&p->data);
        p->next = NULL;
        r->next = p;    //插入到表尾
        r = p;          //r 指向新的尾结点
    }
}

 

循环链表

1.创建

//先创建初始化结点函数
LinkList initlist()
{
    LNode *head = (LinkList)malloc(sizeof(LNode));
    if(head == NULL)
    {
        printf("创建失败,退出程序");
    }
    else
    {
        head->next = NULL;
        return head;
    }
}

//创建循环链表
Status Insert_List(LNode *head)
{
    int data;
    printf("输入插入的元素:");
    scanf("%d",&data);
    
    LinkList node = initlist();
    node->data = data;   //初始化新结点
    
    if(head != NULL)
    {
        LNode *p = head;
        while(p->next != head)  //找到最后一个元素
        {
            p = p->next;
        }
        p->next = node;
        node->next = head;
        return 1;
    }
    else
    {
        printf("头结点已无元素\n");
        return 0;
    }
}

 

2. 带尾指针循环链表合并

LinkList Connect(LinkList Ta, LinkList Tb)
{  //假设Ta,Tb都是非空的单循环链表 
    p = Ta->netx;       //p 存表头结点
    Ta->next = Tb->next->next;  //Tb 表头连接 Ta 表尾
    free Tb->next;         //释放 Tb 表头结点
    Tb->next = p;          //修改指针
    return Yb;
}//时间复杂度O(1)

 

双向链表

1. 创建

//结点创建
typedef struct DuLNode
{
    Elemtype data;           //data
    struct DuLNode *pre;   //前驱 node
    struct DuLNode *next;  //后继 node
}DuLNode,*DuLinkList;

//插入数据
Status ListInsert_DuL(DuLinkList L, int i, ElemType e)
{
    //在带头结点的双链循环线性表L中第i个位置之前插入元素e
    //i的合法值为 1<=i<=表长+1
    if(!(p = GetElemP_DuL(L,i)))  //在L中确定插入的位置
        return ERROR;         //p=NULL,即插入位置不合法
    if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))
        return ERROR;
    s->data = e;
    s->prior = p->prior;    p->prior->next = s;
    s->next = p;            p->prior = s;
    return OK;
}//LinkInsert_DuL

2.删除

Status ListDelete_DuL(DuLinkList L, int i, ElemType e)
{
    //删除带头结点的双链循环线性表L的第i个元素,i的合法值为1<=i<=表长
    if(!(p = GetElemP_DuL(L,i)))   //在L中确定第i个元素的位置指针p
        return ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}ListDelete_DuL

 

觉得有帮助可以投喂下博主哦~感谢!
作者:Echo
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0协议
转载请注明文章地址及作者哦~

评论

  1. Avatar photo
    博主
    已编辑
    10 月前
    2023-8-09 21:56:44

    学习linux系统编程时用到了链表,深感C语言指针和数据结构的重要性,
    一定要认真学!!!

    来自江苏

发送评论(请正确填写邮箱地址,否则将会当成垃圾评论处理) 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇