网站平台开通微信支付,百度知道一下首页,网络推广价格,wordpress显示标题和seo标题目录
顺序表
顺序表的优点
顺序表的实现
1.结构体的定义
2.初始化数组 3.插入数据
4.其余接口函数的实现
5.释放内存
顺序表的缺陷
单向链表
单向链表的优点
单向链表的实现
1.链表的定义
2.链表的初始化
3.其余接口函数的实现
5.释放内存
单向链表的缺陷
双…目录
顺序表
顺序表的优点
顺序表的实现
1.结构体的定义
2.初始化数组 3.插入数据
4.其余接口函数的实现
5.释放内存
顺序表的缺陷
单向链表
单向链表的优点
单向链表的实现
1.链表的定义
2.链表的初始化
3.其余接口函数的实现
5.释放内存
单向链表的缺陷
双向链表
双向链表的优点
双向链表的实现
1.双向链表的初始化
2.链表的初始化
3.其余接口函数的实现 4.释放内存 双向链表的缺陷
总结 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...
线性表和链表的物理结构 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的
线性表在物理上存储时通常以数组和链式结构的形式存储。画出它们的物理结构只是为了方便我们理解它们各自的特性。 顺序表 在计算机科学中顺序表是一种常见且重要的数据结构。顾名思义顺序表是一种按照元素在内存中的物理顺序进行存储和访问的数据结构。它可以看作是一段连续的内存空间用于存储相同类型的元素。
顺序表的优点
1.支持随机访问由于顺序表在内存中是连续存储的因此可以通过下标直接访问任何一个元素。这使得顺序表具有高效的随机访问能力时间复杂度为O(1)。
2.有序存储顺序表中的元素按照其在数组中的位置顺序存储因此保持了元素的逻辑顺序。这使得顺序表适用于需要保持元素有序性的场景例如排序、查找等操作。
3.内存紧凑顺序表中的元素在内存中是连续存储的不需要额外的指针来连接各个元素因此可以更好地利用内存空间。这使得顺序表相对于链表等动态数据结构来说具有更小的存储空间和更高的存取效率。
顺序表的实现 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般都是靠数组来进行存储如果在栈上开辟一块空间我们需要指定数组的元素个数如果指定个数过少我们的数据没有办法进行存储如果指定个数过多又会造成资源的浪费。所以我们选择在堆上开辟空间这样我们可以实现一个动态存储的数据表按需分配空间。下面我们来着手实现一个顺序表
1.结构体的定义
因为要实现一个动态增长的版本所以我们要给定一个数组的指针一个记录有效数据个数的变量和一个代表数组容量的变量用以在我们空间不足时候进行扩容操作。
//实现一个顺序表
typedef struct Sequence
{Seqtype* a;int size;int capacity;
}SeqList;
2.初始化数组
这里要传的是结构体的指针因为我们需要改变结构体里面的值需要传址调用
当我们只定义而不进行初始化的时候我们的指针会是野指针size和capacity都会是随机数因此我们要进行一下初始化
void SeqListInit(SeqList* ps)
{assert(ps);ps-a NULL;ps-capacity ps-size 0;
} 3.插入数据
当插入数据的时候我们就要考虑空间够不够的问题了经过思考其实可以发现,size是有效数据的个数,capacity是容量当有效数据的个数刚好等于容量的时候其实就是要扩容的时候。刚开始时我们还没有分配空间所以我们先给定容量为4后期空间不足再调整即可
void SeqListPushBack(SeqList* ps, Seqtype x)
{assert(ps);if (ps-size ps-capacity){//扩容---三目操作符int newcapacity ps-capacity 0 ? ps-capacity * 2 : 4;Seqtype* newsapce (Seqtype*)realloc(ps-a ,sizeof(Seqtype) * newcapacity);if (newsapce NULL) {printf(malloc fail\n);exit(-1);}ps-a newsapce;ps-capacity newcapacity;}ps-a[ps-size] x;
}
注意在分配空间时我们一定要使用realloc而不是malloc。当使用realloc时如果给定一个空指针那他此时就是malloc的功能。realloc与malloc的一个重要的区别就是realloc在堆上申请空间的时候会返回申请到的空间的指针并把原先的内容按字节拷贝到该指针指向的数组中而malloc不会拷贝切记切记
4.其余接口函数的实现
//接口函数
void SeqListPrint(SeqList* ps);
void SeqListInit(SeqList* ps);
void SeqListPushBack(SeqList* ps, Seqtype x);
void SeqListPushFront(SeqList* ps, Seqtype x);
void SeqListPopBack(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPopFront(SeqList* ps);
int SeqListFind(SeqList* ps, Seqtype x);
void SeqListInsert(SeqList* ps, Seqtype x, int pos);
void SeqListCheckCapacity(SeqList* ps);
这里的接口函数太多不再一一赘述只把几个接口函数的思想进行分析
void SeqListPrint(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void SeqListCheckCapacity(SeqList* ps)
{if (ps-size ps-capacity){//扩容int newcapacity ps-capacity 0 ? ps-capacity * 2 : 4;Seqtype* newsapce (Seqtype*)realloc(ps-a, sizeof(Seqtype) * newcapacity);if (newsapce NULL) {printf(malloc fail\n);exit(-1);}ps-a newsapce;ps-capacity newcapacity;}
}void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}void SeqListPushFront(SeqList* ps, Seqtype x)
{assert(ps);SeqListCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end1] ps-a[end];end--;}ps-a[0] x;ps-size;
}void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps-size 0);int begin 1;while (begin ps-size){ps-a[begin -1] ps-a[begin];begin;}ps-size--;
}int SeqListFind(SeqList* ps, Seqtype x)
{assert(ps);//遍历数组int i 0;for ( i 0; i ps-size; i){if (ps-a[i] x){break;}}return i;
}void SeqListInsert(SeqList* ps, Seqtype x, int pos)
{assert(ps);assert(pos ps-size);SeqListCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}我们发现在插入数据的时候不管是头插还是为尾插只要是插入数据都需要进行判断空间是否充足的处理因此我们决定把这个检查空间的功能封装成一个函数方便我们后续的调用这里其实就是代码复用。
void SeqListCheckCapacity(SeqList* ps)
{if (ps-size ps-capacity){//扩容int newcapacity ps-capacity 0 ? ps-capacity * 2 : 4;Seqtype* newsapce (Seqtype*)realloc(ps-a, sizeof(Seqtype) * newcapacity);if (newsapce NULL) {printf(malloc fail\n);exit(-1);}ps-a newsapce;ps-capacity newcapacity;}
}
其实在实现完Insert函数和Erase函数之后我们就会发现头删尾删都可以进行代码复用了我们的代码能够得到极大的简化。大家可以试着实现一下。
5.释放内存
因为我们的数组是开辟在堆上面的所以我们需要在使用完之后释放掉这块内存否则就会造成内存泄漏。
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}
顺序表的缺陷
1.空间不够了需要扩容扩容是有消耗的会产生很多内存碎片。
2.头部/中间位置的插入删除需要挪动数据时间复杂度为O(N)挪动数据也是有消耗的
3.为避免重复扩容一次一般都是按倍数去扩容一般是二倍还可能存在一定的空间浪费 4.增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 单向链表 针对顺序表的缺陷设计出了链表。按需申请空间不用了就释放空间更加合理的使用了空间
头部中间插入删除数据不需要挪动数据。
链表的概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
单向链表的优点
因为链表是根据顺序表的缺陷进行设计的所以链表的优势就在于它里面的数据不是连续存储的而是通过一个个的指针链接起来的。因此不存在会浪费空间造成空间碎片的问题。
1.动态性链表的大小可以动态地进行调整不需要事先预留固定的内存空间。在插入或删除节点时只需要调整指针的指向而不需要移动其他节点。这使得链表适用于频繁进行插入和删除操作的场景。
2.灵活性相比于顺序表链表的结构更加灵活。链表可以根据实际需求设计成单向链表、双向链表或循环链表。单向链表只有一个指针指向下一个节点双向链表则同时具有前向和后向指针而循环链表的尾节点指针指向头节点。根据实际需求我们可以选择合适的链表类型。
3.内存利用率高链表在内存中不要求连续存储因此可以更好地利用内存空间。相比于顺序表链表可以动态地分配内存并且不会产生内存碎片的问题。 单向链表的实现
1.链表的定义
我们可以根据链表的物理结构来设计链表我们首先要定义一个变量来存储数据因为我们还要存储下一个数据的地址所以我们还要定义一个指针。
typedef struct Slist
{SLtype data;struct Slist* next;
}SLTnode;
2.链表的初始化
因为我们不直接把所需空间直接全部初始化完成而是一个一个地存储通过该结构体中指向下一个数据的指针找到下一个数据所以链表的初始化就是先创建一个新节点并让其中的指针指向空防止野指针。
SLTnode* CreatListNode(SLtype x)
{//创建一个新的节点SLTnode* newnode malloc(sizeof(SLtype));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}3.插入数据
插入数据时我们写的是二级指针有些人可能不理解。在此进行说明
为什么要传二级指针
类比int类型的数据我们在传址调用的时候,该变量我们在函数中用的是(int *)指针进行接受。我们如果要传址调用(int *)类型的变量就要用二级指针(int **)来进行接收。
void SLTpushback(SLTnode** pphead, SLtype x)
{SLTnode* newnode CreatListNode(x);if (*pphead NULL){*pphead newnode;}else{//找到尾节点SLTnode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//链接tail-next newnode;}
}
3.其余接口函数的实现
void SLTprint(SLTnode* phead);
void SLTpushback(SLTnode** phead, SLtype x);
void SLTpushfront(SLTnode** phead, SLtype x);
void SLTpopback(SLTnode** phead);
void SLTpopfront(SLTnode** phead);
SLTnode* SLTfind(SLTnode* phead, SLtype x);
void SLTinsert(SLTnode** phead, SLTnode* pos , SLtype x);
void SLTDestory(SLTnode** phead); 其余接口函数的实现不再一一赘述只挑选重点部分进行说明
void SLTprint(SLTnode* phead)
{SLTnode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}void SLTpushback(SLTnode** pphead, SLtype x)
{SLTnode* newnode CreatListNode(x);if (*pphead NULL){*pphead newnode;}else{//找到尾节点SLTnode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//链接tail-next newnode;}}void SLTpushfront(SLTnode** pphead, SLtype x)
{SLTnode* newnode CreatListNode(x);newnode-next *pphead;*pphead newnode;
}void SLTpopback(SLTnode** pphead)
{assert(*pphead ! NULL);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTnode* tail *pphead;SLTnode* previous *pphead;while (tail-next){previous tail;tail tail-next;}free(tail);tail NULL;previous-next NULL;//注意previous是一个指针指向的是尾节点的前一个节点的地址//我们的目的是要把该内存块中指向下一内存的地址给置空}//错误方法/*SLTnode* tail *pphead;while (tail-next){tail tail-next;}free(tail);tail NULL;*/ //这种方式没办法使新链表指向原最后一个数据的指针置空造成野指针
}void SLTpopfront(SLTnode** pphead)
{assert(*pphead ! NULL);SLTnode* next (*pphead)-next;free(*pphead);*pphead NULL;
}
SLTnode* SLTfind(SLTnode* phead, SLtype x)
{assert(phead ! NULL);//遍历链表找到要查找的值SLTnode* tail phead;while (tail-next){if (tail-data x){return tail;}tail tail-next;}return NULL;
}void SLTinsert(SLTnode** phead, SLTnode* pos, SLtype x)
{assert(*phead ! NULL);SLTnode* newnode CreatListNode( x );if (*phead pos){SLTpushfront(phead , x);}else{SLTnode* previous *phead;while (previous-next ! pos){previous previous-next;}previous-next newnode;newnode-next pos;}
}
我们在删除尾部的数据时不能只把最后一个数据的空间free掉还要把它的前一个数据中指向该数据的指针给置成NULL而在单向链表中我们可以轻松取得链表的头和尾但是如果要访问倒数第二个值还需要额外的指针这也是单向链表的一个弊端
5.释放内存
链表的节点是malloc出来的为了防止内存泄漏我们在使用完之后要进行内存释放。
链表的内存释放有点特殊因为它们不是连续存放的开辟了多个节点每个节点都保留着指向下一个节点的指针所以我们要把这些节点全部free掉。
//销毁链表
void SLTDestory(SLTnode** phead)
{SLTnode* cur *phead;while (cur ! NULL){SLTnode* next cur-next;free(cur);cur next;}*phead NULL;
}
单向链表的缺陷
1.不支持随机访问在删除数据时我们发现了每一个数据都要存一个指针去链接后面的数据节点不支持随机访问用下标直接访问第i个【顺序表支持】
2.删除节点需谨慎删除链表中的某个节点时需要修改前一个节点的指针将其指向下一个节点然后释放被删除节点的内存。如果不仔细处理指针的更新可能会导致内存泄漏或者链表断裂。 双向链表 双向链表的优点 双向链表的设计可以看做是单向链表的扩展每个节点除了存储数据外还需要存储前继节点和后继节点的指针。这种设计使得双向链表具有以下优点
1.可以双向遍历由于每个节点都有前继节点和后继节点的指针因此可以从任意一个节点开始顺着前继节点或后继节点进行遍历。这使得双向链表在某些场景下具有比单向链表更高的遍历效率。
2.方便进行插入和删除操作在双向链表中插入或删除节点时只需要修改相邻节点的指针即可不需要像单向链表那样找到前一个节点来修改指针。这使得双向链表在插入和删除操作方面更加方便。 双向链表的实现
1.双向链表的初始化
双向链表基于单向链表只不过是又加入了一个指针我们注意命名规范直接定义即可。
typedef struct ListNode
{DLtype data;struct ListNode* prev;struct ListNode* next;
}DL;2.链表的初始化 初始化时需要注意的是当链表中只有一个数据的时候这时候的两个指针都指向自己。
DL* ListInit(DL* phead)
{DL* newnode (DL*)malloc(sizeof(DL));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-prev newnode;newnode-next newnode;return newnode;
}
3.其余接口函数的实现
DL* ListInit(DL* phead);
void Listprint(DL* phead);
void Listpushfront(DL* phead, DLtype x);
void Listpushback(DL* phead, DLtype x);
void Listpopfront(DL* phead);
void Listpopback(DL* phead);
void ListInsert(DL* pos,DLtype x);
void Listpop(DL* pos);
void Listfind(DL* phead);
这里跟单向链表的逻辑其实相差不多只是过程比较繁琐在这里我就挑选其中的几个进行实现
void Listprint(DL* phead)
{assert(phead);DL* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n);
}void Listpushfront(DL* phead, DLtype x)
{ListInsert(phead-next, x);
}void Listpushback(DL* phead, DLtype x)
{ListInsert(phead, x);
}void ListInsert(DL* pos, DLtype x)
{DL* newnode (DL*)malloc(sizeof(DL));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x;DL* prev pos-prev;if (prev NULL) // 如果pos是头节点{newnode-next pos;pos-prev newnode;}else // 正常情况{prev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;}
}4.释放内存 我们在释放current的内存之前保存下一个空间的地址然后cur一直往后面走free掉经过的空间当cur指向NULL的时候所有的空间都被free完了
void ListFree(DL** phead)
{DL* current phead;while (current ! NULL){DL* next current-next;free(current);current next;}*phead NULL;
}双向链表的缺陷
1.需要更多的存储空间相比于单向链表双向链表需要多存储一个指针因此需要更多的存储空间。这对于需要大量使用链表的应用程序来说可能会成为内存限制的瓶颈。
2.实现较为繁琐相比于单向链表双向链表需要同时操作两个指针很容易把人绕晕。 总结
通过上面的分析我们发现不管是线性表还是单向链表甚至是双向链表都有自己的优缺点我们要根据实际的使用场景来选择要使用哪一种方式来进行存储数据快捷、高效地处理问题。
今天的分享到这里就结束了欢迎讨论交流~
