数据结构与算法学习（二）
线性表的链式存储结构：除了存储数据元素信息外，还要存储它的后继元素的存储地址（指针）即数据域和指针域，两部分为存储映像即结点(node),每个结点只包含一个指针域，则为单链表
把结点的第一个存储位置叫做头指针，最后一个结点指针为空NULL.
头指针和头结点的异同：
空链表：
头结点的数据域一般是空的，但是也可以存放链表的长度。头结点的指针指向第一个结点的地址。
在C语言中可以用结构指针表示单链表：
typedef struct Node
{Elemtype data;//数据域
struct *Node next;//指针域
}Node；
typedef struct *Node LinkList;
p是指向ai的指针,p->data是数据域，p->next是指针域.
若p->data=ai;则p->next->data=ai+1;
C语言编写GetElem函数：
status GetELem(List L,i,*e)
{int i,j;
LinkList p;
p=L=>next;
j=1;
while(p&&j<i)
{p=p->next;
j++;
}
if(!p||j>i)
{return ERROR;}
*e=p->data;
return OK;
}
这个算法的时间复杂度，在最好的情况，i为第一个元素，复杂度为o(1),在最坏的情况下，i=n则需要遍历n-1，所以复杂度为o(n)，平均情况也为o(n).
单链表没有定义表长，不知道循环次数，不方便用for,采用工作指针后移的思想;
单链表的插入问题，要注意必须先给插入元素的下个地址指针赋值，在给指向自己的指针赋值，顺序不能调换，否则会造成死循环，如下：
需要将结点s插入ai到ai+1之间，指向ai的指针为p,
则，s->next=p->next;
p-next=s;
这两条指令顺序不能弄反.
单链表的插入操作
status ListInsert(LinkList *L,int i, Elemtype e)
{int j;Linklist s;
LinkList p=*L;
j=1;
while(p&&j<i)
{p=p->next;
j++;}
if(!p||j>i)
{return ERROR;}
s=(LinkList)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
单链表的删除操作：
status ListDetele(LinkList *L,int i,Elemtype *e)
{int j; LinkList q,p;
p=*L;
j=1;
while(p->next&&j<i)
{p=p->next;
j++;}
if(!p->next||j>i)
{return ERROR;}
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
效率PK：在插入和删除操作频繁的算法中，链式结构比顺序结构复杂度低。一次则一样为o(n).
例如：在第i个元素插入或删除10个元素，顺序结构每次操作都是o(n)，而链式在第一次操作为 o(n)，以后每次都是o(1).
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
