数据结构-----顺序表

数据结构----顺序表

• 有关线性表
  研究数据结构时，要从他的三要素下手：逻辑结构、存储结构和基本运算（基本操作）。

我们老师上课讲的时候将数据结构抽象成了ADT
按照（1）ADT的定义：数据的逻辑特性和常用操作；（2）ADT的实现：存储结构以及操作算法。这两大部分来讲的，大体差不多。

• 逻辑结构
  1、线性表（Linear List）是具有相同数据类型的n个数据元素的有限序列，其中n为表长。数据元素之间具有线性关系。
  2、线性关系：除第一个元素外，每个元素都有且仅有一个前驱；除最后一个元素外，每个元素都有且仅有一个后继。
  【注】这里的位序是从1开始的，数组元素下标是从0开始的。在接下来的代码书写中要格外注意这一点。
• 存储结构
  线性表的存储结构有多种：一般线性表，即顺序表；链表：单链表和双链表。此外，还有循环链表，静态链表等。

本文仅讨论其中的一种形式：顺序表。在顺序表中，线性关系是通过物理上相邻来表示的，逻辑关系和物理位置一致！

• 算法（基本操作）参考博客：Click

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

#define Max_Size 100

typedef struct
{
   
    int *data;     //顺序表首地址（或者说数组的开头）
    int length;     //顺序表长度
    int maxSize;     //顺序表最大长度
}List;

//初始化
void InitList(List &l){
   
    l.data = (int *)malloc(sizeof(int));
    l.length = 0;
    l.maxSize = Max_Size;
    printf("-------以上为初始化！------\n");
}

//1.头插法
void push_front(List &l,int e){
   
    printf("-------以下为头插法！------\n");
    if(l.length==l.maxSize){
   
        printf("顺序表已满，无法进行头插！\n");
        return;  //本条语句作用：使其不再往下运行！
    }
    for(int i=l.length;i>0;i--){
    //注意循环条件的书写，头插从后往前转移，注意i的取值是>0
        l.data[i]=l.data[i-1];
    }
    l.data[0] = e;
    l.length++;  
}

//2.尾插法
void push_back(List &l,int e){
   
    printf("-------以下为尾插法！------\n");
    if(l.length==l.maxSize){
   
        printf("顺序表已满，无法进行尾插！！！\n");
        return;
    }
    l.data[l.length] = e;
    l.length++;   
}
//3.尾删法
void Del_back(List &l){
   
    printf("-------以下为尾删法！------\n");
    if(l.length == 0 || l.data==NULL){
   
        printf("顺序表为空，无法进行尾删！\n");
        return;
    }
    l.length--;
    
}
//4.头删法
void Del_front(List &l){
   
    printf("-------以下为头删法！------\n");
    if(l.length == 0 || l.data == NULL){
   
        printf("顺序表为空，无法进行头删！\n");
        return;
    }
    for(int i=0;i<l.length-1;i++){
   
        l.data[i] = l.data[i+1];
    }
    l.length--;
    
}
//5.按位插入
void Insert_Loc(List &l,int i,int e){
     //这里的位和数组下标不一致，比之多1
    printf("-------以下为按位插入！------\n");
    if(i>l.length+1 || i<1){
   
        printf("输入的i格式不正确！\n");
        return ;
    }
    if(l.length==l.maxSize){
   
        printf("顺序表已满，无法插入！\n");
        return ;
    }
    for(int j=l.length;j>i-1;j--){
   
        l.data[j] = l.data[j-1];
    }
    l.data[i-1] = e;
    l.length++;   
}
//6.按位删除
void Del_Loc(List &l,int i){
   
    printf("-------以下为按位删除！------\n");
    if(l.length == 0 || l.data == NULL){
   
        printf("顺序表为空，无法删除！\n");
        return ;
    }
    if(i>l.length||i<1){
   
        printf("输入的i不正确！\n");
        return;
    }
    for(int j=i-1;j<l.length-1;j++){
     //注意j循环条件取值
        l.data[j] = l.data[j+1];
    }
    l.length--;
}
//7.按值删除
void Del_Val(List &l,int e){
   
    printf("-------以下为按值删除！------\n");
    if(l.length == 0 || l.data == NULL){
   
        printf("顺序表为空，无法删除！\n");
        return ;
    }
    int data=0;
    for(int i=0;i<l.length;i++){
   
        if(l.data[i]==e){
   
            Del_Loc(l,i+1); //这里数值不太一样 下标和i
            data=1;
            return;
        }
    }
    if(data==0){
   
        printf("该顺序表中没有值为 %d 的数据\n",e);
        return ;
    }
}
//8.按位查找
int Search_Loc(List &l,int i){
   
     printf("-------以下为按位查找！------\n");
    if(i<1||i>l.length){
   
        printf("输入的i格式不正确！\n");
        return NULL;
    }
    if(l.length == 0 || l.data == NULL){
   
        printf("顺序表为空，无法查找！\n");
        return NULL;
    }
    return l.data[i-1];
}
//9.按值查找
int Search_Val(List &l,int e){
   
     printf("-------以下为按值查找！------\n");
    if(l.length == 0 || l.data == NULL){
   
        printf("顺序表为空，无法查找！\n");
        return NULL;
    }
    for(int j=0;j<l.length;j++){
   
        if(l.data[j]==e){
   
            return j+1;
        }
    }
    return NULL;
}
//10.排序(冒泡排序----从大到小)
void sort(List &l){
   
    if(l.length==0||l.data==NULL){
   
        printf("顺序表为空！\n");
        return;
    }
    for(int i=0;i<l.length;i++){
   
        for(int j=i+1;j<l.length;j++){
   
            int e;
            if(l.data[i]<l.data[j]){
   
                e=l.data[j];
                l.data[j]=l.data[i];
                l.data[i]=e;
            }
        }
    }
}
//11.倒置
void Inverse(List &l){
   
    if(l.length==0||l.data==NULL){
   
        printf("顺序表为空，无法查找！\n");
        return;
    }
    int low=0,high=l.length-1;
    int temp;
    while(low < high){
   
        temp=l.data[high];
        l.data[high]=l.data[low];
        l.data[low]=temp;
        low++;
        high--;
    }

}


//遍历输出
void printList(List &l){
   
    if(l.length>l.maxSize){
   
        printf("生成的顺序表中数据溢出！出错啦!\n");
        l.data==NULL;
        return;
    }        
    for(int i=0;i<l.length;i++){
   
        printf("%d ",l.data[i]);
    }
}

int main() {
   
    List l;
    InitList(l);
    //Del_front(l);
    push_front(l,3);
    push_front(l,2);
    push_back(l,4);
    push_back(l,5);
    push_back(l,6);
    push_back(l,7);
    push_back(l,8);
    // Del_front(l);
    // Del_back(l);
    // Del_Loc(l,2);
    // Del_Val(l,4);
    Insert_Loc(l,5,1);
    //sort(l);
    int e=5;
    int i=4;
    printf("顺序表中值为%d的位于第%d位\n",e,Search_Val(l,e));
    printf("顺序表中位于第%d位的值为%d\n",i,Search_Loc(l,i));
    printList(l);
    printf("\n");
    Inverse(l);
    printList(l);
    getchar();
    //system("pause");
    return 0;
}

以下为结果截图：