帮你理解一下线性表

作者: 小北写码 | 来源:发表于2019-04-11 22:17 被阅读0次

帮你理解一下线性表
线性表的链式存储结构Java实现
数据结构-线性表（顺序表和链表）
线性表
算法与数据结构（三）数组与链表
栈和队列
什么是线性表
2016-12-31-定义线性表的接口
基本数据结构 - 链表
数据结构-栈

定义

线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表中除了头尾元素，每个元素都只有一个直接前驱和一个直接后继，而首元素没有直接前驱，尾元素没有直接后继。我们把线性表想象成一个火车，所谓前驱就是火车车厢的前一个车厢，后继就是火车车厢的后一个车厢。
线性表通常有两种存储结构，分别为顺序存储和链式存储，下面我们就来聊聊这两种存储方式的差异。

两种存储结构的差异

顺序存储结构就是在存储的时候系统会分配给你一段连续的内存空间，以供数据的存储，c语言中常见的数组就是这种存储方式。
而链式存储结构就是存储的时候所有数据并不是连续存储的，每个数据节点通过地址的指向进行连接。常见的数据结构有单链表，循环链表，双向链表。
了解了基本概念之后，我们可以对照下图进行理解。

线性表存储结构.png

顺序存储结构基本操作

插入：首先将插入位置的节点向后移一位，空出要插入的位置，将相应的节点插入。
删除：找到要删除的元素，然后用后面的节点的值覆盖前面的节点的值（也就是说后面的节点全部向前移一位）。
修改：从前向后遍历，找到要修改的节点，将相应的值赋给该节点。
查找：从前向后遍历，找到要查询的节点的值，返回该节点的位置即可。
以下是示例代码，如果不合适的地方，还望指教，谢谢。

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


//*******************************************************************************************************************
//顺序结构线性表

struct sequence_node {     //定义一个结构体 
    int *data;
    int length;
    int maxlength;
};
typedef struct sequence_node SList;

void InitSList(SList *slist, int len){
    if(len > 0){
        slist->maxlength = len;
        slist->length = 0;
        slist->data = (int *)malloc(sizeof(int) * len);
    }
}

void InsertSList(SList *slist, int pos, int val){     //在某位置插入一个元素    
    if(pos < 0 || pos > slist->length || slist->length == slist->maxlength){
        printf("插入失败！\n");
        return;
    }
    for(int i = slist->length; i > pos-1; i--)  
        slist->data[i+1] = slist->data[i];
    slist->data[pos] = val;
    slist->length++;
    printf("插入成功！\n"); 
}

void DeleteSList(SList *slist, int val){          //删除一个元素 
    for(int i = 0; i < slist->length; i++){
        if(slist->data[i] == val){
            for(int j = i; j < slist->length; j++)
                slist->data[j] = slist->data[j+1];
            slist->length--;
            printf("删除成功！\n"); 
            return;
        }
    }
    printf("删除失败！\n");
}

void ModifySList(SList *slist, int pos, int val){       //将某位置的节点值修改为指定值 
    if(pos < 0 || pos > slist->length){
        printf("修改失败！\n"); 
        return;
    }
    slist->data[pos] = val;
    printf("修改成功！\n");
} 

int FindSList(SList *slist, int val) {                  //查找某元素的位置 
    for(int i = 0; i < slist->length; i++){
        if(slist->data[i] == val){
            return i;
        } 
    }
    return -1;
} 

void PrintSList(SList *slist){       //打印所有的节点值     
    for(int i = 0; i < slist->length; i++)
        printf("%d",slist->data[i]);
    printf("\n");
}


int main(){
    SList *slist = (SList *)malloc(sizeof(SList));
    InitSList(slist,5);
    InsertSList(slist,0,1);
    PrintSList(slist);
    InsertSList(slist,0,4);
    PrintSList(slist);
    InsertSList(slist,0,8);
    PrintSList(slist);
    ModifySList(slist,1,2);
    PrintSList(slist);
    DeleteSList(slist,8);
    PrintSList(slist);
    int pos = FindSList(slist,1);
    printf("%d\n",pos);
    return 0;
}

链式存储结构基本操作

插入：先将前一个节点指向下一个节点的指针保存下来，然后将前一个节点指向要插入的节点，再将要插入的节点指向下一个节点。如图：

链表插入.png
删除：查找到要删除的节点，然后将该节点的上一个节点指向该节点的下一个节点，但是要避免内存泄漏，将删除的节点保存并清除内存。如图：

链表删除.PNG
修改：从前向后遍历，找到要修改的节点，将相应的值赋给该节点。
查找：从前向后遍历，找到要查询的节点的值，返回该节点的位置，如果查找不到就返回-1。
以下是示例代码，如果不合适的地方，还望指教，谢谢。

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



//*******************************************************************************************************************
//链式结构线性表 
struct chain_list{
    int data;
    struct chain_list *next;
};
typedef struct chain_list CList;

void InsertCList(CList **head, int val){       //插入一个节点 
    CList *clist = (CList *)malloc(sizeof(CList));
    clist->data = val;
    clist->next = *head;
    *head = clist;
}

void DeleteCList(CList *head, int val){        //删除一个节点 
    CList *curr;
    curr = head;
    while(curr->next != NULL){
        if(curr->next->data == val){
            CList *tmp;
            tmp = curr->next;
            curr->next = curr->next->next;
            free(tmp);
            printf("删除成功！\n");
            return;
        }
        curr = curr->next;
    }
    printf("删除失败！\n");
}

void ModifyCList(CList *head, int pre, int mod){       //修改某节点的值 
    CList *curr;
    curr = head;
    while(curr->next != NULL){
        if(curr->next->data == pre){
            curr->next->data = mod;
            printf("修改成功！\n");
            return;
        }
        curr = curr->next;
    }
    printf("修改失败！\n");
} 

int FindCList(CList *head, int val){       //查找某个节点的位置 
    CList *curr;
    curr = head;
    int i = 0;
    while(curr->next != NULL){
        if(curr->next->data == val) {
            return i;
        }
        i++;
        curr = curr->next;
    }
    return -1;
}

void PrintCList(CList *head){      //打印链表 
    CList *curr = head->next;
    while(curr != NULL){
        printf("%d,",curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main(){
    
    CList *head = NULL;
    for(int i = 0; i < 5; i++){
        InsertCList(&head, i);
    }
    PrintCList(head);
    DeleteCList(head, 2);
    PrintCList(head);
    ModifyCList(head, 1, 8);
    PrintCList(head);
    int pos = FindCList(head, 0);
    printf("查找元素的位置:%d\n", pos); 
    return 0;
}