首页 随笔

# 线性表

一个具有相同性质的的数据元素的序列

image-20220913151550098

# 顺序存储和链式存储

# 顺序存储

什么是顺序储存呢？

我们学 c 语言没多久就接触到了数组这个概念，这里所了解到的数组就是顺序储存
我们在很多地方都会用到数组使得我们的算法实现更加简单，但是当我们想要删除某个或者在某个位置加入一个元素的时候就会非常的麻烦

image-20220913005607258

如上图中，如果我们想在 12 之间加入一个字母 A，那么我们就需要将所有的元素后移一位，缺点很明显

  • 数据量大的时候需要移动大量数据，不符合算法的设计要求
  • 数组需要开一个庞大的空间为了防止溢出

为了解决这些问题我们可以选用链式存储的方式

# 链式存储

链表通过不连续的储存方式配合指针的灵活运用，减少计算量，并且链表是自适应大小的，也就是说理论上链表空间可以无限大（小于机器承载）

链表的基本思维是利用结构体的设置，额外开辟出一条内存空间去作指针，她总是指向下一个结点，各个结点通过 NEXT 相互联系

一个结点如下图

image-20220913010445304

这里的 data 数据类型并未做限制，多个链接起来

image-20220913010557172

构成了链表，用链表实现插入操作

image-20220913010635675

可以看到，我们只需要更改指针指向即可

链表有单链表，双链表和循环单链表

image-20220913010758871

# 顺序储存结构

顺序表，全名顺序储存结构，顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

# 1、顺序表的初始化

使用顺序表除了要提前申请到足够大小的物理空间以外，为了方便后期数据的使用，还需要记录两项数据

  1. 顺序表申请的存储容量
  2. 顺序表的长度，也就是表中存储数据元素的个数

注意：正常情况下顺序表的储存容量要大于顺序表的长度

因此我们自定义顺序表

typedef struct Table{
    int *head;// 声明了一个名为 head 的长度不确定的数组，也叫 “动态数组”
    int length;// 记录当前顺序表的长度
    int size;// 记录顺序表分配的存储容量
}table;

这里 head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。

初始化需要做两件事

  1. 给 head 动态数据申请到足够大小的空间
  2. 给 size 和 length 赋值
#define Size 5 // 对 Size 进行宏定义，表示顺序表申请空间的大小
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));// 构造一个空的顺序表，动态申请存储空间
    if (!t.head) // 如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }
    t.length=0;// 空表的长度初始化为 0
    t.size=Size;// 空表的初始存储空间为 Size
    return t;
}

完整的代码

#include <stdio.h>
#include <stdlib.h>
#define Size 5
typedef struct Table{
	int *head;
	int length;
	int size;
}table;
table initTable(){// 初始化函数
	table t;
	t.head=(int *)malloc(Size*sizeof(int));
	t.length=0;
	t.size=Size;
	return t;
}
void dispaly(table t)// 输出函数
{
	for(int i=0;i<t.length;i++){
		printf("%d",t.head[i]);
	}
	printf("\n");
}
int main(){
	table t=initTable();
	for (int i=1; i<=Size; i++) {
        t.head[i-1]=i;
        t.length++;
    }
    dispaly(t);
	return 0;
}
image-20220913233539593
# 2、顺序表的基本操作
# 1、顺序插入元素
向现有的表中插入数据，分下面三种情况
  1. 插入到顺序表的表头
  2. 在表中间插入
  3. 在表的末尾插入
