数据结构编程实例.doc

数据结构编程实例
1． 顺序表得基本操作
#define LEN 100
typedef struct sqlist{
int a[LEN];
int length;
};
void init(struct sqlist *sq) /*初始化*/
{int i;
for (i=0;i<LEN;i++)
sq->a[i]=0;
sq->length=0;
}
void creat(struct sqlist *sq) /*建顺序表*/
{int i;
printf("please input length");
scanf("%d",&sq->length);
printf("please input %d nums\n",sq->length);
for (i=1; i<=sq->length;i++)
scanf("%d",&sq->a[i]);
}
void print(struct sqlist *sq) /*输出顺序表*/
{ int i;
for (i=1; i<=sq->length;i++)
printf(" %d",sq->a[i]);
printf("\n");
}
void insert(struct sqlist *sq,int pos, int x) /*顺序表插入元素*/
{int i;
for (i=sq->length;i>=pos;i--)
sq->a[i+1]=sq->a[i];
sq->a[pos]=x;
sq->length=sq->length+1;
}
int delete(struct sqlist *sq,int pos) /*顺序表删除元素*/
{int i,x;
x=sq->a[pos];
for (i=pos+1;i<=sq->length;i++)
sq->a[i-1]=sq->a[i];
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、init\n");
printf("2、creat\n");
printf("3、insert\n");
printf("4、delete\n");
printf("5、locate_value\n");
printf("6、locate_pos\n");
printf("7、print\n");
printf("0、exit\n");
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 (position<1||position>list->length+1||list->length>=LEN)
printf("position error\n");
else insert(list,position,x);
break;
case 4:printf("pleast input delete position(pos)");
scanf("%d",&position);
if (position<1||position>list->length||list->length==0)
printf("position error\n");
else
printf("delete position=%d,delete data=%d\n",position,delete(list,position));
break;;
case 5:;
case 6:;
case 7:print(list);break;
case 0:exit(0);
} } }
2． 三种方法建立链表
#include <stdio、h>
typedef struct node
{int 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;i<=n;i++)
{p=(NODE*) malloc (sizeof (NODE));
scanf("%d",&p->data);
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->data>q->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、zhengxujianlianbiao\n");
printf("2、nixujianlianbiao\n");
printf("3、jianliyouxulianbiao\n");
printf("0、tuichu\n");
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("\n\n");
}
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;
}}
else
while (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 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->rchild!=p))
{if (b<q->d)
{if (q->lchild!=NULL) q=q->lchild;
else q->lchild=p;
}
else
{if (q->rchild!=NULL) q=q->rchild;
else q->rchild=p;
}}}
return(bt);
}
6． 先序（递归）建立二叉树并中序（递归）输出。
#include <stdio、h>
typedef struct bitree
{char 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");
}