|
作为一名才接触c语言半年的大一学生，在自学数据结构时是非常痛苦的，单是第一章顺序表的创建与操作就令我苦不堪言，在经过两天的钻研后，基本才算理顺了顺序表，所以我就想写下这篇人生中第一篇博客记录我对c语言数据结构中顺序表的理解。（初学者一名，有什么不对的地方大家可以提出来一起讨论，万分感谢）
数据结构主要研究的就是数据在计算机中的存储和处理方法，而线性表就是最简单而且最常用的一种数据结构，线性表的三大特点，有头结点，尾结点，其他的每个结点都有前驱节点和后驱结点，线性表的顺序存储就称为顺序表。
简单的说，顺序表可以看做一个数组，而大多数人习惯用结构体保存顺序表的信息。那怎样创建一个顺序表呢？顺序表是线性表的一种，所以按照线性表的三大特点，首先我们需要建立一个结构体头结点来存放顺序表的信息，因为顺序表创建后需要用来填充数据，但数据并不一定填满所以头结点存放的信息的第一个——你创建的顺序表容量，第二个自然就是你实际使用的顺序表容量。那么问题来了？数据放在哪里？上面讲了，顺序表可以看做一个数组，那我们第三个信息就可以定义一个指向数组首地址的指针，而这个数组就用来保存数据，一个结构体形式的顺序表头结点就建立好了（用来存放顺序表的总容量，顺序表已经使用的容量，一个指向用来存放数据的数组的首地址的指针），代码如下：
顺序表头结点的建立
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct begin_SeqList//定义的头结点结构体用来保存结构体的信息
{
int capacity;//顺序表长度
int length;//实际使用的长度
int *node;//指向数组node[capacity]首地址的指针（存放数据）
}TSeqList;
顺序表的创建?
接下来就是按头结点所保存的信息建立顺序表了（就是写一个函数）这个函数的作用就是创建好顺序表（包括头结点和储存数据的数组）并返回顺序表的地址（也就是头结点），创建失败就返回NULL，这样使用顺序表时就可以通过返回的头结点中指向数组首地址的指针存放数据到数组中，具体代码如下：
?
TSeqList* SeqList_creat(int capacity)//创建指定容量的顺序表返回创建好的顺序表
{
TSeqList *temp=NULL;
temp=(TSeqList *)malloc(sizeof(TSeqList));//为头结点分配空间
if(temp==NULL)//判断申请失败的情况
{
printf("SeqList_Creat():error");
return NULL;//结束创建
}
memset(temp,0,sizeof(TSeqList));//使用memset初始化顺序表（库函数，可以查阅）
temp->capacity=capacity;
temp->length=0;
temp->node=(int *)malloc(sizeof(int )*capacity);//分配头结点指定容量的数组分配空间
if(temp->node==NULL)//申请失败
{
printf("SeqList_Creat():error");
return NULL;
}
return temp;//返回分配好的顺序表地址
}
?
顺序表的使用?
如上，一个顺序表就常见完成了，但怎么使用呢？我最开始在网上查阅“顺序表怎么使用”，但搜出来的都是顺序表数据的插入，删除，查找等操作，现在我才认为我这个问题属实有点弱智了，顺序表的使用其实就是对一个创建好的数组的赋值嘛，哈哈，这么一说你们是不是明白多了。下面就随便写一个顺序表的使用，具体代码如下，粗略看一下就行。（主要还是研究插入，删除等操作的）
int main()
{
int capacity;
printf("请输入顺序表的容量\n");
scanf("%d",&capacity);
TSeqList *p;//用来接收返回的顺序表；
p=SeqList_creat(capacity);//引用顺序表
printf("输入顺序表(-1结束输入)\n");
for(int i=0;i<p->capacity;i++)//给顺序表赋值
{
scanf("%d",&p->node[i]);
while(p->node[i]==-1)
{
goto start;（库函数，可查阅）
}
p->length++;
}
start:
printf("输出顺序表\n");
for(int i=0;i<p->length;i++)
{
printf("%d ",p->node[i]);
}
}
封装顺序表插入数据函数?
好了，顺序表的基本知识弄清楚了，那就需要了解顺序表的插入，删除，这些操作了（重点），这里都用封装函数的方式写，首先是顺序表中元素的插入，顺序表插入时需要考虑的东西很多，首先，刚才应该判断刚才顺序表是否创建成功（健壮性判断），即创建顺序表的函数返回的是不是空；第二个考虑的就是顺序表的容量是不是已经使用完了，如果顺序表已满，你可以选择再分配内存给新的数据或者提示分配错误（偷个懒，哈哈）；
int SeqList_insert(TSeqList *list,int x,int pos)//顺序表，要插入的元素，在哪里插入
{
TSeqList *temp=NULL;
if(list==NULL)//顺序表创建失败
{
return -1;
}
temp=list;//重点
if(temp->length==temp->capacity)//顺序表已满（这个和创建失败也可以用||连接）
{
return -1;
}
if(pos>temp->length)//尾插（可以改变pos在实际长度后面，即中间有空余的情况）
{
pos=temp->length;
}
for(int i=temp->length;i>pos;i--)//实际的length比现在大1，所以不会越界
{
temp->node[i]=temp->node[i-1];
}
temp->node[pos]=x;
temp->length++;
return 0;
}
顺序表插入函数的完整使用?
所以插入数据的函数就封装完了，我们来使用一下，注意这里插入的位置pos相当于数组的下标，例如1235，需要在第4个位置插入一个4，而第四个位置下标是3，所以此时的pos应该代3；
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct begin_SeqList//定义的头结点结构体用来保存结构体的信息
{
int capacity;//最大长度
int length;//当前长度
int *node;//定义指针数组node[capacity]（存放数据）
}TSeqList;
TSeqList* SeqList_creat(int capacity)//创建指定容量的顺序表返回创建好的顺序表
{
TSeqList *temp=NULL;
temp=(TSeqList *)malloc(sizeof(TSeqList));//为头结点分配空间
if(temp==NULL)//判断申请失败的情况
{
printf("SeqList_Creat():error");
return NULL;//结束创建
}
memset(temp,0,sizeof(TSeqList));//使用memset初始化顺序表（库函数，可以查阅）
temp->capacity=capacity;
temp->length=0;
temp->node=(int *)malloc(sizeof(int )*capacity);//分配头结点指定容量的数组分配空间
if(temp->node==NULL)//申请失败
{
printf("SeqList_Creat():error");
return NULL;
}
return temp;//返回分配好的顺序表地址
}
int SeqList_insert(TSeqList *list,int x,int pos)//顺序表，要插入的元素，在哪里插入
{
TSeqList *temp=NULL;
if(list==NULL)//顺序表创建失败
{
return -1;
}
temp=list;//重点
if(temp->length==temp->capacity)//顺序表已满（这个和创建失败也可以用||连接）
{
return -1;
}
if(pos>temp->length)//尾插（可以改变pos在实际长度后面，即中间有空余的情况）
{
pos=temp->length;
}
for(int i=temp->length;i>pos;i--)//实际的length比现在大1，所以不会越界
{
temp->node[i]=temp->node[i-1];
}
temp->node[pos]=x;
temp->length++;
return 0;
}
int main()
{
int capacity;
printf("请输入顺序表的容量\n");
scanf("%d",&capacity);
TSeqList *p;
p=SeqList_creat(capacity);//引用顺序表
printf("输入顺序表(-1结束输入)\n");
for(int i=0;i<p->capacity;i++)
{
scanf("%d",&p->node[i]);
while(p->node[i]==-1)
{
goto start;
}
p->length++;
}
start:
printf("输出顺序表\n");
for(int i=0;i<p->length;i++)
{
printf("%d ",p->node[i]);
}
printf("\n");
int x;
int Node;
printf("输入插入的元素和位置\n");
scanf("%d %d",&x,&Node);
int m=SeqList_insert(p,x,Node);
if(m!=0)
{
printf("SeqList_insert():error %d\n",m);
}
printf("插入后的顺序表\n");
for(int i=0;i<p->length;i++)
{
printf("%d ",p->node[i]);
}
}
运行一下就是下面这个效果?
请输入顺序表的容量
10
输入顺序表(-1结束输入)
1 2 3 4 5 7 -1
输出顺序表
1 2 3 4 5 7
输入插入的元素和位置
6 5
插入后的顺序表
1 2 3 4 5 6 7
顺序表数据的删除?
?相比于插入，删除要考虑的就比较少，只需要考虑顺序表创建失败的情况或者删除的位置有问题的情况，但因为要移动元素，所以效率还是比较低，代码如下：
int SeqList_delete(TSeqList *list,int pos)//删除数据（顺序表，删除位置）
{
TSeqList *temp=NULL;
if(list==NULL||pos<0||pos>list->length)
{
return -1;
}
temp=list;
for(int i=pos+1;i<temp->length;i++)
{
temp->node[i-1]=temp->node[i];
}
temp->length--;
return 0;
}
顺序表删除函数的完整使用?
?顺序表的数据删除函数就封装好了，使用具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct begin_SeqList//定义的头结点结构体用来保存结构体的信息
{
int capacity;//最大长度
int length;//当前长度
int *node;//定义指针数组node[capacity]（存放数据）
}TSeqList;
TSeqList* SeqList_creat(int capacity)//创建指定容量的顺序表返回创建好的顺序表
{
TSeqList *temp=NULL;
temp=(TSeqList *)malloc(sizeof(TSeqList));//为头结点分配空间
if(temp==NULL)//判断申请失败的情况
{
printf("SeqList_Creat():error");
return NULL;//结束创建
}
memset(temp,0,sizeof(TSeqList));//使用memset初始化顺序表
temp->capacity=capacity;
temp->length=0;
temp->node=(int *)malloc(sizeof(int )*capacity);//分配指定容量的数组
if(temp->node==NULL)//申请失败
{
printf("SeqList_Creat():error");
return NULL;
}
return temp;//返回分配好的顺序表地址
}
int SeqList_delete(TSeqList *list,int pos)//删除数据（顺序表，删除位置）
{
TSeqList *temp=NULL;
if(list==NULL||pos<0||pos>list->length)
{
return -1;
}
temp=list;
for(int i=pos+1;i<temp->length;i++)
{
temp->node[i-1]=temp->node[i];
}
temp->length--;
return 0;
}
int main()
{
int capacity;
printf("请输入顺序表的容量\n");
scanf("%d",&capacity);
TSeqList *p;
p=SeqList_creat(capacity);//引用顺序表
printf("输入顺序表(-1结束输入)\n");
for(int i=0;i<p->capacity;i++)
{
scanf("%d",&p->node[i]);
while(p->node[i]==-1)
{
goto start;
}
p->length++;
}
start:
printf("输出顺序表\n");
for(int i=0;i<p->length;i++)
{
printf("%d ",p->node[i]);
}
printf("\n");
printf("请输入要删除的元素位置\n");
int x,m;
scanf("%d",&x);
m=SeqList_delete(p,x);
if(m!=0)
{
printf("SeqList_delete(): error\n");
}
printf("输出删除后的顺序表\n");
for(int i=0;i<p->length;i++)
{
printf("%d ",p->node[i]);
}
}
?请输入顺序表的容量
10
输入顺序表(-1结束输入)
1 2 3 4 5 -1
输出顺序表
1 2 3 4 5
请输入要删除的元素位置
2
输出删除后的顺序表
1 2 4 5
运行下来就是这个效果啦，顺序表的操作还有查找，清空（内容全部置为0），销毁（释放分配的内存）等 ，都是差不多的思路，理解了上面两个之后就很好写了，由于这是我第一次写博客，感觉语言有些繁琐，再加上刚学c语言没多久，可能代码优化也不够完善，如果有什么错误希望大家见谅，万分感谢。
|