插入的方式，先找到插入的位置，将位置后面的元素整体后移一个位置，然后将插入数据放到这个位置上
c 语言中代码实现
table addtable(table t,int data,int add){// 插入函数，data 为插入元素，add 为插入位置 
	if(add>t.length+1||add<1){
		printf("插入位置不合法");
	} 
	if(t.length>=t.size){// 判断顺序表是否已满
		t.head=(int *)realloc(t.head,(t.size+1)*sizeof(int));//realloc 函数重新分配内存空间
		t.size++;
	}
	for(int i=t.length-1;i>=add-1;i--){// 将插入位置后的元素后移
		t.head[i+1]=t.head[i];
	}
	t.head[add-1]=data;// 插入元素
	t.length++;// 顺序表长度加 1
	return t;
}
# 2、顺序表删除元素
和插入相对应，找到这个元素后将这个位置后面的元素整体向前位移一位
table deletetable(table t,int add){// 删除函数，add 为删除位置 
	if(add>t.length||add<1){
		printf("删除位置不合法");
	}
	for(int i=add;i<t.length;i++){// 将删除位置后的元素前移
		t.head[i-1]=t.head[i];
	}
	t.length--;// 顺序表长度减 1
	return t;
}
# 3、顺序表查找元素
table selecttable(table t,int data){// 查找函数，data 为查找元素 
	int i;
	for(i=0;i<t.length;i++){
		if(t.head[i]==data){
			printf("查找成功，该元素位置为%d",i+1);
			break;
		}
	}
	if(i==t.length){
		printf("查找失败");
	}
	return t;
}
# 4、顺序表更改元素
table updatetable(table t,int data,int newdata){// 修改函数，data 为修改元素，newdata 为修改后的元素 
	int i;
	for(i=0;i<t.length;i++){
		if(t.head[i]==data){
			t.head[i]=newdata;
			printf("修改成功");
			break;
		}
	}
	if(i==t.length){
		printf("修改失败");
	}
	return t;
}
# 总
#include <stdio.h>
#include <stdlib.h>
#define Size 5// 对 Size 进行宏定义，表示顺序表申请空间的大小
typedef struct Table{
	int *head;
	int length;// 记录当前顺序表的长度
	int size;// 记录顺序表分配的存储容量
}table;
table initTable(){// 初始化函数 
	table t;
	t.head=(int *)malloc(Size*sizeof(int));
	// 构造一个空的顺序表，动态申请存储空间
	t.length=0;
	t.size=Size;
	return t;
}
void dispaly(table t)// 输出函数 
{
	for(int i=0;i<t.length;i++){
		printf("%d",t.head[i]);
	}
	printf("\n");
}
table addtable(table t,int data,int add){// 插入函数，data 为插入元素，add 为插入位置 
	if(add>t.length+1||add<1){
		printf("插入位置不合法");
	} 
	if(t.length>=t.size){// 判断顺序表是否已满
		t.head=(int *)realloc(t.head,(t.size+1)*sizeof(int));//realloc 函数重新分配内存空间
		t.size++;
	}
	for(int i=t.length-1;i>=add-1;i--){// 将插入位置后的元素后移
		t.head[i+1]=t.head[i];
	}
	t.head[add-1]=data;// 插入元素
	t.length++;// 顺序表长度加 1
	return t;
} 
table deletetable(table t,int add){// 删除函数，add 为删除位置 
	if(add>t.length||add<1){
		printf("删除位置不合法");
	}
	for(int i=add;i<t.length;i++){// 将删除位置后的元素前移
		t.head[i-1]=t.head[i];
	}
	t.length--;// 顺序表长度减 1
	return t;
}
table selecttable(table t,int data){// 查找函数，data 为查找元素 
	int i;
	for(i=0;i<t.length;i++){
		if(t.head[i]==data){
			printf("查找成功，该元素位置为%d",i+1);
			break;
		}
	}
	if(i==t.length){
		printf("查找失败");
	}
	return t;
}
table updatetable(table t,int data,int newdata){// 修改函数，data 为修改元素，newdata 为修改后的元素 
	int i;
	for(i=0;i<t.length;i++){
		if(t.head[i]==data){
			t.head[i]=newdata;
			printf("修改成功");
			break;
		}
	}
	if(i==t.length){
		printf("修改失败");
	}
	return t;
}
int main(){ 
	table t=initTable();
	for (int i=1; i<=Size; i++) {
        t.head[i-1]=i;
        t.length++;
    }
    dispaly(t);
	return 0;
}
# 创建一个学生信息的顺序表
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Students{
	char id[15]; // 学号 
	char name[20]; // 名字 
	int price; // 成绩 
}student;
typedef struct List{
  	student  *elem;    // 指向数据元素的基地址
	int  length;      // 线性表的当前长度
}SqlList;
void init(SqlList &L,int n){
	L.elem=(student *)malloc(n*sizeof(student));// 分配 n 个元素的空间
	if(!L.elem) exit(0);// 分配失败
	printf("初始化成功！当前顺序表的最大长度为%d\n",n);
	L.length=0;// 初始化长度为 0
}
void add(SqlList &L,int n){// 向顺序表中添加 n 个学生的信息
	int i;
	for(i=0;i<n;i++){
		printf("请输入第%d个学生的学号、姓名、成绩:\n",i+1);
		scanf("%s%s%d",L.elem[i].id,L.elem[i].name,&L.elem[i].price);
		while(L.elem[i].price<0||L.elem[i].price>100){  // 判断输入的成绩是否合法
			printf("成绩输入错误，请重新输入:\n");
			scanf("%d",&L.elem[i].price);// 重新输入的合法成绩
		}
		L.length++;
	}
}
void print(SqlList &L){// 输出顺序表中的学生信息
	int i;
	printf("===============================\n");
	printf("学号\t姓名\t成绩\n");
	for(i=0;i<L.length;i++){// 输出学生信息
		printf("%s\t%s\t%d\n",L.elem[i].id,L.elem[i].name,L.elem[i].price);}
	}
