数据结构----链表相关操作

定义链表结构体(节点)

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

NODE 等价于
typedef struct Node
PNODE 等价于
typedef struct * Node

1.创建一个链表

/**
 * 创建一个集合,返回头节点
 * @return [description]
 */
PNODE createList(){
    PNODE pHead=(PNODE)malloc(sizeof(NODE));
    pHead->pNext=NULL;
    return pHead;
}

2.向链表中添加一个节点

/**
 * 添加一个节点
 * @param pHead [description]
 * @param node  [description]
 */
void append(PNODE pHead,PNODE node){
    while(pHead->pNext!=NULL){
        pHead=pHead->pNext;
    }
    pHead->pNext=node;
}

3.向指定的位置添加一个节点

/**
 * 向指定位置添加一个节点   当index超过索引会将元素挂到链表的结尾
 * @param pHead [description]
 * @param node  [description]
 * @param index [description]
 */
void insert(PNODE pHead,PNODE node,int index){
    PNODE temp=pHead;

    while(temp->pNext!=NULL){
        if (index==0&&node)
        {
            /* code */
            node->pNext=temp->pNext;
            temp->pNext=node;
            return;
        }
        index--;
        temp=temp->pNext;
    }
}

4.删除指定位置的结点

/**
 * 删除指定位置的数据
 * @param pHead [description]
 * @param index [description]
 */
PNODE delete(PNODE pHead, int index){
    PNODE r;
    PNODE temp=pHead;

    if (index<=0){
        //如果是删除第一个元素
        r=pHead;
        pHead=pHead->pNext;
        free(r);
        return pHead;
    }

    while(temp->pNext!=NULL){
        if (index==0){
            //删除
            //首先保存temp所指向的结点的指针
            r=temp->pNext;
            //将temp->pNext指向下下个结点
            temp->pNext=temp->pNext->pNext;
            //释放内存
            free(r);

            return pHead;
        }
        index--;
        temp=temp->pNext;
    }
    printf("%s\n", "\n下标越界,指定索引超过链表长度,删除失败");
    return pHead;
}

5.获取链表的长度

/**
 * 获取链表的长度
 * @param  pHead [description]
 * @return       [description]
 */
int size(PNODE pHead){
    int len=0;
    while((pHead=pHead->pNext)!=NULL){
        len++;
    }
    return len;
}

6.对链表排序(冒泡排序算法)

/**
 * 对链表排序(冒泡排序算法)
 * @param pHead [description]
 */
void sortList(PNODE pHead){
    int i,j,max;
    
    int length=size(pHead);

    PNODE r,q;

    r=pHead;
    for (int i = 0; i < length-1; ++i)
    {
        //向下移动
        r=r->pNext;
        
        //假定在外层的本次循环中的第一个节点的数据是最大值
        max=r->data;
        
        //把本次循环的r当前节点赋值给q
        q=r;
        
        //从i的下一个结点开始,往下找,是否有比max打的结点
        for (int j = i+1; j < length; ++j)
        {
            //向下移动一次
            q=q->pNext;
            
            if (q->data>max)
            {
                //找到比max大的数,交换
                max=q->data;
                q->data=r->data;
                r->data=max;
            }
        }
    }
}

7.遍历

/**
 * 遍历链表
 * @param pHead [description]
 */
void traverse(PNODE pHead){
    while((pHead=pHead->pNext)!=NULL){
        printf("%d\t", pHead->data);
    }
}

测试

int main(){
    int i;

    PNODE pHead=NULL;

    //创建
    pHead=createList();

    //添加
    for(i=0;i<10;i++){
        //创建结点
        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        pNew->data=i+1;
        pNew->pNext=NULL;

        //追加结点
        append(pHead,pNew);
    }

    printf("链表长度是length=%d\n",size(pHead));
    traverse(pHead);

    pHead=delete(pHead, 0);
    printf("\n");
    printf("链表长度是length=%d\n",size(pHead));
    traverse(pHead);

    pHead=delete(pHead, 1);
    printf("\n");
    traverse(pHead);
    

    PNODE pNew=(PNODE)malloc(sizeof(NODE));
    pNew->data=100;
    printf("链表长度是length=%d\n",size(pHead));
    pNew->pNext=NULL;

    insert(pHead,pNew,3);
    printf("\n");
    printf("链表长度是length=%d\n",size(pHead));
    traverse(pHead);

    sortList(pHead);
    printf("\n");
    traverse(pHead);

    return 0;
}