数据结构严蔚敏上机代码

1、数据结构第一、二次上机：#include #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 Status;typedef int ElemType;typedef struct ElemType*elem; int length;int lis

2、tsize;SqList;/存储空间基址/当前长度/当前分配的存储容量(以sizeof(ElemType)为单位)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_size;/初始存储容量return OK;/Initlist_SqStatus ListInsert_Sq(SqList &L,int

3、 i,ElemType e) /在顺序线性表L中第i个位置之前插入新的元素e，/i的合法值为1=i=ListLength_Sq(L)+1ElemType *p,*q,*newbase;if(iL.length +1)return ERROR;if(L.length=L.listsize ) newbase=(ElemType/定义指针/i值不合法/当前存储空间已满，增加分配* )realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW); /存储分配失败L.elem =newbase

4、;/新基址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 ListDelete_Sq(SqList &L,int i,ElemType &e) /在顺序线性表L中删除第i个元素，并用e返回其值/i的合法值为1=i=ListLength_Sq(L) ElemType *p,*q;/定义指针if(iL.l

5、ength )return ERROR;p=&(L.elem i-1); e=*p;q=L.elem +L.length -1;for(+p;p=q;+p)*(p-1)=*p;-L.length ;return OK;/ListDelete_sq/i值不合法/p为被删除元素的位置/被删除元素的值赋给e /表尾元素的位置/被删除元素之后的元素左移/表长减1void 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

6、e)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序/若找到，则返回其在L中的位序，否则返回0ElemType *p;int i=1;/i的初值为第一个元素的位序p=L.elem ;/p的初值为第一个元素的存储位置while(i=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的元素也按非

7、递减排列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(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)/

8、归并if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last) *pc+=*pa+; /插入La的剩余元素while(pb=pb_last)*pc+=*pb+;/插入Lb的剩余元素/MergeList_Sq void 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);/调用

9、循环函数ListInsert_Sq(L,3,100);/在L表第三个位置插入100 printf(插入后：n);display(L);ElemType e;/定义eListDelete_Sq(L,3,e);/删除L表的第三个元素，用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插入

10、后：n); display(La);InitList_Sq(Lb);ListInsert_Sq(Lb,1,2);ListInsert_Sq(Lb,2,6);ListInsert_Sq(Lb,3,8);ListInsert_Sq(Lb,4,9);e表示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);int a=LocateEle

11、m_Sq( Lc, 5); printf(%dn,a);第三次上机：#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 LNodeElemType data; struct LNode *next;LNOde,*LinkList;Status GetElem_L(LinkList L,int i,ElemTyp

12、e &e)/L为带头结点的单链表的头指针/当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p;p=L-next;int j=1;/初始化，p指向第一个结点，j为计数器while(p&jnext;+j;if(!p|ji)return ERROR;/第i个元素不存在e=p-data;/取第i个元素return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素e LinkList p,s;p=L;int j=0;while(p&jnext;+j

13、; /寻找第i-1个结点if(!p|ji-1) return ERROR; /i小于或者大于表长+1s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;/插入L中p-next=s;return OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkListp,q;p=L;int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1) return

14、 ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q); return OK;/ListDelete_L void CreateList_L(LinkList &L,int n)/逆位序输入n个元素的值，建立带表头结点的单链线性表L LinkList p;L=(LinkList)malloc(sizeof(LNode);L-next =NULL;/先建立一个带头结点的单链表for(int i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);p-next=L

15、-next ;L-next =p;/CreateList_L void 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,2,e);display(L);printf(被删除的值=%dn,e);GetEl

16、em_L(L,3,e);printf(获取的值=%dn,e);第四次上机#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int SElemType; typedef int Status;/存储空间初始分配量/存储空间分配增量/在栈构造之前和销毁之后，base的值为NULL /栈顶指针/当前已分配的存储空间，以元素为单位Status InitStack(SqStack &S)/构造

17、一个空栈SS.base =(SElemType *)malloc(STACK_INIT_SIZE * sizeof(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的栈顶元素，并返回0K;否则返回ERROR if(S.top =S.base )return ERROR;e=*(S.top -1);return OK;/GetTop

18、Status Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素if(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;#define STACK_INIT_SIZE 100#defin

19、e STRCKINCREMENT 10typedef structSElemType *base;SElemType *top;int stacksize;SqStack;*S.top +=e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)若栈不空，则删除S的栈顶元素，用e返回其值，并返回0K;否则返回if(S.top=S.base )return ERROR;e=*-S.top ;return OK;/PopStatus StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else retur

20、n ERROR;void conversion()/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数SqStack S;int N;SElemType e;InitStack(S);/构造空栈scanf(%d,&N);while(N)Push(S,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);ERRORPush(S,4);P

21、ush(S,3);Push(S,2);Push(S,1);GetTop(S,e); printf(栈顶元素为%dn,e);printf(n);Pop(S,x);printf(删除的栈顶元素为%dn,x);printf(n);printf(输入一个十进制数：); conversion();第五次上机/*队列的链式存储*/#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int QElem

22、Type;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 -next =NULL;retur

23、n 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-next=NULL;Q.rear -next =p;Q.rear =p;re

24、turn OK;Status DeQueue(LinkQueue &Q,QElemType &e)若队列不为空，则删除Q的队头元素，用e返回其值，并返回/否则返回ERRORQueuePtr p;if(Q.front =Q.rear )return ERROR;p=Q.front -next ;/队尾指针OK；e=p-data;Q.front -next =p-next;if(Q.rear =p)Q.rear =Q.front ;free(p);return OK;void disp(LinkQueue Q)QueuePtr p;p=Q.front-next;/定义for循环函数while(p)

25、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);printf(删除队头元素后：n);DeQueue(Q,e);disp(Q);DestroyQueue(Q);if(DestroyQueue(Q)=1)printf(销毁队列成功！n);elseprintf(销毁队列失败！n);附加：/*队

26、列的顺序存储*/#define MAXQSIZE 100 typedefstructQElemType *base/初始化的动态分配存储空间int front;/头指针，若队列不空，指向队列头元素int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置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 Q

27、ueueLenth(SqQueue Q)/返回Q的元素个数，即队列的长度return(Q.rear -Q.front +MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,QElemType e)/插入元素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 #include #include /最大队列长度#define TRUE 1#define FALSE 0#define OK