void search(SqlList &L,char *name){// 查找顺序表中的学生信息
	int i;
	for(i=0;i<L.length;i++){
		if(strcmp(L.elem[i].name,name)==0){// 查找到了
			printf("学号\t成绩\n");
			printf("%s\t%d\n",L.elem[i].id,L.elem[i].price);
			break;
		}
	}
	if(i==L.length) printf("查无此人!\n");
}
void search1(SqlList &L,int rank){// 查找顺序表中指定位置的学生信息
	printf("学号\t姓名\t成绩\n");
	if(rank<1||rank>L.length){
		printf("输入的位次有误！\n");
		printf("表中数据个数为%d",L.length);
		}
	else{
		printf("%s\t%s\t%d\n",L.elem[rank-1].id,L.elem[rank-1].name,L.elem[rank-1].price);
	}
}
void insert(SqlList &L,int rank){// 在顺序表中指定位置插入学生信息
	int i;
	if(rank<1||rank>L.length+1){
		printf("输入的位次有误！\n");
	}
	else{
		for(i=L.length-1;i>=rank-1;i--){
			L.elem[i+1]=L.elem[i];
		}
		printf("请输入要插入的学生的学号、姓名、成绩:\n");
		scanf("%s%s%d",L.elem[rank-1].id,L.elem[rank-1].name,&L.elem[rank-1].price);
		while(L.elem[rank-1].price<0||L.elem[rank-1].price>100){  // 判断输入的成绩是否合法
			printf("成绩输入错误，请重新输入:\n");
			scanf("%d",&L.elem[rank-1].price);// 重新输入的合法成绩
		}
		L.length++;
	}
}
void del(SqlList &L,int rank){// 删除顺序表中指定位置的学生信息
	int i;
	if(rank<1||rank>L.length){
		printf("输入的位次有误！\n");
		printf("删除失败！\n");
	}
	else{
		for(i=rank-1;i<L.length-1;i++){
			L.elem[i]=L.elem[i+1];
		}
		L.length--;
	}
}
void statistics(SqlList &L)// 输出顺序表中学生数量
{
	printf("学生数量为：%d\n",L.length);
}
int main(){
	int N;
	printf("是否初始化顺序表？(y/n)\n");
	char ch;
	scanf("%c",&ch);
	SqlList L;
	if(ch=='y'){
		printf("请输入顺序表的最大长度:\n");
		scanf("%d",&N);
		init(L,N);// 初始化顺序表
	}
	else if(ch=='n'){
		printf("请先初始化顺序表！\n");
		exit(0);
	}
	else{
		printf("输入错误！\n");
		exit(0);
	}
	while(ch=='y'){
		// 功能表
		printf("\n请选择操作:\n");
		printf("===============================\n");
		printf("|1.添加学生信息               |\n");
		printf("|2.显示所有学生信息           |\n");
		printf("|3.查询指定学生信息           |\n");
		printf("|4.显示指定位次学生信息       |\n");
		printf("|5.将新加入学生信息插入       |\n");
		printf("|6.删除指定位次学生信息       |\n");
		printf("|7.显示学生现有学生人数       |\n");
		printf("|8.结束查询                   |\n");
		printf("===============================\n");
		printf("请输入操作序号:\n");
		int flag=-1;
		scanf("%d",&flag);
		switch(flag){
			case 1:
				printf("添加学生信息:\n");
				printf("请输入学生人数:");
				int n;
				scanf("%d",&n);
				if(n>N){
					printf("输入的学生人数超过顺序表的最大长度！\n");
					printf("添加失败！\n");
				}
				else{
					add(L,n);
					printf("添加成功！\n\n");
				}
				break;
			case 2:
				printf("显示所有学生信息:\n");
				print(L);
				break;
			case 3:
				printf("输入要查询的学生姓名:\n");
				char name[20];
				scanf("%s",name);
				search(L,name);
				printf("查询成功！\n\n");
				break;
			case 4:
				printf("输入要查询的学生位次:\n");
				int rank;
				scanf("%d",&rank);
				search1(L,rank);
				printf("查询成功！\n\n");
				break;
			case 5:
				printf("将新加入学生信息插入:\n");
				printf("请输入要插入的学生位次:\n");
				int rank1;
				scanf("%d",&rank1);
				insert(L,rank1);
				printf("插入成功！\n\n");
				break;
			case 6:
				printf("删除指定位次学生信息:\n");
				printf("请输入要删除的学生位次:\n");
				int rank2;
				scanf("%d",&rank2);
				del(L,rank2);
				printf("删除成功！\n\n");
				break;
			case 7:
				printf("显示学生现有学生人数:\n");
				statistics(L);
				break;
			case 8:
				printf("结束查询!我们下次再见\n");
				exit(0);
			    }
	}	
	return 0;
}
# 单链表的基础设计（c 语言实现）
# 1、单链表概念加设计
对于链路的每个结点我们使用结构体来设计
单链表是一种链式存储的数据结构，链表中的数据结构是以结点来表示的
结点 = 元素 + 指针
注：链表的结尾 NEXT 指向 NULL（空），因为结尾没有任何可以指向的空间了
对于一个单链表的结点定义，可以使用代码来描述
// 定义结点类型 
typedef struct Node{
	int data;// 数据类型是什么都行 
	struct Node *next;// 指针域 
}Node,*LinkedList;
//Node 表示结点的类型，Linkedlist 表示指向 Node 结点类型的指针类型
# 2、单链表的初始化
链表也是需要初始化的操作，初始化是创建一个单链表的前置结点，并向后逐步添加结点，一般来说，就是申请结点空间
LinkedList listinit(){
		Node *L;
		L=(Node*)malloc(sizeof(Node));// 申请空间
		if(L==NULL){// 判断空间是否申请成功
			exit(0);
		}
		L->next=null;// 指针指向空
	}
