单链表的学习

1.链表的定义：

1 typedef struct node{
2     DataType data;   /* 每个元素数据信息 */ 
3     struct node* next;  /* 存放后继元素的地址 */ 
4 } LNode, *LinkList;

2.创建空单列表

1 LinkList Creat_LinkList(void)
2 { /* 创建空单链表，入口参数：无；返回值：单链表的头指针，0代表创建失败，非0代表成功 */ 
3     LinkList H;
4     H = (LinkList)malloc(sizeof(LNode));
5     if (H) /* 确认创建头节点是否成功，若成功，修改单链表头节点的指针域为0代表空表 */
6       H->next = NULL;
7     return H; 
8 }

3.销毁单链表

 1 void Destroy_LinkList(LinkList* H)
 2 { /* 销毁单链表，入口参数：单链表头指针的地址 */
 3     LinkList p,q;
 4     p = *H;
 5     while (p)    /* 释放单链表的所有结点 */ 
 6     { 
 7         q = p;
 8         p = p->next;
 9         free(q); 
10     }     /* while */
11     *H = NULL;
12 }

4.求表长

 1 int Length_LinkList(LinkList H)
 2 { /* 求单链表表长，入口参数：单链表头指针，出口参数：表长，-1表示单链表不存在 */ 
 3     LinkList p = H;  /* p指向头节点 */ 
 4     int count = -1;  /* H带头结点所以从-1开始 */
 5     while(p)         /* p所指的时第count+1个结点 */ 
 6     {
 7         p = p->next;
 8         count++;    
 9     } 
10     return (count);
11 }

5.查找操作

（1）按顺序查找

 1 LinkList Locate_LinkList_Pos(LinkList H, int i)
 2 { /* i不正确或者链表不存在，则返回NULL，i==0返回头指针，否者返回第i个结点的指针 */
 3     LinkList p;
 4     int j;
 5     p = H; j = 0;
 6     while (p && j<i)   /* 查找第i个结点 */ 
 7     {
 8         p = p->next;
 9         j++; 
10     }                 /* while */
11     if (j!=i || !p)
12     {
13         printf("参数i错或单链表不存在")
14         return (NULL);
15     }                /* 第i个结点不存在 */
16     return (p); 
17 }

（2)按值查找

 1 LinkList Locate_LinkList_Value(LinkList H, DataType x)
 2 {   /* 在单链表中查找值为x的结点，入口参数：单链表指针，检索元素 */
 3     /* 出口参数：找到后返回其指针，否者返回NULL */
 4     LinkList p = H->next;
 5     while (p && p->data != x)
 6     {
 7         p = p->next;    
 8     } 
 9     return (p);
10 }

6.插入

 1 int Insert_LinkList(LinkList H, int i, DateType x)
 2 {    /* 在单链表H的第i个位置插入值为x的结点，入口参数：单链表，插入位置，插入元素 */
 3     /* 返回参数：成功标志，0表示不成功，1表示成功 */
 4     LinkList p,q; 
 5     p = Locate_LinkList(H,i-1);     /* 找第i-1个结点位置，就是按序号查找 */ 
 6     if (!p)
 7     {
 8         printf("i有误");
 9         return (0); 
10     }
11     q = (LinkList)malloc(sizeof(LNode))
12     if (!q)
13     {
14         printf("申请空间失败");
15         return (0); 
16     }        /* 申请空间失败，不能插入 */ 
17     q->data = x;
18     q->next = p->next;        /* 新节点插入在第i-1个结点的后面 */ 
19     p->next = q;            /* 切记，顺序不能错  */ 
20     return 1;                /* 插入成功，则返回  */ 
21 }

7.删除

 1 int Del_LinkList(LinkList H, int i)
 2 {  /*  删除单链表H上的第i个结点，入口参数:单链表，删除元素序号，返回参数：成功标志，0
 3         表示不成功，1表示成功  */ 
 4     LinkList p,q;
 5     if (H==NULL || H->next==NULL)
 6     {
 7         printf("链表不存在或者空表不能删除");
 8         return (0);
 9     }
10     p = Locate_LinkList(H,i-1);   /* 找第i-1个结点地址，时按序号查找算法  */
11     if (p==NULL || P->next==NULL)
12     {
13         printf("参数i错");
14         return (0);        /* 第i个结点不存在 */   
15     } 
16     q = p->next;       /*  q指向第i个结点 */
17     p->next = q->next;  /* 从链表中删除  */
18     free(q);           /*  释放 * s  */
19     return (1); 
20 }

以上是单链表的一些基本操作。