帶表頭節點單鏈表及其基本應用

• 結構體及其宏定義和所需要的C語言庫

#include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 #define Overflow 2 //表示上溢 #define Underflow 3 //表示下溢 #define NotPresent 4 //表示元素不存在 #define Duplicate 5 //表示有重復元素 #define ElemType int //想要存儲的數據類型， 可修改#define Status int typedef struct node {ElemType element; //結點的數據域struct node *link; //結點的指針域 }Node; typedef struct headerList {Node *head;int n; }HeaderList;

• 初始化

Status Init(HeaderList *h) {h->head = (Node*)malloc(sizeof(Node)); //生成頭節點if (!h->head) return ERROR;h->head->link = NULL; //空鏈表h->n = 0;return OK; }

• 插入

Status Insert(HeaderList *h, int i, ElemType x) {Node *p, *q;int j;if (i < -1 || i > h->n - 1)return ERROR;p = h->head;for (j = 0; j <= i; j++)p = p->link;q = (Node*)malloc(sizeof(Node));q->element = x;q->link = p->link;p->link = q;h->n++;return OK; }

• 刪除

Status Delete(HeaderList *h, int i) {int j;Node *p, *q;if (!h->n)return ERROR;if (i<0 || i>h->n - 1)return ERROR;q = h->head;for (j = 0; j < i; j++)q = q->link;p = q->link;q->link = p->link;free(p);h->n--;return OK; }

• 查找

Status Find(HeaderList *h, int i, int *x) {int j;Node *q;if (i < -1 || i > h->n - 1)return ERROR;q = h->head->link;for (j = 0; j < i; j++)q = q->link;*x = q->element; //將該值傳遞回去return OK; }

• 輸出

Status Output(HeaderList *h) {Node *q;if (!h->n)return ERROR;q = h->head->link;while (q){printf("%d ", q->element);q = q->link;}putchar('\n');return OK; }

• 撤銷

void Destory(HeaderList *h) {Node *p, *q;p = h->head;while (p){q = p;p = p->link;free(q);q = NULL;} }

• 逆置

Status Inverse(HeaderList *h) {int i, j, temp;int m;Node *p, *q;i = h->n / 2;if (!h->n)return ERROR;for (j = 0; j < i; j++){p = q = h->head->link;for (m = 0; m < j; m++)q = q->link;for (m = 0; m < h->n - 1 - j; m++)p = p->link;temp = p->element;p->element = q->element;q->element = temp;}return OK; }

• 交換

Status Swap(HeaderList *h, int i, int j) {int temp, k;Node *p, *q;p = q = h->head->link;if (!h->n)return ERROR;if (i < -1 || i > h->n - 1)return ERROR;if (j < -1 || j > h->n - 1)return ERROR;for (k = 0; k < j; k++)q = q->link;for (k = 0; k < i; k++)p = p->link;temp = p->element;p->element = q->element;q->element = temp;return OK; }

• 排序

Status Sort(HeaderList *h) {int i, j, a, b;Find(h, 0, &a);for (i = 0; i < h->n - 1; i++){Find(h, i, &a);for (j = i; j < h->n; j++){Find(h, j, &b);if (a > b){temp = a;a = b;b = temp;Swap(h, i, j);}}}return OK; }

• 隨便驗證了一下

int main() {int i;HeaderList list;Init(&list);srand(time(NULL));for (i = 0; i < 10; i++)Insert(&list, i - 1, rand() % 20);Output(&list);Inverse(&list);Output(&list);Sort(&list);Output(&list);Destory(&list);return 0; }

源代碼

#include <stdio.h> #include <stdlib.h> #include <time.h> #define ERROR 0 #define OK 1 #define Overflow 2 //表示上溢 #define Underflow 3 //表示下溢 #define NotPresent 4 //表示元素不存在 #define Duplicate 5 //表示有重復元素 #define ElemType int //想要存儲的數據類型， 可修改#define Status int typedef struct node {ElemType element; //結點的數據域struct node *link; //結點的指針域 }Node; typedef struct headerList {Node *head;int n; }HeaderList;//初始化 Status Init(HeaderList *h) {h->head = (Node*)malloc(sizeof(Node)); //生成頭節點if (!h->head)return ERROR;h->head->link = NULL; //空鏈表h->n = 0;return OK; }//插入 Status Insert(HeaderList *h, int i, ElemType x) {Node *p, *q;int j;if (i < -1 || i > h->n - 1)return ERROR;p = h->head;for (j = 0; j <= i; j++)p = p->link;q = (Node*)malloc(sizeof(Node));q->element = x;q->link = p->link;p->link = q;h->n++;return OK; }//刪除 Status Delete(HeaderList *h, int i) {int j;Node *p, *q;if (!h->n)return ERROR;if (i<0 || i>h->n - 1)return ERROR;q = h->head;for (j = 0; j < i; j++)q = q->link;p = q->link;q->link = p->link;free(p);h->n--;return OK; }//查找 Status Find(HeaderList *h, int i, int *x) {int j;Node *q;if (i < -1 || i > h->n - 1)return ERROR;q = h->head->link;for (j = 0; j < i; j++)q = q->link;*x = q->element; //將該值傳遞回去return OK; }//輸出 Status Output(HeaderList *h) {Node *q;if (!h->n)return ERROR;q = h->head->link;while (q){printf("%d ", q->element);q = q->link;}putchar('\n');return OK; }//撤銷 void Destory(HeaderList *h) {Node *p, *q;p = h->head;while (p){q = p;p = p->link;free(q);q = NULL;} }//逆置 Status Inverse(HeaderList *h) {int i, j, temp;int m;Node *p, *q;i = h->n / 2;if (!h->n)return ERROR;for (j = 0; j < i; j++){p = q = h->head->link;for (m = 0; m < j; m++)q = q->link;for (m = 0; m < h->n - 1 - j; m++)p = p->link;temp = p->element;p->element = q->element;q->element = temp;}return OK; }//交換 Status Swap(HeaderList *h, int i, int j) {int temp, k;Node *p, *q;p = q = h->head->link;if (!h->n)return ERROR;if (i < -1 || i > h->n - 1)return ERROR;if (j < -1 || j > h->n - 1)return ERROR;for (k = 0; k < j; k++)q = q->link;for (k = 0; k < i; k++)p = p->link;temp = p->element;p->element = q->element;q->element = temp;return OK; }//排序 Status Sort(HeaderList *h) {int i, j, a, b, temp;for (i = 0; i < h->n - 1; i++){Find(h, i, &a);for (j = i + 1; j < h->n; j++){Find(h, j, &b);if (a > b){temp = a;a = b;b = temp;Swap(h, i, j);}}}return OK; }int main() {int i;HeaderList list;Init(&list);srand(time(NULL));for (i = 0; i < 10; i++)Insert(&list, i - 1, rand() % 20);Output(&list);Inverse(&list);Output(&list);Sort(&list);Output(&list);Destory(&list);return 0; }

總結

以上是生活随笔為你收集整理的带表头节点单链表及其基本应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。