数据结构（2）线性表的顺序存储
数据结构（2）线性表的顺序存储
数据结构这门课，自从大二没学好之后一直想找机会学，之前也学过一段时间，但也只进行到了栈和队列，这学期在过完C++后，又拿出来学这门重要且难学的课，又一次打开学过几次的线性表的顺序存储，但这一次的学习发现了很多漏洞，也学会了一些新的东西。所以这篇文章不会从头到尾长篇大论的讲述整个线性表的顺序存储是怎么个事，仅仅是把自己遇到的问题以及新学到的内容记录下来，加深一下自己的印象。
p、*p与&p
平平无奇的指针，我的问题是，为什么函数的形参设置为指针类型后，调用时传的参数是对这个变量取地址。举个栗子🌰：
//定义时：
int Insert(SqList *L,int i,int e){
......
}
//调用时：
Insert(&L,i,e);这种用法之前一直当做常识去用了，直到昨天我才去想，为什么要这么做？我翻了很久之前学指针时的笔记，才找到答案：
也就是说，我们传进去参数的地址，再通过函数内的* 加 地址来改变变量的值
&引用
关于这个符号之前在学习的时候也疑惑过，只不过当时模棱两可就过去了。疑惑点在于，为什么在定义一系列函数时，可以定义为诸如这样的形式 ：
int Insert(SqList &L){
......
}
int InitList(SqList &L){
.....
}更让我疑问的是，有些书上使用的是上面的格式，有些书使用的又是这样的：
int Insert(SqList *L){
......
}
int InitList(SqList *L){
.....
}在我之前的认知里，*号就是取指，&就是取地址，所以怎么想也想不明白，于是就是Google了一下才找到答案：
&的一个用法是我们熟悉的取地址，另一个用法则是引用，在作为形参使用时，和指针的作用是相同的。
插入操作的-1是怎么来的？
在插入操作中，插进一个元素，则这个元素以及后面的所有元素都向后移一位，理解起来很好理解，但看到有些代码是这样写的：
if (i <= L->length) {//等于可取，因为等于相当于在最后一个元素的位置插，需要把最后一个元素往后移一位
for (int j = L->length-1; j >= i-1; j--) {//注意要-1，因为data[L->length-1]是最后一个元素
L->data[j + 1] = L->data[j];
}
}我就很疑惑为什么循环要从i-1循环到length-1，但其实核心就在于第i位对应的是data[i-1]，上面的函数也完全可以写为：
if(i<=L->length) {
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j-1];
}
}动态分配内存建表以及扩充容量
这个问题也是很早就有了，在暑假时学数据结构看了两本参考书，一本是学校的教材，一本是市面上颇为有名的《大话数据结构》，其中教材中给出的建表就是动态分配内存建表，而大话数据结构中给的代码则是静态分配内存建表。所幸在这几天的学习中，也了解了他们的 区别及用法。
最后 ，也以两种方式的线性表顺序存储的代码收尾。
- 静态实现
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define MaxSize 5
//建表（静态）
typedef struct {
int data[MaxSize];
int length;
}SqList;
//初始化
int InitList(SqList *L){
L->length = 0;
return OK;
}
//按值查找
int GetList(SqList L,int i,int *e){
if(i<1 || i>L.length || L.length==0){
return ERROR;
}
*e = L.data[i-1];
}
//按位查找
int LocateList(SqList L,int e){
int i;
if(L.length==0){
return ERROR;
}
for(i=1;i<L.length;i++){
if(L.data[i-1]==e){
break;
}
}
printf("这个值在第%d位\n",i);
return i;
}
//插入
int Insert(SqList *L,int i,int e){
if(i<1 || i>L->length+1){
return ERROR;
}
if(L->length==L->MaxSize){
return ERROR;
}
if(i<=L->length) {
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j-1];
}
}
L->data[i-1]=e;
L->length++;
return OK;
}
//删除
int Delete(SqList *L,int i,int *e){
if(L->length == 0){
return ERROR;
}
if(i<1 || i>L->length){
return ERROR;
}
if(i<L->length){
for(int j=i;j<=L->length;j++){
L->data[j-1]=L->data[j];
}
}
*e=L->data[i-1];
L->length--;
return OK;
}
//输出
int Print(SqList L){
if(L.length==0){
return ERROR;
}
for(int i=1;i<=L.length;i++){
printf("%d\t",L.data[i-1]);
}
printf("\n");
return OK;
}#include <stdio.h>
#include <stdlib.h>
#include "L.h"
int main(){
SqList L;
int e;
int i;
int a[3]={12,3,4};
InitList(&L);
Print(L);
for(i=1;i<=3;i++){
Insert(&L,i,a[i-1]);
}
Print(L);
GetList(L,2,&e);
printf("查到的值e为%d\n",e);
LocateList(L,3);
Insert(&L,4,9);
Print(L);
Insert(&L,5,19);
Print(L);
}
- 动态实现
/*（线性表）顺序表的实现--动态分配*/
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define InitSize 5
//建表
typedef struct {
int *data;//指向动态分配的数组的指针（指向数组第一个元素）
int MaxSize;//最大容量
int length;//当前表长
}SqList;
//初始化
int InitList(SqList *L){
L->data = (int*) malloc(InitSize*sizeof(int));
L->MaxSize = InitSize;
L->length = 0;
}
//扩大容量
int Increase(SqList *L,int len){//len是要扩大多少
int *p;
p=L->data;
L->data = (int *) malloc((InitSize+len)*sizeof(int));
for(int i=1;i<=L->length;i++){
p[i-1]=L->data[i-1];
}
L->MaxSize = InitSize + len;
free(p);
return OK;
}
//输出当前最大容量
int GetSize(SqList L){
printf("当前最大容量为:%d\n",L.MaxSize);
return OK;
}
//按位查找,第i个元素是啥
int GetList(SqList L,int i,int *e){
if(i<1 || i>L.length){
return ERROR;
}
*e = L.data[i-1];//思考为啥是*e
printf("第%d位是%d\n",i,*e);
return OK;
}
//按值查找
int LocateList(SqList L,int e){
int i;
for(i=1;i<=L.length;i++){
if(e == L.data[i-1]){
break;
}
}
return i;
}
//插入
int Insert(SqList *L,int i,int e){
if(i<1 || i>L->length+1){
return ERROR;
}
if(L->length==L->MaxSize){
return ERROR;
}
if(i<=L->length) {
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j-1];
}
}
L->data[i-1]=e;
L->length++;
return OK;
}
//删除
int Delete(SqList *L,int i,int *e){
if(i<1 || i>L->length){
return ERROR;
}
if(L->length==0){
return ERROR;
}
if(i<L->length){
for(int j=i;j<=L->length;j++){
L->data[j-1]=L->data[j];
}
*e = L->data[i-1];
L->length--;
return OK;
}
}
//输出
int Print(SqList L){
if(L.length==0){
return ERROR;
}
for(int i=1;i<=L.length;i++){
printf("%d\t",L.data[i-1]);
}
printf("\n");
return OK;
}#include <stdio.h>
#include <stdlib.h>
#include "L.h"
int main(){
SqList L;
int e;
int i;
int a[3]={12,3,4};
InitList(&L);
Print(L);
for(i=1;i<=3;i++){
Insert(&L,i,a[i-1]);
}
Print(L);
GetList(L,2,&e);
printf("查到的值e为%d\n",e);
LocateList(L,3);
Insert(&L,4,9);
Print(L);
Insert(&L,5,19);
Print(L);
GetSize(L);
Increase(&L,5);
GetSize(L);
}几个问题（over）
为什么函数参数是*指针类型，调用的时候要用&取地址结论：调用函数时传变量的地址，在被调用函数通过*+地址来改变主调函数中的变量的值*e 、&e 、e 的关系？函数内部能否调用之前定义的函数嵌套插入操作的循环为什么要-1？为什么删除操作的循环就不用-1？基于动态建表又该怎么写？基于动态建表怎么扩容 ？又怎么应用到插入操作里？
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录