@quinn 2015-03-20T01:36:37.000000Z 字数 11929 阅读 4243

C语言单链表-19个功能函数

数据结构

C语言单链表-19个功能函数

线性表链接存储（单链表）操作
刚开始学习数据结构，找点题目练手，题目和部分源码参考 http://www.cnblogs.com/lifuqing/archive/2011/08/20/list.html
注意问题：
1. 采用vs2012开发，由于vs不支持C99标准，因此申明变量必须位于运算语句之前
2. 链表没有设置头结点（第一个结点包含元素值）
3. 对链表指针的编写有些混乱（如有的 Node* L, 有的用Node** ），注意区分
4. 链表的排序没能编写成功，（后续应多联系链表，并着重学习一下排序）

/************************************************************************/  
/*             以下是关于线性表链接存储（单链表）操作的18种算法        */  
/* 1.初始化线性表，即置单链表的表头指针为空 */  
/* 2.创建线性表，此函数输入负数终止读取数据*/  
/* 3.打印链表，链表的遍历*/  
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */  
/* 5.返回单链表的长度 */  
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */  
/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */  
/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */  
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */  
/* 10.向单链表的表头插入一个元素 */  
/* 11.向单链表的末尾添加一个元素 */  
/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */  
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */  
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */  
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */  
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */  
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */  
/* 18.交换2个元素的位置 */  
/* 19.将线性表进行快速排序 */

list_link.h

#ifndef LINK_LIST_H  
#define LINK_LIST_H  
#include<stdlib.h>  
#include <string.h>  
#include <stdio.h>  
typedef int elemType;  
typedef struct Node  
    {  
     elemType element;  
      struct Node *next;  
    } Node;  
void init_list(Node *L);  
Node * creat_list();  
int print_list(Node *L);  
Node * clear_list(Node *L);  
int length_list(Node *L);  
int isEmpty_list(Node *L);  
elemType get_pos_element(Node *L, int pos);  
Node* get_pos_prev_address(Node *L, int pos);  
Node *get_element_position(Node* L, elemType x);  
Node *get_element_prev_position(Node* L, elemType x);  
int modify_element(Node* L, int pos, elemType x);  
void insert_head_node(Node **L, elemType x);  
void insert_end_node(Node **L, elemType x);  
int insert_pos_list(Node **L, int pos, elemType x);  
int insert_element_to_sorted_list(Node **L, elemType x);  
elemType delete_head_node(Node **L);  
elemType delete_end_node(Node **L);  
elemType delete_pos_node(Node **L, int pos);  
int delete_element_node(Node **L, elemType x);  
void swap_element_position(Node**L, elemType x, elemType y);  
int sort_list(Node **L);  
#endif // LINK_LIST_H

link_list.c

