新人第一次写博客，如有不对的地方，请各位大佬指正！

线性表

线性表有两种储存结构，一种是顺序储存结构，一种是链式储存结构。

线性表的顺序储存结构由数组和表长所构成的结构体组成，定义的代码如下

#define MaxSize 20

tyPEdef struct 

{

int data[MaxSize];

int length;   

}SQList;

这里typedef的作用是给struct SqList 起别名，方便后续创建结构体变量

线性表定义了之后，需要读取元素，读取元素的代码如下F1a;

typedef int status;

status GetElem(SqList L,int i,int *e)

{

    if(L.length==0||i<1||i>L.length)   //当线性表为空表或者i输入的范围有误时，返回0

return 0;

*e=L->data[i-1];      //第i个元素对应数组的下标就是i-1，故将该值赋给*e

return 1; }

进行了线性表的读取元素操作后，还需要进行线性表的插入和删除

线性表的顺序储存结构的插入的代码如下：

Status ListInsert(SqList L,int i,int e)

{

int k;

   if(L.length==;maxSize||i<1||i>L.length)  //表满或者i不在范围内时返回0

return 0;

if(i<=L.length)  //插入元素不在表尾

{

for(k=L.length-1;k>=i-1;k--)

L.data[k+1]=L.data[k];   //将i-1之后的元素全部向后移一位

}

L.data[i-1]=e;

return 1;

}

线性表的顺序储存结构的删除代码如下：

status  ListDelete(SqList L,int i,int *e)

