“数据结构和算法II”课程实验报告实验名称：线性表的存储结构定义及基本操作班级姓名学号实验日期：实验机时：2 学时实验成绩：-------------------------------------------------------------------------------一.实验目的：1.掌握线性表的逻辑特征2.掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算3.熟练掌握线性表的链式存储结构定义及基本操作4.理解循环链表和双链表的特点和基本运算5.加深对栈结构的理解，培养解决实际问题的编程能力。

6.加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二.实验内容：（1）基本实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。

（2）扩展实验内容：查前驱元素、查后继元素、顺序表合并，两个有序单链表的合并操作等。

三.程序及注释：1.顺序表：#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int status ;typedef int ElemType ;typedef struct{ElemType *elem;int length,listsize;}SqList;status InitList(SqList &L)//初始化{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.listsize=LIST_INIT_SIZE;L.length=0;return OK;}status Build(SqList &L)//建立表{int i,n;printf("请输入元素个数n和n个元素\n");scanf("%d",&n);if(n>LIST_INIT_SIZE)//如果n大于当前空间{L.elem=(ElemType *)realloc(L.elem,(n+LISTINCREMENT)*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.listsize=n+LISTINCREMENT;}for(i=0;i<n;i++)scanf("%d",L.elem+i);L.length=n;return OK;}void Print(SqList &L)//输出表中元素和长度{int i;for(i=0;i<L.length;i++)printf("%d ",*(L.elem+i));printf("\n长度为:%d\n\n",L.length);}void Tips()//提示函数{printf("请选择你的想要的操作：\n");printf("<1> 输出顺序表及顺序表的长度\n");printf("<2> 删除值为x的结点\n");printf("<3> 删除给定位置i的结点\n");printf("<4> 将顺序表逆置\n");printf("<5> 将顺序表按升序排序\n");printf("<6> 将x插入到顺序表的适当位置上\n");printf("<7> 将两个有序表合并\n");printf("<0> 退出\n\n");}status ListDelete1(SqList &L,int x)//删除值为X的元素{int i;for(i=0;i<L.length;i++)if(*(L.elem+i)==x)break;if(i==L.length)return ERROR;for(i++;i<L.length;i++)*(L.elem+i-1)=*(L.elem+i);L.length--;return OK;}status ListDelete2(SqList &L,int x)//删除第X个元素{int i;if(x<0||x>=L.length)return ERROR;for(i=x+1;i<L.length;i++)*(L.elem+i-1)=*(L.elem+i);L.length--;return OK;}void Inverse(SqList &L)//逆置函数{int i,t;for(i=0;i<L.length/2;i++){t=*(L.elem+i);*(L.elem+i)=*(L.elem+L.length-i-1);*(L.elem+L.length-i-1)=t;}}void Sort(SqList &L)//冒泡排序（升序）{int i,j,t;for(i=1;i<L.length;i++)for(j=0;j<L.length-i;j++){if(*(L.elem+j)>*(L.elem+j+1)){t=*(L.elem+j);*(L.elem+j)=*(L.elem+j+1);*(L.elem+j+1)=t;}}printf("已按升序排列\n\n");}status ListInsert(SqList &L,int x)//将X插入，使仍然有序{int i,k;if(L.length>=L.listsize){L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);L.listsize+=LISTINCREMENT;}for(i=0;i<L.length;i++)if(x<*(L.elem+i))break;k=i;for(i=L.length;i>k;i--)*(L.elem+i)=*(L.elem+i-1);*(L.elem+k)=x;L.length++;return OK;}status Merger(SqList &L,SqList &Lb)//合并两个线性表{int i,j,k;SqList Lc;InitList(Lc);if(Lc.listsize<L.length+Lb.length){Lc.elem=(ElemType *)realloc(Lc.elem,(L.length+Lb.length+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);Lc.listsize=L.length+Lb.length+LISTINCREMENT;}i=j=k=0;while(i<L.length && j<Lb.length){if(*(L.elem+i) < *(Lb.elem+j)){*(Lc.elem+k)=*(L.elem+i);k++;i++;}else{*(Lc.elem+k)=*(Lb.elem+j);k++;j++;}}while(i<L.length){*(Lc.elem+k)=*(L.elem+i);k++;i++;}while(j<Lb.length){*(Lc.elem+k)=*(Lb.elem+j);k++;j++;}Lc.length=L.length+Lb.length;L=Lc;return OK;}int main(){int op,x,flag;SqList L,Lb;InitList(L);Build(L);Tips();scanf("%d",&op);while(op){switch(op){case 1:Print(L);case 2:printf("请输入要删除的数据X:\n");scanf("%d",&x);flag=ListDelete1(L,x);if(flag)printf("删除成功!!\n\n");elseprintf("元素不存在,删除失败!!\n\n");break;case 3:printf("请输入要删除的位置i:\n");scanf("%d",&x);flag=ListDelete2(L,x-1);//第i个元素对应的下标为i-1 if(flag)printf("删除成功!!\n\n");elseprintf("元素不存在,删除失败!!\n\n");break;case 4:Inverse(L);break;case 5:Sort(L);break;case 6:printf("请输入要插入的数据X:\n");scanf("%d",&x);flag=ListInsert(L,x);if(flag)printf("插入成功!!\n\n");elseprintf("插入失败!!\n\n");break;case 7:printf("请输入Lb的内容:\n");InitList(Lb);Build(Lb);flag=Merger(L,Lb);if(flag)printf("合并成功!!\n\n");break;}Tips();scanf("%d",&op);}2.单链表typedef int ElementType;#ifndef _List_H#define _List_Hstruct Node;typedef struct Node *PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;List MakeEmpty( List L );int IsEmpty( List L );int IsLast( Position P, List L );Position Find( ElementType X, List L );void Delete( ElementType X, List L );Position FindPrevious( ElementType X, List L );void Insert( ElementType X, List L, Position P );void DeleteList( List L );Position Header( List L );Position First( List L );Position Advance( Position P );ElementType Retrieve( Position P );#endif#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) struct Node{ElementType Element;Position Next;};List MakeEmpty( List L ) //创建空链表{if( L != NULL )DeleteList( L );L = malloc( sizeof( struct Node ) );if( L == NULL )FatalError( "Out of memory!" );L->Next = NULL;return L;}int IsEmpty( List L )//判断链表是否为空{return L->Next == NULL;}int IsLast( Position P, List L ){return P->Next == NULL;}Position Find( ElementType X, List L )//精确查找函数{Position P;P = L->Next;while( P != NULL && P->Element != X ){P = P->Next;n++;}if(P==NULL)printf("查找的成员不存在！！\n\n");elseprintf("查找的成员位于链表第%d位\n\n",n); }void Delete( ElementType X, List L )//精确删除函数{Position P, TmpCell;P = FindPrevious( X, L );if( !IsLast( P, L ) ){TmpCell=P->Next;P->Next=TmpCell->Next;free( TmpCell );}}Position FindPrevious( ElementType X, List L )//前驱查找函数{Position P;P = L;while( P->Next != NULL && P->Next->Element != X )P = P->Next;return P;}void Insert( ElementType X, List L, Position P )//元素插入函数{Position TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space" );TmpCell->Element = X;TmpCell->Next = P->Next;P->Next = TmpCell;}void DeleteList( List L )//清空链表函数{Position P, Tmp;P = L->Next;L->Next = NULL;while( P != NULL ){Tmp = P->Next;free( P );P = Tmp;}if(IsEmpty(L))printf("链表清空成功！\n\n");}Position Header( List L )//表头调用函数{return L;}Position First( List L )//首元素调用函数{return L->Next;}Position Advance( Position P )//元素递进函数{return P->Next;}void show(List L)//显示链表函数{if(!IsEmpty(L)){Position p;p=First(L);printf("当前链表成员如下：\n");while(p!=NULL){printf("%d ",p->Element);if(Advance(p))p=Advance(p);else{printf("\n\n");break;}}}elseprintf("当前链表为空！！\n\n"); }void join(List L) //插入函数调用函数{int x,n,i;Position p=Header(L);printf("请输入需要插入的成员：\n");scanf("%d",&x);printf("需要将成员插入到第几位呢？\n");scanf("%d",&n);for(i=1;i<n;i++){p=p->Next;}Insert(x,L,p);show(L);}void find(List L)//查找函数调用函数{printf("请输入需要查找的成员：\n");int x;scanf("%d",&x);Find(x,L);}void count(List L)//链表长度统计函数{Position p;p=First(L);int n=0;while(p!=NULL){n++;if(Advance(p))p=Advance(p);elsebreak;}printf("当前链表长度为：%d\n\n",n);}void direction(List L)//位置访问函数{int n,i;Position p=Header(L);printf("请输入n的值：\n");scanf("%d",&n);for(i=0;i<n;i++){p=p->Next;}printf("第%d位成员为：%d\n\n",n,p->Element);}void change(List L)//修改元素函数{printf("请输入n的值：\n");int x,n,i;scanf("%d",&n);printf("请输入修改后的值：\n");scanf("%d",&x);Position p=Header(L);for(i=0;i<n;i++){p=p->Next;}p->Element=x;show(L);}void deletion(List L)//删除函数调用函数{printf("你要删除的成员是：\n");int x;scanf("%d",&x);Delete(x,L);show(L);}void main(){ List L;L=MakeEmpty(NULL);printf("请输入需要插入的成员个数：\n");int n;scanf("%d",&n);printf("请输入需要插入的成员以空格隔开：\n");int i;Position p;p=Header(L);for(i=0;i<n;i++){int x;scanf("%d",&x);Insert(x,L,p);p=Advance(p);}show(L);printf("请选择需要进行的操作：\n 1.计算链表长度\n 2.取第n个位置成员\n 3.修改第n个位置成员\n 4.在第n位插入新成员\n 5.删除成员\n 6.搜索成员\n 7.销毁链表\n 8.退出\n你输入的选项是：");scanf("%d",&n);while(n!=8){switch(n){case 1:count(L);break;case 2:direction(L);break;case 3:change(L);break;case 4:join(L);break;case 5:deletion(L);break;case 6:find(L);break;case 7:DeleteList(L);break;}printf("请选择需要进行的操作：\n 1.计算链表长度\n 2.取第n个位置成员\n 3.修改第n个位置成员\n 4.在第n位插入新成员\n 5.删除成员\n 6.搜索成员\n 7.销毁链表\n 8.退出\n你输入的选项是：");scanf("%d",&n);}}四.运行结果：1.顺序表：3.单链表：五.实验心得：通过这次写实验报告，我深切的理解了这门课的本质。