一、静态链表概念
用数组描述的链表,即称为静态链表。
在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 <stdio.h>#include <malloc.h>#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