文章目录
数据结构（c语言版） 第二章 线性表
2.1线性表的类型定义
- 线性表：
线性表是最常用且最简单的一种数据结构。
在稍复杂的线性表中，我们常把数据元素称为记录，含有大量记录的线性表又称为文件。
线性表中的数据元素可以是各种各样的，但==同一线性表中的元素必定具有相同特性。 ==
2.2线性表的顺序表示和实现
- 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
直接上代码：
首先是用结构体构造你需要的节点
struct node{ //构造线性表的顺序结构的节点(数据元素）
int *elem; //注意你要存储什么类型的数据就定义怎样的指针
int len; //表中实际使用的长度
int listlen; //表被分配的长度
};
然后是创建顺序结构的线性表
void creatlist(node *list,int llen){ //创建顺序结构的线性表，向函数中传输两个参数，
list->elem = (int *)malloc(llen*sizeof(int)); //一个是即将创建的线性表 ，一个是表的长度。
if(!list->elem){
printf("空间分配失败！");
return;
}else{
list->len = 0;
list->listlen = llen;
}
}
创建链表的顺序结构后坑定要向链表中添加元素，所以需要插入元素的代码
void insertnode(node list,int insertplace,int element){ //这里是顺序线性表的插入insertplace是插入的位置，element是要插入的数据，首先要检测
if(list.len+1>list.listlen){ //首先要检测线性表的长度是不是能够满足插入后所需要的长度
int *newbase = (int*)realloc(list.elem,list.listlen+1*sizeof(int)); //不满足时要增加空间，用realloc函数增加
if(newbase) list.elem = newbase;
}
for(int i = list.len+1;i > insertplace;i --){ //将从插入位置开始的数据依次向后移动一位
*(list.elem+i) = *(list.elem+i-1);
}
*(list.elem+insertplace) = element; //在需要的位置插入数据
list.len += 1; //别忘记插入成功后把线性表实际使用的长度+1
}
这段代码就是向你想要添加元素的位置进行元素的添加
顺序结构的特点——地址连续
node testlist; //定义一个测试线性表
creatlist(&testlist,100); //开始创建个长度为100的线性表
for(int i = 0;i < 10;i ++){ //简单的输入十个数，因为是学习，就不放太多
scanf("%d",testlist.elem+i);//值得注意的是，与书上的格式不同，这里是elem+i
testlist.len ++;
} //要学会指针啊！！
for(int i = 0;i < 10;i ++){
printf("%p\n",testlist.elem+i);//这里是输出分配的地址
}
我们向其中输入十个数并得到这十个数的地址
- 这里可以看到，每一个地址都是连续的，他们之间只差了一个int（你的表中数据元素的格式是什么，这里就是什么）的大小，这对应了上面对线性表顺序结构的介绍——地址连续.
能输入必然能输出
- 我们输入了十个数，就可以输出这十个数
node testlist; //定义一个测试线性表
creatlist(&testlist,100); //开始创建个长度为100的线性表
for(int i = 0;i < 10;i ++){ //简单的输入十个数，因为是学习，就不放太多
scanf("%d",testlist.elem+i);//值得注意的是，与书上的格式不同，这里是elem+i
testlist.len ++;
} //要学会指针啊！！
for(int i = 0;i < 10;i ++){
printf("%d ",*(testlist.elem+i));//这里是输出我们刚刚输入的十个数
}
看一下输出的结果是不是相同
- 显然这里的输入输出是相同的，证明我们的线性表的顺序结构代码是对的。
前面还有一个插入模块
node testlist; //定义一个测试线性表
creatlist(&testlist,100); //开始创建个长度为100的线性表
for(int i = 0;i < 10;i ++){ //简单的输入十个数，因为是学习，就不放太多
scanf("%d",testlist.elem+i);//值得注意的是，与书上的格式不同，这里是elem+i
testlist.len ++;
} //要学会指针啊！！
insertnode(testlist,5,100); //接着上面的测试，我们将测试线性表的第6个位置插入100,值得提醒的是，我们是从0开始储存，第六个位置的下表就是5
for(int i = 0;i < testlist.len;i ++){
printf("%d ",*(testlist.elem+i)); //输出插入后的线性表
}
- 看一下插入结果
- 数据元素成功添加进入线性表，证明插入模块没有问题。
- 最后将完整代码写入
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
struct node{ //构造线性表的顺序结构的节点(数据元素）
int *elem; //注意你要存储什么类型的数据就定义怎样的指针
int len; //表中实际使用的长度
int listlen; //表被分配的长度
};
void creatlist(node *list,int llen){ //创建顺序结构的线性表，向函数中传输两个参数，
list->elem = (int *)malloc(llen*sizeof(int)); //一个是即将创建的线性表 ，一个是表的长度。
if(!list->elem){
printf("空间分配失败！");
return;
}else{
list->len = 0;
list->listlen = llen;
}
}
void insertnode(node list,int insertplace,int element){ //这里是顺序线性表的插入insertplace是插入的位置，element是要插入的数据，首先要检测
if(list.len+1>list.listlen){ //首先要检测线性表的长度是不是能够满足插入后所需要的长度
int *newbase = (int*)realloc(list.elem,list.listlen+1*sizeof(int)); //不满足时要增加空间，用realloc函数增加
if(newbase) list.elem = newbase;
}
for(int i = list.len+1;i > insertplace;i --){ //将从插入位置开始的数据依次向后移动一位
*(list.elem+i) = *(list.elem+i-1);
}
*(list.elem+insertplace) = element; //在需要的位置插入数据
list.len += 1; //别忘记插入成功后把线性表实际使用的长度+1
}
int main(){
node testlist; //定义一个测试线性表
creatlist(&testlist,100); //开始创建个长度为100的线性表
for(int i = 0;i < 10;i ++){ //简单的输入十个数，因为是学习，就不放太多
scanf("%d",testlist.elem+i);//值得注意的是，与书上的格式不同，这里是elem+i
testlist.len ++;
} //要学会指针啊！！
for(int i = 0;i < 10;i ++){
printf("%p\n",testlist.elem+i);//这里是输出分配的地址
}
for(int i = 0;i < 10;i ++){
printf("%d ",*(testlist.elem+i));//这里是输出我们刚刚输入的十个数
}
insertnode(testlist,5,100); //接着上面的测试，我们将测试线性表的第6个位置插入100,值得提醒的是，我们是从0开始储存，第六个位置的下表就是5
for(int i = 0;i < testlist.len;i ++){
printf("%d ",*(testlist.elem+i)); //输出插入后的线性表
}
}
今天就告一段落，每天继续写链式结构。