有小广告的网站,金华网站制作推广,福建石狮有做网站的没,网站建设环境分析1.线性表
我们在C语言当中学过数组#xff0c;其实呢#xff0c;数组可以实现线性表#xff0c;线性表理解上类似于数组#xff0c;那么什么是线性表呢#xff1f;线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构#xff0c;常见…
1.线性表
我们在C语言当中学过数组其实呢数组可以实现线性表线性表理解上类似于数组那么什么是线性表呢线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。下面我们就将介绍顺序表和链表。 2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。一般情况下顺序表可以分为静态顺序表和动态顺序表
静态顺序表使用定长数组存储元素。动态顺序表使用动态开辟的数组存储。
静态数据表呢其实就是给一个数组我们对这个数组进行增删查改只不过数据结构的意思把这一系列的操作封装了起来我们在使用的使用直接调用相应的接口。顺序表的静态存储相对简单我们不在此实现。
动态顺序表的意思就是可以根据需要及时的进行扩容从而满足要求我们之前实现过通讯录其实这里和通讯录的原理是类似的接下来我们实现相应的接口。
typedef struct SeqList
{SLDataType *a;//指向这块空间的起始地址int size;//存放的有效数据int capacity;//容量
}SL ;//通过typedef将它重命名为SL方便我们以后使用
//初始化顺序表
void SeqListInit(SL* ps);
//扩容
void SeqListCheck(SL* ps);
//打印
void SeqListPrint(SL* ps);
// 尾插尾删
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
//头插头删
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);
//任意位置插入删除
void SeqListInsert(SL* ps, size_t pos, SLDataType x);
void SeqListErase(SL* psl, size_t pos);
这是顺序表整个工程文件的头文件包含了结构体的声明和各种接口的声明。结构体的定义中我们定义了一个指向我们目标空间的起始地址这是用来指向我们所开辟的空间的当然能不能定义一个数组呢也是可以但是这样就变成了静态顺序表的实现了。size的定义是为了实时的显示空间内的有效数据大小当然一个空间是不是有它的大小那capacity就是它的容量。接下来将对任意位置插入删除的函数进行实现。
//任意位置插入
void SeqListInsert(SL* ps, size_t pos, SLDataType x)
{assert(ps);//如果psNULL则终止程序if (ps-size ps-capacity)//扩容{SeqListCheck(ps);}int end ps-size - 1;while (pos end){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
} 任意位置的插入实际上是把数据整体往后挪动最终把目标位置空出来把目标数据放进去注意这是从后往前挪我们的头插也是这样的道理事实上头插就是一种特殊的任意位置插入因此任意位置插入实现之后可以在头插直接调用该接口就可实现。
//任意位置删除
void SeqListErase(SL* ps, size_t pos)
{assert(ps);for (int start pos; start ps-size - 1; start){ps-a[start] ps-a[start 1];}ps-size--;
} 任意位置的删除实际上就是把后面的数据逐个往前挪把目标位置的数据覆盖掉便达到了删除的目的了注意这是从前往后挪头删也是这样的道理头删可以直接调用该接口来实现头删。 补充知识 realloc增容是一般取2倍为什么呢因为如果增的越多的话有可能空间的浪费就越多如果增的越少虽然空间越省但是如果我们存放的数据相对增容是比较大的这就面临着频繁增容的情况这消耗代价也是蛮大的所以我们取折中的方法增2倍。 3.链表
上面我们介绍了顺序表但是大家敏锐的发现了问题没有我们在任意位置插入的时候就加入在头部插入时间复杂度是多少是不是ON而且它在扩容的时候面临着扩的过大扩的过小的问题那有没有一种结构让我们可以不挪动其它数据直接插入而且需要多少我们申请多少当然也是存在这样的一种数据结构的这就是我们的链表。
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 注意
链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续
一个数据结构我们一般对它进行的操作就是进行增删查改所以下面将对链表的一些接口进行实现。主要涉及以下接口
typedef int SListDataType;
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SListNode;// 动态申请一个结点
SListNode* BuySListNode(SListDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SListDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SListDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SListDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
// 因为单链表只能找到它后面的节点找不到它前面的节点双链表可以
void SListInsertAfter(SListNode* pos, SListDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
// 删除了之后pos后面位置的内容上哪找会造成内存泄露
void SListEraseAfter(SListNode* pos);
这是链表整个工程文件的头文件包含了结构体的声明和各种接口的声明。结构体的定义中我们定义了节点的数据以及节点所存放下一个节点的地址这个地址就是用来指向下一个节点的从而实现链表的逻辑连续。在链表接口声明中下面将进行一一的实现。
// 动态申请一个结点
SListNode* BuySListNode(SListDataType x)
{SListNode* pList (SListNode*)malloc(sizeof(SListNode));if (pList NULL){printf(开辟新节点失败);exit(-1);}pList-data x;pList-next NULL;//这点很重要如果不置为NULL极有可能越界访问return pList;
}
上面所介绍的顺序表由于在通讯录当中已经介绍了大部分内容所以只将部分接口进行实现链表是一个新的知识点因此进行详细的介绍前面我们已经了解单链表它的一种形式所以我们在开辟一个新节点时要注意pList-next NULL不置为空系统会随机生成一个地址那如果我们不小心调用了就会造成越界访问。 补充知识 链表在堆区开辟空间时有可能缠绕在一起为什么呢因为堆区虽然向上生长的但是存在下面的空间被释放掉之后开辟在下面了。 // 单链表尾插
void SListPushBack(SListNode** pplist, SListDataType x)
{if (*pplist NULL)//分情况如果这种情况没有下面cur-next就会导致对NULL访问的错误{*pplist BuySListNode(x);}else{SListNode* cur *pplist;while (cur-next ! NULL){cur cur-next;}cur-next BuySListNode(x);//这里通过cur可以改外部变量的值需要注意一下}
} 尾插整体的思路就是我们应该首先找到尾当然这里就分了情况如果一开始就是尾直接插入数据不是的话我们就需要遍历整个链表找到尾然后将数据插入遍历唯一需要注意的就是cur cur-next这是链表的关键所以单链表的使用就两点一是头指针的建立与使用二是节点中存放着下一个节点的地址。
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{if (*pplist NULL)//分情况如果这种情况没有下面cur-next就会导致对NULL访问的错误{return;//空就是没有要删的直接返回}else{SListNode* cur *pplist;SListNode* tail *pplist;//设置该指针变量唯一目的就是为了是新的尾节点的next置成NULL防止成为野指针while (cur-next ! NULL){tail cur;//最后一次执行的时候会把cur之前那个节点即最终结果的尾赋给tailcur cur-next;}free(cur);tail-next NULL;//别忘记置成NULL防止对NULL造成访问}
}
尾删的整体思路和尾插是一样的唯一的区别就在于多定义了一个tail指针变量设置该指针变量唯一目的就是为了是新的尾节点的next置成NULL防止成为野指针。
// 单链表的头插
void SListPushFront(SListNode** pplist, SListDataType x)
{SListNode* NewNode BuySListNode(x);NewNode-next *pplist;*pplist NewNode;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{if (*pplist NULL)//分情况如果这种情况没有下面cur-next就会导致对NULL访问的错误{return;//空就是没有要删的直接返回}else{SListNode* cur *pplist;*pplist (*pplist)-next;free(cur);cur NULL;//别忘记置成NULL防止成为野指针}
} 头插相对比较简单把我们新的节点中存放原先第一个节点的地址然后把头指针的地址链接到我们所建立的新的节点上时刻应该注意到链表的数据别丢失。
头删建立一个临时的指针变量cur是一个关键如果不建立第一个节点已释放找不到了之后的数据把头指针指向第二个节点那第一个节点的空间又无法释放因此建立一个临时指针变量去存储其中一个地址两个方法都可以。
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pos, SListDataType x)
{if (*pos NULL){SListPushBack(pos, x);//这就是该接口也使用二级指针的原因如果不使用把pos传过去} //最终改变不了test.c中的pList只能改变pos的地址因为一级指针pos只能改变pList所指向的空间内容else //1.要改变量内容传变量地址 { //2.要改变变量地址需要传变量地址的地址SListNode* next BuySListNode(x);next-next (*pos)-next;(*pos)-next next;}
}
任意位置之后插入的原理其实和头删是一样的就是要注意临时指针变量的建立防止内存泄漏和野指针的问题需要把插入位置的两头连上。唯一需要注意的是如果没有*posNULL的情况就不需要传二级指针其实*posNULL就是尾插可以直接调用尾插接口就可以了。
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{if (pos NULL){return;}else if (pos-next NULL){printf(你所要删除的位置之后没有数据\n);return;}else{SListNode* next pos-next;pos-next next-next;free(next);}
}
pos位置之后的删除也是同样的道理 需要注意就是说我们只能删除指定位置的后一个数据插入也一样因为我们都不知道这个位置的前一个节点的地址这不是双链表因此只能删除和插入pos之后的节点。
4.顺序表与链表区别
顺序表可动态增长的数组数据在数组中存储时必须是连续的。优点可以随机访问缓存命中率比较高。缺点中间或者头部的插入删除很慢需要挪动数据时间复杂度是O(N)。空间不够时增容会有一定消耗和空间浪费。
链表逻辑上连续物理上不一定连续。优点头部插入只需修改指针指向即可不需要挪动数据。缺点缓存命中率比较低不支持随机访问。 补充知识 顺序表的缓存命中率比较高为什么呢因为顺序表的数据在物理上是连续的因此cpu读取数据会从缓冲器上拿第一次拿的时候缓冲器没有我们在内存中存储的数据因此缓冲器会去内存里拿拿的时候会连续拿好几个数据当cpu读取数据的时候就会先在缓冲器上拿这样就会拿到数据这就是缓冲命中率。 而链表物理上不是连续的因此缓冲器拿的时候拿不到连续的我们自己的数据因此导致cpu每次在缓冲器上都拿不到数据都会是缓冲器去内存上加载再cpu在缓冲器上拿而且也会导致缓冲器的污染因为链表可能这一个那一个缓冲器加载时候会把旁边不是它的数据也会捎带拿着就会导致不是我们想要的数据也被加载到缓冲器。
