从今天开始我们正式进入数据结构的学习，开始之前我们先思考几个问题。
生活中遇到哪些线性表的例子？
如何通过程序实现线性表？
线性表结构有哪些基本操作？
线性表结构在软件方面有哪些应用？
看着上面的表情包是不是有种熟悉的味道，没错，这就是我们生活中最常见的线性表结构——糖葫芦。根据它的结构特性我们给出相应的定义，一个线性表，由有限个具有相同性质的元素构成，结构上要求，非表头和表尾元素有且只有一个前驱和后继。对于表头和表尾元素，如果是没有环的线性表，则表头元素没有前驱，表尾元素没有后继。如果有环则均存在前驱和后继元素，如下图所示。
线性表的实现线性表的实现，根据表元素存储方式的不同，可以分为两种。一种是线性表中的所有元素占用一片连续的存储空间，我们称之为顺序存储，一种是表中的所有元素不需要占据连续的空间，当表中插入新的元素的时候，额外申请元素所需要的空间，插入到线性表中即可，我们称之为链式存储，下面我们通过程序来依次实现以上两种存储方式。
顺序表的实现（假设顺序表起始地址为b，每个元素占据内存为l）
根据上图所示，显然我们可以使用数组来表示一个顺序表结构，具体如下所示：
//使用数组来表示顺序表结构#defineMAXSIZE//顺序表最大长度typedefintElemTypetypedefstruct{ElemTypedata[MAXSIZE];intlen//顺序表长度}SqList;
使用数组来表示顺序存储结构有一个问题，就是在程序的执行过程中其能表示的元素的个数最大值是不可修改的，如果顺序表元素较少，则存在存储空间的浪费，如果顺序表元素比较多，则有可能导致顺序表的存储空间不够。基于这个问题，我们可以使用动态分配来实现顺序表结构，当内存空间不够用的时候可以重新分配一块更大的内存，并把当前数据拷贝到新的内存当中，具体操作请看后面的基本操作。
//通过动态分配内存来实现顺序表结构#defineINIT_SIZE#defineINCREMENT20typedefintElemTypetypedefstruct{ElemType*data;intlen;//顺序表长intcap;//顺序表最大容量}SqList;
链式表(链表)实现
链式表相比于顺序表，不要求整个表分配在一块连续的存储空间，这对于占用内存比较大的数据来说比较方便，具体实现如下所示。
//使用链表实现线性表结构typedefintElemTypetypedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;
假设L是LinkList类型的变量，为了操作方便我们通常使用该变量的指针域作为链表的第一个节点，L称之为链表的头节点，对链表判空直接看L-next==NULL?empty:nonempty即可。
线性表的基本操作数组实现的顺序表
//初始化、插入、更新、删除操作#defineMAXSIZE//顺序表最大长度typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];intlen//顺序表长度}SqList;boolinit_sq_1(SqList*sq){if(NULL==sq){returnfalse;}sq-len=0;returntrue;}//init_sq_1boolinsert_sq_1(SqList*sq,intpos,ElemTypedata){//判断顺序表是否为空，顺序表是否已满，pos是否合法if(sq==NULL
pos0
possq-len
sq-len==MAXSIZE){returnfalse;}inti=sq-len;for(;ipos;i--){sq-data=sq-data[i-1];}sq-data[pos]=data;sq-len++;returntrue;}//insert_sq_1boolupdate_sq_1(SqList*sq,intpos,ElemTypedata){//判断顺序表是否为空，pos是否合法if(NULL==sq
pos0
possq-len
pos==MAXSIZE){returnfalse;}//pos==sq-len直接做插入操作if(pos==sq-len){returninsert_sq_1(sq,pos,data);}sq-data[pos]=data;returntrue;}//update_sq_1booldelete_sq_1(SqList*sq,intpos,ElemType*value){//判断顺序表是否为空，pos是否合法if(NULL==sq
pos0
pos=sq-len){returnfalse;}inti=pos;*value=sq-data[pos];for(;isq-len-1;i++){sq-data=sq-data[i+1];}sq-len--;returntrue;}//delete_sq_1
通过动态分配内存来实现的顺序表结构
//初始化、插入、查找、删除操作#defineINIT_SIZE#defineINCREMENT20typedefintElemType;typedefstruct{ElemType*data;intlen;//顺序表长intcap;//顺序表最大容量}SqList;boolinit_sq_2(SqList*sq){if(NULL==sq){returnfalse;}sq-data=(ElemType*)malloc(sizeof(ElemType)*INIT_SIZE);if(NULL==sq-data){returnfalse;}sq-len=0;sq-cap=INIT_SIZE;returntrue;}//init_sq_2boolinsert_sq_2(SqList*sq,intpos,ElemTypedata){//判断顺序表是否为空，pos是否合法if(NULL==sq
pos0
possq-len){returnfalse;}//当前动态数组已经满了，插入新元素需要重新申请一块内存inti=0;ElemType*newData=NULL,*tmpData=NULL;if(sq-len==sq-cap){tmpData=(ElemType*)malloc(sizeof(ElemType)*(sq-cap+INCREMENT));if(tmpData==NULL){returnfalse;}newData=tmpData;for(i=0;isq-len;i++){*tmpData++=sq-data;}free(sq-data);sq-data=newData;sq-cap+=INCREMENT;}//插入新元素到中间位置for(i=sq-len;ipos;i--){sq-data=sq-data[i-1];}sq-data[pos]=data;sq-len++;returntrue;}//insert_sq_2boolupdate_sq_2(SqList*sq,intpos,ElemTypevalue){//判断顺序表是否为空，pos是否合法if(NULL==sq
pos0
pos=sq-len){returnfalse;}sq-data[pos]=value;returntrue;}//update_sq_2booldelete_sq_2(SqList*sq,intpos,ElemType*value){//判断顺序表是否为空，pos是否合法if(NULL==sq
pos0
pos=sq-len){returnfalse;}inti=pos;*value=sq-data[pos];for(i=pos;isq-len;i++){sq-data=sq-data[i+1];}sq-len--;returntrue;}
使用链表实现的线性表结构
//初始化、插入、查找、删除操作typedefstructLNode{//为了操作方便，头节点的data用于记录链表的长度ElemTypedata;structLNode*next;}LNode,*LinkList;boolinit_link_list(LinkListL){if(NULL==L){returnfalse;}L-data=0;L-next=NULL;returntrue;}//init_link_listboolinsert_link_list(LinkListL,intpos,ElemTypedata){//判断链表是否为空，pos是否合法if(L==NULL
pos0
posL-data){returnfalse;}inti=0;LNode*tmpNode=L-next;LNode*newNode=NULL,*prior=L;//创建新节点newNode=(LNode*)malloc(sizeof(LNode));if(newNode==NULL){returnfalse;}newNode-data=data;newNode-next=NULL;//确定插入节点位置while(i++postmpNode!=NULL){prior=tmpNode;tmpNode=tmpNode-next;}prior-next=newNode;newNode-next=tmpNode;L-data++;returntrue;}//insert_link_listboolupdate_link_list(LinkListL,intpos,ElemTypedata){//判断链表是否为空，pos是否合法if(L==NULL
pos0
pos=L-data){returnfalse;}inti=0;LNode*tmpNode=L-next;while(i++pos){tmpNode=tmpNode-next;}tmpNode-data=data;returntrue;}//update_link_listbooldelete_link_list(LinkListL,intpos,ElemType*data){//判断链表是否为空，pos是否合法if(L==NULL
pos0
pos=L-data){returnfalse;}inti=0;LNode*tmpNode=L-next;LNode*prior=L;while(i++postmpNode!=NULL){prior=tmpNode;tmpNode=tmpNode-next;}*data=tmpNode-data;prior-next=tmpNode-next;free(tmpNode);L-data--;returntrue;}//delete_link_list应用
设将n(n1)个整数存放到一维数组中，设计一个再时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0pn)个位置，即将R中的数据由(X0,X1,X2...Xn)变换为(Xp,X(p+1),...,X0,X1,...,X(p-1))。
解析图示
从下图我们可以看出，要实现一维数组的左移操作，我们可以先将将整个数组进行reverse，然后将数组分成两部分分别进行元素reverse，第一部分为前n-p个元素，第二部分为后p个元素，reverse结束最终实现数组左移操作。
示例代码
boolShiftLeft(SqList*SQ,intleft,intright){inttmpData=0;if(leftright
left0
rightSQ-len-1){printf("left%dorright%dinvalid\n",left,right);returnfalse;}//reversetablewhile(leftright){tmpData=SQ-data[left];SQ-data[left]=SQ-data[right];SQ-data[right]=tmpData;left++;right--;}returntrue;}
判断链表是否存在环
解析
我们定义两个指针，一个fast指针，一个low指针。两个指针初始位置都是链表的头节点，分别移动这两个指针，fast指针每次移动两个位置，low指针每次移动一个位置。下图中我们可以看到，如果链表存在环，fast指针和low指针必然相遇。如果链表没有环，则fast必然先指向NULL。
示例代码
boolCircularLinkedList(LinkListL){if(L==NULL){//链表为空returnfalse;}//初始位置设为头节点LinkListslow=L-next;LinkListfast=L-next;while(slow!=NULLfast-next!=NULL){slow=slow-next;fast=fast-next-next;if(slow==fast){returntrue;}}//说明slow==NULL
fast-next==NULL//没有环returnfalse;}预览时标签不可点收录于话题#个上一篇下一篇