数据结构笔记1线性表及其实现

终于开始学习数据结构了 c语言结束之后 我们通过题目来巩固了 接下来我们来学习数据结构

这里我们将去认识到数据结构的一些基础知识，我在第一次学习的时候会很迷糊现在重新学习发现之前的时候还是因为c语言学的不牢固导致学习数据结构困难 这里 我会尽量的多写代码注释

目录

一什么是数据结构？

二线性表

2.1概述

2.2特点

2.3储存方式

2.4线性表的基本操作

2.5线性表的顺序存储结构

2.5.1概述

2.5.2 创建顺序线性表

2.5.3获得元素操作

2.5.4插入操作

2.5.6删除操作

2.6线性表的链式存储结构

2.6.1概述

2.6.2 单链表的建立

 2.6.3单链表的读取

2.6.4单链表的插入

 2.6.5单链表的删除

2.6.6链表的整表删除

一什么是数据结构？

1.1 概述：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）

二线性表

2.1概述

：0个或多个数据元素的有限序列 

2.2特点

               1 元素之间是有顺序的 

                2 若元素存在多个，则第一个元素无前驱，最后一个元素无后驱 其他每个元素有且只有一个前驱和后驱

                3 元素的个数是有限的

2.3储存方式

                       顺序储存

                      链式储存

2.4线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表 L，并分配内存空间。

ListEmpty(L):若线性表为空，返回true 否则返回false

ClearList （*L）：将线性表清空

GetElem（L，i，*e）：将线性表L中的第i个元素值返回给e

LocateElem（L,e）：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功否则返回0 表示失败

ListInsert（*L，i，e）：在线性表L中第i个位置插入新元素e

ListDelete（*L,i，*e）：删除线性表L中第i个位置元素，并用e返回其值

LiseLength（L）：返回线性表L的元素个数

这里的基本操作 后面我们会都写出来的

2.5线性表的顺序存储结构

2.5.1概述

：用一段地址连续的储存单元依次储存线性表的数据元素

那说到这里的定义，大家是不是会联想到数组 数组的定义：数组由数据类型相同的一系列元素组成 即开辟一块内存空间 给数组 数组每相邻的元素不仅逻辑上相邻物理地址上也是相邻的

是不是和线性表的顺序储存结构一样 所以我们利用数组来完成线性表的顺序储存

我们来看线性表的顺序储存的结构代码

#define MAXSIZE 20 /*储存空间初始分配量 值无具体要求看线性表的大小*/
typedef int ElemType;/*这里我们将int类型取个别名为ElemType 方便我们后面对线性表的类型进行定义 ElemType也就是线性表的类型根据实际情况定，这里以int举例*/
typedef struct
{ElemType data[MAXSIZE]; //数组储存数据元素，最大值为MAXSIZEint length;
}Sqlist;//定义了一个结构体类型，别名为Sqlist 

这里我们发现描述顺序存储结构需要三个属性：

1 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置

2 线性表的最大存储空间：数组的长度MAXSIZE

3 线性表的当前长度：length。

我们再来补充一点：数据长度和线性表长度的区别

数组的长度是存放线性表的储存空间的长度，存储分配后一般不变，除非是动态分配

线性表的长度是线性表中数据元素的个数 伴随着线性表的插入和删除操作的进行这个量会进行改变。

简单的说呢 线性表存放在数组里面 但不一定是达到最大值存放的 所以线性表的长度是小于或等于数组的长度

这里我们举个例子，比如数组data[5] 数组的长度是5 线性表只有俩个元素 只用到了俩个数组元素

所以线性表的长度是2

2.5.2 创建顺序线性表

我们来通过示例来创建一个线性表