#include "link_list.h"  
/* 1.初始化线性表，即置单链表的表头指针为空 */  
void init_list(Node * L)  
{  
    L = NULL;  
    printf("初始化链表成功！\n");  
}  
/* 2.创建线性表，此函数输入负数终止读取数据*/  
Node * creat_list()  
{  
    Node * L = NULL;  
    Node *p1, *p2;  
    p1 = ( Node *)malloc(sizeof(struct Node));  
    p2 = ( Node *)malloc(sizeof(struct Node));  
    if(p1 == NULL || p2 == NULL)  
    {  
        printf("内存分配失败！\n");  
        exit(0);  
        system("pause");  
    }  
    memset(p1, 0, sizeof(struct  Node));  
    printf("请输入链表元素的值：");  
    scanf("%d",&(p1->element));  
    p1->next = NULL;  
    //while(p1->element > 0)  
    while(p1->element > 0)  
    {  
        if( L == NULL)  
        {  
            L = p1;  
        }  
        else  
        {  
            p2->next = p1;  
        }  
        p2 = p1;  
        p1 = ( Node *)malloc(sizeof(struct Node));  
        if(p1 == NULL || p2 == NULL)  
        {  
            printf("内存分配失败！\n");  
            exit(0);  
            system("pause");  
        }  
        memset(p1, 0, sizeof(struct  Node));  
        printf("请输入链表元素的值：");  
        scanf("%d",&(p1->element));  
        p1->next = NULL;  
    }  
    printf("创建链表成功！\n");  
    return L;  
}  
/* 3.打印链表，链表的遍历*/  
int print_list(Node * L)  
{  
    Node *p = L;  
    if (NULL == p)  
    {  
        printf("print_list:链表为空!\n");  
        return 0;  
    }  
    printf("打印链表如下：\n   ");  
    while (p != NULL)  
    {  
        printf("%d, ",p->element);  
        p = p->next;  
    }  
    printf("\n");  
    return 0;  
}  
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */  
Node* clear_list(Node *L)  
{  
    Node *p = L;  
    Node *temp = NULL;  
    printf("clear_list运行成功！\n");  
    if (p == NULL)  
    {  
        printf("链表为空，不需清空\n");  
        exit(0);  
    }  
    while (p != NULL)  
    {  
        temp = p->next;  
        free(p);  
        p = temp;  
    }  
    L =NULL;  
    printf("已清空链表！\n");  
    return L;  
}  
/* 5.返回单链表的长度 */  
int length_list(Node *L)  
{  
    int count = 0;  
    printf("length_list运行成功！\n");  
    if (L == NULL)  
    {  
        printf("链表为空,长度为0\n");  
        return 0;  
    }  
    while( L != NULL)  
    {  
        ++count;  
        L = L->next;  
    }  
    return count;  
}  
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */  
int isEmpty_list(Node *L)  
{  
    printf("isEmpty_list运行成功！\n");  
    if (L == NULL)  
    {  
        printf("链表为空！\n");  
        return 1;  
    }  
    else  
    {  
        printf("链表非空！\n");  
        return 0;  
    }  
}  
/* 7.1 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */  
elemType get_pos_element( Node *L, int pos )  
{  
    int i = 1;  
    if (L == NULL)  
    {  
        printf("get_pos_element()运行成功，链表为空, 获取元素失败！\n");  
        system("pause");  
        exit(0);  
    }  
    if (pos < 1)  
    {  
        printf("get_pos_element()运行成功，给定节点数非法！\n");  
        system("pause");  
        exit(0);  
    }  
    while(L != NULL)  
    {  
        if ( i == pos)  
        {  
            printf("get_pos_element()运行成功，第%d个节点元素为%d！\n", pos, L->element);  
            return L->element;  
        }  
        L = L->next;  
        ++i;  
    }  
    printf("get_pos_element()运行成功，超出查找范围！\n");  
    system("pause");  
    exit(0);  
}  
/* 7.2 返回单链表中第pos个结点的前一个地址，方便在pos位置上插入元素，若pos超出范围，则停止程序运行 */  
Node* get_pos_prev_address(Node *L, int pos)  
{  
    Node *prev = NULL;  
    int i = 1;  
    if (L == NULL)  
    {  
        printf("get_pos_address()运行成功，链表为空, 获取元素失败！\n");  
        system("pause");  
        return NULL;  
    }  
    if (pos < 1)  
    {  
        printf("get_pos_address()运行成功，给定节点数非法, 获取元素失败！\n");  
        system("pause");  
        return NULL;  
    }  
    while(L != NULL)  
    {  
        if ( i == pos)  
        {  
            printf("get_pos_address()运行成功，第%d个节点元素前一结点的地址为0x%x！\n", pos, L);  
            //return L;  //若返回L，则方便在pos的后一个位置插入元素  
            return prev; //返回pos的前一个地址，方便在pos位置上插入元素  
        }  
        prev = L;  
        L = L->next;  
        ++i;  
    }  
    printf("get_pos_address()运行成功，超出查找范围！\n");  
    system("pause");  
    return NULL;  
}  
/* 8.1 从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */  
Node * get_element_position( Node* L, elemType x )  
{  
    if (L == NULL)  
    {  
        printf("get_element_position运行成功，链表为空, 获取元素失败！\n");  
        system("pause");  
        exit(0);  
    }  
    while (L != NULL)  
    {  
        if ( L->element == x)  
        {  
            printf("get_element_position运行成功，该链表中元素%d的地址为0x%x\n", x, L);  
            return L;  
        }  
        L = L->next;  
    }  
    printf("get_element_position运行成功，该链表不含有元素%d\n",x);  
    return NULL;  
}  
/* 8.2 从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点前一结点data域的存储地址，否则返回NULL */  
Node * get_element_prev_position( Node* L, elemType x ) //和8.2程序只有返回值的不同  
{  
    Node *prev = NULL;  
    if (L == NULL)  
    {  
        printf("get_element_prev_position运行成功，链表为空, 获取元素失败！\n");  
        system("pause");  
        exit(0);  
    }  
    while (L != NULL)  
    {  
        if ( L->element == x)  
        {  
            printf("get_element_prev_position运行成功，该链表中元素%d前一结点的地址为0x%x\n", x, L);  
            return prev;  
        }  
        prev = L;  
        L = L->next;  
    }  
    printf("get_element_prev_position运行成功，该链表不含有元素%d\n",x);  
    return NULL;  
}  
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */  
int modify_element(Node* L, int pos, elemType x)  
{  
    int i = 1;  
    if (L == NULL)  
    {  
        printf("modify_element函数运行成功，链表为空, 修改失败！\n");  
        system("pause");  
        return 0;  
    }  
    if (pos < 1)  
    {  
        printf("modify_element函数运行成功，给定节点非法！\n");  
        system("pause");  
        return 0;  
    }  
    while(L != NULL)  
    {  
        if ( i == pos)  
        {  
            L->element = x;  
            printf("modify_element函数运行成功，已更换第%d个节点为 %d！\n", pos, x);  
            return 1;  
        }  
        L = L->next;  
        ++i;  
    }  
    printf("modify_element函数运行成功，超出查找范围！\n");  
    system("pause");  
    return 0;  
}  
/* 10.向单链表的表头插入一个元素 */  
void insert_head_node( Node **L, elemType x )  
{  
    Node *insert_node;  
    insert_node = (Node*)malloc(sizeof(Node));  
    insert_node->element = x;  
    insert_node->next = *L;  
    *L = insert_node;  
    printf("insert_head_list运行成功,向表头添加元素%d！\n", x);  
}  
/* 11.向单链表的末尾添加一个元素 */  
void insert_end_node(Node **L, elemType x)  
{  
    Node *insert_node, *last = NULL;  
    Node *p = (*L);  
    insert_node = (Node*)malloc(sizeof(Node));  
    while (p != NULL)  
    {  
        last = p;  
        p = p->next;  
    }  
    last->next = insert_node;  
    insert_node->element = x;  
    insert_node->next = NULL;  
    printf("insert_end_list运行成功,向末尾添加元素%d！\n", x);  
}  
/* 12.向单链表中第pos个结点位置插入元素为x的结点，成功返回1， 失败返回0 */  
int insert_pos_list(Node **L, int pos, elemType x)  
{  
    Node *insert_node = (Node *)malloc(sizeof(Node));  
    Node *pos_node = get_pos_prev_address(*L, pos);  
    if (pos_node == NULL)  
    {  
        printf("insert_pos_list已运行，但向第%d个节点处添加元素%d时失败，请查看上述提示\n",pos, x);  
        return 0;  
    }  
    insert_node->element = x;  
    insert_node->next = pos_node->next;  
    pos_node->next = insert_node;  
    printf("insert_pos_list运行,向第%d个节点处添加元素%d 成功！\n", pos, x);  
    return 1;  
}  
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */  
int insert_element_to_sorted_list(Node **L, elemType x)  
{  
    int sort_type = 0; //升序排列为1，降序为0  
    int ret = 1; //标志位，判断是否为异常情况  
    elemType first;  
    Node *p = *L;  
    Node *left = NULL, *right = NULL, *temp = NULL;  
    Node *insert_node = (Node *)malloc(sizeof(Node));  
    insert_node->element = x;  
    if (p == NULL)  
    {  
        printf("insert_element_to_sorted_list运行，链表为空，插入失败\n");  
        return 0;  
    }  
    if ( p->next == NULL) //只有一个元素时  
    {  
        printf("insert_element_to_sorted_list运行，链表只有一个元素，插入成功\n");  
        insert_head_node(L, x);  
        return 1;  
    }  
    first = p->element;  
    if (p->element >= p->next->element) //根据1st >= 2nd 降序  
    {  
        sort_type = 1;  
    }  
    //降序时x>=max, 升序时x <= min 应该将x插入表头  
    if (sort_type && (x >= first))  
    {  
        insert_head_node(L, x);  
        ret = 0; //标志位置0，跳过while  
    }  
    if ( (!sort_type) &&  x <= first)  
    {  
        insert_head_node(L, x);  
        ret = 0; //标志位置0，跳过while  
    }  
    while(ret && p != NULL)  
    {  
        //升序排列时，right首先非0  
        if(x < p->element )   
            right = p;  
        else  
            left = p;  
        // x 左右一大一小时，插入x  
        if (left != NULL && right != NULL)  
        {  
            if (sort_type) //降序，right在insert_node前面，left在后；  
            {  
                insert_node->next = right->next;  
                right->next = insert_node;  
            }  
            else //升序，left在前，right在后  
            {  
                insert_node->next = left->next;  
                left->next = insert_node;  
            }  
            break;//插入成功，跳出循环  
        }  
        p = p->next;  
    } //while  
    //降序时x<min, 升序时x > max 应该将x插入表尾  
    if (p == NULL)  
    {  
        insert_end_node(L, x);  
    }  
    printf("insert_element_to_sorted_list运行，插入元素%d成功\n",x);  
    return 1;  
}  
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */  
elemType delete_head_node(Node **L)  
{  
    elemType head_element;  
    Node *head = NULL;  
    if(*L == NULL)  
    {  
        printf("delete_head_node执行，此链表为空，删除失败, 程序将终止运行\n");  
        system("pause");  
        exit(0);  
    }  
    head = *L;  
    head_element = head->element;  
    *L = head->next;  
    free(head);  
    printf("delete_head_node执行，删除表头结点元素%d 成功\n",head_element);  
    return head_element;  
}  
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */  
elemType delete_end_node(Node **L)  
{  
    elemType end_element;  
    Node *p = *L, *prev = NULL;  
    if(p == NULL)  
    {  
        printf("delete_end_node执行，此链表为空，删除失败, 程序将终止运行\n");  
        system("pause");  
        exit(0);  
    }  
    while(p->next != NULL)  
    {  
        prev = p;  
        p = p->next;  
    }  
    end_element = p->element;  
    if ( prev != NULL)//链表只有一个元素时，prev == NULL  
    {  
        prev->next = NULL;  
    }  
    else   
        *L = NULL; //只有一个元素，将表头置空  
    free(p);  
    printf("delete_end_node执行，删除表尾结点元素%d 成功\n",end_element);  
    return end_element;  
}  
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */  
elemType delete_pos_node(Node **L, int pos)  
{  
    elemType delete_node_element;  
    Node *delete_node = NULL;  
    Node *pos_prev_node = NULL;  
    if(*L == NULL)  
    {  
        printf("delete_pos_node执行，此链表为空，删除失败, 程序将终止运行\n");  
        system("pause");  
        exit(0);  
    }  
    pos_prev_node = get_pos_prev_address(*L, pos);  
    if(pos_prev_node == NULL)  
    {  
        printf("delete_pos_node执行，查找第%d个结点失败，删除失败, 程序将终止运行\n", pos);  
        exit(0);  
    }  
    delete_node = pos_prev_node->next;  
    pos_prev_node->next = delete_node->next;  
    delete_node_element = delete_node->element;  
    free(delete_node);  
    printf("delete_pos_node执行，删除第%d个结点（其元素值为%d）成功, 程序将终止运行\n", pos, delete_node_element);  
    return delete_node_element;  
}  
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */  
int delete_element_node(Node **L, elemType x)  
{  
    Node *delete_node = NULL;  
    Node *x_prev_node = NULL;  
    if(*L == NULL)  
    {  
        printf("delete_pos_node执行，此链表为空，删除失败\n");  
        return 0;  
    }  
    x_prev_node = get_element_prev_position(*L, x);  
    if(x_prev_node == NULL)  
    {  
        printf("delete_element_node执行，查找结点元素%d失败，删除失败\n", x);  
        return 0;  
    }  
    delete_node = x_prev_node->next;  
    x_prev_node->next = delete_node->next;  
    free(delete_node);  
    printf("delete_element_node执行，删除元素值为%d的结点成功, 程序将终止运行\n", x);  
    return 1;  
}  
/* 18.交换2个元素的位置 */  
void swap_element_position(Node**L, elemType x, elemType y)  
{  
    Node *x_prev_node = NULL, *y_prev_node = NULL, *x_node = NULL, *y_node = NULL, *temp = NULL;  
    Node *head = NULL;  
    elemType first = (*L)->element;  
    if ( *L ==NULL )  
    {  
        printf("swap_element_position运行，链表为空，终止运行\n");  
    }  
    /*===由于采用返回查找元素前一结点的地址，因此表头节点需要单独考虑===*/  
    if ( first ==x )  
    {  
        y_prev_node = get_element_prev_position(*L, y);  
        y_node = y_prev_node->next;  
        x_node = *L;  
        temp = y_node->next;  
        y_prev_node->next = x_node;  
        y_node->next =  x_node->next;  
        *L = y_node;  
        x_node->next = temp;  
    }  
    else if( first == y)  
    {  
        x_prev_node = get_element_prev_position(*L, x);  
        x_node = x_prev_node->next;  
        y_node = *L;  
        temp = x_node->next;  
        x_prev_node->next = y_node;  
        x_node->next =  y_node->next;  
        *L = x_node;  
        y_node->next = temp;  
    }  
    else //一般情况，x, y 都不在表头  
    {  
        x_prev_node = get_element_prev_position(*L, x);  
        y_prev_node = get_element_prev_position(*L, y);  
        if (x_prev_node != NULL && y_prev_node != NULL) //画出结点连接图，易懂  
        {  
            y_node = y_prev_node->next;  
            x_node = x_prev_node->next;  
            temp = y_node->next;  
            y_prev_node->next = x_node;  
            y_node->next =  x_node->next;  
            x_prev_node->next = y_node;  
            x_node->next = temp;  
        }  
    }  
    printf("交换元素%d和%d成功！\n", x, y);  
}  
/* 19.将线性表进行快速排序 */  
int sort_list(Node **L) //有错误，仍需修改  
{  
    Node *x = NULL, *y = NULL;  
    Node *p = NULL, *f = NULL, *head = *L;  
    if ( p == NULL || p->next == NULL)  
    {  
    }  
    f = NULL;    
    //判断是否只有一个元素或者没有元素    
    if(head == NULL || head  -> next == NULL)    
    {    
        printf("sort_list运行，链表为空or只有一个元素，终止运行\n");  
        return;    
    }    
    while(f != head->next)    
    {    
        for(p = head; p -> next -> next != f; p = p -> next)    
        {    
            if(p -> next -> element > p -> next -> next ->element)    
            {    
                x = p -> next;    
                y = p -> next -> next;    
                p -> next = y;    
                x -> next = y -> next;    
                y -> next = x;    
            }    
        }    
        f = p -> next;    
    }    
    //*L = p;  
    printf("升序排列完成\n");  
}

