C语言之链表

这两天在复习C语言的知识，为了给下个阶段学习OC做准备，以下的代码的编译运行环境是Xcode5.0版本，写篇博文把昨天复习的C语言有关链表的知识给大家分享一下，以下是小菜自己总结的内容，代码也是按照自己的思路所编写的，有不足之处还请大牛们批评指教。

　　确切的说链表属于数据结构中线性表中的内容，在链表中存储的内容是按线性排列的，就像是一条线把所要存的数据串起来，可以把链表类比成一串珠子，数据就是一个个的珠子，数据间的next指针就相当于穿珠子的线。

　　链表操作的时间复杂度： 往链表中插入数据的时间复杂度为O(1)。

　　想真正的理解链表及在C语言中的表示方法的前提是理解C语言中的指针和结构体，闲话少说，进代码才是关键，代码中基本上都有注释

　　1.用结构体定义链表的节点

//定义链表中的节点
typedef struct node{
 //存储数据
 int data;
 //指向下一个节点
 struct node *next;
}Node;

//定义链表结构
typedef struct {
 //存放头节点
 Node *head;
 //记录节点的个数
 int count;
}List;

　　3.链表的初始化，给链表分配头结点，节点个数初始化为0

/************************************************
 *功能：初始化链表，分配头结点，结点个数为0
 *参数：链表指针
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void initLinkList(List *list)
{
 //给头节点分配内存
 list->head = malloc(sizeof(Node));
 //头结点的下一个节点为空
 list->head->next = NULL;
 //总节点个数为0
 list->count = 0;
}

　　4.建立单项链表，这里为了简单起见，把要存入数据先存入到array中，下面我是用逆序的方法来创建链表的，是从head节点后插入数据，也可以用顺序建链表，从链表的后面插入数据

/************************************************
 *功能：逆序建立链表，从头结点后插入
 *参数：链表指针
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void createLinkList(List *list)
{
 //建立链表用到的数据
 int a[10] = {1,2,3,4,5,6,7,8,9,10};
 //临时节点指针用于分配节点内存
 Node *p;
 for (int i = 0; i < 10; i++)
 {
 //给新的节点分配内存
 p = (Node *)malloc(sizeof(Node));
 //给新节点赋值
 p->data = a[i];
 //把值加入到头节点后面，逆序建立链表
 p->next = list->head->next;
 list->head->next = p;
 //链表节点个数加一
 list->count++;
 }
}

　　5.为了方便查看链表中的值，需要一个打印链表中的数据的函数

/************************************************
 *功能：打印链表中的值
 *参数：链表指针
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void printList(List *list)
{
 //临时节点指针变量
 Node *p;
 //从头开始遍历
 p = list->head->next;
 while (p != NULL)
 {
 //自定义的输出整的函数
 print(p->data);
 p = p->next;
 }
 putchar('\n');
}

　　6.查询元素在链表中对于的位置

/************************************************
 *功能：查找链表中指定值的位置，有的返还其位置，无，返还-1
 *参数：链表指针，要查找的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
int search(List *list, int obj)
{
 //定义游标指针
 Node *p;
 //标记值的位置
 int local = 0;
 p = list->head->next;
 while (p != NULL)
 {
 local ++;
 if (p->data == obj)
 {
 //返回值的位置
 return local;
 }
 p = p->next;
 }
 //值不存在返回-1
 return -1;
}

　　7.删除链表中的相应的数据

/************************************************
 *功能：删除链表中的值
 *参数：链表指针，要删除的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void delete(List *list, int obj)
{
 //查询要删除的元素是否在链表中，有返还相应的位置，没有则返还-1
 int flag = search(list, obj);
 
 //判断值的合法性
 if (flag == -1)
 {
 printf("没有要删除的值！\n");
 }
 else
 {
 //定义两个辅助游标指针
 Node *p, *q;
 
 //给q,p赋值
 q= list->head;
 p = list->head->next;
 
 //循环查找相应的值并删除
 while (p != NULL)
 {
 if (p->data == obj)
 {
 q->next = p->next;
 p->next = NULL;
 free(p);
 break;
 }
 q = p;
 p = p->next;
 }
 }
}

　　8.往链表中插入数据

/************************************************
 *功能：往指定的位置后插入相应的值
 *参数：链表指针，插入的位置，插入的值
 *作者：Mr.li
 *日期：14-07-23
 ************************************************/
void insert(List *list, int local, int number)
{
 int count = 0;
 //判断值的合法性
 if(count > list->count)
 {
 printf("你输入的值不合法\n");
 }
 else
 {
 //定义游标指针,指向链表的头结点
 Node *p = list->head;
 while (count != local) {
 p++;
 count++;
 }
 
 //分配新的结点并给新的结点赋值
 Node *q = (Node *) malloc(sizeof(Node));
 q->data = number;
 q->next = NULL;
 
 //插入新的结点
 q->next = p->next;
 p->next = q;
 }
 
}