线表、堆栈、链表c语言程序.doc

#include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType;typedef int Status;typedef structElemType *elem;int length;/当前线性表长度int listsize;/线性表的最大长度SqList;/初始化线性表，引用就是别名，用&表示，来自于C+Status InitList_Sq(SqList &L)/分配了一个空线性表的总的空间,返回值为1表示分配成功,否则失败返回0L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);/ElemType elem100;if( !L.elem ) exit(OVERFLOW); /空线性表L.length = 0;/线性表容量L.listsize = LIST_INIT_SIZE; return OK; / 在顺序线性表L的第i个元素之前插入新的元素e，Status ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4 / i的合法值为1iListLength_Sq(L)+1 ElemType *p; if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = &(L.elemi-1); / q为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; / ListInsert_Sq/ 在顺序线性表L中删除第i个元素，并用e返回其值。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / i的合法值为1iListLength_Sq(L)。 ElemType *p, *q; if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK; / ListDelete_Sq/ 已知顺序线性表La和Lb的元素按值非递减排列。void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 算法2.7 / 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。 ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType); if (!Lc.elem) exit(OVERFLOW); / 存储分配失败 pa_last = La.elem+La.length-1; pb_last = Lb.elem+Lb.length-1; while (pa = pa_last & pb = pb_last) / 归并 if (*pa = *pb) *pc+ = *pa+; else*pc+ = *pb+; while (pa = pa_last) *pc+ = *pa+; / 插入La的剩余元素 while (pb = pb_last) *pc+ = *pb+; / 插入Lb的剩余元素 / MergeList/线性表遍历void TranverseList_Sq(SqList &L)for(int counter=0; counterL.length; counter+)printf(%d , L.elemcounter);printf(n);void main()SqList L;if(!InitList_Sq(L)printf(线性表创建失败n);exit(ERROR);int length;printf(请输入元素个数n);scanf(%d,&length);printf(请输入%d个元素n,length);for(int counter=0; counterlength; counter+)scanf(%d, &L.elemcounter); L.length = length;printf(线性表中元素是n);TranverseList_Sq(L);printf(请输入插入元素的位置n);int position;scanf(%d, &position);printf(请输入插入元素的值n);ElemType value;scanf(%d, &value);ListInsert_Sq(L,position,value);printf(插入新元素后，线性表中元素是n);TranverseList_Sq(L); #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType;typedef int Status;typedef struct SElemType *base;SElemType *top; int stacksize;SqStack;Status InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; Status Push(SqStack &S, SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top = S.base+S.stacksize;S.stacksize += STACKINCREMENT;*S.top = e;S.top+;return OK; Status Pop(SqStack &S, SElemType &e)if(S.top = S.base)return ERROR;S.top-;e = *S.top;return OK; void main() SqStack S; if(!InitStack(S) printf(堆栈创建失败n); exit(ERROR); int length; printf(请输入元素个数n);#include #include #define TRUE 1 #define FALSE 0 #define OK 1#define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2#define LIST_INIT_SIZE 100 #define STACK_INIT_SIZE 100 #define LISTINCREMENT 10 #define STACKINCREMENT 10typedef int QlemType; typedef int Status; typedef int QElemType;typedef struct QNode QElemType data;struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear; LinkQueue;#include #include #includetypedef struct node char data; struct node *lchild; struct node *rchild; tnode;tnode *createtree() tnode *t; char ch; ch=getchar(); if(ch=0) t=NULL; else t=(tnode *)malloc(sizeof(tnode); t-data=ch; t-lchild=createtree(); t-rchild=createtree(); return t; void listtree(tnode *t) if (t!=NULL) printf(%c,t-data); if(t-lchild!=NULL|t-rchild!=NULL) printf(); listtree(t-lchild); if(t-rchild!=NULL) printf(,); listtree(t-rchild); printf(); /递归先序遍历二叉树void preorder(tnode *t) if(t!=NULL) printf(%c ,t-data);preorder(t-lchild); preorder(t-rchild); /递归中序遍历二叉树void inorder(tnode *t) if(t!=NULL) inorder(t-lchild); printf(%c ,t-data); inorder(t-rchild); /递归后序遍历二叉树void postorder(tnode *t) if(t!=NULL) postorder(t-lchild); postorder(t-rchild); printf(%c ,t-data); /层次遍历void level(tnode *t)tnode *queue100; int front,rear; front=-1; rear=0; queuerear=t; while(front!=rear) front+;printf(%c ,queuefront-data);if(queuefront-lchild!=NULL)rear+;queuerear=queuefront-lchild;if(queuefront-rchild!=NULL)rear+;queuerear=queuefront-rchild; void main() tnode *t=NULL; printf(请输入二叉树元素：); t=createtree(); printf(广义表的输出：); listtree(t); printf(n); printf(二叉树的先序遍历：); preorder(t); printf(n); printf(二叉树的中序遍历：); inorder(t); printf(n); printf(二叉树的后序遍历：); postorder(t); printf(n); printf(二叉树的层次遍历：); level(t); printf(n); #include #include #define MAXSIZE 20typedef structint rMAXSIZE+1;int length; SortList;void InsertSort(SortList *L)for(int i=2; ilength; i+)L-r0 = L-ri;for(int j=i-1; L-r0rj; j-)L-rj+1 = L-rj;L-rj+1 = L-r0;void display(SortList *L)for(int i=1; ilength; i+)printf(%d , L-ri);printf(n);void main()int size;SortList *list;list = (SortList *)malloc(sizeof(SortList);printf(请输入线性表表长n);scanf(%d, &size);list-length = size;for(int counter=1; counterrcounter); printf(进行排序前线性表元素是n); display(list); InsertSort(list); printf(进行排序后线性表元素是n); display(list); #include #include #includelist.htypedef structSElemType *base