数据结构核心算法介绍.doc

数据结构核心算法介绍一、顺序表操作采用的数据描述为：顺序表在C语言中用一维数组表示。#define MAXLEN 100/*线性表的最大长度*/typedef structelemtype elemMAXLEN; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/ int last; /*顺序表的长度，即元素个数*/Sqlisttp; 1、插入status insert(Sqlisttp &V,int i,elemtype b) /*在顺序表V中第i个元素前插入新元素b*/if (iV.last+1) return ERROR; /*插入位置不正确则出错*/ else if (V.last=MAXLEN) return OVERFLOW; /*顺序表V中已放满元素，再做插入操作则溢出*/ else for(j=V.last-1;j=i-1;j-) V.elemj+1=V.elemj;/*将第i个元素及后续元素位置向后移一位*/ V.elemi-1=b;/*在第i个元素位置处插入新元素b*/ V.last+;/*顺序表V的长度加1*/ return OK; 2、删除status delete(Sqlisttp &V,int i) /*在顺序表V中删除第i个元素*/if (iV.last) return ERROR; /*删除位置不正确则出错*/else for(j=i;jnext=NULL;/*头结点的指针域初始为空*/ while(node!=0) p=(Linklist)malloc(sizeof(LNODE);/*生成一个新结点*/ p-data=node;/*新结点数据域赋值*/ p-next=L-next;/*新结点指针域指向开始结点*/ L-next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/ void creat2(Linklist &L) /*用尾插法建立单链表(带头结点)*/ L=(Linklist)malloc(sizeof(LNODE);/*生成头结点*/ L-next=NULL;/*头结点的指针域初始为空*/ r=L;/*尾指针初始指向头结点*/ while(node!=0) p=(Linklist)malloc(sizeof(LNODE);/*生成一个新结点*/ p-data=node; /*新结点数据域赋值*/ p-next=NULL; /*新结点指针域为空*/ r-next=p;/*尾结点指针域指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/ 2、插入status list_insert(Linklist &L,int i;elemtype x) /*在带头结点的单链表L中第I个位置之前插入新元素x*/ p=la; j=0; while(p!=NULL&jnext; +j;/*寻找插入位置，使p指向单链表L中第I-1个位置*/ if(p=NULL|ji-1) return ERROR;/*若位置不正确则出错*/ s=(Linklist)malloc(sizeof(LNODE);/*生成一个新结点*/ s-data=x;/*新结点数据域赋值*/ s-next=p-next;/*新结点指针域指向p的后继结点*/ p-next=s;/*新结点成为p的后继结点*/ return OK;3、删除status list_delete(Linklist &L,int i)/*在带头结点的单链表L中，删除第I个结点*/ p=la;j=0; while(p-next!=NULL&jnext; +j; /*寻找插入位置，使p指向单链表L中第I-1个位置*/ if (p-next=NULL|ji-1) return ERROR;/*若位置不正确则出错*/ q=p-next; /* q指向p的后继结点*/ p-next=q-next;/*q的后继结点成为p的后继结点*/ x=q-data;/*返回第I个位置的元素*/free(q);/*释放q所指结点的空间*/return OK; 三、队列操作采用的数据描述为：循环队列采用顺序结构#define MAXQSIZE 100/*循环队列的最大长度*/ typedef struct elemtype baseMAXQSIZE; /*存放元素的数组空间*/int front; /*“头指针”*/int rear; /*“尾指针”*/ Sqqueue;1、入队status enqueue(Sqqueue &Q,elemtype x) /*在循环队列Q中，插入新元素使其成为队尾元素*/ if (Q.rear+1)%MAXQSIZE=Q.front) return ERROR;/*若队列满，插入操作出错*/ Q.baseQ.rear=x;/*新元素成为队尾元素*/ Q.rear=(Q.rear+1)%MAXQSIZE;/*利用模运算，“尾指针”加1*/ return OK; 2、出队status dequeue(Sqqueue &Q)/*在循环队列Q中，删除Q的队首元素*/ if (Q.front=Q.rear) return ERROR;/*若队列空，删除操作出错*/ x=Q.baseQ.front;/*取队首元素*/ Q.front=(Q.front+1)%MAXQSIZE;/*利用模运算，“头指针”加1*/ return OK; 四、二叉树操作 采用的数据描述为：二叉树采用二叉链表作为存储结构。 typedef struct Bitnodeelemtype data;/*数据域*/ struct Bitnode *lchild, *rchild;/*指针域,分别指向左子树和右子树*/ Bitnode,*Bitree;1、建立void createbitree(Bitree &T) /*建立二叉树(若按先序次序输入各个结点)*/ scanf(x); if(x=#) T=NULL; else T=(Bitree)malloc(sizeof(Bitnode);/*生成一个新结点*/ T-data=x;/*新结点数据域赋值*/ createbitree(T-lchild);/*递归建立左子树*/ createbitree(T-rchild); /*递归建立右子树*/ 2、遍历status preorder(Bitree &T) /*先序遍历二叉树*/ if(T!=NULL)/*若二叉树非空*/ visit(T-data);/*访问根结点*/ preorder(T-lchild);/*递归先序遍历左子树*/ preorder(T-rchild); /*递归先序遍历右子树*/ return OK;status inorder(Bitree &T) /*中序遍历二叉树*/ if(T!=NULL) /*若二叉树非空*/ inorder(T-lchild); /*递归中序遍历左子树*/ visit(T-data); /*访问根结点*/ inorder(T-rchild); /*递归中序遍历右子树*/ return OK; status postorder(Bitree &T) /*后序遍历二叉树*/ if(T!=NULL) /*若二叉树非空*/ postorder(T-lchild); /*递归后序遍历左子树*/ postorder(T-rchild); /*递归后序遍历右子树*/ visit(T-data); /*访问根结点*/ return OK; 3、查找Bitree searchbst(Bitree T,keytype K) /*二叉排序树的查找*/if (T=NULL|K=T-data) return T;/*找到*/ else if (Kdata) return(searchbst(T-lchild,K);/*递归查找二叉排序树的左子树*/ else return(searchbst(T-rchild,K);/*递归查找二叉排序树的右子树*/五、图操作1、深度优先搜索首先访问出发点Vi，并将其标记为已访问过，然后依次从Vi出发搜索Vi的每一个邻接点Vj，若Vj未曾访问过，则以Vj为新的出发点继续进行深度优先搜索，特点是尽可能先对纵深方向进行搜索。 void dfs(int v) visit(v);/*访问结点*/adjlistv.tag=1;/*设置标志*/ptrv=adjlistv.firstarc;while(ptrv!=num) w=ptrv-adjvex; if(adjlistw.tag=0) dfs(w);/*递归调用深度优先遍历算法*/ ptrv=ptrv-next;2、广度优先搜索首先访问出发点Vi，接着访问Vi的所有邻接点W1，W2，Wt，然后再依次访问与W1，W2，Wt邻接的所有未访问过的顶点，直到图中所有与初始出发点Vi有路径相通的顶点都已访问到为止，特点是尽可能先对横向进行搜索。 void bfs(int v) visit(v);/*访问出发点*/adjlistv=tag=1; enqueue(v);/*调用入队列函数*/ while(v1=dequeue()!=EOF()/*调用出队列函数，判断是否为空*/ ptr=adjlistv1.firstarc; while(ptr!=null) w=ptr!=null ptr=ptr-next; if(adjlistw.tag=0); visit(w);/*访问其余结点*/adjlistw.tag=1; enqueue(w); 六、查找1、顺序查找从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字值与给定值K比较，若当前扫描到的结点关键字值与给定值K相等，则查找成功；若扫描结束后，仍未找到关键字值等于给定值K的结点，则查找失败。在程序设计中为了较少执行的循环次数使用监视哨。#define MAXSIZE 100 /*顺序表的最大长度*/typedef int keytype;typedef structkeytype key;redtype;typedef struct redtype elemMAXSIZE; int length;Sstable;int sxsearch(Sstable ST, keytype K) ST.elem0.key=K;for(i=ST.length;ST.elemi.key!=K;-i);/*从后往前顺序查找*/return i;2、二分查找设有序数组ST中每个记录的关键字按升序排列为：ST.elem1.key，ST.elem2.key,ST.elemn.key,其中n为记录个数，开始时，中间位置序号为m=(n+1)/2，相应的记录的关键字值为ST.elemm.key，将给定数据K与ST.elemm.key比较，有三种可能：*KST.elemm.key要找的记录在右半部分，对右半部分进行折半查找。重复上述过程，区间不断对分，当最后只剩下一个记录，且此记录不是要找的记录，则查找失败。int binsearch(Sstable ST,keytype K) l=1;h=ST.length; while(l=h) m=(l+h)/2;if (K=ST.elemm.key) return m;/*找到匹配记录*/else if (KST.elemm.key) h=m-1;/*对左半部分进行折半查找*/ else l=m+1；/*对右半部分进行折半查找*/return 0;/*找不到匹配记录*/ 七、排序操作 采用的数据描述为：#define MAXSIZE 100/*数组的最大长度*/typedef int keytypetypedef struct keytype key;/*关键字项*/ infotype otherinfo;/*其它数据项*/redtype;typedef struct redtype rMAXSIZE+1;/*存放记录中各个数据项的数组*/ int length;/*数组长度*/ Sqlist;1、插入排序假设待排序的记录存放在数组Rn中，排序过程的某一中间时刻，数组R被划分成两个子区间R1，Ri-1和Ri，Rn，其中前一个子区间是已排好序的有序区，后一个区间是当前未排好序的无序区。直接插入排序的基本操作是将当前无序区的第一个记录Ri插入到有序区中适当位置，使R1到Ri变成新的有序区。void insertsort(Sqlist &L)/*直接插入排序*/ for (i=2;i=L.length;+i) if (L.ri.keyL.ri-1.key) L.r0=L.ri;/*L.r0具有监视哨的作用*/ for(j=i-1;L.r0.keyL.rj.key;-j) L.rj+1=L.rj;/*记录后移*/ 2、 交换排序将待排序的记录看成从上到下的存放，把关键字较小的记录看成“较轻的”，关键字较大的记录看成“较重的”，小关键字的记录好像水中的气泡一样，向上浮；大关键字的记录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，且所有的石块都沉到了水中，排序就结束了。void bubblesort(Sqlist &L)/*起泡排序*/ for (i=1;i=L.length-1;+i) for(j=1;j=L.length-i;+j) if (L.rj+1.keyL.rj.key) temp=L.rj; L.rj=L.rj+1; L.rj+1=temp; /*数据交换*/ L.rj+1=L.r0; 3、选择排序首先在所有记录中选出关键字最小的记录，把它与第一个记录进行位置交换，然后在其余的记录中再选出关键字次小的记录与第二个记录进行位置交换，依此类推，直到所有记录排好序。void selectsort(Sqlist &L)/*直接选择排序*/ for(i=1;i=L.length-1;+i) k=i; for(j=i+1;j=L.length;+j) if (L.rj.keyL.rk.key) k=j;/* k始终“指向”关键字最小的记录*/ if (k!=i) temp=L.ri; L.ri=L.rk; L.rk=