2022年线性表、堆栈、链表c语言程序 .pdf

《2022年线性表、堆栈、链表c语言程序 .pdf》由会员分享，可在线阅读，更多相关《2022年线性表、堆栈、链表c语言程序 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#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 ElemType*elem;int length;/当前线性表长度int listsize;/线性表的最大长度SqList;/初始化线性表，引用就是别名，用&表示，来自

2、于C+Status InitList_Sq(SqList&L)/分配了一个空线性表的总的空间,返回值为 1 表示分配成功,否则失败返回0 L.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

3、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;/增加存储容量 Elem

4、Type*q=&(L.elemi-1);/q 为插入位置名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -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.

5、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 的元素也按值非递减排列。E

6、lemType*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

7、+;else *pc+=*pb+;while(pa=pa_last)*pc+=*pa+;/插入 La 的剩余元素 while(pb=pb_last)*pc+=*pb+;/插入 Lb 的剩余元素 /MergeList 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -/线性表遍历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)pri

8、ntf(线性表创建失败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 v

9、alue;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;名

10、师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -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)i

11、f(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

12、;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 STACKINCREM

13、ENT 10 typedef int QlemType;typedef int Status;typedef int QElemType;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;#include#include#include typedef struct node char data;struct node*lchi

14、ld;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)

15、;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)名师资料总结-精品资料欢迎下载

16、-名师精心整理-第 5 页，共 7 页 -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-r

17、child!=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);#i

18、nclude#include#define MAXSIZE 20 typedef struct int 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;li

19、st=(SortList*)malloc(sizeof(SortList);printf(请输入线性表表长n);scanf(%d,&size);list-length=size;for(int counter=1;counterrcounter);printf(进行排序前线性表元素是n);display(list);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -InsertSort(list);printf(进行排序后线性表元素是n);display(list);#include#include#includelist.h typedef struct SElemTy

20、pe*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.ba

21、se=(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;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -