Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
275 lines (245 sloc) 5.99 KB
/**
* @ProjectName:CircularLinkedList 循环链表算法实现
* @Author: MagicDevil.Top (MagicDevil.Zhang@gmail.com)
* @Description: 实现功能:初始化循环链表、插入元素、更新元素、删除元素、清空表、查找元素数量、获取指定索引的元素内容、查找元素所在的索引位置、导出指针数组、打印顺序表所有元素
*/
#include <stdio.h>
#include <windows.h>
#define SUCCESS 1
#define ERROR -1
#define ElemType int
#define StatusType int
#define getArrSize(x) sizeof(x) / sizeof(x[0]) //数组长度计算公式(忽略数组结尾存在'\0'的问题,此方法适用于大部分时候)
//自定义单链表类型
typedef struct LNode
{
ElemType data; //单链表存储
struct LNode *next; //下个链表节点的指针
} LNode, *LinkedList;
//1.初始化单链表
StatusType InitLinkedList(LinkedList &L, ElemType data[], int length)
{
LinkedList temp[length];
if (!data)
{ //空数组退出
return ERROR;
}
for (int i = 0; i < length; i++)
{ //为临时链表节点数组分配空间
temp[i] = (LinkedList)malloc(sizeof(LNode));
}
for (int i = 0; i < length; i++)
{ //为临时链表节点数组设置内容
temp[i]->data = data[i];
temp[i]->next = (i == length - 1 ? temp[0] : temp[i + 1]); //到达最后一个元素时,连接尾节点和头结点,以此设置循环
}
L = temp[0];
return SUCCESS;
}
//2.插入元素(给定index越界后在链表中进行循环不报错)
StatusType InsertLinkedList(LinkedList &L, ElemType content, int index)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
LinkedList temp;
temp = L;
for (int i = 0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
{
temp = temp->next;
}
LinkedList newlist = (LinkedList)malloc(sizeof(LNode));
//通过在指定位置后插入一个新节点,两个节点间内容再进行交换,实现插入
newlist->data = temp->data;
newlist->next = temp->next;
temp->data = content;
temp->next = newlist;
return SUCCESS;
}
//3.更新元素
StatusType UpdateLinkedList(LinkedList &L, ElemType content, int index)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
LinkedList temp;
temp = L;
for (int i = 0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
{
temp = temp->next;
}
temp->data = content;
return SUCCESS;
}
//4.删除元素
StatusType DeleteLinkedList(LinkedList &L, int index)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
LinkedList temp;
temp = L;
if (index == 0)
{ //删除头结点时,需要到达尾节点位置
while (temp->next != L)
{
temp = temp->next;
}
}
else
{
for (int i = 0; i < index - 1; i++) //从第0个到第index-1个元素(指定元素前一个元素)需要向后挪动index-1次
{
temp = temp->next;
}
}
if (temp->next == L)
{ //若删除头结点,则让参数的头结点L后移一位
L = L->next;
}
LinkedList g = temp->next;
temp->next = g->next;
free(g);
return SUCCESS;
}
//5.清空表
StatusType ClearLinkedList(LinkedList &L)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
LinkedList temp = L;
do
{
LinkedList g; //标记垃圾内存
g = temp;
temp = temp->next;
free(g);
g = NULL;
} while (temp->next != L); //遍历到最后一个元素时停止
free(temp);
L = NULL;
return SUCCESS;
}
//6.查找元素数量
StatusType getLinkedListNum(LinkedList &L)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
int num = 0;
LinkedList temp = L;
do
{
num++;
temp = temp->next;
} while (L != temp);
return num;
}
//7.获取指定索引的元素内容
ElemType getLinkedList(LinkedList &L, int index)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
LinkedList temp;
temp = L;
for (int i = 0; i < index; i++) //从第0个到第index个元素需要向后挪动index次
{
temp = temp->next;
}
return temp->data;
}
//8.查找元素所在的索引位置
int indexOfLinkedList(LinkedList &L, ElemType content)
{
if (!L) //空链表时返回错误
{
return ERROR;
}
int foot = 0;
LinkedList temp = L;
do
{
if (temp->data == content)
{ //找到元素时退出
break;
}
foot++;
temp = temp->next;
if (temp == L && temp->data != content)
{ //到达最后元素时仍未找到则返回ERROR
foot = ERROR;
break;
}
} while (L != temp);
return foot;
}
//9.导出指针数组
ElemType *toArrayLinkedList(LinkedList &L)
{
StatusType getLinkedListNum(LinkedList & L);
if (!L) //空链表时返回错误
{
return NULL;
}
ElemType *s = (ElemType *)malloc(sizeof(ElemType) * getLinkedListNum(L));
int foot = 0;
LinkedList temp;
temp = L;
do
{ //对数组赋值
*(s + foot) = temp->data;
foot++;
temp = temp->next;
} while (L != temp);
return s;
}
//10.打印所以元素
StatusType PrintLinkedList(LinkedList &L)
{
int foot = 0;
int flag = 0;
int num = 0;
LinkedList s;
s = L;
if (!L)
{ //空链表时不进入循环表
flag = 1;
}
printf("List Information\n");
while (flag == 0)
{
if (s->next == L)
{ //当遍历一圈时退出
flag = 1;
}
num++;
printf(" |- List %d : %d\n", foot++, s->data);
s = s->next;
}
printf("Num : %d\n", num);
return SUCCESS;
}
int main(int argc, char const *argv[])
{
LinkedList p;
int a[5] = {1, 3, 5, 7, 8};
InitLinkedList(p, a, getArrSize(a));
InsertLinkedList(p, 0, 0);
UpdateLinkedList(p, 9, 5);
DeleteLinkedList(p, 2);
//ClearLinkedList(p);
PrintLinkedList(p);
printf("%d\n", getLinkedListNum(p));
printf("%d\n", indexOfLinkedList(p, 5));
printf("%d\n", getLinkedList(p, 25));
system("pause");
return 0;
}