数据结构和算法(二)线性表(顺序存储)

正文

线性表：他是一种基本的数据结构类型，具有相同特性的n个数据的集合。
线性表的常用存储结构有两种:顺序结构存储 和 链表结构存储。

书接上文，本文实现线性表的顺序存储逻辑。全文实行使用C语言进行。

image.png

1.顺序表的定义

#include <stdio.h>
#include "stdlib.h"
#define KSequentialListLength 5

//顺序表的数据结构
typedef struct SeqList{
    int *seqListAddr;  //顺序表首地址
    int listLength;    //顺序表长度
}mySeqList;

2.顺序表初始化

// 顺序存储结构初始化 (默认存储的是int类型数据，所以申请内存时以int长度为基础)
int InitSeqList(mySeqList *seqList){
    seqList-> seqListAddr = malloc(sizeof(int)* KSequentialListLength);
    //判断是否初始化成功
   if(seqList-> seqListAddr == NULL) renturn 0; //初始化失败
   //初始长度设为0
   seqList-> listLength = 0;
   return 1;
}

3.顺序表遍历

void ShowSeqList(mySeqList seqList){
    //判空
   if(seqList-> listLength ==0){
      pintf("顺序表为空\n");
      return;
    }
  //遍历
   for (int i=0;i<seqList.listLength;i++){
    pintf("%d ",seqList.seqListAddr[i]);    
    }
  pintf("\n");
}    

4.顺序表的插入

image.png

int InsertValueToSeqList(mySeqList *seqList,int insertValue,int insertPlace){
  if (insertPlace<1) {
        printf("插入位置非法\n");
        return 0;
    }
    
    if (seqList-> listLength >= KSequentialListLength) {
        printf("当前顺序表已满\n");
        return 0;
    }

    if (insertPlace > seqList-> listLength ) { //插入位置大于长度，默认加到最后
        seqList-> seqListAddr[seqList->linkLength] = insertValue;
        seqList-> listLength ++;
    }else{ //逆序 把后面的值接个后移 直到插入的位置的索引
        for(int i = seqList->linkLength;i>=insertPlace;i--){
            seqList-> seqListAddr[i] = seqList-> seqListAddr[i-1];
         }
        seqList[insertPlace-1] = insertValue;
        seqList-> listLength ++;
    }
}

5.顺序表的删除

image.png

/// 删除顺序表的某一个值
int DeletElementOnSeqList(mySeqList * seqList,int deleteplace){
    if (deleteplace < 1 || deleteplace > seqList-> listLength) {
        printf("删除位置不存在\n");
        return 0;
    }
    
    //从需要删除的位置 把后面的值一次前移覆盖
    for (int i = deleteplace; i <= seqList->linkLength; i++) {
        seqList-> seqListAddr[i-1] = seqList-> seqListAddr[i];
    }
    seqList-> listLength--;
    return 0;
}

6.顺序表查找元素

/// 查找
int searchElement(mySeqList * seqList,int index,int *resValue){
    if (index < 1 || index > seqList-> listLength) {
        printf("查找位置不存在\n");
        return 0;
    }
    
    *resValue = seqList-> seqListAddr[index-1];
    return 1;
}

7.顺序表修改

/// 改
int modifyElement(mySeqList * seqList,int modifyPlace,int value){
    if (modifyPlace < 1 || modifyPlace > seqList-> listLength) {
        printf("修改位置不存在\n");
        return 0;
    }
    
    seqList-> seqListAddr[modifyPlace-1] = value;
    return 1;
}

总结:

以上是顺序表的基本操作和代码实现。具体其他方法可以根据自己的需要进行实现。顺序表的实现逻辑就是类比数组的实现。申请一个连续大小的内存空间进行操作。