链表的定义与简单操作

看代码理解。

/*************************************************************************
    > File Name: list.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2014/12/15 16:49:28
 ************************************************************************/

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

typedef struct Node {
    int data;   // 数据域 
    struct Node *pNext;     // 指针域 
} Node;

Node * create_list(); // 创建链表 
void traverse_list(Node * pHead); // 遍历链表 
bool is_empty_list(Node * pHead); // 判断链表是否为空 
int length_list(Node *pHead); // 链表长度 
void sort_list(Node *pHead); // 链表排序 
bool insert_list(Node *pHead,int pos,int val); // 插入元素至链表第 pos 位 
bool delete_list(Node *pHead,int pos); // 删除链表第 pos 个元素 

int main() {
    Node *pHead;
    pHead = create_list(); // 创建一个新链表 
    traverse_list( pHead );
    if( is_empty_list( pHead ) )
        printf("list is empty.\n");
    else {
        printf("list is not empty.\n");
        printf("length of list: %d\n", length_list( pHead ));
    }
    if(insert_list(pHead, 3, 26)) // 插入测试 
        puts("Third position successfully inserted into the list.");
    else
        puts("Third position failed inserted into the list.");
    traverse_list(pHead);

    if(delete_list(pHead, 4)) // 删除测试 
        puts("Delete the success the fourth element on the list.");
    else
        puts("Delete failed the fourth element on the list.");
    traverse_list(pHead);
    puts("Sorting list.");
    sort_list(pHead); // 排序测试 
    traverse_list(pHead);

    return 0;
}

Node * create_list()
{
    Node *pHead = (Node *)malloc(sizeof(Node)); // 分配头指针，用来指向第一个有效节点 
    Node *pTail = pHead; // 尾指针，用来指向最后一个节点，开始则指向头节点 
    pTail->pNext = NULL; // 首先使头指针和尾指针指向空节点 
    int len;
    printf("input length of linked list :");
    scanf("%d",&len); // 定义链表长度 
    printf("input %d data:\n",len);
    for(int i=0;i<len;++i) {
        Node * pNew = (Node *)malloc(sizeof(Node)); // 为每个新节点分配内存 
        pNew->pNext = NULL; // 新节点的指向下一个空节点 
        scanf("%d",&pNew->data); // 输入节点数据 
        pTail->pNext = pNew; // 使尾结点指向下一个新节点 
        pTail = pNew; // 同时将尾结点重置到尾结点处 
    }
    return pHead; // 返回头指针 
}

void traverse_list(Node * pHead)
{
    Node *p = pHead->pNext;
    while(p != NULL) { // 如果到达尾结点则退出循环 
        printf("%d",p->data); // 输出节点的数据 
        p = p->pNext;
    }
    puts("");
}

bool is_empty_list(Node * pHead)
{
    if( pHead->pNext == NULL )
        return true;
    else
        return false;
}


int length_list(Node *pHead)
{
    int len = 0;
    Node *p = pHead->pNext;
    while( p != NULL ) { // 累加，最终 len 值为链表长度 
        ++len;
        p = p->pNext;
    }
    return len;
}

void sort_list(Node *pHead)
{
    int len = length_list( pHead );
    if(len <=0)
        return ;
    Node *p,*q; // 这里容易写成 Node *p,q 导致 q 不为指针而出错 
    int i,j;    // 这里我犯了低级错误，将 int i,j 分别写到 for 中结果一堆错误。。
                // 注意 for 的初始化只能有一个定义或一个赋值。。
                // 比如,for(p = pHead->pNext,int i=0;...;...) 将出错 
                // 建议分开写吧。。
    for(p = pHead->pNext,i=0; i<len; ++i, p = p->pNext) // 冒泡排序法 = =
        for(q = p->pNext,j=i+1; j<len; ++j,q = q->pNext) {
            if( q->data < p->data )
            {
                int t = q->data;
                q->data = p->data;
                p->data = t;
            }
        }
}

bool insert_list(Node *pHead,int pos,int val)
{
    Node *p = pHead;
    int i;
    for(i=0; i < pos-1 && NULL != p; ++i,p = p->pNext); // 定位，因为从 0 开始所以到 pos-1 就要退出定位了 
    if( i != pos-1 || p == NULL) // 如果不在 pos-1 位上或者该结点为空则返回失败 
        return false;
    Node *pNew = (Node*)malloc(sizeof(Node)); // 为新节点分配空间 
    pNew->data = val; // 插入值 
    pNew->pNext = p->pNext; // 使新节点指向 p 的下一个节点，然后 p 就指向新节点 
    p->pNext = pNew; // p 就指向新节点 
}

bool delete_list(Node *pHead,int pos)
{
    Node * p = pHead;
    int i;
    for(i=0; i<pos-1 && NULL != p; ++i,p = p->pNext); // 定位 
    if( i!=pos-1 || p == NULL)
        return false;
    Node *q = p->pNext; // 这里要标记删除的结点指针 
    p->pNext = q->pNext; // 如果前面不标记结点的话就找不到要删除的那个结点导致内存泄漏 
    free(q); // 删除节点 
    return true;
}