#include <stdio.h>
#define MAXSIZE 5 //这里我们举例就不用那么大的了 最大为5
typedef struct 
{int data[MAXSIZE];int length;
}Sqlist; /*这里的注释上面有 我就不提了*/
/*初始化线性表函数 我们需要对线性表进行操作 所以将线性表的地址传入进来通过指针对线性表进行操作*/
void Initlist(Sqlist *L)
{L->length=5;//线性表的长度为5for(int i=0;i<5;i++)//将线性表的每个元素都赋值{L->data[i]=i+1;}
}int main()
{Sqlist L;//建立一个线性表Initlist(&L);//初始化线性表for(int i;i<5;i++)//输出线性表的每个元素{printf("L.data[i]=%d\n",L.data[i]);}return 0;
}

这里需要特别注意，我们需要对线性表进行初始化，传入函数的参数一定不能错了 需要通过指针去操作的，这里我们的一个线性表就创建好了 我们将来一一介绍对线性表的操作

上面有过注释的 下面的代码 很有可能就不带了 大家需要一步一步的去理解 每一部分的注释我肯定都会写过的

2.5.3获得元素操作

概述：返回线性表L中的第i个元素的值

思路：就是将线性表的指定位置的值给输出出来

#include <stdio.h>
#define MAXSIZE 5 
typedef struct 
{int data[MAXSIZE];int length;
}Sqlist;
void Initlist(Sqlist *L)
{L->length=5;for(int i=0;i<5;i++){L->data[i]=i+2;}
}
//获得指定位置元素的值，参数是L 和指定位置比如指定获得线性表第二个元素的值
int GetElem(Sqlist L,int i)
{if(L.length==0 || i<1||i>L.length)//防止意外情况 返回0 即错误return 0;else{return i-1;/*在查找操作正确的时候，返回指定值的数组下标 因为数组下标是从0开始的 第2个元素的数组下标实际上是1所以返回指定位置-1即是数组的下标*/}
}
int main()
{Sqlist L;Initlist(&L);for(int i=0;i<5;i++){printf("L.data[i]:%d\n",L.data[i]);}int a;a=GetElem(L,2);//用a来接收GetElem的值 并判断是否查找正常if(a){printf("指定位置的值是%d\n",L.data[a]);       }elseprintf("获取指定位置的值出现错误 ");return 0;
}

2.5.4插入操作

概述：在线性表L中的第i个位置插入新元素e

思路：1 如果插入位置不合理，即错误

           2 如果线性表的长度等于数组的长度时即饱和了 无法进行插入 即错误除非动态增加容量

           3 从最后一个元素开始向前遍历到第i个位置，分别将它们都往后移动一个位置

           4 表长加1

代码有点长是因为我是举具体示例 实际上 这里只是ListInsert的应用

