C语言数据结构[线性表]

一、顺序表

优点：查询操作比较快
缺点：数据存放必须是连续的；添加删除操作移动次数过多

A:动态分配 1.1 初始化

// 结构体存放初始数据
typedef struct student
{
    int* p;
    int len;
} STUDENT;

// 全局变量表创建时使用
int max_size=10;

// 初始化创建，用一个结构体存放动态创建内容的首地址
void arr_init(STUDENT* p){
    p->p = (int*)malloc(sizeof(int)*max_size);
    p->len=0;// 表写入数据的长度
}

1.2 插入

void arr_insert(STUDENT *p,int positon,int data){
    int i;
    if(positon>max_size){
        printf("超出允许的范围");
    }
    for(i=p->len;i>positon-1;i--){
        *(p->p+i)=*(p->p+i-1);
    }// 0 1 2
    *(p->p+i)=data;
    p->len++;
}

1.3 删除

void arr_remove(STUDENT* p,int positon){
    int i;
    if(positon>max_size){
        printf("超出允许的范围");
        return;
    }// 1 2 3
    for(i=positon-1;ilen-1;i++){
        *(p->p+i)=*(p->p+i+1);
    }
    p->len--;
}

1.4 释放

free(stu.p);

1.5 打印

void arr_printf(STUDENT p){
    int i;
    for(i=0;i
        printf("%dn",*(p.p+i));
    }
}

1.6 示例程序

void main(){
    STUDENT stu;
    arr_init(&stu);
    arr_insert(&stu,1,151);
    arr_insert(&stu,2,15);
    arr_insert(&stu,3,1);
    arr_insert(&stu,4,15111);
    arr_remove(&stu,4);
    arr_printf(stu);
    free(stu.p);
}

B:静态分配

解释：单纯的把结构体中的指针换为数组

区别：分配位置大小固定

二.单链表 A:单链表

优点：相比于顺序表，添加删除操作比较快，比较方便
缺点：相比于顺序表，查询比较慢；只能单向按顺序访问

2.1 有头节点

注意：用有头节点写程序会很方便，本程序的头结构体与数据结构体不一致，造成程序更杂乱，普通使用头结构体与数据结构体相同即可
图解：

2.1.1 初始化

typedef struct student
{
    int data;
    int next;
} NODE;
// 初始化
NODE* list_init()
{
    NODE* p =(NODE*)malloc(sizeof(NODE));
    p->data=0;
    p->next=NULL;
    return p;
}

2.1.2 插入

// 按位置插入
void list_insert(NODE* head,int data,int position)
{
    int i;
    NODE* node = (NODE*)malloc(sizeof(NODE));// head 1 2 3
    for(i=1;i
        head=head->next;
    }
    if(head){
        node->data=data;
        node->next=head->next;
        head->next=node;
    }

}

2.1.3 删除

// 删除指定位置的内容
void list_remove(NODE* head,int position)
{
    int i;
    for(i=1;i
        head=head->next;
    }
    NODE* temporary=head->next;
    head->next=temporary->next;
    free(temporary);
}

2.1.4 打印

// 打印内容
void list_printf(NODE* p)
{
    p=p->next;
    while(p){
        printf("%dn",p->data);
        p=p->next;
    }
}

2.1.5 主程序

void main()
{
    NODE*p = list_init();
    list_insert(p,5,1);
    list_insert(p,69,2);
    list_insert(p,6555,3);
    list_remove(p,2);
    list_printf(p);

    return 0;
}

2.2 无头节点

注意：无头节点，在涉及到第一位元素的操作时会变得很麻烦，代码同时更杂乱

// 初始化
typedef struct student
{
  	int a;
    int b;
    struct student* next;
} NODE;

NODE* list_init(int a,int b)
{
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=a;
    node->b=b;
    node->next=NULL;
    return node;
}
// 插入
NODE* list_insert(NODE* p,int a,int b,int position)// 带返回值主要是为了头插法，改变p的指向
{
    int i;
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=a;
    node->b=b;
    NODE* pos=p;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    if(position==1)
    {
        node->next=p;
        p=node;// 此时不用返回值，p在main里面并不会和此一样
        return p;
    }
    else
    {
        for(i=1; i
            pos=pos->next;
        }
        node->next=pos->next;
        pos->next=node;
        return p;
    }
}
// 删除
void list_remove(NODE* p,int position)
{
    int i;
    NODE* pos=p;
    NODE* pos_one;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    if(position==1) //不能直接简单交换指针，可以换数据
    {
        pos_one=p->next; // 准备删除第二个，此作为中介
        p->a=p->next->a;
        p->b=p->next->b;
        p->next=p->next->next;
        free(pos_one);
    }
    else
    {
        for(i=1; i
            pos=pos->next;// 即将删除位置前的一个
        }
        pos_one=pos->next;//post_one指针是要删除的内容
        pos->next=pos_one->next;// 把删除位置前的一个的指针，指向被删除指针指向的地址
        free(pos_one);
    }
}
// 释放
void list_del(NODE* p)
{
    NODE* node_one;
    NODE* node_two=p;
    while(node_two)
    {
        node_one=node_two;
        node_two=node_one->next;
        free(node_one);
    }
}
// 打印
void list_printf(NODE* p)
{
    NODE* pos=p;
    while(pos)
    {
        printf("%d %dn",pos->a,pos->b);
        pos=pos->next;
    }
}
void main()
{
    int a=1200,b=1500;
    NODE* p = list_init(a,b);
    p=list_insert(p,1,2,2);
    p=list_insert(p,1115,212112,1);
    p=list_insert(p,15,212,1);
    list_remove(p,1);
    list_printf(p);
    list_del(p);
}

B:单循环链表

区别：可以从任意位置按照顺序去查询数据

代码细节：①初始化放置的头节点放置不是NULL而是指向自己②循环结束条件改为pos!=p

// 单循环链表
#include 
#include 
typedef struct student
{
    int a;
    int b;
    struct student* next;
} NODE;
// 带头指针的初始化
NODE* list_init()
{
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=0;
    node->b=0;
    node->next=node;
    return node;
}
// 按位置插入
void list_insert(NODE* p,int a,int b,int position)
{
    int i;
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=a;
    node->b=b;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    for(i=1; i
        p=p->next;
    }
    node->next=p->next;
    p->next=node;
}
// 打印内容
void list_printf(NODE* p)
{
    NODE* pos=p->next;
    while(pos!=p)
    {
        printf("%d %dn",pos->a,pos->b);
        pos=pos->next;
    }
}
// 清空
void list_del(NODE* p)
{
    NODE* node_one;
    NODE* node_two=p->next;
    while(node_two!=p)
    {
        node_one=node_two;
        node_two=node_one->next;
        free(node_one);
    }
}
// 删除指定位置的内容
void list_remove(NODE* p,int position)
{
    int i;
    NODE* pos_one;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    for(i=1; i
        p=p->next;// 即将删除位置前的一个
    }
    pos_one=p->next;//post_one指针是要删除的内容
    p->next=pos_one->next;// 把删除位置前的一个的指针，指向被删除指针指向的地址
    free(pos_one);
//    }
}
void main()
{
    NODE* p = list_init();
    list_insert(p,1,2,1);
    list_insert(p,1115,212112,2);
    list_insert(p,1115,2121,3);
    list_remove(p,1);
    list_printf(p);
    list_del(p);
}

三.双链表 A:双链表

优点：增加删除还是比顺序表方便，查询效率有提高，双向按顺序访问
缺点：使用的内存空间增大

代码细节：如果把移动指针指向目标上（而不是它前一个节点），注意null的处理

// 双链表
#include 
#include 
typedef struct student
{
    int a;
    int b;
    struct student* pre;
    struct student* next;
} NODE;
// 带头指针的初始化
NODE* list_init()
{
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=0;
    node->b=0;
    node->pre=NULL;
    node->next=NULL;
    return node;
}
// 按位置插入
void list_insert(NODE* p,int a,int b,int position)
{
    int i;
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=a;
    node->b=b;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    for(i=1; i
        p=p->next;
    }
    node->next=p->next;
    node->pre=p;
    p->next=node;
}
// 打印内容
void list_printf(NODE* p)
{
    NODE* pos=p->next;
    while(pos)
    {
        printf("%d %dn",pos->a,pos->b);
        pos=pos->next;
    }
}
// 清空
void list_del(NODE* p)
{
    NODE* node=p->next;
    NODE* node_tem;
    while(node)// 1 2 3
    {
        node_tem=node;
        node=node->next;
        free(node_tem);
    }
    free(p);
}
// 删除指定位置的内容
void list_remove(NODE* p,int position)
{
    int i;
    NODE* pos_one=p->next;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    for(i=1; i
        pos_one=pos_one->next;// 即将删除位置前的一个
    }
    pos_one->pre->next=pos_one->next; //这里引用的要删除的当前元素
    if(pos_one->next){ // 此种定位到要变动元素的方法，要防止末尾出现null的情况
        pos_one->next->pre=pos_one->pre;
    }
    free(pos_one);
}
void main()
{
    NODE* p = list_init();
    list_insert(p,1,2,1);
    list_insert(p,1115,212112,2);
    list_insert(p,1115,2121,3);
//    list_remove(p,3);
    list_printf(p);
    list_del(p);
}

B:双链表循环

代码细节：无需再注意NULL；注意循环条件的改变；尾插法时头节点的pre变化；插入其它位置时pre的变化；初始化时pre和next都指向头节点

