一、静态链表概念

用数组描述的链表，即称为静态链表。

在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标。

优点：

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

二、代码实现

1.构建结构体

typedef struct StaticLinkedNode{char data;int next;
} *NodePtr;typedef struct StaticLinkedList{NodePtr nodes;int* used;
} *ListPtr;

2.初始化结构体

ListPtr initLinkedList(){// The pointer to the whole list space.ListPtr tempPtr = (ListPtr)malloc(sizeof(StaticLinkedList));// Allocate total space.tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE);tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE);// The first node is the header.tempPtr->nodes[0].data = '\0';tempPtr->nodes[0].next = -1;// Only the first node is used.tempPtr->used[0] = 1;for (int i = 1; i < DEFAULT_SIZE; i ++){tempPtr->used[i] = 0;}// Of for ireturn tempPtr;
}

3.打印结点

void printList(ListPtr paraListPtr){int p = 0;while (p != -1) {printf("%c", paraListPtr->nodes[p].data);p = paraListPtr->nodes[p].next;}// Of whileprintf("\r\n");
}

4.插入元素

void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition){int p, q, i;// Step 1. Search to the position.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.\r\n", paraPosition);return;}// Of if} // Of for i// Step 2. Construct a new node.for (i = 1; i < DEFAULT_SIZE; i ++){if (paraListPtr->used[i] == 0){// This is identical to malloc.printf("Space at %d allocated.\r\n", i);paraListPtr->used[i] = 1;q = i;break;}// Of if}// Of for iif (i == DEFAULT_SIZE){printf("No space.\r\n");return;}// Of ifparaListPtr->nodes[q].data = paraChar;// Step 3. Now link.printf("linking\r\n");paraListPtr->nodes[q].next = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = q;
}

5.删除元素

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;}// Of whileif (paraListPtr->nodes[p].next == -1) {printf("Cannot delete %c\r\n", paraChar);return;}// Of ifq = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next;// This statement is identical to free(q)paraListPtr->used[q] = 0;
}// Of deleteElement/*** Unit test.*/
void appendInsertDeleteTest(){// Step 1. Initialize an empty list.ListPtr tempList = initLinkedList();printList(tempList);// Step 2. Add some characters.insertElement(tempList, 'H', 0);insertElement(tempList, 'e', 1);insertElement(tempList, 'l', 2);insertElement(tempList, 'l', 3);insertElement(tempList, 'o', 4);printList(tempList);// Step 3. Delete some characters (the first occurrence).printf("Deleting 'e'.\r\n");deleteElement(tempList, 'e');printf("Deleting 'a'.\r\n");deleteElement(tempList, 'a');printf("Deleting 'o'.\r\n");deleteElement(tempList, 'o');printList(tempList);insertElement(tempList, 'x', 1);printList(tempList);
}

6.原代码展示

#include 
#include #define DEFAULT_SIZE 5typedef struct StaticLinkedNode{char data;int next;
} *NodePtr;typedef struct StaticLinkedList{NodePtr nodes;int* used;
} *ListPtr;/*** Initialize the list with a header.* @return The pointer to the header.*/
ListPtr initLinkedList(){// The pointer to the whole list space.ListPtr tempPtr = (ListPtr)malloc(sizeof(StaticLinkedList));// Allocate total space.tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE);tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE);// The first node is the header.tempPtr->nodes[0].data = '\0';tempPtr->nodes[0].next = -1;// Only the first node is used.tempPtr->used[0] = 1;for (int i = 1; i < DEFAULT_SIZE; i ++){tempPtr->used[i] = 0;}// Of for ireturn tempPtr;
}// Of initLinkedList/*** Print the list.* @param paraListPtr The pointer to the list.*/
void printList(ListPtr paraListPtr){int p = 0;while (p != -1) {printf("%c", paraListPtr->nodes[p].data);p = paraListPtr->nodes[p].next;}// Of whileprintf("\r\n");
}// Of printList/*** Insert an element to the given position.* @param paraListPtr The position of the list.* @param paraChar The given char.* @param paraPosition The given position.*/
void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition){int p, q, i;// Step 1. Search to the position.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.\r\n", paraPosition);return;}// Of if} // Of for i// Step 2. Construct a new node.for (i = 1; i < DEFAULT_SIZE; i ++){if (paraListPtr->used[i] == 0){// This is identical to malloc.printf("Space at %d allocated.\r\n", i);paraListPtr->used[i] = 1;q = i;break;}// Of if}// Of for iif (i == DEFAULT_SIZE){printf("No space.\r\n");return;}// Of ifparaListPtr->nodes[q].data = paraChar;// Step 3. Now link.printf("linking\r\n");paraListPtr->nodes[q].next = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = q;
}// Of insertElement/*** Delete an element from the list.* @param paraHeader The header of the list.* @param paraChar The given char.*/
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;}// Of whileif (paraListPtr->nodes[p].next == -1) {printf("Cannot delete %c\r\n", paraChar);return;}// Of ifq = paraListPtr->nodes[p].next;paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next;// This statement is identical to free(q)paraListPtr->used[q] = 0;
}// Of deleteElement/*** Unit test.*/
void appendInsertDeleteTest(){// Step 1. Initialize an empty list.ListPtr tempList = initLinkedList();printList(tempList);// Step 2. Add some characters.insertElement(tempList, 'H', 0);insertElement(tempList, 'e', 1);insertElement(tempList, 'l', 2);insertElement(tempList, 'l', 3);insertElement(tempList, 'o', 4);printList(tempList);// Step 3. Delete some characters (the first occurrence).printf("Deleting 'e'.\r\n");deleteElement(tempList, 'e');printf("Deleting 'a'.\r\n");deleteElement(tempList, 'a');printf("Deleting 'o'.\r\n");deleteElement(tempList, 'o');printList(tempList);insertElement(tempList, 'x', 1);printList(tempList);
}// Of appendInsertDeleteTest/*** The entrance.*/
void main(){appendInsertDeleteTest();
}// Of main

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！