数据结构编程实例

1、数据结构编程实例1. 顺序表的基本操作#defi ne LEN 100 typ edef struct sqlist int aLEN;int len gth;void init(struct sqlist *sq) /* 初始化 */ int i;for (i=0;i<LEN;i+)sq->ai=0;sq->le ngth=0;void creat(struct sqlist *sq)/* 建顺序表 */ int i;p ri ntf("p lease input len gth");sca nf("%d", &sq->

2、le ngth);p ri ntf("p lease input %d numsn ”,sq->le ngth);for (i=1; i<=sq->le ngth;i+)sca nf("%d", &sq->ai);void print(struct sqlist *sq) /* 输出顺序表 */ int i;for (i=1; i<=sq->le ngth;i+)printf(" %d",sq->ai);prin tf("n");voidinsert(struct sqlis

3、t *sq,int pos, int x)/*顺序表插入元素 */ int i;for (i=sq->le ngth;i> 二p os;i-)sq->ai+1=sq->ai;sq->a po s=x;sq->le ngth二sq->le ngth+1;int delete(struct sqlist *sq,int pos) /*顺序表删除元素 */ int i,x;x=sq->a po s;for (i 二p os+1;i<二sq->le ngth;i+)sq->ai-1=sq->ai;sq->le ngth二sq

4、->le ngth-1;return(x);mai n() int po siti on,x;struct sqlist *list;struct sqlist slist;int xz=0;list 二&slist;while (1) prin tf("1.i ni tn");prin tf("2.creatn");prin tf("3.i nsert n");prin tf("4.deleten");prin tf("5.locate_valuen");prin tf(&quo

5、t;6.locate_ posn");prin tf("7. prin tn");prin tf("0.exitn");printf("pl ease input your choice");sca nf("%d", &xz);switch(xz)case 1:i nit(list);break;case 2:creat(list);break;case 3:prin tf(" pleast input in set po siti on(p os) and value(x)"

6、);sca nf("%d%d",&po siti on,&x);if (p ositi on <1| po siti on >list->le ngth+1|list->le ngth>=LEN)pnntf("po siti on error'n");else in sert(list, positi on, x);break;case 4:pnntf("pleast input delete position(pos)");sca nf("%d",&p

7、 ositio n);if (p ositi on <1| po siti on >list->le ngth|list->le ngth=O)pnntf("po siti on error'n");elseprin tf("delete p ositi on=%d,delete data=%dn", positi on, delete(list ,p ositi on);break;case 5:;case 6:;case 7:prin t(list);break;case 0:exit(0);2. 三种方法建立链表#i

8、n clude <stdio.h> typ edef struct node int data;struct n ode *li nk;NODE;NODE *creat1()/*按输入数据的顺序建立链表，输入数据通过个数控制*/ int i,data ,n;NODE *h=NULL,* p,*last二NULL;pnntf("p lease input the nu m:");sca nf("%d",&n);pnntf("p lease input %d datas:", n);for (i=1;i< 二n

9、;i+)p=(NODE*) malloc (sizeof (NODE);sca nf("%d",&p->data);if (i=1) h二p;else last->li nk二p;last 二p;last->li nk二NULL;return(h);NODE *creat2()/*按输入数据的逆序建立链表，输入数据以0结束*/ int data;NODE *h=NULL,* p;pnntf("p lease input datas(0 end)n");sea nf("%d",&data);while

10、(data)p=(NODE*) malloe (sizeof (NODE);p->data二data;if (h=NULL) h=p; h->li nk二NULL;else p->li nk二h; h=p;sea nf("%d"，& data);return(h);NODE *ereat3()/*按输入数据的大小顺序建立带头结点的链表，输入数据以0结束*/ int data;NODE *h,* p,*q,*r;h=(NODE*) malloe (sizeof (NODE); h->li nk二NULL;pnntf("p lease

11、input datas(0 end)n");sea nf("%d"，&data);while (data)p=(NODE*) malloe (sizeof (NODE);p->data二data; p->li nk二NULL;if (h->li nk=NULL) h->li nk二p;elser=h; q=r->li nk;while (p->data>q->data && q)r=q; q=q->li nk;if (q)p->li nk二q;r->li nk二p;sca n

12、f("%d"，& data);return(h->li nk);mai n() NODE *h,* p;int x;don");printf(”prin tf("1.zhe ngxujia nlia nbiaon");prin tf("2. nixujia nlia nbiao'n");prin tf("3.jia nliyouxulia nbiaon");prin tf("0.tuichun");printf(”pnntf("pl ease input

13、 your chosice");sea nf("%d"，&x);switch(x)case 1: h=creat1();break;case 2: h=creat2();break;case 3: h=creat3();break;case 0: retu rn;p=h;while (p)prin tf("%5d", p->data);p二p->li nk;prin tf("n'n");while (x);3. 试写出逆转线性单链表的算法要逆转一个线性单链表，只需从头指针指向的结点开始扫描该链表,

14、在扫描过程中改变各结点的指针（由指向后件改为指向原来的前件）即可。Struct node/*ET位数据元素类型*/ET d;struct node *next ； in vlst(head) struct node *head ;struct node *p, *q, *r ;if (*head=NULL) return;p 二*head; q二p->n ext;p-> next二NULL;while (q!=NULL) r二q->n ext; q->n ext 二p;p=q; q=r;*head 二p;return;4. 设有两个有序线性单链表，头指针分别为 AH和B

15、H。试写出将两个有序线性单链表合并为一个头指针为CH的有序线性单链Struct node/*ET位数据元素类型*/表的算法，要求去掉重复元素。ET d;struct node *next ； #inelude 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; i=i->n ext;

16、else x=j->d; j=j-> next; if (*ch=NULL) p二(struct node *) malloc (sizeof(struct no de);p->d=x; *ch 二p; k二p;else if (d!=k->d) p二(struct node *) malloc (sizeof(struct no de);p->d=x; k->n ext 二p; k=p; if (j=NULL) while (i!=NULtructL) x=i->d; i=i->n ext;if (*ch=NULL) p二(struct nod

17、e *) malloc (sizeof(struct no de);p->d=x; *ch 二p; k二p;else if (d!=k->d) p二(struct node *) malloc (sizeof(struct no de);p->d=x; k->n ext 二p; k二p; else while (j!=NULL) x=j->d; j=j->n ext;if (*ch=NULL) p二(struct node *) malloc (sizeof(struct no de);p->d=x; *ch 二p; k二p;else if (d!=k

18、->d) p二(struct node *) malloc (sizeof(struct no de);p->d=x; k->n ext 二p; k二p; if (k!二NULL) k->n ext=NULL;return;5. 试编写在二叉排序树中插入一个元素的算法。# include stdlib.h ”struct btnode ET d;struct btnode *lchild;struct btnode *rchild;； struct btnode *in sort(bt,b) struct btnode *bt;ET b;struct btnode *p, *q;p=(struct btnode *)malloc (sizeof(struct btno de);p->d=b; p->lchild二NULL; p->rchild二NULL;q=bt;if (q=NULL) bt二p;elsewhile (q->lchild!=p) && (q->rchild!二 p) if (b<q->d) if (q->lchi