数据结构(C语言学习知识版)实验报告

.\\

数据结构(C语言版) 实验报告

专业：计算机科学与技术、软件工程

学号:____201240703061___________________ 班级:_________软件二班______________ 姓名:________朱海霞______________ 指导教师:___刘遵仁________________

青岛大学信息工程学院

2013年10月

.\\

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include #include #define OK 1 #define ERROR 0

#define OVERFLOW -2

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int* elem; int length; int listsize; }Sqlist;

int InitList_Sq(Sqlist &L){ L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L.elem) return -1; L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int ListInsert_Sq(Sqlist&L,int i,int e){ if(i<1||i>L.length+1) return ERROR; if(L.length==L.listsize){

.\\

int *newbase; newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) return -1; L.elem=newbase; L.listsize+=LISTINCREMENT; } int *p,*q; q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }

int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q; if(i<1||i>L.length)return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; }

int main(){ Sqlist L; InitList_Sq(L);//初始化 int i,a[]={3,-5,6,8,2,-5,4,7,-9}; for(i=1;i<10;i++)

ListInsert_Sq(L,i,a[i-1]); for(i=0;i<9;i++) printf(\ %d\ printf(\插入9个数 ListInsert_Sq(L,3,24); for(i=0;i<10;i++) printf(\ %d\ printf(\插入一个数 int e; ListDelete_Sq(L,2, e); for(i=0;i<9;i++) printf(\ %d\删除一个数 printf(\ return 0;

.\\

}

实验结果：

3，-5,6,8,2，-5,4,7，-9 3，-5,24,6,8,2，-5,4,7，-9 3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快；结构简单，逻辑上相邻的元素在物理上也相邻；不使用指针，节省存储空间；但是插入和删除元素需要移动大量元素，消耗大量时间；需要一个连续的存储空间；插入元素可能发生溢出；自由区中的存储空间不能被其他数据共享

实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M），测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除。 5、修改程序：

（1） 增加插入结点的功能。

（2） 建立链表的方法有“前插”、“后插”法。

程序代码:

#include #include #define NULL 0 #define OK 1

#define ERROR 0 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList;

.\\

int InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; return OK; }

int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s; int j; p=L;j=0; while(p&&jnext;++j; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return OK; }

int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q; int j; p=L;j=0; while(p->next&&jnext;++j; } if(!(p->next)||jnext;p->next=q->next; e=q->data;free(q); return OK; }

int main(){ LinkList L,p; char a[8]={'A','C','E','F','H','J','Q','U'}; int i,j; InitList_L(L); for(i=1,j=0;i<=8,j<8;i++,j++) ListInsert_L(L,i,a[j]); p=L->next; while(p!=NULL){ printf(\ p=p->next;