c语言进阶12-线性表之顺序表
一、 线性表的定义
为什么要学习线性表呢？
因为我们日常生活中存在种数据关系，计算机程序是为了解决日常生活的数据关系，因此我们要学习线性表。
线性表是什么呢？
线性表是由n个元素组成的有限序列。
需要强调几点:
- 1. 首先它是一个序列。也就是说元素之间是有顺序的，若元素有多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
- 2. 其次强调一个有限的元素个数。
例子1：
例子2:
大家判断是不是线性表？
答： 当然是，符合线性表的定义。
例子3：
大家再思考一下公司的组织架构，是不是线性表表呢？
答： 当然不是了，因为每一个元素，都不只一个后继，所以它不是线性表。
例子4:
大家思考，班级同学的友谊关系是不是线性表？
答：当然不是了，因为每个同学可以建立多个友谊关系，不满足线性表的定义，
例子:5
大家思考，班级同学的点名，是不是线性表示?
答： 是，因为点名是按顺序进行的，满足类型相同的特点。其中每个元素除了学生的学号外，还可以有学生的姓名、性别、出生年月日等。这些具体信息构成了一条数据项。
在复杂的线性表中，一个数据元素可以由若干个数据项组成。
二、 线性表的顺序存储结构
- 1. 顺序存储定义
我们来看看线性表的两种物理结构的第一种——顺序存储结构。线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
例子1 :
这就是很形象的顺序存储结构。
- 2. 顺序存储方式
线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位置的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个元素的类型都相同，所以可以用C语言的一维数组实现顺序存储结构，即把第一个数据元素存到数据下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。这个接着，因为我们一共9个人，所以他需要占9个座。线性表中，我们估算这个线性表最大存储容量，建立一个数组，数组的长度就是这个最大存储点容量。
·来看线性表的顺序存储的结构代码
#define MAXSIZE 20 /*存储空间初始分配量*/
typedef int ElemType; /* ElemType 类型根据实际情况而定，这里假设为int*/
typedef struct
{
ElemType data[MAXSIZE]; /*数组存储数据元素，最大值为MAXSIZE */
int length; /*线性表当前长度*/
}Sqlist;
这里，我们就发现描述顺序存储结构需要三个属性：
1、存储空间的起始位置:数组data，它的存储位置就是存在空间的存储位置。
2、线性表的最大存储容量：数组长度MaxSize.
3、线性表的当前长度:length. Length<=MaxSize
- 3. 数据长度与线性表长度区别
这里有两个概念”数组长度”和“线性表的长度”需要区分一下。数组的长度是存放线性表的存储空间的长度。线性表的长度是线性表中元素个数，随着线性表插入和删除操作的进行，这个量是变化的。在任何时刻，线性表的长度应该小于等于数组的长度。
- 4. 地址计算方法
由于我们数数都是从1开始数的，线性表的定义也不能避免，起始也是1，可C语言中的数组却是从0开始的第一个下标，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数组元素的序号和存放它的数组下标之间存在对应关系。
用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
其实，内存中的地址，就和图书馆或电影院里的座位一样，都是编号的。存储器中的每个存储单元都有自己的编号，这个编号称为地址。假设占用的是c个存储单元，那么线性表第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系：
通过这个例子，你可以随时计算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的访问时间。那么我们就可以对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存储时间性能为O(1)。我们通常把具有这一个特点的存储结构称之为随机存取结构。
三、 顺序存储结构的插入与删除
- 1. ACM算法：顺序表的插入操作
刚才我们也谈到，这里的时间复杂度为O(1)。我们考虑，如果我们要实现ListInsert，即在线性表L中的第i个位置插入新元素e，应该如何操作?
举个例子，本来我们在春运时候去买火车票，大家都排队的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲病了，我得着急回去看她，这队伍这么长，你可否让我排在你的前面？”你心一软，就同意了。这时，你必须的退一步。这个例子其实已经说明了线性表的顺序结构，在插入数据时的现实的实现过程。
插入算法的思路：
(1) 如果插入位置不合理，抛出异常；
(2) 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
(3) 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
(4) 将要插入元素填入位置i处；
(5) 表长加1;
实现代码如下:
#define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0
typedef int Status;
- 2. ACM算法：顺序表的删除操作
删除算法的思路:
(1) 如果删除位置不合理，抛出异常；
(2) 取出删除元素；
(3) 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
(4) 表长减1；
链表实现代码
/* Note:Your choice is C IDE */
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
typedef struct person{
int id;
char name[];
struct person *next;
}PERSON;
PERSON *head;
void lines(PERSON *p){
PERSON *pa,*pb;
pb=head;
if(head==NULL){
head=p; //链表头指针指向插入节点
}
else {
while(pb){
pa=pb;//第一次将头指针的指向赋给pa其他直接将自己指向的传给pa
pb=pb->next;//pb变为指向下一个节点的指针
}//循环完后p变为
pa->next=p;
}
p->next=NULL;
}
void charu(int j)
{
int p=,i;
PERSON *pa,*pb,*pc;
pb=head;
while(pb!=NULL)
{
pb=pb->next;
p++;
}
pa=head;
printf("\n现在的节点共%d个\n",p);
if(j<||j>p){
printf("输入数字有误！");
}else {
for(i=;i<j;i++)
{
pb=pa;
pa=pa->next;
}
printf("输入插入内容\n");
pc=(PERSON*)malloc(sizeof(PERSON));
if(!pc){
printf("内存分配失败!");
exit();
}
printf("请输入id：");
scanf("%d",&pc->id);
printf("请输入名字:");
fflush(stdin);
gets(pc->name);
pb->next=pc;
pc->next=pa;
}
}
void Delete(int j)
{
int p=,i;
PERSON *pa,*pb;
pb=head;
while(pb!=NULL)
{
pb=pb->next;
p++;
}
pa=head;
printf("\n现在的节点共%d个\n",p-);
if(j<=||j>p){
printf("输入数字有误！");
}else if(j==){
pb=pa->next;
head=pb;
free(pa);
}else
{
for(i=;i<j;i++)//找到要找一个
{
pb=pa;
pa=pa->next;
}
pb->next=pa->next;
free(pa);
}
}
void main()
{
int i=;
int j;
PERSON *p;
PERSON *pp;
char ch;
do{
//动态生成一个对象
p=(PERSON*)malloc(sizeof(PERSON));
if(!p){
printf("内存分配失败!");
ch=getchar();
exit();
}
printf("请输入id：");
scanf("%d",&p->id);
printf("请输入名字:");
fflush(stdin);
gets(p->name); lines(p);
printf("是否继续:");
ch=getchar();
fflush(stdin);
i++;
}while(ch=='y'||ch=='Y');
printf("准备插入在第几个:");
scanf("%d",&j);
charu(j);
pp=head;
while(pp!=NULL){
printf("%d %s\n",pp->id,pp->name);
pp=pp->next;
}
printf("你想删除第几个:");
scanf("%d",&j);
Delete(j);
pp=head;
while(pp!=NULL){
printf("%d %s\n",pp->id,pp->name);
pp=pp->next;
}
}
单链表无空头
#include "stdio.h"
#include "stdlib.h"
int i;//循环变量
struct nobe
{
int data;
struct nobe *next;
}*head;
void lines(struct nobe *p);//输入结点
void output();//输出节点
void delet();//删除一个节点
void cls();
void input();
void main()
{
struct nobe *p;
int bh;
for(;;){
printf("请选择链表功能:\n");
printf("1.创建链表\n");
printf("2.输出链表\n");
printf("3.删除节点\n");
printf("4.清空链表\n");
printf("5.插入节点\n");
printf("0.退出\n");
printf("请输入功能编号:");
scanf("%d",&bh);
switch(bh)
{
case :
printf("您选择的是常见链表功能:\n");
for(i=;i<;i++)
{
p=(struct nobe*)malloc(sizeof(struct nobe ));
if(!p)
{
printf("分配失败！");
}
printf("请输入第%d个节点的数据域的数据:\n",i+);
scanf("%d",&p->data);
fflush(stdin);
lines(p);
}
break;
case :
output();
break;
case :
delet();
break;
case :
cls();
break;
case :
input();
break;
case :
exit();
break;
default :
printf("您输入的功能编号有误！\n");
break;
}
}
}
void lines(struct nobe *p)//输入结点
{
struct nobe *pa,*pb;
pa=head;
if(head==NULL)
{
head=p;//将第一个节点当作表头
}else
{
while(pa)
{
pb=pa;
pa=pa->next;
}
pb->next=p;
}
p->next=NULL;
}
void output()//输出节点
{
struct nobe *p;
p=head;
if(head==NULL)
{
printf("暂无数据\n");
}else
{
while(p)
{ printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
}
void delet()
{
struct nobe *pa,*pb;
int a;
if(head==NULL)
{
printf("暂无数据\n");
}else
{
printf("请输入您准备删除的数据：");
scanf("%d",&a);
pa=head;
while(pa)
{
if(pa->data==a)
{
break;
}
pb=pa;//pa等于他前一个节点
pa=pa->next;
}
if(pa==NULL)
{
printf("您输入的数据有误！\n");
}
else if(pa->next==NULL)
{
pb->next=NULL;
free(pa);
}else{
pb->next=pa->next;
free(pa);
printf("删除成功！\n");
}
} }
void cls()
{
struct nobe *pa,*pb;
if(head==NULL)
{
printf("暂无数据\n");
}else
{
pa=head;
while(pa)
{
pb=pa;//pa等于他前一个节点
pa=pa->next;
free(pb);
}
head=NULL;
}
}
void input()
{
int n;
struct nobe *p,*pa;
p=(struct nobe *)malloc(sizeof(struct nobe));
pa=head;
printf("请输入要插入在第几个之后：");
scanf("%d",&n);
printf("输入数据:");
scanf("%d",&p->data);
if(n==)
{
head=p;
p->next=pa;
}else{
for(i=;i<n;i++)
{
pa=pa->next;
}
p->next=pa->next;
pa->next=p;}
printf("插入成功\n");
}
队列的实现代码
/* Note:Your choice is C IDE */
#include "stdio.h"
struct person{
int age[];
int top;
int rear;
};
void fun1(struct person *s){
int n;
printf("输入数字：");
scanf("%d",&n); if(s->rear<=){
s->age[s->rear]=n;
s->rear++;
} }
void fun2(struct person *s){
if(s->top!=s->rear){
s->top++;
}else
{
printf("无内容\n");
}
}
void fun3(struct person *s)
{
int i;
for(i=s->top;i<s->rear;i++)
{
printf(" %d \n",s->age[i]);
}
}
void main()
{
struct person s;
int bh;
s.top=;
s.rear=;
for(;;){
printf("1.入列\n2.出列\n3.输出\n");
scanf("%d",&bh);
switch(bh)
{
case :
fun1(&s);
break;
case :
fun2(&s);
break;
case :
fun3(&s);
break;
}
}
}
最新文章
- js复制内容加版权声明代码
- mysql使用笔记（四）
- POJ 2955 括号匹配，区间DP
- 关于text-align无法居中的问题
- oracle参数优化
- Cocos2d-x 2地图步行实现：SPFA算法
- Javascript实例技巧精选(7)—设置和获取文本框与文本域的光标位置（兼容IE和Chrome,Firefox）
- L3-001. 凑零钱
- HttpClient（二）HttpClient使用Ip代理与处理连接超时
- go 学习第一个hello world 遇到的问题
- Linux：Gentoo系统的安装笔记（一）
- vue 动态添加 <style> 样式 vue动态添加 绑定自定义字体样式
- eclipse哪个版本好
- 使用iostat来对linux硬盘IO性能进行检测
- HDU 1241 Oil Deposits（石油储藏）
- 【SpringBoot】单元测试进阶实战、自定义异常处理、t部署war项目到tomcat9和启动原理讲解
- 【Unity笔记】提示框ToolTips大小自适应，及其闪烁的问题
- 自定义 Core Data 迁移
- vs2012团队连接（Team Foundation Server）怎样从已登录的用户退出
- python3.6 ubuntu