我們知道，數組結構的定義包括數組元素的邏輯關係、存儲實現和作用於元素之上的一些操作等三個方面。
一組數據元素的邏輯關係包括：線性關係，如數組；非線性關係，如樹、圖形關係等；
一組數據元素的存儲實現可以是順序、鏈式存儲實現以及索引、散列存儲實現。
對於一組數據元素的增、刪、改、查、遍歷等操作的限制或定義也可以定義出特定的數據結構。
當然，因為數據元素本身的特殊性，也可以區分出不同類別的數據結構。
在數據元素中增添一個指針域來實現數據元素之間的關連，這種鏈式存儲的數據結構稱為鏈表。
1 用鏈表實現棧
對於一組線性關係的數據元素，如果限制為只在一頭進行增、刪、訪問等操作，這樣的數據結構稱為棧，棧可以用數據實現，也可以用鏈表實現：
<code>#include <stdio.h>#include <stdlib.h>#define RogueValue -9999typedef struct node {int num;struct node *next;} Node, *NodePtr;typedef struct stackType {NodePtr top;} StackType, *Stack;Stack initStack();int empty(Stack);void push(Stack, int);int pop(Stack);int top(Stack S);Stack initStack() {Stack sp = (Stack) malloc(sizeof(StackType));sp -> top = NULL;return sp;}int empty(Stack S) {return (S -> top == NULL);}void push(Stack S, int n) {NodePtr np = (NodePtr) malloc(sizeof(Node));np -> num = n;np -> next = S -> top;// 新節點指針域指向棧頂S -> top = np;// 移動棧頂節點指向新節點}int pop(Stack S) {if (empty(S)) return RogueValue;int hold = S -> top -> num;NodePtr temp = S -> top;// 獲取棧頂節點指針，待釋放S -> top = S -> top -> next;// 棧頂節點指向下一個節點free(temp);return hold;}int top(Stack S) {if (empty(S)) return RogueValue;int hold = S -> top -> num;return hold;}int main() {int n;Stack S = initStack();printf("Enter some integers, ending with 0\\n");scanf("%d", &n);while (n != 0) {push(S, n);scanf("%d", &n);}printf("%d\\n",top(S));printf("Numbers in reverse order\\n");while (!empty(S))printf("%d ", pop(S));printf("\\n");system("pause");}/*Enter some integers, ending with 04 6 8 12 3 03Numbers in reverse order3 12 8 6 4*//<stdlib.h>/<stdio.h>/<code> 2 用數組實現隊列
對於線性關係的一組數據元素，如果限制為在一頭進行增，另一頭進行刪、訪問等操作，這樣的數據結構稱為隊列，棧可以用數據實現，也可以用鏈表實現：
<code>#include <stdlib.h>#include <stdio.h>typedef struct {int num;} QueueData;typedef struct node {QueueData data;struct node *next;} Node, *NodePtr;typedef struct queueType {NodePtr head, tail;} QueueType, *Queue;Queue initQueue() {Queue qp = (Queue) malloc(sizeof(QueueType));qp -> head = NULL;qp -> tail = NULL;return qp;}int empty(Queue Q) {return (Q -> head == NULL);}void enqueue(Queue Q, QueueData d) {NodePtr np = (NodePtr) malloc(sizeof(Node));np -> data = d;np -> next = NULL;if (empty(Q)) {Q -> head = np;Q -> tail = np;}else {Q -> tail -> next = np; // 連接新建節點Q -> tail = np;// 移動tail指針到新建節點}}QueueData dequeue(Queue Q) {if (empty(Q)) {printf("\\nAttempt to remove from an empty queue\\n");exit(1);}QueueData hold = Q -> head -> data;NodePtr temp = Q -> head;// 獲取準備移除的頭節點指針Q -> head = Q -> head -> next;// 移動head指針到鄰近節點if (Q -> head == NULL) Q -> tail = NULL;free(temp);return hold;}int main() {int n;QueueData temp;Queue Q = initQueue();printf("Enter a positive Multidigit integer: ");scanf("%d", &n);while (n > 0) {temp.num = n % 10;enqueue(Q, temp);n = n / 10;}printf("\\nDigits in reverse order: ");while (!empty(Q))printf("%d", dequeue(Q).num);printf("\\n");system("pause");}/*Enter a positive Multidigit integer: 34589Digits in reverse order: 98543*//<stdio.h>/<stdlib.h>/<code>－End－
分享到:
閱讀更多 小智雅匯 的文章
