数据结构作业及答案.doc

上机实验的问题和要求：顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及有序表的形成、元素的查找、插入与删除。具体实现要求：1.从键盘输入n个整数，产生顺序表，并输入结点值;2.将已知的顺序表形成一个有序表（从小到大或从大到小）;3.从键盘输入1个待查找的整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”;4.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果;#include #include typedef int ElemType;struct List ElemType *list; int size;int MaxSize;void TraverseList(struct List *L) int i; for(i=0;isize;i+) printf(%d ,L-listi); printf(nn);void againMalloc(struct List *L) ElemType *p=realloc(L-list,2*L-MaxSize*sizeof(ElemType); if(!p) printf(存储空间用完!n); exit(1);L-list=p;L-MaxSize=2*L-MaxSize;void InsertPosList(struct List *L,int pos,ElemType x) int i; if(posL-size+1)exit(1);if(L-size=L-MaxSize)againMalloc(L);for(i=L-size-1;i=pos-1;i-)L-listi+1=L-listi;L-listpos-1=x;L-size+;void CreateList(struct List *L,int n) int i; if(nlist=malloc(n*sizeof(ElemType); L-MaxSize=n; printf(请输入%d个数：n,n); for(i=0;ilisti); L-size=n; printf(n);void OrderList(struct List *L)int i,j;ElemType t;for(i=0;isize-1;i+)for(j=0;jsize-1-i;j+)if(L-listjL-listj+1) t=L-listj;L-listj=L-listj+1;L-listj+1=t;void CheckList(struct List *L,ElemType x)int i;for(i=0;isize;i+)if(L-listi=x) break;if(i=L-size)printf(在线性表中找不到与%d相等的数!nn,x);elseprintf( 元素“%d”在数组存储空间的下标为%d的位置上。nn,x,i);void main()int m,p,q,k=10;struct List La;CreateList(&La,k);printf(第一小题,请输出线性表中的各元素：n); TraverseList(&La);OrderList(&La);printf(第二小题，请输入经排序后的线性表中的元素:n);TraverseList(&La);printf(第三小题，请输入要查找的整数：);scanf(%d,&m);CheckList(&La,m);printf(第四小题，请输入需要在线性表中插入数的位置和数值：);scanf(%d,%d,&p,&q);InsertPosList(&La,p,q);printf(在第%d个元素位置插入%d后，线性表为：n,p,q);TraverseList(&La);1.建立带头结点的单链表；2.输出带头结点的单链表；3.将单链表逆序链接，假定仍使用原有结点；4.以选择法对单链表进行排序；5.在主函数实现对上述四个函数的调用，输出运行结果。#include#includetypedef int ElemType;struct sNodeElemType data;struct sNode *next;void CreateHeadList(struct sNode* HL,int pos)struct sNode *p,*q,*h;int i;h=p=(struct sNode*)malloc(sizeof(struct sNode);printf(请输入%d个元素：n,pos);for(i=0;idata);p-next=q;p=q;p-next=NULL;*HL=h;printf(n);void TraverseList(struct sNode* HL)struct sNode *p=(*HL)-next;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(nn);void ContraryList(struct sNode* HL)struct sNode *p,*q;p=(*HL)-next;(*HL)-next=NULL;while(p!=NULL)q=p;p=p-next;q-next=(*HL)-next;(*HL)-next=q;void OrderList(struct sNode* HL)struct sNode *p,*q,*h;struct sNode *mp=*HL,*ap,*cp,*rp;p=(*HL)-next;while(p!=NULL)cp=p;q=p;while(q!=NULL)if(cp-dataq-data) cp=q;h=ap;ap=q;q=q-next; if(p!=cp) if(p-next=cp)p-next=cp-next;cp-next=p;mp-next=cp;elserp=cp-next;cp-next=p-next;p-next=rp;h-next=p;mp-next=cp;mp=cp;p=cp-next;void main()struct sNode *m;int i=0;printf(请输入要建立的单链表中元素的个数：); scanf(%d,&i);CreateHeadList(&m,i);printf(请输出单链表中存放的元素：n);TraverseList(&m);printf(对单链表进行逆序链接。n);ContraryList(&m);printf(请输出经逆序链接后的单链表中的元素：n);TraverseList(&m);printf(用选择法对单链表进行排序。n);OrderList(&m);printf(经排序后的单链表中的各元素依次为:n );TraverseList(&m);1 构建一个二叉排序树的二叉链表；2 编写一个非递归算法：删除二叉排序树上给定的元素值为x;3 编写一个非递归算法：求出二叉排序树中的关键字最大和最小的元素值；4 在主函数中输入有关构建二叉排序树的元素值（假设为整数），然后调用上述算法，并通过中序遍历算法的调用，验证上述算法是否正确。#include #include typedef int ElemType;struct BTreeNodeElemType data;struct BTreeNode* left;struct BTreeNode* right;void Inorder(struct BTreeNode* BST)if(BST!=NULL)Inorder(BST-left);printf(%d ,BST-data);Inorder(BST-right);void Insert(struct BTreeNode* BST,ElemType x)struct BTreeNode* p;struct BTreeNode* t=*BST,*parent=NULL;while(t!=NULL)parent=t;if(xdata) t=t-left;elset=t-right;p=malloc(sizeof(struct BTreeNode);p-data=x;p-left=p-right=NULL;if(parent=NULL)*BST=p;else if(xdata)parent-left=p;elseparent-right=p;void CreateBSTree(struct BTreeNode* BST,ElemType a,int n)int i;*BST=NULL;for(i=0;idata=x)ap=*BST;if(*BST)-left=NULL & (*BST)-right=NULL)*BST=NULL;return 0;elsewhile(p!=NULL)if(xdata)ap=p;p=p-left;k=0;else if(xp-data)ap=p;p=p-right;k=1;elsebreak;if(p=NULL)return 0;if(p-left=NULL)if(k=0)ap-left=p-right;elseap-right=p-right;free(p);return 1;else if(p-right=NULL)if(k=0)ap-left=p-left;elseap-right=p-left;free(p);return 1;elseif(p-left-right=NULL)p-data=p-left-data;p-left=p-left-left;free(p-left);return 1;elsestruct BTreeNode *p1,*ap1;p1=p-left;ap1=p;while(p1-right!=NULL)ap1=p1;p1=p1-right;p-data=p1-data;ap1-right=p1-left;return 1;ElemType CheckMin(struct BTreeNode *BST)if(BST=NULL)printf(二叉排序树为空，无最小值!n);exit(1);while(BST-left!=NULL)BST=BST-left;return BST-data;ElemType CheckMax(struct BTreeNode* BST)if(BST=NULL)printf(二叉排序树为空，无最大值!n);exit(1);while(BST-right!=NULL)BST=BST-right;return BST-data;void main()int i,j;ElemType max,min,x;ElemType a12;struct BTreeNode* bst=NULL;printf(请输入要建立二叉搜索树的12个元素：n);for(i=0;i12;i+)scanf(%d,&ai);printf(建立一个二叉排序树的二叉链表。n);CreateBSTree(&bst,a,12);printf(中序遍历二叉排序树:n );Inorder(bst);printf(n);printf(请输入要删除