数据结构与算法学习(二)

时间:2022-04-07 10:20:08

线性表的链式存储结构:除了存储数据元素信息外,还要存储它的后继元素的存储地址(指针)即数据域和指针域,两部分为存储映像即结点(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).