数据结构编程实例.doc

数据结构编程实例1 顺序表得基本操作#define LEN 100typedef struct sqlistint 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; ilength;i+) scanf(%d,&sq-ai); 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) /*顺序表插入元素*/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); 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(please 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); if (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); elseprintf(delete position=%d,delete data=%dn,position,delete(list,position); break; case 5:; case 6:; case 7:print(list);break; case 0:exit(0); 2 三种方法建立链表#include typedef struct nodeint data; struct node *link;NODE;NODE *creat1() /*按输入数据得顺序建立链表，输入数据通过个数控制*/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 input datas(0 end)n);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()/*按输入数据得大小顺序建立带头结点得链表，输入数据以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; 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、jianliyouxulianbiaon); printf(0、tuichun); 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 0: return; p=h; while (p) printf(%5d,p-data); p=p-link; printf(nn); while (x);3 试写出逆转线性单链表得算法要逆转一个线性单链表，只需从头指针指向得结点开始扫描该链表，在扫描过程中改变各结点得指针（由指向后件改为指向原来得前件）即可。Struct node/*ET位数据元素类型*/ET d;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位数据元素类型*/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; 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;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;elsewhile (j!=NULL)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 (k!=NULL) k-next=NULL;return;5 试编写在二叉排序树中插入一个元素得算法。include “stdlib、h”struct btnodeET 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-rchild!=p)if (bd)if (q-lchild!=NULL) q=q-lchild;else q-lchild=p;elseif (q-rchild!=NULL) q=q-rchild;else q-rchild=p;return(bt);6 先序（递归）建立二叉树并中序（递归）输出。#include typedef struct bitreechar 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(); 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);