信息与计算科学专业数据结构实验报告.doc

实 验 报 告学院：理学院专业年级： 信息与计算科学 姓名： 王然 学号：2009112040127 实验一：顺序表一、 实验目的掌握顺序表的建立，插入，删除操作。二、 实验内容（C语言源程序代码、运行结果）C语言源程序代码：#include#include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct int *elem;int length;int listsize;Sqlist;int InitList_Sq(Sqlist &aL) / 算法2.3 / 构造一个空的线性表L。 aL.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int); if (!aL.elem) return 0; / 存储分配失败 aL.length = 0; / 空表长度为0 aL.listsize = LIST_INIT_SIZE; / 初始存储容量 return 1;int ListInsert_Sq(Sqlist &aL, int i, int e) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 int *p, *q; if (i aL.length+1) return 0; / i值不合法 if (aL.length = aL.listsize) / 当前存储空间已满，增加容量 int *newbase = (int *)realloc(aL.elem, (aL.listsize+LISTINCREMENT)*sizeof (int); if (!newbase) return 0; / 存储分配失败 aL.elem = newbase; / 新基址 aL.listsize += LISTINCREMENT; / 增加存储容量 q = &(aL.elemi-1); / q为插入位置 for (p = &(aL.elemaL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +aL.length; / 表长增1 return 1; / ListInsert_Sqvoid main()int x;Sqlist al;x=InitList_Sq(al);x=ListInsert_Sq(al,1,2);x=ListInsert_Sq(al,2,6);printf(%dn,al.elem0);3运行结果：实验二：链表实验目的掌握链表的建立，插入，删除操作。实验内容（C语言源程序代码、运行结果）C语言源程序代码：#include#include typedef struct LNODEint data;struct LNODE *next;LNODE,*LinkList;void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L LinkList p; int i; L = (LinkList)malloc(sizeof(LNODE); L-next = NULL; / 先建立一个带头结点的单链表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNODE); / 生成新结点 p-data =int(0.1*rand(); / 改为一个随机生成的数字(200以内) p-next = L-next; L-next = p; / 插入到表头 / CreateList_Lint ListInsert_L(LinkList &L, int i, int e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p & j next; +j; if (!p | j i-1) return 0; / i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNODE); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return 1; / LinstInsert_Lint ListDelete_L(LinkList &L, int i, int e) / 算法2.10 LinkList p,q; p = L; int j = 0;while (p-next & j next; +j; if (!(p-next) | j i-1) return 0; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return 1; / ListDelete_Lint main(void)int i,x,e;LinkList al,p;CreateList_L(al,10);p=al-next;for (i=10; i0; -i) printf(%d ,p-data);p=p-next;x=ListInsert_L(al,2,0);p=al-next;printf(insert aftern);for (i=11; i0; -i) printf(%d ,p-data);p=p-next;x= ListDelete_L(al, 2, e);p=al-next;printf(delete aftern);for (i=10; i0; -i) printf(%d ,p-data);p=p-next;return 1;实验三：栈实验目的掌握栈的建立，压栈和删除元素实验内容（C语言源程序代码、运行结果）C语言源程序代码：#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;/栈的当前可使用的最大容量SqStack;int InitStack(SqStack &S)/构造一个空栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)return 0;/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;int Push(SqStack &S,int e)/插入元素e作为新的栈顶元素if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)return 0;/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top=e;+S.top;return 1;int Pop(SqStack &S,int &e)/若栈不空，则删除S的栈顶元素，用e返回2其值，并返回1，否则返回0if(S.top=S.base)return 0;e=*-S.top;return 1;/Popvoid main()int i,j,m;SqStack S1;j=InitStack(S1);for(i=10;i0;-i)*S1.top=i;+S1.top;j=Push(S1,2);printf(%dn,*(S1.top-1);j=Pop(S1,m);j=Pop(S1,m);j=Pop(S1,m);j=Pop(S1,m);printf(%dn,m);3,运行结果：实验四：队列实验目的掌握队列的建立，插入和删除实验内容（C语言源程序代码、运行结果）C语言源程序代码：#include #include typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;int InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(int);if(!Q.front)return 0;/存储分配失败Q.front-next=NULL;return 1;int EnQueue(LinkQueue &Q,int e)/插入元素e为Q的新队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return 0;/存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;int DeQueue(LinkQueue &Q,int e)/若队列不空，则删除Q的队头元素，用e返回其值，并返回1，否则返回0QueuePtr p;if(Q.front=Q.rear)return 0;p=Q.front-ne