数据结构实验报告-实验一顺序表、单链表基本操作的实现

实验⼀ 顺序表、单链表基本操作的实现

l 实验⽬的1、顺序表

（1）掌握线性表的基本运算。

（2）掌握顺序存储的概念，学会对顺序存储数据结构进⾏操作。

（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容1、 顺序表

1、编写线性表基本操作函数：

（1）InitList(LIST *L,int ms)初始化线性表；

（2）InsertList(LIST *L,int item,int rc)向线性表的指定位置插⼊元素； （3）DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；（4）DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；（5）FindList(LIST *L,int item)查找线性表的元素；（6）OutputList(LIST *L)输出线性表元素；2、调⽤上述函数实现下列操作：（1）初始化线性表；

（2）调⽤插⼊函数建⽴⼀个线性表；（3）在线性表中寻找指定的元素；（4）在线性表中删除指定值的元素；（5）在线性表中删除指定位置的元素；（6）遍历并输出线性表；

l 实验结果1、顺序表（1）流程图

（2）程序运⾏主要结果截图

（3）程序源代码

#include#include#include

struct LinearList/*定义线性表结构*/{

int *list; /*存线性表元素*/ int size; /*存线性表长度*/

int Maxsize; /*存list数组元素的个数*/};

typedef struct LinearList LIST;

