最新消息:点击查看大S的省钱秘笈

单链表的操作C语言版

编程相关 Slyar 5124浏览 4评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

昨天数据结构课在讲单链表,所以写了一份单链表的操作C语言实现代码。如果代码有什么不完善的地方,还请指出,谢谢。

操作中包括单链表的创建、插入、查找、删除和销毁等。

/*
单链表的操作C语言实现
Slyar 2009.3.23
//www.slyar.com
*/

#include 
#include 

/* 给 char 类型定义别名 datatype */
typedef char datatype;

/* 定义链表节点类型 */
typedef struct node
{
        datatype data;
        struct node *next;
}linklist;

/* 函数声明部分 */
linklist* CreatList();
linklist* Get(linklist*, int);
linklist* Locate(linklist*, datatype);
void PrintList(linklist*);
void InsertAfter(linklist*, datatype);
void InsertBefore(linklist*, int, datatype);
void DeleteAfter(linklist*);
void Deleter(linklist*, int);
void FreeList(linklist*);

int main()
{
        int pos;
        datatype value;
       
        /* 测试创建链表函数 */
        printf("请输入一串字符,以 $ 结束\n");
        linklist *head, *p;
        head = CreatList();
       
        /* 测试打印链表函数 */
        printf("\n打印链表\n");
        PrintList(head);

        /* 测试按序号查找函数 */
        printf("\n请输入要查找的节点序号:\n");
        scanf("%d", &pos);
        getchar();
        p = Get(head, pos);
        if(p != NULL)
        {
                printf("%c\n", p -> data);
        }
        else
        {
                printf("Can't Get This Key!\n");
        }
       
        /* 测试按值查找函数 */
        printf("\n请输入要查找的值:\n");
        scanf("%c", &value);
        p = Locate(head, value);
        if(p != NULL)
        {
                printf("%c\n", p -> data);
        }
        else
        {
                printf("Can't Get This Key!\n");
        }
       
        /* 测试插入节点函数 */
        printf("\n你想在第几个节点前插入?\n");
        scanf("%d", &pos);
        getchar();
        printf("请输入要插入的值\n");
        scanf("%c", &value);
        InsertBefore(head, pos, value);
        PrintList(head);        

        /* 测试删除节点函数 */
        printf("\n你想删除第几个节点?\n");
        scanf("%d", &pos);
        Deleter(head, pos);
        PrintList(head);
       
        /* 销毁链表 */
        FreeList(head);
        
        //system("pause");
        return 0;
}

/* 带头结点后插法创建链表函数 */
linklist* CreatList()
{
        datatype key;
        /* head 为头指针, s 为新节点, r 为尾指针 */
        linklist *head, *s, *r;
        head = (linklist*) malloc(sizeof(linklist));
        r = head;
        key = getchar();
        /* 遇到 $ 就停止创建 */
        while(key != '$')
        {
                s = (linklist*) malloc(sizeof(linklist));
                s -> data = key;
                /* 新节点插入表尾 */
                r -> next = s;
                /* 尾指针指向新的表尾 */
                r = s;
                key = getchar();
        }
        r -> next = NULL;
        /* 返回头指针 */
        return head;
}

/* 打印链表函数 */
void PrintList(linklist* head)
{
        linklist *p;
        p = head -> next;
        while(p != NULL)
        {
                printf("%c", p -> data);
                p = p -> next;
        }
        printf("\n");
}

/* 查找链表中第 i 个节点 */
linklist* Get(linklist* head, int i)
{
        /* j 为扫描计数器 */
        int j = 0;
        linklist *p;
        /* p 指向头节点 */
        p = head;
        /* 到达表尾或序号不合法就退出循环 */
        while((p -> next != NULL) && (j < i))
        {
                p = p -> next;
                j++;
        }
        if (i == j)
        {
                return p;
        }
        else
        {
                return NULL;
        }
}

/* 在链表中查找值 key 并返回所在节点 */
linklist* Locate(linklist* head, datatype key)
{
        linklist *p;
        /* p 指向开始结点 */
        p = head -> next;
        while(p != NULL)
        {
                if(p -> data != key)
                {
                        p = p -> next;
                }
                else
                {
                        break;
                }
        }
        return p;
}

/* 在节点 p 后插入 key */
void InsertAfter(linklist* p, datatype key)
{
        linklist *s;
        s = (linklist*) malloc(sizeof(linklist));
        s -> data = key;
        /* 先将 s 指向后一个节点,再将前一个节点指向 s */
        s -> next = p -> next;
        p -> next = s;
}

/* 将 key 插入链表第 i 个节点之前 */
void InsertBefore(linklist* head, int i, datatype key)
{
        linklist *p;
        int j = i - 1;
        /* 找到第 i-1 个节点 p */
        p = Get(head, j);
        if (p == NULL)
        {
                printf("Insert Error!\n");
        }
        else
        {
                /* 将 key 插入节点 p 之后 */
                InsertAfter(p, key);
        }
}

/* 删除 p 节点的后继节点 */
void DeleteAfter(linklist* p)
{
        linklist *r;
        /* r 指向要删除的节点 */
        r = p -> next;
        /* 将 p 直接与 r 下一个节点链接 */
        p -> next = r -> next;
        /* 释放节点 r */
        free(r);
}

/* 删除链表的第 i 个节点 */
void Deleter(linklist* head, int i)
{
        linklist *p;
        int j = i - 1;
        /* 找到第 i-1 个节点 p */
        p = Get(head, j);
        if ((p != NULL) && (p -> next != NULL))
        {
                /* 删除 p 的后继节点 */
                DeleteAfter(p);
        }
        else
        {
                printf("Delete Error!\n");
        }
}

/* 递归释放单链表 */
void FreeList(linklist* p)
{
        if (p -> next != NULL)
        {
                FreeList(p -> next);
        }
        free(p);
}

转载请注明:Slyar Home » 单链表的操作C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (4)

  1. 我是从java转过来写C 我觉得你这种写法很适合java programmer 嘿嘿
    martinv778年前 (2013-05-29)回复
  2. 有没有按值删除的节点啊,我都不知道怎么删除了。
    radix7210年前 (2010-10-24)回复
  3. 如果我想拥有您这样的一个网站,应该怎么做 再则,我很喜欢你网站的内容
    travis11年前 (2010-03-13)回复
  4. 大一的时候我把单链表写了n多遍。。。
    Felix02112年前 (2009-03-25)回复