线性表、堆栈、链表c语言程序

1、#include<stdio.h>#include<stdlib.h>#define true 1#define false 0#define ok 1#define error 0#define infeasible-1#define overflow -2#define l1st_1nit_s1ze 100#define listincrement 10typedef int elemtype;typedef ini status;typedef struct elemtype *elem;int length;/当前线性表长度int listsize;/线性表的最

2、大长度sqlist;初始化线性表，引用就是别名，用&表示，来自于c+status lnitlist_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,stat

3、us listlnsert_sq(sqlist &l, int i, elemtype e)/算法2.4i 的合法值为 lwiwlistlength_sq(l)+lelemtype *p;if (i < 1 | i > l.length+1) return error; i 值不合法if (l.length >= l.listsize)/当前存储空间已满，增加容量elemtype *newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*sizeof (elemtype);if (inewbase

4、) return error; /存储分配失败l.elem = newbase;/ 新基址l.listsize + 二 listincrement; / 增加存储容量 elemtype *q = &(l.elemi-1);/ q 为插入位置for (p = &(l.elemlengthl); p>=q; -p)*(p+l) = *p；/插入位置及之后的元素右移*q = e;/ 插入 e+l.length;/ 表长增 1return ok;)/ listinsert_sq/在顺序线性表l中删除第i个元素，并用e返回其值。status listdelete_sq(sqlist

5、 &l, int i, elemtype &e) /算法2.5i 的合法值为 1 wiwlistlength_sq(l)。elemtype *p, *q;if (i<l | i>l.length)return error; i 值不合法 )p = &(l.elemi-1);p为被删除元素的位置e = *p;/被删除元素的值赋给eq = l.elem+l.length-1;/ 表尾元素的位置for (+p; p<=q; +p) *(p-l) = *p;/被删除元素之后的元素左移-l.length;/ 表长减 1return ok; / listdelet

6、e_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(lcistsize*sizeof(elemtype);if

7、(ilc.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 <= pajast)*pc+ = *pa+;/插入la的剩余元素while (pb <= pbast)*pc+二*pb+;/插入lb的剩余元素 / mergelist线性表遍

8、历void tranverselist_sq(sqlist &l) for(int counter=0; counter<l.length; counter+) printf(n%d", l.elemcounter);)printf(unu);void main() sqlist l;if(!initlist_sq(l)printfc线性表创建失败n“)；exit(error); int length;printfc'is输入元素个数n”)； scanf("%d",&length);printf(”请输入d 个元素nu,length)

9、;for(int counter=0; counter<length; counter+) scanf(”d”，&l.elemcounter); length = length;print”线性表中元素是n”);tranverselist_sq(l);printf(n请输入插入元素的位置n");int position;scanf("%d", &position);printfc '请输入插入元素的值n”);elemtype value;scanf(”d", &value);listinsert_sq(l,posit

10、ion,value);printf(“插入新元素后,线性表中元素是n“);tranverselist_sq(l);)#include<stdio.h>#include<stdlib.h>#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 10typedef int elemtype;typedef int status;typedef st

11、ruct selemtype *base;selemtype *top;int stacksize;jsqstack;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.stacksi

12、ze)s.base=(selemtype*)reanoc(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 &c)if(s.top = s.base)return error; s.top-;e = *s.top;return o

13、k; void main() sqstack s;if(!lnitstack(s)printf(”堆栈创建失败n”);exit(error); int length;printf(”请输入元素个数n”);#include<stdio.h> #include<stdlib.h> #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

14、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 struct queueptr front;queueptr rear;linkqueue;#include <stdio.h>#include <stdlib.h># includ

15、e<malloc.h>typedef struct node char data;struct node *lchild;struct node *rchild;jtnode;tnode *createtree() tnode *t;char ch;ch=getchar();if(ch='0,)匸 null;else t=(tnode *)malloc(sizeof(tnode); t->data=ch;t->lchild=createtree();t->rchild=createtree(); return t; void listtree(tnode

16、*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(h%c ",t->data);preorder(t->lchild);pre

17、order(t->rchild); )递归中序遍历二叉树void inorder(tnode *t) if(t!=null) inorder(t->lchild); printf(m%c *',t->data);inorder(t->rchild); /递归后序遍历二叉树void postorder(tnode *t) if(t!=null) postorder(t->lchild); postorder(t->rchild); printf(n%c t->data); 层次遍历void level(tnode *t) tnode *queue

18、 100;int front,rear;front二 1;rear=0; queuerearl=t;while(front! =rear)front+; printf(u%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（”请输入二叉树元素:

19、"）;t=createtree();printfc广义表的输出：”）；listtree(t);printf(mnm);printf(''二叉树的先序遍历:”);preorder(t);printf(mnh);printf（"二叉树的中序遍历：”）；inorder（t）;printfcan0);printf(h二叉树的后序遍历：”); postorder(t);printfcvn*'); printf(m二叉树的层次遍历：”);level(t); printf(,'nn); #include<stdio.h>#include<

20、stdlib.h>#define maxsize 20typedef struct int ijmaxsize+1; int length; jsortlist;void insertsort(sortlist *l) for(int i=2; i<=l->length; i+)l->rloj = l->rlij;for(int j=i-l; l->r0<l->rj; j-)l->rj+l = l->rfj; l->rj+l = l->r0;void display(sortlist *l) for(int i=l; i&

21、lt;=l->length; i+)printfcd h, l->ri);)printf("nu);void main() int size; sortlist *】ist;list = (sortlist *)malloc(sizeof(sortlist);printf(”请输入线性表表长n”)；scanf(”d”, &size); list->length = size;for(int counter= 1; counter<=size; counter+) printf("ih输入线性表的第<1个元素n",counter);scanf("%d", &list->rcounter); printf(”进行排序前线性表元素是n”);display(list);#include<stdio.h>#include<stdlib.h