数据结构---线性表的链式表示和实现（一）

数据结构---线性表的链式表示和实现（一）
16年2月26日19:46:29
这一块的内容就是所谓的链表操作，对于这一块的内容需要熟练的掌握，以下的源程序是单链表的一些操作，对于双链表和循环链表，以及linux内核中的链表，我们将在后面写出来，现在先分析单链表：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *pNext;
}NODE, *PNODE;

/**
 * Initialise the link_list.
 * @param  pHead [this link_list]
 * @return [if success, return the address of the pHead]
 */
PNODE InitLink(PNODE pHead)
{
    pHead = (PNODE)malloc(sizeof(NODE));
    if (!pHead)
    {
        printf("Cannot malloc memory for pHead.\n");
        exit(-1);
    }

    pHead->pNext = NULL;

    return pHead;
}

/**
 * Judge the link_list is empty or not.
 * @param  pHead [this link_list]
 * @return [if empty, return 1, if not empty, return 0]
 */
int IsLinkEmpty(PNODE pHead)
{
    return pHead->pNext ? 0 : 1;
}

/**
 * Insert entry to the link_list.
 * @param  pHead [this link_list]
 * @param  pos [position]
 * @param  val [the entry value]
 * @return [if success, return 1]
 */
int InsertLink(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE pTmp = pHead;
    PNODE pNew;

    if (pos < 1)
    {
        printf("Error position.\n");
        exit(-1);
    }

    while (pTmp && i < pos - 1)
    {
        pTmp = pTmp->pNext;
        i++;
    }

    pNew = (PNODE)malloc(sizeof(NODE));
    if (!pNew)
    {
        printf("Cannot malloc memory for pNew.\n");
        exit(-1);
    }

    pNew->data = val;
    pNew->pNext = pTmp->pNext;

    pTmp->pNext = pNew;

    return 1;
}

/**
 * Delete entry of the link_list.
 * @param  pHead [this link_list]
 * @param  pos [position]
 * @param  val [the value of the deleted entry]
 * @return [if success, return 1]
 */
int DeleteLink(PNODE pHead, int pos, int *val)
{
    PNODE pTmp = pHead;
    PNODE q;
    int i = 0;

    if (pos < 1)
    {
        printf("Error position.\n");
        exit(-1);
    }

    while (pTmp && i < pos - 1)
    {
        pTmp = pTmp->pNext;
        i++;
    }

    q = pTmp->pNext;
    *val = q->data;
    pTmp->pNext = q->pNext;
    free(q);

    return 1;
}

/**
 * Traverse this link_list.
 * @param pHead [this link_list]
 */
void TraverseLink(PNODE pHead)
{
    PNODE pTmp;

    pTmp = pHead->pNext;
    while (pTmp)
    {
        printf("%d ", pTmp->data);
        pTmp = pTmp->pNext;
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    PNODE pHead = NULL;
    int val;

    pHead = InitLink(pHead);
    if (IsLinkEmpty(pHead))
    {
        printf("The link_list is empty.\n");
    }
    InsertLink(pHead, 1, 1);
    InsertLink(pHead, 1, 2);
    InsertLink(pHead, 1, 3);
    InsertLink(pHead, 1, 4);
    InsertLink(pHead, 1, 5);
    InsertLink(pHead, 4, 33);
    TraverseLink(pHead);
    if (IsLinkEmpty(pHead))
    {
        printf("The link_list is empty.\n");
    }
    if (DeleteLink(pHead, 4, &val))
    {
        printf("The delete value is %d.\n", val);
    }
    TraverseLink(pHead);
    if (DeleteLink(pHead, 3, &val))
    {
        printf("The delete value is %d.\n", val);
    }
    TraverseLink(pHead);
    return 0;
}

程序的运行结果如下所示：
The link_list is empty.
5 4 3 33 2 1
The delete value is 33.
5 4 3 2 1
The delete value is 3.
5 4 2 1

对于这一块，有一个C语言的指针问题没有掌握，在上述程序中，刚开始是这样的：
void InitLink(PNODE pHead)
{
    pHead = (PNODE)malloc(sizeof(NODE));
    if (!pHead)
    {
        printf("Cannot malloc memory for pHead.\n");
        exit(-1);
    }

    pHead->pNext = NULL;
}
然后在main函数中是这样的：
int main(int argc, char const *argv[])
{
    PNODE pHead = NULL;
    int val;

    InitLink(pHead);
    InsertLink(pHead, 1, 1);
    InsertLink(pHead, 1, 2);
    。。。。。。
    return 0;
}
在调试的时候，它总提示在InsertLink(pHead,
1, 1); 这个函数中出错的。好好思考这个问题。在InitLink()这个函数中，pHead是临时变量，是储存在栈中的，当执行完这个函数以后，pHead的值会被释放，但是通过malloc动态分配的内存它不会释放，但是如果pHead释放的话，我们就找不到这个动态分配的内存地址，这时候，main函数中的pHead仍为空，没有赋值，所以在下面的插入操作中将要出错。 
			
			
				
			
			
				但是如果我想把这个pHead的值直接存进main函数中声明的pHead变量中，这个怎么改呢？如果想直接修改main函数中的pHead变量，就需要把它的地址传过去，就是如下所示的： 
			
			
				void
InitLink(PNODE pHead)  
			
			
				{  
			
			
				     pHead
= (PNODE)malloc(sizeof(NODE));  
			
			
				     if
(!pHead)  
			
			
				     {  
			
			
				     printf("Cannot
malloc memory for pHead.\n");  
			
			
				     exit(-1);  
			
			
				     }  
			
			
				
			
			
				     pHead->pNext
= NULL;  
			
			
				}  
			
			
				然后在main函数中是这样的： 
			
			
				int
main(int argc, char const *argv[])  
			
			
				{  
			
			
				     PNODE
pHead = NULL;  
			
			
				     int
val;  
			
			
				
			
			
				     InitLink(&pHead);  
			
			
				     InsertLink(pHead,
1, 1);  
			
			
				     InsertLink(pHead,
1, 2); 
			
			
				     。。。。。。 
			
			
				     return
0;  
			
			
				} 
			
			
				这样在main函数中就不需要采用pHead
= InitLink(pHead);的形式。 
			
			
				
			
			
				总结一下： 
			
			
				以这个InitLink()函数为例，比如在main函数中声明了一个PNODE
pHead = NULL;变量， 
			
			
				（1）如果想要初始化这个变量，就需要对这个变量中的一些元素进行修改，所以需要传进去pHead变量的指针，在main函数中就需要这样的形式：InitLink(&pHead); 
			
			
				（2）如果不想给这个InitLink()函数传递指针，只是把这个PNODE 类型的pHead传进去，那么就需要在main函数中采取这样的形式：pHead
= InitLink(pHead); 
			
			
				同时，需要在这个InitLink()函数中返回这个pHead的地址。