《数据结构作业答案(大连理工大学)》由会员分享，可在线阅读，更多相关《数据结构作业答案(大连理工大学)（25页珍藏版）》请在金锄头文库上搜索。
1、作业1. 线性表l 编程作业：1 将顺序表逆置，要求用最少的附加空间。参考答案#include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct ElemType *elem; int length; int
2、 listsize; SqList;/创建空顺序表Status InitList_Sq( SqList &L ) L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;/顺序表在第i个元素之前插入eStatus sxbcr(SqList &L, int i, ElemType e) ElemType *p,*q;if(iL.length+1) return (ER
3、ROR); else q=&(L.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return (OK); /顺序表显示void xsList(SqList L)int i=L.length,k;for(k=0;ki;k+)printf(%d ,L.elemk);printf(n);/顺序表逆置void nizhi(SqList &L)int i=0,j=L.length-1; ElemType temp;for(;i10-20-30-40）;（3） InsertList()：在有序单链表中插入元素
4、x；（4） ReverseList()：单链表就地逆置；（5） DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct node ElemType data; struct nod
5、e *link;Lnode, *LinkList;/头插法建立单链表void Create_L1(LinkList &L, int n) LinkList p; int i; L=(LinkList)malloc(sizeof(Lnode); L-link = NULL; for (i = n; i 0; -i) p=(LinkList)malloc(sizeof(Lnode); scanf(%d,&p-data); p- link = L- link; L- link = p; /尾插法建立单链表void Create_L2(LinkList &L,int n) LinkList s, p;
6、 int i; L=(LinkList)malloc(sizeof(Lnode); L-data=0; L-link=NULL; p=L; for(i=1;idata);s-link=NULL;p-link=s;p=s; /查找是否存在结点eLinkList dlbcz(LinkList L, ElemType e) LinkList p=L-link; while(p!=NULL & p-data!=e) p=p-link; return (p);/在第i个元素之前插入结点eStatus ListInsert_L(LinkList L, int i, ElemType e) LinkList
7、 p = L,s; int j = 0; while (p & j link;+j; if (!p | j i-1) return ERROR; s = (LinkList) malloc ( sizeof (Lnode); s-data = e; s-link = p-link; p-link = s; return OK;/删除第i个结点Status ListDelete_L(LinkList L, int i, ElemType &e) LinkList p = L,q; int j = 0; while (p-link & j link; +j; if (!(p-link) | j i
8、-1) return ERROR; q=p-link; p-link=q-link; e=q-data; free(q); return OK;/求第i个元素值Status GetElem_L(LinkList L, int i, ElemType &e) int j=1; LinkList p=L-link; while(p&jlink; j+; if(!p|ji) return ERROR; e=p-data; return OK;/显示单链表中元素void xsList(LinkList L)LinkList p=L-link;while(p)printf(%d ,p-data);p=p
9、-link;/删除大于mink且小于maxk的元素void DelList(LinkList &L, ElemType mink, ElemType maxk)LinkList p=L,q;while(p-link&p-link-datalink;q=p;while(q&q-datalink;p-link=q;/就地升序排序void sh_sort(LinkList &L)LinkList p=L-link,pre=L,q=L-link-link,u;p-link=NULL;while(q)p=L-link;pre=L;while(p&p-datadata)pre=p;p=p-link;u=q-link;pre-link=q;q-link=p;q=u;/就地逆置void nizhi(LinkList &L)
