域名空间网站,营销手机网站制作,网页设计字号设置代码,版式设计模板顺序表与链表 线性表顺序表链表链表的概念链表的分类不带头单向非循环链表的实现带头双向循环链表的实现顺序表与链表的区别 线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。
常见的线性结构#xff1a;顺序表、链表、栈、队… 顺序表与链表 线性表顺序表链表链表的概念链表的分类不带头单向非循环链表的实现带头双向循环链表的实现顺序表与链表的区别 线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。
常见的线性结构顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性结构也就是说是连续的一条直线但是在物理结构上并不一定是连续的线性表在物理存储时通常以数组和链式结构的形式存储。
顺序表 顺序表从开始连续存储size个 顺序表时用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组数据存储在数组上完成数组的增删查改。
顺序表一般分为 1.静态顺序表 缺点保存数据的数组较小不够使用较大浪费 //静态顺序表
typedef int SLDateType;
#define N 10
struct Seqlist
{SLDateType a[N];int size;
};2.动态顺序表 可以实现按需申请 此时如果free出现问题原因可能是指针为野指针指针未从初始地址释放或者指针越界
//动态顺序表
typedef int SLDateType;
struct Seqlist
{SLDateType* a;int size;int capacity;
};使用顺序表完成增删查改
seqlist.h文件
#define _CRT_SECURE_NO_WARNINGS 1
//头文件
#includestdio.h
#includestdlib.h
#includeassert.h静态顺序表
//typedef int SLDateType;
//#define N 10
//struct Seqlist
//{
// SLDateType a[N];
// int size;
//};//动态顺序表
//定义类型
typedef int SLDataType;
//设置初始容量
#define INIT_CAPACITY 5typedef struct Seqlist
{SLDataType* a;//有效数据个数int size;//容量int capacity;
}SL;//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//增
//后增
void SLPushBack(SL* ps, SLDataType X);
//前增
void SLPushFront(SL* ps, SLDataType X);
//插入
void SLInsert(SL* ps, int pos, SLDataType X);
//删
//后删
void SLPopBack(SL* ps);
//前删
void SLPopFront(SL* ps);
//中间删除
void SLErase(SL* ps, int pos);
//查
int SLFind(SL* ps, SLDataType X);
//改
int SLChange(SL* ps, SLDataType X,SLDataType Y);
//扩容
void SLCheckCapseqlist.c文件
#includeseqlist.h//初始化顺序表
void SLInit(SL* ps)
{assert(ps-a);ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps-a NULL){perror(Malloc fail);}ps-size 0;ps-capacity INIT_CAPACITY;
}//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps-a);free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}//打印顺序表
void SLPrint(SL* ps)
{assert(ps-a);int i 0;for (i 0; i ps-size; i){printf(%d ,ps-a[i]);}printf(\n);
}//后增
void SLPushBack(SL* ps, SLDataType X)
{assert(ps-a);SLCheckCapacity(ps);ps-a[ps-size] X;ps-size;
}//后删
void SLPopBack(SL* ps)
{assert(ps-a);assert(ps-size0);/*if (ps-size 0){return;}*/ps-size--;
}//前增
void SLPushFront(SL* ps, SLDataType X)
{assert(ps-a);SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-a[end1] ps-a[end];end--;}ps-a[0] X;ps-size;
}//前删
void SLPopFront(SL* ps)
{assert(ps-a);int begin 0;while (begin 0 begin ps-size){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
}//中间插入
void SLInsert(SL* ps, int pos, SLDataType X)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] X;ps-size;
}//中间删除
void SLErase(SL* ps, int pos)
{assert(ps-a);assert(pos 0 pos ps-size);int begin pos;while (begin pos begin ps-size){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
}//查找
int SLFind(SL* ps, SLDataType X)
{assert(ps-a);int i 0;for (i 0; i ps-size; i){if (ps-a[i] X){return i;}}return -1;
}//改
int SLChange(SL* ps, SLDataType X , SLDataType Y)
{assert(ps-a);int i 0;for (i 0; i ps-size; i){if (ps-a[i] X){ps-a[i] Y;return 0;}}return -1;
}//扩容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){SLDataType* p (SLDataType*)realloc((void*)ps-a, ps-capacity * sizeof(SLDataType)*2);if (p NULL){printf(Realloc fail);return;}ps-a p;p NULL;ps-capacity * 2;}
}main.c文件
#includeseqlist.h//测试顺序表
void TestSeqlist1()
{//定义顺序表SL s;//初始化顺序表SLInit(s);//后增SLPushBack(s,1);SLPushBack(s, 2);SLPushBack(s, 3);SLPushBack(s, 4);//后删SLPopBack(s);//打印SLPrint(s);//前增SLPushFront(s, 10);SLPushFront(s, 20);SLPushFront(s, 40);//打印SLPrint(s);//前删SLPopFront(s);//打印SLPrint(s);//中间插入SLInsert(s, 1, 6);//打印SLPrint(s);//中间删除SLErase(s, 2);//打印SLPrint(s);//改SLChange(s, 2, 9);//打印SLPrint(s);//销毁顺序表SLDestroy(s);
}int main(void)
{//测试顺序表TestSeqlist1();return 0;
}链表
了解完顺序表之后可以明显发现顺序的缺点
中间与头部的插入删除时间复杂度为O(N)增容需要申请空间拷贝数据释放旧空间会有不小的消耗增容一般是呈2倍增长会有一定的空间浪费
链表的概念
链表是一种物理存储的结构上非连续非顺序的存储结构数据元素的逻辑是通过链表中的指针链接次序实现的
注意 1.链式结构在逻辑上是连续的但是在物理上不一定连续。 2.现实中的结点一边拿都是从堆上申请出来的 3.从堆上申请的空间是按照一定的策略来分配的俩次申请的空间可能连续也可能不连续
链表的分类
链表的分类大致分为 1.单向或者双向
2.带头或者不带头
3.循环或者非循环 其中最常用的是不带头单向非循环链表与带头双向循环链表 不带头单向非循环链表
结构简单一般不会单独用来存数据实际中更多是作为其他数据结构的子结构如哈希桶图的邻接表等等
带头双向循环链表
结构最复杂一般用来单独存储数据实际中使用的链表数据结构都是双向循环链表
不带头单向非循环链表的实现
slist.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDatatype;typedef struct SLinklistNode
{SLTDatatype date;struct SLinklistNode* next;
}SLTNode;//增加结点
SLTNode* SLTNewNode(SLTDatatype X);//打印
void SLTPrintf(SLTNode* phead);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X);
//头删
void SLTPopFront(SLTNode** pphead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype X);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X);
//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos ,SLTDatatype X);
//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);
//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X);
//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//销毁
void SLTDestory(SLTNode** pphead);
slist.c文件
#includeslist.h//打印
void SLTPrintf(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-date);cur cur-next;}printf(NULL\n);
}//新增加一个结点
SLTNode* SLTNewNode( SLTDatatype X)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-date X;newnode-next NULL;return newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype X)
{//动态增加一个结点SLTNode* newnode SLTNewNode(X);newnode-next *pphead;*pphead newnode;
}//头删
void SLTPopFront(SLTNode** pphead)
{//温柔/*if (*pphead NULL){return;}*///断言assert(*pphead);SLTNode* first *pphead;*pphead first-next;free(first);first NULL;
}//尾删
void SLTPopBack(SLTNode** pphead)
{if (*pphead NULL){return;}assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}//尾增
void SLTPushBack(SLTNode** pphead, SLTDatatype X)
{//新增一个结点SLTNode* newnode SLTNewNode(X);SLTNode* tail *pphead;if (*pphead NULL){*pphead newnode;}else{while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}//查找
SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X)
{SLTNode* cur pphead;while (cur){if (cur-date X){return cur;}cur cur-next;}return NULL;
}//前插
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{assert(pos);assert(pphead);if (*pphead pos){SLTPushFront(pphead, X);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode SLTNewNode(X);prev-next newnode;newnode-next pos;}
}//pos位置删
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPopFront(pphead);}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);
}//后插
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X)
{assert(pos);SLTNode* newnode SLTNewNode(X);newnode-next pos-next;pos-next newnode;
}//后删
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}
//销毁
void SLTDestory(SLTNode** pphead)
{SLTNode* cur *pphead;while(cur){SLTNode* tmp cur-NEXT;free(cur);cur tmp;}*pphead NULL;
}带头双向循环链表的实现
Dlist.h文件
#define _CRT_SECURE_NO_WARNINGS 1
//带头双向循环链表的增删查改
#includestdio.h
#includestdlib.h
#includeassert.h//定义类型
typedef int LTDataType;//定义结构体
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;//创建一个返回链表的头结点哨兵
ListNode* ListCreate();//双向链表的销毁
void ListDestory(ListNode* phead);//双向链表的打印
void ListPrintf(ListNode* phead);//创造一个newnode
ListNode* ListNewNode(LTDataType x);//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x);//双向链表的尾删
void ListPopBack(ListNode* phead);//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x);//双向链表的头删
void ListPopFront(ListNode* phead);//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x);//双向链表在pos前插入
void ListInsert(ListNode* phead, LTDataType x);//双向链表在pos删除
void ListErase(ListNode* pos);Dlist.c文件
#includeDList.h
//创建一个返回链表的头结点哨兵
ListNode* ListCreate()
{ListNode* phead ListNewNode(-1);phead-next phead;phead-prev phead;return phead;
}//双向链表的销毁(需自行释放哨兵头)
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){ListNode* tail cur;cur cur-next;free(tail);tail NULL;}
}//双向链表的打印
void ListPrintf(ListNode* phead)
{assert(phead);ListNode* cur phead-next;printf(-NULL-);while (cur ! phead){printf(%d-, cur-data);cur cur-next;}printf(\n);
}//创造一个newnode
ListNode* ListNewNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}//双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode ListNewNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}//双向链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead-next ! phead);ListNode* tail phead-prev;phead-prev tail-prev;tail-prev-next phead;free(tail);tail NULL;
}//双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode ListNewNode(x);newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}//双向链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead-next ! phead);ListNode* first phead-next;phead-next first-next;first-next-prev phead;free(first);first NULL;
}//双向链表的查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//双向链表在pos前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode ListNewNode(x);ListNode* front pos-prev;newnode-prev front;newnode-next pos;front-next newnode;pos-prev newnode;
}//双向链表在pos删除(自行释放指针)
void ListErase(ListNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);
}顺序表与链表的区别
不同点顺序表链表存储空间上物理上连续逻辑上连续物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要移动元素效率低O(N)只需要修改指针指向插入动态顺序表空间不够需要扩容没有容量的概念应用场景元素高效访问频繁访问任意位置插入和删除频繁缓存利用率高低
