带表头节点单链表及其基本应用

• 结构体及其宏定义和所需要的C语言库

#include 
#include 
#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 
#include 
#include 
#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;
}

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