| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿以码会友 以友辅仁
共有 189 人关注过本帖
标题:[数据结构]单链表
只看楼主 加入收藏
八画小子
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:16
帖 子:515
专家分:1252
注 册:2010-11-11
结帖率:96.3%
  问题点数:0  回复次数:0   
[数据结构]单链表
SList.h
程序代码:
#ifndef SLIST_H
#define SLIST_H

#include <stddef.h>
#include <stdbool.h>

typedef struct SListNode_struct
{
    int m_Data;
    struct SListNode_struct * m_Next;
} SListNode_t;

typedef struct
{
    SListNode_t * m_Head;
    size_t m_Count;
} SList_t;

bool SList_Init(SList_t * list);
bool SList_Insert(SList_t * list, int index, int data);
bool SList_Delete(SList_t * list, int index);
bool SList_Update(SList_t * list, int index, int newData);
void SList_Reverse(SList_t * list);
void SList_Empty(SList_t * list);
bool SList_Sort(SList_t * list);

void SList_Print(const SList_t * list);

static inline size_t SList_Count(const SList_t * list)
{
    return list->m_Count;
}

static inline bool SList_IsEmpty(const SList_t * list)
{
    return list->m_Count == 0;
}

#endif


SList.c
程序代码:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SList.h"

void QuickSort(int array[], int firstIndex, int lastIndex)
{
    int i = 0;
    int j = 0;
    int key = 0;

    if(firstIndex >= lastIndex)
        return;
   

    i = firstIndex;
    j = lastIndex;
    key = array[firstIndex];

    while(i < j)
    {
        while(i < j && key <= array[j])
            j--;
        array[i] = array[j];

        while(i < j && array[i] <= key)
            i++;
        array[j] = array[i];
    }

    array[i] = key;
    QuickSort(array, firstIndex, i - 1);
    QuickSort(array, i + 1, lastIndex);
}

bool SList_Init(SList_t * list)
{
    if(!list)
        return false;
   

    SListNode_t * node = malloc(sizeof(SListNode_t));
    if(!node)
        return false;
   

    node->m_Data = 0;
    node->m_Next = NULL;
   

    list->m_Head = node;
    list->m_Count = 0;

    return true;
}

bool SList_Insert(SList_t * list, int index, int data)
{
    SListNode_t * p = NULL;

    if(!list)
        return false;
    if(index < 0)
        index = 0;
    if(index > list->m_Count)
        index = list->m_Count;
   

    SListNode_t * node = malloc(sizeof(SListNode_t));
    if(!node)
        return false;

    node->m_Data = data;

    p = list->m_Head;
    for(int i = 0; i < index; i++)
        p = p->m_Next;
   

    node->m_Next = p->m_Next;
    p->m_Next = node;

    list->m_Count++;

    return true;
}

bool SList_Delete(SList_t * list, int index)
{
    SListNode_t * p = NULL;
    SListNode_t * q = NULL;

    if(!list)
        return false;
    if(index < 0 || index >= list->m_Count)
        return false;

    p = list->m_Head;
    for(int i = 0; i < index; i++)
        p = p->m_Next;
   

    q = p->m_Next;
    p->m_Next = q->m_Next;
    free(q);

    list->m_Count--;

    return true;
}

bool SList_Update(SList_t * list, int index, int newData)
{
    SListNode_t * p = NULL;

    if(!list)
        return false;
   

    if(index < 0 || index >= list->m_Count)
        return false;
   

    p = list->m_Head->m_Next;
    for(int i = 0; i < index; i++)
        p = p->m_Next;
   

    p->m_Data = newData;

    return true;
}

void SList_Reverse(SList_t * list)
{
    SListNode_t * p = NULL;
    SListNode_t * q = NULL;
    SListNode_t * r = NULL;

    if(!list)
        return;
   

    if(list->m_Count < 2)
        return;
   

    p = list->m_Head->m_Next;
    q = p->m_Next;
    p->m_Next = NULL;
    while(q)
    {
        r = q->m_Next;

        q->m_Next = p;

        p = q;
        q = r;
    }
    list->m_Head->m_Next = p;
}

void SList_Empty(SList_t * list)
{
    SListNode_t * p = NULL;
    SListNode_t * q = NULL;

    p = list->m_Head->m_Next;
    while(p)
    {
        q = p->m_Next;
        free(p);
        p = q;
    }

    list->m_Head->m_Next = NULL;
    list->m_Count = 0;
}

bool SList_Sort(SList_t * list)
{
    int * array = NULL;
    SListNode_t * p = NULL;
    size_t count = 0;

    count = list->m_Count;
    array = malloc(sizeof(int) * count);
    if(!array)
        return false;
   

    p = list->m_Head->m_Next;
    for(int i = 0; i < count; i++, p = p->m_Next)
    {
        array[i] = p->m_Data;
    }

    // 下面用快速排序法对array[]进行排序
    QuickSort(array, 0, count - 1);

    SList_Empty(list);
    for(int i = 0; i < count; i++)
    {
        SList_Insert(list, list->m_Count, array[i]);
    }

    return true;
}

void SList_Print(const SList_t * list)
{
    SListNode_t * p = NULL;

    if(!list)
        return;

    printf("[ ");
    p = list->m_Head->m_Next;
    while(p)
    {
        printf("%d ", p->m_Data);
        p = p->m_Next;
    }
    printf("]\n");
}

搜索更多相关主题的帖子: list int index return array 
2019-08-06 10:15
快速回复:[数据结构]单链表
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.207263 second(s), 9 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved