C语言数据结构基本操作.doc

/*顺序表的基本操作*/#include #include #include #include #define Length 10#define LISTINCREMENT 3#define TRUE 1#define FALSE 0#define OK 1#define ERROR -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct lineorder int *elem; int length; int listsize; SqList;Status initlist_Sq(SqList &L)/*初始化顺序表*/L.elem=(ElemType*)malloc(sizeof(ElemType)*Length); if(!L.elem) exit(OVERFLOW); L.listsize=Length; L.length=0; return OK;void destroylist(SqList &c) /*销毁顺序表*/ free(c.elem); c.elem=NULL; c.length=0;void clearlist_Sq(SqList &c) /*清空顺序表*/ c.length=0; Status listempty_Sq(SqList c)/*测试顺序表是否为空*/ if(c.length!=0) return(FALSE); return(TRUE);Status ListInsert_Sq(SqList &L, int i,ElemType e) /*在第i个位置上插入一个元素*/ int j,*newbase; if (iL.length+1) return ERROR; if (L.length = L.listsize) newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; for (j=L.length ; j=i ; -j) L.elemj=L.elemj-1; L.elemj=e ; +L.length ; return OK;int LocateElem_Sq(SqList L,ElemType e) /*返回元素e在顺序表中的位置*/ int i=1; ElemType *p=L.elem; while(i=L.length &!(*p=e) i+; p+; if(i=L.length) return i; return FALSE;Status ListDelete_Sq(SqList &L , int i , int &e) /*删除第i个位置上的元素*/ int j; if(iL.length) return ERROR; e=L.elemi-1; for( j=i; jL.length;j+) L.elemj-1=L.elemj; L.length-; return OK;void Print_Sq(SqList L) /*输出顺序表*/ int i; if (listempty_Sq(L) printf(nSequential Lists length is %d. Its empty!,L.length); else printf(nSequential Lists length is %d. These element are : ,L.length); for(i=0;iL.length;i+) printf( %d,L.elemi);void menu() printf(n); printf(n* * * * * * * * * * * * * * * * * * * * * * * * * *n); printf( 1 - Print the Sequential List.n); printf( 2 - Insert a data in the Sequential List.n); printf( 3 - Delete a data in the Sequential List.n); printf( 4 - Get a elements locationt in the SqList.n); printf( 5 - Clear the Sequential List.n); printf( 6 - Exit.n); printf(* * * * * * * * * * * * * * * * * * * * * * * * * *n); printf(n);void menuselect(SqList L) int k,i,done=1; ElemType e; char ch10; while (done) menu(); printf(Please choose: ); scanf(%d,&k); getchar(); switch(k) case 1: Print_Sq(L); break;case 2: printf(nInput the location and data you want to Insert: ); scanf(%d,%d,&i,&e); if (ListInsert_Sq(L,i,e)=ERROR) printf(Insert location is not correct!n); break; case 3: printf(nInput the location you want to delete data: ); scanf(%d,&i);if(ListDelete_Sq(L,i,e)=ERROR) printf(Delete location is not exit!n); else printf(nDelete data is %d.,e); break; case 4: printf(nInput the data you want to find: ); scanf(%d,&e);if(LocateElem_Sq(L,e)!=FALSE) printf(nData %d location in the Sequential List is %d，e,LocateElem_Sq(L,e); else printf(n%d is not in the Sequential List.n, e); break; case 5: clearlist_Sq(L); break;case 6: done=0; void main() ElemType e; SqList La; int n,i; clrscr(); initlist_Sq(La); printf(Input a number of the element in the Sequential List (n=%d):,Length); scanf(%d,&n); printf(Enter these elements:); for(i=1;ilength,Lb_len=Lb.length,j; ElemType e; for(i=1;i=Lb_len;i+) e=Lb.elemi-1; if(!LocateElem_Sq(La,e) ListInsert_Sq(La,+La_len,e); return OK;MergeList(SqList La,SqList Lb,SqList *Lc) int i=1,j=1,k=0,La_len=La.length,Lb_len=Lb.length; ElemType ai,bj; while(i=La_len)&(j=Lb_len) ai=La.elemi-1; bj=Lb.elemj-1; if(ai=bj) ListInsert_Sq(Lc,+k,ai);i+; else ListInsert_Sq(Lc,+k,bj);j+; while(i=La_len) ai=La.elem-1+i+;ListInsert_Sq(Lc,+k,ai);while(j=Lb_len) bj=Lb.elem-1+j+;ListInsert_Sq(Lc,+k,bj); return OK;void main() ElemType e; SqList La,Lb,Lc; int n,i; clrscr(); initlist_Sq(La); initlist_Sq(Lb); printf(nInput a number of the element in the Sequential List La (n=%d):,Length); scanf(%d,&n); printf(nEnter these elements:); for(i=1;i=n;i+) scanf(%d,&e); ListInsert_Sq(&La,i,e); printf(nInput a number of the element in the Sequential List Lb (n=%d):,Length); scanf(%d,&n); printf(nEnter these elements:); for(i=1;i=n;i+) scanf(%d,&e); ListInsert_Sq(&Lb,i,e); Print_Sq(La,La); printf(n); Print_Sq(Lb,Lb); union_Sq(&La,Lb); printf(n); Print_Sq(La after union (La&Lb),La); initlist_Sq(Lc);MergeList(La,Lb,&Lc); printf(n); Print_Sq(Lc (La or Lb),Lc); printf(n); clearlist_Sq(Lc); Print_Sq(Lc after clear,Lc); getch();/*单链表的基本操作*/#include #include #include #define TRUE 1#define FALSE 0typedef int ET;typedef ET * Ep;typedef int Status;typedef struct LNode ET data; struct LNode *next;LNode, *LinkList;/*逆序建立一个长度为n的单链表*/void CreatList( LinkList *L,int n) int i; LinkList p,q; ET e; p=(LinkList)malloc(sizeof(LNode); p-next=NULL; *L=q=p; printf(Please input these datas :); for (i=n;i0;i-) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&e); p-data=e; p-next=q-next; q-next=p; /*初始化单链表*/void Init(LinkList *L) int n; printf(Please input the number of the node : ); scanf(%d,&n); CreatList(L,n);/*打印单链表中的结点元素值*/void printlk(LinkList L) LinkList p; p=L-next; while (p) printf(%d - ,p-data); p = p-next; printf(NULLn);/*在单链表的第i个结点位置之后插入一个新结点*/int ListInsert(LinkList L,int i,ET e) int j=0; LinkList p,s; p=L-next;/*指针p初始值指向第1个结点*/ while(p&jnext; +j; if(!p|ji-1) return FALSE; s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return TRUE;/*删除单链表中的第i个结点*/int ListDelete(LinkList L,int i,ET *e) LinkList p,q; int j=0; p=L;/*指针p初始值指向头结点*/ while(p&jnext; +j; if(!(p-next)|(ji-1) return FALSE; q=p-next;/*指针q指向要删除的第i个结点位置*/ p-next=q-next; *e=q-data; free(q); return TRUE;int Insert(LinkList L) /*插入函数*/ int i,flag; ET data; printf(nPlease input the insert position : ); scanf(%d,&i); printf(Input the data you want to Insert : ); scanf(%d,&data); flag = ListInsert(L,i,data); return flag;Status Delete(LinkList L) /*删除函数*/ int i,flag; ET e; printf(nPlease input the delete position : ); scanf(%d,&i); flag = ListDelete(L,i,&e); if (flag=TRUE) printf(Deleted element is %dn,e); return flag;/*取单链表中第i个结点的数据元素值*/int GetElem(LinkList L,int i,ET &e) int j=1; LinkList p; p=L-next; while(p&jnext; +j; if(!p|ji) return FALSE; e=p-data; return TRUE;Status GetElem_List(LinkList L) int i,flag; ET e; printf(nPlease input the position : ); scanf(%d,&i); flag=GetElem(L,i,e); if (flag=TRUE) printf(Get element is %dn,e); return flag;/*在单链表中查询第一个满足判定条件的数据元素*/*若存在，则返回它的位序，否则返回0*/int LocateElem(LinkList L,ET e) int i=0; LinkList p; p=L-next; while (p) i+; if (p-data=e) return i; else p=p-next; return 0;Status LocateElem_List(LinkList L) int i,flag; ET e; printf(nPlease input the element :); scanf(%d,&e); flag=LocateElem(L,e); if (flag) printf(Location of a %d in the LA is %dn,e,flag); return flag;/*栈的基本操作源程序*/#include stdio.h#include stdlib.h#include alloc.h#include conio.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 2#define STACK_INIT_SIZE 10#define STACKINCREMENT 2typedef char ET;typedef int Status;typedef struct stack ET *base, *top; int stacksize;Stack;Status InitStack(Stack *S) S-base=(ET*)malloc(STACK_INIT_SIZE*sizeof(ET); if(!S-base) exit(OVERFLOW); S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;Status GetTop(Stack *S, ET *e) if(S-top=S-base) return ERROR; *e=*(S-top-1); return OK;Status Push(Stack *S, ET e) if(S-top-S-base=S-stacksize) S-base=(ET *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(ET); if(!S-base) exit(OVERFLOW); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; return OK;Status Pop(Stack *S, ET *e) if(S-top=S-base) return ERROR; *e=*-S-top; return OK;Status StackEmpty(Stack *S) if(S-top=S-base) return TRUE; else return FALSE;void Destroy_Stack(Stack *S) if(S-base) free(S-base); S-base=NULL; S-top=NULL; S-stacksize=0;void Clear_Stack(Stack *S) S-top=S-base;void menu() printf(n* * * * * * * * * * * * * * * * * * * * * * * * * *n); printf( 1 - Insert a data in the Stack.n); printf( 2 - Delete the Stacktop data in the Stack.n); printf( 3 - Print Stacktop element.n); printf( 4 - Clear the Stack.n); printf( 5 - Destroy the Stack.n); printf( 6 - Exit.n); printf(* * * * * * * * * * * * * * * * * * * * * * * * * *n);void menuselect(Stack *S) int k,done=1; ET e; char ch10; while (done) menu(); printf(Please choose: ); scanf(%d,&k); getchar(); switch(k) case 1: printf(Input the data you want to Insert: ); scanf(%c,&e); getchar(); printf(n); Push(S,e); break; case 2: Pop(S,&e); break;case 3: GetTop(S,&e); if(S-top!=S-base) printf(Stacktop element is %c.n,e); else if (S-top=S-base&S-base!=NULL) printf(Stack is empty!n); else printf(Stack is not exist!n); break; case 4: Clear_Stack(S); break;case 5: Destroy_Stack(S); break;case 6: done=0; void main() Stack S; int i,j,k; ET e; char ch10; clrscr(); InitStack(&S); printf(Input the number of the Stack data:); scanf(%d,&i); getchar(); printf(n); printf(Input the data of the Stack:n); for(j=1;jbase=(ET*)malloc(MAXQSIZE*sizeof(ET); if(!Q-base) exit(OVERFLOW); Q-front=Q-rear=0; return OK;/*返回Q的元素个数，即队列的长度*/Status QueueLength(SqQueue *Q) return (Q-rear-Q-front+MAXQSIZE)%MAXQSIZE;/*插入元素e为Q的新的队尾元素*/Status EnQueue(SqQueue *Q,ET e) if(Q-rear+1)%MAXQSIZE=Q-front) return ERROR; Q-baseQ-rear=e; Q-rear=(Q-rear+1)%MAXQSIZE; return OK;Status DeQueue(SqQueue *Q,ET *e) if(Q-front=Q-rear) return ERROR; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return OK;Status GetHead(SqQueue *Q,ET *e) if(Q-front=Q-rear) return ERROR;*e=Q-baseQ-front; return OK;Status Clear_SqQueue(SqQueue *Q) ET e; while (Q-front!=Q-rear) DeQueue(Q,&e); return OK;void menu() printf(n* * * * * * * * * * * * * * * * * * * *n); printf( 1 - Insert a data in the Queue.n); printf( 2 - Delete a data in the Queue.n); printf( 3 - Print Queuefront data.n); printf( 4 - Clear the Queue.n); printf( 5 - Length of the Queue.n); printf( 6 - Exit.n); printf(* * * * * * * * * * * * * * * * * * * * n);void menuselect(SqQueue *Q) int k,done=1; ET e;while (done) menu(); printf(please choose: ); scanf(%d,&k); getchar(); switch(k) case 1: printf(Input the data you want to Insert: ); scanf(%c,&e); getchar(); printf(n); if (EnQueue(Q,e)=ERROR) printf(Queue is full!n); break; case 2: if (DeQueue(Q,&e)=ERROR) printf(Queue is empty!n); else printf(Delete the data is %c.n,e); break; case 3: if(GetHead(Q,&e)=ERROR) printf(Queue is empty!n); elseprintf(Queuefront data is %c.n,e);break; case 4:Clear_SqQueue(Q);break; case 5:printf(Length of the queue is %d.n, QueueLength(Q); break; case 6:done=0; void main() SqQueue Q; int i,j; ET e; clrscr(); InitQueue(&Q); printf(Input the number of the Queue data (number%d): ,MAXQSIZE); scanf(%d,&i); getchar(); printf(n); printf(Input the data of the Queue:n); for(j=1;jbase=(QElemType *)malloc(sizeof(QElemType)*MAXQSIZE); if(! Q-base) exit(OVERFLOW); Q-front=0; Q-rear=0; return OK;destroylist(SqQueue *Q)/*销毁循环队列*/ free(Q-base); Q-base=NULL; Q-front=0; Q-rear=0;clearstack(SqQueue *Q)/*清空循环队列*/ Q-front=0;Q-rear=0; Status QueueEmpty(SqQueue Q) /*测试循环队列是否为空*/ if(!Q.base) return ERROR; if(Q.rear=Q.front) return(TRUE); else return(FALSE);Status EnQueue(SqQueue *Q,QElemType e) /*在循环队列队尾插入元素*/ int j; QElemType *newbase; if(!Q-base) return ERROR; if(Q-rear+1)%MAXQSIZE=Q-front) return ERROR; Q-baseQ-rear=e; Q-rear=(Q-rear+1) % MAXQSIZE; return OK;Status DeQueue(SqQueue *Q,QElemType *e)/*在循环队列队头删除元素*/ if(Q-front=Q-rear) return ERROR; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return OK;void Jesephu(SqQueue Q, int n , int i , int m,int A ) QElemType e; int j,k=0; InitQueue(&Q); for(j=0 ; jn ; j+) EnQueue(&Q, j+1) ; for( j=1; ji ; j+) DeQueue(&Q,&e);EnQueue(&Q,e); while(!QueueEmpty(Q) for(j=1 ; j m; j+) DeQueue(&Q,&e);EnQueue(&Q,e); DeQueue(&Q,&e);Ak+=e; main() int n,m,start,k,aMAXQSIZE-1;SqQueue Q; clrscr(); printf(please input n (n%d), start, m: ,MAXQSIZE); scanf(%d %d %d,&n,&start,&m); Jesephu(Q,n,start, m, a); printf(nOutput List are : ); for(k=0;kn;k+) printf(%d ,ak); getch();/*二叉树的建立、三种遍历的递归算法、并计算出二叉树高度的源程序*/#include stdio.h#include stdlib.h#include conio.h#define OK 0#define ERROR -1#define OVERFLOW -2typedef int Status;typedef char TElemtype;typedef struct BiTNode TElemtype data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;Status CreateBiTree(BiTree *T) int ch,n,i,j,f; BiTNode *p,*nar100; printf(Please input numbers of tree node:); scanf(%dn,&n); for(i=0;idata=ch; p-lchild=NULL; p-rchild=NULL; narj=p; if(j=1) *T=p; else f=j/2; if(j% 2)=0) narf-lchild=p; else narf-rchild=p; printf(*Return*); return OK;Status Pre(BiTree T) if(T) printf(%3c,T-data); Pre(T-lchild); Pre(T-rchild); Status Post(BiTree T) if(T) Post(T-lchild); Post(T-rchild); printf(%3c,T-data); Status In(BiTree T) if(T) In(T-lchild); printf(%3c,T-data); In(T-rchild); int Height(BiTree t) int h,h1,h2; if(t=NULL) return(0); else h1=Height(t-lchild); h2=Height(t-rchild); if (h1h2) h=h1+1; else h=h2+1; return(h);main() BiTree T; int h; clrscr(); printf(n); CreateBiTree(&T); printf(nPreorder Traverse: ); Pre(T); printf(nInorder Traverse: ); In(T); printf(nPostorder Traverse: ); Post(T); h=Height(T); printf(nThe height of this tree is: %d,h); getch();/*二叉树中序遍历的非递归算法源程序*/#include #include #include #define ERROR 0;#define OK 1;typedef int ElemType;typedef struct BinaryTree ElemType data; struct BinaryTree *l; struct B