1.总结
说到数据结构,第一个想到的就是链表,因为后面所以的数据结构都是可以通过链表的形式实现。
2.时间复杂度
说到算法,第一个想到的就是效率问题,让我们简单看下时间复杂度:如果一个算法用常数时间(O(1))将问题的大小消减为其一部分(通常是二分之一),那木该算法就是O(logN),如果使用常数时间只是把问题减少一个常数(如将问题减少1),那木这种算法就是O(N)。
3.单链表(为了方便分析,链表都是带有头结点数据域不存放值)
<a href="https://s5.51cto.com/wyfs02/M02/05/FD/wKiom1mvohXRSvD3AAAPrUcfeYM026.png" target="_blank"></a>
代码实现如下(每个函数传入指针默认不是NULL):
<code>node.h</code>
<code>#ifndef _LIST_</code>
<code>#define _LIST_</code>
<code>typedef</code> <code>struct</code> <code>node{</code>
<code> </code><code>int</code> <code>Data;</code>
<code> </code><code>struct</code> <code>node *Next;</code>
<code>}*Pnode,Node;</code>
<code>int</code> <code>IsEmpty(Pnode L);</code>
<code>int</code> <code>IsLast(Pnode L);</code>
<code>Pnode Find(</code><code>int</code> <code>X,Pnode L);</code>
<code>void</code> <code>Delete(</code><code>int</code> <code>X,Pnode L);</code>
<code>Pnode FindPrevious(</code><code>int</code> <code>X,Pnode L);</code>
<code>void</code> <code>HeadInsert(</code><code>int</code> <code>X,Pnode L,Pnode P);</code>
<code>void</code> <code>TialInsert(</code><code>int</code> <code>X,Pnode L,Pnode P);</code>
<code>void</code> <code>DisplayList(Pnode L);</code>
<code>Pnode MallocNode();</code>
<code>#endif</code>
<code>node.c</code>
<code>#include<stdio.h></code>
<code>#include<stdlib.h></code>
<code>#include"node.h"</code>
<code>/*申请节点*/</code>
<code>Pnode MallocNode()</code>
<code>{</code>
<code> </code><code>Pnode P = (Pnode)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(Node));</code>
<code> </code><code>if</code><code>(NULL != P)</code>
<code> </code><code>{</code>
<code> </code><code>return</code> <code>P;</code>
<code> </code><code>}</code>
<code> </code><code>else</code>
<code> </code><code>return</code> <code>NULL;</code>
<code>}</code>
<code>/*判断是否为空*/</code>
<code>int</code> <code>IsEmpty(Pnode L)</code>
<code> </code><code>if</code><code>(L->Next == NULL)</code>
<code> </code><code>return</code> <code>0;</code>
<code> </code><code>return</code> <code>-1;</code>
<code>/*判断是否是最后一个节点*/</code>
<code>int</code> <code>IsLast(Pnode L)</code>
<code>/*查找数据域为X的节点*/</code>
<code>Pnode Find(</code><code>int</code> <code>X,Pnode L)</code>
<code> </code><code>Pnode P = L->Next;</code>
<code> </code><code>if</code><code>(0 == IsEmpty(L))</code>
<code> </code><code>printf</code><code>(</code><code>"list is empty!\n"</code><code>);</code>
<code> </code><code>while</code><code>(P != NULL && P->Data != X)</code>
<code> </code><code>P = P->Next;</code>
<code> </code><code>return</code> <code>P;</code>
<code>/*查找数据域为X的前驱节点*/</code>
<code>Pnode FindPrevious(</code><code>int</code> <code>X,Pnode L)</code>
<code> </code><code>Pnode P = L;</code>
<code> </code><code>while</code><code>(P->Next != NULL && P->Next->Data != X )</code>
<code>/*删除数据为X的节点*/</code>
<code>void</code> <code>Delete(</code><code>int</code> <code>X,Pnode L)</code>
<code> </code><code>Pnode P,Temp;</code>
<code> </code><code>return</code> <code>;</code>
<code> </code><code>P = FindPrevious(X,L);</code>
<code> </code><code>if</code><code>(0 != IsLast(P))</code>
<code> </code><code>Temp = P->Next;</code>
<code> </code><code>P->Next = Temp->Next;</code>
<code> </code><code>free</code><code>(Temp);</code>
<code> </code><code>printf</code><code>(</code><code>"no find data!\n"</code><code>);</code>
<code> </code><code>return</code><code>;</code>
<code>/*头插*/</code>
<code>void</code> <code>HeadInsert(</code><code>int</code> <code>X,Pnode L,Pnode P)</code>
<code> </code><code>P->Data = X;</code>
<code> </code><code>if</code><code>(NULL == L->Next)</code>
<code> </code><code>L->Next = P;</code>
<code> </code><code>P->Next = NULL;</code>
<code> </code><code>P->Next = L->Next;</code>
<code>/*尾插*/</code>
<code>void</code> <code>TialInsert(</code><code>int</code> <code>X,Pnode L,Pnode P)</code>
<code> </code><code>P->Next = NULL;</code>
<code> </code><code>Pnode T = L;</code>
<code> </code><code>while</code><code>(NULL != T->Next)</code>
<code> </code><code>T = T->Next;</code>
<code> </code><code>T->Next = P;</code>
<code>/*显示链表*/</code>
<code>void</code> <code>DisplayList(Pnode L)</code>
<code> </code><code>while</code><code>(NULL != P)</code>
<code> </code><code>printf</code><code>(</code><code>" %d"</code><code>,P->Data);</code>
4.双向链表
<a href="https://s3.51cto.com/wyfs02/M02/05/FD/wKiom1mvonTyi1G3AAAQfPeZTQQ068.png" target="_blank"></a>
5.双向循环链表
<a href="https://s5.51cto.com/wyfs02/M02/A4/AE/wKioL1mvommimiSsAAAO6spsgMk570.png" target="_blank"></a>
双向链表和双向循环链表以后用到再实现,上面的结构不对,应该有前驱指针。
<code>struct</code> <code>Node{</code>
<code> </code><code>Ele Data;</code>
<code> </code><code>struct</code> <code>Node *Tail;</code>
<code> </code><code>struct</code> <code>Node *Next;</code>
本文转自 8yi少女的夢 51CTO博客,原文链接:http://blog.51cto.com/zhaoxiaohu/1963104,如需转载请自行联系原作者