数据结构与算法分析：习题3-1（链表）

单向链表基本介绍（引用：http://blog.csdn.net/jianyuerensheng/article/details/51200274）

链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。下面对单向链表做一个介绍。

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。 

上图中最左边的节点即为头结点（Head），但是添加节点的顺序是从右向左的，添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用，所以头节点就可以操作所有节点了。 

下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成了一个单向链表。 

节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：

解决了概念问题，再来解决数据结构与算法分析（第二版）习题3-1：

/******题目：编写打印出一个单链表的所有元素的程序****************/

#include

#include

/*创建节点结构*/

struct Node_t //显示声明，无结构体变量

{

int val;//数据域

struct Node *next;//指针域

};

typedef struct Node_t Node;//用typedef来简化结构体的写法

Node *findEnd(Node *list) //寻找至尾

{

while (list->next)

list = list->next;

return list;

}

void insert(int val, Node *list) //链表插入

{

Node *p = (Node *)malloc(sizeof(Node));//分配内存空间

p->val = val; //将val赋给结构体p的成员

p->next = NULL; //指针域指向空

Node *end = findEnd(list);//寻找表尾

end->next = p; //插入

}

Node *EmptyList()//创建一个空链表

{

Node* list = (Node*)malloc(sizeof(Node));

if (list == NULL) //检查内存是否分配成功

printf("out of space");

list->val = 0;

list->next = NULL;

return list;

}

int main(){

EmptyList();//创建一个空表

Node *list = (Node *)malloc(sizeof(Node)), *p;//定义两个结构体类型的变量

list->next = NULL;//指针域指向空

int a;

for (a = 11; a >0; a--)

insert(a, list);//将a插入链表

p = list->next;//p为list的指针域

while (p){

printf("%d ", p->val);

p = p->next;

}

while (1);//为了使得调试窗口稳定

return 0;

}

---

`以上便是关于单向链表与习题3-1的解法，不足之处大家多交流，以后再分享文章吧。————老子涤生 `