#include <stdio.h>
#define MAXSIZE 10 
typedef struct 
{int data[MAXSIZE];int length;
}Sqlist;
void Initlist(Sqlist *L)
{L->length=5;for(int i=0;i<5;i++){L->data[i]=i+2;}for(int j=5;j<10;j++){L->data[j]=0;}
}
int ListInsert(Sqlist *L,int i,int e)
{/*这里的判断条件是异常情况L->length==0 线性表长度为0L->length==MAXSIZE 线性表的长度等于数组的长度饱和了无法插入i>L->length+1 插入的位置在数组内，但是大于线性表的长度*/if(L->length==0 || L->length==MAXSIZE || i<1 || i>L->length+1){return 0;}/*如果插入的位置不在表尾 我们需要将i后的每一个元素都往后移动一位 将i位置空出来给新元素*/if(i<=L->length){//这里的判断循环条件大家注意一下 j>=i-1 因为我们需要将i位置在数组下标就是i-1的位置空出来//所以包括i-1的位置也需要往后移动 这里判断才有=号for(int j=L->length;j>=i-1;j--){L->data[j+1]=L->data[j];//每个元素往后移动一位，并不会影响到未移动的元素}}L->data[i-1]=e;//i-1的数组位置已经空出来了直接插入就可以L->length++;//因为加入了新元素 表长加一return 1;//代表插入成功
}
int main()
{Sqlist L;Initlist(&L);for(int i=0;i<5;i++){printf("L.data[i]:%d\n",L.data[i]);}int e=66;printf("插入后\n");if(ListInsert(&L,2,e))//如果插入成功，输出插入后的线性表的元素{for(int i=0;i<L.length;i++){printf("L.data[i]:%d\n",L.data[i]);}}else{printf("插入错误\n");}return 0;
}

2.5.6删除操作

删除算法的思路：如果删除的位置不合理 报错

                          ：取出删除元素

                          ：从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一位

                          ：表长减一

#include <stdio.h>
#define MAXSIZE 10 
typedef struct 
{int data[MAXSIZE];int length;
}Sqlist;
void Initlist(Sqlist *L)
{L->length=5;for(int i=0;i<5;i++){L->data[i]=i+2;}
} 
//删除 函数的参数是线性表地址和删除的位置i
int Listdelete(Sqlist *L,int i)
{if(L->length==0 || i<1 || i>L->length+1)//异常情况 前面都有详细描述 {return 0;}if(i<L->length)//如果不是尾元素{for(int j=i-1;j<=L->length;j++)//将i之后的元素全部往前移动一位 {L->data[j]=L->data[j+1];}}L->length--;// 表长减一return 1;
}
int main()
{Sqlist L;Initlist(&L);for(int i=0;i<5;i++){printf("L.data[i]:%d\n",L.data[i]);}printf("删除之后的线性表\n");if(Listdelete(&L,2)){for(int i=0;i<L.length;i++){printf("L.data[i]:%d\n",L.data[i]);}}return 0;
}

说到这里我们来总结一下线性表的顺序存储结构的优缺点

优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间

        ：可以快速地存取表中任一位置的元素

缺点：插入和删除操作需要移动大量元素

       ：当线性表长度变化较大时，难以确定存储空间的容量

       ：造成存储空间的碎片

2.6线性表的链式存储结构

2.6.1概述

：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的也可以是不连续的。即这些数据元素可以存在内存未被占用的任意位置。

前面我们说线性表的特点的时候说过线性表应该是有序的 但这里为什么是任意的呢？

因为在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址

因此：为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这俩部分信息组成数据元素ai的存储映像，称为结点

其实简单的来说，链式存储有俩个部分组成，一个是数据域 一个是指针域 因为地址可以是任意的，所以通过指针来将线性表中的结点去连接起来。

这里我们介绍几个特殊的地方：对于线性表来说，有头有尾，链表也一样。我们把链表中第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始进行的，之后的每一个结点，其实是上一个的后继指针指向的位置 ，其中最后一个结点的指针指向空

我们有时会在单链表的第一个结点前，设一个结点，称为头结点，头结点的数据域不存储任何信息

头结点的指针域指向第一个结点的指针

我们来看一下头节点和头指针的异同

头指针：头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

           ：头指针具标识作用，所以常用头指针冠以链表的名字

          ：无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点：头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义

          ：有了头结点，对于第一元素结点前插入和删除第一结点，其操作与其他结点的操作就统一了

           ：头结点不一定是链表的必须要素

2.6.2 单链表的建立

这里我们来看一下c语言的实现先来看结构体

typedef struct node{int data;//数据域struct node *next;//指针域
}node, *LinkList;  //结构体的定义

再来看一下建立单链表，需要注意我们新建一个新结点就需要新开辟一次内存空间出来

为什么需要建立三个指针 一个是头指针，一个是用于新建结点，一个是用于存储上一次建立结点

通过存储上一次建立的结点 将上一次的结点与新建立的结点进行链接

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{int data;struct node *next;
}node, *LinkList;  //结构体的定义LinkList create_Link()
{  //创建单链表的主要代码（尾插法建立单链表）LinkList head = NULL;//建立一个头指针，用于指向第一个结点LinkList temp = NULL;LinkList tail = NULL;head=(LinkList)malloc(sizeof(node));//声明头指针的内存head->next=NULL;//将头指针指向空int x;//用于键入结点的数据域 也是用来判断循环结束的条件scanf("%d",&x);while(x!=0)//当建立足够的结点的时候 键入0 停止建立{temp=(LinkList)malloc(sizeof(node));//声明一块内存是用来存储新结点temp->next=NULL;//将新结点的指针指向空防止野指针temp->data=x;//新结点的数据域数据就是键入的值if(head->next==NULL)//当第一次插入的时候把头指针指向第一个结点{head->next=temp;}else//非第一次 ，将上一次的结点的指针域指向新结点{tail->next=temp;}tail=temp;//用于保存上一次建立的结点，用于中间值scanf("%d",&x);}tail->next=NULL;//将最后一个结点的指针域指向空return head;
}int main(){  //主函数LinkList L = create_Link();L=L->next;while(L!=NULL){printf("%d\n",L->data);L=L->next;}return 0;
}

 这里我们重新新建一个线性表将数据域元素改成赋值 而不是键入 方便我们后面其他操作 比如删除插入等，核心代码是不会变得

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{int data;struct node *next;
}node, *LinkList;  //结构体的定义LinkList create_Link()
{  //创建单链表的主要代码（尾插法建立单链表）LinkList head = NULL;//建立一个头指针，用于指向第一个结点LinkList temp = NULL;LinkList tail = NULL;head=(LinkList)malloc(sizeof(node));//声明头指针的内存head->next=NULL;//将头指针指向空for(int i=0;i<5;i++){temp=(LinkList)malloc(sizeof(node));//声明一块内存是用来存储新结点temp->next=NULL;//将新结点的指针指向空防止野指针temp->data=i;//新结点的数据域数据就是键入的值if(head->next==NULL)//当第一次插入的时候把头指针指向第一个结点{head->next=temp;}else//非第一次 ，将上一次的结点的指针域指向新结点{tail->next=temp;}tail=temp;//用于保存上一次建立的结点，用于中间值}tail->next=NULL;//将最后一个结点的指针域指向空return head;
}int main(){  //主函数LinkList L = create_Link();L=L->next;while(L!=NULL){printf("%d\n",L->data);L=L->next;}return 0;
}

这里我们新建了一个单链表 有5个结点 数据域存放的分别是 0 1 2 3 4

后面我们对单链表的操作都是对这个表进行操作

 2.6.3单链表的读取

概述：获取第i个元素的数据域的值

思路：声明一个结点p指向链表的第一个结点，初始化j从1开始

       ：当j<i时，就遍历链表 让p的指针往后移动，不断指向下一结点，j累加1

       ：若到链表未尾p为空，则说明第i个元素不存在

       ：否则查找成功，返回结点p的数据。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{int data;struct node *next;
}node, *LinkList;  //结构体的定义LinkList create_Link()
{  //创建单链表的主要代码（尾插法建立单链表）LinkList head = NULL;//建立一个头指针，用于指向第一个结点LinkList temp = NULL;LinkList tail = NULL;head=(LinkList)malloc(sizeof(node));//声明头指针的内存head->next=NULL;//将头指针指向空for(int i=0;i<5;i++){temp=(LinkList)malloc(sizeof(node));//声明一块内存是用来存储新结点temp->next=NULL;//将新结点的指针指向空防止野指针temp->data=i;//新结点的数据域数据就是键入的值if(head->next==NULL)//当第一次插入的时候把头指针指向第一个结点{head->next=temp;}else//非第一次 ，将上一次的结点的指针域指向新结点{tail->next=temp;}tail=temp;//用于保存上一次建立的结点，用于中间值}tail->next=NULL;//将最后一个结点的指针域指向空return head;
}
int Getlist(LinkList L,int i)
{//i=3int j=0;LinkList p;//声明一个结点pp=L->next;//p指向链表l的第一个结点while( p&& j<i)//当p不为空 和j《i的时候循环直到p为空 或者j》=i{p=p->next;++j;}if(!p || j>i)//如果上述判断条件是p为空或者j>i的时候 即错误返回0return 0;return p->data;//返回第i个元素的数据域值
}
int main(){  //主函数LinkList L = create_Link();printf("%d\n",Getlist(L,3));return 0;
}

2.6.4单链表的插入

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{int data;struct node *next;
}node, *LinkList;  //结构体的定义LinkList create_Link()
{  //创建单链表的主要代码（尾插法建立单链表）LinkList head = NULL;//建立一个头指针，用于指向第一个结点LinkList temp = NULL;LinkList tail = NULL;head=(LinkList)malloc(sizeof(node));//声明头指针的内存head->next=NULL;//将头指针指向空for(int i=0;i<5;i++){temp=(LinkList)malloc(sizeof(node));//声明一块内存是用来存储新结点temp->next=NULL;//将新结点的指针指向空防止野指针temp->data=i;//新结点的数据域数据就是键入的值if(head->next==NULL)//当第一次插入的时候把头指针指向第一个结点{head->next=temp;}else//非第一次 ，将上一次的结点的指针域指向新结点{tail->next=temp;}tail=temp;//用于保存上一次建立的结点，用于中间值}tail->next=NULL;//将最后一个结点的指针域指向空return head;
}
int  listinsert(LinkList L,int i,int e)
{LinkList p,new;p=L;int j=1;while(p&&j<i){p=p->next;++j;}if(!p || j>i)return 0;//第i个元素不存在new=(LinkList)malloc(sizeof(node));//建立一块新的内存 存放结点new->data=e;//数据域赋值new->next=p->next;//将新结点的指针指向插入位置的下一个结点p->next=new;//将插入位置的上一个结点的指针域指向新结点return  1;
}
int main(){  //主函数LinkList L = create_Link();int a=listinsert(L,2,9);if(a){L=L->next;while(L!=NULL){printf("%d\n",L->data);L=L->next;}}return 0;
}

成功将9插入在第二个位置，这俩句是核心，一定要先将新结点的指针指向插入位置的下一个结点

    new->next=p->next;//将新结点的指针指向插入位置的下一个结点p->next=new;//将插入位置的上一个结点的指针域指向新结点

 2.6.5单链表的删除

这里我们需要注意我们要删除某个结点的时候我们将指针指向删除结点的上一个结点

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{int data;struct node *next;
}node, *LinkList;  //结构体的定义LinkList create_Link()
{  //创建单链表的主要代码（尾插法建立单链表）LinkList head = NULL;//建立一个头指针，用于指向第一个结点LinkList temp = NULL;LinkList tail = NULL;head=(LinkList)malloc(sizeof(node));//声明头指针的内存head->next=NULL;//将头指针指向空for(int i=0;i<5;i++){temp=(LinkList)malloc(sizeof(node));//声明一块内存是用来存储新结点temp->next=NULL;//将新结点的指针指向空防止野指针temp->data=i;//新结点的数据域数据就是键入的值if(head->next==NULL)//当第一次插入的时候把头指针指向第一个结点{head->next=temp;}else//非第一次 ，将上一次的结点的指针域指向新结点{tail->next=temp;}tail=temp;//用于保存上一次建立的结点，用于中间值}tail->next=NULL;//将最后一个结点的指针域指向空return head;
}
int  listdelete(LinkList L,int i)
{LinkList p,q;p=L;int j=1;while(p->next&&j<i){p=p->next;++j;}if(!p || j>i)return 0;//第i个元素不存在q=p->next;//将要删除的结点赋值给qp->next=q->next;//将指向删除结点的指针指向删除结点的下一个结点free(q);//释放删除结点的内存空间return  1;
}
int main(){  //主函数LinkList L = create_Link();int a=listdelete(L,2);if(a){L=L->next;while(L!=NULL){printf("%d\n",L->data);L=L->next;}}return 0;
}

2.6.6链表的整表删除

将每个结点的内存空间都进行释放

int  listclear(LinkList L,int i)
{LinkList p,q;p=L->next;while(p){q=p->next;free(p);p=q;}L->next=NULL;return  1;
}

最后我们将单链表和顺序链接做一下对比

存储分配方式：顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 利用数组

                      ：单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 利用指针

空间性能：顺序存储结构需要预分配存储空间，分大了 浪费 分小了 易发生上溢

              ：单链表不需要分配存储空间只要有就可以分配，元素个数也不受限制