{

int k;

if(L.length=MaxSize||i<1;i>L.length)  //判断数据是否合理

return 0;

*e=L.data[i-1];

if(i<=L.length)   //如果不在表尾

{ for(k=i;k<=L.length-1;k++)  

L.data[k-1]=L.data[k];   //第i个之后的元素向前移动一位 }

L.length--;   //表长减1

return 1;

}

线性表的链式储存结构

线性表的链式储存结构又叫链表，链表由多个结点链接而成，每个结点又有由指针域和数据域组成，链表的定义代码如下：

//先创建结点

typedef  struct Node

{

int data;   //数据域

struct Node* next;   //指针域

}Node;

//定义链表

typedef struct Node* LinkList;

由于链表的每个结点只有一个指针域，所以又叫作单链表，对于线性表来说，总得有个头有个尾，链表也不例外，我们把链表中的第一个结点的储存位置叫作头指针。除最后一个结点外每一个结点的指针都指向下一个结点，而最后一个结点的指针指向空。

单链表的读取代码如下：

Status GetElem(LinkList L,int i,int *e)

{

int j=1;

if(i<1||i>MaxSize)    //当输入的数据不合理时，返回0

return 0;

p=L->next;  //让p指向链表的第一个结点

while(j<i&&p)

{

p=p->next;   //让p指向下一个结点

j++;   

}

if(!p||j>i)    //第i个结点不存在

return 0;

*e=p->data;   //将要读取元素的数据赋值给*e

reuturn 1; }

单链表的插入和删除代码如下：

Status ListInsert(LinkList *L,int i,int e)

{

   LinkList p,s;   //创建两个结点 p，s

  int j=1;

p=*L;   //让p指向链表的头结点

while(p&amp;&j<i)

{

p=p->next;    //使得p指向下一个结点

j++;

}

if(!p||j>i)     //未读取到该节点

return 0;

s=(LinkList)malloc(sizeof(Node));

s->data=e;

s->next=p->next;

p->next=s;

return 1; }

Status ListDelete(LinkList *L,int i,int *e)

{ LinkList p,q;   //创建两个结点

p=*L;    //让p指向链表的头部 

int j=1;    //创建计数器

while(j<i&&p->next)

{

p=p->next;    //让p指向下一个结点

j++; }

if(!p||j>i)    //未找到该结点

return 0;

*e=p->data;    //将要删除的数据赋值给*e

q=p->next;    

p->next=q->next;

free(q);    //释放q

return 1;

}

单链表的整表创建的代码如下：

//头插法   将每一个新的结点插入头结点的后一个位置，这使得每一个新插入的结点会是链表的第一个结点

Status CreatLinkListHead(LinkList *L,int n)

{

LinkList p;

int j;

*L=(LinkList)malloc(sizeof(Node));   //创建头结点

(*L)->next=NULL;      //头结点置空

srand(time(0));   //初始化随机数种子

{

for(j=1;j<=n;j++)

{

p=(LinkList)malloc(sizeof(Node));

p->data=rand()%100+1;

p->next=(*L)->next;

(*L)->next=p;

}

return 1;

}

//尾插法   将每一个新的结点插入链表的尾部，使得每一个新的节点成为链表的最后一个结点

Status CreatLinkListTail(LinkList *L,int n)

{

LinkList p,r;   //创建p，q两个结点

srand(time(0));   //初始化随机数种子

*L=(LinkList)malloc(sizeof(Node));    //创建头结点

r=*L;    //使得r成为链表的头结点

int j;  //创建计数器

for(j=1;j<=n;j++)

{

p=(LinkList)malloc(sizeof(Node));   //创建一个新节点p

p->data=rand()%100+1;    //给p赋值

r->next=p;   //使得p成为r的下一个结点

r=p;    //使得p成为链表的最后一个结点

}

r->next=NULL;   //表示该链表结束

return 1;

} //单链表的整表删除

Status ListDelete(LinkList *L)

{

LinkList p,q;  //创建两个结点p，q

p=(*L)->next;   //使得p指向链表的第一个结点

while(p)

{

q=p->next;   //将下一个结点的值赋给q

free(q);   //释放q

p=q;   //把p的值赋给p

}

(*L)->next=NULL;   //将头结点置空

return 1; }

静态链表

静态链表=数据+游标，静态链表是指用数组描述的链表，数组的元素都是由两个数据域组成，一个叫data，一个叫cur，数据域data用来存放数据元素，也就是通常要处理的数据，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫作游标。

静态链表的数组的第一个元素的cur用来存放备用链表第一个结点的下标，备用链表是指未被使用的数组元素。静态链表的数组的最后一个元素的cur用来存放第一个插入元素的下标，相当于头结点。

静态链表的定义代码如下：

typedef struct

{

int data;   //数据

int cur;   //游标

}component,StaticLinkList[MaxSize];

//静态链表的初始化

Status InITList(StaticLinkList L)

{

int i;

for(i=0;i<MaxSize-1;i++)

{ 

L[i].cur=i+1;//每个元素的游标等于下标加1      }

L[MaxSize-1]=0;      //目前静态链表为空，最后一个元素的cur为0

return 1; }

//静态链表的插入操作，因为静态链表自身没有内存申请的函数，故该函数需要自己定义，该函数的作用是若备用空间链表非空，则返回分配的结点下标，否则返回0

Status Malloc_SSL(StaticLinkList Space)

{

int i=Space[0].cur;   //当前数组第一个元素的cur存的值就是要返回的第一个备用空闲的下标

if(Space[0].cur)      

Space[0].cur=Space[i].cur;   //由于要拿出一个分量来使用了，

return i;                                 //所以我们就得把它的下一个分量用来做备用 }

//静态链表的长度计算

Status ListLength(StaticLinkList Space)

{

int j;

int i=Space[MaxSize-1].cur;    //从头结点开始

while(i)

{

i=Space[i].cur;

j++;   //每读取一次游标，j就加1

}

return j;

}

//静态链表的插入

Status ListInsert(StaticLinkList L,int i,int e)

{

int j,k,l;

k=MaxSize-1;    //链表的最后一个元素的下标

if(i<1||i>ListLength(L))    //输入数据不符合范围   ListLength为链表的长度计算函数

return 0;

j=Malloc_SSL(L);    //向备用空间链表申请内存

if(j)

{

L[j]=e;   //赋值

for(l=1;l<=i-1;l++)

k=L[k].cur;    //找到i之前的元素的位置

L[j].cur=L[k].cur;    //游标更替

L[k].cur=j;

return 1;

}

return 0; }

//静态链表的删除，因为静态链表是由数组链接而成的，故没有内存释放的函数，需要自己定义，该函数用来释放结点，代码如下：

void Free_SSL(StaticLinkList L，int k)

{

Space[k].cur=Space[0].cur;   //把第一个元素cur值赋给要删除的分量cur

Space[0].cur=k;   //把要删除的分量下标赋值给第一个元素的cur }

//静态链表的删除

Status  ListDelete(StaticLinkList L,int i)

{

int j,k;

k=MaxSize-1;    

if(i<1||i>ListLength(L))     //输出的数据不合理的时候返回0

return 0;

for(k=1;k<=i-1k++)

k=L[k].cur;   //找到i之前被删除元素的下标

L[k].cur=L[j].cur;

Free_SSL(L,j);   //

return 1;

}

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表

循环链表的函数大多与单链表一致，只是多了个尾指针，当要将两个循环链表合并成一个表时，有了尾指针就非常简单了

/*   rearA为A的尾结点   rearB为B的尾结点   

p=rearA->next   //p保存链表A的头结点

rearA->next=rearB->next->next;   //使得A链表的尾结点指向B链表的第一个结点

q=rearB->next    //q保存链表B的头结点

rearB->next=p;

free(q);

*/

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域，所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱

//双向链表的定义

typedef struct DullNode 

{

int data;   //数据域

struct DullNode *next;   //后继指针

struct DullNode *PRior;   //前驱指针 }DullNode,*DuLinkList;

//双向链表的插入操作的部分代码如下

//   p   s   p->next

s->prior=p;    //把p的值赋给s的前驱

s->next=p->next;   //把p->next的值赋给s的后继

p->next->prior=s;   //把s的值赋给p->next的前驱     

p->next=s;   //把s赋给p的后继

//双向链表的删除操作

//   p->prior     p     p->next

p->prior->next=p->next;   把p->next的值赋给p->prior的后继

p->next->prior=p->prior;    把p->prior的值赋给p->next的前驱

free(p);