湘潭大学 数据结构实验1 实验报告 源代码 线性表基本操作

1、“数据结构和算法II”课程实验报告实验名称：线性表的存储结构定义及基本操作 班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩：-一. 实验目的：1. 掌握线性表的逻辑特征2. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算3. 熟练掌握线性表的链式存储结构定义及基本操作4. 理解循环链表和双链表的特点和基本运算5. 加深对栈结构的理解，培养解决实际问题的编程能力。6. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二. 实验内容：（1）基本实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、

2、查找元素、判线性表是否为空；建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。（2）扩展实验内容：查前驱元素、查后继元素、顺序表合并，两个有序单链表的合并操作等。三. 程序及注释：1. 顺序表：#include#include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10ty

3、pedef int status ;typedef int ElemType ;typedef structElemType *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(

4、请输入元素个数n和n个元素n);scanf(%d,&n);if(nLIST_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;in;i+)scanf(%d,L.elem+i);L.length=n;return OK;void Print(SqList &L)/输出表中元素和长度 int i; for(i=0;iL.length;i+) prin

5、tf(%d ,*(L.elem+i); printf(n长度为:%dnn,L.length);void Tips()/提示函数 printf(请选择你的想要的操作：n); printf( 输出顺序表及顺序表的长度n); printf( 删除值为x的结点n); printf( 删除给定位置i的结点n); printf( 将顺序表逆置n); printf( 将顺序表按升序排序n); printf( 将x插入到顺序表的适当位置上n); printf( 将两个有序表合并n); printf( 退出nn);status ListDelete1(SqList &L,int x)/删除值为X的元素 int

6、i; for(i=0;iL.length;i+) if(*(L.elem+i)=x) break; if(i=L.length) return ERROR; for(i+;iL.length;i+) *(L.elem+i-1)=*(L.elem+i); L.length-; return OK; status ListDelete2(SqList &L,int x)/删除第X个元素 int i; if(x=L.length) return ERROR; for(i=x+1;iL.length;i+) *(L.elem+i-1)=*(L.elem+i); L.length-; return OK

7、; void Inverse(SqList &L)/逆置函数 int i,t; for(i=0;iL.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;iL.length;i+) for(j=0;j*(L.elem+j+1) t=*(L.elem+j); *(L.elem+j)=*(L.elem+j+1); *(L.elem+j+1)=t; printf(已按升序排列nn

8、); 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;iL.length;i+) if(xk;i-) *(L.elem+i)=*(L.elem+i-1); *(L.elem+k)=x; L.length+;

9、 return OK; status Merger(SqList &L,SqList &Lb)/合并两个线性表 int i,j,k; SqList Lc; InitList(Lc); if(Lc.listsizeL.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; wh

10、ile(iL.length & jLb.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(iL.length) *(Lc.elem+k)=*(L.elem+i); k+;i+; while(jLb.length) *(Lc.elem+k)=*(Lb.elem+j); k+;j+; Lc.length=L.length+Lb.length; L=Lc; return OK; int main() int op,x,fla

11、g; SqList L,Lb; InitList(L); Build(L); Tips(); scanf(%d,&op); while(op) switch(op) case 1: Print(L); break; case 2: printf(请输入要删除的数据X:n); scanf(%d,&x); flag=ListDelete1(L,x); if(flag) printf(删除成功!nn); else printf(元素不存在,删除失败!nn); break; case 3: printf(请输入要删除的位置i:n); scanf(%d,&x); flag=ListDelete2(L,x

12、-1);/第i个元素对应的下标为i-1 if(flag) printf(删除成功!nn); else printf(元素不存在,删除失败!nn); 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(插入成功!nn); else printf(插入失败!nn); break; case 7: printf(请输入Lb的内容:n); InitList(Lb); Build

13、(Lb); flag=Merger(L,Lb); if(flag) printf(合并成功!nn); break; Tips(); scanf(%d,&op); return 0;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

14、( 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

15、 );ElementType Retrieve( Position P );#endif#include #include #define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, %sn, Str ), exit( 1 )struct NodeElementType Element; Position Next;List MakeEmpty( List L ) /创建空链表 if( L != NULL ) DeleteList( L ); L = malloc( sizeof( struc

16、t 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; int n=1; P = L-Next; while( P != NULL & P-Element != X )

17、 P = P-Next;n+; if(P=NULL) printf(查找的成员不存在！nn);elseprintf(查找的成员位于链表第%d位nn,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 )/前驱查找函数 Pos

18、ition 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

19、 = 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(链表清空成功！nn);Position Header( List L )/表头调用函数 return L;Position First( List L )/首元素调用函数 return L-Next;Position Advance( Position P )/元素递进函数

20、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);elseprintf(nn);break; else printf(当前链表为空！nn); void join(List L) /插入函数调用函数 int x,n,i;Position p=Header(L);printf(请输入需要插入的成员：n);scanf(%d,&x);pri

21、ntf(需要将成员插入到第几位呢？n); scanf(%d,&n);for(i=1;iNext;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(当前链表长度为：%dnn,n);void direction(Lis

22、t L)/位置访问函数 int n,i;Position p=Header(L);printf(请输入n的值：n);scanf(%d,&n);for(i=0;iNext;printf(第%d位成员为：%dnn,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;iNext;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;in;i