顺序表及链表的应用.doc

设计一 顺序表的应用代码Head.h#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量#define STACK_INIT_SIZE 100/栈存储空间初始分配量#define STACKINCREMENT 10/栈存储空间分配增量#define MAXQSIZE 10/最大队列长度typedef int ElemType;typedef char SElemType;typedef int QElemType;typedef structint *elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量SqList;typedef structSElemType *base;/在栈构造之前和销毁之后，base的值为nullSElemType *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单位SqStack;typedef structQElemType *base;/初始化的动态分配存储空间int front;/头指针，若队列不空，指向队列头元素int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;void Check1();void Check2();void Check3();void Check4();int InitList_Sq(SqList *L);int CreateList(SqList *L);int DeleteElem_Sq(SqList *L);int PrintElem(SqList L);int DeleteElem_1(SqList *L);int DevideList_Sq(SqList L,SqList *La,SqList *Lb);int InitStack(SqStack *L);int Push(SqStack *S,SElemType e);int StackEmpty(SqStack S);int GetTop(SqStack S,SElemType *e);int Pop(SqStack *S,SElemType *e);int Correct(char exp, int n);int InitQueue(SqQueue *Q);int CreateQueue(SqQueue *Q);int PrintQueue(SqQueue Q);int EnQueue(SqQueue *Q,QElemType e);int DeQueue(SqQueue *Q,QElemType *e);.main.cpp#include#include head.h#includestdlib.h#include void main()int choice;doprintf(n 顺序表的应用n);printf(n -主菜单- n);printf(1) 删除线性表中值为item的元素n);printf(2) 将一个顺序表分拆成两个顺序表n);printf(3) 判断括弧是否匹对 n);printf(4) 循环队列中插入和取出节点n);printf(0) 退出系统 n);printf(n请选择操作步骤：);scanf(%d,&choice);if(choice4) continue;switch(choice)case 1:Check1();break;case 2:Check2();break;case 3:Check3();break;case 4:Check4();break;case 0:exit(0);default:break;while(1);.Check1.cpp#include head.h#include void Check1()SqList L1;printf(实现删除线性表中值为item的元素的算法：n);CreateList(&L1);/实现第一个算法PrintElem(L1);DeleteElem_1(&L1);PrintElem(L1);CreateList.cpp#includehead.h#includestdio.h#includestdlib.h/创建顺序表，在顺序表中输入数据元素。int CreateList(SqList *L)int i,n;if(!InitList_Sq(L)exit(-1);printf(请输入顺序表的长度：);scanf(%d,&n);(*L).length=n;ElemType *p=(*L).elem;printf(请输入顺序表的数据元素：);for(i=0;in;i+)scanf(%d,p);p+;return 1;PrintElem.cpp#include head.h#include int PrintElem(SqList L)if(L.length=0)printf(Empty!n);int i;for(i=0;iL.length;i+)printf(%4d,L.elemi);printf(n);return 1;DeleteElem_1.cpp#include head.h#includeint DeleteElem_1(SqList *L)int *p,*q,item;printf(请输入要删去的元素：);scanf(%d,&item);p=(*L).elem;q=(*L).elem+(*L).length-1;while(pq)if(*p=item)*p=*q;q-;(*L).length-;else p+;if(*p=item)(*L).length-;return 1;.Check2().cpp#include head.h#include void Check2()SqList L2,La,Lb;printf(实现将一个顺序表分拆成两个顺序表的算法：n);CreateList(&L2);/实现第二个算法PrintElem(L2);DevideList_Sq(L2,&La,&Lb);PrintElem(La);PrintElem(Lb);DevideList_Sq.cpp#include head.hint DevideList_Sq(SqList L,SqList *La,SqList *Lb)InitList_Sq(La);InitList_Sq(Lb);(*La).length=(*La).length=0;int *p,*q;p=L.elem;q=L.elem+L.length-1;for(;p0)(*La).elem(*La).length+=*p;else (*Lb).elem(*Lb).length+=*p;return 1;InitList_Sq.cpp#include head.h#include /构造一个空的线性表int InitList_Sq(SqList *L)(*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)exit(-1);/存储分配失败(*L).length=0;/空表长度为0(*L).listsize=LIST_INIT_SIZE;/初始存储容量return 1;.Check3().cpp#include head.h#include #includevoid Check3()printf(实现判断括弧是否匹对的算法：n);char a20;/实现第三个算法int tag;printf(Input String:);scanf(%s,a);tag=Correct(a,strlen(a);if(tag) printf(correct!n);else printf(wrong!n);Correct.cpp#include head.hint Correct(char exp, int n)SqStack S; InitStack(&S);char *p=exp,e,x;int i;for(i=0;in;i+,p+)if(*p=(|*p=|*p=)Push(&S,*p);else if(*p=)|*p=|*p=)GetTop(S,&e);switch(*p)case ):if(e=()Pop(&S,&x);else return 0;break;case :if(e=)Pop(&S,&x);else return 0;break;case :if(e=)Pop(&S,&x);else return 0;break;if(!StackEmpty(S)return 0;else return 1;GetTop.cpp#include head.hint GetTop(SqStack S,SElemType *e)/若栈不空，则用e返回S的栈顶元素，并返回1，否则返回0if(S.top=S.base)return 0;else *e=*(S.top-1);return 1;InitStack.cpp#include#include head.h/构造一个空栈int InitStack(SqStack *S)(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(*S).base)exit(-1);/存储分配失败(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return 1;Pop.cpp#include head.hint Pop(SqStack *S,SElemType *e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1，否则返回0if(StackEmpty(*S)return 0;*e=*(-(*S).top);return 1;Push.cpp#include#include head.hint Push(SqStack *S,SElemType e)/插入元素e为新的栈顶元素if(*S).top-(*S).base=(*S).stacksize)/栈满，追加存储空间(*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base)exit(-1);/存储分配失败(*S).stacksize+=STACKINCREMENT;*(*S).top+)=e;return 1;StackEmpty.cpp#include head.hint StackEmpty(SqStack S)if(S.top=S.base)return 1;else return 0;.Check4().cpp#include head.h#include void Check4()printf(实现循环队列中插入和取出节点的算法：n);SqQueue Q;/实现第四个算法QElemType e;CreateQueue(&Q);printf(请输入插入的节点：);scanf(%d,&e);PrintQueue(Q);EnQueue(&Q,e);PrintQueue(Q);DeQueue(&Q,&e);PrintQueue(Q);CreateQueue.cpp#include#include head.h/创建一个队列int (SqQueue *Q)int n,i;InitQueue(Q);printf(输入队列的长度 :);scanf(%d,&n);if(nMAXQSIZE)printf(overflow!n);return 0;for(i=0;in-1;i+)scanf(%d,(*Q).base)+i);(*Q).rear=n-1;return 1;DeQueue.cpp#include head.h#includeint DeQueue(SqQueue *Q,QElemType *e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回1，否则返回0if(*Q).front=(*Q).rear)printf(The Queue is empty!);return 0;*e=(*Q).base(*Q).front;(*Q).front=(*Q).front+1)%MAXQSIZE;return 1;EnQueue.cpp#include#include head.hint EnQueue(SqQueue *Q,QElemType e)/插入元素e为新的队尾元素if(*Q).rear+1)%MAXQSIZE=(*Q).front)printf(overflow!n);return 0;/队列满(*Q).base)(*Q).rear=e;(*Q).rear=(*Q).rear+1)%MAXQSIZE;return 1;InitQueue.cpp#include head.h#include /构造一个空队列int InitQueue(SqQueue *Q)(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!(*Q).base)exit(-1);/存储空间分配失败(*Q).front=(*Q).rear=0;return 1;PrintQueue.cpp#include head.h#includeint PrintQueue(SqQueue Q)if(Q.front=Q.rear)printf(empty!);return 0;int i,n;QElemType *p;n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;p=&(Q.base)Q.front;for(i=0;in;i+)printf(%4d,*p);if(p=&Q.baseMAXQSIZE-1)p=Q.base;else p+;printf(n);return 1;.设计二链表的应用代码Head.htypedef int ElemType;typedef struct LNode/线性表的单链表存储结构ElemType data;struct LNode *next;LNode,*LinkList;typedef struct DuLNode/线性表的双向链表存储结构ElemType data;struct DuLNode *prior;struct DuLNode *next;int freq;DulNode,*DuLinkList;void CreateList_L(LinkList *L,int n);int PrintLinkList(LinkList L);int EqualLinkList(LinkList *La,LinkList *Lb);void CreatCircularLinkList(LinkList *L,int n);int MonkeyKing(LinkList L,int n);int LinkListLength_Dul(DuLinkList L);int CreateLinkList_Dul(DuLinkList *L,int n);int PrintLinkList_Dul(DuLinkList L);int Locate(DuLinkList *L,ElemType e);/int InterSection(LinkList La,LinkList Lb,LinkList *Lc);void Check_1();void Check_2();void Check_3();.main.cpp#include#include head.h#includevoid main()int choice;doprintf(n 链表的应用n);printf(n -主菜单- n);printf(1) 删除两个递增链表中不同的元素n);printf(2) 猴子选大王n);printf(3) 实现locate函数n);printf(0) 退出系统.n);printf(n请选择操作步骤：);scanf(%d,&choice);if(choice3) continue;switch(choice)case 1:Check_1();break;case 2:Check_2();break;case 3:Check_3();break;case 0:exit(0);default:break;while(1);.Check_1.cpp#include head.h#include void Check_1()LinkList La,Lb;int n1,n2;printf(请输入单链表La的长度:);scanf(%d,&n1);printf(请按逆位序输入：n);CreateList_L(&La,n1);printf(La:);PrintLinkList(La);printf(请输入单链表Lb的长度：:);scanf(%d,&n2);printf(请按逆位序输入：n);CreateList_L(&Lb,n2);printf(Lb:);PrintLinkList(Lb);EqualLinkList(&La,&Lb);printf(删除元素以后 n);printf(La:);PrintLinkList(La);printf(Lb:);PrintLinkList(Lb);CreateList_L.cpp#include#include head.h#includevoid CreateList_L(LinkList *L,int n)/逆位序输入n个元素的值，建立带表头结点的单性线性表Lint i;LinkList p;*L=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;/先建立一个带头结点的单链表for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);/生成新结点scanf(%d,&(p-data);/输入元素值p-next=(*L)-next;(*L)-next=p;/插入到表头EqualLinkList.cpp#include head.h#includeint EqualLinkList(LinkList *La,LinkList *Lb)/删除两单链表中不同的元素LinkList ha,hb,pa,pb;ha=*La;hb=*Lb;pa=ha-next;pb=hb-next;while(pa&pb)if(pa-datadata)ha-next=pa-next;free(pa);pa=ha-next;else if(pa-datapb-data)hb-next=pb-next;free(pb);pb=hb-next;else ha=pa;pa=pa-next;hb=pb;pb=pb-next;if(pa)ha-next=NULL;free(pa);else hb-next=NULL;free(pb);return 1;PrintLinkList.cpp#include head.h#includeint PrintLinkList(LinkList L)/输出单链表LinkList p=L-next;if(!p)printf(Empty!n);while(p)printf(%4d,p-data);p=p-next;printf(n);return 1;.Check_2.cpp#include head.h#includevoid Check_2()int n;LinkList L;printf(请输入猴子的个数：);scanf(%d,&n);CreatCircularLinkList(&L,n);MonkeyKing(L,n);MonkeyKing.cpp#include head.h#include int MonkeyKing(LinkList L,int n)int m;printf(输入 m:);scanf(%d,&m);LinkList p=L,p1=L;while(p1-next!=L)p1=p1-next;int k=n,i=0,j=0;while(inext=p-next;j=0;i+;else p1=p;p=p-next;printf(%d is the Kingn,p1-data);return 1;CreatCircularLinkList.cpp#include head.h#include#includevoid (LinkList *L,int n)/建一个不带头结点的循环链表，L为头指针int i;LinkList p;*L=(LinkList)malloc(sizeof(LNode);(*L)-next=*L;(*L)-data=1;/printf(input the number of elements of LNode:);/scanf(%d,&n);for(i=n;i1;-i)p=(LinkList)malloc(sizeof(LNode);/scanf(%d,&(p-data);p-data=i;p-next=(*L)-next;(*L)-next=p;.Check_3.cpp#include#include head.hvoid Check_3()DuLinkList D;int e,i,choice;printf(请输入非循环双链表的元素的个数：);scanf(%d,&i);CreateLinkList_Dul(&D,i);printf(执行Locate运算前：n);PrintLinkList_Dul(D);doprintf(请输入要访问元素的值：);scanf(%d,&e);Locate(&D,e);printf(执行Locate运算后：n);PrintLinkList_Dul(D);printf(输入choice的值，输入1代表继续执行locate，输入0代表退出:n);scanf(%d,&choice);while(choice);printf(OK!n);Locate.cpp#include head.h#includeint Locate(DuLinkList *L,ElemType e)DuLinkList s,t,p=(*L)-next;if(!p)