顺序表小解

从这个程序开始，我会分为两个板块，一个是单个代码功能块分解讲解，另一个是完整的代码，供各位取用

顺序表重点在于结构体的建立，要理解结构体的作用、创建时的方法——堆空间法，栈空间法，这会涉及指针和分配空间的方法。
1）堆空间法：
关键字——new——分配堆空间
适用于定义一个指针变量。
需要将记录存储数据的长度的变量初始化为-1；

table *InsList(){ 
    table *L; L = new table; L->length = -1; return L; } int main(){ 
    table *L; L = InsList(); }

2）栈空间法：
适用于定义一个顺序表的变量，非指针。
值用将记录存储数据的长度的变量初始化为-1；

void InsList(table *L){ 
    L->length = -1; } int main(){ 
    table L; InsList(&L); }

从上述例子看出，堆空间法的结构体变量申明的是指针类型变量，在电脑内部只会给你这个结构体的指针类型变量，但没有给他分配空间，于是初始化时候，需要用到new或者malloc来分配空间。
而栈空间法则不用，只需要直接给初始长度归零即可。不过一般使用堆空间法，因为这样可以对分配的空间进行一定程度的掌控。

这个程序用的是栈空间法初始化，因此要用到NEW来分配空间。

1、顺序表创建及初始化。
程序如下：

#include <iostream> #include <stdlib.h> using namespace std; static int size; //结构体  typedef struct Student{ 
    int * stuNu; int length; }stu; //-------------------------------------------------实现功能-----------------------------------------------------//  //初始化表  stu InitList(){ 
    stu s; s.stuNu = new int; if(!s.stuNu ){ 
    printf("空间申请失败，建表失败！！\n"); exit(0); } s.length = 0; return s; } //选择功能的菜单  void menu(){ 
    printf("1.创建 2.插入*\n"); printf("3.删除 4.查找*\n"); printf("5.输出 6.退出*\n"); } int main(){ 
    //初始化一个表  stu s1;s1 = InitList(); int choose; while(1){ 
    menu();//菜单  printf("请输入对应功能的序号！！\n"); scanf("%d",&choose); switch (choose) { 
    case 1:creation(s1);break; case 2:Insert(s1);break; case 3:Delete(s1);break; case 4:Locate(s1);break; case 5:displaystudent(s1);break; case 6: exit(0); default:printf("输入非法！！！\n"); } } displaystudent(s1); return 0; }

讲解：
这里我用了菜单这个功能，感觉用起来高大上、也好用，但是有个问题，将会在下一个代码——链表里面体现出来，到时候我会大概解释一下。
至于初始化的其他方面则没啥好说的，

2、顺序表素的输出。
程序如下：

//输出  void displaystudent(stu s){ 
    printf("表的内容如下：\n"); for(int i=0; i<s.length; i++){ 
    printf("%d ",s.stuNu[i]); } printf("\n"); } //创建表并且输入  void creation(stu &s){ 
    printf("请输入数据个数：\n"); scanf("%d",&size); printf("请输入数据（每个数据用空格隔开）：\n"); for(int i=0; i<size; i++){ 
    scanf("%d",&s.stuNu[i]); s.length++; } displaystudent(s); }

讲解：
输出没啥，注意传递顺序表的时候别掉了取地址符——“&”就行，这个的作用是将你用的那个顺序表的地址传递给你这个输出函数的形参顺序表，让这两个绑定，这样，你在输出函数里对顺序表的操作——删除、插入、改值（可以注意后面的删除、插入代码块的传顺序表，都用到了取地址符）等都会影响到原本的那个顺序表。如果你不带取地址符，则不会影响。这个涉及到了指针的一点知识

3、顺序表的插入运算。
程序如下：

//实现插入功能 bool ListInsert(stu &s, int place, int data){ 
    if (place<1 || place>s.length) { 
    printf("位置无效！！！\n"); return false; } for (int j = s.length; j >= place; j--)//位置i及之后素后移 { 
    s.stuNu[j] = s.stuNu[j - 1]; } s.stuNu[place - 1] = data; s.length++; return true; } //插入 void Insert(stu &s){ 
    int place, data; bool flag; printf("请输入插入数据的位置(从1开始)：\n"); scanf("%d",&place); printf("请输入要插入的数据：\n"); scanf("%d",&data); flag = ListInsert(s, place, data); if(flag){ 
    printf("插入成功！！\n"); displaystudent(s); } }

讲解：
我这里是分为两个板块，一个 bool型的插入功能板块，一个是中间过渡，与外界衔接的viod型板块。这样可以使得代码块的功能更加单一，后期出问题更好解决。
再就是注意插入的话，需要把涉及到的值移位。

4、顺序表的删除运算
程序如下：

//实现删除功能  bool ListDelete(stu &s, int place) { 
    if (place<1 || place>s.length) { 
    printf("位置无效！！！\n"); return false; } for (int j = place; j <= s.length - 1; j++)//位置i之后素依次后移覆盖 { 
    s.stuNu[j - 1] = s.stuNu[j]; } s.length--; return true; } //操作删除功能  void Delete(stu &s){ 
    int place;bool flag; printf("请输入想要删除的数据的位置序号(从1开始)：\n"); scanf("%d",&place); flag = ListDelete(s, place); if(flag){ 
    printf("删除成功！！\n"); displaystudent(s); } }