void InitList(LIST *L,int ms)/*初始化线性表*/{

if((L->list=(int*)malloc(ms*sizeof(int)))==NULL) {

printf(\"内存申请错误\"); exit(1); }

L->size=0; L->Maxsize=ms;}

int InsertList(LIST *L,int item,int rc)/*item记录值；rc插⼊位置*/{ int i;

if(L->size==L->Maxsize)/*线性表已满*/ return -1; if(rc<0) rc=0; if(rc>L->size) rc=L->size;

for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/ L->list[i+=1]=L->list[i]; L->list[rc]=item; L->size++; return 0;}

void OutputList(LIST *L)/*输出线性表元素*/{ int i;

for(i=0;isize;i++)

printf(\"%d\",L->list[i]); printf(\"\\n\");}

int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/{ int i;

for(i=0;isize;i++) if(item==L->list[i]) return i; return -1;}

int DeleteList1(LIST *L,int item)/*删除 指定元素值得线性表记录，返回值为>=0为删除成功*/{ int i,n;

for(i=0;isize;i++) if(item==L->list[i]) break; if(isize) {

for(n=i;nsize-1;n++) L->list[n]=L->list[n+1]; L->size--; return i; } return -1;}

int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{ int i,n;

if(rc<0||rc>=L->size) return -1;

for(n=rc;nsize-1;n++) L->list[n]=L->list[n+1]; L->size--; return 0;}int main(){

LIST LL; int i,r;

printf(\"list addr=%p\size=%d\Maxsize=%d\\n\",LL.list,LL.size,LL.Maxsize); InitList(&LL,10);

printf(\"list addr=%p\size=%d\Maxsize=%d\\n\",LL.list,LL.list,LL.Maxsize);

while(1) {

printf(\"请输⼊元素值，输⼊0结束插⼊操作:\"); fflush(stdin);/*清空标准输⼊缓冲区*/ scanf(\"%d\",&i); if(i==0) break;

printf(\"请输⼊插⼊位置：\"); scanf(\"%d\",&r); InsertList(&LL,i,r-1); printf(\"线性表为：\"); OutputList(&LL); } while(1) {

printf(\"请输⼊查找元素值，输⼊0结束查找操作：\"); fflush(stdin);/*清空标准输⼊缓冲区*/ scanf(\"%d \",&i); if(i==0) break;

r=FindList(&LL,i); if(r<0)

printf(\"没有找到\\n\"); else

printf(\"有符合条件的元素，位置为：%d\\n\",r+1); } while(1) {

printf(\"请输⼊删除元素值，输⼊0结束查找操作：\"); fflush(stdin);/*清楚标准缓存区*/ scanf(\"%d\",&i); if(i==0) break;

r=DeleteList1(&LL,i); if(i<0)

printf(\"没有找到\\n\"); else{

printf(\"有符合条件的元素，位置为：%d\\n线性表为：\",r+1); OutputList(&LL); }

} while(1) {

printf(\"请输⼊删除元素位置，输⼊0结束查找操作：\"); fflush(stdin);/*清楚标准输⼊缓冲区*/ scanf(\"%d\",&r); if(r==0) break;

i=DeleteList2(&LL,r-1); if(i<0)

printf(\"位置越界\\n\"); else {

printf(\"线性表为：\"); OutputList(&LL); } }}

链表基本操作

l 实验⽬的2、链表

（1）掌握链表的概念，学会对链表进⾏操作。

（2）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容

1、编写链表基本操作函数：

（1）InitList(LIST *L,int ms)初始化链表；

（2）InsertList1(LIST *L,int item,int rc)向链表的指定位置插⼊元素；（3）InsertList2(LIST *L,int item,int rc)向有序链表的指定位置插⼊元素；（4）DeleteList(LIST *L,int item)删除指定元素值的链表记录；（5）FindList(LIST *L,int item)查找链表中的元素；（6）OutputList(LIST *L)输出链表中的元素；2、调⽤上述函数实现下列操作：（1）初始化链表；

（2）调⽤插⼊函数建⽴⼀个链表；（3）在链表中寻找指定的元素；（4）在链表中删除指定值的元素；（5）遍历并输出链表；

l 实验结果（1）、流程图：

（2）程序运⾏主要结果截图：

（3）程序源代码：

#include#includetypedef struct list{

int data; struct list *next;}LIST;

void initlist(LIST **p){

*p=NULL;}

void insertlist1(LIST **p,int item,int rc){ int i;

LIST *u,*q,*r;

u=(LIST*)malloc(sizeof(LIST)); u->data=item;

for(i=1,r=*p;inext; } if(r==*p) *p=u; else

q->next=u; u->next=r;}

void insertlist2(LIST **p,int item){

LIST *u,*q,*r;

u=(LIST*)malloc(sizeof(LIST)); u->data=item;

for(r=*p;r!=NULL&&r->datanext) if(r==*p) *p=u; else

q->next=u; u->next=r; }

int deletelist(LIST **p,int item){

LIST *q,*r; q=*p;r=q; if(q==NULL) return 1; if(q->data==item) {

*p=q->next; free(r); return 0; }

for( ;q->data!=item&&q->next!=NULL;r=q,q=q->next) if(q->data==item) {

r->next=q->next; free(q); return 0;

} return 1;}

int findlist(LIST *p,int item){ int i;

for(i=1;p->data!=item&&p!=NULL;p=p->next,i++) return(p==NULL)?-1:i;}

void outputlist(LIST *p){

while(p!=NULL) {

printf(\"%4d\",p->data); p=p->next; }

printf(\"\\n\");}

void freelist(LIST **p){

LIST *q,*r; for(q=*p;q!=NULL;) { r=q; q=q->next; free(r); } *p=NULL;}int main(){

LIST *p; int op,i,rc; initlist(&p); while(1) {

printf(\"---------------\\n\"); printf(\"- 1：指定位置追加\\n\"); printf(\"- 2：升序追加\\n\"); printf(\"- 3：查找结点\\n\"); printf(\"- 4：删除结点\\n\"); printf(\"- 5：输出链表\\n\");

printf(\"- 6：清空链表\\n\"); printf(\"- 0：退出\\n\"); printf(\"--------------\\n\");

printf(\"请输⼊0~6 进⾏操作：\"); fflush(stdin); scanf(\"%d\",&op); switch(op) { case 0: return -1; case 1:

printf(\"请输⼊新增结点的键值和位置：\"); scanf(\"%d%d\",&i,&rc); insertlist1(&p,i,rc); break; case 2:

printf(\"请输⼊新增结点的键值：\"); scanf(\"%d\",&i); insertlist2(&p,i); break; case 3:

printf(\"请输⼊要查找结点的键值：\"); scanf(\"%d\",&i); rc=findlist(p,i); if(rc>0)

printf(\" 位置位 %d\\n\",rc); else

printf(\"没有找到\\n\"); break; case 4:

printf(\"请输⼊要删除的结点的键值：\"); scanf(\"%d\",&i); rc=deletelist(&p,i); if(rc==0)

printf(\"删除成功！\\n\",rc); else

printf(\"没找到！\\n\"); break; case 5:

printf(\"\\n 链表内容为：\\n\"); outputlist(p); break;

case 6: freelist(&p); break; } }}