数据结构(严蔚敏)上机代码完整版(共15页)

1、精选优质文档-倾情为你奉上数据结构第一、二次上机：#include <stdio.h>#include <malloc.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 10 /线性表存储空间的分配增量typedef int Status;typedef

2、 int ElemType;typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList;Status InitList_Sq(SqList &L)/构造一个空的线性表LL.elem =(ElemType * )malloc(list_init_size*sizeof(ElemType);if(!L.elem )exit(OVERFLOW);/存储分配失败L.length =0; /空表长度为0L.listsize =list_init

3、_size;/初始存储容量return OK;/Initlist_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在顺序线性表L中第i个位置之前插入新的元素e，/i的合法值为1<=i<=ListLength_Sq(L)+1ElemType *p,*q,*newbase; /定义指针if(i<1|i>L.length +1)return ERROR; /i值不合法if(L.length >=L.listsize ) /当前存储空间已满，增加分配newbase=(ElemType * )realloc(L.

4、elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW); /存储分配失败L.elem =newbase; /新基址L.listsize +=LISTINCREMENT; /增加存储容量q=&(L.elem i-1); /q为插入位置for(p=&(L.elem L.length -1);p>=q;-p)*(p+1)=*p; /插入位置及之后的元素右移*q=e; /插入e+L.length ; /表长增1return OK;/ListInsert_SqStatus ListD

5、elete_Sq(SqList &L,int i,ElemType &e)/在顺序线性表L中删除第i个元素，并用e返回其值/i的合法值为1<=i<=ListLength_Sq(L)ElemType *p,*q; /定义指针if(i<1) | (i>L.length )return ERROR; /i值不合法p=&(L.elem i-1); /p为被删除元素的位置e=*p; /被删除元素的值赋给eq=L.elem +L.length -1; /表尾元素的位置for(+p;p<=q;+p)*(p-1)=*p; /被删除元素之后的元素左移-L.l

6、ength ; /表长减1return OK;/ListDelete_sqvoid display(SqList L) /定义for循环函数int i;for(i=0;i<=L.length -1;i+)printf("%dn",L.elem i);int LocateElem_Sq(SqList L,ElemType e)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序/若找到，则返回其在L中的位序，否则返回0ElemType *p;int i=1; /i的初值为第一个元素的位序p=L.elem ; /p的初值为第一个元素的存储位置while(i

7、<=L.length && *p+!=e) +i;if(i<=L.length) return i; else return 0;/LocateElem_Sqvoid MergeList_Sq(SqList La,SqList Lb,SqList &Lc )/已知顺序线性表La和Lb的元素按值非递减排列/归并La和Lb得到新的顺序线性表Lc，Lc的元素也按非递减排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem ;pb=Lb.elem ;Lc.listsize =Lc.length =La.length +

8、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的剩余元素

9、while(pb<=pb_last) *pc+=*pb+; /插入Lb的剩余元素/MergeList_Sqvoid main()/*SqList L;/定义线性表InitList_Sq(L);/调用空表 /插入数据ListInsert_Sq(L,1,10);ListInsert_Sq(L,2,20);ListInsert_Sq(L,1,30);ListInsert_Sq(L,3,40);printf("插入后：n");display(L);/调用循环函数ListInsert_Sq(L,3,100);/在L表第三个位置插入100printf("插入后：n&qu

10、ot;);display(L);ElemType e;/定义eListDelete_Sq(L,3,e);/删除L表的第三个元素，用e表示printf("删除后：n");display(L);printf("被删除元素：%dnnnn",e);*/SqList La,Lb,Lc;InitList_Sq(La);ListInsert_Sq(La,1,3);ListInsert_Sq(La,2,5);ListInsert_Sq(La,3,8);ListInsert_Sq(La,4,11);printf("La插入后：n");display(L

11、a);InitList_Sq(Lb);ListInsert_Sq(Lb,1,2);ListInsert_Sq(Lb,2,6);ListInsert_Sq(Lb,3,8);ListInsert_Sq(Lb,4,9);ListInsert_Sq(Lb,5,11);ListInsert_Sq(Lb,6,15);ListInsert_Sq(Lb,7,20);printf("Lb插入后：n");display(Lb);MergeList_Sq(La,Lb,Lc);printf("归并后：n");display(Lc);printf("n");

12、int a=LocateElem_Sq( Lc, 5);printf("%dn",a);第三次上机：#include <stdio.h>#include <malloc.h>#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 LNodeElemType data;struct LNode *next;LN

13、Ode,*LinkList;Status GetElem_L(LinkList L,int i,ElemType &e)/L为带头结点的单链表的头指针/当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORLinkList p;p=L->next;int j=1; /初始化，p指向第一个结点，j为计数器while(p&&j<i) /顺指针向后查找，直到p指向第i个元素或p为空p=p->next;+j;if(!p|j>i) return ERROR; /第i个元素不存在e=p->data; /取第i个元素return OK;/GetEl

14、em_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素eLinkList p,s;p=L; int j=0;while(p&&j<i-1)p=p->next;+j; /寻找第i-1个结点if(!p|j>i-1) return ERROR; /i小于或者大于表长+1s=(LinkList)malloc(sizeof(LNode); /生成新结点s->data=e;s->next=p->next; /插入L中p->next=s;re

15、turn OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q;p=L;int j=0;while(p->next&&j<i-1)/寻找第i个结点，并令p指向其前趋p=p->next;+j;if(!(p->next)|j>i-1) return ERROR; /删除位置不合理q=p->next;p->next=q->next; /删除并释放结点e=q-&

16、gt;data; free(q);return OK;/ListDelete_Lvoid CreateList_L(LinkList &L,int n)/逆位序输入n个元素的值，建立带表头结点的单链线性表LLinkList p;L=(LinkList)malloc(sizeof(LNode);L->next =NULL; /先建立一个带头结点的单链表for(int i=n;i>0;-i)p=(LinkList)malloc(sizeof(LNode); /生成新结点scanf("%d",&p->data); /输入元素值p->next

17、=L->next ;L->next =p; /插入到表头/CreateList_Lvoid display(LinkList L) LinkList p=L->next;/定义for循环函数while(p) printf("%d,",p->data); p=p->next;printf("n");void main() LinkList L; CreateList_L(L,3); display(L); ListInsert_L(L,2,100); display(L); ElemType e; ListDelete_L(L

18、,2,e); display(L); printf("被删除的值=%dn",e); GetElem_L(L,3,e); printf("获取的值=%dn",e);第四次上机#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int SElemType;ty

19、pedef int Status;#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STRCKINCREMENT 10 /存储空间分配增量typedef structSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;Status InitStack(SqStack &S)/构造一个空栈SS.base =(SElemType *)malloc(STACK_INIT_SIZE * sizeof(

20、SElemType);if(!S.base )exit(OVERFLOW); /存储分配失败S.top =S.base ;S.stacksize =STACK_INIT_SIZE;return OK;/InitStackStatus GetTop(SqStack S,SElemType &e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top =S.base )return ERROR;e=*(S.top -1);return OK;/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素if

21、(S.top - S.base >=S.stacksize )/栈满，追加存储空间S.base =(SElemType * )realloc(S.base ,(S.stacksize +STRCKINCREMENT) * sizeof(SElemType);if(!S.base )exit(OVERFLOW); /存储分配失败S.top =S.base +S.stacksize ;S.stacksize +=STRCKINCREMENT;*S.top +=e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若栈不空，则

22、删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top =S.base )return ERROR;e=*-S.top ;return OK;/PopStatus StackEmpty(SqStack S)if(S.top=S.base) return TRUE;else return ERROR;void conversion()/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数SqStack S;int N;SElemType e;InitStack(S); /构造空栈scanf("%d",&N);while(N)Push(S

23、,N % 8);N=N/8;printf("转换成八进制后的数为：");while(!StackEmpty(S)Pop(S,e);printf("%d",e);printf("n");/conversionvoid main()SqStack S;SElemType e,x;InitStack(S);Push(S,5);Push(S,4);Push(S,3);Push(S,2);Push(S,1);GetTop(S,e);printf("栈顶元素为%dn",e);printf("n");Pop(

24、S,x);printf("删除的栈顶元素为%dn",x);printf("n");printf("输入一个十进制数：");conversion();第五次上机/*队列的链式存储*/#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef in

25、t QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;Status InitQueue(LinkQueue &Q)/构造一个空队列QQ.front =Q.rear =(QueuePtr)malloc(sizeof(QNode);if(!Q.front )exit(OVERFLOW); /存储分配失败Q.front

26、 ->next =NULL;return OK;Status DestroyQueue(LinkQueue &Q)/销毁队列Qwhile(Q.front )Q.rear =Q.front ->next ;free(Q.front );Q.front =Q.rear ;return OK;Status EnQueue(LinkQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW); /存储分配失败p->data=e;p

27、->next=NULL;Q.rear ->next =p;Q.rear =p;return OK;Status DeQueue(LinkQueue &Q,QElemType &e)/若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；/否则返回ERRORQueuePtr p;if(Q.front =Q.rear )return ERROR;p=Q.front ->next ;e=p->data;Q.front ->next =p->next;if(Q.rear =p)Q.rear =Q.front ;free(p);return OK

28、;void disp(LinkQueue Q)QueuePtr p; p=Q.front->next; /定义for 循环函数 while(p) printf("%d ",p->data); p=p->next; printf("n");void main()LinkQueue Q;QElemType e;InitQueue(Q);printf("插入的元素为：n");EnQueue(Q,25);EnQueue(Q,5);EnQueue(Q,12);EnQueue(Q,60);EnQueue(Q,33);disp(Q

29、);printf("删除队头元素后：n");DeQueue(Q,e);disp(Q);DestroyQueue(Q);if(DestroyQueue(Q)=1)printf("销毁队列成功！n");elseprintf("销毁队列失败！n");附加：/*队列的顺序存储*/#define MAXQSIZE 100 /最大队列长度typedef structQElemType *base /初始化的动态分配存储空间int front; /头指针，若队列不空，指向队列头元素int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置

30、SqQueue;Status InitQueue(SqQueue &Q)/构造一个空队列Q.base =(QElemType *)malloc(MAXQSIZE * sizeof(QElemType);if(!Q.base )exit(OVERFLOW); /存储分配失败Q.front =Q.rear =0;return OK;int QueueLenth(SqQueue Q)/返回Q的元素个数，即队列的长度return(Q.rear -Q.front +MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,QElemType e)/插入元素

31、e为Q的新的队尾元素if(Q.rear +1) % MAXQSIZE =Q.front) return ERROR; /队列满Q.base Q.rear =e;Q.rear =(Q.rear +1) % MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)/若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；/否则返回ERRORif(Q.front =Q.rear ) return ERROR;e=Q.base Q.front ;Q.front =(Q.front +1)% MAXQSIZE;return OK;第六次上机#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#defin