讲解：
同样的，分为两个代码块。这里的就是注意删除后，将后面的值前移，填补空位。

5、顺序表的按值查找。
程序如下：

//实现查找功能  int ListLocate(stu s, int data){ 
    int i;bool flag; for(i=0; i<s.length; i++){ 
    if(s.stuNu[i] == data){ 
    flag = true; break; } } if(flag){ 
    return i; } else{ 
    return -1; } } //操作查找功能  void Locate(stu s){ 
    int data; printf("请输入想要查找的数据：\n"); scanf("%d",&data); if(ListLocate(s, data) == -1){ 
    printf("查无此数！！\n"); } printf("%d在表中的位置是：%d\n",data,ListLocate(s, data)); }

讲解：
注意看我的查找代码，他的形参顺序表是没有取地址符的，因为我这里只是查值，不涉及表内容的更改，一次用不到取地址。再就是查找的时候注意，值的存在性与是否超位置。查找分为按值查找和按位置查找。如果按位置查找就有可能越界。

完整代码：

#include <iostream> #include <stdlib.h> using namespace std; static int size; //结构体  typedef struct Student{ 
    int * stuNu; int length; }stu; //-------------------------------------------------实现功能-----------------------------------------------------//  //初始化表  stu InitList(){ 
    stu s; s.stuNu = new int; if(!s.stuNu ){ 
    printf("空间申请失败，建表失败！！\n"); exit(0); } s.length = 0; return s; } //实现插入功能 bool ListInsert(stu &s, int place, int data){ 
    if (place<1 || place>s.length) { 
    printf("位置无效！！！\n"); return false; } for (int j = s.length; j >= place; j--)//位置i及之后素后移 { 
    s.stuNu[j] = s.stuNu[j - 1]; } s.stuNu[place - 1] = data; s.length++; return true; } //实现删除功能  bool ListDelete(stu &s, int place) { 
    if (place<1 || place>s.length) { 
    printf("位置无效！！！\n"); return false; } for (int j = place; j <= s.length - 1; j++)//位置i之后素依次后移覆盖 { 
    s.stuNu[j - 1] = s.stuNu[j]; } s.length--; return true; } //实现查找功能  int ListLocate(stu s, int data){ 
    int i;bool flag; for(i=0; i<s.length; i++){ 
    if(s.stuNu[i] == data){ 
    flag = true; break; } } if(flag){ 
    return i; } else{ 
    return -1; } } //----------------------------------------------------操作实现功能-------------------------------------------------//  //输出  void displaystudent(stu s){ 
    printf("表的内容如下：\n"); for(int i=0; i<s.length; i++){ 
    printf("%d ",s.stuNu[i]); } printf("\n"); } //创建表并且输入  void creation(stu &s){ 
    printf("请输入数据个数：\n"); scanf("%d",&size); printf("请输入数据（每个数据用空格隔开）：\n"); for(int i=0; i<size; i++){ 
    scanf("%d",&s.stuNu[i]); s.length++; } displaystudent(s); } //插入 void Insert(stu &s){ 
    int place, data; bool flag; printf("请输入插入数据的位置(从1开始)：\n"); scanf("%d",&place); printf("请输入要插入的数据：\n"); scanf("%d",&data); flag = ListInsert(s, place, data); if(flag){ 
    printf("插入成功！！\n"); displaystudent(s); } } //操作查找功能  void Locate(stu s){ 
    int data; printf("请输入想要查找的数据：\n"); scanf("%d",&data); if(ListLocate(s, data) == -1){ 
    printf("查无此数！！\n"); } printf("%d在表中的位置是：%d\n",data,ListLocate(s, data)); } //操作删除功能  void Delete(stu &s){ 
    int place;bool flag; printf("请输入想要删除的数据的位置序号(从1开始)：\n"); scanf("%d",&place); flag = ListDelete(s, place); if(flag){ 
    printf("删除成功！！\n"); displaystudent(s); } } //选择功能的菜单  void menu(){ 
    printf("1.创建 2.插入*\n"); printf("3.删除 4.查找*\n"); printf("5.输出 6.退出*\n"); } int main(){ 
    //初始化一个表  stu s1;s1 = InitList(); int choose; while(1){ 
    menu();//菜单  printf("请输入对应功能的序号！！\n"); scanf("%d",&choose); switch (choose) { 
    case 1:creation(s1);break; case 2:Insert(s1);break; case 3:Delete(s1);break; case 4:Locate(s1);break; case 5:displaystudent(s1);break; case 6: exit(0); default:printf("输入非法！！！\n"); } } displaystudent(s1); return 0; }

再说一遍功能。删除功能有两种思路，一种是对确切的值进行删除，一种是对确切的位置进行删除。但首先都需要判断表里是否为空。然后再去寻找对应的值或者位置，将其删除。这里体现了顺序表的不变之处，不管什么思路的删除，完了之后，都要进行一个顺位前移后面的素，即删除素后的空位需要后面的补上来。
但是再看查找，可以遍历表，匹配精确的值，或者根据实际的数据的某种规律进行推导，得到该值大概的下标范围，然后查找，如果在实际中，数据比较庞大的时候，这个就非常好用。
还有插入功能同样如此，根据实际的值来寻找插入的位置，或者给定下标来插入，都是非常方便的，所以顺序表较链表的查找、插入功能，着实方便。

相关推荐