队列的头文件
2010年10月05日 04:02 | Comments(1) | Category:C语言 | Tags:数据结构 循环队列 链式队列
/* 数据结构 队列的实现 Queue.h * author : star */ //防止重复定义 #ifndef QUEUE_H #define QUEUE_H #include "defs.h" //初始化大小为n的队列 int InitSqqueue(SQQUEUE *Q, int n) { Q->data = (ElemType *)malloc((n+1) * sizeof(ElemType)); if(Q->data == NULL) return 0; Q->front = Q->rear = 0; Q->size = n + 1; return 1; } //销毁队列 void DestroySqqueue(SQQUEUE *Q) { free(Q->data); Q->data = NULL; Q->front = Q->rear = Q->size = 0; } //判断队空还是满 int IsSqqueueEmpty(SQQUEUE Q) { return Q.front == Q.rear; } int IsSqqueueFull(SQQUEUE Q) { return Q.front == (Q.rear+1) % Q.size; } //入队 int EnSqqueue(SQQUEUE *Q, ElemType e) { if(IsSqqueueFull(*Q)) return 0; Q->data[Q->rear] = e; Q->rear = (Q->rear+1) % Q->size;\ return 1; } //出队 int DeSqqueue(SQQUEUE *Q, ElemType *e) { if(IsSqqueueFull(*Q)) return 0; *e = Q->data[Q->front]; Q->front = (Q->front+1) % Q->size; return 1; } //队列长度 int SqqueueLen(SQQUEUE Q) { return (Q.size + Q.rear + Q.front) % Q.size; } //初始化空链式队 void InitLkqueue(LKQUEUE *Q) { Q->front = Q->rear = NULL; } //销毁链式队列 void DestroyLkqueue(LKQUEUE *Q) { LQNODEPTR p; while(Q->front != NULL) { p = Q->front; Q->front = p->next; free(p); } Q->rear = NULL; } //入链队 int EnLkqueue(LKQUEUE *Q, ElemType e) { LQNODEPTR p; p = (LQNODEPTR)malloc(sizeof(LQNODE)); if(p == NULL) return 0; p->data = e; p->next = NULL; if(Q->front == NULL) Q->front = Q->rear = p; else Q->rear->next = Q->rear = p; return 1; } //出链队 int DeLkqueue(LKQUEUE *Q, ElemType *e) { LQNODEPTR p; if(Q->front == NULL) return 0; p = Q->front; Q->front = p->next; if(Q->front == NULL) Q->rear = NULL; *e = p->data; free(p); return 1; } #endif
栈的头文件
2010年10月05日 04:00 | Comments(2) | Category:C语言 | Tags:数据结构 栈 链式栈
/* 数据结构 栈的实现 Stack.h * author : star */ //防止重复定义 #ifndef STACK_H #define STACK_H #include "defs.h" //初始化大小为n的栈 int InitSqstack(SQSTACK *S, int n) { S->data = (ElemType *)malloc(n * sizeof(ElemType)); if(S->data == NULL) return 0; S->size = n; S->top = -1; return 1; } //销毁栈 void DestroySqstack(SQSTACK *S) { free(S->data); S->data = NULL; S->top = -1; S->size = 0; } //判断栈空、栈满 int IsSqstackEmpty(SQSTACK S) { return S.top == -1; } int IsSqstackFull(SQSTACK S) { return S.top == S.size-1; } //入栈 int PushS(SQSTACK *S, ElemType e) { if(IsSqstackFull(*S)) return 0; ++S->top; S->data[S->top] = e; return 1; } //出栈 int PopS(SQSTACK *S, ElemType *e) { if(IsSqstackEmpty(*S)) return 0; *e = S->data[S->top]; --S->top; return 1; } //初始化链式栈 int InitLinkstack(LINKSTACK *S) { *S = (LINKSTACK)malloc(sizeof(LSNODE)); if(*S == NULL) return 0; (*S)->next = NULL; return 1; } //销毁链式栈 int DestroyLinkstack(LINKSTACK *S) { LSNODEPTR q, p; p = *S; while(p) { q = p; p = p->next; free(q); } *S = NULL; } //判断链栈空、满 IsLinkstackEmpty(LINKSTACK S) { return S->next == NULL; } IsLinkstackFull(LINKSTACK S) { return S->next != NULL; } //入链栈 int PushL(LINKSTACK S, ElemType e) { LSNODEPTR p; p = (LSNODEPTR)malloc(sizeof(LSNODE)); if(p == NULL) return 0; p->data = e; p->next = S->next; S->next = p; return 1; } //出链栈 int PopL(LINKSTACK S, ElemType *e) { LSNODEPTR p; p = S->next; if(p == NULL) return 0; S->next = p->next; *e = p->data; free(p); return 1; } #endif
数据结构头文件Ver2.0
2010年10月05日 03:57 | Comments(1) | Category:C语言 | Tags:数据结构 链表 栈 队列
/* 数据结构 全部结构定义文件 defs.h * author : star */ //引入所有需要的头文件 #include <stdio.h> #include <stdlib.h> #include <string.h> //防止重复定义 #ifndef DEF_H #define DEF_H //定义执行状态返回结果 #define TRUE 1 //成功 #define FALSE 0 //失败 #ifndef FORMATSTR #define FORMATSTR "%d " //输出格式 typedef int ElemType; //基本数据类型 #endif //线性表 typedef struct { ElemType *data; //数据 int size; //容量 int len; //长度 }SQLIST; //单链表 typedef struct link_node { ElemType data; //数据 struct link_node *next; //结点 }NODE, *NODEPTR, *LINKLIST; //双向链表 typedef struct dlink_node { ElemType data; //数据 struct dlink_node *next, *prior; //前后结点 }DBNODE, *DBNODEPTR, *DBLINKLIST; //循环单向链表 原理同单链表 //循环双向链表 原理同双向链表 //静态链表 #define SLEN 512 //静态链表长度 typedef struct slink_node { ElemType data; //数据 int next; //指针 }SNODE, *SLINKLIST; /*静态链表是给没有指针的语言写的,C语言有指针,* *而且静态链表不实用,定义多而杂,因此不写了 */ //广义表 enum{ATOM,LIST}; typedef struct glist_node { int tag; //ATOM或LIST union { ElemType data; //ATOM struct glist_node *head; //LIST }item; struct glist_node *next; //结点 }GLNODE, *GLIST; //顺序栈 typedef struct { ElemType *data; //数据 int top; //栈顶 int size; //容量 }SQSTACK; //链式栈 typedef struct stack_node { ElemType data; //数据 struct stack_node *next; //结点 }LSNODE, *LSNODEPTR, *LINKSTACK; //顺序循环队列 typedef struct { ElemType *data; //数据 int front, rear; //队首与队尾 int size; //容量 }SQQUEUE; //链式队列 typedef struct queue_node //结点 { ElemType data; struct queue_node *next; }LQNODE, *LQNODEPTR; typedef struct { LQNODEPTR front, rear; //队首与队尾 }LKQUEUE; #endif
表的3个例子
2010年10月03日 21:00 | Comments(5) | Category:C语言 | Tags:c 双向链表 链表 线性表 数据结构
1.线性表的例子
#include "List.h" int data[5] = {2, 3, 6, 7, 11}; int main(void) { //线性表的简单示例 int i, j, k; SQLIST L; k = InitSqlist(&L, 10); //初始化线性表 if(k == 0) { puts("ERROR"); exit(-1); } for(i = 0; i < 5; ++i) AppendSqlistElem(&L, data[i]); //把data数据放入线性表 TraverseSqlist(L); //遍历线性表 putchar(10); j = SearchSqlist(L, 6); //查找数据6 DeleteSqlistElemAt(&L, j); //删除 InsertSqlistElemAt(&L, 5, j); //插入5 TraverseSqlist(L); DestroySqlist(&L); //销毁线性表 return 0; }
2.单链表的例子
#include "List.h" int data[5] = {2, 3, 6, 7, 11}; int main(void) { //链表示例 int i, j, k; LINKLIST L = NULL; NODEPTR S, SPRE; k = InitLinklist(&L); //初始化链表 if(k == 0) { puts("ERROR"); exit(-1); } for(i = 0; i < 5; ++i) AddLinklistElem(L, data[4-i]); //添加数据 TraverseLinklist(L); //遍历 putchar(10); DeleteLinklistElem(L, 6); //删除元素6 InsertLinklistElemAt(L, 5, 3); //插入元素5 TraverseLinklist(L); DestroyLinklist(&L); //释放表 return 0; }
3.双向链表的例子
#include "List.h" int data[5] = {2, 3, 6, 7, 11}; int main(void) { //双向链表的简单示例 int i, j, k; DBLINKLIST L; DBNODEPTR t; k = InitDBLinklist(&L); //初始化双向链表 if(k == 0) { puts("ERROR"); exit(-1); } for(i = 0, t = L; i < 5; ++i,t = t->next) InsertDBLinklistElemAfter(t, data[i]); //把data数据放入双向链表 TraverseDBLinklist(L); //遍历双向链表 putchar(10); t = SearchDBLinklist(L, 6); //找到6 DeleteDBLinklistElem(t); //删除6 t = SearchDBLinklist(L, 3); //找到3 InsertDBLinklistElemAfter(t, 5); //插入5 TraverseDBLinklist(L); DestroyDBLinklist(&L); //销毁双向链表 return 0; }
表的头文件
2010年10月03日 20:54 | Comments(1) | Category:C语言 | Tags:c 数据结构 线性表 链表 双向链表
/* 数据结构 表的实现 List.h * author : star */ //防止重复定义 #ifndef LIST_H #define LIST_H #include "defs.h" //初始化容量为n的线性表 //时间复杂度O(1) int InitSqlist(SQLIST *L, int n) { L->data = (ElemType *)malloc(n * sizeof(ElemType)); if(L->data == NULL) return 0; L->size = n; L->len = 0; return 1; } //销毁线性表 //时间复杂度O(1) void DestroySqlist(SQLIST *L) { free(L->data); L->data = NULL; L->size = 0; L->len = 0; } //判断线性表的空与满 //时间复杂度O(1) int IsSqlistFull(SQLIST L) { return L.len == L.size; } int IsSqlistEmpty(SQLIST L) { return L.len == 0; } //获取第i个数据 //时间复杂度O(1) //if(i >= 0 || i <= L->len) return L->data[i-1]; //追加数据 //时间复杂度O(1) int AppendSqlistElem(SQLIST *L, ElemType e) { if(IsSqlistFull(*L)) return 0; L->data[L->len] = e; ++L->len; return 1; } //在i(i>=0)处插入数据 //时间复杂度O(n) int InsertSqlistElemAt(SQLIST *L, ElemType e, int i) { int k; if(i > L->len || IsSqlistFull(*L)) return 0; for(k = L->len - 1; k >= i; --k) L->data[k+1] = L->data[k]; L->data[i] = e; ++L->len; return 1; } //删除表中i(i>=0)处的数据 //时间复杂度O(n) int DeleteSqlistElemAt(SQLIST *L, int i) { int k; if(i >= L->len || IsSqlistEmpty(*L)) return 0; for(k = i+1; k < L->len; ++k) L->data[k-1] = L->data[k]; --L->len; return 1; } //遍历线性表 //时间复杂度O(n) void TraverseSqlist(SQLIST L) { int i; for(i = 0; i < L.len; ++i) printf(FORMATSTR, L.data[i]); } //查找数据 //时间复杂度O(n) int SearchSqlist(SQLIST L, ElemType key) { int i; for(i = 0; i < L.len; ++i) if(L.data[i] == key) return i; return -1; } //初始化链表 //时间复杂度O(1) int InitLinklist(LINKLIST *L) { *L = (LINKLIST)malloc(sizeof(NODE)); if(*L == NULL) return 0; (*L)->next = NULL; return 1; } //销毁链表 //时间复杂度O(n) void DestroyLinklist(LINKLIST *L) { NODEPTR p, q; p = *L; while(p) { q = p; p = p->next; free(q); } *L = NULL; } //获取第i(i>=1)个元素 //时间复杂度O(n) NODEPTR GetLinklistElem(LINKLIST L, int i, NODEPTR *pre) { NODEPTR p; int k; p = L; k = 0; while(k < i && p != NULL) { *pre = p; p = p->next; ++k; } if(k < i) *pre = NULL; return p; } //添加数据 //时间复杂度O(1) int AddLinklistElem(LINKLIST L, ElemType e) { NODEPTR p; p = (NODEPTR)malloc(sizeof(NODE)); if(p == NULL) return 0; p->data = e; p->next = L->next; L->next = p; return 1; } //在i(i>=1)处插入数据 //时间复杂度O(n) int InsertLinklistElemAt(LINKLIST L, ElemType e, int i) { NODEPTR p, q, pre; q = (NODEPTR)malloc(sizeof(NODE)); if(q == NULL) return 0; q->data = e; p = GetLinklistElem(L, i, &pre); if(pre == NULL) return 0; q->next = p; pre->next = q; return 1; } //删除表中i(i>=1)处的数据 //时间复杂度O(n) int DeleteLinklistElemAt(LINKLIST L, int i) { NODEPTR p, pre; p = GetLinklistElem(L, i, &pre); if(p == NULL) return 0; pre->next = p->next; free(p); return 1; } //遍历线性表 //时间复杂度O(n) void TraverseLinklist(LINKLIST L) { NODEPTR p; p = L->next; while(p) { printf(FORMATSTR, p->data); p = p->next; } } //查找数据 //时间复杂度O(n) NODEPTR SearchLinklist(LINKLIST L, ElemType e, NODEPTR *pre) { NODEPTR p; *pre = L; p = L->next; while(p != NULL && p->data != e) { *pre = p; p = p->next; } if(p == NULL) *pre = NULL; return p; } //删除表中的数据 //时间复杂度O(n) int DeleteLinklistElem(LINKLIST L, ElemType e) { NODEPTR p, pre; p = SearchLinklist(L, e, &pre); if(p == NULL) return 0; pre->next = p->next; free(p); return 1; } //初始化链表 //时间复杂度O(1) int InitDBLinklist(DBLINKLIST *L) { *L = (DBLINKLIST)malloc(sizeof(DBNODE)); if(*L == NULL) return 0; (*L)->next = (*L)->prior = NULL; return 1; } //销毁双向链表 //时间复杂度O(n) void DestroyDBLinklist(DBLINKLIST *L) { DBNODEPTR p, q; p = *L; while(p) { q = p; p = p->next; free(q); } *L = NULL; } //在双向链表结点后插入元素 //时间复杂度O(1) int InsertDBLinklistElemAfter(DBNODEPTR p, ElemType e) { DBNODEPTR q; q = (DBNODEPTR)malloc(sizeof(DBNODE)); if(q == NULL) return 0; q->data = e; q->next = p->next; q->prior = p; if(p->next != NULL) p->next->prior = q; p->next = q; return 1; } //遍历双向链表 //时间复杂度O(n) void TraverseDBLinklist(DBLINKLIST L) { DBNODEPTR p; p = L->next; while(p) { printf(FORMATSTR, p->data); p = p->next; } } //删除双向链表中的某个结点 //时间复杂度O(1) void DeleteDBLinklistElem(DBNODEPTR p) { DBNODEPTR pre; pre = p->prior; if(pre != NULL) pre->next = p->next; if(p->next != NULL) p->next->prior = pre; free(p); } //查找双向链表的数据 //时间复杂度O(n) DBNODEPTR SearchDBLinklist(DBLINKLIST L, ElemType e) { DBNODEPTR p; p = L->next; while(p != NULL && p->data != e) p = p->next; return p; } #endif