实验一 线性表
一、 实验目的
1. 掌握在Borland C 3.1的集成环境中调试程序的基本方法。 2. 掌握线性表的插入和删除操作在顺序存储结构上的实现。
3. 掌握线性表的建立、插入、删除、打印和查找操作在链式存储结构上的实现。 4. 理解一元多项式的求和操作在链式存储结构上的实现。
二、 实验内容
1. 线性表的插入和删除操作在顺序存储结构上的实现。其中函数insertsqllist的功能是在顺序线性表中第i个元素之前插入一个元素，函数deletesqlist的功能是删除顺序线性表中第i个元素。 #define m 1000 #include \
typedef int datatype;
typedef struct{datatype a[m]; int n;} sqlist; void insertsqlist (sqlist &list, int i, datatype x) {
int j;
if(list.n+1>m) printf(\
else if(i<1||i>list.n+1) printf(\else {
for(j=list.n-1;j>=i-1; j--) list.a[j+1]=list.a[j];
/* 以上循环语句的功能是将从第i个位置开始的元素均向后移动一个位置 */ list.a[i-1]=x; list.n=list.n+1; }
}
void deletesqlist(sqlist &list, int i, datatype *y) {
int j;
if(i<1||i>list.n) printf(\else {
*y=list.a[i-1]; list.n=list.n-1;
for(j=i;j<=list.n-1; j++) list.a[j-1]=list.a[j]; } }
main( ) {
datatype i,y;
sqlist list={{1,2,3,4},4}; /* 初始化线性表list中有4个元素 */ for(i=0; i for(i=0; i - 1 - for(i=0; i } 2. 线性表的建立、插入、删除、打印和查找操作在链式存储结构上的实现。其中函数createlklist的功能是利用从尾部插入的方法建立一个有n个结点的单链表，函数printlklist的功能是从单链表的头部开始顺序打印单链表，函数locatelklist的功能是在单链表查找指定的结点并将指向该结点的指针作为函数值返回，函数insertlklist的功能是在单链表中值为y的结点之前插入一个值为x的新结点，函数deletelklist的功能是在单链表中删除值为x的结点。 #include \#include \#define n 10 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void createlklist(lklist *&head ) { int i; lklist *p,*q; for (i=1;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist)); scanf(\ if(i==1)head=q=p;else {q->next=p;q=p;} } } void printlklist(lklist *head) { lklist *p=head; while(p!=0){ printf(\ printf(\ } lklist *locatelklist(lklist *head,datatype x) { lklist *p=head; while(p!=0) {if(p->data==x) return(p); else p=p->next;} return(0); } void insertlklist(lklist *&head, datatype x, datatype y) { lklist *r,*p,*q; r=(lklist *)malloc(sizeof(lklist)); r->data=x; if (head==0) printf(\ else if (head->data==y){r->next=head; head=r;} else { for(q=head, p=head->next; p!=0; q=p, p=p->next) if (p->data==y) break; if (p!=0){q->next=r; r->next=p;} else printf(\} } - 2 - void deletelklist(lklist *&head, datatype x) { lklist *p,*q; if(head==0) printf(\ else if(head->data==x) {p=head; head=head->next; free(p); } else { for(q=head, p=head->next;p!=0; q=p, p=p->next) if (p->data==x) break; if(p!=0){q->next=p->next; free(p);}else printf(\ } } main( ) { lklist *head=0,*p; createlklist(head); printlklist(head); p=locatelklist(head,2); if (p!=0) printf(\ %d\\n\else printf(“not found\\n”); insertlklist(head,100,3); printlklist(head); deletelklist(head,2); printlklist(head); } 3. 一元多项式的求和操作在链式存储结构上的实现。其中函数createlklist是利用从尾部插入结点的方法建立链式结构表示一元多项式，函数createitem的功能是生成结果多项式中的一个结点并将之链接到结果多项式链表中，函数printlklist的功能是从单链表头部开始顺序打印单链表中的结点元素，函数addmutiploy的功能是计算两个一元多项式的和。 #include \#include \#define n 4 struct node{int exp; float coef; struct node *next;}; void createlklist(struct node *&head ) { int i; struct node *p,*q; for (i=1;i<=n;i++) { p=(struct node *)malloc(sizeof(struct node )); scanf(\ if(i==1)head=q=p;else {q->next=p;q=p;} } } void createitem(struct node *&pc,float coef,int exp) { struct node *p; p=(struct node *)malloc(sizeof(struct node)); p->next=0; p->coef=coef; p->exp=exp; pc->next=p; pc=p; } void printlklist(struct node *head) { - 3 - struct node *p=head; while(p!=0){ printf(\ printf(\} void addmutiploy(struct node *pah,struct node *pbh,struct node *&pch) { struct node *pa=pah,*pb=pbh,*pc=0; float x; pc=pch=(struct node *)malloc(sizeof(struct node)); /* 为头指针pch申请头结点 */ while(pa!=0 && pb!=0) { if(pa->exp==pb->exp) {x=pa->coef+pb->coef; if(x!=0)createitem(pc,x,pa->exp);pa=pa->next; pb=pb->next;} else if(pa->exp>pb->exp){createitem(pc,pa->coef,pa->exp); pa=pa->next;} else if(pa->exp while (pa!=0) {createitem(pc,pa->coef,pa->exp); pa=pa->next;} while (pb!=0) {createitem(pc,pb->coef,pb->exp); pb=pb->next;} pc=pch; pch=pch->next; free(pc); /* 释放头指针pch中的头结点 */ } main( ) { struct node *pa=0,*pb=0,*pc=0; createlklist(pa); printlklist(pa); createlklist(pb); printlklist(pb); addmutiploy(pa,pb,pc);printlklist(pc); } - 4 - 实验二 栈和队列 一、 实验目的 1． 掌握栈的入栈和出栈操作在顺序存储结构上的实现。 2． 掌握栈的入栈和出栈操作在链式存储结构上的实现。 3． 掌握队列的入队列和出队列操作在顺序存储结构上的实现。 4． 掌握队列的入队列和出队列操作在链式存储结构上的实现。 二、 实验内容 1． 栈的入栈和出栈操作在顺序存储结构上的实现。其中函数pushsqstack的功能是实现入栈操作，函数popsqstack的功能是实现出栈操作。 #include \#define m 100 typedef int datatype; typedef struct{datatype s[m]; int top;}sqstack; void pushsqstack(sqstack &stack, datatype x) { if (stack.top==m-1) printf(\ else { stack.top=stack.top+1; stack.s[stack.top]=x; } } void popsqstack(sqstack &stack, datatype *y) { if (stack.top== -1) printf(\ else { *y=stack.s[stack.top]; stack.top=stack.top-1; } } main( ) { int y; sqstack stack={{1,2,3,4,5},4}; /* 初始化stack栈中的元素及当前栈顶指针 */ pushsqstack(stack,100); pushsqstack(stack,200); popsqstack(stack,&y); printf(\ popsqstack(stack,&y); printf(\ popsqstack(stack,&y); printf(\ } 2． 入栈和出栈操作在链式存储结构上的实现。其中函数pushlkstack的功能是实现链栈的入栈操作，函数poplkstack的功能是实现链栈的出栈操作。 #include \#include \#define n 10 typedef int datatype; typedef struct node {datatype data; struct node *next;}lkstack; void pushlkstack(lkstack *&top, datatype x) { lkstack *p; p=(lkstack *)malloc(sizeof(lkstack)); p->data=x; p->next=top; top=p; } - 5 -