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

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

2、查找元素、判线性表是否为空；建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。（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_SIZ

3、E 100#define LISTINCREMENT 10typedef 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

4、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)

5、;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长度为:%dnn",L.length);void Tips()/提示函数 printf("请选择你的想要的操作：n"); printf("<1> 输出顺序表及顺序表的长度n"); printf("<2> 删除值为x的结点n"

6、); printf("<3> 删除给定位置i的结点n"); printf("<4> 将顺序表逆置n"); printf("<5> 将顺序表按升序排序n"); printf("<6> 将x插入到顺序表的适当位置上n"); printf("<7> 将两个有序表合并n"); printf("<0> 退出nn");status ListDelete1(SqList &L,int x)/删除值为X的元素 i

7、nt 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

8、.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.e

9、lem+j+1) t=*(L.elem+j); *(L.elem+j)=*(L.elem+j+1); *(L.elem+j+1)=t; printf("已按升序排列nn"); 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.listsi

10、ze+=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

11、=(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

12、.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

13、 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-1);/第i

14、个元素对应的下标为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("插

15、入失败!nn"); break; case 7: printf("请输入Lb的内容:n"); InitList(Lb); Build(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 *PtrToNod

16、e;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

17、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, "%sn",

18、Str ), exit( 1 )struct NodeElementType 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 =

19、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 ) P = P->Next;n+; if(P=NULL) printf("查找的成员不存在！nn");elseprintf("查找的成员位于链表第%d位nn",n); v

20、oid 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->

21、;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;voi

22、d 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( Positi

23、on 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);elseprintf("nn");break; else printf("当前链表为空！nn"); void join(List L) /插入函数调用函

24、数 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",

25、&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(List L)/位置访问函数 int n,i;Position p=Header(L);printf("请输入n的值：n");scanf("%d",&n);for(i=0;i<n;i+)

26、p=p->Next;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;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("请输入需要插