数据结构顺序表与链表 6.16-EW帮帮网

前言

今天来到顺序表与链表。

顺序表与链表通过结构体实现。这里主要讲顺序表与链表的基本操作，以及链表功能的实现。

概述

1.数据结构：顺序表

2.数据结构：链表

3.链表相关功能函数。

1.顺序表

定义：

typedef struct seq_list

{

        int arr[max];

        int len;

}seq_list,*seq_p;

增：

细节见链表内容下方手写笔记

for(int i=S->len-1;i>=pos;--i)
{
    S->arr[i+1] = S->arr[i];
}
S->arr[pos] = data;
S->len++;            //先增后移

删：

S->len--;            //len--后打印不出，即已删除

2.链表

定义：

typedef struct node
{
    union
    {
        int data;
        int len;
    };
    struct node* next;
}node, *node_p;

增：

new->next = H->next;
H->next = new;            //先尾后首

删：

node_p p_delete = H->next;
H->next = p_delete->next;
free(p_delete);

手写笔记：

3.链表相关功能函数

代码如下：

1.makefile

EXE=01_seq_list
Objs=$(patsubst %.c,%.o,$(wildcard *.c))
CC=gcc
CFlags=-c -o

all:$(EXE)
$(EXE):$(Objs)
	$(CC) $^ -o $@
%.o:%.c
	$(CC) $^ $(CFlags) $@

#伪目标
.PHONY:clean
clean:
	rm $(EXE) $(Objs)

2.head.h

#ifndef _HEAD_H_
#define _HEAD_H_

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{
    union
    {
        int data;
        int len;
    };
    struct node* next;
}node,*node_p;

//
void printlist(node_p H);//0
node_p creat_head_node();//1
node_p creat_node(int value);//2
int empty_link(node_p H);//3
void insert_head(node_p H,int value);//4
void insert_tail(node_p H,int value);//5
void show_link(node_p H);//6
void delete_head(node_p H);//7
void delete_tail(node_p H);//8
void insert_pos(node_p H,int pos,int value);//9
void delete_pos(node_p H,int pos);//10
int seek_pose(node_p H,int pos);//11
void change_val(node_p H, int value, int new);//12
void reversed(node_p H);//13

#endif

3.fun.c

#include "head.h"
//0
void printlist(node_p H)
{
    node_p p = H;
    if(p != NULL)
    {
        /*
        do 
        {
            printf("%d ", p->data);
            p = p->next;
        } while (p != NULL);
        */
        
        while(p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        
        printf("\n");
    }
}
//1、申请头结点
node_p creat_head_node()
{
    node_p H=(node_p)malloc(sizeof(node));
    H->next=NULL;
    H->len=0;
    return H;
}
//2、申请数据结点
node_p creat_node(int value)
{
    node_p new_node=(node_p)malloc(sizeof(node));
    if(new_node==NULL)
    {
        printf("申请空间失败。\n");
        return NULL;
    }
    new_node->data=value;
    new_node->next=NULL;
    return new_node;
}
//3、判空
int empty_link(node_p H)
{
    if(H==NULL)return -1;
    return H->next==NULL?1:0;
}
//4、头插
void insert_head(node_p H,int value)
{
    if(H==NULL)
    {
        printf("入参为空。\n");
        return;
    }
    else
    {
        //申请空间
        node_p new = creat_node(value);

        //链接：从后往前
        new->next = H->next;
        H->next = new;

        //链表长度发生改变
        ++H->len;
    }
}
//5、尾插
void insert_tail(node_p H,int value)
{
    if(H==NULL)
    {
        printf("入参为空。\n");
        return;
    }
    //else
    //接收指针
    node_p p=H;
    //找到尾节点
    while(p->next != NULL)
    {
        p = p->next;
    }

    //申请空间
    node_p new = creat_node(value);

    //链接：从后往前
    p->next = new;

    //链表长度发生改变
    ++H->len;
}
//6、输出列表
void show_link(node_p H)
{
    if(H==NULL)return;
    if(empty_link(H)){printf("空链表\n");return;}
    node_p p = H;
    p = p->next;
    if(p != NULL)
    {
        while(p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        
        printf("\n");
    }
}
//7、头删
void delete_head(node_p H)
{
    if(H==NULL)return;
    if(empty_link(H)){printf("空链表\n");return;}

    node_p p_delete = H->next;
    H->next = p_delete->next;

    free(p_delete);
    --H->len;
}
//8、尾删
void delete_tail(node_p H)
{
    if(H==NULL)return;
    if(empty_link(H)){printf("空链表\n");return;}

    node_p p = H;
    while(p->next->next != NULL)p = p->next;
    
    node_p p_delete = p->next;
    p->next = NULL;

    free(p_delete);
    --H->len;
}
//9、按位置插入
void insert_pos(node_p H,int pos,int value)
{
    if(H==NULL)return;

    //申请空间
    node_p new = creat_node(value);
    node_p p_pos = H;
    for(int i = 0; i<pos; ++i)
    {
        p_pos = p_pos->next;
        if(p_pos==NULL)
        {
            printf("输入有误。");
        }
    }

    //链接：从后往前
    new->next = p_pos->next;
    p_pos->next = new;

    //链表长度发生改变
    ++H->len;
}
//10、按位置删除
void delete_pos(node_p H,int pos)
{
    if(H==NULL)return;
    node_p p_pos = H;
    for(int i = 0; i<pos; ++i)
    {
        p_pos = p_pos -> next;
    }

    if(p_pos->next==NULL)
    {
        printf("位置不合理");
        return;
    }
    
    node_p p_delete = p_pos->next;
    p_pos->next = p_pos->next->next;

    free(p_delete);
    --H->len;
}
//11、按位置查找
int seek_pose(node_p H,int pos)
{
    if(H==NULL)return -1;
    if(empty_link(H)){printf("空链表\n");return -2;}
    H = H->next;    //跳过链表表头的计数结构体
    for(int i = 0; i<pos; ++i)
    {
        H = H->next;
    }
    return H->data;
}
//12、按值修改
void change_val(node_p H, int value, int new)
{
    if(H==NULL)return;
    if(empty_link(H)){printf("空链表\n");return;}
    for(int i = 0; i <= H->len-1; ++i)
    {
        H = H->next;
        if(H->data == value)
        {
            H->data = new;
            return;
        }
    }
}
//13、逆置
void reversed(node_p H)
{
    if(H==NULL)return;
    if(empty_link(H)){printf("空链表\n");return;}
    
    node_p prev = NULL;//防丢失用
    node_p p = H->next;  
    node_p next = NULL;//防丢失用
    
    while(p != NULL) 
    {
        //将下一个元素地址提取出来，存在next里
        next = p->next;

        //对该元素操作，把p存入p->next  
        p->next = prev;  
        prev = p; 
        
        //把p->next存入p
        p = next;        
    }
    
    //最后将最后一个元素的地址给链表表头
    H->next = prev;  
}

4.main.c

#include "head.h"

int main(int argc, const char *argv[])
{
    node_p H = creat_head_node();
    printf("判空?：");
    //printf("%d\n",empty_link(H));
    show_link(H);

    //头插9
    insert_head(H,9);
    printf("头插9：");
    show_link(H);

    //头插8
    insert_head(H,8);
    printf("头插8：");
    show_link(H);

    //尾插1
    insert_tail(H,1);
    printf("尾插1：");
    show_link(H);

    //尾插2
    insert_tail(H,2);
    printf("尾插2：");
    show_link(H);

    //头删
    delete_head(H);
    printf("头删 ：");
    show_link(H);

    //尾删
    delete_tail(H);
    printf("尾删 ：");
    show_link(H);

    //尾插2
    insert_tail(H,2);
    printf("尾插2：");
    show_link(H);

    //头插8
    insert_head(H,8);
    printf("头插8：");
    show_link(H);

    //位插入
    insert_pos(H,2,5);
    printf("插入5：");
    show_link(H);

    //位删除
    delete_pos(H,2);
    printf("位删 ：");
    show_link(H);

    //查找
    int num=seek_pose(H,1);
    printf("查找 ：");
    printf("%d\n",num);

    //按值修改
    change_val(H,9,5);
    printf("修改 ：");
    show_link(H);

    reversed(H);
    printf("逆置 ：");
    show_link(H);

    return 0;
}

结语

顺序表由于操作相对简单，就没有贴代码进行演示。

链表的操作难点在于需要通过指针进行访问，通过p->next进行自增，但其实底层逻辑与数组十分相似。最后的链表逆置逻辑上与数组不同，用的是一个头插的逻辑，但如果指针熟练，也可以通过与数组逆置一致的方式实现。

数据结构顺序表与链表 6.16

前言

概述

1.顺序表

定义：

增：

删：

2.链表

定义：

增：

删：

手写笔记：

3.链表相关功能函数

1.makefile

2.head.h

3.fun.c

4.main.c

结语

网站公告

今日签到

热门文章

最新发布

数据结构 顺序表与链表 6.16

前言

概述

1.顺序表

定义：

增：

删：

2.链表

定义：

增：

删：

手写笔记：

3.链表相关功能函数

1.makefile

2.head.h

3.fun.c

4.main.c

结语

网站公告

今日签到

热门文章

最新发布

数据结构顺序表与链表 6.16