数据结构课本算法实现.docx
- 文档编号:17524259
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:67
- 大小:116.02KB
数据结构课本算法实现.docx
《数据结构课本算法实现.docx》由会员分享,可在线阅读,更多相关《数据结构课本算法实现.docx(67页珍藏版)》请在冰点文库上搜索。
数据结构课本算法实现
线性结构
一类型定义
1顺序表
#defineMAXSIZE100typedefstructnode
typedefstruct{ElemTypedata;
{ElemTypedata[MAXSIZE];structnode*next;
intlength;}SLink;
}SqList;
2单链表
3双链表
typedefstructnode
{ElemTypedata;
structnode*prior,*next;
}dlink;
二基础要点
1单链表
2双链表
三算法
1删除顺序表中重复元素
voiddelsame(intA[],intcount)
{inti,j,k;
if(N>1)
{j=1;
for(i=1;i {k=0; while(k =A[i])k++; if(k>=j)A[j++]==A[i]; } A[j]==‘\0’ } } 2给无序表建有序索引表 typedefstructindexelem {KeyTypekey;//关键字 intsn;//序号 }IndexType;//索引项 IndexTypeidx[1...m];//索引表 DataTypedata[1...m];//原顺序表 for(i=1;i<=m;i++) {j=i-1; while(j>0&&idx[j].key>data[i].key)//把大于data[i].key的所有idx[j].key后移 {idx[j+1]=idx[j]; j--; } idx[j+1].key=data[i].key;//插入data[i].key至idx中,并记下其序号i idx[j+1].sn=i; } 3逆置单链表 voidreverse(LinkListH) {SNode*p,*temp; P=H->next; H->next=NULL; while(p) {temp=p; p=p->next; temp->next=H->next; H->next=temp; } } voidreverse(LinkListH) {SNode*p,*q,*temp; P=H->next; q=NULL; while(p) {temp=p; p=p->next; temp->next=q; q=temp; } H->next=q; } 4拆分单链表 decompese(SNode*L,SNode*ha,SNode*hb,SNode*hc) {SNode*temp,*p; p=L; ha=(SNode*)malloc(sizeof(SNode)); hb=(SNode*)malloc(sizeof(SNode)); hc=(SNode*)malloc(sizeof(SNode)); ha->next=ha; hb->next=hb; hc->next=hc; while(p) {if((p->data>=‘A’&&p->data<=‘Z’)||(p->data>=‘a’&&p->data<=‘z’)) {temp=p; p=p->next; temp->next=ha->next; ha->next=temp; } elseif(p->data>=‘0’&&p->data<=‘9’) {temp=p; p=p->next; temp->next=hb->next; hb->next=temp; } else {temp=p; p=p->next; temp->next=hc->next; hc->next=temp; } } } 5删除单链表重复元素 voiddelete(LinkListH) {SNode*p,*q,*r; P=H->next; while(p! =NULL) {q=p; while(q->next) {if(q->next->data==p->data) {r=q->next; q->next=r->next; free(r); } else q=q->next; } p=p->next; } } 6合并单链表 LinkListmerge(LinkListA,LinkListB) {LinkListC; SNode*p,*q; P=A->next; q=B->next; C=A; C->next=NULL; free(B); while(p&&q) {if(p->data {s=p; p=p->next; } else {s=q; q=q->next; } s->next=C->next;/*插入到C表的头部*/ C->next=s; } if(p==NULL)r=q; if(q==NULL)r=p; while(r)/*将剩余的结点一个个摘下,插入到C表的头部*/ { s=r; r=r->next; s->next=C->next; C->next=s; } } 7顺序表和链表的递归输出 已知head是带头结点的单链表的头指针,试编写逆序/顺序输出表中各元素的递归算法; 有一个整数数组A[n],按顺序/逆序递归输出数组中的各元素 output(LinkList*head) {if(head! =NULL) {output(head->next); printf(“%d”,head->data);//printf在output下为逆序输出,在上为顺序输出 } } 8带访问频度的双向链表的查找 8置逆栈 voidreverse(Stack*s) {Stacks1,s2; ElemTypex; InitStack(s1); InitStack(s2);//将s栈中的内容转移到s1栈中 while(StackEmpty(s)! =0) {Pop(s,x); Push(s1,x); }//将s1栈中的内容转移到s2栈中 while(StackEmpty(s1)! =0) {Pop(s1,x); Push(s2,x); }//将s2栈中的内容转移到s栈中 while(StackEmpty(s2)! =0) {Pop(s2,x); Push(s,x); } } 9用栈实现队列操作 intEnQueue(Stack*s1,Stack*s2,ElemTypex) {if(s1->top==MaxSize)//队列上溢 return-1; else {Push(s1,x); return0; } } intDeQueue(Stack*s1,Stack*s2,ElemType*x) {ElemTypey; while(StackEmpty(s1)! =0)//将s1的所有元素退栈进入s2中 {Pop(s1,y); Push(s2,y); } Pop(s2,x);//将s2的栈顶元素退栈并赋给x while(StackEmpty(s2)! =0)//将s2余下的元素退栈后进入s1中 {Pop(s2,y); Push(s1,y); } } 10共享存储空间的栈的基本操作 top1=1; top2=m; intpush(ElemTypex,inti) {if(top1==top2-1)return-1;//上溢出 elseif(i==1)//对第一个栈进行进栈操作 {top1++; c[top1]=x; } else//对第二个栈进行进栈操作 {top2--; c[top2]=x; } return0; } intpop(ElemType*x,inti) {if(i==1)//对第一个栈进行出栈操作 {if(top1==0)return-1;//栈1下溢出 else {x=c[top1]; top1--; } } else//对第二个栈进行出栈操作 {if(top2==m+1)return-1;//栈2下溢出 else {x=c[top2]; top2++; } } return0; } voidsetnull(inti) {if(i==1)top1=1; elsetop2=m; } 11括号匹配检验 #definem100 Correct(exp,tag) {inttop=0;i=1;tag=1 while(i<=m&&tag) {if(exp[i]==’(‘||exp[i]==’[‘‘||exp[i]==’{‘) st[top++]=exp[i]; if(exp[i]==’)’) if(st[top]==’(’)top--; elsetag=0; if(exp[i]==’]’) if(st[top]==’(’)top--; elsetag=0; if(exp[i]==’}’) if(st[top]==’(’)top--; elsetag=0; i++; } If(top>0)tag=0; } 四查找排序算法 1折半查找 #defineMAX100 typedefstruct {KeyTypekey; ElemTypedate; }RecType; typedefstruct {RecTyper[MAX]; intlength; }sqlist; intBinary_Search(sqlistR,KeyTypek) {intmid,low=1,high=r.length; while(low<=high) {mid=(low+high)/2; if(k high=mid-1; elseif(k>R.r[mid].key) low=mid+1; else returnmid; } return-1; } 2分块查找 3哈希表的插入 hashinsert(ints[],intm,intkey) {H=hash(key); if(s[H]==空)s[H]=key; else {H1=(H+1)%m; while(s[H1]! =空)H1=(H1+1)%m; } s[H1]=key; } 4哈希表的查找 hashsearch(ints[],intm,intkey) {H=hash(key); if(s[H]==空)return-1; elseif(s[H]==key)returnH; else {H1=(H+1)%m; while(s[H1]! =key&&s[H1]! =空&&H1! =H)H1=(H1+1)%m; } if(s[H1]==key)returnH1; elsereturn-1; } 5哈希表的删除 用除留余数法作为哈希函数,用线性探测再散列解决冲突,设计算法删除关键字并将所有可以前移的元素前移填空位置,以尽量保证不断裂 HashDelete(ElemTypes[],intm,intkey) {H=hash(key); if(s[H]==空)return-1; elseif(s[H]==key)delete(s,H,H,key); else {H1=(H+1)%m; while(s[H1]! =key&&s[H1]! =空&&H1! =H)H1=(H1+1)%m; } if(s[H1]==key)delete(s,H,H1,key); elsereturn-1 } delete(ElemTypes[],inti,intj,intkey) {last=j; H1=(j+1)%m; while(H1! =i) {if(s[H1]==空)break; elseif(hash(s[H1]==i))last=H1; H1=(H1+1)%m; } s[j]=s[last];//将最后一个同义词前移 s[last]=空;//置空 } //i为hash(key)得到的值;j为key在s中的位置; //本函数的作用是将s中和关键字key是同义词的关键字找到并确定其 //最后一个位置,然后将最后一个填充到j的位置,将最后一个的置空 6直接插入排序 #defineMAX100 structrec {KeyTypekey;//关键字域 ElemTypedata;//其他数据域 }; typedefstructrecsqlist[MAX];//假定要排序的记录存储在上面这种结构的表中 voidInsertSort(sqlistr,intn) {inti,j; for(i=2;i<=n;i++) {r[0]=r[i]; for(j=i-1;r[0].key r[j+1]=r[j]; r[j+1]=r[0]; } } 7希尔排序 voidshellsort(sqlistr,intn)//本算法的步长是2的整数倍 {inti,j,gap; gap=n/2; while(gap>0) {for(i=gap+1;i<=n;i++) {if(r[i].key {r[0]=r[i]; for(j=i-gap;j>0&&r[0].key r[j+gap]=r[j]; r[j+gap]=r[0]; }//if }//for gap=gap/2; }//while } 8冒泡排序 voidbubblesort(sqlistr,intn) {inti,j,exchange; structrectemp; for(i=1;i<=n-1;i++) {exchange=0; for(j=n;j>=i+1;j--) {if(r[j].key {temp=r[j]; r[j]=r[j-1]; r[j-1]=temp; exchange=1; } } if(exchange==0)return; } } 9快速排序 voidquicksort(sqlistr,ints,intt) {intlow=s,high=t; r[0]=r[low]; while(low {while(low r[low]=r[high]; while(low r[high]=r[low]; } r[low]=r[0]; quicksort(r,s,low-1); quicksort(r,low+1,t); } 非递归算法 10简单选择排序 voidselectsort(sqlistr,intn) {inti,j,k; structrectemp; for(i=1;i<=n-1;i++) {k=i; for(j=j+1;j<=n;j++) {if(r[j].key k=j; } temp=r[i]; r[i]=r[k]; r[k]=temp; } } 11堆排序 voidHeapAdjust(sqllistr,ints,intm) {/*r[s…m]中的记录关键码除r[s]外均满足堆的定义,本函数将对第s个结点为根的子树筛选,使其成为大顶堆*/ structrectemp; temp=r[s]; for(j=2*s;j<=m;j=j*2) {if(j j=j+1; if(temp.key {r[s]=r[j]; s=j; } elsebreak; } r[s]=temp; } voidHeapSort(sqlistrintn) {//对顺序表进行堆排序 for(i=n/2;i>0;i--) HeapAdjust(h,i,n);/*将r[1..n]建成大顶堆*/ for(i=n;i>1;i--) { r[1]<-->r[i];/*堆顶与堆低元素交换*/ HeapAdjust(h,1,i-1);/*将r[1..i-1]重新调整为堆*/ } } 12两路归并排序 voidmerge(sqllist*r,sqllist*rf,intu,intv,intt) {//将有序的r[u…v]和r[v+1…t]归并为有序的rf[u…t] for(i=u,j=v,k=u;i {if(r[i].key { rf[k]=r[i]; i++; } else {rf[k]=r[j]; j++; } } if(i<=v)rf[k…t]=r[i…v-1]; if(j<=t)rf[k…t]=r[j…t]; } voidMSort(sqllist*r,sqllist*r1,ints,intt) {/*将r[s…t]归并排序为r1[s…t]*/ if(s==t)r1[s]=r[s] else {m=(s+t)/2;/*平分*r表*/ MSort(r,r2,s,m);/*递归地将r[s…m]归并为有序的r2[s…m]*/ MSort(r,r2,m+1,t);/*递归地将r[m+1…t]归并为有序的r2[m+1…t]*/ Merge(r2,r1,s,m+1,t);/*将r2[s…m]和r2[m+1…t]归并到r1[s…t]*/ } } voidMergeSort(sqllist*r,intn) {/*对顺序表*r作归并排序*/ MSort(r,r,1,n); } 树形结构 一类型定义 1二叉链表 typedefstructBTreeNode {ElemTypedata; structBTreeNode*lchild; structBTreeNode*rchild; }BiTree; 2线索二叉树 typedefstructBiThrNode {Elemtypedata; structBiThrNode*lchild; structBiThrNode*rchild; intltag; intrtag; }BiThrTree; 二算法 1二叉树的遍历(非递归) a二叉树的层次遍历 voidLevelOrder(BiTree*bt) {intMaxSize=100; BiTree*Queue[MaxSize],*p; intfront=0,rear=0;//定义队列的头指针和尾指针 if(bt==NULL)return; Queue[rear++]=bt; while(front! =rear)//当队列非空时执行循环 {p=Queue[front++]; Visite(p->data);//访问队列的首节点的数据域 if(p->left! =NULL)Queue[rear++]=p->left;//若节点存在左孩子,则左孩子节点指针进入队列 if(p->right! =NULL)Queue[rear++]=p->right;//若节点存在右孩子,则右孩子节点指针进入队列 } } 层次遍历二叉树时,统计二叉树的每一层的信息 intLevelOrder(BiTree*bt) {BiTree*queue[100],*p; intfront=rear=0; intlevel=count=1;//level表示当前的层数;count表示当前层元素的个数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课本 算法 实现