《数据结构严蔚敏上机代码.doc》由会员分享，可在线阅读，更多相关《数据结构严蔚敏上机代码.doc（32页珍藏版）》请在三一文库上搜索。
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 10typedef int Stat
2、us;typedef 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_in
3、it_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* )r
4、ealloc(L.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_SqS
5、tatus ListDelete_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;/ 被删除
6、元素之后的元素左移-L.length ;/ 表长减 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 中的位序，否则返回 0 ElemType *p;int i=1;/i 的初值为第一个元素的位序p=L
7、.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的元素也按非递减排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem ;pb=Lb.elem
8、;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+;else*pc+=*pb+;while(
9、pa<=pa_last) *pc+=*pa+;while(pb<=pb_last) *pc+=*pb+;/ 插入 La 的剩余元素/ 插入 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);/ 调用循环函数ListInsert_
10、Sq(L,3,100);/ 在 L 表第三个位置插入 100 printf(" 插入后： n");display(L);e 表示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
11、,8);ListInsert_Sq(La,4,11);printf("La 插入后： 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);ListInsert_Sq(Lb,5,11);ListInsert_Sq(Lb,6,15);ListInsert_Sq(Lb,7,20); printf("Lb 插入后： n"); display(Lb);MergeList_Sq(L
12、a,Lb,Lc); printf(" 归并后： n"); display(Lc);printf("n");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;ty
13、pedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNOde,*LinkList;Status GetElem_L(LinkList L,int i,ElemType &e)/L 为带头结点的单链表的头指针ERROR/ 当第 i 个元素存在时，其值赋给 e 并返回 OK ，否则返回 LinkList p;p=L->next;int j=1; / 初始化， p 指向第一个结点， j 为计数器 while(p&&j<i)/ 顺指针向后查找，直到 p 指向第 i 个元素或
14、 p 为空 p=p->next;+j;if(!p|j>i)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&&j<i-1)p=p->next;+j; / 寻找第 i-1 个结点if(!p|j>i-1) return ERROR
15、; /i 小于或者大于表长 s=(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个元素，并由LinkList p,q;p=L;int j=0;while(p->next&&j<i-1)/ 寻找第 i 个结点，并令 p 指向其前
16、趋+1e 返回其值p=p->next;+j;if(!(p->next)|j>i-1) return ERROR;/ 删除位置不合理q=p->next;p->next=q->next; / 删除并释放结点 e=q->data;free(q);return OK;/ListDelete_Lvoid CreateList_L(LinkList &L,int n)/ 逆位序输入 n 个元素的值，建立带表头结点的单链线性表 L LinkList p;L=(LinkList)malloc(sizeof(LNode);L->next =NULL; /
17、先建立一个带头结点的单链表 for(int i=n;i>0;-i)p=(LinkList)malloc(sizeof(LNode);/ 生成新结点scanf("%d",&p->data);/ 输入元素值p->next=L->next ;L->next =p;/ 插入到表头/CreateList_L void display(LinkList L) LinkList p=L->next;/ 定义 for 循环函数while(p)printf("%d,",p->data);p=p->next;print
18、f("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);GetElem_L(L,3,e);printf(" 获取的值 =%dn",e);第四次上机#include <stdio.h>#include <malloc.h>#include <stdlib
19、.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int SElemType;typedef int Status;#define STACK_INIT_SIZE 100/ 存储空间初始分配量#define STRCKINCREMENT 10/ 存储空间分配增量typedef structSElemType *base;/ 在栈构造之前和销毁之后， base 的值为 NULLSElemType *top;/ 栈顶指针int
20、stacksize;/ 当前已分配的存储空间，以元素为单位SqStack;Status InitStack(SqStack &S)/ 构造一个空栈 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
21、 的栈顶元素，并返回 OK ；否则返回 ERROR if(S.top =S.base )return ERROR;e=*(S.top -1);return OK;/GetTopStatus 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(OVERF
22、LOW); / 存储分配失败S.top =S.base +S.stacksize ;S.stacksize +=STRCKINCREMENT;*S.top +=e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)ERROR/若栈不空，则删除 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 re
23、turn 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()SqS
24、tack 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(S,x);printf(" 删除的栈顶元素为 %dn",x);printf("n");printf(" 输入一个十进制数： ");conversion();第五次上机/* 队列的链式存储 */#include <stdio.
25、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 QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct/ 队头指针/ 队尾指针QueuePtr fr
26、ont;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue &Q)/ 构造一个空队列 QQ.front =Q.rear =(QueuePtr)malloc(sizeof(QNode);if(!Q.front )exit(OVERFLOW); / 存储分配失败Q.front ->next =NULL;return OK;Status DestroyQueue(LinkQueue &Q)/ 销毁队列 Qwhile(Q.front )Q.rear =Q.front ->next ;free(Q.front );Q.fron
27、t =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;return OK;Status DeQueue(LinkQueue &Q,QElemType &e)OK；/ 若队列不为空，则删除 Q 的队头元
28、素，用 e 返回其值，并返回/ 否则返回 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;void disp(LinkQueue Q)QueuePtr p;p=Q.front->next;/ 定义 for 循环函数while(p)printf("%d ",p->data);p=p->ne
29、xt;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"
30、);elseprintf(" 销毁队列失败！ n");附加：/ 最大队列长度/* 队列的顺序存储 */#define MAXQSIZE 100typedef structQElemType *base/ 初始化的动态分配存储空间int front;/ 头指针，若队列不空，指向队列头元素int rear;/ 尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;Status InitQueue(SqQueue &Q)/ 构造一个空队列Q.base =(QElemType *)malloc(MAXQSIZE * sizeof(QElemType);if(!Q.b
31、ase )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)/ 插入元素 e 为 Q 的新的队尾元素if(Q.rear +1) % MAXQSIZE =Q.front) return ERROR; / 队列满Q.base Q.rear =e;Q.rear =(Q.rear +1) %
32、MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)OK；/ 若队列不为空，则删除 Q 的队头元素，用 e 返回其值，并返回/ 否则返回 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
33、1#define FALSE 0#define OK 1#define ERROR 0 #define INFEASIBLE -1#define OVERFLOW -2 typedef int Status;typedef char TElemType;/ 二叉树的二叉链表存储表示 typedef struct BiTNodeTElemType data;/ 左右孩子指针struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTree &T)/ 按先序次序输入二叉树中结点的值(一个字符) ，空格字符表示空
34、树，/ 构造二叉树链表表示的二叉树 Tchar ch;scanf("%c",&ch);if(ch=' ')T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);T->data =ch;/ 生成根结点CreateBiTree(T->lchild );/ 构造左子树CreateBiTree(T->rchild );/ 构造右子树return OK;/CreateBiTree void PreOrderTraverse(BiTree T)/ 先序遍历if(T)
35、printf("%c ",T->data ); / 输出结点PreOrderTraverse(T->lchild );PreOrderTraverse(T->rchild );void InOrderTraverse(BiTree T)/ 中序遍历if(T)PreOrderTraverse(T->lchild );printf("%c ",T->data );PreOrderTraverse(T->rchild );void PostOrderTraverse(BiTree T)/ 后序遍历if(T)PreOrderTraverse(T->lchild );PreOrderTraverse(T->rchild ); printf("%c ",T->data );void main()BiTree T;CreateBiTree(T);printf("nPreOrder: n ");PreOrderTraverse(T);