| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
 Reworld，下班在家制作游戏，1500万奖金等你拿 以码会友 以友辅仁

问题点数：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
{
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_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;

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;

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;

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;

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

q->m_Next = p;

p = q;
q = r;
}
}

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

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

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;

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("[ ");
while(p)
{
printf("%d ", p->m_Data);
p = p->m_Next;
}
printf("]\n");
}```

• 1
• 1/1页
• 1