// 双循环链表
#include 
#include 
typedef struct student
{
    int a;
    int b;
    struct student* pre;
    struct student* next;
} NODE;
// 带头指针的初始化
NODE* list_init()
{
    NODE* node=(NODE*)malloc(sizeof(NODE));
    node->a=0;
    node->b=0;
    node->pre=node;
    node->next=node;
    return node;
}
// 按位置插入
void list_insert(NODE* p,int a,int b,int position)
{
    int i;
    NODE* node=(NODE*)malloc(sizeof(NODE));
    NODE* p2=p;
    node->a=a;
    node->b=b;// 1 2 ox12  ,  5 5 ox19, 66 6 ox35  ,  99 9 ox356
    for(i=1; i
        p=p->next;
    }
    node->next=p->next;
    node->pre=p;
    p->next=node;
    if(node->next==p2){// 应对尾插法，头节点pre的处理
        p2->pre=node;
    }
    if(node->next->pre!=node){// 判断非尾插法插入
        node->next->pre=node;
    }


}
// 打印内容
void list_printf(NODE* p)
{
    NODE* pos=p->next;
    while(pos!=p)
    {
        printf("%d %dn",pos->a,pos->b);
        pos=pos->next;
    }
}
// 清空
void list_del(NODE* p)
{
    NODE* node=p->next;
    NODE* node_tem;
    while(node!=p)// 1 2 3
    {
        node_tem=node;
        node=node->next;
        free(node_tem);
    }
    free(p);
}
// 删除指定位置的内容
void list_remove(NODE* p,int position)
{
    int i;
    NODE* pos_one=p->next;// 1 2 ox12  ,5 5 ox19  ,66 6 ox35
    for(i=1; i
        pos_one=pos_one->next;// 即将删除位置前的一个
    }
    pos_one->pre->next=pos_one->next; //这里引用的要删除的当前元素
    pos_one->next->pre=pos_one->pre;
    free(pos_one);
}
void main()
{
    NODE* p = list_init();
    list_insert(p,1,2,1);
    list_insert(p,1115,212112,1);
    list_insert(p,1115,2121,1);
    list_remove(p,3);
    list_printf(p);
    list_del(p);
    return 0;
}

四.静态链表

优点：移动数据时只需要移动游标即可
缺点：表长固定不能变

思路：两条链路；一条是已分配路线，一条是未分配路线；其中第一位置和最后一个位置是不填充数据，第一个位置表示未分配线路起始下标，最后一个位置表示已分配路线的起始下标

1.初始化

// 初始化
NODE* list_init(NODE* p)// 初始时都是属于未分配这条链表
{
    int i=0;
    for(i=0;i
        (p+i)->next=i+1;
        (p+i)->data=0;
    }
    (p+MAX-1)->next=0;// 表示开始着开头元素的下标
    (p+MAX-2)->next=0;// 表示结束
}

2.插入

图解：假设已经填充了三条数据，现在已分配链是1->2，未分配链是3->4

图解：在第二位插入data，现在已分配链是1->3->2，未分配链是4->

// 按位置插入
void list_insert(NODE* head,int data,int position)// 开始增加数据形成已分配表
{


    // 初期建立的未分配表，下标0的next一直指向未分配数据
    int last = MAX-1;
    int newplace = head->next;//4
    int i;
    if(head->next) // 防止到最后一个数据为空的情况
    {
        head->next=(head+newplace)->next;
    }
    // 上面的代码是找到新空闲可分配位置
    if(newplace)
    {
        (head+newplace)->data=data;
        for(i=1; i
            last=(head+last)->next;
        }
        (head+newplace)->next=(head+last)->next;
        (head+last)->next=newplace;
    }

}

3.删除

思路：找到被删除内容的前一个节点，想办法让其和被删除节点的下一个节点接起来；然后想办法让被删除节点连入未分配链路

// 删除指定位置的内容
void list_remove(NODE* head,int position)
{
    int i;
    int last = MAX-1;
    int old;
    for(i=1; i
        last=(head+last)->next;
    }
    old=(head+last)->next;
    (head+last)->next=(head+old)->next;
    // 上面的代码成功断开联系，下面的代码负责刚刚释放的接入到未分配链表中去
    (head+old)->data=0;
    (head+old)->next=head->next;
    head->next=old;
}

4.打印

// 打印内容
void list_printf(NODE* p)
{
    int i;
    NODE* p1=p;
    int firstplace = (p+MAX-1)->next;
    p = p+firstplace;
    do
    {
        printf("%dn",p->data);
        i = p->next;
        p=p1;// 让p回到起始位置
        p=p+i;
    }
    while(p->next);
    printf("%d",p->data);// 最后一位专门打印
// 下面注释的是检测数组的代码
//for(i=0;i
//    printf("%d-%dn",p->data,p->next);
//    p++;
//}
}

5.主程序

void main()
{
    NODE p[MAX];
    list_init(p);
    list_insert(p,5,1);
    list_insert(p,69,1);
    list_insert(p,6555,1);
    list_remove(p,3);
    list_printf(p);

    return 0;
}

C语言数据结构[线性表]

C/C++/C#相关栏目本月热门文章