首先定义结构体存放该结点的数据和下一个结点的int类型的下标next，通过下标next来访问整个链表。同时再定义一个结构体来表明开辟的空间是否存有数据如果有数据则used的值为1，没有存数据则used的值为0。本质上静态链表就是以数组的形式来存储数据的，只是在存储数据时多了下一个结点的下标。
上代码
//宏定义整个链表的大小
#define DEFAULT_SIZE 5
//创建结点
typedef struct StaticLinkedNode
{
char data;
int next;
} *NodePtr;
typedef struct StaticLinkedList
{
NodePtr nodes;
int *used;
} *ListPtr;
//头结点的初始化
ListPtr initLinkedList()
{
ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticLinkedList));
tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE);
tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE);
tempPtr->nodes[0].data = ' ';
tempPtr->nodes[0].next = -1;
tempPtr->used[0] = 1;
for(int i = 1; i < DEFAULT_SIZE; i++)
{
tempPtr->used[i] = 0;
}
return tempPtr;
}
添加元素
//插入元素
void insertElement(ListPtr paraListPtr,char paraChar,int paraPosition)
{
int p,q,i;
//刚开始插入到时候必须从0的位置插入，不能随意的选择一个位置插入
p = 0;
for(i = 0; i < paraPosition; i++)
{
p = paraListPtr->nodes[p].next;
if(p == -1)
{
printf("The position %d is beyond the scope of the list.n",paraPosition);
return;
}
}
//找到没有数据的空间的地址
for(i = 1; i < DEFAULT_SIZE; i++)
{
if(paraListPtr->used[i] == 0)
{
printf("Space at %d allocated.n",i);
paraListPtr->used[i] = 1;//再插入元素后该位置就有数据了used = 1
q = i;
break;
}
}
if(i == DEFAULT_SIZE)
{
printf("No space!n");
return;
}
paraListPtr->nodes[q].data = paraChar;
printf("linkingn");
paraListPtr->nodes[q].next = paraListPtr->nodes[p].next;
paraListPtr->nodes[p].next = q;
}
删除元素
void deleteElement(ListPtr paraListPtr,char paraChar)
{
int p,q;
//定位要删除的值
p = 0;
while((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data) != paraChar)
{
p = paraListPtr->nodes[p].next;
}
if (paraListPtr->nodes[p].next == -1)
{
printf("Can not locate the %c,can not delete!n",paraChar);
return;
}
//将要删除的结点的上一个结点的下标next改为要删除的结点的下标，在遍历的时候就可以跳过要删除的结点
q = paraListPtr->nodes[p].next;
paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next;
//因为删除了该结点所以该结点对应的used改为0
paraListPtr->used[q] = 0;
}
打印链表
//打印整个链表
void printList(ListPtr paraListPtr)
{
int p = 0;
while(p != -1)
{
printf("%c",paraListPtr->nodes[p].data);
p = paraListPtr->nodes[p].next;
}
printf("n");
}
全部代码
#include#include //宏定义整个链表的大小 #define DEFAULT_SIZE 5 //创建结点 typedef struct StaticLinkedNode { char data; int next; } *NodePtr; typedef struct StaticLinkedList { NodePtr nodes; int *used; } *ListPtr; //头结点的初始化 ListPtr initLinkedList() { ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticLinkedList)); tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE); tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE); tempPtr->nodes[0].data = ' '; tempPtr->nodes[0].next = -1; tempPtr->used[0] = 1; for(int i = 1; i < DEFAULT_SIZE; i++) { tempPtr->used[i] = 0; } return tempPtr; } //打印整个链表 void printList(ListPtr paraListPtr) { int p = 0; while(p != -1) { printf("%c",paraListPtr->nodes[p].data); p = paraListPtr->nodes[p].next; } printf("n"); } //插入元素 void insertElement(ListPtr paraListPtr,char paraChar,int paraPosition) { int p,q,i; //刚开始插入到时候必须从0的位置插入，不能随意的选择一个位置插入 p = 0; for(i = 0; i < paraPosition; i++) { p = paraListPtr->nodes[p].next; if(p == -1) { printf("The position %d is beyond the scope of the list.n",paraPosition); return; } } //找到没有数据的空间的地址 for(i = 1; i < DEFAULT_SIZE; i++) { if(paraListPtr->used[i] == 0) { printf("Space at %d allocated.n",i); paraListPtr->used[i] = 1;//再插入元素后该位置就有数据了used = 1 q = i; break; } } if(i == DEFAULT_SIZE) { printf("No space!n"); return; } paraListPtr->nodes[q].data = paraChar; printf("linkingn"); paraListPtr->nodes[q].next = paraListPtr->nodes[p].next; paraListPtr->nodes[p].next = q; } void deleteElement(ListPtr paraListPtr,char paraChar) { int p,q; //定位要删除的值 p = 0; while((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data) != paraChar) { p = paraListPtr->nodes[p].next; } if (paraListPtr->nodes[p].next == -1) { printf("Can not locate the %c,can not delete!n",paraChar); return; } //将要删除的结点的上一个结点的下标next改为要删除的结点的下标，在遍历的时候就可以跳过要删除的结点 q = paraListPtr->nodes[p].next; paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next; //因为删除了该结点所以该结点对应的used改为0 paraListPtr->used[q] = 0; } void appendInsterDeleteTest() { ListPtr tempList = initLinkedList(); printList(tempList); insertElement(tempList,'H',0); insertElement(tempList,'e',1); insertElement(tempList,'l',2); insertElement(tempList,'l',3); insertElement(tempList,'o',4); printList(tempList); printf("Deleting,'a'n"); deleteElement(tempList,'a'); printList(tempList); printf("Deleting,'e'n"); deleteElement(tempList,'e'); printList(tempList); printf("Deleting,'o'n"); deleteElement(tempList,'o'); printList(tempList); insertElement(tempList,'x',1); printList(tempList); } int main() { appendInsterDeleteTest(); return 0; }
测试结果
Space at 1 allocated. linking Space at 2 allocated. linking Space at 3 allocated. linking Space at 4 allocated. linking No space! Hell Deleting,'a' Can not locate the a,can not delete! Hell Deleting,'e' Hll Deleting,'o' Can not locate the o,can not delete! Hll Space at 2 allocated. linking Hxll
相比单链表静态链表的空间是固定的这样有可能造成空间的浪费比如申请了100个单位的空间但是只存储了50单位的数据这样剩下的空间任然存在造成空间的浪费。
在单链表的遍历中是通过指针域next来访问的，而静态链表是通过int类型的next为数组的下标来访问的。