main.c

#include "link_list.h"  
int main()  
{  
    int n;  
    Node * L = NULL;  
    Node *p = NULL;  
    init_list(L);  
    length_list(L);  
    isEmpty_list(L);  
    L = creat_list();  
    length_list(L);  
    insert_element_to_sorted_list(&L, 5);  
    print_list(L);  
    swap_element_position(&L, 2, 5);  
    print_list(L);  
    sort_list(&L);  
    print_list(L);  
    delete_element_node(&L, 3);  
    print_list(L);  
    delete_pos_node(&L, 2);  
    print_list(L);  
    delete_head_node(&L);  
    print_list(L);  
    delete_end_node(&L);  
    print_list(L);  
    insert_head_node(&L, 200);  
    insert_end_node(&L, 400);  
    print_list(L);  
    insert_pos_list(&L, 2, 50);  
    insert_pos_list(&L, 6, 40);  
    print_list(L);  
    n = get_pos_element(L, 3);  
    printf("第3个元素为%d\n",n);  
    modify_element(L, 3, 100);  
    print_list(L);  
    modify_element(L, 5, 100);  
    print_list(L);  
    modify_element(L, 0, 100);  
    print_list(L);  
    p = get_element_position(L, 3);  
    printf("元素3的地址：%x\n",p);  
    p = get_element_position(L, 10);  
    printf("元素10的地址：%x\n",p);  
    isEmpty_list(L);  
    n = length_list(L);  
    printf("链表长度为：%d\n", n);  
    print_list(L);  
    L = clear_list(L);  
    system("pause");  
    return 0;  
}

在此输入正文

C语言单链表-19个功能函数

list_link.h

link_list.c

main.c

内容目录