数据结构-静态链表

概述本文章向大家介绍数据结构-静态链表，主要包括数据结构-静态链表使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

静态链表就是把链表与数组结合起来，也就是用数组描述的链表，即称为静态链表。

与线性表与数组的区别

首先同样是定义一个头文件在头文件中定义函数，宏和全局变量

#ifndef STATIClinkList_H_INCLUDED

#define STATIClinkList_H_INCLUDED

#include

#include

#define MAX_SIZE_SSL 10

#define OK 1

#define ERROR 0

//定义数据元素

typedef struct{

int ID;

char * name;

}ElementType;

/** 静态链表-就是一个结构数组 */

typedef struct{

ElementType data; //数据域

int next; //int cursor; 游标，如果为0表示无指向

}StaticlinkList[MAX_SIZE_SSL];

/** 初始化链表 */

voID InitStaticlinkList(StaticlinkList slList);

/** 向指定位置插入元素 */

int InsertStaticlinkList(StaticlinkList slList,int pos,ElementType element);

/** 为静态链表分配一个空间的内存，返回ERROR表示分配失败 */

int malloCSSL(StaticlinkList slList);

/** 删除链表中指定位置的元素 */

int DeleteStaticlinkList(StaticlinkList slList,int pos);

/** 回收原始数组中指定下标的空间 */

voID FreeStaticlinkList(StaticlinkList slList,int index);

/** 获得静态链表的长度 */

int GetStaticlinkList(StaticlinkList slList);

voID PrintStaticlinkList(StaticlinkList slList);

#endif // STATIClinkList_H_INCLUDED

下面在.c中对静态链表进行 *** 作

插入的过程相当于数组的位置没有改变但是改变了游标的指向，使之排列起来

#include "StaticlinkList.h"

/** 初始化链表 */

voID InitStaticlinkList(StaticlinkList slList)

{

for(int i = 0; i < MAX_SIZE_SSL; i++)

{

slList[i].data.ID = -1;

slList[i].data.name = NulL;

slList[i].next = i + 1;

}

//将最后一个结点置空

slList[MAX_SIZE_SSL - 1].next = 0;

//将备用链表的尾结点置为空

slList[MAX_SIZE_SSL - 2].next = 0;

}

/** 删除链表中指定位置的元素 */

int DeleteStaticlinkList(StaticlinkList slList,int pos){

if(pos < 1 || pos > GetStaticlinkList(slList)){

return ERROR;

}

int cursor = MAX_SIZE_SSL - 1;

//通过循环找到要删除位置的前缀结点

for(int i = 1; i <= pos - 1; i++){

cursor = slList[cursor].next;

}

int delindex = slList[cursor].next;

slList[cursor].next = slList[delindex].next;

//释放空间

FreeStaticlinkList(slList,delindex);

return OK;

}

/** 回收原始数组中指定下标的空间 */

voID FreeStaticlinkList(StaticlinkList slList,int index){

//将下标为index的空闲结点回收到备用链表

slList[index].next = slList[0].next;

//0号元素的next结点指向备用链表的第一个结点，表示index结点空闲

slList[0].next = index;

}

/** 向指定位置插入元素 */

int InsertStaticlinkList(StaticlinkList slList,ElementType element){

if(pos < 1 || pos > GetStaticlinkList(slList) + 1){

return ERROR;

}

int cursor = MAX_SIZE_SSL - 1; //拿到第一个元素的下标

//需要判断cursor的范围是否合法

//分配内存

int newIndex = malloCSSL(slList);

if(newIndex){

slList[newIndex].data = element;

//找到newIndex的前缀结点

for(int i = 1; i <= pos - 1; i++){

cursor = slList[cursor].next;

}

slList[newIndex].next = slList[cursor].next;

slList[cursor].next = newIndex;

return OK;

}

return ERROR;

}

/** 为静态链表分配一个空间的内存，返回ERROR表示分配失败 */

int malloCSSL(StaticlinkList slList){

//拿到第一个空闲结点下标（备用链表）下标

int cursor = slList[0].next;

if(cursor){

slList[0].next = slList[cursor].next;

}

return cursor;

}

/** 获得静态链表的长度 */

int GetStaticlinkList(StaticlinkList slList){

int count = 0;

int cursor = slList[MAX_SIZE_SSL - 1].next;

while(cursor){

//p = p->next

cursor = slList[cursor].next;

count++;

}

return count;

}

voID PrintStaticlinkList(StaticlinkList slList){

for(int i = 0; i < MAX_SIZE_SSL; i++)

{

printf("i:%dtnext:%dtID:%dtname:%sn",i,slList[i].next,slList[i].data.ID,slList[i].data.name);

}

}

总结

以上是内存溢出为你收集整理的数据结构-静态链表全部内容，希望文章能够帮你解决数据结构-静态链表所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。