《数据结构》上机实验参考程序.doc

实验一 单链表的建立、删除和插入 参考程序 #include stdio.h #include malloc.h #define N 5 typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; LNode *CreateList(int n) /* 算法2.11 ,见课本p30*/ { /* 逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L */ int i; LinkList p,L; L=(LinkList)malloc(sizeof(struct LNode)); L-next=NULL; /* 先建立一个带头结点的单链表 */ printf(请输入%d个数据\n,n); for(i=n;i0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ scanf(%d,p-data); /* 输入元素值 */ p-next=L-next; /* 插入到表头 */ L-next=p; } return L; } Lnode *insert(LinkList L,int i,int e)/*算法2.9，见课本p29*/ {/*在带头结点的单链线性表L中第i个位置之前插入元素e*/ LinkList p=L,s; int j=0; while(pji-1) {p=p-next; ++j;} if(!p||ji-1) return L; /*假如i小于1或者大于表长，则不插入结点，返回原链表*/ s=(LinkList)malloc(sizeof(struct LNode)); s-data=e; s-next=p-next; p-next=s; return L; } LNode *delete1(LinkList L,int i,int *e)/*算法2.10,见课本p30*/ {/*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/ LinkList p=L,q; int j=0; while(p-nextji-1){ /*寻找第i个结点，并令p指向其前趋*/ p=p-next; ++j; } if(!(p-next)||ji-1) return L; /* 删除位置不合理 */ q=p-next; p-next=q-next; *e=q-data; free(q); return L; } void ListTraverse(LinkList L) {LinkList p=L-next; while(p) {printf(%d ,p-data); p=p-next; } printf(\n); } void main() { LinkList Lb; int *p=NULL; Lb=CreateList(N); /* 逆位序输入n个元素的值 */ printf(Lb=); /* 输出链表Lb的内容 */ ListTraverse(Lb); Lb=insert(Lb,2,9);/*在带头结点的单链线性表L中第i个位置之前插入元素e*/ printf(Lb=); /* 输出链表Lb的内容 */ ListTraverse(Lb); Lb=delete(Lb,3,p);/*在带头结点的单链线性表L中，删除第i个元素，并由p返回其值*/ printf(Delete number:%d\n,*p); printf(Lb=); /* 输出链表Lb的内容 */ ListTraverse(Lb); } 实验二 栈的建立、插入和删除 参考程序 #include stdio.h #include malloc.h #define STACK_INIT_SIZE 100 /*存储空间初始分配量*/ #define INC 10 /*存储空间分配增量*/ typedef struct {char *base; /*在栈构造之前和销毁之后，base值为NULL*/ char *top; /*栈顶指针*/ int stacksize; /*当前已分配的存储空间，以元素为单位*/ }sqstack; void Initstack(sqstack *s) {/*构造一个空栈S*/ (*s).base=(char*)mall