《2022年数据结构编程实例》由会员分享,可在线阅读,更多相关《2022年数据结构编程实例(14页珍藏版)》请在金锄头文库上搜索。
1、数据结构编程实例1顺序表的基本操作#define LEN 100 typedef struct sqlist int aLEN; int length; ; void init(struct sqlist *sq) /*初始化 */ int i; for (i=0;iai=0; sq-length=0; void creat(struct sqlist *sq) /*建顺序表 */ int i; printf(please input length); scanf(%d,&sq-length); printf(please input %d numsn,sq-length); for (i=1
2、; ilength;i+) scanf(%d,&sq-ai); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 14 页 - - - - - - - - - void print(struct sqlist *sq) /*输出顺序表 */ int i; for (i=1; ilength;i+) printf( %d,sq-ai); printf(n); void insert(struct sqlist *sq,int pos, int x) /*顺序表插入元素 */
3、int i; for (i=sq-length;i=pos;i-) sq-ai+1=sq-ai; sq-apos=x; sq-length=sq-length+1; int delete(struct sqlist *sq,int pos) /*顺序表删除元素 */ int i,x; x=sq-apos; for (i=pos+1;ilength;i+) sq-ai-1=sq-ai; sq-length=sq-length-1; return(x); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -
4、- - - 第 2 页,共 14 页 - - - - - - - - - main() int position,x; struct sqlist *list; struct sqlist slist; int xz=0; list =&slist; while (1) printf(1.initn); printf(2.creatn); printf(3.insertn); printf(4.deleten); printf(5.locate_valuen); printf(6.locate_posn); printf(7.printn); printf(0.exitn); printf(p
5、lease input your choice); scanf(%d,&xz); switch(xz) case 1:init(list);break; case 2:creat(list);break; case 3:printf(pleast input inset position(pos) and value(x); scanf(%d%d,&position,&x); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 14 页 - - - - - - - - - i
6、f (positionlist-length+1|list-length=LEN) printf(position errorn); else insert(list,position,x); break; case 4:printf(pleast input delete position(pos); scanf(%d,&position); if (positionlist-length|list-length=0) printf(position errorn); else printf(delete position=%d,delete data=%dn,position,delete
7、(list,position); break; case 5:; case 6:; case 7:print(list);break; case 0:exit(0); 2三种方法建立链表#include typedef struct node int data; struct node *link;NODE; NODE *creat1() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 14 页 - - - - - - - - - /*按输入数据的顺序建立链表,输入数据通
8、过个数控制*/ int i,data,n; NODE *h=NULL,*p,*last=NULL; printf(please input the num:); scanf(%d,&n); printf(please input %d datas:,n); for (i=1;idata); if (i=1) h=p; else last-link=p; last=p; last-link=NULL; return(h); NODE *creat2() /*按输入数据的逆序建立链表,输入数据以0 结束*/ int data; NODE *h=NULL,*p; printf(please inpu
9、t datas(0 end)n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 14 页 - - - - - - - - - scanf(%d,&data); while (data) p=(NODE*) malloc (sizeof (NODE); p-data=data; if (h=NULL) h=p; h-link=NULL; else p-link=h; h=p; scanf(%d,&data); return(h); NODE *creat3() /*按输
10、入数据的大小顺序建立带头结点的链表,输入数据以0 结束*/ int data; NODE *h,*p,*q,*r; h=(NODE*) malloc (sizeof (NODE); h-link=NULL; printf(please input datas(0 end)n); scanf(%d,&data); while (data) p=(NODE*) malloc (sizeof (NODE); p-data=data; p-link=NULL; if (h-link=NULL) h-link=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
11、 - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 14 页 - - - - - - - - - else r=h; q=r-link; while (p-dataq-data & q) r=q; q=q-link; if (q) p-link=q; r-link=p; scanf(%d,&data); return(h-link); main() NODE *h,*p; int x; do printf(=n); printf(1.zhengxujianlianbiaon); printf(2.nixujianlianbiaon); printf(3.jian
12、liyouxulianbiaon); printf(0.tuichun); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 14 页 - - - - - - - - - printf(=n); printf(please input your chosice); scanf(%d,&x); switch(x) case 1: h=creat1();break; case 2: h=creat2();break; case 3: h=creat3();break; case
13、 0: return; p=h; while (p) printf(%5d,p-data); p=p-link; printf(nn); while (x); 3试写出逆转线性单链表的算法要逆转一个线性单链表,只需从头指针指向的结点开始扫描该链表,在扫描过程中改变各结点的指针(由指向后件改为指向原来的前件)即可。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 14 页 - - - - - - - - - Struct node /*ET 位数据元素类型 */ ET d;
14、struct node *next ; invlst(head) struct node *head ; struct node *p, *q, *r ; if (*head=NULL) return; p=*head; q=p-next; p-next=NULL; while (q!=NULL) r=q-next; q-next=p; p=q; q=r; *head=p; return; 4设有两个有序线性单链表,头指针分别为AH 和 BH。试写出将两个有序线性单链表合并为一个头指针为CH 的有序线性单链表的算法,要求去掉重复元素。Struct node /*ET 位数据元素类型 */ 名师
15、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 14 页 - - - - - - - - - ET d; struct node *next ; #include “ stdio.h”mglst1(ah,bh,ch) struct node ah,bh,*ch; struct node *i, *j, *k, *p; et x; i=ah; j=bh; *ch=NULL; k=NULL; while (i!=NULL)&(j!=NULL) if (j-d=i-d) x=i-d
16、; i=i-next; else x=j-d; j=j-next; if (*ch=NULL) p=(struct node *) malloc (sizeof(struct node); p-d=x; *ch=p; k=p; else if (d!=k-d) p=(struct node *) malloc (sizeof(struct node); p-d=x; k-next=p; k=p; if (j=NULL) while (i!=NULtructL) x=i-d; i=i-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
17、 - - - 名师精心整理 - - - - - - - 第 10 页,共 14 页 - - - - - - - - - if (*ch=NULL) p=(struct node *) malloc (sizeof(struct node); p-d=x; *ch=p; k=p; else if (d!=k-d) p=(struct node *) malloc (sizeof(struct node); p-d=x; k-next=p; k=p; else while (j!=NULL) x=j-d; j=j-next; if (*ch=NULL) p=(struct node *) mall
18、oc (sizeof(struct node); p-d=x; *ch=p; k=p; else if (d!=k-d) p=(struct node *) malloc (sizeof(struct node); p-d=x; k-next=p; k=p; if (k!=NULL) k-next=NULL; return; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 14 页 - - - - - - - - - 5试编写在二叉排序树中插入一个元素的算法。inclu
19、de “ stdlib.h”struct btnode ET d; struct btnode *lchild; struct btnode *rchild; ; struct btnode *insort(bt,b) struct btnode *bt; ET b; struct btnode *p, *q; p=(struct btnode *)malloc (sizeof(struct btnode); p-d=b; p-lchild=NULL; p-rchild=NULL; q=bt; if (q=NULL) bt=p; else while (q-lchild!=p) & (q-rc
20、hild!=p) if (bd) if (q-lchild!=NULL) q=q-lchild; else q-lchild=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 14 页 - - - - - - - - - else if (q-rchild!=NULL) q=q-rchild; else q-rchild=p; return(bt); 6先序(递归)建立二叉树并中序(递归)输出。#include typedef struct bitree char
21、data; struct bitree *lchild,*rchild; BTREE; BTREE *creatree() BTREE *t; char ch; scanf(%c,&ch); if (ch= ) t=NULL; else t=(BTREE*) malloc (sizeof(BTREE); t-data=ch; t-lchild=creatree(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 14 页 - - - - - - - - - t-rchild=creatree(); return(t); void inorder(BTREE *bt) if(bt!=NULL) inorder(bt-lchild); printf(%c ,bt-data); inorder(bt-rchild); main() BTREE *root; root=creatree(); inorder(root); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 14 页 - - - - - - - - -