赣州优化/百度seo关键词优化电话
相信每个看到这篇博客的朋友，无论你是学计算机的，还是电子电气类相关专业出身的，都学过基本的编程语言----C语言。在C语言的学习中，我们会大量的接触到数组和结构体等。但是对于非计算机专业的朋友来说，数据结构和算法可能并不是必修的一门课程。对于这部分同学来说，尤其是对于这部分中那些想从事程序员开发工作的同学来说，数据结构与算法成为他们函需加强的课程。无论你去参加面试，或者实际工作编写和阅读代码，没有良好的数据结构基础，就不敢说真正进入了编程的大门。作为电气工程和自动化专业出身的我，对此深有体会。如果你碰巧是这部分人群中一员，并且迫切的想掌握好数据结构的基础，那么，本文就是为你量身定做的。
好了，闲话不多说，我们进入正题。
1.链表与数组的异同
你也许要说，数组的长度是固定的，链表不是。果真如此吗？No!数组有静态和动态之分。动态数组的长度也可以根据存储数据多少自动调整，但这需要我们用程序来实现。那么他们区别在哪里呢？
其一，动态数组本身占用一块连续的内存，而链表的每个结点要占用一块内存。在频繁增删数据的情况下，链表更容易造成内存碎片，具体影响与内存管理器的好坏有关。
其二，链表的调整操作，如插入或者删除某个结点，通常只需要交换指针就可以了，相当方便；而数组则不然，通常需要在数组空间进行内存快的移动。
其三，数组通常占用一块连续的内存，而链表的每个结点都需要占用一块内存，是不连续的。
其四，数组的排序支持很多高效率的算法，而这些算法在链表中的表现比较让人失望。
其五，有序数组可以使用二分查找，而排好序的链表依然只能使用顺序查找。原因在于，链表并不支持随机定位，只能一个个移动指针。
当然，它们之间还有其它差别。这些差别将在以后进行补充。
由上述的5几个差别可以看出，当数据是动态变化的尤其是不可预测时， 这些数据的存储方式应优先选择链表；当数据是相对静态的时候，可以选用数组来存储。
2.链表的种类。
链表可以分为单链表、双链表和循环链表等。相关定义读者可在任何一本教科书上查到满意的结果，在此不再赘述。
3.链表的结构定义(以单链表为例)
这里我们采用伪代码的形式来抽象表示单链表：
typedef struct ListNode
{
ElemType data;
struct ListNode *next;
}ListNode, *LinkList；
LinkList head; //head为单链表头指针。
4.简单单链表的建立
显然，建立单链表，首先要有结点。结点可认为是组成链表的基本元素。那么结点是什么结构呢？我们采用上节的结构体法。假设结构如下：
typedef struct NameVal
{
char *name;
char value;
NameVal *next;
}NameVal;
结点的创建如下：
NameVal *CreateNode(char *name, int value)
{
NameVal *NewNodePtr;
NewNodePtr = (NameVal *)malloc( sizeof (NameVal) );
NewNodePtr->name = name;
NewNodePtr->value = value;
NewNodePtr->next = NULL;
return NewNodePtr;
}
如何把结点添加到链表中呢？有2种办法，一种是头插法，一种是尾插法。
头插法：从空表开始，把建立好的结点插入到链表的头部；读入数据的顺序和线性表中的顺序是相反的。这是最简单的办法。代码示例如下：
NameVal *AddNodeToListFront(NameVal *SingleListPtr, NameVal *CurNodePtr)
{
CurNodePtr->next = SingleListPtr;
return SingleListPtr;
}
在代码中， 实际调用往往是这样的：NameValList = AddNodeToListFront (NameValList , CreateNode( " Smith.Hu ", 0x263A ) );
尾插法与头插法刚好相反，把新来的结点插入到链表的尾部。读入数据的顺序和线性表中的顺序是相同。代码示例如下：
NameVal *AddNodeToListRear(NameVal *SingleListPtr, NameVal *CurNodePtr)
{
NameVal *ListPointerBuffer;
if( NULL == SingleListPtr ) //如果链表为空表，返回当前结点指针，即使得当前结点为待建链表的第一个结点
{
return CurNodePtr;
}
for( ListPointerBuffer =SingleListPtr; ListPointerBuffer ->next != NULL; ListPointerBuffer = ListPointerBuffer ->next ); //查找尾指针
SingleListPtr ->next = CurNodePtr;//找到尾指针后，插入在链表的尾巴上
return SingleListPtr;
}
如果想使得尾插法的时间复杂度为O(1), 代码变得要相对复杂些，需要另外添加一个指向当前结点的尾巴指针。这种办法的缺陷有：（1）需要维护一个尾指针，（2）无法只用一个链表指针（如SingleListPtr）来代表要建立的链表。当然，好处是时间复杂度降低了。
文章的最后，我们看一个面试中经常出现的问题：链表的反转问题。代码如下，系参考网上资料整理而来。
///
// Reverse a list iteratively
// Input: pHead - the head of the original list
// Output: the head of the reversed head
///
ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL; //初始状态，为空表
ListNode* pNode = pHead; //初始状态，原链表待逆转的结点为第一个结点--》头结点
ListNode* pPrev = NULL; //初始状态，头结点前驱结点为NULL
while(pNode != NULL)
{
// get the next node, and save it at pNext
ListNode* pNext = pNode->m_pNext;
// if the next node is null, the currect is the end of original
// list, and it's the head of the reversed list
if(pNext == NULL)
pReversedHead = pNode;
// reverse the linkage between nodes
pNode->m_pNext = pPrev;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return pReversedHead;
}
（转载）