赞
踩
线性表:线性表是零个或者多个数据元素的有限序列,是最常用且最简单的一种数据结构。
特点:
(1)存在惟一的一个被称做“第一个”的数据元素。
(2)存在惟一的一个被称做“最后一个”的数据元素。
(3)除第一之外,集合中每个元素均只有一个前驱。
(4)除最后一个之外,集合中每个数据元素均只有一个后继。
数学语言来定义: 线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定具有相同特性,即属于同一数据对象,相邻数据元素之间存在着序偶关系。 若将线性表记为(a1,…ai-1,ai,ai+1…,an),则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2…,n-1时,ai有且仅有一个直接后继,当i=2,3…n时,ai有且仅有一个直接前驱。如图所示:
所以线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。
例如:我们的的星座表就是一个简单的线性表。
在较复杂的线性表中,一个数据元素可以由若干个数据项组成。这种情况下,常把数据元素称为记录,含有大量记录的线性表又称为文件。 例如:
线性表的抽象数据类型: 线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,还可以进行插入和删除等。
抽象数据类型线性表的定义如下:
对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的。对于实际问题中涉及的关于线性表的更复杂的操作,完全可以使用这些基本操作的组合来实现。
例如:要实现两个线性表集合A和集合B的并集操作。即要使得集合A=AUB。就是把存在集合B但并不存在A中的数据元素插入到A中即可。只要循环B中的每个元素,判断当前元素是否存在A中,若不存在,插入到A中即可。
线性表的顺序存储:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构,说白了就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。例如:我们C语言中的一维数组就是如此,从们可以用它来实现线性表的顺序存储,把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。线性表的这种机内表示称做线性表的顺序存储结构或顺序映像,通常称为这种存储结构的线性表为顺序表。通常用数组来描述数据结构中的顺序存储结构。
描述顺序存储结构需要三个属性:
1.存储空间的起始位置ElemType * elem:ElemType为数据元素的类型,ElemType * elem代表它的存储位置就是存储空间的位置。
2.线性表的当前长度(元素)length:在任意时刻,线性表的当前长度应该小于等于最大长度。
3.线性表的最大长度listsize(容量):如果最大长度不足时,可再分配。
如果最大长度不足时,可再分配(一般为扩大2倍):
线性表的地址计算:
线性表的第i个元素存储在数组下标为i-1的位置,数据元素的序号和存放它的数组下标之间存在对对应关系如图:
存储器中每个存储单元都有自己的编号,这个编号称为地址。由于每个数据元素,不管它是整型、实型还是字符型,他都是需要占用一定的存储空间的。假设占用的是c个存储单元,那么线性表中第i+1个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)
因此对于第i个数据元素ai的存储位置可以由a1推算得出:
顺序存储的优点与缺点:
线性表的顺序存储结构,在存、读数据时,不管哪个位置,时间复杂都是O(1);而插入和删除时,时间复杂度都是O(n)。
头文件:
#pragma once //动态增长内存,将存放数据的内存放在堆上 //动态数组 如果当前5个元素内存不够 不要申请内存 拷贝数据 释放数据 //容量capacity表示我这块内存空间一共可以存放多少元素 //size 记录当前数组中具体的元素个数 //动态数据结构体 typedef struct DYNAMICARRAY { int* pAddr;//具体存放数据的地址 int size;//当前有多少个元素 int capacity;//容量,容器当前最大能容纳多少个元素 }Dynamic_Array; //写一系列的相关对DYNAMICARRAY结构体操作的函数 //初始化 Dynamic_Array* Init_Array(); //获得动态数组容量 int Capacity_Array(DYNAMICARRAY* arr); //获得动态数组当前元素个数 int Size_Array(DYNAMICARRAY* arr); //插入:尾插 void PushBack_Array(Dynamic_Array* arr,int val); //根据位置删除 void RemoveByPos_Array(DYNAMICARRAY* arr,int pos); //根据值查找 int Find_Array(DYNAMICARRAY*arr,int value); //根据值删除 void RemoveByValue_Array(DYNAMICARRAY*arr,int value); //根据给位获得某个位置元素 int At_Array(DYNAMICARRAY*arr ,int pos); //打印 void Print_Array(DYNAMICARRAY*arr); //清空数组 void Clear_Array(DYNAMICARRAY*arr); //释放动态数组的内存 void FreeSpace_Array(DYNAMICARRAY* arr);
函数功能实现文件:
//Author:Mr.Rain //Data:2020.2.13 #include <stdio.h> #include <stdlib.h> #include <string.h> #include "DynamicArray.h" //初始化 Dynamic_Array* Init_Array() { //申请内存 Dynamic_Array* myArray = (Dynamic_Array*)malloc(sizeof(Dynamic_Array)); //初始化 myArray->size = 0; myArray->capacity = 20; myArray->pAddr = (int*)malloc(sizeof(int)*myArray->capacity); return myArray; } //获得动态数组容量 int Capacity_Array(DYNAMICARRAY* arr) { if (arr == NULL) return -1; return arr->capacity; } //获得动态数组当前元素个数 int Size_Array(DYNAMICARRAY* arr) { if (arr == NULL) return -1; return arr->size; } //插入 void PushBack_Array(Dynamic_Array* arr,int value) { if (arr == NULL) return; //判断空间是否足够 if (arr->size == arr->capacity) { //1.申请一块更大的内存空间 新空间是旧空间的2倍 int* newSpace = (int*)malloc(sizeof(int)*arr->capacity*2); //2.拷贝数据到新的空间 memcpy(newSpace,arr->pAddr,arr->capacity * sizeof(int)); //3.释放旧空间的内存 free(arr->pAddr); //4.更新容量 arr->capacity = arr->capacity*2; arr->pAddr = newSpace; } //插入新元素 arr->pAddr[arr->size] = value; arr->size++; } //根据位置删除 void RemoveByPos_Array(DYNAMICARRAY* arr,int pos) { if (arr == NULL) return; //判断位置是否有效 if (pos<0 || pos>=arr->size) return; //删除元素 for (int i=pos; i<arr->size-1; i++) { arr->pAddr[i] = arr->pAddr[i+1]; } arr->size--; } //根据值查找 int Find_Array(DYNAMICARRAY*arr,int value) { if (arr == NULL) return -1; //查找 int pos = -1; for (int i=0; i<arr->size; i++) { if (arr->pAddr[i] == value) { pos = i; break; } } return pos; } //根据值删除value第一次出现的位置 void RemoveByValue_Array(DYNAMICARRAY*arr,int value) { if (arr == NULL) return; //找到值的位置 int pos = Find_Array(arr,value); //根据位置删除 RemoveByPos_Array(arr,pos); } //根据位置获得某个位置元素 int At_Array(DYNAMICARRAY*arr ,int pos) { return arr->pAddr[pos]; } //打印 void Print_Array(DYNAMICARRAY*arr) { for (int i=0; i<arr->size; i++) { printf("%d ",arr->pAddr[i]); } printf("\n"); } //清空数组 void Clear_Array(DYNAMICARRAY*arr) { if (arr == NULL) return; //pAddr->空间 arr->size = 0; } //释放动态数组的内存 void FreeSpace_Array(DYNAMICARRAY* arr) { if (arr == NULL) return; if (arr->pAddr != NULL) { free(arr->pAddr); } free(arr); }
main中测试文件:
void test1() { //初始化动态数组 Dynamic_Array* myArray = Init_Array(); //打印容量,插入前打印 //printf("插入前数组容量:%d\n",Capacity_Array(myArray)); //printf("插入前数组大小:%d\n",Size_Array(myArray)); //插入元素 for (int i=0; i<30; i++) { PushBack_Array(myArray,i); } //打印容量,插入后打印 printf("插入后数组容量:%d\n",Capacity_Array(myArray)); printf("插入后数组大小:%d\n",Size_Array(myArray)); //打印 Print_Array(myArray); //删除 RemoveByPos_Array(myArray,0); RemoveByValue_Array(myArray,28); //打印 Print_Array(myArray); //查找第五个位置的元素 int pos = Find_Array(myArray,5); printf("5查找到pos为%d %d\n",pos,At_Array(myArray,pos)); //销毁 FreeSpace_Array(myArray); }
测试:
测试案例1:插入10个元素并打印
测试结果:插入并打印成功。
测试案例2:插入30个元素进行扩容测试
测试结果:成功扩容并插入成功
测试案例3:按位置删除0号下标的元素与值为28的元素
测试结果:删除成功。
测试案例4:按位置删除0号下标的元素与值为28的元素后查找数值为5的下标
线性表的链式存储:是用一组任意的存储单元存储线性表的数据元素,这组数据元素可以是连续的,也可以是不连续的。为了表示每个数据元素ai与其直接后继ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为结点。
n个结点链结成一个链表,即为线性表(a1,a2,…an)的链式存储结构,因此链表的每个结点中只包含一个指针域,所以叫单链表。 如图所示:
我们把链表中第一个结点的存储位置叫做头指针,整个链表的存取从头指针进行。线性表的最后一个结点指针为“空”(NULL或^也可以)。
为了更加方便使用,有时我们会在单链表的第一个结点前附设一个头结点。头结点的数据域可以不存储任何信息。头结点的指针域存储指向第一个结点的指针。
头指针与头结点的异同点:
空链表:若线性表为空表,则头结点的指针域为空。
单链表:实际使用中,我们更关系线性表中的数据元素及数据元素之间的逻辑关系。因此,改用更方便的存储示意图来表示单链表。
带有头结点的单链表如图所示:
空链表如图所示:
那么我们如何使用代码表示它呢?我们可以使用C语言中的指针来表示这一结构。
结点由存放数据元素的数据域存放后继结点地址的指针域组成。 假设p是指向线性表第i个元素的指针,则该结点ai的数据域我们可以用p->data来表示,p->data的值是一个数据元素,结点ai的指针域可以用p->next来表示,p->next的值是一个指针。p->next指向第i+1个元素,即指向ai+1的指针。也就是说,p->data=ai,p->next->data=ai+1。如图所示:
(1)若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。
(2)当线性表中的元素个数变化较大或者根本不知道多大时,最好采用单链表结构,这样可以不用考虑存储空间大小问题。而如果事先知道线性表的大致长度,例如一年2个月这种用顺序存储结构效率会高很多。
头文件:
#pragma once //链表结点 typedef struct LINKNODE { void* data;//数据域,指向任何类型数据 struct LINKNODE* next;//指针域 }LinkNode; //链表结构体 typedef struct LINKLIST { LinkNode* head; int size; }LinkList; //打印函数指针 typedef void(*PRINTLINKNODE)(void*); //初始化链表 LinkList* Init_LinkList(); //指定位置插入数据 void Insert_LinkList(LinkList* list,int pos,void* data); //删除指定位置的值 void RemoveByPos_LinkList(LinkList* list,int pos); //获得链表的长度 int Size_LinkList(LinkList* list); //查找 int Find_List(LinkList* list,void* data); //返回第一个结点的位置 void* Front_LinkList(LinkList* list); //打印链表结点 void Print_LinkList(LinkList* list,PRINTLINKNODE print); //释放链表内存 void FreeSpace_LinkList(LinkList* list);
函数功能实现文件:
//Author:Mr.Rain //Data:2020.2.13 #include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkList.h" //初始化链表 LinkList* Init_LinkList() { LinkList* list = (LinkList*)malloc(sizeof(LinkList)); list->size = 0; //头结点 是不保存数据信息 list->head = (LinkNode*)malloc(sizeof(LinkNode)); list->head->data = NULL; list->head->next = NULL; return list; } //指定位置插入数据 void Insert_LinkList(LinkList* list,int pos,void* data) { if (list == NULL || data == NULL ) return ; if (pos<0 || pos>list->size) return ; //创建新的结点 LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode)); newnode->data = data; newnode->next = NULL; //找结点,辅助指针变量 LinkNode* pCurrent = list->head; for (int i=0; i<pos; i++) { pCurrent = pCurrent->next; } //新结点入链表 newnode->next = pCurrent->next; pCurrent->next = newnode; list->size++; } //删除指定位置的值 void RemoveByPos_LinkList(LinkList* list,int pos) { if (list == NULL) return ; if (pos<0 || pos>=list->size) return; //查找删除结点的前一个结点 LinkNode* pCurrent = list->head; for (int i=0; i<pos; i++) { pCurrent = pCurrent->next; } //缓存删除的结点 LinkNode* pDel = pCurrent->next; pCurrent->next = pDel->next; //释放删除结点的内存 free(pDel); list->size--; } //获得链表的长度 int Size_LinkList(LinkList* list) { return list->size; } //查找 int Find_List(LinkList* list,void* data) { if (list == NULL || data == NULL) return -1; //遍历 LinkNode* pCurrent = list->head->next; int i=0; while (pCurrent != NULL) { if (pCurrent->data == data) { break; } i++; pCurrent = pCurrent->next; } return i; } //返回第一个结点的位置 void* Front_LinkList(LinkList* list) { return list->head->next->data; } //打印链表结点 void Print_LinkList(LinkList* list,PRINTLINKNODE print) { if (list == NULL) return; //辅助指针变量 LinkNode* pCurrent = list->head->next; while (pCurrent != NULL) { print(pCurrent->data); pCurrent = pCurrent->next; } } //释放链表内存 void FreeSpace_LinkList(LinkList* list) { if (list == NULL) return; //辅助指针变量 LinkNode* pCurrent = list->head; while (pCurrent != NULL) { //缓存下一个结点再删 LinkNode* pNext = pCurrent->next; free(pCurrent); pCurrent = pNext; } //释放链表内存 list->size = 0; free(list); }
main文件:
#pragma once //Author:Mr.Rain //Data:2020.2.13 #include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkList.h" //自定义数据类型 typedef struct PERSON { char name[64]; int age; int score; }Person; void MyPrint(void* data) { Person* p = (Person*)data; printf("Name:%s Age:%d Score:%d\n",p->name,p->age,p->score); } void test() { //创建一个链表 LinkList* list = Init_LinkList(); //创建数据 Person p1 = {"aaa",18,100}; Person p2 = {"bbb",19,99}; Person p3 = {"ccc",20,101}; Person p4 = {"ddd",17,97}; Person p5 = {"eee",16,59}; //数据插入链表 Insert_LinkList(list,0,&p1); Insert_LinkList(list,0,&p2); Insert_LinkList(list,0,&p3); Insert_LinkList(list,0,&p4); Insert_LinkList(list,0,&p5); //打印 Print_LinkList(list,MyPrint); //删除3号位置,即p2 RemoveByPos_LinkList(list,3); printf("-------------------------\n"); //打印 Print_LinkList(list,MyPrint); //返回第一个结点 printf("-------------------------\n"); Person* ret = (Person*)Front_LinkList(list); printf("Name:%s Age:%d Score:%d\n",ret->name,ret->age,ret->score); //销毁 FreeSpace_LinkList(list); } int main() { test(); return 0; }
测试:
测试案例1:插入数据
测试结果:插入成功。
测试案例2:删除数据
测试结果:删除成功。
测试案例3:返回第一个结点
测试结果:返回成功
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。