注：这个判断过程在现在的环境中基本用不上，但是得有
# 3、创建单链表（头插入法）
上面的初始化结束后遍可以创建了
单链表的创建分为头插入法和尾插入法，两者都是利用指针指向下一个结点元素方式逐个创建，不过使用头插入法得到的结果是逆序的
image-20220913140633812
类似这种，讲数据插在链表的表头
image-20220913151836019
c 语言实现
#include <stdio.h>
#include <stdlib.h>
typedef struct Link{// 定义结点类型 
	int data;// 数据类型 
	struct Link *next;// 指针域 
}link,*Linklist;
//link 表示结点的类型，LinkedList 表示指向 link 结点类型的指针类型
// 头插法建立单链表 
Linklist listcreeth(){
	link *p;
	p=(link *)malloc(sizeof(link));
	p->next=NULL;// 初始化一个空链表 
	
	int x;
	while(scanf("%d",&x)!=EOF){
		link *l;
		l=(link *)malloc(sizeof(link));
		l->data=x;
		l->next=p->next;
		p->next=l; 
	}
	return p;
} 
void display(link *p){
    link *temp=p;// 将 temp 指针重新指向头结点
    // 只要 temp 指针指向的结点的 next 不是 Null，就执行输出语句。
    while (temp) {
    	temp=temp->next;
        printf("%d ",temp->data);
    }
    printf("\n");
}
int main(){
	link *p=listcreeth();
	display(p);
	return 0;
}
<img src="https://note-1311335427.cos.ap-shanghai.myqcloud.com/images/image-20220913213253645.png" alt="image-20220913213253645" style="zoom:150%;" />
# 链表实现学生表
#include<stdio.h> 
#include<stdlib.h>
#include<string.h>
typedef struct Student
{
	char no[8];// 学号
	char name[20];// 姓名
	int graeds;// 成绩
}student;
typedef struct Node
{
	student data;// 数据域
	struct Node *next;// 指针域
}Link,*LinkList;
void linkinit(LinkList &L){// 初始化
	L=(LinkList)malloc(sizeof(Link));
	L->next=NULL;
	if(L==NULL){
		printf("初始化失败！！");
		exit(0);
	}
}
// 添加学生信息
void linkadd(LinkList &L){
	LinkList p=L;
	LinkList q;
	q=(LinkList)malloc(sizeof(Link));
	if(q==NULL){
		printf("录入失败！！");
	}
	printf("请输入学生学号和成绩\n");
	scanf("%s %s %d",q->data.no,q->data.name,&q->data.graeds);
	//printf("debug--->%s %s %d",q->data.no,q->data.name,q->data.graeds);
	while(p->next!=NULL){
		p=p->next;
	}
	p->next=q;
	q->next=NULL;
}
// 显示所有学生信息
void linkshow(LinkList &L){
	LinkList p=L->next;
	printf("学号\t姓名\t成绩\n");
	for(;p!=NULL;p=p->next){
		printf("%s\t%s\t%d\n",p->data.no,p->data.name,p->data.graeds);
	}
}
// 查找学生信息
void  linksearch(LinkList &L){
	LinkList p=L->next;
	char no[8];
	printf("请输入要查找的学生学号：");
	scanf("%s",no);
	while(p!=NULL){
		if(strcmp(p->data.no,no)==0){
			printf("学号\t姓名\t成绩\n");
			printf("%s\t%s\t%d\n",p->data.no,p->data.name,p->data.graeds);
			break;
		}
		p=p->next;
	}
	if(p==NULL){
		printf("没有找到该学生信息！！");
	}
}
// 显示指定位次学生信息
void linkshowrank(LinkList &L){
	LinkList p=L->next;
	int rank;
	printf("请输入要查找的学生位次：");
	scanf("%d",&rank);
	for(int i=1;i<rank;i++){
		p=p->next;
	}
	printf("学号\t姓名\t成绩\n");
	printf("%s\t%s\t%d\n",p->data.no,p->data.name,p->data.graeds);
}
// 将新加入学生信息插入到指定位置
void linkinsert(LinkList &L){
	LinkList p=L;
	LinkList q;
	q=(LinkList)malloc(sizeof(Link));
	if(q==NULL){
		printf("录入失败！！");
		exit(0);
	}
	printf("请输入学生学号和成绩\n");
	scanf("%s%s%d",q->data.no,q->data.name,&q->data.graeds);
	int rank;
	printf("请输入要插入的位置：");
	scanf("%d",&rank);
	for(int i=1;i<rank;i++){
		p=p->next;
	}
	q->next=p->next;
	p->next=q;
}
// 显示学生现有学生人数
void linkshownum(LinkList &L){
	LinkList p=L->next;
	int num=0;
	for(;p!=NULL;p=p->next){
		num++;
	}
	printf("现有学生人数为：%d",num);
}
// 删除指定学生信息
void linkdelete(LinkList &L){
	LinkList p=L->next;
	LinkList q=L;
	char no[8];
	printf("请输入要删除的学生学号：");
	scanf("%s",no);
	while(p!=NULL){
		if(strcmp(p->data.no,no)==0){
			q->next=p->next;
			free(p);
			break;
		}
		q=p;
		p=p->next;
	}
	if(p==NULL){
		printf("没有找到该学生信息！！");
	}
}
int main()
{
	printf("是否初始化链表?(y/n/q)\n");
	LinkList L;
	char ch='n';
	scanf("%c",&ch);
	if(ch=='y'){
		linkinit(L);
		printf("初始化成功！！\n");
	}
	else if(ch=='n'){
		printf("请先初始化链表！\n");
	}
	else if(ch=='q'){
		printf("退出程序！\n");
		exit(0);
	}
	else{
		printf("输入错误！\n");
	}
	while(ch=='y'){
		printf("\n请选择操作:\n");
		printf("===============================\n");
		printf("|1.添加学生信息               |\n");
		printf("|2.显示所有学生信息           |\n");
		printf("|3.查询指定学生信息           |\n");
		printf("|4.显示指定位次学生信息       |\n");
		printf("|5.将新加入学生信息插入       |\n");
		printf("|6.删除指定位次学生信息       |\n");
		printf("|7.显示学生现有学生人数       |\n");
		printf("|8.结束查询                   |\n");
		printf("===============================\n");
		int choose=-1;
		scanf("%d",&choose);
		switch(choose){
			case 1:// 添加学生信息
			{
				linkadd(L);
			}
			case 2:// 显示所有学生信息
			{
				linkshow(L);
				break;
			}
			case 3:// 查询指定学生信息
			{
				linksearch(L);
				break;
			}
			case 4:// 显示指定位次学生信息
			{
				linkshowrank(L);
				break;
			}
			case 5:// 将新加入学生信息插入到指定位置
			{
				linkinsert(L);
				break;
			}
			case 6:// 删除指定位次学生信息
			{
				linkdelete(L);
				break;
			}
			case 7:// 显示学生现有学生人数
			{
				linkshownum(L);
				break;
			}
			case 8:// 结束查询
			{
				printf("退出程序！\n");
				exit(0);
			}
		}
	}	
	return 0;
}